Subversion Repositories Games.Chess Giants

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
112 pmbaty 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