tools/ucl/src/n2_99.ch

   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