Subversion Repositories Games.Chess Giants

Rev

Rev 33 | Blame | Last modification | View Log | Download | RSS feed

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