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