Subversion Repositories Games.Chess Giants

Rev

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