1 /* $NetBSD: bzlib.c,v 1.3 2015/02/05 01:26:54 agc Exp $ */
2
3
4 /*-------------------------------------------------------------*/
5 /*--- Library top-level functions. ---*/
6 /*--- bzlib.c ---*/
7 /*-------------------------------------------------------------*/
8
9 /* ------------------------------------------------------------------
10 This file is part of bzip2/libbzip2, a program and library for
11 lossless, block-sorting data compression.
12
13 bzip2/libbzip2 version 1.0.6 of 6 September 2010
14 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
15
16 Please read the WARNING, DISCLAIMER and PATENTS sections in the
17 README file.
18
19 This program is released under the terms of the license contained
20 in the file LICENSE.
21 ------------------------------------------------------------------ */
22
23 /* CHANGES
24 0.9.0 -- original version.
25 0.9.0a/b -- no changes in this file.
26 0.9.0c -- made zero-length BZ_FLUSH work correctly in bzCompress().
27 fixed bzWrite/bzRead to ignore zero-length requests.
28 fixed bzread to correctly handle read requests after EOF.
29 wrong parameter order in call to bzDecompressInit in
30 bzBuffToBuffDecompress. Fixed.
31 */
32
33 #include "config.h"
34
35 #include "bzlib_private.h"
36
37
38 /* $NetBSD: bzlib.c,v 1.3 2015/02/05 01:26:54 agc Exp $ */
39
40
41 /*-------------------------------------------------------------*/
42 /*--- Table for randomising repetitive blocks ---*/
43 /*--- randtable.c ---*/
44 /*-------------------------------------------------------------*/
45
46 /* ------------------------------------------------------------------
47 This file is part of bzip2/libbzip2, a program and library for
48 lossless, block-sorting data compression.
49
50 bzip2/libbzip2 version 1.0.6 of 6 September 2010
51 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
52
53 Please read the WARNING, DISCLAIMER and PATENTS sections in the
54 README file.
55
56 This program is released under the terms of the license contained
57 in the file LICENSE.
58 ------------------------------------------------------------------ */
59
60
61
62 /*---------------------------------------------*/
63 Int32 BZ2_rNums[512] = {
64 619, 720, 127, 481, 931, 816, 813, 233, 566, 247,
65 985, 724, 205, 454, 863, 491, 741, 242, 949, 214,
66 733, 859, 335, 708, 621, 574, 73, 654, 730, 472,
67 419, 436, 278, 496, 867, 210, 399, 680, 480, 51,
68 878, 465, 811, 169, 869, 675, 611, 697, 867, 561,
69 862, 687, 507, 283, 482, 129, 807, 591, 733, 623,
70 150, 238, 59, 379, 684, 877, 625, 169, 643, 105,
71 170, 607, 520, 932, 727, 476, 693, 425, 174, 647,
72 73, 122, 335, 530, 442, 853, 695, 249, 445, 515,
73 909, 545, 703, 919, 874, 474, 882, 500, 594, 612,
74 641, 801, 220, 162, 819, 984, 589, 513, 495, 799,
75 161, 604, 958, 533, 221, 400, 386, 867, 600, 782,
76 382, 596, 414, 171, 516, 375, 682, 485, 911, 276,
77 98, 553, 163, 354, 666, 933, 424, 341, 533, 870,
78 227, 730, 475, 186, 263, 647, 537, 686, 600, 224,
79 469, 68, 770, 919, 190, 373, 294, 822, 808, 206,
80 184, 943, 795, 384, 383, 461, 404, 758, 839, 887,
81 715, 67, 618, 276, 204, 918, 873, 777, 604, 560,
82 951, 160, 578, 722, 79, 804, 96, 409, 713, 940,
83 652, 934, 970, 447, 318, 353, 859, 672, 112, 785,
84 645, 863, 803, 350, 139, 93, 354, 99, 820, 908,
85 609, 772, 154, 274, 580, 184, 79, 626, 630, 742,
86 653, 282, 762, 623, 680, 81, 927, 626, 789, 125,
87 411, 521, 938, 300, 821, 78, 343, 175, 128, 250,
88 170, 774, 972, 275, 999, 639, 495, 78, 352, 126,
89 857, 956, 358, 619, 580, 124, 737, 594, 701, 612,
90 669, 112, 134, 694, 363, 992, 809, 743, 168, 974,
91 944, 375, 748, 52, 600, 747, 642, 182, 862, 81,
92 344, 805, 988, 739, 511, 655, 814, 334, 249, 515,
93 897, 955, 664, 981, 649, 113, 974, 459, 893, 228,
94 433, 837, 553, 268, 926, 240, 102, 654, 459, 51,
95 686, 754, 806, 760, 493, 403, 415, 394, 687, 700,
96 946, 670, 656, 610, 738, 392, 760, 799, 887, 653,
97 978, 321, 576, 617, 626, 502, 894, 679, 243, 440,
98 680, 879, 194, 572, 640, 724, 926, 56, 204, 700,
99 707, 151, 457, 449, 797, 195, 791, 558, 945, 679,
100 297, 59, 87, 824, 713, 663, 412, 693, 342, 606,
101 134, 108, 571, 364, 631, 212, 174, 643, 304, 329,
102 343, 97, 430, 751, 497, 314, 983, 374, 822, 928,
103 140, 206, 73, 263, 980, 736, 876, 478, 430, 305,
104 170, 514, 364, 692, 829, 82, 855, 953, 676, 246,
105 369, 970, 294, 750, 807, 827, 150, 790, 288, 923,
106 804, 378, 215, 828, 592, 281, 565, 555, 710, 82,
107 896, 831, 547, 261, 524, 462, 293, 465, 502, 56,
108 661, 821, 976, 991, 658, 869, 905, 758, 745, 193,
109 768, 550, 608, 933, 378, 286, 215, 979, 792, 961,
110 61, 688, 793, 644, 986, 403, 106, 366, 905, 644,
111 372, 567, 466, 434, 645, 210, 389, 550, 919, 135,
112 780, 773, 635, 389, 707, 100, 626, 958, 165, 504,
113 920, 176, 193, 713, 857, 265, 203, 50, 668, 108,
114 645, 990, 626, 197, 510, 357, 358, 850, 858, 364,
115 936, 638
116 };
117
118 /*---------------------------------------------------*/
119 /*--- Compression stuff ---*/
120 /*---------------------------------------------------*/
121
122
123 /*---------------------------------------------------*/
124 #ifndef BZ_NO_STDIO
BZ2_bz__AssertH__fail(int errcode)125 void BZ2_bz__AssertH__fail ( int errcode )
126 {
127 fprintf(stderr,
128 "\n\nbzip2/libbzip2: internal error number %d.\n"
129 "This is a bug in bzip2/libbzip2, %s.\n"
130 "Please report it to me at: jseward@bzip.org. If this happened\n"
131 "when you were using some program which uses libbzip2 as a\n"
132 "component, you should also report this bug to the author(s)\n"
133 "of that program. Please make an effort to report this bug;\n"
134 "timely and accurate bug reports eventually lead to higher\n"
135 "quality software. Thanks. Julian Seward, 10 December 2007.\n\n",
136 errcode,
137 BZ2_bzlibVersion()
138 );
139
140 if (errcode == 1007) {
141 fprintf(stderr,
142 "\n*** A special note about internal error number 1007 ***\n"
143 "\n"
144 "Experience suggests that a common cause of i.e. 1007\n"
145 "is unreliable memory or other hardware. The 1007 assertion\n"
146 "just happens to cross-check the results of huge numbers of\n"
147 "memory reads/writes, and so acts (unintendedly) as a stress\n"
148 "test of your memory system.\n"
149 "\n"
150 "I suggest the following: try compressing the file again,\n"
151 "possibly monitoring progress in detail with the -vv flag.\n"
152 "\n"
153 "* If the error cannot be reproduced, and/or happens at different\n"
154 " points in compression, you may have a flaky memory system.\n"
155 " Try a memory-test program. I have used Memtest86\n"
156 " (www.memtest86.com). At the time of writing it is free (GPLd).\n"
157 " Memtest86 tests memory much more thorougly than your BIOSs\n"
158 " power-on test, and may find failures that the BIOS doesn't.\n"
159 "\n"
160 "* If the error can be repeatably reproduced, this is a bug in\n"
161 " bzip2, and I would very much like to hear about it. Please\n"
162 " let me know, and, ideally, save a copy of the file causing the\n"
163 " problem -- without which I will be unable to investigate it.\n"
164 "\n"
165 );
166 }
167
168 exit(3);
169 }
170 #endif
171
172
173 /*---------------------------------------------------*/
174 static
bz_config_ok(void)175 int bz_config_ok ( void )
176 {
177 if (sizeof(int) != 4) return 0;
178 if (sizeof(short) != 2) return 0;
179 if (sizeof(char) != 1) return 0;
180 return 1;
181 }
182
183
184 /*---------------------------------------------------*/
185 static
default_bzalloc(void * opaque,Int32 items,Int32 size)186 void* default_bzalloc ( void* opaque, Int32 items, Int32 size )
187 {
188 void* v = malloc ( items * size );
189 USE_ARG(opaque);
190 return v;
191 }
192
193 static
default_bzfree(void * opaque,void * addr)194 void default_bzfree ( void* opaque, void* addr )
195 {
196 USE_ARG(opaque);
197 if (addr != NULL) free ( addr );
198 }
199
200
201
202
203 /*---------------------------------------------------*/
204
205
206
207 /*---------------------------------------------------*/
208
209
210 /*---------------------------------------------------*/
211
212
213 /*---------------------------------------------------*/
214 #define ADD_CHAR_TO_BLOCK(zs,zchh0) \
215 { \
216 UInt32 zchh = (UInt32)(zchh0); \
217 /*-- fast track the common case --*/ \
218 if (zchh != zs->state_in_ch && \
219 zs->state_in_len == 1) { \
220 UChar ch = (UChar)(zs->state_in_ch); \
221 BZ_UPDATE_CRC( zs->blockCRC, ch ); \
222 zs->inUse[zs->state_in_ch] = True; \
223 zs->block[zs->nblock] = (UChar)ch; \
224 zs->nblock++; \
225 zs->state_in_ch = zchh; \
226 } \
227 else \
228 /*-- general, uncommon cases --*/ \
229 if (zchh != zs->state_in_ch || \
230 zs->state_in_len == 255) { \
231 if (zs->state_in_ch < 256) \
232 add_pair_to_block ( zs ); \
233 zs->state_in_ch = zchh; \
234 zs->state_in_len = 1; \
235 } else { \
236 zs->state_in_len++; \
237 } \
238 }
239
240
241 /*---------------------------------------------------*/
242
243 /*---------------------------------------------------*/
244 /*--- Decompression stuff ---*/
245 /*---------------------------------------------------*/
246
247 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompressInit)248 int BZ_API(BZ2_bzDecompressInit)
249 ( bz_stream* strm,
250 int verbosity,
251 int small )
252 {
253 DState* s;
254
255 if (!bz_config_ok()) return BZ_CONFIG_ERROR;
256
257 if (strm == NULL) return BZ_PARAM_ERROR;
258 if (small != 0 && small != 1) return BZ_PARAM_ERROR;
259 if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;
260
261 if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
262 if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
263
264 s = BZALLOC( sizeof(DState) );
265 if (s == NULL) return BZ_MEM_ERROR;
266 s->strm = strm;
267 strm->state = s;
268 s->state = BZ_X_MAGIC_1;
269 s->bsLive = 0;
270 s->bsBuff = 0;
271 s->calculatedCombinedCRC = 0;
272 strm->total_in_lo32 = 0;
273 strm->total_in_hi32 = 0;
274 strm->total_out_lo32 = 0;
275 strm->total_out_hi32 = 0;
276 s->smallDecompress = (Bool)small;
277 s->ll4 = NULL;
278 s->ll16 = NULL;
279 s->tt = NULL;
280 s->currBlockNo = 0;
281 s->verbosity = verbosity;
282
283 return BZ_OK;
284 }
285
286
287 /*---------------------------------------------------*/
288 /* Return True iff data corruption is discovered.
289 Returns False if there is no problem.
290 */
291 static
unRLE_obuf_to_output_FAST(DState * s)292 Bool unRLE_obuf_to_output_FAST ( DState* s )
293 {
294 UChar k1;
295
296 if (s->blockRandomised) {
297
298 while (True) {
299 /* try to finish existing run */
300 while (True) {
301 if (s->strm->avail_out == 0) return False;
302 if (s->state_out_len == 0) break;
303 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
304 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
305 s->state_out_len--;
306 s->strm->next_out++;
307 s->strm->avail_out--;
308 s->strm->total_out_lo32++;
309 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
310 }
311
312 /* can a new run be started? */
313 if (s->nblock_used == s->save_nblock+1) return False;
314
315 /* Only caused by corrupt data stream? */
316 if (s->nblock_used > s->save_nblock+1)
317 return True;
318
319 s->state_out_len = 1;
320 s->state_out_ch = s->k0;
321 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
322 k1 ^= BZ_RAND_MASK; s->nblock_used++;
323 if (s->nblock_used == s->save_nblock+1) continue;
324 if (k1 != s->k0) { s->k0 = k1; continue; };
325
326 s->state_out_len = 2;
327 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
328 k1 ^= BZ_RAND_MASK; s->nblock_used++;
329 if (s->nblock_used == s->save_nblock+1) continue;
330 if (k1 != s->k0) { s->k0 = k1; continue; };
331
332 s->state_out_len = 3;
333 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
334 k1 ^= BZ_RAND_MASK; s->nblock_used++;
335 if (s->nblock_used == s->save_nblock+1) continue;
336 if (k1 != s->k0) { s->k0 = k1; continue; };
337
338 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
339 k1 ^= BZ_RAND_MASK; s->nblock_used++;
340 s->state_out_len = ((Int32)k1) + 4;
341 BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK;
342 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
343 }
344
345 } else {
346
347 /* restore */
348 UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC;
349 UChar c_state_out_ch = s->state_out_ch;
350 Int32 c_state_out_len = s->state_out_len;
351 Int32 c_nblock_used = s->nblock_used;
352 Int32 c_k0 = s->k0;
353 UInt32* c_tt = s->tt;
354 UInt32 c_tPos = s->tPos;
355 char* cs_next_out = s->strm->next_out;
356 unsigned int cs_avail_out = s->strm->avail_out;
357 Int32 ro_blockSize100k = s->blockSize100k;
358 /* end restore */
359
360 UInt32 avail_out_INIT = cs_avail_out;
361 Int32 s_save_nblockPP = s->save_nblock+1;
362 unsigned int total_out_lo32_old;
363
364 while (True) {
365
366 /* try to finish existing run */
367 if (c_state_out_len > 0) {
368 while (True) {
369 if (cs_avail_out == 0) goto return_notr;
370 if (c_state_out_len == 1) break;
371 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
372 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
373 c_state_out_len--;
374 cs_next_out++;
375 cs_avail_out--;
376 }
377 s_state_out_len_eq_one:
378 {
379 if (cs_avail_out == 0) {
380 c_state_out_len = 1; goto return_notr;
381 };
382 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
383 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
384 cs_next_out++;
385 cs_avail_out--;
386 }
387 }
388 /* Only caused by corrupt data stream? */
389 if (c_nblock_used > s_save_nblockPP)
390 return True;
391
392 /* can a new run be started? */
393 if (c_nblock_used == s_save_nblockPP) {
394 c_state_out_len = 0; goto return_notr;
395 };
396 c_state_out_ch = c_k0;
397 BZ_GET_FAST_C(k1); c_nblock_used++;
398 if (k1 != c_k0) {
399 c_k0 = k1; goto s_state_out_len_eq_one;
400 };
401 if (c_nblock_used == s_save_nblockPP)
402 goto s_state_out_len_eq_one;
403
404 c_state_out_len = 2;
405 BZ_GET_FAST_C(k1); c_nblock_used++;
406 if (c_nblock_used == s_save_nblockPP) continue;
407 if (k1 != c_k0) { c_k0 = k1; continue; };
408
409 c_state_out_len = 3;
410 BZ_GET_FAST_C(k1); c_nblock_used++;
411 if (c_nblock_used == s_save_nblockPP) continue;
412 if (k1 != c_k0) { c_k0 = k1; continue; };
413
414 BZ_GET_FAST_C(k1); c_nblock_used++;
415 c_state_out_len = ((Int32)k1) + 4;
416 BZ_GET_FAST_C(c_k0); c_nblock_used++;
417 }
418
419 return_notr:
420 total_out_lo32_old = s->strm->total_out_lo32;
421 s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
422 if (s->strm->total_out_lo32 < total_out_lo32_old)
423 s->strm->total_out_hi32++;
424
425 /* save */
426 s->calculatedBlockCRC = c_calculatedBlockCRC;
427 s->state_out_ch = c_state_out_ch;
428 s->state_out_len = c_state_out_len;
429 s->nblock_used = c_nblock_used;
430 s->k0 = c_k0;
431 s->tt = c_tt;
432 s->tPos = c_tPos;
433 s->strm->next_out = cs_next_out;
434 s->strm->avail_out = cs_avail_out;
435 /* end save */
436 }
437 return False;
438 }
439
440
441
442 /*---------------------------------------------------*/
BZ2_indexIntoF(Int32 indx,Int32 * cftab)443 __inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab )
444 {
445 Int32 nb, na, mid;
446 nb = 0;
447 na = 256;
448 do {
449 mid = (nb + na) >> 1;
450 if (indx >= cftab[mid]) nb = mid; else na = mid;
451 }
452 while (na - nb != 1);
453 return nb;
454 }
455
456
457 /*---------------------------------------------------*/
458 /* Return True iff data corruption is discovered.
459 Returns False if there is no problem.
460 */
461 static
unRLE_obuf_to_output_SMALL(DState * s)462 Bool unRLE_obuf_to_output_SMALL ( DState* s )
463 {
464 UChar k1;
465
466 if (s->blockRandomised) {
467
468 while (True) {
469 /* try to finish existing run */
470 while (True) {
471 if (s->strm->avail_out == 0) return False;
472 if (s->state_out_len == 0) break;
473 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
474 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
475 s->state_out_len--;
476 s->strm->next_out++;
477 s->strm->avail_out--;
478 s->strm->total_out_lo32++;
479 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
480 }
481
482 /* can a new run be started? */
483 if (s->nblock_used == s->save_nblock+1) return False;
484
485 /* Only caused by corrupt data stream? */
486 if (s->nblock_used > s->save_nblock+1)
487 return True;
488
489 s->state_out_len = 1;
490 s->state_out_ch = s->k0;
491 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
492 k1 ^= BZ_RAND_MASK; s->nblock_used++;
493 if (s->nblock_used == s->save_nblock+1) continue;
494 if (k1 != s->k0) { s->k0 = k1; continue; };
495
496 s->state_out_len = 2;
497 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
498 k1 ^= BZ_RAND_MASK; s->nblock_used++;
499 if (s->nblock_used == s->save_nblock+1) continue;
500 if (k1 != s->k0) { s->k0 = k1; continue; };
501
502 s->state_out_len = 3;
503 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
504 k1 ^= BZ_RAND_MASK; s->nblock_used++;
505 if (s->nblock_used == s->save_nblock+1) continue;
506 if (k1 != s->k0) { s->k0 = k1; continue; };
507
508 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
509 k1 ^= BZ_RAND_MASK; s->nblock_used++;
510 s->state_out_len = ((Int32)k1) + 4;
511 BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK;
512 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
513 }
514
515 } else {
516
517 while (True) {
518 /* try to finish existing run */
519 while (True) {
520 if (s->strm->avail_out == 0) return False;
521 if (s->state_out_len == 0) break;
522 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
523 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
524 s->state_out_len--;
525 s->strm->next_out++;
526 s->strm->avail_out--;
527 s->strm->total_out_lo32++;
528 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
529 }
530
531 /* can a new run be started? */
532 if (s->nblock_used == s->save_nblock+1) return False;
533
534 /* Only caused by corrupt data stream? */
535 if (s->nblock_used > s->save_nblock+1)
536 return True;
537
538 s->state_out_len = 1;
539 s->state_out_ch = s->k0;
540 BZ_GET_SMALL(k1); s->nblock_used++;
541 if (s->nblock_used == s->save_nblock+1) continue;
542 if (k1 != s->k0) { s->k0 = k1; continue; };
543
544 s->state_out_len = 2;
545 BZ_GET_SMALL(k1); s->nblock_used++;
546 if (s->nblock_used == s->save_nblock+1) continue;
547 if (k1 != s->k0) { s->k0 = k1; continue; };
548
549 s->state_out_len = 3;
550 BZ_GET_SMALL(k1); s->nblock_used++;
551 if (s->nblock_used == s->save_nblock+1) continue;
552 if (k1 != s->k0) { s->k0 = k1; continue; };
553
554 BZ_GET_SMALL(k1); s->nblock_used++;
555 s->state_out_len = ((Int32)k1) + 4;
556 BZ_GET_SMALL(s->k0); s->nblock_used++;
557 }
558
559 }
560 }
561
562
563 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompress)564 int BZ_API(BZ2_bzDecompress) ( bz_stream *strm )
565 {
566 Bool corrupt;
567 DState* s;
568 if (strm == NULL) return BZ_PARAM_ERROR;
569 s = strm->state;
570 if (s == NULL) return BZ_PARAM_ERROR;
571 if (s->strm != strm) return BZ_PARAM_ERROR;
572
573 while (True) {
574 if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;
575 if (s->state == BZ_X_OUTPUT) {
576 if (s->smallDecompress)
577 corrupt = unRLE_obuf_to_output_SMALL ( s ); else
578 corrupt = unRLE_obuf_to_output_FAST ( s );
579 if (corrupt) return BZ_DATA_ERROR;
580 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
581 BZ_FINALISE_CRC ( s->calculatedBlockCRC );
582 if (s->verbosity >= 3)
583 VPrintf2 ( " {0x%08x, 0x%08x}", s->storedBlockCRC,
584 s->calculatedBlockCRC );
585 if (s->verbosity >= 2) VPrintf0 ( "]" );
586 if (s->calculatedBlockCRC != s->storedBlockCRC)
587 return BZ_DATA_ERROR;
588 s->calculatedCombinedCRC
589 = (s->calculatedCombinedCRC << 1) |
590 (s->calculatedCombinedCRC >> 31);
591 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
592 s->state = BZ_X_BLKHDR_1;
593 } else {
594 return BZ_OK;
595 }
596 }
597 if (s->state >= BZ_X_MAGIC_1) {
598 Int32 r = BZ2_decompress ( s );
599 if (r == BZ_STREAM_END) {
600 if (s->verbosity >= 3)
601 VPrintf2 ( "\n combined CRCs: stored = 0x%08x, computed = 0x%08x",
602 s->storedCombinedCRC, s->calculatedCombinedCRC );
603 if (s->calculatedCombinedCRC != s->storedCombinedCRC)
604 return BZ_DATA_ERROR;
605 return r;
606 }
607 if (s->state != BZ_X_OUTPUT) return r;
608 }
609 }
610
611 AssertH ( 0, 6001 );
612
613 return 0; /*NOTREACHED*/
614 }
615
616
617 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompressEnd)618 int BZ_API(BZ2_bzDecompressEnd) ( bz_stream *strm )
619 {
620 DState* s;
621 if (strm == NULL) return BZ_PARAM_ERROR;
622 s = strm->state;
623 if (s == NULL) return BZ_PARAM_ERROR;
624 if (s->strm != strm) return BZ_PARAM_ERROR;
625
626 if (s->tt != NULL) BZFREE(s->tt);
627 if (s->ll16 != NULL) BZFREE(s->ll16);
628 if (s->ll4 != NULL) BZFREE(s->ll4);
629
630 BZFREE(strm->state);
631 strm->state = NULL;
632
633 return BZ_OK;
634 }
635
636
637 #ifndef BZ_NO_STDIO
638 /*---------------------------------------------------*/
639 /*--- File I/O stuff ---*/
640 /*---------------------------------------------------*/
641
642 #define BZ_SETERR(eee) \
643 { \
644 if (bzerror != NULL) *bzerror = eee; \
645 if (bzf != NULL) bzf->lastErr = eee; \
646 }
647
648 typedef
649 struct {
650 FILE* handle;
651 Char buf[BZ_MAX_UNUSED];
652 Int32 bufN;
653 Bool writing;
654 bz_stream strm;
655 Int32 lastErr;
656 Bool initialisedOk;
657 }
658 bzFile;
659
660
661 /*---------------------------------------------*/
myfeof(FILE * f)662 static Bool myfeof ( FILE* f )
663 {
664 Int32 c = fgetc ( f );
665 if (c == EOF) return True;
666 ungetc ( c, f );
667 return False;
668 }
669
670
671 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadOpen)672 BZFILE* BZ_API(BZ2_bzReadOpen)
673 ( int* bzerror,
674 FILE* f,
675 int verbosity,
676 int small,
677 void* unused,
678 int nUnused )
679 {
680 bzFile* bzf = NULL;
681 int ret;
682
683 if (bzerror == NULL) {
684 return NULL;
685 }
686
687 BZ_SETERR(BZ_OK);
688
689 if (f == NULL ||
690 (small != 0 && small != 1) ||
691 (verbosity < 0 || verbosity > 4) ||
692 (unused == NULL && nUnused != 0) ||
693 (unused != NULL && (nUnused < 0 || nUnused > BZ_MAX_UNUSED)))
694 { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };
695
696 if (ferror(f))
697 { BZ_SETERR(BZ_IO_ERROR); return NULL; };
698
699 bzf = malloc ( sizeof(bzFile) );
700 if (bzf == NULL)
701 { BZ_SETERR(BZ_MEM_ERROR); return NULL; };
702
703 BZ_SETERR(BZ_OK);
704
705 bzf->initialisedOk = False;
706 bzf->handle = f;
707 bzf->bufN = 0;
708 bzf->writing = False;
709 bzf->strm.bzalloc = NULL;
710 bzf->strm.bzfree = NULL;
711 bzf->strm.opaque = NULL;
712
713 while (nUnused > 0) {
714 bzf->buf[bzf->bufN] = *((UChar*)(unused)); bzf->bufN++;
715 unused = ((void*)( 1 + ((UChar*)(unused)) ));
716 nUnused--;
717 }
718
719 ret = BZ2_bzDecompressInit ( &(bzf->strm), verbosity, small );
720 if (ret != BZ_OK)
721 { BZ_SETERR(ret); free(bzf); return NULL; };
722
723 bzf->strm.avail_in = bzf->bufN;
724 bzf->strm.next_in = bzf->buf;
725
726 bzf->initialisedOk = True;
727 return bzf;
728 }
729
730
731 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadClose)732 void BZ_API(BZ2_bzReadClose) ( int *bzerror, BZFILE *b )
733 {
734 bzFile* bzf = (bzFile*)b;
735
736 BZ_SETERR(BZ_OK);
737 if (bzf == NULL)
738 { BZ_SETERR(BZ_OK); return; };
739
740 if (bzf->writing)
741 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
742
743 if (bzf->initialisedOk)
744 (void)BZ2_bzDecompressEnd ( &(bzf->strm) );
745 free ( bzf );
746 }
747
748
749 /*---------------------------------------------------*/
BZ_API(BZ2_bzRead)750 int BZ_API(BZ2_bzRead)
751 ( int* bzerror,
752 BZFILE* b,
753 void* buf,
754 int len )
755 {
756 Int32 n, ret;
757 bzFile* bzf = (bzFile*)b;
758
759 BZ_SETERR(BZ_OK);
760
761 if (bzf == NULL || buf == NULL || len < 0)
762 { BZ_SETERR(BZ_PARAM_ERROR); return 0; };
763
764 if (bzf->writing)
765 { BZ_SETERR(BZ_SEQUENCE_ERROR); return 0; };
766
767 if (len == 0)
768 { BZ_SETERR(BZ_OK); return 0; };
769
770 bzf->strm.avail_out = len;
771 bzf->strm.next_out = buf;
772
773 while (True) {
774
775 if (ferror(bzf->handle))
776 { BZ_SETERR(BZ_IO_ERROR); return 0; };
777
778 if (bzf->strm.avail_in == 0 && !myfeof(bzf->handle)) {
779 n = fread ( bzf->buf, sizeof(UChar),
780 BZ_MAX_UNUSED, bzf->handle );
781 if (ferror(bzf->handle))
782 { BZ_SETERR(BZ_IO_ERROR); return 0; };
783 bzf->bufN = n;
784 bzf->strm.avail_in = bzf->bufN;
785 bzf->strm.next_in = bzf->buf;
786 }
787
788 ret = BZ2_bzDecompress ( &(bzf->strm) );
789
790 if (ret != BZ_OK && ret != BZ_STREAM_END)
791 { BZ_SETERR(ret); return 0; };
792
793 if (ret == BZ_OK && myfeof(bzf->handle) &&
794 bzf->strm.avail_in == 0 && bzf->strm.avail_out > 0)
795 { BZ_SETERR(BZ_UNEXPECTED_EOF); return 0; };
796
797 if (ret == BZ_STREAM_END)
798 { BZ_SETERR(BZ_STREAM_END);
799 return len - bzf->strm.avail_out; };
800 if (bzf->strm.avail_out == 0)
801 { BZ_SETERR(BZ_OK); return len; };
802
803 }
804
805 return 0; /*not reached*/
806 }
807
808
809 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadGetUnused)810 void BZ_API(BZ2_bzReadGetUnused)
811 ( int* bzerror,
812 BZFILE* b,
813 void** unused,
814 int* nUnused )
815 {
816 bzFile* bzf = (bzFile*)b;
817 if (bzf == NULL)
818 { BZ_SETERR(BZ_PARAM_ERROR); return; };
819 if (bzf->lastErr != BZ_STREAM_END)
820 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
821 if (unused == NULL || nUnused == NULL)
822 { BZ_SETERR(BZ_PARAM_ERROR); return; };
823
824 BZ_SETERR(BZ_OK);
825 *nUnused = bzf->strm.avail_in;
826 *unused = bzf->strm.next_in;
827 }
828 #endif
829
830
831 /*---------------------------------------------------*/
BZ_API(BZ2_bzBuffToBuffDecompress)832 int BZ_API(BZ2_bzBuffToBuffDecompress)
833 ( char* dest,
834 unsigned int* destLen,
835 char* source,
836 unsigned int sourceLen,
837 int small,
838 int verbosity )
839 {
840 bz_stream strm;
841 int ret;
842
843 if (dest == NULL || destLen == NULL ||
844 source == NULL ||
845 (small != 0 && small != 1) ||
846 verbosity < 0 || verbosity > 4)
847 return BZ_PARAM_ERROR;
848
849 strm.bzalloc = NULL;
850 strm.bzfree = NULL;
851 strm.opaque = NULL;
852 ret = BZ2_bzDecompressInit ( &strm, verbosity, small );
853 if (ret != BZ_OK) return ret;
854
855 strm.next_in = source;
856 strm.next_out = dest;
857 strm.avail_in = sourceLen;
858 strm.avail_out = *destLen;
859
860 ret = BZ2_bzDecompress ( &strm );
861 if (ret == BZ_OK) goto output_overflow_or_eof;
862 if (ret != BZ_STREAM_END) goto errhandler;
863
864 /* normal termination */
865 *destLen -= strm.avail_out;
866 BZ2_bzDecompressEnd ( &strm );
867 return BZ_OK;
868
869 output_overflow_or_eof:
870 if (strm.avail_out > 0) {
871 BZ2_bzDecompressEnd ( &strm );
872 return BZ_UNEXPECTED_EOF;
873 } else {
874 BZ2_bzDecompressEnd ( &strm );
875 return BZ_OUTBUFF_FULL;
876 };
877
878 errhandler:
879 BZ2_bzDecompressEnd ( &strm );
880 return ret;
881 }
882
883
884 /*---------------------------------------------------*/
885 /*--
886 Code contributed by Yoshioka Tsuneo (tsuneo@rr.iij4u.or.jp)
887 to support better zlib compatibility.
888 This code is not _officially_ part of libbzip2 (yet);
889 I haven't tested it, documented it, or considered the
890 threading-safeness of it.
891 If this code breaks, please contact both Yoshioka and me.
892 --*/
893 /*---------------------------------------------------*/
894
895 /*---------------------------------------------------*/
896 /*--
897 return version like "0.9.5d, 4-Sept-1999".
898 --*/
BZ_API(BZ2_bzlibVersion)899 const char * BZ_API(BZ2_bzlibVersion)(void)
900 {
901 return BZ_VERSION;
902 }
903
904
905 #ifndef BZ_NO_STDIO
906 /*---------------------------------------------------*/
907
908 #if defined(_WIN32) || defined(OS2) || defined(MSDOS)
909 # include <fcntl.h>
910 # include <io.h>
911 # define SET_BINARY_MODE(file) setmode(fileno(file),O_BINARY)
912 #else
913 # define SET_BINARY_MODE(file)
914 #endif
915 static
bzopen_or_bzdopen(const char * path,int fd,const char * mode,int open_mode)916 BZFILE * bzopen_or_bzdopen
917 ( const char *path, /* no use when bzdopen */
918 int fd, /* no use when bzdopen */
919 const char *mode,
920 int open_mode) /* bzopen: 0, bzdopen:1 */
921 {
922 int bzerr;
923 char unused[BZ_MAX_UNUSED];
924 int blockSize100k = 9;
925 int writing = 0;
926 char mode2[10] = "";
927 FILE *fp = NULL;
928 BZFILE *bzfp = NULL;
929 int verbosity = 0;
930 int smallMode = 0;
931 int nUnused = 0;
932
933 USE_ARG(blockSize100k);
934
935 if (mode == NULL) return NULL;
936 while (*mode) {
937 switch (*mode) {
938 case 'r':
939 writing = 0; break;
940 case 'w':
941 writing = 1; break;
942 case 's':
943 smallMode = 1; break;
944 default:
945 if (isdigit((unsigned char)(*mode))) {
946 blockSize100k = *mode-BZ_HDR_0;
947 }
948 }
949 mode++;
950 }
951 strcat(mode2, writing ? "w" : "r" );
952 strcat(mode2,"b"); /* binary mode */
953
954 if (open_mode==0) {
955 if (path==NULL || strcmp(path,"")==0) {
956 fp = (writing ? stdout : stdin);
957 SET_BINARY_MODE(fp);
958 } else {
959 fp = fopen(path,mode2);
960 }
961 } else {
962 #ifdef BZ_STRICT_ANSI
963 fp = NULL;
964 #else
965 fp = fdopen(fd,mode2);
966 #endif
967 }
968 if (fp == NULL) return NULL;
969
970 if (writing) {
971 } else {
972 bzfp = BZ2_bzReadOpen(&bzerr,fp,verbosity,smallMode,
973 unused,nUnused);
974 }
975 if (bzfp == NULL) {
976 if (fp != stdin && fp != stdout) fclose(fp);
977 return NULL;
978 }
979 return bzfp;
980 }
981
982
983 /*---------------------------------------------------*/
984 /*--
985 open file for read or write.
986 ex) bzopen("file","w9")
987 case path="" or NULL => use stdin or stdout.
988 --*/
BZ_API(BZ2_bzopen)989 BZFILE * BZ_API(BZ2_bzopen)
990 ( const char *path,
991 const char *mode )
992 {
993 return bzopen_or_bzdopen(path,-1,mode,/*bzopen*/0);
994 }
995
996
997 /*---------------------------------------------------*/
BZ_API(BZ2_bzdopen)998 BZFILE * BZ_API(BZ2_bzdopen)
999 ( int fd,
1000 const char *mode )
1001 {
1002 return bzopen_or_bzdopen(NULL,fd,mode,/*bzdopen*/1);
1003 }
1004
1005
1006 /*---------------------------------------------------*/
BZ_API(BZ2_bzread)1007 int BZ_API(BZ2_bzread) (BZFILE* b, void* buf, int len )
1008 {
1009 int bzerr, nread;
1010 if (((bzFile*)b)->lastErr == BZ_STREAM_END) return 0;
1011 nread = BZ2_bzRead(&bzerr,b,buf,len);
1012 if (bzerr == BZ_OK || bzerr == BZ_STREAM_END) {
1013 return nread;
1014 } else {
1015 return -1;
1016 }
1017 }
1018
1019
1020 /*---------------------------------------------------*/
BZ_API(BZ2_bzflush)1021 int BZ_API(BZ2_bzflush) (BZFILE *b)
1022 {
1023 USE_ARG(b);
1024 /* do nothing now... */
1025 return 0;
1026 }
1027
1028
1029 /*---------------------------------------------------*/
BZ_API(BZ2_bzclose)1030 void BZ_API(BZ2_bzclose) (BZFILE* b)
1031 {
1032 int bzerr;
1033 FILE *fp;
1034
1035 if (b==NULL) {return;}
1036 fp = ((bzFile *)b)->handle;
1037 if(((bzFile*)b)->writing){
1038 }else{
1039 BZ2_bzReadClose(&bzerr,b);
1040 }
1041 if(fp!=stdin && fp!=stdout){
1042 fclose(fp);
1043 }
1044 }
1045
1046
1047 /*---------------------------------------------------*/
1048 /*--
1049 return last error code
1050 --*/
1051 static const char *bzerrorstrings[] = {
1052 "OK"
1053 ,"SEQUENCE_ERROR"
1054 ,"PARAM_ERROR"
1055 ,"MEM_ERROR"
1056 ,"DATA_ERROR"
1057 ,"DATA_ERROR_MAGIC"
1058 ,"IO_ERROR"
1059 ,"UNEXPECTED_EOF"
1060 ,"OUTBUFF_FULL"
1061 ,"CONFIG_ERROR"
1062 ,"???" /* for future */
1063 ,"???" /* for future */
1064 ,"???" /* for future */
1065 ,"???" /* for future */
1066 ,"???" /* for future */
1067 ,"???" /* for future */
1068 };
1069
1070
BZ_API(BZ2_bzerror)1071 const char * BZ_API(BZ2_bzerror) (BZFILE *b, int *errnum)
1072 {
1073 int err = ((bzFile *)b)->lastErr;
1074
1075 if(err>0) err = 0;
1076 *errnum = err;
1077 return bzerrorstrings[err*-1];
1078 }
1079 #endif
1080
1081
1082 /*-------------------------------------------------------------*/
1083 /*--- end bzlib.c ---*/
1084 /*-------------------------------------------------------------*/
1085 /* $NetBSD: bzlib.c,v 1.3 2015/02/05 01:26:54 agc Exp $ */
1086
1087
1088 /*-------------------------------------------------------------*/
1089 /*--- Decompression machinery ---*/
1090 /*--- decompress.c ---*/
1091 /*-------------------------------------------------------------*/
1092
1093 /* ------------------------------------------------------------------
1094 This file is part of bzip2/libbzip2, a program and library for
1095 lossless, block-sorting data compression.
1096
1097 bzip2/libbzip2 version 1.0.6 of 6 September 2010
1098 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
1099
1100 Please read the WARNING, DISCLAIMER and PATENTS sections in the
1101 README file.
1102
1103 This program is released under the terms of the license contained
1104 in the file LICENSE.
1105 ------------------------------------------------------------------ */
1106
1107
1108
1109 /*---------------------------------------------------*/
1110 static
makeMaps_d(DState * s)1111 void makeMaps_d ( DState* s )
1112 {
1113 Int32 i;
1114 s->nInUse = 0;
1115 for (i = 0; i < 256; i++)
1116 if (s->inUse[i]) {
1117 s->seqToUnseq[s->nInUse] = i;
1118 s->nInUse++;
1119 }
1120 }
1121
1122
1123 /*---------------------------------------------------*/
1124 #define RETURN(rrr) \
1125 { retVal = rrr; goto save_state_and_return; };
1126
1127 #define GET_BITS(lll,vvv,nnn) \
1128 case lll: s->state = lll; \
1129 while (True) { \
1130 if (s->bsLive >= nnn) { \
1131 UInt32 v; \
1132 v = (s->bsBuff >> \
1133 (s->bsLive-nnn)) & ((1 << nnn)-1); \
1134 s->bsLive -= nnn; \
1135 vvv = v; \
1136 break; \
1137 } \
1138 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
1139 s->bsBuff \
1140 = (s->bsBuff << 8) | \
1141 ((UInt32) \
1142 (*((UChar*)(s->strm->next_in)))); \
1143 s->bsLive += 8; \
1144 s->strm->next_in++; \
1145 s->strm->avail_in--; \
1146 s->strm->total_in_lo32++; \
1147 if (s->strm->total_in_lo32 == 0) \
1148 s->strm->total_in_hi32++; \
1149 }
1150
1151 #define GET_UCHAR(lll,uuu) \
1152 GET_BITS(lll,uuu,8)
1153
1154 #define GET_BIT(lll,uuu) \
1155 GET_BITS(lll,uuu,1)
1156
1157 /*---------------------------------------------------*/
1158 #define GET_MTF_VAL(label1,label2,lval) \
1159 { \
1160 if (groupPos == 0) { \
1161 groupNo++; \
1162 if (groupNo >= nSelectors) \
1163 RETURN(BZ_DATA_ERROR); \
1164 groupPos = BZ_G_SIZE; \
1165 gSel = s->selector[groupNo]; \
1166 gMinlen = s->minLens[gSel]; \
1167 gLimit = &(s->limit[gSel][0]); \
1168 gPerm = &(s->perm[gSel][0]); \
1169 gBase = &(s->base[gSel][0]); \
1170 } \
1171 groupPos--; \
1172 zn = gMinlen; \
1173 GET_BITS(label1, zvec, zn); \
1174 while (1) { \
1175 if (zn > 20 /* the longest code */) \
1176 RETURN(BZ_DATA_ERROR); \
1177 if (zvec <= gLimit[zn]) break; \
1178 zn++; \
1179 GET_BIT(label2, zj); \
1180 zvec = (zvec << 1) | zj; \
1181 }; \
1182 if (zvec - gBase[zn] < 0 \
1183 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
1184 RETURN(BZ_DATA_ERROR); \
1185 lval = gPerm[zvec - gBase[zn]]; \
1186 }
1187
1188
1189 /*---------------------------------------------------*/
BZ2_decompress(DState * s)1190 Int32 BZ2_decompress ( DState* s )
1191 {
1192 UChar uc;
1193 Int32 retVal;
1194 Int32 minLen, maxLen;
1195 bz_stream* strm = s->strm;
1196
1197 /* stuff that needs to be saved/restored */
1198 Int32 i;
1199 Int32 j;
1200 Int32 t;
1201 Int32 alphaSize;
1202 Int32 nGroups;
1203 Int32 nSelectors;
1204 Int32 EOB;
1205 Int32 groupNo;
1206 Int32 groupPos;
1207 Int32 nextSym;
1208 Int32 nblockMAX;
1209 Int32 nblock;
1210 Int32 es;
1211 Int32 N;
1212 Int32 curr;
1213 Int32 zt;
1214 Int32 zn;
1215 Int32 zvec;
1216 Int32 zj;
1217 Int32 gSel;
1218 Int32 gMinlen;
1219 Int32* gLimit;
1220 Int32* gBase;
1221 Int32* gPerm;
1222
1223 if (s->state == BZ_X_MAGIC_1) {
1224 /*initialise the save area*/
1225 s->save_i = 0;
1226 s->save_j = 0;
1227 s->save_t = 0;
1228 s->save_alphaSize = 0;
1229 s->save_nGroups = 0;
1230 s->save_nSelectors = 0;
1231 s->save_EOB = 0;
1232 s->save_groupNo = 0;
1233 s->save_groupPos = 0;
1234 s->save_nextSym = 0;
1235 s->save_nblockMAX = 0;
1236 s->save_nblock = 0;
1237 s->save_es = 0;
1238 s->save_N = 0;
1239 s->save_curr = 0;
1240 s->save_zt = 0;
1241 s->save_zn = 0;
1242 s->save_zvec = 0;
1243 s->save_zj = 0;
1244 s->save_gSel = 0;
1245 s->save_gMinlen = 0;
1246 s->save_gLimit = NULL;
1247 s->save_gBase = NULL;
1248 s->save_gPerm = NULL;
1249 }
1250
1251 /*restore from the save area*/
1252 i = s->save_i;
1253 j = s->save_j;
1254 t = s->save_t;
1255 alphaSize = s->save_alphaSize;
1256 nGroups = s->save_nGroups;
1257 nSelectors = s->save_nSelectors;
1258 EOB = s->save_EOB;
1259 groupNo = s->save_groupNo;
1260 groupPos = s->save_groupPos;
1261 nextSym = s->save_nextSym;
1262 nblockMAX = s->save_nblockMAX;
1263 nblock = s->save_nblock;
1264 es = s->save_es;
1265 N = s->save_N;
1266 curr = s->save_curr;
1267 zt = s->save_zt;
1268 zn = s->save_zn;
1269 zvec = s->save_zvec;
1270 zj = s->save_zj;
1271 gSel = s->save_gSel;
1272 gMinlen = s->save_gMinlen;
1273 gLimit = s->save_gLimit;
1274 gBase = s->save_gBase;
1275 gPerm = s->save_gPerm;
1276
1277 retVal = BZ_OK;
1278
1279 switch (s->state) {
1280
1281 GET_UCHAR(BZ_X_MAGIC_1, uc);
1282 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
1283
1284 GET_UCHAR(BZ_X_MAGIC_2, uc);
1285 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
1286
1287 GET_UCHAR(BZ_X_MAGIC_3, uc)
1288 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
1289
1290 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
1291 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
1292 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
1293 s->blockSize100k -= BZ_HDR_0;
1294
1295 if (s->smallDecompress) {
1296 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
1297 s->ll4 = BZALLOC(
1298 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
1299 );
1300 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
1301 } else {
1302 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
1303 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
1304 }
1305
1306 GET_UCHAR(BZ_X_BLKHDR_1, uc);
1307
1308 if (uc == 0x17) goto endhdr_2;
1309 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
1310 GET_UCHAR(BZ_X_BLKHDR_2, uc);
1311 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
1312 GET_UCHAR(BZ_X_BLKHDR_3, uc);
1313 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
1314 GET_UCHAR(BZ_X_BLKHDR_4, uc);
1315 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
1316 GET_UCHAR(BZ_X_BLKHDR_5, uc);
1317 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
1318 GET_UCHAR(BZ_X_BLKHDR_6, uc);
1319 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
1320
1321 s->currBlockNo++;
1322 if (s->verbosity >= 2)
1323 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
1324
1325 s->storedBlockCRC = 0;
1326 GET_UCHAR(BZ_X_BCRC_1, uc);
1327 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1328 GET_UCHAR(BZ_X_BCRC_2, uc);
1329 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1330 GET_UCHAR(BZ_X_BCRC_3, uc);
1331 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1332 GET_UCHAR(BZ_X_BCRC_4, uc);
1333 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1334
1335 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
1336
1337 s->origPtr = 0;
1338 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
1339 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1340 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
1341 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1342 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
1343 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1344
1345 if (s->origPtr < 0)
1346 RETURN(BZ_DATA_ERROR);
1347 if (s->origPtr > 10 + 100000*s->blockSize100k)
1348 RETURN(BZ_DATA_ERROR);
1349
1350 /*--- Receive the mapping table ---*/
1351 for (i = 0; i < 16; i++) {
1352 GET_BIT(BZ_X_MAPPING_1, uc);
1353 if (uc == 1)
1354 s->inUse16[i] = True; else
1355 s->inUse16[i] = False;
1356 }
1357
1358 for (i = 0; i < 256; i++) s->inUse[i] = False;
1359
1360 for (i = 0; i < 16; i++)
1361 if (s->inUse16[i])
1362 for (j = 0; j < 16; j++) {
1363 GET_BIT(BZ_X_MAPPING_2, uc);
1364 if (uc == 1) s->inUse[i * 16 + j] = True;
1365 }
1366 makeMaps_d ( s );
1367 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
1368 alphaSize = s->nInUse+2;
1369
1370 /*--- Now the selectors ---*/
1371 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
1372 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
1373 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
1374 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
1375 for (i = 0; i < nSelectors; i++) {
1376 j = 0;
1377 while (True) {
1378 GET_BIT(BZ_X_SELECTOR_3, uc);
1379 if (uc == 0) break;
1380 j++;
1381 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
1382 }
1383 s->selectorMtf[i] = j;
1384 }
1385
1386 /*--- Undo the MTF values for the selectors. ---*/
1387 {
1388 UChar pos[BZ_N_GROUPS], tmp, v;
1389 for (v = 0; v < nGroups; v++) pos[v] = v;
1390
1391 for (i = 0; i < nSelectors; i++) {
1392 v = s->selectorMtf[i];
1393 tmp = pos[v];
1394 while (v > 0) { pos[v] = pos[v-1]; v--; }
1395 pos[0] = tmp;
1396 s->selector[i] = tmp;
1397 }
1398 }
1399
1400 /*--- Now the coding tables ---*/
1401 for (t = 0; t < nGroups; t++) {
1402 GET_BITS(BZ_X_CODING_1, curr, 5);
1403 for (i = 0; i < alphaSize; i++) {
1404 while (True) {
1405 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
1406 GET_BIT(BZ_X_CODING_2, uc);
1407 if (uc == 0) break;
1408 GET_BIT(BZ_X_CODING_3, uc);
1409 if (uc == 0) curr++; else curr--;
1410 }
1411 s->len[t][i] = curr;
1412 }
1413 }
1414
1415 /*--- Create the Huffman decoding tables ---*/
1416 for (t = 0; t < nGroups; t++) {
1417 minLen = 32;
1418 maxLen = 0;
1419 for (i = 0; i < alphaSize; i++) {
1420 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
1421 if (s->len[t][i] < minLen) minLen = s->len[t][i];
1422 }
1423 BZ2_hbCreateDecodeTables (
1424 &(s->limit[t][0]),
1425 &(s->base[t][0]),
1426 &(s->perm[t][0]),
1427 &(s->len[t][0]),
1428 minLen, maxLen, alphaSize
1429 );
1430 s->minLens[t] = minLen;
1431 }
1432
1433 /*--- Now the MTF values ---*/
1434
1435 EOB = s->nInUse+1;
1436 nblockMAX = 100000 * s->blockSize100k;
1437 groupNo = -1;
1438 groupPos = 0;
1439
1440 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
1441
1442 /*-- MTF init --*/
1443 {
1444 Int32 ii, jj, kk;
1445 kk = MTFA_SIZE-1;
1446 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
1447 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1448 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
1449 kk--;
1450 }
1451 s->mtfbase[ii] = kk + 1;
1452 }
1453 }
1454 /*-- end MTF init --*/
1455
1456 nblock = 0;
1457 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
1458
1459 while (True) {
1460
1461 if (nextSym == EOB) break;
1462
1463 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
1464
1465 es = -1;
1466 N = 1;
1467 do {
1468 /* Check that N doesn't get too big, so that es doesn't
1469 go negative. The maximum value that can be
1470 RUNA/RUNB encoded is equal to the block size (post
1471 the initial RLE), viz, 900k, so bounding N at 2
1472 million should guard against overflow without
1473 rejecting any legitimate inputs. */
1474 if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
1475 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
1476 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
1477 N = N * 2;
1478 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
1479 }
1480 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
1481
1482 es++;
1483 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
1484 s->unzftab[uc] += es;
1485
1486 if (s->smallDecompress)
1487 while (es > 0) {
1488 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1489 s->ll16[nblock] = (UInt16)uc;
1490 nblock++;
1491 es--;
1492 }
1493 else
1494 while (es > 0) {
1495 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1496 s->tt[nblock] = (UInt32)uc;
1497 nblock++;
1498 es--;
1499 };
1500
1501 continue;
1502
1503 } else {
1504
1505 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1506
1507 /*-- uc = MTF ( nextSym-1 ) --*/
1508 {
1509 Int32 ii, jj, kk, pp, lno, off;
1510 UInt32 nn;
1511 nn = (UInt32)(nextSym - 1);
1512
1513 if (nn < MTFL_SIZE) {
1514 /* avoid general-case expense */
1515 pp = s->mtfbase[0];
1516 uc = s->mtfa[pp+nn];
1517 while (nn > 3) {
1518 Int32 z = pp+nn;
1519 s->mtfa[(z) ] = s->mtfa[(z)-1];
1520 s->mtfa[(z)-1] = s->mtfa[(z)-2];
1521 s->mtfa[(z)-2] = s->mtfa[(z)-3];
1522 s->mtfa[(z)-3] = s->mtfa[(z)-4];
1523 nn -= 4;
1524 }
1525 while (nn > 0) {
1526 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1527 };
1528 s->mtfa[pp] = uc;
1529 } else {
1530 /* general case */
1531 lno = nn / MTFL_SIZE;
1532 off = nn % MTFL_SIZE;
1533 pp = s->mtfbase[lno] + off;
1534 uc = s->mtfa[pp];
1535 while (pp > s->mtfbase[lno]) {
1536 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
1537 };
1538 s->mtfbase[lno]++;
1539 while (lno > 0) {
1540 s->mtfbase[lno]--;
1541 s->mtfa[s->mtfbase[lno]]
1542 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1543 lno--;
1544 }
1545 s->mtfbase[0]--;
1546 s->mtfa[s->mtfbase[0]] = uc;
1547 if (s->mtfbase[0] == 0) {
1548 kk = MTFA_SIZE-1;
1549 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1550 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1551 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1552 kk--;
1553 }
1554 s->mtfbase[ii] = kk + 1;
1555 }
1556 }
1557 }
1558 }
1559 /*-- end uc = MTF ( nextSym-1 ) --*/
1560
1561 s->unzftab[s->seqToUnseq[uc]]++;
1562 if (s->smallDecompress)
1563 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
1564 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
1565 nblock++;
1566
1567 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
1568 continue;
1569 }
1570 }
1571
1572 /* Now we know what nblock is, we can do a better sanity
1573 check on s->origPtr.
1574 */
1575 if (s->origPtr < 0 || s->origPtr >= nblock)
1576 RETURN(BZ_DATA_ERROR);
1577
1578 /*-- Set up cftab to facilitate generation of T^(-1) --*/
1579 /* Check: unzftab entries in range. */
1580 for (i = 0; i <= 255; i++) {
1581 if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)
1582 RETURN(BZ_DATA_ERROR);
1583 }
1584 /* Actually generate cftab. */
1585 s->cftab[0] = 0;
1586 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
1587 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
1588 /* Check: cftab entries in range. */
1589 for (i = 0; i <= 256; i++) {
1590 if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
1591 /* s->cftab[i] can legitimately be == nblock */
1592 RETURN(BZ_DATA_ERROR);
1593 }
1594 }
1595 /* Check: cftab entries non-descending. */
1596 for (i = 1; i <= 256; i++) {
1597 if (s->cftab[i-1] > s->cftab[i]) {
1598 RETURN(BZ_DATA_ERROR);
1599 }
1600 }
1601
1602 s->state_out_len = 0;
1603 s->state_out_ch = 0;
1604 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
1605 s->state = BZ_X_OUTPUT;
1606 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
1607
1608 if (s->smallDecompress) {
1609
1610 /*-- Make a copy of cftab, used in generation of T --*/
1611 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
1612
1613 /*-- compute the T vector --*/
1614 for (i = 0; i < nblock; i++) {
1615 uc = (UChar)(s->ll16[i]);
1616 SET_LL(i, s->cftabCopy[uc]);
1617 s->cftabCopy[uc]++;
1618 }
1619
1620 /*-- Compute T^(-1) by pointer reversal on T --*/
1621 i = s->origPtr;
1622 j = GET_LL(i);
1623 do {
1624 Int32 tmp = GET_LL(j);
1625 SET_LL(j, i);
1626 i = j;
1627 j = tmp;
1628 }
1629 while (i != s->origPtr);
1630
1631 s->tPos = s->origPtr;
1632 s->nblock_used = 0;
1633 if (s->blockRandomised) {
1634 BZ_RAND_INIT_MASK;
1635 BZ_GET_SMALL(s->k0); s->nblock_used++;
1636 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
1637 } else {
1638 BZ_GET_SMALL(s->k0); s->nblock_used++;
1639 }
1640
1641 } else {
1642
1643 /*-- compute the T^(-1) vector --*/
1644 for (i = 0; i < nblock; i++) {
1645 uc = (UChar)(s->tt[i] & 0xff);
1646 s->tt[s->cftab[uc]] |= (i << 8);
1647 s->cftab[uc]++;
1648 }
1649
1650 s->tPos = s->tt[s->origPtr] >> 8;
1651 s->nblock_used = 0;
1652 if (s->blockRandomised) {
1653 BZ_RAND_INIT_MASK;
1654 BZ_GET_FAST(s->k0); s->nblock_used++;
1655 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
1656 } else {
1657 BZ_GET_FAST(s->k0); s->nblock_used++;
1658 }
1659
1660 }
1661
1662 RETURN(BZ_OK);
1663
1664
1665
1666 endhdr_2:
1667
1668 GET_UCHAR(BZ_X_ENDHDR_2, uc);
1669 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
1670 GET_UCHAR(BZ_X_ENDHDR_3, uc);
1671 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
1672 GET_UCHAR(BZ_X_ENDHDR_4, uc);
1673 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
1674 GET_UCHAR(BZ_X_ENDHDR_5, uc);
1675 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
1676 GET_UCHAR(BZ_X_ENDHDR_6, uc);
1677 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
1678
1679 s->storedCombinedCRC = 0;
1680 GET_UCHAR(BZ_X_CCRC_1, uc);
1681 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1682 GET_UCHAR(BZ_X_CCRC_2, uc);
1683 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1684 GET_UCHAR(BZ_X_CCRC_3, uc);
1685 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1686 GET_UCHAR(BZ_X_CCRC_4, uc);
1687 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1688
1689 s->state = BZ_X_IDLE;
1690 RETURN(BZ_STREAM_END);
1691
1692 default: AssertH ( False, 4001 );
1693 }
1694
1695 AssertH ( False, 4002 );
1696
1697 save_state_and_return:
1698
1699 s->save_i = i;
1700 s->save_j = j;
1701 s->save_t = t;
1702 s->save_alphaSize = alphaSize;
1703 s->save_nGroups = nGroups;
1704 s->save_nSelectors = nSelectors;
1705 s->save_EOB = EOB;
1706 s->save_groupNo = groupNo;
1707 s->save_groupPos = groupPos;
1708 s->save_nextSym = nextSym;
1709 s->save_nblockMAX = nblockMAX;
1710 s->save_nblock = nblock;
1711 s->save_es = es;
1712 s->save_N = N;
1713 s->save_curr = curr;
1714 s->save_zt = zt;
1715 s->save_zn = zn;
1716 s->save_zvec = zvec;
1717 s->save_zj = zj;
1718 s->save_gSel = gSel;
1719 s->save_gMinlen = gMinlen;
1720 s->save_gLimit = gLimit;
1721 s->save_gBase = gBase;
1722 s->save_gPerm = gPerm;
1723
1724 return retVal;
1725 }
1726
1727
1728 /*-------------------------------------------------------------*/
1729 /*--- end decompress.c ---*/
1730 /*-------------------------------------------------------------*/
1731 /* $NetBSD: bzlib.c,v 1.3 2015/02/05 01:26:54 agc Exp $ */
1732
1733
1734 /*-------------------------------------------------------------*/
1735 /*--- Table for doing CRCs ---*/
1736 /*--- crctable.c ---*/
1737 /*-------------------------------------------------------------*/
1738
1739 /* ------------------------------------------------------------------
1740 This file is part of bzip2/libbzip2, a program and library for
1741 lossless, block-sorting data compression.
1742
1743 bzip2/libbzip2 version 1.0.6 of 6 September 2010
1744 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
1745
1746 Please read the WARNING, DISCLAIMER and PATENTS sections in the
1747 README file.
1748
1749 This program is released under the terms of the license contained
1750 in the file LICENSE.
1751 ------------------------------------------------------------------ */
1752
1753
1754 /*--
1755 I think this is an implementation of the AUTODIN-II,
1756 Ethernet & FDDI 32-bit CRC standard. Vaguely derived
1757 from code by Rob Warnock, in Section 51 of the
1758 comp.compression FAQ.
1759 --*/
1760
1761 UInt32 BZ2_crc32Table[256] = {
1762
1763 /*-- Ugly, innit? --*/
1764
1765 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
1766 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
1767 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
1768 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
1769 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
1770 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
1771 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
1772 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
1773 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
1774 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
1775 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
1776 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
1777 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
1778 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
1779 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
1780 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
1781 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
1782 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
1783 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
1784 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
1785 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
1786 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
1787 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
1788 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
1789 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
1790 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
1791 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
1792 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
1793 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
1794 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
1795 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
1796 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
1797 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
1798 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
1799 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
1800 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
1801 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
1802 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
1803 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
1804 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
1805 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
1806 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
1807 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
1808 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
1809 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
1810 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
1811 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
1812 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
1813 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
1814 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
1815 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
1816 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
1817 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
1818 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
1819 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
1820 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
1821 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
1822 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
1823 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
1824 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
1825 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
1826 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
1827 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
1828 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
1829 };
1830
1831
1832 /*-------------------------------------------------------------*/
1833 /*--- end crctable.c ---*/
1834 /*-------------------------------------------------------------*/
1835 /* $NetBSD: bzlib.c,v 1.3 2015/02/05 01:26:54 agc Exp $ */
1836
1837
1838 /*-------------------------------------------------------------*/
1839 /*--- Huffman coding low-level stuff ---*/
1840 /*--- huffman.c ---*/
1841 /*-------------------------------------------------------------*/
1842
1843 /* ------------------------------------------------------------------
1844 This file is part of bzip2/libbzip2, a program and library for
1845 lossless, block-sorting data compression.
1846
1847 bzip2/libbzip2 version 1.0.6 of 6 September 2010
1848 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
1849
1850 Please read the WARNING, DISCLAIMER and PATENTS sections in the
1851 README file.
1852
1853 This program is released under the terms of the license contained
1854 in the file LICENSE.
1855 ------------------------------------------------------------------ */
1856
1857
1858 /*---------------------------------------------------*/
1859 #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
1860 #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
1861 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
1862
1863 #define ADDWEIGHTS(zw1,zw2) \
1864 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
1865 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
1866
1867 #define UPHEAP(z) \
1868 { \
1869 Int32 zz, tmp; \
1870 zz = z; tmp = heap[zz]; \
1871 while (weight[tmp] < weight[heap[zz >> 1]]) { \
1872 heap[zz] = heap[zz >> 1]; \
1873 zz >>= 1; \
1874 } \
1875 heap[zz] = tmp; \
1876 }
1877
1878 #define DOWNHEAP(z) \
1879 { \
1880 Int32 zz, yy, tmp; \
1881 zz = z; tmp = heap[zz]; \
1882 while (True) { \
1883 yy = zz << 1; \
1884 if (yy > nHeap) break; \
1885 if (yy < nHeap && \
1886 weight[heap[yy+1]] < weight[heap[yy]]) \
1887 yy++; \
1888 if (weight[tmp] < weight[heap[yy]]) break; \
1889 heap[zz] = heap[yy]; \
1890 zz = yy; \
1891 } \
1892 heap[zz] = tmp; \
1893 }
1894
1895
1896 /*---------------------------------------------------*/
BZ2_hbMakeCodeLengths(UChar * len,Int32 * freq,Int32 alphaSize,Int32 maxLen)1897 void BZ2_hbMakeCodeLengths ( UChar *len,
1898 Int32 *freq,
1899 Int32 alphaSize,
1900 Int32 maxLen )
1901 {
1902 /*--
1903 Nodes and heap entries run from 1. Entry 0
1904 for both the heap and nodes is a sentinel.
1905 --*/
1906 Int32 nNodes, nHeap, n1, n2, i, j, k;
1907 Bool tooLong;
1908
1909 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
1910 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
1911 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
1912
1913 for (i = 0; i < alphaSize; i++)
1914 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
1915
1916 while (True) {
1917
1918 nNodes = alphaSize;
1919 nHeap = 0;
1920
1921 heap[0] = 0;
1922 weight[0] = 0;
1923 parent[0] = -2;
1924
1925 for (i = 1; i <= alphaSize; i++) {
1926 parent[i] = -1;
1927 nHeap++;
1928 heap[nHeap] = i;
1929 UPHEAP(nHeap);
1930 }
1931
1932 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
1933
1934 while (nHeap > 1) {
1935 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
1936 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
1937 nNodes++;
1938 parent[n1] = parent[n2] = nNodes;
1939 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
1940 parent[nNodes] = -1;
1941 nHeap++;
1942 heap[nHeap] = nNodes;
1943 UPHEAP(nHeap);
1944 }
1945
1946 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
1947
1948 tooLong = False;
1949 for (i = 1; i <= alphaSize; i++) {
1950 j = 0;
1951 k = i;
1952 while (parent[k] >= 0) { k = parent[k]; j++; }
1953 len[i-1] = j;
1954 if (j > maxLen) tooLong = True;
1955 }
1956
1957 if (! tooLong) break;
1958
1959 /* 17 Oct 04: keep-going condition for the following loop used
1960 to be 'i < alphaSize', which missed the last element,
1961 theoretically leading to the possibility of the compressor
1962 looping. However, this count-scaling step is only needed if
1963 one of the generated Huffman code words is longer than
1964 maxLen, which up to and including version 1.0.2 was 20 bits,
1965 which is extremely unlikely. In version 1.0.3 maxLen was
1966 changed to 17 bits, which has minimal effect on compression
1967 ratio, but does mean this scaling step is used from time to
1968 time, enough to verify that it works.
1969
1970 This means that bzip2-1.0.3 and later will only produce
1971 Huffman codes with a maximum length of 17 bits. However, in
1972 order to preserve backwards compatibility with bitstreams
1973 produced by versions pre-1.0.3, the decompressor must still
1974 handle lengths of up to 20. */
1975
1976 for (i = 1; i <= alphaSize; i++) {
1977 j = weight[i] >> 8;
1978 j = 1 + (j / 2);
1979 weight[i] = j << 8;
1980 }
1981 }
1982 }
1983
1984
1985 /*---------------------------------------------------*/
BZ2_hbAssignCodes(Int32 * code,UChar * length,Int32 minLen,Int32 maxLen,Int32 alphaSize)1986 void BZ2_hbAssignCodes ( Int32 *code,
1987 UChar *length,
1988 Int32 minLen,
1989 Int32 maxLen,
1990 Int32 alphaSize )
1991 {
1992 Int32 n, vec, i;
1993
1994 vec = 0;
1995 for (n = minLen; n <= maxLen; n++) {
1996 for (i = 0; i < alphaSize; i++)
1997 if (length[i] == n) { code[i] = vec; vec++; };
1998 vec <<= 1;
1999 }
2000 }
2001
2002
2003 /*---------------------------------------------------*/
BZ2_hbCreateDecodeTables(Int32 * limit,Int32 * base,Int32 * perm,UChar * length,Int32 minLen,Int32 maxLen,Int32 alphaSize)2004 void BZ2_hbCreateDecodeTables ( Int32 *limit,
2005 Int32 *base,
2006 Int32 *perm,
2007 UChar *length,
2008 Int32 minLen,
2009 Int32 maxLen,
2010 Int32 alphaSize )
2011 {
2012 Int32 pp, i, j, vec;
2013
2014 pp = 0;
2015 for (i = minLen; i <= maxLen; i++)
2016 for (j = 0; j < alphaSize; j++)
2017 if (length[j] == i) { perm[pp] = j; pp++; };
2018
2019 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
2020 for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
2021
2022 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
2023
2024 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
2025 vec = 0;
2026
2027 for (i = minLen; i <= maxLen; i++) {
2028 vec += (base[i+1] - base[i]);
2029 limit[i] = vec-1;
2030 vec <<= 1;
2031 }
2032 for (i = minLen + 1; i <= maxLen; i++)
2033 base[i] = ((limit[i-1] + 1) << 1) - base[i];
2034 }
2035
2036
2037 /*-------------------------------------------------------------*/
2038 /*--- end huffman.c ---*/
2039 /*-------------------------------------------------------------*/
2040