1 /* $NetBSD: bzlib.c,v 1.1 2014/03/09 00:15:45 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.1 2014/03/09 00:15:45 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 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 if (mode == NULL) return NULL; 934 while (*mode) { 935 switch (*mode) { 936 case 'r': 937 writing = 0; break; 938 case 'w': 939 writing = 1; break; 940 case 's': 941 smallMode = 1; break; 942 default: 943 if (isdigit((unsigned char)(*mode))) { 944 blockSize100k = *mode-BZ_HDR_0; 945 } 946 } 947 mode++; 948 } 949 strcat(mode2, writing ? "w" : "r" ); 950 strcat(mode2,"b"); /* binary mode */ 951 952 if (open_mode==0) { 953 if (path==NULL || strcmp(path,"")==0) { 954 fp = (writing ? stdout : stdin); 955 SET_BINARY_MODE(fp); 956 } else { 957 fp = fopen(path,mode2); 958 } 959 } else { 960 #ifdef BZ_STRICT_ANSI 961 fp = NULL; 962 #else 963 fp = fdopen(fd,mode2); 964 #endif 965 } 966 if (fp == NULL) return NULL; 967 968 if (writing) { 969 } else { 970 bzfp = BZ2_bzReadOpen(&bzerr,fp,verbosity,smallMode, 971 unused,nUnused); 972 } 973 if (bzfp == NULL) { 974 if (fp != stdin && fp != stdout) fclose(fp); 975 return NULL; 976 } 977 return bzfp; 978 } 979 980 981 /*---------------------------------------------------*/ 982 /*-- 983 open file for read or write. 984 ex) bzopen("file","w9") 985 case path="" or NULL => use stdin or stdout. 986 --*/ 987 BZFILE * BZ_API(BZ2_bzopen) 988 ( const char *path, 989 const char *mode ) 990 { 991 return bzopen_or_bzdopen(path,-1,mode,/*bzopen*/0); 992 } 993 994 995 /*---------------------------------------------------*/ 996 BZFILE * BZ_API(BZ2_bzdopen) 997 ( int fd, 998 const char *mode ) 999 { 1000 return bzopen_or_bzdopen(NULL,fd,mode,/*bzdopen*/1); 1001 } 1002 1003 1004 /*---------------------------------------------------*/ 1005 int BZ_API(BZ2_bzread) (BZFILE* b, void* buf, int len ) 1006 { 1007 int bzerr, nread; 1008 if (((bzFile*)b)->lastErr == BZ_STREAM_END) return 0; 1009 nread = BZ2_bzRead(&bzerr,b,buf,len); 1010 if (bzerr == BZ_OK || bzerr == BZ_STREAM_END) { 1011 return nread; 1012 } else { 1013 return -1; 1014 } 1015 } 1016 1017 1018 /*---------------------------------------------------*/ 1019 int BZ_API(BZ2_bzflush) (BZFILE *b) 1020 { 1021 USE_ARG(b); 1022 /* do nothing now... */ 1023 return 0; 1024 } 1025 1026 1027 /*---------------------------------------------------*/ 1028 void BZ_API(BZ2_bzclose) (BZFILE* b) 1029 { 1030 int bzerr; 1031 FILE *fp; 1032 1033 if (b==NULL) {return;} 1034 fp = ((bzFile *)b)->handle; 1035 if(((bzFile*)b)->writing){ 1036 }else{ 1037 BZ2_bzReadClose(&bzerr,b); 1038 } 1039 if(fp!=stdin && fp!=stdout){ 1040 fclose(fp); 1041 } 1042 } 1043 1044 1045 /*---------------------------------------------------*/ 1046 /*-- 1047 return last error code 1048 --*/ 1049 static const char *bzerrorstrings[] = { 1050 "OK" 1051 ,"SEQUENCE_ERROR" 1052 ,"PARAM_ERROR" 1053 ,"MEM_ERROR" 1054 ,"DATA_ERROR" 1055 ,"DATA_ERROR_MAGIC" 1056 ,"IO_ERROR" 1057 ,"UNEXPECTED_EOF" 1058 ,"OUTBUFF_FULL" 1059 ,"CONFIG_ERROR" 1060 ,"???" /* for future */ 1061 ,"???" /* for future */ 1062 ,"???" /* for future */ 1063 ,"???" /* for future */ 1064 ,"???" /* for future */ 1065 ,"???" /* for future */ 1066 }; 1067 1068 1069 const char * BZ_API(BZ2_bzerror) (BZFILE *b, int *errnum) 1070 { 1071 int err = ((bzFile *)b)->lastErr; 1072 1073 if(err>0) err = 0; 1074 *errnum = err; 1075 return bzerrorstrings[err*-1]; 1076 } 1077 #endif 1078 1079 1080 /*-------------------------------------------------------------*/ 1081 /*--- end bzlib.c ---*/ 1082 /*-------------------------------------------------------------*/ 1083 /* $NetBSD: bzlib.c,v 1.1 2014/03/09 00:15:45 agc Exp $ */ 1084 1085 1086 /*-------------------------------------------------------------*/ 1087 /*--- Decompression machinery ---*/ 1088 /*--- decompress.c ---*/ 1089 /*-------------------------------------------------------------*/ 1090 1091 /* ------------------------------------------------------------------ 1092 This file is part of bzip2/libbzip2, a program and library for 1093 lossless, block-sorting data compression. 1094 1095 bzip2/libbzip2 version 1.0.6 of 6 September 2010 1096 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org> 1097 1098 Please read the WARNING, DISCLAIMER and PATENTS sections in the 1099 README file. 1100 1101 This program is released under the terms of the license contained 1102 in the file LICENSE. 1103 ------------------------------------------------------------------ */ 1104 1105 1106 1107 /*---------------------------------------------------*/ 1108 static 1109 void makeMaps_d ( DState* s ) 1110 { 1111 Int32 i; 1112 s->nInUse = 0; 1113 for (i = 0; i < 256; i++) 1114 if (s->inUse[i]) { 1115 s->seqToUnseq[s->nInUse] = i; 1116 s->nInUse++; 1117 } 1118 } 1119 1120 1121 /*---------------------------------------------------*/ 1122 #define RETURN(rrr) \ 1123 { retVal = rrr; goto save_state_and_return; }; 1124 1125 #define GET_BITS(lll,vvv,nnn) \ 1126 case lll: s->state = lll; \ 1127 while (True) { \ 1128 if (s->bsLive >= nnn) { \ 1129 UInt32 v; \ 1130 v = (s->bsBuff >> \ 1131 (s->bsLive-nnn)) & ((1 << nnn)-1); \ 1132 s->bsLive -= nnn; \ 1133 vvv = v; \ 1134 break; \ 1135 } \ 1136 if (s->strm->avail_in == 0) RETURN(BZ_OK); \ 1137 s->bsBuff \ 1138 = (s->bsBuff << 8) | \ 1139 ((UInt32) \ 1140 (*((UChar*)(s->strm->next_in)))); \ 1141 s->bsLive += 8; \ 1142 s->strm->next_in++; \ 1143 s->strm->avail_in--; \ 1144 s->strm->total_in_lo32++; \ 1145 if (s->strm->total_in_lo32 == 0) \ 1146 s->strm->total_in_hi32++; \ 1147 } 1148 1149 #define GET_UCHAR(lll,uuu) \ 1150 GET_BITS(lll,uuu,8) 1151 1152 #define GET_BIT(lll,uuu) \ 1153 GET_BITS(lll,uuu,1) 1154 1155 /*---------------------------------------------------*/ 1156 #define GET_MTF_VAL(label1,label2,lval) \ 1157 { \ 1158 if (groupPos == 0) { \ 1159 groupNo++; \ 1160 if (groupNo >= nSelectors) \ 1161 RETURN(BZ_DATA_ERROR); \ 1162 groupPos = BZ_G_SIZE; \ 1163 gSel = s->selector[groupNo]; \ 1164 gMinlen = s->minLens[gSel]; \ 1165 gLimit = &(s->limit[gSel][0]); \ 1166 gPerm = &(s->perm[gSel][0]); \ 1167 gBase = &(s->base[gSel][0]); \ 1168 } \ 1169 groupPos--; \ 1170 zn = gMinlen; \ 1171 GET_BITS(label1, zvec, zn); \ 1172 while (1) { \ 1173 if (zn > 20 /* the longest code */) \ 1174 RETURN(BZ_DATA_ERROR); \ 1175 if (zvec <= gLimit[zn]) break; \ 1176 zn++; \ 1177 GET_BIT(label2, zj); \ 1178 zvec = (zvec << 1) | zj; \ 1179 }; \ 1180 if (zvec - gBase[zn] < 0 \ 1181 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ 1182 RETURN(BZ_DATA_ERROR); \ 1183 lval = gPerm[zvec - gBase[zn]]; \ 1184 } 1185 1186 1187 /*---------------------------------------------------*/ 1188 Int32 BZ2_decompress ( DState* s ) 1189 { 1190 UChar uc; 1191 Int32 retVal; 1192 Int32 minLen, maxLen; 1193 bz_stream* strm = s->strm; 1194 1195 /* stuff that needs to be saved/restored */ 1196 Int32 i; 1197 Int32 j; 1198 Int32 t; 1199 Int32 alphaSize; 1200 Int32 nGroups; 1201 Int32 nSelectors; 1202 Int32 EOB; 1203 Int32 groupNo; 1204 Int32 groupPos; 1205 Int32 nextSym; 1206 Int32 nblockMAX; 1207 Int32 nblock; 1208 Int32 es; 1209 Int32 N; 1210 Int32 curr; 1211 Int32 zt; 1212 Int32 zn; 1213 Int32 zvec; 1214 Int32 zj; 1215 Int32 gSel; 1216 Int32 gMinlen; 1217 Int32* gLimit; 1218 Int32* gBase; 1219 Int32* gPerm; 1220 1221 if (s->state == BZ_X_MAGIC_1) { 1222 /*initialise the save area*/ 1223 s->save_i = 0; 1224 s->save_j = 0; 1225 s->save_t = 0; 1226 s->save_alphaSize = 0; 1227 s->save_nGroups = 0; 1228 s->save_nSelectors = 0; 1229 s->save_EOB = 0; 1230 s->save_groupNo = 0; 1231 s->save_groupPos = 0; 1232 s->save_nextSym = 0; 1233 s->save_nblockMAX = 0; 1234 s->save_nblock = 0; 1235 s->save_es = 0; 1236 s->save_N = 0; 1237 s->save_curr = 0; 1238 s->save_zt = 0; 1239 s->save_zn = 0; 1240 s->save_zvec = 0; 1241 s->save_zj = 0; 1242 s->save_gSel = 0; 1243 s->save_gMinlen = 0; 1244 s->save_gLimit = NULL; 1245 s->save_gBase = NULL; 1246 s->save_gPerm = NULL; 1247 } 1248 1249 /*restore from the save area*/ 1250 i = s->save_i; 1251 j = s->save_j; 1252 t = s->save_t; 1253 alphaSize = s->save_alphaSize; 1254 nGroups = s->save_nGroups; 1255 nSelectors = s->save_nSelectors; 1256 EOB = s->save_EOB; 1257 groupNo = s->save_groupNo; 1258 groupPos = s->save_groupPos; 1259 nextSym = s->save_nextSym; 1260 nblockMAX = s->save_nblockMAX; 1261 nblock = s->save_nblock; 1262 es = s->save_es; 1263 N = s->save_N; 1264 curr = s->save_curr; 1265 zt = s->save_zt; 1266 zn = s->save_zn; 1267 zvec = s->save_zvec; 1268 zj = s->save_zj; 1269 gSel = s->save_gSel; 1270 gMinlen = s->save_gMinlen; 1271 gLimit = s->save_gLimit; 1272 gBase = s->save_gBase; 1273 gPerm = s->save_gPerm; 1274 1275 retVal = BZ_OK; 1276 1277 switch (s->state) { 1278 1279 GET_UCHAR(BZ_X_MAGIC_1, uc); 1280 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC); 1281 1282 GET_UCHAR(BZ_X_MAGIC_2, uc); 1283 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC); 1284 1285 GET_UCHAR(BZ_X_MAGIC_3, uc) 1286 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC); 1287 1288 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) 1289 if (s->blockSize100k < (BZ_HDR_0 + 1) || 1290 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC); 1291 s->blockSize100k -= BZ_HDR_0; 1292 1293 if (s->smallDecompress) { 1294 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); 1295 s->ll4 = BZALLOC( 1296 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) 1297 ); 1298 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); 1299 } else { 1300 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); 1301 if (s->tt == NULL) RETURN(BZ_MEM_ERROR); 1302 } 1303 1304 GET_UCHAR(BZ_X_BLKHDR_1, uc); 1305 1306 if (uc == 0x17) goto endhdr_2; 1307 if (uc != 0x31) RETURN(BZ_DATA_ERROR); 1308 GET_UCHAR(BZ_X_BLKHDR_2, uc); 1309 if (uc != 0x41) RETURN(BZ_DATA_ERROR); 1310 GET_UCHAR(BZ_X_BLKHDR_3, uc); 1311 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 1312 GET_UCHAR(BZ_X_BLKHDR_4, uc); 1313 if (uc != 0x26) RETURN(BZ_DATA_ERROR); 1314 GET_UCHAR(BZ_X_BLKHDR_5, uc); 1315 if (uc != 0x53) RETURN(BZ_DATA_ERROR); 1316 GET_UCHAR(BZ_X_BLKHDR_6, uc); 1317 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 1318 1319 s->currBlockNo++; 1320 if (s->verbosity >= 2) 1321 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); 1322 1323 s->storedBlockCRC = 0; 1324 GET_UCHAR(BZ_X_BCRC_1, uc); 1325 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 1326 GET_UCHAR(BZ_X_BCRC_2, uc); 1327 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 1328 GET_UCHAR(BZ_X_BCRC_3, uc); 1329 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 1330 GET_UCHAR(BZ_X_BCRC_4, uc); 1331 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 1332 1333 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); 1334 1335 s->origPtr = 0; 1336 GET_UCHAR(BZ_X_ORIGPTR_1, uc); 1337 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 1338 GET_UCHAR(BZ_X_ORIGPTR_2, uc); 1339 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 1340 GET_UCHAR(BZ_X_ORIGPTR_3, uc); 1341 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 1342 1343 if (s->origPtr < 0) 1344 RETURN(BZ_DATA_ERROR); 1345 if (s->origPtr > 10 + 100000*s->blockSize100k) 1346 RETURN(BZ_DATA_ERROR); 1347 1348 /*--- Receive the mapping table ---*/ 1349 for (i = 0; i < 16; i++) { 1350 GET_BIT(BZ_X_MAPPING_1, uc); 1351 if (uc == 1) 1352 s->inUse16[i] = True; else 1353 s->inUse16[i] = False; 1354 } 1355 1356 for (i = 0; i < 256; i++) s->inUse[i] = False; 1357 1358 for (i = 0; i < 16; i++) 1359 if (s->inUse16[i]) 1360 for (j = 0; j < 16; j++) { 1361 GET_BIT(BZ_X_MAPPING_2, uc); 1362 if (uc == 1) s->inUse[i * 16 + j] = True; 1363 } 1364 makeMaps_d ( s ); 1365 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); 1366 alphaSize = s->nInUse+2; 1367 1368 /*--- Now the selectors ---*/ 1369 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); 1370 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); 1371 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); 1372 if (nSelectors < 1) RETURN(BZ_DATA_ERROR); 1373 for (i = 0; i < nSelectors; i++) { 1374 j = 0; 1375 while (True) { 1376 GET_BIT(BZ_X_SELECTOR_3, uc); 1377 if (uc == 0) break; 1378 j++; 1379 if (j >= nGroups) RETURN(BZ_DATA_ERROR); 1380 } 1381 s->selectorMtf[i] = j; 1382 } 1383 1384 /*--- Undo the MTF values for the selectors. ---*/ 1385 { 1386 UChar pos[BZ_N_GROUPS], tmp, v; 1387 for (v = 0; v < nGroups; v++) pos[v] = v; 1388 1389 for (i = 0; i < nSelectors; i++) { 1390 v = s->selectorMtf[i]; 1391 tmp = pos[v]; 1392 while (v > 0) { pos[v] = pos[v-1]; v--; } 1393 pos[0] = tmp; 1394 s->selector[i] = tmp; 1395 } 1396 } 1397 1398 /*--- Now the coding tables ---*/ 1399 for (t = 0; t < nGroups; t++) { 1400 GET_BITS(BZ_X_CODING_1, curr, 5); 1401 for (i = 0; i < alphaSize; i++) { 1402 while (True) { 1403 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); 1404 GET_BIT(BZ_X_CODING_2, uc); 1405 if (uc == 0) break; 1406 GET_BIT(BZ_X_CODING_3, uc); 1407 if (uc == 0) curr++; else curr--; 1408 } 1409 s->len[t][i] = curr; 1410 } 1411 } 1412 1413 /*--- Create the Huffman decoding tables ---*/ 1414 for (t = 0; t < nGroups; t++) { 1415 minLen = 32; 1416 maxLen = 0; 1417 for (i = 0; i < alphaSize; i++) { 1418 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 1419 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 1420 } 1421 BZ2_hbCreateDecodeTables ( 1422 &(s->limit[t][0]), 1423 &(s->base[t][0]), 1424 &(s->perm[t][0]), 1425 &(s->len[t][0]), 1426 minLen, maxLen, alphaSize 1427 ); 1428 s->minLens[t] = minLen; 1429 } 1430 1431 /*--- Now the MTF values ---*/ 1432 1433 EOB = s->nInUse+1; 1434 nblockMAX = 100000 * s->blockSize100k; 1435 groupNo = -1; 1436 groupPos = 0; 1437 1438 for (i = 0; i <= 255; i++) s->unzftab[i] = 0; 1439 1440 /*-- MTF init --*/ 1441 { 1442 Int32 ii, jj, kk; 1443 kk = MTFA_SIZE-1; 1444 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { 1445 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 1446 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); 1447 kk--; 1448 } 1449 s->mtfbase[ii] = kk + 1; 1450 } 1451 } 1452 /*-- end MTF init --*/ 1453 1454 nblock = 0; 1455 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); 1456 1457 while (True) { 1458 1459 if (nextSym == EOB) break; 1460 1461 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { 1462 1463 es = -1; 1464 N = 1; 1465 do { 1466 /* Check that N doesn't get too big, so that es doesn't 1467 go negative. The maximum value that can be 1468 RUNA/RUNB encoded is equal to the block size (post 1469 the initial RLE), viz, 900k, so bounding N at 2 1470 million should guard against overflow without 1471 rejecting any legitimate inputs. */ 1472 if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR); 1473 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 1474 if (nextSym == BZ_RUNB) es = es + (1+1) * N; 1475 N = N * 2; 1476 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 1477 } 1478 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 1479 1480 es++; 1481 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 1482 s->unzftab[uc] += es; 1483 1484 if (s->smallDecompress) 1485 while (es > 0) { 1486 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 1487 s->ll16[nblock] = (UInt16)uc; 1488 nblock++; 1489 es--; 1490 } 1491 else 1492 while (es > 0) { 1493 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 1494 s->tt[nblock] = (UInt32)uc; 1495 nblock++; 1496 es--; 1497 }; 1498 1499 continue; 1500 1501 } else { 1502 1503 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 1504 1505 /*-- uc = MTF ( nextSym-1 ) --*/ 1506 { 1507 Int32 ii, jj, kk, pp, lno, off; 1508 UInt32 nn; 1509 nn = (UInt32)(nextSym - 1); 1510 1511 if (nn < MTFL_SIZE) { 1512 /* avoid general-case expense */ 1513 pp = s->mtfbase[0]; 1514 uc = s->mtfa[pp+nn]; 1515 while (nn > 3) { 1516 Int32 z = pp+nn; 1517 s->mtfa[(z) ] = s->mtfa[(z)-1]; 1518 s->mtfa[(z)-1] = s->mtfa[(z)-2]; 1519 s->mtfa[(z)-2] = s->mtfa[(z)-3]; 1520 s->mtfa[(z)-3] = s->mtfa[(z)-4]; 1521 nn -= 4; 1522 } 1523 while (nn > 0) { 1524 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 1525 }; 1526 s->mtfa[pp] = uc; 1527 } else { 1528 /* general case */ 1529 lno = nn / MTFL_SIZE; 1530 off = nn % MTFL_SIZE; 1531 pp = s->mtfbase[lno] + off; 1532 uc = s->mtfa[pp]; 1533 while (pp > s->mtfbase[lno]) { 1534 s->mtfa[pp] = s->mtfa[pp-1]; pp--; 1535 }; 1536 s->mtfbase[lno]++; 1537 while (lno > 0) { 1538 s->mtfbase[lno]--; 1539 s->mtfa[s->mtfbase[lno]] 1540 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 1541 lno--; 1542 } 1543 s->mtfbase[0]--; 1544 s->mtfa[s->mtfbase[0]] = uc; 1545 if (s->mtfbase[0] == 0) { 1546 kk = MTFA_SIZE-1; 1547 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 1548 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 1549 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 1550 kk--; 1551 } 1552 s->mtfbase[ii] = kk + 1; 1553 } 1554 } 1555 } 1556 } 1557 /*-- end uc = MTF ( nextSym-1 ) --*/ 1558 1559 s->unzftab[s->seqToUnseq[uc]]++; 1560 if (s->smallDecompress) 1561 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 1562 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 1563 nblock++; 1564 1565 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 1566 continue; 1567 } 1568 } 1569 1570 /* Now we know what nblock is, we can do a better sanity 1571 check on s->origPtr. 1572 */ 1573 if (s->origPtr < 0 || s->origPtr >= nblock) 1574 RETURN(BZ_DATA_ERROR); 1575 1576 /*-- Set up cftab to facilitate generation of T^(-1) --*/ 1577 /* Check: unzftab entries in range. */ 1578 for (i = 0; i <= 255; i++) { 1579 if (s->unzftab[i] < 0 || s->unzftab[i] > nblock) 1580 RETURN(BZ_DATA_ERROR); 1581 } 1582 /* Actually generate cftab. */ 1583 s->cftab[0] = 0; 1584 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 1585 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 1586 /* Check: cftab entries in range. */ 1587 for (i = 0; i <= 256; i++) { 1588 if (s->cftab[i] < 0 || s->cftab[i] > nblock) { 1589 /* s->cftab[i] can legitimately be == nblock */ 1590 RETURN(BZ_DATA_ERROR); 1591 } 1592 } 1593 /* Check: cftab entries non-descending. */ 1594 for (i = 1; i <= 256; i++) { 1595 if (s->cftab[i-1] > s->cftab[i]) { 1596 RETURN(BZ_DATA_ERROR); 1597 } 1598 } 1599 1600 s->state_out_len = 0; 1601 s->state_out_ch = 0; 1602 BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 1603 s->state = BZ_X_OUTPUT; 1604 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 1605 1606 if (s->smallDecompress) { 1607 1608 /*-- Make a copy of cftab, used in generation of T --*/ 1609 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 1610 1611 /*-- compute the T vector --*/ 1612 for (i = 0; i < nblock; i++) { 1613 uc = (UChar)(s->ll16[i]); 1614 SET_LL(i, s->cftabCopy[uc]); 1615 s->cftabCopy[uc]++; 1616 } 1617 1618 /*-- Compute T^(-1) by pointer reversal on T --*/ 1619 i = s->origPtr; 1620 j = GET_LL(i); 1621 do { 1622 Int32 tmp = GET_LL(j); 1623 SET_LL(j, i); 1624 i = j; 1625 j = tmp; 1626 } 1627 while (i != s->origPtr); 1628 1629 s->tPos = s->origPtr; 1630 s->nblock_used = 0; 1631 if (s->blockRandomised) { 1632 BZ_RAND_INIT_MASK; 1633 BZ_GET_SMALL(s->k0); s->nblock_used++; 1634 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 1635 } else { 1636 BZ_GET_SMALL(s->k0); s->nblock_used++; 1637 } 1638 1639 } else { 1640 1641 /*-- compute the T^(-1) vector --*/ 1642 for (i = 0; i < nblock; i++) { 1643 uc = (UChar)(s->tt[i] & 0xff); 1644 s->tt[s->cftab[uc]] |= (i << 8); 1645 s->cftab[uc]++; 1646 } 1647 1648 s->tPos = s->tt[s->origPtr] >> 8; 1649 s->nblock_used = 0; 1650 if (s->blockRandomised) { 1651 BZ_RAND_INIT_MASK; 1652 BZ_GET_FAST(s->k0); s->nblock_used++; 1653 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 1654 } else { 1655 BZ_GET_FAST(s->k0); s->nblock_used++; 1656 } 1657 1658 } 1659 1660 RETURN(BZ_OK); 1661 1662 1663 1664 endhdr_2: 1665 1666 GET_UCHAR(BZ_X_ENDHDR_2, uc); 1667 if (uc != 0x72) RETURN(BZ_DATA_ERROR); 1668 GET_UCHAR(BZ_X_ENDHDR_3, uc); 1669 if (uc != 0x45) RETURN(BZ_DATA_ERROR); 1670 GET_UCHAR(BZ_X_ENDHDR_4, uc); 1671 if (uc != 0x38) RETURN(BZ_DATA_ERROR); 1672 GET_UCHAR(BZ_X_ENDHDR_5, uc); 1673 if (uc != 0x50) RETURN(BZ_DATA_ERROR); 1674 GET_UCHAR(BZ_X_ENDHDR_6, uc); 1675 if (uc != 0x90) RETURN(BZ_DATA_ERROR); 1676 1677 s->storedCombinedCRC = 0; 1678 GET_UCHAR(BZ_X_CCRC_1, uc); 1679 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 1680 GET_UCHAR(BZ_X_CCRC_2, uc); 1681 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 1682 GET_UCHAR(BZ_X_CCRC_3, uc); 1683 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 1684 GET_UCHAR(BZ_X_CCRC_4, uc); 1685 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 1686 1687 s->state = BZ_X_IDLE; 1688 RETURN(BZ_STREAM_END); 1689 1690 default: AssertH ( False, 4001 ); 1691 } 1692 1693 AssertH ( False, 4002 ); 1694 1695 save_state_and_return: 1696 1697 s->save_i = i; 1698 s->save_j = j; 1699 s->save_t = t; 1700 s->save_alphaSize = alphaSize; 1701 s->save_nGroups = nGroups; 1702 s->save_nSelectors = nSelectors; 1703 s->save_EOB = EOB; 1704 s->save_groupNo = groupNo; 1705 s->save_groupPos = groupPos; 1706 s->save_nextSym = nextSym; 1707 s->save_nblockMAX = nblockMAX; 1708 s->save_nblock = nblock; 1709 s->save_es = es; 1710 s->save_N = N; 1711 s->save_curr = curr; 1712 s->save_zt = zt; 1713 s->save_zn = zn; 1714 s->save_zvec = zvec; 1715 s->save_zj = zj; 1716 s->save_gSel = gSel; 1717 s->save_gMinlen = gMinlen; 1718 s->save_gLimit = gLimit; 1719 s->save_gBase = gBase; 1720 s->save_gPerm = gPerm; 1721 1722 return retVal; 1723 } 1724 1725 1726 /*-------------------------------------------------------------*/ 1727 /*--- end decompress.c ---*/ 1728 /*-------------------------------------------------------------*/ 1729 /* $NetBSD: bzlib.c,v 1.1 2014/03/09 00:15:45 agc Exp $ */ 1730 1731 1732 /*-------------------------------------------------------------*/ 1733 /*--- Table for doing CRCs ---*/ 1734 /*--- crctable.c ---*/ 1735 /*-------------------------------------------------------------*/ 1736 1737 /* ------------------------------------------------------------------ 1738 This file is part of bzip2/libbzip2, a program and library for 1739 lossless, block-sorting data compression. 1740 1741 bzip2/libbzip2 version 1.0.6 of 6 September 2010 1742 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org> 1743 1744 Please read the WARNING, DISCLAIMER and PATENTS sections in the 1745 README file. 1746 1747 This program is released under the terms of the license contained 1748 in the file LICENSE. 1749 ------------------------------------------------------------------ */ 1750 1751 1752 /*-- 1753 I think this is an implementation of the AUTODIN-II, 1754 Ethernet & FDDI 32-bit CRC standard. Vaguely derived 1755 from code by Rob Warnock, in Section 51 of the 1756 comp.compression FAQ. 1757 --*/ 1758 1759 UInt32 BZ2_crc32Table[256] = { 1760 1761 /*-- Ugly, innit? --*/ 1762 1763 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L, 1764 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L, 1765 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L, 1766 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL, 1767 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L, 1768 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L, 1769 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L, 1770 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL, 1771 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L, 1772 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L, 1773 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L, 1774 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL, 1775 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L, 1776 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L, 1777 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L, 1778 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL, 1779 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL, 1780 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L, 1781 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L, 1782 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL, 1783 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL, 1784 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L, 1785 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L, 1786 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL, 1787 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL, 1788 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L, 1789 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L, 1790 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL, 1791 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL, 1792 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L, 1793 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L, 1794 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL, 1795 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L, 1796 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL, 1797 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL, 1798 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L, 1799 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L, 1800 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL, 1801 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL, 1802 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L, 1803 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L, 1804 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL, 1805 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL, 1806 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L, 1807 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L, 1808 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL, 1809 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL, 1810 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L, 1811 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L, 1812 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL, 1813 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L, 1814 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L, 1815 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L, 1816 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL, 1817 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L, 1818 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L, 1819 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L, 1820 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL, 1821 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L, 1822 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L, 1823 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L, 1824 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL, 1825 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L, 1826 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L 1827 }; 1828 1829 1830 /*-------------------------------------------------------------*/ 1831 /*--- end crctable.c ---*/ 1832 /*-------------------------------------------------------------*/ 1833 /* $NetBSD: bzlib.c,v 1.1 2014/03/09 00:15:45 agc Exp $ */ 1834 1835 1836 /*-------------------------------------------------------------*/ 1837 /*--- Huffman coding low-level stuff ---*/ 1838 /*--- huffman.c ---*/ 1839 /*-------------------------------------------------------------*/ 1840 1841 /* ------------------------------------------------------------------ 1842 This file is part of bzip2/libbzip2, a program and library for 1843 lossless, block-sorting data compression. 1844 1845 bzip2/libbzip2 version 1.0.6 of 6 September 2010 1846 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org> 1847 1848 Please read the WARNING, DISCLAIMER and PATENTS sections in the 1849 README file. 1850 1851 This program is released under the terms of the license contained 1852 in the file LICENSE. 1853 ------------------------------------------------------------------ */ 1854 1855 1856 /*---------------------------------------------------*/ 1857 #define WEIGHTOF(zz0) ((zz0) & 0xffffff00) 1858 #define DEPTHOF(zz1) ((zz1) & 0x000000ff) 1859 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3)) 1860 1861 #define ADDWEIGHTS(zw1,zw2) \ 1862 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \ 1863 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2))) 1864 1865 #define UPHEAP(z) \ 1866 { \ 1867 Int32 zz, tmp; \ 1868 zz = z; tmp = heap[zz]; \ 1869 while (weight[tmp] < weight[heap[zz >> 1]]) { \ 1870 heap[zz] = heap[zz >> 1]; \ 1871 zz >>= 1; \ 1872 } \ 1873 heap[zz] = tmp; \ 1874 } 1875 1876 #define DOWNHEAP(z) \ 1877 { \ 1878 Int32 zz, yy, tmp; \ 1879 zz = z; tmp = heap[zz]; \ 1880 while (True) { \ 1881 yy = zz << 1; \ 1882 if (yy > nHeap) break; \ 1883 if (yy < nHeap && \ 1884 weight[heap[yy+1]] < weight[heap[yy]]) \ 1885 yy++; \ 1886 if (weight[tmp] < weight[heap[yy]]) break; \ 1887 heap[zz] = heap[yy]; \ 1888 zz = yy; \ 1889 } \ 1890 heap[zz] = tmp; \ 1891 } 1892 1893 1894 /*---------------------------------------------------*/ 1895 void BZ2_hbMakeCodeLengths ( UChar *len, 1896 Int32 *freq, 1897 Int32 alphaSize, 1898 Int32 maxLen ) 1899 { 1900 /*-- 1901 Nodes and heap entries run from 1. Entry 0 1902 for both the heap and nodes is a sentinel. 1903 --*/ 1904 Int32 nNodes, nHeap, n1, n2, i, j, k; 1905 Bool tooLong; 1906 1907 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ]; 1908 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ]; 1909 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; 1910 1911 for (i = 0; i < alphaSize; i++) 1912 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8; 1913 1914 while (True) { 1915 1916 nNodes = alphaSize; 1917 nHeap = 0; 1918 1919 heap[0] = 0; 1920 weight[0] = 0; 1921 parent[0] = -2; 1922 1923 for (i = 1; i <= alphaSize; i++) { 1924 parent[i] = -1; 1925 nHeap++; 1926 heap[nHeap] = i; 1927 UPHEAP(nHeap); 1928 } 1929 1930 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 ); 1931 1932 while (nHeap > 1) { 1933 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 1934 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 1935 nNodes++; 1936 parent[n1] = parent[n2] = nNodes; 1937 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]); 1938 parent[nNodes] = -1; 1939 nHeap++; 1940 heap[nHeap] = nNodes; 1941 UPHEAP(nHeap); 1942 } 1943 1944 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 ); 1945 1946 tooLong = False; 1947 for (i = 1; i <= alphaSize; i++) { 1948 j = 0; 1949 k = i; 1950 while (parent[k] >= 0) { k = parent[k]; j++; } 1951 len[i-1] = j; 1952 if (j > maxLen) tooLong = True; 1953 } 1954 1955 if (! tooLong) break; 1956 1957 /* 17 Oct 04: keep-going condition for the following loop used 1958 to be 'i < alphaSize', which missed the last element, 1959 theoretically leading to the possibility of the compressor 1960 looping. However, this count-scaling step is only needed if 1961 one of the generated Huffman code words is longer than 1962 maxLen, which up to and including version 1.0.2 was 20 bits, 1963 which is extremely unlikely. In version 1.0.3 maxLen was 1964 changed to 17 bits, which has minimal effect on compression 1965 ratio, but does mean this scaling step is used from time to 1966 time, enough to verify that it works. 1967 1968 This means that bzip2-1.0.3 and later will only produce 1969 Huffman codes with a maximum length of 17 bits. However, in 1970 order to preserve backwards compatibility with bitstreams 1971 produced by versions pre-1.0.3, the decompressor must still 1972 handle lengths of up to 20. */ 1973 1974 for (i = 1; i <= alphaSize; i++) { 1975 j = weight[i] >> 8; 1976 j = 1 + (j / 2); 1977 weight[i] = j << 8; 1978 } 1979 } 1980 } 1981 1982 1983 /*---------------------------------------------------*/ 1984 void BZ2_hbAssignCodes ( Int32 *code, 1985 UChar *length, 1986 Int32 minLen, 1987 Int32 maxLen, 1988 Int32 alphaSize ) 1989 { 1990 Int32 n, vec, i; 1991 1992 vec = 0; 1993 for (n = minLen; n <= maxLen; n++) { 1994 for (i = 0; i < alphaSize; i++) 1995 if (length[i] == n) { code[i] = vec; vec++; }; 1996 vec <<= 1; 1997 } 1998 } 1999 2000 2001 /*---------------------------------------------------*/ 2002 void BZ2_hbCreateDecodeTables ( Int32 *limit, 2003 Int32 *base, 2004 Int32 *perm, 2005 UChar *length, 2006 Int32 minLen, 2007 Int32 maxLen, 2008 Int32 alphaSize ) 2009 { 2010 Int32 pp, i, j, vec; 2011 2012 pp = 0; 2013 for (i = minLen; i <= maxLen; i++) 2014 for (j = 0; j < alphaSize; j++) 2015 if (length[j] == i) { perm[pp] = j; pp++; }; 2016 2017 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0; 2018 for (i = 0; i < alphaSize; i++) base[length[i]+1]++; 2019 2020 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1]; 2021 2022 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0; 2023 vec = 0; 2024 2025 for (i = minLen; i <= maxLen; i++) { 2026 vec += (base[i+1] - base[i]); 2027 limit[i] = vec-1; 2028 vec <<= 1; 2029 } 2030 for (i = minLen + 1; i <= maxLen; i++) 2031 base[i] = ((limit[i-1] + 1) << 1) - base[i]; 2032 } 2033 2034 2035 /*-------------------------------------------------------------*/ 2036 /*--- end huffman.c ---*/ 2037 /*-------------------------------------------------------------*/ 2038