Subversion Repositories freemyipod

Rev

Rev 184 | Details | Compare with Previous | Last modification | View Log | RSS feed

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