1 /* $NetBSD: bzlib.c,v 1.2 2014/03/09 07:01:42 christos 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.2 2014/03/09 07:01:42 christos 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 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 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 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 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 /*---------------------------------------------------*/ 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 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 /*---------------------------------------------------*/ 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 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------*/ 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 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 --*/ 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 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(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 --*/ 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 1021 int BZ_API(BZ2_bzflush) (BZFILE *b) 1022 { 1023 USE_ARG(b); 1024 /* do nothing now... */ 1025 return 0; 1026 } 1027 1028 1029 /*---------------------------------------------------*/ 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 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.2 2014/03/09 07:01:42 christos 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 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 /*---------------------------------------------------*/ 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.2 2014/03/09 07:01:42 christos 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.2 2014/03/09 07:01:42 christos 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 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 /*---------------------------------------------------*/ 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