src/tbdecode.h

   1 #ifndef TBDECODE
   2 #define TBDECODE
   3
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7 #include <time.h>
   8 #ifndef CLOCKS_PER_SEC
   9 #define CLOCKS_PER_SEC CLK_TCK
  10 #endif
  11
  12 /* ---------------------------- Error codes --------------------------- */
  13 /*                              -----------                             */
  14
  15 #define COMP_ERR_NONE     0     /* everything is OK                     */
  16 #define COMP_ERR_READ     2     /* input file read error                */
  17 #define COMP_ERR_NOMEM    5     /* no enough memory                     */
  18 #define COMP_ERR_BROKEN   6     /* damaged compressed data              */
  19 #define COMP_ERR_PARAM    7     /* incorrect function parameter         */
  20 #define COMP_ERR_INTERNAL 9     /* everything else is internal error    */
  21                                 /* hopefully it should never happen     */
  22
  23 /* Almost all  functions listed further return one as  its result on of */
  24 /* codes given  above: if no  error occured then COMP_ERR_NONE (i.e. 0) */
  25 /* is returned, otherwise functions return  error  code  plus number of */
  26 /* line in "comp.c"  where the error  was detected multiplied  by  256; */
  27 /* line number may  be  used for exact specification  of  a place where */
  28 /* error was detected thus making debugging slightly simpler.           */
  29 /*                                                                      */
  30 /* Thus, "(code &  0xff)"  gives proper error code,  and  "(code >> 8)" */
  31 /* gives number of line where the error was raised.                     */
  32
  33 /* -------------------------------------------------------------------- */
  34 /*                                                                      */
  35 /*                Compress/decompress some chess tables                 */
  36 /*                                                                      */
  37 /*               Copyright (c) 1991--1998 Andrew Kadatch                */
  38 /*                                                                      */
  39 /* The Limited-Reference  variant  of  Lempel-Ziv algorithm implemented */
  40 /* here was first described in  my  B.Sc.  thesis "Efficient algorithms */
  41 /* for image  compression",  Novosibirsk  State  University,  1992, and */
  42 /* cannot be  used in any product distributed in  Russia or CIS without */
  43 /* written permission from the author.                                  */
  44 /*                                                                      */
  45 /* Most of the code listed below is significantly  simplified code from  */
  46 /* the PRS data compression library and therefore it should not be used */
  47 /* in any product (software or hardware, commercial or not, and  so on) */
  48 /* without written permission from the author.                          */
  49 /*                                                                      */
  50 /* -------------------------------------------------------------------- */
  51
  52 /* ---------------------------- Debugging ----------------------------- */
  53 /*                              ---------                               */
  54
  55 #ifndef DEBUG
  56 #define DEBUG   0
  57 #endif
  58
  59 #if DEBUG
  60 #define assert(cond) ((cond) ? (void) 0 : _local_assert (__LINE__))
  61 static void _local_assert(int lineno)
  62 {
  63   fprintf(stderr, "assertion at line %u failed\n", lineno);
  64   exit(33);
  65 }
  66
  67 #define debug(x) x
  68 #define dprintf(x) printf x
  69 #else
  70 #if !defined (assert)
  71 #define assert(cond) ((void) 0)
  72 #endif
  73 #define debug(x)     ((void) 0)
  74 #define dprintf(x)   ((void) 0)
  75 #endif
  76
  77 /* mob_pach */
  78 #ifndef  __cplusplus
  79 int       cbEGTBCompBytes = 0;
  80 #else
  81 extern    "C" {
  82   int       cbEGTBCompBytes = 0;
  83 }
  84 #endif
  85 /* --------------------- Constants, types, etc. ----------------------- */
  86 /*                       ----------------------                         */
  87 #define MIN_BLOCK_BITS  8       /* LOG2 (min size of block to compress) */
  88 #define MAX_BLOCK_BITS  16      /* LOG2 (max size of block to compress) */
  89                         /* max. integer we can take LOG2 by table       */
  90 #define MAX_BITS_HALF   ((MAX_BLOCK_BITS + 1) >> 1)
  91 #define MAX_BITS        (MAX_BITS_HALF * 2)
  92 /* assume that integer is at least 32 bits wide */
  93 #ifndef uint
  94 #define uint unsigned
  95 #endif
  96 #ifndef uchar
  97 #define uchar unsigned char
  98 #endif
  99 #define HEADER_SIZE             80      /* number of reserved bytes     */
 100 #define STOP_SEARCH_LENGTH      256     /* terminate search if match    */
 101                                         /* length exceeds that value    */
 102 #define MAX_LENGTH_BITS         5
 103 #define MAX_LENGTH              (1 << MAX_LENGTH_BITS)
 104 #define LONG_BITS               1
 105 #define LONG_LENGTH             (MAX_BLOCK_BITS - LONG_BITS)
 106 #define LONG_QUICK              (MAX_LENGTH - LONG_LENGTH)
 107 #if LONG_LENGTH > (MAX_BLOCK_BITS - LONG_BITS)
 108 #  undef LONG_LENGTH
 109 #  define LONG_LENGTH           (MAX_BLOCK_BITS - LONG_BITS)
 110 #endif
 111 #if LONG_LENGTH >= MAX_LENGTH || LONG_LENGTH <= 0
 112 #error LONG_LENGTH is out of range
 113 #endif
 114 #if LONG_BITS <= 0
 115 #error LONG_BITS must be positive
 116 #endif
 117 #define DELTA   (LONG_BITS + LONG_QUICK - 1)
 118 #if (MAX_LENGTH - 1) - (LONG_LENGTH - LONG_BITS) != DELTA
 119 #error Hmmm
 120 #endif
 121 #define MAX_DISTANCES           24
 122 #define LOG_MAX_DISTANCES       6       /* see check below      */
 123 #if MAX_DISTANCES > (1 << LOG_MAX_DISTANCES)
 124 #error MAX_DISTANCES should not exceed (1 << LOG_MAX_DISTANCES)
 125 #endif
 126 #define ALPHABET_SIZE           (256 + (MAX_DISTANCES << MAX_LENGTH_BITS))
 127 #define MAX_ALPHABET    ALPHABET_SIZE   /* max. alphabet handled by     */
 128                                         /* Huffman coding routines      */
 129 #define USE_CRC32               1
 130 /* 0 - use Fletcher's checksum, != 0 - use proper CRC32                 */
 131     static uchar header_title[64] =
 132     "Compressed by DATACOMP v 1.0 (c) 1991--1998 Andrew Kadatch\r\n\0";
 133
 134 #define RET(n) ((n) + __LINE__ * 256)
 135
 136 /* ------------------------- CRC32 routines --------------------------- */
 137 /*                           --------------                             */
 138
 139 #if USE_CRC32
 140
 141 static unsigned CRC32_table[256];
 142 static int CRC32_initialized = 0;
 143
 144 static void CRC32_init(void)
 145 {
 146   int       i, j;
 147   unsigned  k, m = (unsigned) 0xedb88320L;
 148
 149   if (CRC32_initialized)
 150     return;
 151   for (i = 0; i < 256; ++i) {
 152     k = i;
 153     j = 8;
 154     do {
 155       if ((k & 1) != 0)
 156         k >>= 1;
 157       else {
 158         k >>= 1;
 159         k ^= m;
 160       };
 161     }
 162     while (--j);
 163     CRC32_table[i] = k;
 164   }
 165   CRC32_initialized = 1;
 166 }
 167
 168 static unsigned CRC32(uchar * p, int n, unsigned k)
 169 {
 170   unsigned *table = CRC32_table;
 171   uchar    *e = p + n;
 172
 173   while (p + 16 < e) {
 174 #   define X(i) k = table[((uchar) k) ^ p[i]] ^ (k >> 8)
 175     X(0);
 176     X(1);
 177     X(2);
 178     X(3);
 179     X(4);
 180     X(5);
 181     X(6);
 182     X(7);
 183     X(8);
 184     X(9);
 185     X(10);
 186     X(11);
 187     X(12);
 188     X(13);
 189     X(14);
 190     X(15);
 191 #   undef X
 192     p += 16;
 193   }
 194   while (p < e)
 195     k = table[((uchar) k) ^ *p++] ^ (k >> 8);
 196   return (k);
 197 }
 198
 199 #else
 200
 201 #define CRC32_init()
 202
 203 static unsigned CRC32(uchar * p, int n, unsigned k1)
 204 {
 205   unsigned  k0 = k1 & 0xffff;
 206   uchar    *e = p + n;
 207
 208   k1 = (k1 >> 16) & 0xffff;
 209   while (p + 16 < e) {
 210 #   define X(i) k0 += p[i]; k1 += k0;
 211     X(0);
 212     X(1);
 213     X(2);
 214     X(3);
 215     X(4);
 216     X(5);
 217     X(6);
 218     X(7);
 219     X(8);
 220     X(9);
 221     X(10);
 222     X(11);
 223     X(12);
 224     X(13);
 225     X(14);
 226     X(15);
 227 #   undef X
 228     k0 = (k0 & 0xffff) + (k0 >> 16);
 229     k1 = (k1 & 0xffff) + (k1 >> 16);
 230     p += 16;
 231   }
 232   while (p < e) {
 233     k0 += *p++;
 234     k1 += k0;
 235   }
 236   k0 = (k0 & 0xffff) + (k0 >> 16);
 237   k1 = (k1 & 0xffff) + (k1 >> 16);
 238   k0 = (k0 & 0xffff) + (k0 >> 16);
 239   k1 = (k1 & 0xffff) + (k1 >> 16);
 240   assert(((k0 | k1) >> 16) == 0);
 241   return (k0 + (k1 << 16));
 242 }
 243
 244 #endif                          /* USE_CRC32    */
 245
 246 /* ------------------------ Bit IO interface -------------------------- */
 247 /*                          ----------------                            */
 248
 249 #define BITIO_LOCALS    \
 250   uint   _mask;         \
 251   int    _bits;         \
 252   uchar *_ptr
 253
 254 typedef struct {
 255   BITIO_LOCALS;
 256 } bitio_t;
 257
 258 #define BITIO_ENTER(p) do {     \
 259   _mask = (p)._mask;            \
 260   _bits = (p)._bits;            \
 261   _ptr  = (p)._ptr;             \
 262 } while (0)
 263
 264 #define BITIO_LEAVE(p) do {     \
 265   (p)._mask = _mask;            \
 266   (p)._bits = _bits;            \
 267   (p)._ptr  = _ptr;             \
 268 } while (0)
 269
 270 #define BIORD_START(from) do {          \
 271   _ptr = (uchar *) (from);              \
 272   _bits = sizeof (_mask);               \
 273   _mask = 0;                            \
 274   do                                    \
 275     _mask = (_mask << 8) | *_ptr++;     \
 276   while (--_bits != 0);                 \
 277   _bits = 16;                           \
 278 } while (0)
 279
 280 /* read [1, 17] bits at once */
 281 #define BIORD(bits)      \
 282   (_mask >> (8 * sizeof (_mask) - (bits)))
 283
 284 #define BIORD_MORE(bits) do {           \
 285   _mask <<= (bits);                     \
 286   if ((_bits -= (bits)) <= 0)           \
 287   {                                     \
 288     _mask |= ((_ptr[0] << 8) + _ptr[1]) << (-_bits);    \
 289     _ptr += 2; _bits += 16;             \
 290   }                                     \
 291 } while (0)
 292
 293 /* ------------------------ Huffman coding ---------------------------- */
 294 /*                          --------------                              */
 295
 296 #if MAX_ALPHABET <= 0xffff
 297 #  if MAX_ALPHABET <= 1024
 298 /* positive value takes 15 bits => symbol number occupies <= 10 bits    */
 299 #    define huffman_decode_t    short
 300 #  else
 301 #    define huffman_decode_t    int
 302 #  endif
 303 #else
 304 #  define huffman_decode_t      int
 305 #endif
 306
 307 #define HUFFMAN_DECODE(ch,table,start_bits) do {        \
 308   (ch) = table[BIORD (start_bits)];                     \
 309   if (((int) (ch)) >= 0)                                \
 310   {                                                     \
 311     BIORD_MORE ((ch) & 31);                             \
 312     (ch) >>= 5;                                         \
 313     break;                                              \
 314   }                                                     \
 315   BIORD_MORE (start_bits);                              \
 316   do                                                    \
 317   {                                                     \
 318     (ch) = table[BIORD (1) - (ch)];                     \
 319     BIORD_MORE (1);                                     \
 320   }                                                     \
 321   while (((int) (ch)) < 0);                             \
 322 } while (0)
 323
 324 #define HUFFMAN_TABLE_SIZE(n,start_bits) \
 325   ((1 << (start_bits)) + ((n) << 1))
 326
 327 static int huffman_decode_create(huffman_decode_t * table, uchar * length,
 328                                  int n, int start_bits)
 329 {
 330   int       i, j, k, last, freq[32], sum[32];
 331
 332  /* calculate number of codewords                                      */
 333   memset(freq, 0, sizeof(freq));
 334   for (i = 0; i < n; ++i) {
 335     if ((k = length[i]) > 31)
 336       return RET(COMP_ERR_BROKEN);
 337     ++freq[k];
 338   }
 339
 340  /* handle special case(s) -- 0 and 1 symbols in alphabet              */
 341   if (freq[0] == n) {
 342     memset(table, 0, sizeof(table[0]) << start_bits);
 343     return (0);
 344   }
 345   if (freq[0] == n - 1) {
 346     if (freq[1] != 1)
 347       return RET(COMP_ERR_BROKEN);
 348     for (i = 0; length[i] == 0;)
 349       ++i;
 350     i <<= 5;
 351     for (k = 1 << start_bits; --k >= 0;)
 352       *table++ = (huffman_decode_t) i;
 353     return (0);
 354   }
 355
 356  /* save frequences                    */
 357   memcpy(sum, freq, sizeof(sum));
 358
 359  /* check code correctness             */
 360   k = 0;
 361   for (i = 32; --i != 0;) {
 362     if ((k += freq[i]) & 1)
 363       return RET(COMP_ERR_BROKEN);
 364     k >>= 1;
 365   }
 366   if (k != 1)
 367     return RET(COMP_ERR_BROKEN);
 368
 369  /* sort symbols               */
 370   k = 0;
 371   for (i = 1; i < 32; ++i)
 372     freq[i] = (k += freq[i]);
 373   last = freq[31];      /* preserve number of symbols in alphabet       */
 374   for (i = n; --i >= 0;) {
 375     if ((k = length[i]) != 0)
 376       table[--freq[k]] = (huffman_decode_t) i;
 377   }
 378
 379  /* now create decoding table  */
 380   k = i = (1 << start_bits) + (n << 1);
 381   for (n = 32; --n > start_bits;) {
 382     j = i;
 383     while (k > j)
 384       table[--i] = (huffman_decode_t) - (k -= 2);
 385     for (k = sum[n]; --k >= 0;)
 386       table[--i] = table[--last];
 387     k = j;
 388   }
 389
 390   j = i;
 391   i = 1 << start_bits;
 392   while (k > j)
 393     table[--i] = (huffman_decode_t) - (k -= 2);
 394
 395   for (; n > 0; --n) {
 396     for (k = sum[n]; --k >= 0;) {
 397       assert(last <= i && last > 0);
 398       j = i - (1 << (start_bits - n));
 399       n |= table[--last] << 5;
 400       do
 401         table[--i] = (huffman_decode_t) n;
 402       while (i != j);
 403       n &= 31;
 404     }
 405   }
 406   assert((i | last) == 0);
 407
 408   return (0);
 409 }
 410
 411 /* -------------------- Read/write Huffman code ----------------------- */
 412 /*                      -----------------------                         */
 413
 414 #define MIN_REPT        2
 415
 416 #if MIN_REPT <= 1
 417 #error MIN_REPT must exceed 1
 418 #endif
 419
 420 #define TEMP_TABLE_BITS 8
 421
 422 static int huffman_read_length(bitio_t * bitio, uchar * length, int n)
 423 {
 424   BITIO_LOCALS;
 425   huffman_decode_t table[2][HUFFMAN_TABLE_SIZE(64, TEMP_TABLE_BITS)];
 426   uchar     bits[128];
 427   int       i, j, k;
 428
 429   BITIO_ENTER(*bitio);
 430   k = BIORD(1);
 431   BIORD_MORE(1);
 432   if (k != 0) {
 433     memset(length, 0, n);
 434     goto ret;
 435   }
 436
 437   if (n <= 128) {
 438     k = BIORD(5);
 439     BIORD_MORE(5);
 440     for (i = 0; i < n;) {
 441       length[i] = (uchar) BIORD(k);
 442       BIORD_MORE(k);
 443       if (length[i++] == 0) {
 444         j = i + BIORD(4);
 445         BIORD_MORE(4);
 446         if (j > n)
 447           return RET(COMP_ERR_BROKEN);
 448         while (i != j)
 449           length[i++] = 0;
 450       }
 451     }
 452     goto ret;
 453   }
 454
 455   BITIO_LEAVE(*bitio);
 456   i = huffman_read_length(bitio, bits, 128);
 457   if (i != 0)
 458     return (i);
 459   i = huffman_decode_create(table[0], bits, 64, TEMP_TABLE_BITS);
 460   if (i != 0)
 461     return (i);
 462   i = huffman_decode_create(table[1], bits + 64, 64, TEMP_TABLE_BITS);
 463   if (i != 0)
 464     return (i);
 465   BITIO_ENTER(*bitio);
 466
 467   for (i = 0; i < n;) {
 468     HUFFMAN_DECODE(k, table[0], TEMP_TABLE_BITS);
 469     if (k <= 31) {
 470       length[i++] = (uchar) k;
 471       continue;
 472     }
 473     k &= 31;
 474     HUFFMAN_DECODE(j, table[1], TEMP_TABLE_BITS);
 475     if (j > 31) {
 476       int       jj = j - 32;
 477
 478       j = 1 << jj;
 479       if (jj != 0) {
 480         if (jj > 16) {
 481           j += BIORD(16) << (jj - 16);
 482           BIORD_MORE(16);
 483         }
 484         j += BIORD(jj);
 485         BIORD_MORE(jj);
 486       }
 487       j += 31;
 488     }
 489     j += MIN_REPT + i;
 490     if (j > n)
 491       return RET(COMP_ERR_BROKEN);
 492     do
 493       length[i] = (uchar) k;
 494     while (++i != j);
 495   }
 496
 497 ret:
 498   BITIO_LEAVE(*bitio);
 499   return (0);
 500 }
 501
 502 /* ----------------------- Proper compression ------------------------- */
 503 /*                         ------------------                           */
 504
 505 #if MIN_BLOCK_BITS > MAX_BLOCK_BITS || MAX_BLOCK_BITS > MAX_BITS_HALF*2
 506 #error condition MIN_BLOCK_BITS <= MAX_BLOCK_BITS <= MAX_BITS_HALF*2 failed
 507 #endif
 508
 509 #define DECODE_MAGIC    ((int) 0x5abc947fL)
 510 #define BLOCK_MAGIC     ((int) 0x79a3f29dL)
 511
 512 #define START_BITS      13
 513
 514 #define SHORT_INDEX     8u
 515
 516 typedef struct {
 517   huffman_decode_t table[HUFFMAN_TABLE_SIZE(ALPHABET_SIZE, START_BITS)];
 518   int       distance[MAX_DISTANCES];
 519   unsigned *crc, *blk_u;
 520   unsigned short *blk_s;
 521   int       block_size_log,     /* block_size is integral power of 2    */
 522             block_size,         /* 1 << block_size_log                  */
 523             last_block_size,    /* [original] size of last block        */
 524             n_blk,              /* total number of blocks               */
 525             comp_block_size,    /* size of largest compressed block+32  */
 526             check_crc;          /* check CRC32?                         */
 527   uchar    *comp;
 528   int       magic;
 529 } decode_info;
 530
 531 typedef struct {
 532   unsigned char *ptr;           /* pointer to the first decoded byte */
 533   int       decoded;            /* number of bytes decoded so far    */
 534   int       total;              /* total number of bytes in block    */
 535   int       number;             /* number of this block              */
 536 } COMP_BLOCK_T;
 537
 538 /* Pointer to compressed data block                                     */
 539
 540 typedef struct {
 541   COMP_BLOCK_T b;
 542   struct {
 543     uchar    *first;
 544     int       size;
 545   } orig   , comp;
 546   struct {
 547     uchar    *ptr, *src;
 548     int       rept;
 549   } emit;
 550   bitio_t   bitio;
 551   int       n;
 552   int       magic;
 553 } decode_block;
 554
 555 static int calculate_offset(decode_info * info, unsigned n)
 556 {
 557   unsigned  i;
 558
 559   i = n / (2 * SHORT_INDEX);
 560   if (n & SHORT_INDEX)
 561     return info->blk_u[i + 1] - info->blk_s[n];
 562   else
 563     return info->blk_u[i] + info->blk_s[n];
 564 }
 565
 566 static void do_decode(decode_info * info, decode_block * block, uchar * e)
 567 {
 568   BITIO_LOCALS;
 569   uchar    *p, *s = 0;
 570   int       ch;
 571
 572   if ((p = block->emit.ptr) >= e)
 573     return;
 574   if (p == block->orig.first) {
 575     BIORD_START(block->comp.first);
 576     block->emit.rept = 0;
 577   } else {
 578     BITIO_ENTER(block->bitio);
 579     if ((ch = block->emit.rept) != 0) {
 580       block->emit.rept = 0;
 581       s = block->emit.src;
 582       goto copy;
 583     }
 584   }
 585 #define OVER if (p < e) goto over; break
 586   do {
 587   over:
 588     HUFFMAN_DECODE(ch, info->table, START_BITS);
 589     if ((ch -= 256) < 0) {
 590       *p++ = (uchar) ch;
 591       OVER;
 592     }
 593
 594     s = p + info->distance[ch >> MAX_LENGTH_BITS];
 595
 596     ch &= MAX_LENGTH - 1;
 597     if (ch <= 3) {
 598       p[0] = s[0];
 599       p[1] = s[1];
 600       p[2] = s[2];
 601       p[3] = s[3];
 602       p += ch + 1;
 603       OVER;
 604     } else if (ch >= LONG_LENGTH) {
 605       ch -= LONG_LENGTH - LONG_BITS;
 606 #if (MAX_BLOCK_BITS - 1) + (LONG_LENGTH - LONG_BITS) >= MAX_LENGTH
 607       if (ch == DELTA) {
 608         ch = BIORD(5);
 609         BIORD_MORE(5);
 610         ch += DELTA;
 611       }
 612 #endif
 613       {
 614         int       n = 1 << ch;
 615
 616         if (ch > 16) {
 617           n += BIORD(16) << (ch -= 16);
 618           BIORD_MORE(16);
 619         }
 620         n += BIORD(ch);
 621         BIORD_MORE(ch);
 622         ch = n;
 623       }
 624       ch += LONG_LENGTH - (1 << LONG_BITS);
 625     }
 626     ++ch;
 627   copy:
 628     if (ch > 16) {
 629       if (p + ch > e) {
 630         block->emit.rept = ch - (int) (e - p);
 631         ch = (int) (e - p);
 632         goto copy;
 633       }
 634       do {
 635 #       define X(i) p[i] = s[i]
 636         X(0);
 637         X(1);
 638         X(2);
 639         X(3);
 640         X(4);
 641         X(5);
 642         X(6);
 643         X(7);
 644         X(8);
 645         X(9);
 646         X(10);
 647         X(11);
 648         X(12);
 649         X(13);
 650         X(14);
 651         X(15);
 652 #       undef X
 653         p += 16;
 654         s += 16;
 655       }
 656       while ((ch -= 16) > 16);
 657     }
 658     p += ch;
 659     s += ch;
 660     switch (ch) {
 661 #     define X(i) case i: p[-i] = s[-i]
 662       X(16);
 663       X(15);
 664       X(14);
 665       X(13);
 666       X(12);
 667       X(11);
 668       X(10);
 669       X(9);
 670       X(8);
 671       X(7);
 672       X(6);
 673       X(5);
 674       X(4);
 675       X(3);
 676       X(2);
 677 #     undef X
 678     }
 679     p[-1] = s[-1];
 680   }
 681   while (p < e);
 682 #undef OVER
 683   block->emit.ptr = p;
 684   block->emit.src = s;
 685   BITIO_LEAVE(block->bitio);
 686 }
 687
 688 /* pretty ugly */
 689 static int comp_open_file(decode_info ** res, FILE * fd, int check_crc)
 690 {
 691   BITIO_LOCALS;
 692   bitio_t   Bitio;
 693   uchar     temp[ALPHABET_SIZE >= HEADER_SIZE ? ALPHABET_SIZE : HEADER_SIZE];
 694   uchar    *ptr;
 695   int       header_size, block_size, block_size_log, n_blk, i, n, n_s, n_u;
 696   unsigned *blk_u, *blk;
 697   unsigned short *blk_s;
 698   decode_info *info;
 699
 700   if (res == 0)
 701     return RET(COMP_ERR_PARAM);
 702
 703   CRC32_init();
 704
 705   *res = 0;
 706
 707   if (fread(temp, 1, HEADER_SIZE, fd) != HEADER_SIZE)
 708     return RET(COMP_ERR_READ);
 709
 710   if (memcmp(temp, header_title, 64) != 0)
 711     return RET(COMP_ERR_READ);
 712
 713   ptr = temp;
 714 #define R4(i) \
 715   ((ptr[i] << 24) + (ptr[(i) + 1] << 16) + (ptr[(i) + 2] << 8) + (ptr[(i) + 3]))
 716
 717   header_size = R4(64);
 718   block_size_log = ptr[70];
 719   if (block_size_log > MAX_BITS || header_size < 84)
 720     return RET(COMP_ERR_BROKEN);
 721   block_size = 1 << block_size_log;
 722   if (ptr[71] != MAX_DISTANCES)
 723     return RET(COMP_ERR_BROKEN);
 724   n_blk = R4(72);
 725   if (R4(76) !=
 726       (ALPHABET_SIZE << 12) + (LONG_BITS << 8) + (LONG_LENGTH << 4) +
 727       MAX_LENGTH_BITS)
 728     return RET(COMP_ERR_BROKEN);
 729
 730   if ((ptr = (uchar *) malloc(header_size)) == 0)
 731     return RET(COMP_ERR_NOMEM);
 732
 733   if (fread(ptr + HEADER_SIZE, 1, header_size - HEADER_SIZE, fd) !=
 734       (size_t) (header_size - HEADER_SIZE)) {
 735     free(ptr);
 736     return RET(COMP_ERR_NOMEM);
 737   }
 738   memcpy(ptr, temp, HEADER_SIZE);
 739   header_size -= 4;
 740   if (CRC32(ptr, header_size, 0) != (unsigned) R4(header_size)) {
 741     free(ptr);
 742     return RET(COMP_ERR_BROKEN);
 743   }
 744   header_size += 4;
 745
 746  /*
 747     blk = (unsigned *) malloc (sizeof (unsigned) * (1 + n_blk));
 748   */
 749   n = sizeof(unsigned) * (1 + n_blk);
 750   if (n < 4 * 1024 * 1024)
 751     n = 4 * 1024 * 1024;
 752   blk = (unsigned *) malloc(n);
 753
 754   if (blk == 0) {
 755     free(ptr);
 756     return RET(COMP_ERR_NOMEM);
 757   }
 758   n = sizeof(info->crc[0]) * (1 + (check_crc ? (2 * n_blk) : 0));
 759   n_u = sizeof(unsigned) * (2 + n_blk / (2 * SHORT_INDEX));
 760   n_s = sizeof(unsigned short) * (1 + n_blk);
 761   if ((info = (decode_info *) malloc(sizeof(*info) + n + n_u + n_s)) == 0) {
 762     free(ptr);
 763     free(blk);
 764     return RET(COMP_ERR_NOMEM);
 765   }
 766   cbEGTBCompBytes += sizeof(*info) + n + n_s + n_u;
 767   info->crc = (unsigned *) (info + 1);
 768   if (check_crc)
 769     blk_u = info->blk_u = info->crc + 2 * n_blk;
 770   else
 771     blk_u = info->blk_u = info->crc;
 772   blk_s = info->blk_s =
 773       (unsigned short *) (blk_u + 2 + n_blk / (2 * SHORT_INDEX));
 774
 775   info->check_crc = check_crc;
 776   info->block_size_log = block_size_log;
 777   info->block_size = block_size;
 778   info->n_blk = n_blk;
 779
 780   if (check_crc) {
 781     n_blk <<= 1;
 782     i = HEADER_SIZE;
 783     for (n = 0; n < n_blk; ++n) {
 784       info->crc[n] = R4(i);
 785       i += 4;
 786     }
 787     n_blk >>= 1;
 788   }
 789
 790   i = HEADER_SIZE + (n_blk << 3);
 791   BIORD_START(ptr + i);
 792
 793   info->comp_block_size = 0;
 794   for (n = 0; n <= n_blk; ++n) {
 795     if ((blk[n] = BIORD(block_size_log)) == 0)
 796       blk[n] = block_size;
 797     if (info->comp_block_size < (int) (blk[n]))
 798       info->comp_block_size = (int) (blk[n]);
 799     BIORD_MORE(block_size_log);
 800   }
 801   info->comp_block_size += 32;
 802
 803   for (n = 0; n < MAX_DISTANCES; ++n) {
 804     info->distance[n] = -((int) BIORD(block_size_log));
 805     BIORD_MORE(block_size_log);
 806   }
 807
 808   i += ((n_blk + 1 + MAX_DISTANCES) * block_size_log + 7) >> 3;
 809   BIORD_START(ptr + i);
 810   BITIO_LEAVE(Bitio);
 811   if (huffman_read_length(&Bitio, temp, ALPHABET_SIZE) != 0) {
 812     free(blk);
 813     free(info);
 814     free(ptr);
 815     return RET(COMP_ERR_BROKEN);
 816   }
 817
 818   if (huffman_decode_create(info->table, temp, ALPHABET_SIZE, START_BITS) != 0) {
 819     free(blk);
 820     free(info);
 821     free(ptr);
 822     return RET(COMP_ERR_BROKEN);
 823   }
 824
 825   info->last_block_size = blk[n_blk];
 826   blk[n_blk] = 0;
 827   for (n = 0; n <= n_blk; ++n) {
 828     i = blk[n];
 829     blk[n] = header_size;
 830     header_size += i;
 831     if (0 == n % (2 * SHORT_INDEX))
 832       blk_u[n / (2 * SHORT_INDEX)] = blk[n];
 833   }
 834   blk_u[n_blk / (2 * SHORT_INDEX) + 1] = blk[n_blk];
 835
 836   for (n = 0; n <= n_blk; ++n) {
 837     i = n / (2 * SHORT_INDEX);
 838     if (n & SHORT_INDEX)
 839       blk_s[n] = blk_u[i + 1] - blk[n];
 840     else
 841       blk_s[n] = blk[n] - blk_u[i];
 842   }
 843
 844   free(blk);
 845   free(ptr);
 846   info->comp = 0;
 847   info->magic = DECODE_MAGIC;
 848   *res = info;
 849
 850   return (COMP_ERR_NONE);
 851 }
 852
 853 static int comp_tell_blocks(decode_info * info)
 854 {
 855   if (info == 0 || info->magic != DECODE_MAGIC)
 856     return (-1);
 857   return (info->n_blk);
 858 }
 859
 860 static int comp_init_block(decode_block * block, int block_size, uchar * orig)
 861 {
 862   if (block == 0)
 863     return RET(COMP_ERR_PARAM);
 864   block->orig.first = orig;
 865   block->comp.first = (uchar *) (block + 1);
 866   block->b.ptr = 0;
 867   block->b.decoded = -1;
 868   block->b.total = -1;
 869   block->b.number = -1;
 870   block->n = -1;
 871   block->magic = BLOCK_MAGIC;
 872   return (COMP_ERR_NONE);
 873 }
 874
 875 static int comp_alloc_block(decode_block ** ret_block, int block_size)
 876 {
 877   decode_block *block;
 878
 879   if (ret_block == 0)
 880     return RET(COMP_ERR_PARAM);
 881   *ret_block = 0;
 882   if ((block = (decode_block *) malloc(sizeof(*block) + block_size)) == 0)
 883     return RET(COMP_ERR_NOMEM);
 884   cbEGTBCompBytes += sizeof(*block) + block_size;
 885   if (0 != comp_init_block(block, block_size, NULL))
 886     return RET(COMP_ERR_PARAM);
 887   *ret_block = block;
 888   return (COMP_ERR_NONE);
 889 }
 890
 891 #define RETURN(n) \
 892   return ((n) == COMP_ERR_NONE ? COMP_ERR_NONE : RET (n));
 893
 894 static int comp_read_block(decode_block * block, decode_info * info, FILE * fd,
 895                            int n)
 896 {
 897   int       comp_size, orig_size, comp_start;
 898   uchar    *comp, *orig;
 899
 900   if (block == 0 || block->magic != BLOCK_MAGIC)
 901     return RET(COMP_ERR_PARAM);
 902   assert(info->magic == DECODE_MAGIC);
 903   if ((unsigned) n >= (unsigned) info->n_blk)
 904     RETURN(COMP_ERR_PARAM);
 905   comp = block->comp.first;
 906   block->n = n;
 907   orig = block->orig.first;
 908   orig_size = info->block_size;
 909   if (n == info->n_blk - 1)
 910     orig_size = info->last_block_size;
 911   block->orig.size = orig_size;
 912   comp_start = calculate_offset(info, n);
 913   block->comp.size = comp_size = calculate_offset(info, n + 1) - comp_start;
 914   if (fseek(fd, comp_start, SEEK_SET) != 0)
 915     RETURN(COMP_ERR_READ);
 916   if (fread(comp, 1, comp_size, fd) != (size_t) comp_size)
 917     RETURN(COMP_ERR_READ);
 918   if (info->check_crc
 919       && info->crc[(n << 1) + 1] != CRC32(block->comp.first, comp_size, 0))
 920     RETURN(COMP_ERR_BROKEN);
 921   block->emit.rept = 0;
 922   if (comp_size == orig_size) {
 923     memcpy(orig, comp, comp_size);
 924     block->emit.ptr = orig + comp_size;
 925     block->b.decoded = comp_size;
 926   } else {
 927     block->emit.ptr = orig;
 928     block->b.decoded = 0;
 929   }
 930   block->b.number = n;
 931   block->b.ptr = orig;
 932   block->b.total = orig_size;
 933
 934   RETURN(COMP_ERR_NONE);
 935 }
 936
 937 static int comp_decode_and_check_crc(decode_block * block, decode_info * info,
 938                                      int n, int check_crc)
 939 {
 940   if (block == 0 || block->magic != BLOCK_MAGIC)
 941     return RET(COMP_ERR_PARAM);
 942   assert(info->magic == DECODE_MAGIC);
 943   if ((unsigned) (n - 1) > (unsigned) (block->orig.size - 1))
 944     RETURN(COMP_ERR_PARAM);
 945   if (check_crc)
 946     n = block->orig.size;
 947   do_decode(info, block, block->orig.first + n);
 948   block->b.ptr = block->orig.first;
 949   block->b.total = block->orig.size;
 950   if (block->b.decoded >= block->b.total) {
 951     if (block->b.decoded > block->b.total)
 952       RETURN(COMP_ERR_BROKEN);
 953     if (block->emit.rept != 0)
 954       RETURN(COMP_ERR_BROKEN);
 955   }
 956   if (check_crc && info->check_crc
 957       && info->crc[block->n << 1] != CRC32(block->orig.first, block->orig.size,
 958                                            0))
 959     RETURN(COMP_ERR_BROKEN);
 960
 961   RETURN(COMP_ERR_NONE);
 962 }
 963
 964 #if !defined (COLOR_DECLARED)
 965
 966 /*
 967    Test driver
 968  */
 969
 970 #define CRC_CHECK       1
 971
 972 int main(int argc, char *argv[])
 973 {
 974   int       i;
 975   int       size;
 976   int       result;
 977   FILE     *fp;
 978   decode_info *comp_info;
 979   decode_block *comp_block;
 980   clock_t   tStart, tEnd;
 981   double    dSeconds;
 982   uchar     rgbBuf[8192 + 32];
 983
 984   if (2 != argc) {
 985     printf("Invalid arguments\n");
 986     exit(1);
 987   }
 988   fp = fopen(argv[1], "rb");
 989   if (0 == fp) {
 990     printf("Unable to open file\n");
 991     exit(1);
 992   }
 993   result = comp_open_file(&comp_info, fp, CRC_CHECK);
 994   if (0 != result) {
 995     printf("Unable to read file (1): %d\n", result);
 996     exit(1);
 997   }
 998   if (8192 != comp_info->block_size) {
 999     printf("Invalid block size: %d\n", comp_info->block_size);
1000     exit(1);
1001   }
1002   result = comp_alloc_block(&comp_block, comp_info->block_size);
1003   if (0 != result) {
1004     printf("Unable to allocate block: %d\n", result);
1005     exit(1);
1006   }
1007
1008   size = 0;
1009   tStart = clock();
1010   for (i = 0; i < comp_info->n_blk; i++) {
1011     if (0 !=
1012         (result = comp_init_block(comp_block, comp_info->block_size, rgbBuf))) {
1013       printf("Unable to init block: %d\n", result);
1014       exit(1);
1015     }
1016     if (0 != (result = comp_read_block(comp_block, comp_info, fp, i))) {
1017       printf("Unable to read block: %d\n", result);
1018       exit(1);
1019     }
1020     size += comp_block->orig.size;
1021     if (0 !=
1022         (result =
1023          comp_decode_and_check_crc(comp_block, comp_info, comp_block->orig.size,
1024                                    CRC_CHECK))) {
1025       printf("Unable to decode block: %d\n", result);
1026       exit(1);
1027     }
1028   }
1029   tEnd = clock();
1030   dSeconds = (double) (tEnd - tStart) / CLOCKS_PER_SEC;
1031   printf("Total memory allocated: %dKb\n", (cbEGTBCompBytes + 1023) / 1024);
1032   printf("%g seconds, %dMb, %gMb/sec)\n", dSeconds, size / (1024 * 1024),
1033          size / (1024 * 1024) / dSeconds);
1034   return 0;
1035 }
1036
1037 #endif
1038 #endif