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 |