Subversion Repositories freemyipod

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
65 cmwslw 1 
/* n2_99.ch -- implementation of the NRV2[BDE]-99 compression algorithms
2 
 
3 
   This file is part of the UCL data compression library.
4 
 
5 
   Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer
6 
   All Rights Reserved.
7 
 
8 
   The UCL library is free software; you can redistribute it and/or
9 
   modify it under the terms of the GNU General Public License as
10 
   published by the Free Software Foundation; either version 2 of
11 
   the License, or (at your option) any later version.
12 
 
13 
   The UCL library is distributed in the hope that it will be useful,
14 
   but WITHOUT ANY WARRANTY; without even the implied warranty of
15 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 
   GNU General Public License for more details.
17 
 
18 
   You should have received a copy of the GNU General Public License
19 
   along with the UCL library; see the file COPYING.
20 
   If not, write to the Free Software Foundation, Inc.,
21 
   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 
 
23 
   Markus F.X.J. Oberhumer
24 
   <markus@oberhumer.com>
25 
   http://www.oberhumer.com/opensource/ucl/
26 
 */
27 
 
28 
 
29 
 
30 
#include <ucl/uclconf.h>
31 
#include <ucl/ucl.h>
32 
#include "ucl_conf.h"
33 
 
34 
#if 0
35 
#undef UCL_DEBUG
36 
#define UCL_DEBUG
37 
#endif
38 
 
39 
#include <stdio.h>
40 
 
41 
#if 0 && !defined(UCL_DEBUG)
42 
#undef NDEBUG
43 
#include <assert.h>
44 
#endif
45 
 
46 
 
47 
/***********************************************************************
48 
//
49 
************************************************************************/
50 
 
51 
#if 0
52 
#define N       (128*1024ul)        /* size of ring buffer */
53 
#else
54 
#define N       (1024*1024ul)       /* size of ring buffer */
55 
#define SWD_USE_MALLOC
56 
#define SWD_HSIZE   65536ul
57 
#endif
58 
#define THRESHOLD       1           /* lower limit for match length */
59 
#define F            2048           /* upper limit for match length */
60 
 
61 
#if defined(NRV2B)
62 
#  define UCL_COMPRESS_T                ucl_nrv2b_t
63 
#  define ucl_swd_t                     ucl_nrv2b_swd_t
64 
#  define ucl_nrv_99_compress           ucl_nrv2b_99_compress
65 
#  define M2_MAX_OFFSET                 0xd00
66 
#elif defined(NRV2D)
67 
#  define UCL_COMPRESS_T                ucl_nrv2d_t
68 
#  define ucl_swd_t                     ucl_nrv2d_swd_t
69 
#  define ucl_nrv_99_compress           ucl_nrv2d_99_compress
70 
#  define M2_MAX_OFFSET                 0x500
71 
#elif defined(NRV2E)
72 
#  define UCL_COMPRESS_T                ucl_nrv2e_t
73 
#  define ucl_swd_t                     ucl_nrv2e_swd_t
74 
#  define ucl_nrv_99_compress           ucl_nrv2e_99_compress
75 
#  define M2_MAX_OFFSET                 0x500
76 
#else
77 
#  error
78 
#endif
79 
#define ucl_swd_p       ucl_swd_t * __UCL_MMODEL
80 
 
81 
#if 0
82 
#  define HEAD3(b,p) \
83 
    ((((((ucl_uint32)b[p]<<3)^b[p+1])<<3)^b[p+2]) & (SWD_HSIZE-1))
84 
#endif
85 
#if 0 && defined(UCL_UNALIGNED_OK_4) && (UCL_BYTE_ORDER == UCL_LITTLE_ENDIAN)
86 
#  define HEAD3(b,p) \
87 
    (((* (ucl_uint32p) &b[p]) ^ ((* (ucl_uint32p) &b[p])>>10)) & (SWD_HSIZE-1))
88 
#endif
89 
 
90 
#include "ucl_mchw.ch"
91 
 
92 
 
93 
/***********************************************************************
94 
//
95 
************************************************************************/
96 
 
97 
static void code_prefix_ss11(UCL_COMPRESS_T *c, ucl_uint32 i)
98 
{
99 
    if (i >= 2)
100 
    {
101 
        ucl_uint32 t = 4;
102 
        i += 2;
103 
        do {
104 
            t <<= 1;
105 
        } while (i >= t);
106 
        t >>= 1;
107 
        do {
108 
            t >>= 1;
109 
            bbPutBit(c, (i & t) ? 1 : 0);
110 
            bbPutBit(c, 0);
111 
        } while (t > 2);
112 
    }
113 
    bbPutBit(c, (unsigned)i & 1);
114 
    bbPutBit(c, 1);
115 
}
116 
 
117 
 
118 
#if defined(NRV2D) || defined(NRV2E)
119 
static void code_prefix_ss12(UCL_COMPRESS_T *c, ucl_uint32 i)
120 
{
121 
    if (i >= 2)
122 
    {
123 
        ucl_uint32 t = 2;
124 
        do {
125 
            i -= t;
126 
            t <<= 2;
127 
        } while (i >= t);
128 
        do {
129 
            t >>= 1;
130 
            bbPutBit(c, (i & t) ? 1 : 0);
131 
            bbPutBit(c, 0);
132 
            t >>= 1;
133 
            bbPutBit(c, (i & t) ? 1 : 0);
134 
        } while (t > 2);
135 
    }
136 
    bbPutBit(c, (unsigned)i & 1);
137 
    bbPutBit(c, 1);
138 
}
139 
#endif
140 
 
141 
 
142 
static void
143 
code_match(UCL_COMPRESS_T *c, ucl_uint m_len, const ucl_uint m_off)
144 
{
145 
    unsigned m_low = 0;
146 
 
147 
    while (m_len > c->conf.max_match)
148 
    {
149 
        code_match(c, c->conf.max_match - 3, m_off);
150 
        m_len -= c->conf.max_match - 3;
151 
    }
152 
 
153 
    c->match_bytes += m_len;
154 
    if (m_len > c->result[3])
155 
        c->result[3] = m_len;
156 
    if (m_off > c->result[1])
157 
        c->result[1] = m_off;
158 
 
159 
    bbPutBit(c, 0);
160 
 
161 
#if defined(NRV2B)
162 
    if (m_off == c->last_m_off)
163 
    {
164 
        bbPutBit(c, 0);
165 
        bbPutBit(c, 1);
166 
    }
167 
    else
168 
    {
169 
        code_prefix_ss11(c, 1 + ((m_off - 1) >> 8));
170 
        bbPutByte(c, (unsigned)m_off - 1);
171 
    }
172 
    m_len = m_len - 1 - (m_off > M2_MAX_OFFSET);
173 
    if (m_len >= 4)
174 
    {
175 
        bbPutBit(c,0);
176 
        bbPutBit(c,0);
177 
        code_prefix_ss11(c, m_len - 4);
178 
    }
179 
    else
180 
    {
181 
        bbPutBit(c, m_len > 1);
182 
        bbPutBit(c, (unsigned)m_len & 1);
183 
    }
184 
#elif defined(NRV2D)
185 
    m_len = m_len - 1 - (m_off > M2_MAX_OFFSET);
186 
    assert(m_len > 0);
187 
    m_low = (m_len >= 4) ? 0u : (unsigned) m_len;
188 
    if (m_off == c->last_m_off)
189 
    {
190 
        bbPutBit(c, 0);
191 
        bbPutBit(c, 1);
192 
        bbPutBit(c, m_low > 1);
193 
        bbPutBit(c, m_low & 1);
194 
    }
195 
    else
196 
    {
197 
        code_prefix_ss12(c, 1 + ((m_off - 1) >> 7));
198 
        bbPutByte(c, ((((unsigned)m_off - 1) & 0x7f) << 1) | ((m_low > 1) ? 0 : 1));
199 
        bbPutBit(c, m_low & 1);
200 
    }
201 
    if (m_len >= 4)
202 
        code_prefix_ss11(c, m_len - 4);
203 
#elif defined(NRV2E)
204 
    m_len = m_len - 1 - (m_off > M2_MAX_OFFSET);
205 
    assert(m_len > 0);
206 
    m_low = (m_len <= 2);
207 
    if (m_off == c->last_m_off)
208 
    {
209 
        bbPutBit(c, 0);
210 
        bbPutBit(c, 1);
211 
        bbPutBit(c, m_low);
212 
    }
213 
    else
214 
    {
215 
        code_prefix_ss12(c, 1 + ((m_off - 1) >> 7));
216 
        bbPutByte(c, ((((unsigned)m_off - 1) & 0x7f) << 1) | (m_low ^ 1));
217 
    }
218 
    if (m_low)
219 
        bbPutBit(c, (unsigned)m_len - 1);
220 
    else if (m_len <= 4)
221 
    {
222 
        bbPutBit(c, 1);
223 
        bbPutBit(c, (unsigned)m_len - 3);
224 
    }
225 
    else
226 
    {
227 
        bbPutBit(c, 0);
228 
        code_prefix_ss11(c, m_len - 5);
229 
    }
230 
#else
231 
#  error
232 
#endif
233 
 
234 
    c->last_m_off = m_off;
235 
    UCL_UNUSED(m_low);
236 
}
237 
 
238 
 
239 
static void
240 
code_run(UCL_COMPRESS_T *c, const ucl_byte *ii, ucl_uint lit)
241 
{
242 
    if (lit == 0)
243 
        return;
244 
    c->lit_bytes += lit;
245 
    if (lit > c->result[5])
246 
        c->result[5] = lit;
247 
    do {
248 
        bbPutBit(c, 1);
249 
        bbPutByte(c, *ii++);
250 
    } while (--lit > 0);
251 
}
252 
 
253 
 
254 
/***********************************************************************
255 
//
256 
************************************************************************/
257 
 
258 
static int
259 
len_of_coded_match(UCL_COMPRESS_T *c, ucl_uint m_len, ucl_uint m_off)
260 
{
261 
    int b;
262 
    if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
263 
        || m_off > c->conf.max_offset)
264 
        return -1;
265 
    assert(m_off > 0);
266 
 
267 
    m_len = m_len - 2 - (m_off > M2_MAX_OFFSET);
268 
 
269 
    if (m_off == c->last_m_off)
270 
        b = 1 + 2;
271 
    else
272 
    {
273 
#if defined(NRV2B)
274 
        b = 1 + 10;
275 
        m_off = (m_off - 1) >> 8;
276 
        while (m_off > 0)
277 
        {
278 
            b += 2;
279 
            m_off >>= 1;
280 
        }
281 
#elif defined(NRV2D) || defined(NRV2E)
282 
        b = 1 + 9;
283 
        m_off = (m_off - 1) >> 7;
284 
        while (m_off > 0)
285 
        {
286 
            b += 3;
287 
            m_off >>= 2;
288 
        }
289 
#else
290 
#  error
291 
#endif
292 
    }
293 
 
294 
#if defined(NRV2B) || defined(NRV2D)
295 
    b += 2;
296 
    if (m_len < 3)
297 
        return b;
298 
    m_len -= 3;
299 
#elif defined(NRV2E)
300 
    b += 2;
301 
    if (m_len < 2)
302 
        return b;
303 
    if (m_len < 4)
304 
        return b + 1;
305 
    m_len -= 4;
306 
#else
307 
#  error
308 
#endif
309 
    do {
310 
        b += 2;
311 
        m_len >>= 1;
312 
    } while (m_len > 0);
313 
 
314 
    return b;
315 
}
316 
 
317 
 
318 
/***********************************************************************
319 
//
320 
************************************************************************/
321 
 
322 
#if !defined(NDEBUG)
323 
static
324 
void assert_match( const ucl_swd_p swd, ucl_uint m_len, ucl_uint m_off )
325 
{
326 
    const UCL_COMPRESS_T *c = swd->c;
327 
    ucl_uint d_off;
328 
 
329 
    assert(m_len >= 2);
330 
    if (m_off <= (ucl_uint) (c->bp - c->in))
331 
    {
332 
        assert(c->bp - m_off + m_len < c->ip);
333 
        assert(ucl_memcmp(c->bp, c->bp - m_off, m_len) == 0);
334 
    }
335 
    else
336 
    {
337 
        assert(swd->dict != NULL);
338 
        d_off = m_off - (ucl_uint) (c->bp - c->in);
339 
        assert(d_off <= swd->dict_len);
340 
        if (m_len > d_off)
341 
        {
342 
            assert(ucl_memcmp(c->bp, swd->dict_end - d_off, d_off) == 0);
343 
            assert(c->in + m_len - d_off < c->ip);
344 
            assert(ucl_memcmp(c->bp + d_off, c->in, m_len - d_off) == 0);
345 
        }
346 
        else
347 
        {
348 
            assert(ucl_memcmp(c->bp, swd->dict_end - d_off, m_len) == 0);
349 
        }
350 
    }
351 
}
352 
#else
353 
#  define assert_match(a,b,c)   ((void)0)
354 
#endif
355 
 
356 
 
357 
#if defined(SWD_BEST_OFF)
358 
 
359 
static void
360 
better_match ( const ucl_swd_p swd, ucl_uint *m_len, ucl_uint *m_off )
361 
{
362 
}
363 
 
364 
#endif
365 
 
366 
 
367 
/***********************************************************************
368 
//
369 
************************************************************************/
370 
 
371 
UCL_PUBLIC(int)
372 
ucl_nrv_99_compress        ( const ucl_bytep in, ucl_uint in_len,
373 
                                   ucl_bytep out, ucl_uintp out_len,
374 
                                   ucl_progress_callback_p cb,
375 
                                   int level,
376 
                             const struct ucl_compress_config_p conf,
377 
                                   ucl_uintp result)
378 
{
379 
    const ucl_byte *ii;
380 
    ucl_uint lit;
381 
    ucl_uint m_len, m_off;
382 
    UCL_COMPRESS_T c_buffer;
383 
    UCL_COMPRESS_T * const c = &c_buffer;
384 
#undef swd
385 
#if 1 && defined(SWD_USE_MALLOC)
386 
    ucl_swd_t the_swd;
387 
#   define swd (&the_swd)
388 
#else
389 
    ucl_swd_p swd;
390 
#endif
391 
    ucl_uint result_buffer[16];
392 
    int r;
393 
 
394 
    struct swd_config_t
395 
    {
396 
        unsigned try_lazy;
397 
        ucl_uint good_length;
398 
        ucl_uint max_lazy;
399 
        ucl_uint nice_length;
400 
        ucl_uint max_chain;
401 
        ucl_uint32 flags;
402 
        ucl_uint32 max_offset;
403 
    };
404 
    const struct swd_config_t *sc;
405 
    static const struct swd_config_t swd_config[10] = {
406 
        /* faster compression */
407 
        {   0,   0,   0,   8,    4,   0,  48*1024L },
408 
        {   0,   0,   0,  16,    8,   0,  48*1024L },
409 
        {   0,   0,   0,  32,   16,   0,  48*1024L },
410 
        {   1,   4,   4,  16,   16,   0,  48*1024L },
411 
        {   1,   8,  16,  32,   32,   0,  48*1024L },
412 
        {   1,   8,  16, 128,  128,   0,  48*1024L },
413 
        {   2,   8,  32, 128,  256,   0, 128*1024L },
414 
        {   2,  32, 128,   F, 2048,   1, 128*1024L },
415 
        {   2,  32, 128,   F, 2048,   1, 256*1024L },
416 
        {   2,   F,   F,   F, 4096,   1, N }
417 
        /* max. compression */
418 
    };
419 
 
420 
    if (level < 1 || level > 10)
421 
        return UCL_E_INVALID_ARGUMENT;
422 
    sc = &swd_config[level - 1];
423 
 
424 
    memset(c, 0, sizeof(*c));
425 
    c->ip = c->in = in;
426 
    c->in_end = in + in_len;
427 
    c->out = out;
428 
    if (cb && cb->callback)
429 
        c->cb = cb;
430 
    cb = NULL;
431 
    c->result = result ? result : (ucl_uintp) result_buffer;
432 
    memset(c->result, 0, 16*sizeof(*c->result));
433 
    c->result[0] = c->result[2] = c->result[4] = UCL_UINT_MAX;
434 
    result = NULL;
435 
    memset(&c->conf, 0xff, sizeof(c->conf));
436 
    if (conf)
437 
        memcpy(&c->conf, conf, sizeof(c->conf));
438 
    conf = NULL;
439 
    r = bbConfig(c, 0, 8);
440 
    if (r == 0)
441 
        r = bbConfig(c, c->conf.bb_endian, c->conf.bb_size);
442 
    if (r != 0)
443 
        return UCL_E_INVALID_ARGUMENT;
444 
    c->bb_op = out;
445 
 
446 
    ii = c->ip;             /* point to start of literal run */
447 
    lit = 0;
448 
 
449 
#if !defined(swd)
450 
    swd = (ucl_swd_p) ucl_alloc(1, ucl_sizeof(*swd));
451 
    if (!swd)
452 
        return UCL_E_OUT_OF_MEMORY;
453 
#endif
454 
    swd->f = UCL_MIN(F, c->conf.max_match);
455 
    swd->n = UCL_MIN(N, sc->max_offset);
456 
    if (c->conf.max_offset != UCL_UINT_MAX)
457 
        swd->n = UCL_MIN(N, c->conf.max_offset);
458 
    if (in_len >= 256 && in_len < swd->n)
459 
        swd->n = in_len;
460 
    if (swd->f < 8 || swd->n < 256)
461 
        return UCL_E_INVALID_ARGUMENT;
462 
    r = init_match(c,swd,NULL,0,sc->flags);
463 
    if (r != UCL_E_OK)
464 
    {
465 
#if !defined(swd)
466 
        ucl_free(swd);
467 
#endif
468 
        return r;
469 
    }
470 
    if (sc->max_chain > 0)
471 
        swd->max_chain = sc->max_chain;
472 
    if (sc->nice_length > 0)
473 
        swd->nice_length = sc->nice_length;
474 
    if (c->conf.max_match < swd->nice_length)
475 
        swd->nice_length = c->conf.max_match;
476 
 
477 
    if (c->cb)
478 
        (*c->cb->callback)(0,0,-1,c->cb->user);
479 
 
480 
    c->last_m_off = 1;
481 
    r = find_match(c,swd,0,0);
482 
    if (r != UCL_E_OK)
483 
        return r;
484 
    while (c->look > 0)
485 
    {
486 
        ucl_uint ahead;
487 
        ucl_uint max_ahead;
488 
        int l1, l2;
489 
 
490 
        c->codesize = c->bb_op - out;
491 
 
492 
        m_len = c->m_len;
493 
        m_off = c->m_off;
494 
 
495 
        assert(c->bp == c->ip - c->look);
496 
        assert(c->bp >= in);
497 
        if (lit == 0)
498 
            ii = c->bp;
499 
        assert(ii + lit == c->bp);
500 
        assert(swd->b_char == *(c->bp));
501 
 
502 
        if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
503 
            || m_off > c->conf.max_offset)
504 
        {
505 
            /* a literal */
506 
            lit++;
507 
            swd->max_chain = sc->max_chain;
508 
            r = find_match(c,swd,1,0);
509 
            assert(r == 0);
510 
            continue;
511 
        }
512 
 
513 
    /* a match */
514 
#if defined(SWD_BEST_OFF)
515 
        if (swd->use_best_off)
516 
            better_match(swd,&m_len,&m_off);
517 
#endif
518 
        assert_match(swd,m_len,m_off);
519 
 
520 
        /* shall we try a lazy match ? */
521 
        ahead = 0;
522 
        if (sc->try_lazy <= 0 || m_len >= sc->max_lazy || m_off == c->last_m_off)
523 
        {
524 
            /* no */
525 
            l1 = 0;
526 
            max_ahead = 0;
527 
        }
528 
        else
529 
        {
530 
            /* yes, try a lazy match */
531 
            l1 = len_of_coded_match(c,m_len,m_off);
532 
            assert(l1 > 0);
533 
            max_ahead = UCL_MIN(sc->try_lazy, m_len - 1);
534 
        }
535 
 
536 
        while (ahead < max_ahead && c->look > m_len)
537 
        {
538 
            if (m_len >= sc->good_length)
539 
                swd->max_chain = sc->max_chain >> 2;
540 
            else
541 
                swd->max_chain = sc->max_chain;
542 
            r = find_match(c,swd,1,0);
543 
            ahead++;
544 
 
545 
            assert(r == 0);
546 
            assert(c->look > 0);
547 
            assert(ii + lit + ahead == c->bp);
548 
 
549 
            if (c->m_len < 2)
550 
                continue;
551 
#if defined(SWD_BEST_OFF)
552 
            if (swd->use_best_off)
553 
                better_match(swd,&c->m_len,&c->m_off);
554 
#endif
555 
            l2 = len_of_coded_match(c,c->m_len,c->m_off);
556 
            if (l2 < 0)
557 
                continue;
558 
#if 1
559 
            if (l1 + (int)(ahead + c->m_len - m_len) * 5 > l2 + (int)(ahead) * 9)
560 
#else
561 
            if (l1 > l2)
562 
#endif
563 
            {
564 
                c->lazy++;
565 
                assert_match(swd,c->m_len,c->m_off);
566 
 
567 
#if 0
568 
                if (l3 > 0)
569 
                {
570 
                    /* code previous run */
571 
                    code_run(c,ii,lit);
572 
                    lit = 0;
573 
                    /* code shortened match */
574 
                    code_match(c,ahead,m_off);
575 
                }
576 
                else
577 
#endif
578 
                {
579 
                    lit += ahead;
580 
                    assert(ii + lit == c->bp);
581 
                }
582 
                goto lazy_match_done;
583 
            }
584 
        }
585 
 
586 
        assert(ii + lit + ahead == c->bp);
587 
 
588 
        /* 1 - code run */
589 
        code_run(c,ii,lit);
590 
        lit = 0;
591 
 
592 
        /* 2 - code match */
593 
        code_match(c,m_len,m_off);
594 
        swd->max_chain = sc->max_chain;
595 
        r = find_match(c,swd,m_len,1+ahead);
596 
        assert(r == 0);
597 
 
598 
lazy_match_done: ;
599 
    }
600 
 
601 
    /* store final run */
602 
    code_run(c,ii,lit);
603 
 
604 
    /* EOF */
605 
    bbPutBit(c, 0);
606 
#if defined(NRV2B)
607 
    code_prefix_ss11(c, UCL_UINT32_C(0x1000000));
608 
    bbPutByte(c, 0xff);
609 
#elif defined(NRV2D) || defined(NRV2E)
610 
    code_prefix_ss12(c, UCL_UINT32_C(0x1000000));
611 
    bbPutByte(c, 0xff);
612 
#else
613 
#  error
614 
#endif
615 
    bbFlushBits(c, 0);
616 
 
617 
    assert(c->textsize == in_len);
618 
    c->codesize = c->bb_op - out;
619 
    *out_len = c->bb_op - out;
620 
    if (c->cb)
621 
        (*c->cb->callback)(c->textsize,c->codesize,4,c->cb->user);
622 
 
623 
#if 0
624 
    printf("%7ld %7ld -> %7ld   %7ld %7ld   %ld  (max: %d %d %d)\n",
625 
          (long) c->textsize, (long) in_len, (long) c->codesize,
626 
           c->match_bytes, c->lit_bytes,  c->lazy,
627 
           c->result[1], c->result[3], c->result[5]);
628 
#endif
629 
    assert(c->lit_bytes + c->match_bytes == in_len);
630 
 
631 
    swd_exit(swd);
632 
#if !defined(swd)
633 
    ucl_free(swd);
634 
#endif
635 
    return UCL_E_OK;
636 
#undef swd
637 
}
638 
 
639 
 
640 
/*
641 
vi:ts=4:et
642 
*/
643