1 2char hexdigits[17] = "0123456789abcdef"; 3 4int itox( unsigned int n, char s[]) 5{ 6 int i = 10; 7 s[i--]='\0'; 8 do s[i--] = hexdigits[ n % 16 ]; 9 while ( ( ( n /= 16 ) > 0 ) && ( i > 1 ) ); 10 for ( ; i>1; s[i--] = '0' ); 11 s[i--]='x'; 12 s[i--]='0'; 13 return 0; 14} 15 16int putix( unsigned int n) 17{ 18 char swork[17]; 19 itox( n, swork ); 20 puts( swork ); 21 return 0; 22} 23 24int putpx( void * n) 25{ 26 char swork[17]; 27 itox( (unsigned int)n, swork ); 28 puts( swork ); 29 return 0; 30} 31 32void bz_internal_error ( int i ) 33{ 34 puts("\n"); 35 putix(i); 36 puts("\n"); 37 error("Bzip2 internal error."); 38} 39 40/*-------------------------------------------------------------*/ 41/* 42 43 bzip2 stuff for linux kernel and ramdisk decompression. 44 45 This file was derived by Thomas Oehser, Tom@Toms.NET, 46 from bzlib.c from bzip2-1.0.2, to fit more with less. 47 48 The initial implementation is only tested to work with 49 kernel version 2.2.20 and only with bzImage (bz2bzImage). 50 51 Mostly I just chopped out compression stuff (leaving 52 only decompression) and the 'high-level' stuff, (that 53 expects stdio and libc), and chopped out any other bits 54 that required stuff that isn't around during kernel boot. 55 56 I crammed everything it needed together into this one 57 file, also. And not always in a logical order. 58 59*/ 60 61/*-------------------------------------------------------------*/ 62 63/*-- 64 This file is a part of bzip2 and/or libbzip2, a program and 65 library for lossless, block-sorting data compression. 66 67 Copyright (C) 1996-2002 Julian R Seward. All rights reserved. 68 69 Redistribution and use in source and binary forms, with or without 70 modification, are permitted provided that the following conditions 71 are met: 72 73 1. Redistributions of source code must retain the above copyright 74 notice, this list of conditions and the following disclaimer. 75 76 2. The origin of this software must not be misrepresented; you must 77 not claim that you wrote the original software. If you use this 78 software in a product, an acknowledgment in the product 79 documentation would be appreciated but is not required. 80 81 3. Altered source versions must be plainly marked as such, and must 82 not be misrepresented as being the original software. 83 84 4. The name of the author may not be used to endorse or promote 85 products derived from this software without specific prior written 86 permission. 87 88 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 89 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 90 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 91 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 92 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 93 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 94 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 95 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 96 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 97 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 98 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 99 100 Julian Seward, Cambridge, UK. 101 jseward@acm.org 102 bzip2/libbzip2 version 1.0 of 21 March 2000 103 104 This program is based on (at least) the work of: 105 Mike Burrows 106 David Wheeler 107 Peter Fenwick 108 Alistair Moffat 109 Radford Neal 110 Ian H. Witten 111 Robert Sedgewick 112 Jon L. Bentley 113 114 For more information on these sources, see the manual. 115--*/ 116 117/*-- General stuff. --*/ 118 119#define BZ_VERSION "1.0.2, 30-Dec-2001" 120 121typedef char Char; 122typedef unsigned char Bool; 123typedef unsigned char UChar; 124typedef int Int32; 125typedef unsigned int UInt32; 126typedef short Int16; 127typedef unsigned short UInt16; 128 129#define True ((Bool)1) 130#define False ((Bool)0) 131 132#ifndef __GNUC__ 133#define __inline__ /* */ 134#endif 135 136extern void bz_internal_error ( int errcode ); 137 138#define AssertH(cond,errcode) \ 139 { if (!(cond)) bz_internal_error ( errcode ); } 140#define AssertD(cond,msg) /* */ 141#define VPrintf0(zf) /* */ 142#define VPrintf1(zf,za1) /* */ 143#define VPrintf2(zf,za1,za2) /* */ 144#define VPrintf3(zf,za1,za2,za3) /* */ 145#define VPrintf4(zf,za1,za2,za3,za4) /* */ 146#define VPrintf5(zf,za1,za2,za3,za4,za5) /* */ 147 148#define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1) 149#define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp)) 150 151/*-- Header bytes. --*/ 152 153#define BZ_HDR_B 0x42 /* 'B' */ 154#define BZ_HDR_Z 0x5a /* 'Z' */ 155#define BZ_HDR_h 0x68 /* 'h' */ 156#define BZ_HDR_0 0x30 /* '0' */ 157 158/*-- Constants for the back end. --*/ 159 160#define BZ_MAX_ALPHA_SIZE 258 161#define BZ_MAX_CODE_LEN 23 162 163#define BZ_RUNA 0 164#define BZ_RUNB 1 165 166#define BZ_N_GROUPS 6 167#define BZ_G_SIZE 50 168#define BZ_N_ITERS 4 169 170#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) 171 172 173 174/*-- Stuff for randomising repetitive blocks. --*/ 175 176// extern Int32 BZ2_rNums[512]; 177 178#define BZ_RAND_DECLS \ 179 Int32 rNToGo; \ 180 Int32 rTPos \ 181 182#define BZ_RAND_INIT_MASK \ 183 s->rNToGo = 0; \ 184 s->rTPos = 0 \ 185 186#define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0) 187 188#define BZ_RAND_UPD_MASK \ 189 if (s->rNToGo == 0) { \ 190 s->rNToGo = BZ2_rNums[s->rTPos]; \ 191 s->rTPos++; \ 192 if (s->rTPos == 512) s->rTPos = 0; \ 193 } \ 194 s->rNToGo--; 195 196/*-- Stuff for doing CRCs. --*/ 197 198// extern UInt32 BZ2_crc32Table[256]; 199 200#define BZ_INITIALISE_CRC(crcVar) \ 201{ \ 202 crcVar = 0xffffffffL; \ 203} 204 205#define BZ_FINALISE_CRC(crcVar) \ 206{ \ 207 crcVar = ~(crcVar); \ 208} 209 210#define BZ_UPDATE_CRC(crcVar,cha) \ 211{ \ 212 crcVar = (crcVar << 8) ^ \ 213 BZ2_crc32Table[(crcVar >> 24) ^ \ 214 ((UChar)cha)]; \ 215} 216 217/*-- states for decompression. --*/ 218 219#define BZ_X_IDLE 1 220#define BZ_X_OUTPUT 2 221 222#define BZ_X_MAGIC_1 10 223#define BZ_X_MAGIC_2 11 224#define BZ_X_MAGIC_3 12 225#define BZ_X_MAGIC_4 13 226#define BZ_X_BLKHDR_1 14 227#define BZ_X_BLKHDR_2 15 228#define BZ_X_BLKHDR_3 16 229#define BZ_X_BLKHDR_4 17 230#define BZ_X_BLKHDR_5 18 231#define BZ_X_BLKHDR_6 19 232#define BZ_X_BCRC_1 20 233#define BZ_X_BCRC_2 21 234#define BZ_X_BCRC_3 22 235#define BZ_X_BCRC_4 23 236#define BZ_X_RANDBIT 24 237#define BZ_X_ORIGPTR_1 25 238#define BZ_X_ORIGPTR_2 26 239#define BZ_X_ORIGPTR_3 27 240#define BZ_X_MAPPING_1 28 241#define BZ_X_MAPPING_2 29 242#define BZ_X_SELECTOR_1 30 243#define BZ_X_SELECTOR_2 31 244#define BZ_X_SELECTOR_3 32 245#define BZ_X_CODING_1 33 246#define BZ_X_CODING_2 34 247#define BZ_X_CODING_3 35 248#define BZ_X_MTF_1 36 249#define BZ_X_MTF_2 37 250#define BZ_X_MTF_3 38 251#define BZ_X_MTF_4 39 252#define BZ_X_MTF_5 40 253#define BZ_X_MTF_6 41 254#define BZ_X_ENDHDR_2 42 255#define BZ_X_ENDHDR_3 43 256#define BZ_X_ENDHDR_4 44 257#define BZ_X_ENDHDR_5 45 258#define BZ_X_ENDHDR_6 46 259#define BZ_X_CCRC_1 47 260#define BZ_X_CCRC_2 48 261#define BZ_X_CCRC_3 49 262#define BZ_X_CCRC_4 50 263 264/*-- Constants for the fast MTF decoder. --*/ 265 266#define MTFA_SIZE 4096 267#define MTFL_SIZE 16 268 269 270#define BZ_RUN 0 271#define BZ_FLUSH 1 272#define BZ_FINISH 2 273 274#define BZ_OK 0 275#define BZ_RUN_OK 1 276#define BZ_FLUSH_OK 2 277#define BZ_FINISH_OK 3 278#define BZ_STREAM_END 4 279#define BZ_SEQUENCE_ERROR (-1) 280#define BZ_PARAM_ERROR (-2) 281#define BZ_MEM_ERROR (-3) 282#define BZ_DATA_ERROR (-4) 283#define BZ_DATA_ERROR_MAGIC (-5) 284#define BZ_IO_ERROR (-6) 285#define BZ_UNEXPECTED_EOF (-7) 286#define BZ_OUTBUFF_FULL (-8) 287#define BZ_CONFIG_ERROR (-9) 288 289typedef 290 struct { 291 char *next_in; 292 unsigned int avail_in; 293 unsigned int total_in_lo32; 294 unsigned int total_in_hi32; 295 296 char *next_out; 297 unsigned int avail_out; 298 unsigned int total_out_lo32; 299 unsigned int total_out_hi32; 300 301 void *state; 302 303 void *(*bzalloc)(void *,int,int); 304 void (*bzfree)(void *,void *); 305 void *opaque; 306 } 307 bz_stream; 308 309#ifndef BZ_IMPORT 310#define BZ_EXPORT 311#endif 312 313# define BZ_API(func) func 314# define BZ_EXTERN extern 315 316/*-- Structure holding all the decompression-side stuff. --*/ 317 318typedef 319 struct { 320 /* pointer back to the struct bz_stream */ 321 bz_stream* strm; 322 323 /* state indicator for this stream */ 324 Int32 state; 325 326 /* for doing the final run-length decoding */ 327 UChar state_out_ch; 328 Int32 state_out_len; 329 Bool blockRandomised; 330 BZ_RAND_DECLS; 331 332 /* the buffer for bit stream reading */ 333 UInt32 bsBuff; 334 Int32 bsLive; 335 336 /* misc administratium */ 337 Int32 blockSize100k; 338 Bool smallDecompress; 339 Int32 currBlockNo; 340 Int32 verbosity; 341 342 /* for undoing the Burrows-Wheeler transform */ 343 Int32 origPtr; 344 UInt32 tPos; 345 Int32 k0; 346 Int32 unzftab[256]; 347 Int32 nblock_used; 348 Int32 cftab[257]; 349 Int32 cftabCopy[257]; 350 351 /* for undoing the Burrows-Wheeler transform (FAST) */ 352 UInt32 *tt; 353 354 /* for undoing the Burrows-Wheeler transform (SMALL) */ 355 UInt16 *ll16; 356 UChar *ll4; 357 358 /* stored and calculated CRCs */ 359 UInt32 storedBlockCRC; 360 UInt32 storedCombinedCRC; 361 UInt32 calculatedBlockCRC; 362 UInt32 calculatedCombinedCRC; 363 364 /* map of bytes used in block */ 365 Int32 nInUse; 366 Bool inUse[256]; 367 Bool inUse16[16]; 368 UChar seqToUnseq[256]; 369 370 /* for decoding the MTF values */ 371 UChar mtfa [MTFA_SIZE]; 372 Int32 mtfbase[256 / MTFL_SIZE]; 373 UChar selector [BZ_MAX_SELECTORS]; 374 UChar selectorMtf[BZ_MAX_SELECTORS]; 375 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 376 377 Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 378 Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 379 Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 380 Int32 minLens[BZ_N_GROUPS]; 381 382 /* save area for scalars in the main decompress code */ 383 Int32 save_i; 384 Int32 save_j; 385 Int32 save_t; 386 Int32 save_alphaSize; 387 Int32 save_nGroups; 388 Int32 save_nSelectors; 389 Int32 save_EOB; 390 Int32 save_groupNo; 391 Int32 save_groupPos; 392 Int32 save_nextSym; 393 Int32 save_nblockMAX; 394 Int32 save_nblock; 395 Int32 save_es; 396 Int32 save_N; 397 Int32 save_curr; 398 Int32 save_zt; 399 Int32 save_zn; 400 Int32 save_zvec; 401 Int32 save_zj; 402 Int32 save_gSel; 403 Int32 save_gMinlen; 404 Int32* save_gLimit; 405 Int32* save_gBase; 406 Int32* save_gPerm; 407 408 } 409 DState; 410 411/*-- Macros for decompression. --*/ 412 413#define BZ_GET_FAST(cccc) \ 414 s->tPos = s->tt[s->tPos]; \ 415 cccc = (UChar)(s->tPos & 0xff); \ 416 s->tPos >>= 8; 417 418#define BZ_GET_FAST_C(cccc) \ 419 c_tPos = c_tt[c_tPos]; \ 420 cccc = (UChar)(c_tPos & 0xff); \ 421 c_tPos >>= 8; 422 423#define SET_LL4(i,n) \ 424 { if (((i) & 0x1) == 0) \ 425 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \ 426 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ 427 } 428 429#define GET_LL4(i) \ 430 ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF) 431 432#define SET_LL(i,n) \ 433 { s->ll16[i] = (UInt16)(n & 0x0000ffff); \ 434 SET_LL4(i, n >> 16); \ 435 } 436 437#define GET_LL(i) \ 438 (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16)) 439 440#define BZ_GET_SMALL(cccc) \ 441 cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \ 442 s->tPos = GET_LL(s->tPos); 443 444/*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/ 445 446#ifndef NULL 447#define NULL 0 448#endif 449 450/*-------------------------------------------------------------*/ 451/*--- Table for doing CRCs ---*/ 452/*--- crctable.c ---*/ 453/*-------------------------------------------------------------*/ 454 455/*-- 456 I think this is an implementation of the AUTODIN-II, 457 Ethernet & FDDI 32-bit CRC standard. Vaguely derived 458 from code by Rob Warnock, in Section 51 of the 459 comp.compression FAQ. 460--*/ 461 462UInt32 BZ2_crc32Table[256] = { 463 464 /*-- Ugly, innit? --*/ 465 466 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L, 467 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L, 468 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L, 469 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL, 470 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L, 471 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L, 472 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L, 473 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL, 474 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L, 475 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L, 476 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L, 477 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL, 478 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L, 479 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L, 480 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L, 481 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL, 482 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL, 483 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L, 484 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L, 485 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL, 486 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL, 487 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L, 488 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L, 489 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL, 490 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL, 491 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L, 492 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L, 493 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL, 494 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL, 495 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L, 496 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L, 497 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL, 498 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L, 499 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL, 500 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL, 501 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L, 502 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L, 503 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL, 504 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL, 505 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L, 506 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L, 507 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL, 508 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL, 509 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L, 510 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L, 511 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL, 512 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL, 513 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L, 514 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L, 515 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL, 516 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L, 517 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L, 518 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L, 519 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL, 520 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L, 521 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L, 522 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L, 523 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL, 524 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L, 525 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L, 526 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L, 527 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL, 528 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L, 529 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L 530}; 531 532/*-------------------------------------------------------------*/ 533/*--- Table for randomising repetitive blocks ---*/ 534/*--- randtable.c ---*/ 535/*-------------------------------------------------------------*/ 536 537Int32 BZ2_rNums[512] = { 538 619, 720, 127, 481, 931, 816, 813, 233, 566, 247, 539 985, 724, 205, 454, 863, 491, 741, 242, 949, 214, 540 733, 859, 335, 708, 621, 574, 73, 654, 730, 472, 541 419, 436, 278, 496, 867, 210, 399, 680, 480, 51, 542 878, 465, 811, 169, 869, 675, 611, 697, 867, 561, 543 862, 687, 507, 283, 482, 129, 807, 591, 733, 623, 544 150, 238, 59, 379, 684, 877, 625, 169, 643, 105, 545 170, 607, 520, 932, 727, 476, 693, 425, 174, 647, 546 73, 122, 335, 530, 442, 853, 695, 249, 445, 515, 547 909, 545, 703, 919, 874, 474, 882, 500, 594, 612, 548 641, 801, 220, 162, 819, 984, 589, 513, 495, 799, 549 161, 604, 958, 533, 221, 400, 386, 867, 600, 782, 550 382, 596, 414, 171, 516, 375, 682, 485, 911, 276, 551 98, 553, 163, 354, 666, 933, 424, 341, 533, 870, 552 227, 730, 475, 186, 263, 647, 537, 686, 600, 224, 553 469, 68, 770, 919, 190, 373, 294, 822, 808, 206, 554 184, 943, 795, 384, 383, 461, 404, 758, 839, 887, 555 715, 67, 618, 276, 204, 918, 873, 777, 604, 560, 556 951, 160, 578, 722, 79, 804, 96, 409, 713, 940, 557 652, 934, 970, 447, 318, 353, 859, 672, 112, 785, 558 645, 863, 803, 350, 139, 93, 354, 99, 820, 908, 559 609, 772, 154, 274, 580, 184, 79, 626, 630, 742, 560 653, 282, 762, 623, 680, 81, 927, 626, 789, 125, 561 411, 521, 938, 300, 821, 78, 343, 175, 128, 250, 562 170, 774, 972, 275, 999, 639, 495, 78, 352, 126, 563 857, 956, 358, 619, 580, 124, 737, 594, 701, 612, 564 669, 112, 134, 694, 363, 992, 809, 743, 168, 974, 565 944, 375, 748, 52, 600, 747, 642, 182, 862, 81, 566 344, 805, 988, 739, 511, 655, 814, 334, 249, 515, 567 897, 955, 664, 981, 649, 113, 974, 459, 893, 228, 568 433, 837, 553, 268, 926, 240, 102, 654, 459, 51, 569 686, 754, 806, 760, 493, 403, 415, 394, 687, 700, 570 946, 670, 656, 610, 738, 392, 760, 799, 887, 653, 571 978, 321, 576, 617, 626, 502, 894, 679, 243, 440, 572 680, 879, 194, 572, 640, 724, 926, 56, 204, 700, 573 707, 151, 457, 449, 797, 195, 791, 558, 945, 679, 574 297, 59, 87, 824, 713, 663, 412, 693, 342, 606, 575 134, 108, 571, 364, 631, 212, 174, 643, 304, 329, 576 343, 97, 430, 751, 497, 314, 983, 374, 822, 928, 577 140, 206, 73, 263, 980, 736, 876, 478, 430, 305, 578 170, 514, 364, 692, 829, 82, 855, 953, 676, 246, 579 369, 970, 294, 750, 807, 827, 150, 790, 288, 923, 580 804, 378, 215, 828, 592, 281, 565, 555, 710, 82, 581 896, 831, 547, 261, 524, 462, 293, 465, 502, 56, 582 661, 821, 976, 991, 658, 869, 905, 758, 745, 193, 583 768, 550, 608, 933, 378, 286, 215, 979, 792, 961, 584 61, 688, 793, 644, 986, 403, 106, 366, 905, 644, 585 372, 567, 466, 434, 645, 210, 389, 550, 919, 135, 586 780, 773, 635, 389, 707, 100, 626, 958, 165, 504, 587 920, 176, 193, 713, 857, 265, 203, 50, 668, 108, 588 645, 990, 626, 197, 510, 357, 358, 850, 858, 364, 589 936, 638 590}; 591 592 593/*-- Core (low-level) library functions --*/ 594 595BZ_EXTERN int BZ_API(BZ2_bzCompressInit) ( 596 bz_stream* strm, 597 int blockSize100k, 598 int verbosity, 599 int workFactor 600 ); 601 602BZ_EXTERN int BZ_API(BZ2_bzCompress) ( 603 bz_stream* strm, 604 int action 605 ); 606 607BZ_EXTERN int BZ_API(BZ2_bzCompressEnd) ( 608 bz_stream* strm 609 ); 610 611BZ_EXTERN int BZ_API(BZ2_bzDecompressInit) ( 612 bz_stream *strm, 613 int verbosity, 614 int small 615 ); 616 617BZ_EXTERN int BZ_API(BZ2_bzDecompress) ( 618 bz_stream* strm 619 ); 620 621BZ_EXTERN int BZ_API(BZ2_bzDecompressEnd) ( 622 bz_stream *strm 623 ); 624 625/*-- Utility functions --*/ 626 627BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffCompress) ( 628 char* dest, 629 unsigned int* destLen, 630 char* source, 631 unsigned int sourceLen, 632 int blockSize100k, 633 int verbosity, 634 int workFactor 635 ); 636 637BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffDecompress) ( 638 char* dest, 639 unsigned int* destLen, 640 char* source, 641 unsigned int sourceLen, 642 int small, 643 int verbosity 644 ); 645 646 647/*-- 648 Code contributed by Yoshioka Tsuneo 649 (QWF00133@niftyserve.or.jp/tsuneo-y@is.aist-nara.ac.jp), 650 to support better zlib compatibility. 651 This code is not _officially_ part of libbzip2 (yet); 652 I haven't tested it, documented it, or considered the 653 threading-safeness of it. 654 If this code breaks, please contact both Yoshioka and me. 655--*/ 656 657BZ_EXTERN const char * BZ_API(BZ2_bzlibVersion) ( 658 void 659 ); 660 661 662 663/*---------------------------------------------------*/ 664 665static 666int bz_config_ok ( void ) 667{ 668 if (sizeof(int) != 4) return 0; 669 if (sizeof(short) != 2) return 0; 670 if (sizeof(char) != 1) return 0; 671 return 1; 672} 673 674/*---------------------------------------------------*/ 675static 676void* default_bzalloc ( void* opaque, Int32 items, Int32 size ) 677{ 678 void* v = malloc ( items * size ); 679 return v; 680} 681 682static 683void default_bzfree ( void* opaque, void* addr ) 684{ 685 if (addr != NULL) free ( addr ); 686} 687 688/*---------------------------------------------------*/ 689int BZ_API(BZ2_bzDecompressInit) 690 ( bz_stream* strm, 691 int verbosity, 692 int small ) 693{ 694 DState* s; 695 696 if (!bz_config_ok()) return BZ_CONFIG_ERROR; 697 698 if (strm == NULL) return BZ_PARAM_ERROR; 699 if (small != 0 && small != 1) return BZ_PARAM_ERROR; 700 if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR; 701 702 if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc; 703 if (strm->bzfree == NULL) strm->bzfree = default_bzfree; 704 705 s = BZALLOC( sizeof(DState) ); 706 if (s == NULL) return BZ_MEM_ERROR; 707 s->strm = strm; 708 strm->state = s; 709 s->state = BZ_X_MAGIC_1; 710 s->bsLive = 0; 711 s->bsBuff = 0; 712 s->calculatedCombinedCRC = 0; 713 strm->total_in_lo32 = 0; 714 strm->total_in_hi32 = 0; 715 strm->total_out_lo32 = 0; 716 strm->total_out_hi32 = 0; 717 s->smallDecompress = (Bool)small; 718 s->ll4 = NULL; 719 s->ll16 = NULL; 720 s->tt = NULL; 721 s->currBlockNo = 0; 722 s->verbosity = verbosity; 723 724 return BZ_OK; 725} 726 727 728/*---------------------------------------------------*/ 729static 730void unRLE_obuf_to_output_FAST ( DState* s ) 731{ 732 UChar k1; 733 734 if (s->blockRandomised) { 735 736 while (True) { 737 /* try to finish existing run */ 738 while (True) { 739 if (s->strm->avail_out == 0) return; 740 if (s->state_out_len == 0) break; 741 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; 742 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); 743 s->state_out_len--; 744 s->strm->next_out++; 745 s->strm->avail_out--; 746 s->strm->total_out_lo32++; 747 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; 748 } 749 750 /* can a new run be started? */ 751 if (s->nblock_used == s->save_nblock+1) return; 752 753 754 s->state_out_len = 1; 755 s->state_out_ch = s->k0; 756 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 757 k1 ^= BZ_RAND_MASK; s->nblock_used++; 758 if (s->nblock_used == s->save_nblock+1) continue; 759 if (k1 != s->k0) { s->k0 = k1; continue; }; 760 761 s->state_out_len = 2; 762 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 763 k1 ^= BZ_RAND_MASK; s->nblock_used++; 764 if (s->nblock_used == s->save_nblock+1) continue; 765 if (k1 != s->k0) { s->k0 = k1; continue; }; 766 767 s->state_out_len = 3; 768 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 769 k1 ^= BZ_RAND_MASK; s->nblock_used++; 770 if (s->nblock_used == s->save_nblock+1) continue; 771 if (k1 != s->k0) { s->k0 = k1; continue; }; 772 773 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 774 k1 ^= BZ_RAND_MASK; s->nblock_used++; 775 s->state_out_len = ((Int32)k1) + 4; 776 BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK; 777 s->k0 ^= BZ_RAND_MASK; s->nblock_used++; 778 } 779 780 } else { 781 782 /* restore */ 783 UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC; 784 UChar c_state_out_ch = s->state_out_ch; 785 Int32 c_state_out_len = s->state_out_len; 786 Int32 c_nblock_used = s->nblock_used; 787 Int32 c_k0 = s->k0; 788 UInt32* c_tt = s->tt; 789 UInt32 c_tPos = s->tPos; 790 char* cs_next_out = s->strm->next_out; 791 unsigned int cs_avail_out = s->strm->avail_out; 792 /* end restore */ 793 794 UInt32 avail_out_INIT = cs_avail_out; 795 Int32 s_save_nblockPP = s->save_nblock+1; 796 unsigned int total_out_lo32_old; 797 798 while (True) { 799 800 /* try to finish existing run */ 801 if (c_state_out_len > 0) { 802 while (True) { 803 if (cs_avail_out == 0) goto return_notr; 804 if (c_state_out_len == 1) break; 805 *( (UChar*)(cs_next_out) ) = c_state_out_ch; 806 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch ); 807 c_state_out_len--; 808 cs_next_out++; 809 cs_avail_out--; 810 } 811 s_state_out_len_eq_one: 812 { 813 if (cs_avail_out == 0) { 814 c_state_out_len = 1; goto return_notr; 815 }; 816 *( (UChar*)(cs_next_out) ) = c_state_out_ch; 817 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch ); 818 cs_next_out++; 819 cs_avail_out--; 820 } 821 } 822 /* can a new run be started? */ 823 if (c_nblock_used == s_save_nblockPP) { 824 c_state_out_len = 0; goto return_notr; 825 }; 826 c_state_out_ch = c_k0; 827 BZ_GET_FAST_C(k1); c_nblock_used++; 828 if (k1 != c_k0) { 829 c_k0 = k1; goto s_state_out_len_eq_one; 830 }; 831 if (c_nblock_used == s_save_nblockPP) 832 goto s_state_out_len_eq_one; 833 834 c_state_out_len = 2; 835 BZ_GET_FAST_C(k1); c_nblock_used++; 836 if (c_nblock_used == s_save_nblockPP) continue; 837 if (k1 != c_k0) { c_k0 = k1; continue; }; 838 839 c_state_out_len = 3; 840 BZ_GET_FAST_C(k1); c_nblock_used++; 841 if (c_nblock_used == s_save_nblockPP) continue; 842 if (k1 != c_k0) { c_k0 = k1; continue; }; 843 844 BZ_GET_FAST_C(k1); c_nblock_used++; 845 c_state_out_len = ((Int32)k1) + 4; 846 BZ_GET_FAST_C(c_k0); c_nblock_used++; 847 } 848 849 return_notr: 850 total_out_lo32_old = s->strm->total_out_lo32; 851 s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out); 852 if (s->strm->total_out_lo32 < total_out_lo32_old) 853 s->strm->total_out_hi32++; 854 855 /* save */ 856 s->calculatedBlockCRC = c_calculatedBlockCRC; 857 s->state_out_ch = c_state_out_ch; 858 s->state_out_len = c_state_out_len; 859 s->nblock_used = c_nblock_used; 860 s->k0 = c_k0; 861 s->tt = c_tt; 862 s->tPos = c_tPos; 863 s->strm->next_out = cs_next_out; 864 s->strm->avail_out = cs_avail_out; 865 /* end save */ 866 } 867} 868 869/*---------------------------------------------------*/ 870__inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab ) 871{ 872 Int32 nb, na, mid; 873 nb = 0; 874 na = 256; 875 do { 876 mid = (nb + na) >> 1; 877 if (indx >= cftab[mid]) nb = mid; else na = mid; 878 } 879 while (na - nb != 1); 880 return nb; 881} 882 883/*---------------------------------------------------*/ 884static 885void unRLE_obuf_to_output_SMALL ( DState* s ) 886{ 887 UChar k1; 888 889 if (s->blockRandomised) { 890 891 while (True) { 892 /* try to finish existing run */ 893 while (True) { 894 if (s->strm->avail_out == 0) return; 895 if (s->state_out_len == 0) break; 896 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; 897 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); 898 s->state_out_len--; 899 s->strm->next_out++; 900 s->strm->avail_out--; 901 s->strm->total_out_lo32++; 902 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; 903 } 904 905 /* can a new run be started? */ 906 if (s->nblock_used == s->save_nblock+1) return; 907 908 909 s->state_out_len = 1; 910 s->state_out_ch = s->k0; 911 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 912 k1 ^= BZ_RAND_MASK; s->nblock_used++; 913 if (s->nblock_used == s->save_nblock+1) continue; 914 if (k1 != s->k0) { s->k0 = k1; continue; }; 915 916 s->state_out_len = 2; 917 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 918 k1 ^= BZ_RAND_MASK; s->nblock_used++; 919 if (s->nblock_used == s->save_nblock+1) continue; 920 if (k1 != s->k0) { s->k0 = k1; continue; }; 921 922 s->state_out_len = 3; 923 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 924 k1 ^= BZ_RAND_MASK; s->nblock_used++; 925 if (s->nblock_used == s->save_nblock+1) continue; 926 if (k1 != s->k0) { s->k0 = k1; continue; }; 927 928 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 929 k1 ^= BZ_RAND_MASK; s->nblock_used++; 930 s->state_out_len = ((Int32)k1) + 4; 931 BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK; 932 s->k0 ^= BZ_RAND_MASK; s->nblock_used++; 933 } 934 935 } else { 936 937 while (True) { 938 /* try to finish existing run */ 939 while (True) { 940 if (s->strm->avail_out == 0) return; 941 if (s->state_out_len == 0) break; 942 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; 943 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); 944 s->state_out_len--; 945 s->strm->next_out++; 946 s->strm->avail_out--; 947 s->strm->total_out_lo32++; 948 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; 949 } 950 951 /* can a new run be started? */ 952 if (s->nblock_used == s->save_nblock+1) return; 953 954 s->state_out_len = 1; 955 s->state_out_ch = s->k0; 956 BZ_GET_SMALL(k1); s->nblock_used++; 957 if (s->nblock_used == s->save_nblock+1) continue; 958 if (k1 != s->k0) { s->k0 = k1; continue; }; 959 960 s->state_out_len = 2; 961 BZ_GET_SMALL(k1); s->nblock_used++; 962 if (s->nblock_used == s->save_nblock+1) continue; 963 if (k1 != s->k0) { s->k0 = k1; continue; }; 964 965 s->state_out_len = 3; 966 BZ_GET_SMALL(k1); s->nblock_used++; 967 if (s->nblock_used == s->save_nblock+1) continue; 968 if (k1 != s->k0) { s->k0 = k1; continue; }; 969 970 BZ_GET_SMALL(k1); s->nblock_used++; 971 s->state_out_len = ((Int32)k1) + 4; 972 BZ_GET_SMALL(s->k0); s->nblock_used++; 973 } 974 975 } 976} 977 978Int32 BZ2_decompress ( DState* s ); 979 980/*---------------------------------------------------*/ 981int BZ_API(BZ2_bzDecompress) ( bz_stream *strm ) 982{ 983 DState* s; 984 if (strm == NULL) return BZ_PARAM_ERROR; 985 s = strm->state; 986 if (s == NULL) return BZ_PARAM_ERROR; 987 if (s->strm != strm) return BZ_PARAM_ERROR; 988 989 while (True) { 990 if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR; 991 if (s->state == BZ_X_OUTPUT) { 992 if (s->smallDecompress) 993 unRLE_obuf_to_output_SMALL ( s ); else 994 unRLE_obuf_to_output_FAST ( s ); 995 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) { 996 BZ_FINALISE_CRC ( s->calculatedBlockCRC ); 997 if (s->verbosity >= 3) 998 VPrintf2 ( " {0x%x, 0x%x}", s->storedBlockCRC, 999 s->calculatedBlockCRC ); 1000 if (s->verbosity >= 2) VPrintf0 ( "]" ); 1001 if (s->calculatedBlockCRC != s->storedBlockCRC) 1002 return BZ_DATA_ERROR; 1003 s->calculatedCombinedCRC 1004 = (s->calculatedCombinedCRC << 1) | 1005 (s->calculatedCombinedCRC >> 31); 1006 s->calculatedCombinedCRC ^= s->calculatedBlockCRC; 1007 s->state = BZ_X_BLKHDR_1; 1008 } else { 1009 return BZ_OK; 1010 } 1011 } 1012 if (s->state >= BZ_X_MAGIC_1) { 1013 Int32 r = BZ2_decompress ( s ); 1014 if (r == BZ_STREAM_END) { 1015 if (s->verbosity >= 3) 1016 VPrintf2 ( "\n combined CRCs: stored = 0x%x, computed = 0x%x", 1017 s->storedCombinedCRC, s->calculatedCombinedCRC ); 1018 if (s->calculatedCombinedCRC != s->storedCombinedCRC) 1019 return BZ_DATA_ERROR; 1020 return r; 1021 } 1022 if (s->state != BZ_X_OUTPUT) return r; 1023 } 1024 } 1025 1026 AssertH ( 0, 6001 ); 1027 1028 return 0; /*NOTREACHED*/ 1029} 1030 1031/*---------------------------------------------------*/ 1032int BZ_API(BZ2_bzDecompressEnd) ( bz_stream *strm ) 1033{ 1034 DState* s; 1035 if (strm == NULL) return BZ_PARAM_ERROR; 1036 s = strm->state; 1037 if (s == NULL) return BZ_PARAM_ERROR; 1038 if (s->strm != strm) return BZ_PARAM_ERROR; 1039 1040 if (s->tt != NULL) BZFREE(s->tt); 1041 if (s->ll16 != NULL) BZFREE(s->ll16); 1042 if (s->ll4 != NULL) BZFREE(s->ll4); 1043 1044 BZFREE(strm->state); 1045 strm->state = NULL; 1046 1047 return BZ_OK; 1048} 1049 1050/*---------------------------------------------------*/ 1051int BZ_API(BZ2_bzBuffToBuffDecompress) 1052 ( char* dest, 1053 unsigned int* destLen, 1054 char* source, 1055 unsigned int sourceLen, 1056 int small, 1057 int verbosity ) 1058{ 1059 bz_stream strm; 1060 int ret; 1061 1062 if (dest == NULL || destLen == NULL || 1063 source == NULL || 1064 (small != 0 && small != 1) || 1065 verbosity < 0 || verbosity > 4) 1066 return BZ_PARAM_ERROR; 1067 1068 strm.bzalloc = NULL; 1069 strm.bzfree = NULL; 1070 strm.opaque = NULL; 1071 ret = BZ2_bzDecompressInit ( &strm, verbosity, small ); 1072 if (ret != BZ_OK) return ret; 1073 1074 strm.next_in = source; 1075 strm.next_out = dest; 1076 strm.avail_in = sourceLen; 1077 strm.avail_out = *destLen; 1078 1079 ret = BZ2_bzDecompress ( &strm ); 1080 if (ret == BZ_OK) goto output_overflow_or_eof; 1081 if (ret != BZ_STREAM_END) goto errhandler; 1082 1083 /* normal termination */ 1084 *destLen -= strm.avail_out; 1085 BZ2_bzDecompressEnd ( &strm ); 1086 return BZ_OK; 1087 1088 output_overflow_or_eof: 1089 if (strm.avail_out > 0) { 1090 BZ2_bzDecompressEnd ( &strm ); 1091 return BZ_UNEXPECTED_EOF; 1092 } else { 1093 BZ2_bzDecompressEnd ( &strm ); 1094 return BZ_OUTBUFF_FULL; 1095 }; 1096 1097 errhandler: 1098 BZ2_bzDecompressEnd ( &strm ); 1099 return ret; 1100} 1101 1102/*---------------------------------------------------*/ 1103static 1104void makeMaps_d ( DState* s ) 1105{ 1106 Int32 i; 1107 s->nInUse = 0; 1108 for (i = 0; i < 256; i++) 1109 if (s->inUse[i]) { 1110 s->seqToUnseq[s->nInUse] = i; 1111 s->nInUse++; 1112 } 1113} 1114 1115/*---------------------------------------------------*/ 1116#define RETURN(rrr) \ 1117 { retVal = rrr; goto save_state_and_return; }; 1118 1119#define GET_BITS(lll,vvv,nnn) \ 1120 case lll: s->state = lll; \ 1121 while (True) { \ 1122 if (s->bsLive >= nnn) { \ 1123 UInt32 v; \ 1124 v = (s->bsBuff >> \ 1125 (s->bsLive-nnn)) & ((1 << nnn)-1); \ 1126 s->bsLive -= nnn; \ 1127 vvv = v; \ 1128 break; \ 1129 } \ 1130 if (s->strm->avail_in == 0) RETURN(BZ_OK); \ 1131 s->bsBuff \ 1132 = (s->bsBuff << 8) | \ 1133 ((UInt32) \ 1134 (*((UChar*)(s->strm->next_in)))); \ 1135 s->bsLive += 8; \ 1136 s->strm->next_in++; \ 1137 s->strm->avail_in--; \ 1138 s->strm->total_in_lo32++; \ 1139 if (s->strm->total_in_lo32 == 0) \ 1140 s->strm->total_in_hi32++; \ 1141 } 1142 1143#define GET_UCHAR(lll,uuu) \ 1144 GET_BITS(lll,uuu,8) 1145 1146#define GET_BIT(lll,uuu) \ 1147 GET_BITS(lll,uuu,1) 1148 1149/*---------------------------------------------------*/ 1150#define GET_MTF_VAL(label1,label2,lval) \ 1151{ \ 1152 if (groupPos == 0) { \ 1153 groupNo++; \ 1154 if (groupNo >= nSelectors) \ 1155 RETURN(BZ_DATA_ERROR); \ 1156 groupPos = BZ_G_SIZE; \ 1157 gSel = s->selector[groupNo]; \ 1158 gMinlen = s->minLens[gSel]; \ 1159 gLimit = &(s->limit[gSel][0]); \ 1160 gPerm = &(s->perm[gSel][0]); \ 1161 gBase = &(s->base[gSel][0]); \ 1162 } \ 1163 groupPos--; \ 1164 zn = gMinlen; \ 1165 GET_BITS(label1, zvec, zn); \ 1166 while (1) { \ 1167 if (zn > 20 /* the longest code */) \ 1168 RETURN(BZ_DATA_ERROR); \ 1169 if (zvec <= gLimit[zn]) break; \ 1170 zn++; \ 1171 GET_BIT(label2, zj); \ 1172 zvec = (zvec << 1) | zj; \ 1173 }; \ 1174 if (zvec - gBase[zn] < 0 \ 1175 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ 1176 RETURN(BZ_DATA_ERROR); \ 1177 lval = gPerm[zvec - gBase[zn]]; \ 1178} 1179 1180/*---------------------------------------------------*/ 1181void BZ2_hbCreateDecodeTables ( Int32 *limit, 1182 Int32 *base, 1183 Int32 *perm, 1184 UChar *length, 1185 Int32 minLen, 1186 Int32 maxLen, 1187 Int32 alphaSize ) 1188{ 1189 Int32 pp, i, j, vec; 1190 1191 pp = 0; 1192 for (i = minLen; i <= maxLen; i++) 1193 for (j = 0; j < alphaSize; j++) 1194 if (length[j] == i) { perm[pp] = j; pp++; }; 1195 1196 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0; 1197 for (i = 0; i < alphaSize; i++) base[length[i]+1]++; 1198 1199 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1]; 1200 1201 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0; 1202 vec = 0; 1203 1204 for (i = minLen; i <= maxLen; i++) { 1205 vec += (base[i+1] - base[i]); 1206 limit[i] = vec-1; 1207 vec <<= 1; 1208 } 1209 for (i = minLen + 1; i <= maxLen; i++) 1210 base[i] = ((limit[i-1] + 1) << 1) - base[i]; 1211} 1212 1213 1214/*---------------------------------------------------*/ 1215Int32 BZ2_decompress ( DState* s ) 1216{ 1217 UChar uc; 1218 Int32 retVal; 1219 Int32 minLen, maxLen; 1220 bz_stream* strm = s->strm; 1221 1222 /* stuff that needs to be saved/restored */ 1223 Int32 i; 1224 Int32 j; 1225 Int32 t; 1226 Int32 alphaSize; 1227 Int32 nGroups; 1228 Int32 nSelectors; 1229 Int32 EOB; 1230 Int32 groupNo; 1231 Int32 groupPos; 1232 Int32 nextSym; 1233 Int32 nblockMAX; 1234 Int32 nblock; 1235 Int32 es; 1236 Int32 N; 1237 Int32 curr; 1238 Int32 zt; 1239 Int32 zn; 1240 Int32 zvec; 1241 Int32 zj; 1242 Int32 gSel; 1243 Int32 gMinlen; 1244 Int32* gLimit; 1245 Int32* gBase; 1246 Int32* gPerm; 1247 1248 if (s->state == BZ_X_MAGIC_1) { 1249 /*initialise the save area*/ 1250 s->save_i = 0; 1251 s->save_j = 0; 1252 s->save_t = 0; 1253 s->save_alphaSize = 0; 1254 s->save_nGroups = 0; 1255 s->save_nSelectors = 0; 1256 s->save_EOB = 0; 1257 s->save_groupNo = 0; 1258 s->save_groupPos = 0; 1259 s->save_nextSym = 0; 1260 s->save_nblockMAX = 0; 1261 s->save_nblock = 0; 1262 s->save_es = 0; 1263 s->save_N = 0; 1264 s->save_curr = 0; 1265 s->save_zt = 0; 1266 s->save_zn = 0; 1267 s->save_zvec = 0; 1268 s->save_zj = 0; 1269 s->save_gSel = 0; 1270 s->save_gMinlen = 0; 1271 s->save_gLimit = NULL; 1272 s->save_gBase = NULL; 1273 s->save_gPerm = NULL; 1274 } 1275 1276 /*restore from the save area*/ 1277 i = s->save_i; 1278 j = s->save_j; 1279 t = s->save_t; 1280 alphaSize = s->save_alphaSize; 1281 nGroups = s->save_nGroups; 1282 nSelectors = s->save_nSelectors; 1283 EOB = s->save_EOB; 1284 groupNo = s->save_groupNo; 1285 groupPos = s->save_groupPos; 1286 nextSym = s->save_nextSym; 1287 nblockMAX = s->save_nblockMAX; 1288 nblock = s->save_nblock; 1289 es = s->save_es; 1290 N = s->save_N; 1291 curr = s->save_curr; 1292 zt = s->save_zt; 1293 zn = s->save_zn; 1294 zvec = s->save_zvec; 1295 zj = s->save_zj; 1296 gSel = s->save_gSel; 1297 gMinlen = s->save_gMinlen; 1298 gLimit = s->save_gLimit; 1299 gBase = s->save_gBase; 1300 gPerm = s->save_gPerm; 1301 1302 retVal = BZ_OK; 1303 1304 switch (s->state) { 1305 1306 GET_UCHAR(BZ_X_MAGIC_1, uc); 1307 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC); 1308 1309 GET_UCHAR(BZ_X_MAGIC_2, uc); 1310 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC); 1311 1312 GET_UCHAR(BZ_X_MAGIC_3, uc) 1313 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC); 1314 1315 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) 1316 if (s->blockSize100k < (BZ_HDR_0 + 1) || 1317 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC); 1318 s->blockSize100k -= BZ_HDR_0; 1319 1320 if (s->smallDecompress) { 1321 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); 1322 s->ll4 = BZALLOC( 1323 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) 1324 ); 1325 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); 1326 } else { 1327 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); 1328 if (s->tt == NULL) RETURN(BZ_MEM_ERROR); 1329 } 1330 1331 GET_UCHAR(BZ_X_BLKHDR_1, uc); 1332 1333 if (uc == 0x17) goto endhdr_2; 1334 if (uc != 0x31) RETURN(BZ_DATA_ERROR); 1335 GET_UCHAR(BZ_X_BLKHDR_2, uc); 1336 if (uc != 0x41) RETURN(BZ_DATA_ERROR); 1337 GET_UCHAR(BZ_X_BLKHDR_3, uc); 1338 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 1339 GET_UCHAR(BZ_X_BLKHDR_4, uc); 1340 if (uc != 0x26) RETURN(BZ_DATA_ERROR); 1341 GET_UCHAR(BZ_X_BLKHDR_5, uc); 1342 if (uc != 0x53) RETURN(BZ_DATA_ERROR); 1343 GET_UCHAR(BZ_X_BLKHDR_6, uc); 1344 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 1345 1346 s->currBlockNo++; 1347 if (s->verbosity >= 2) 1348 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); 1349 1350 s->storedBlockCRC = 0; 1351 GET_UCHAR(BZ_X_BCRC_1, uc); 1352 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 1353 GET_UCHAR(BZ_X_BCRC_2, uc); 1354 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 1355 GET_UCHAR(BZ_X_BCRC_3, uc); 1356 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 1357 GET_UCHAR(BZ_X_BCRC_4, uc); 1358 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 1359 1360 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); 1361 1362 s->origPtr = 0; 1363 GET_UCHAR(BZ_X_ORIGPTR_1, uc); 1364 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 1365 GET_UCHAR(BZ_X_ORIGPTR_2, uc); 1366 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 1367 GET_UCHAR(BZ_X_ORIGPTR_3, uc); 1368 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 1369 1370 if (s->origPtr < 0) 1371 RETURN(BZ_DATA_ERROR); 1372 if (s->origPtr > 10 + 100000*s->blockSize100k) 1373 RETURN(BZ_DATA_ERROR); 1374 1375 /*--- Receive the mapping table ---*/ 1376 for (i = 0; i < 16; i++) { 1377 GET_BIT(BZ_X_MAPPING_1, uc); 1378 if (uc == 1) 1379 s->inUse16[i] = True; else 1380 s->inUse16[i] = False; 1381 } 1382 1383 for (i = 0; i < 256; i++) s->inUse[i] = False; 1384 1385 for (i = 0; i < 16; i++) 1386 if (s->inUse16[i]) 1387 for (j = 0; j < 16; j++) { 1388 GET_BIT(BZ_X_MAPPING_2, uc); 1389 if (uc == 1) s->inUse[i * 16 + j] = True; 1390 } 1391 makeMaps_d ( s ); 1392 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); 1393 alphaSize = s->nInUse+2; 1394 1395 /*--- Now the selectors ---*/ 1396 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); 1397 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); 1398 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); 1399 if (nSelectors < 1) RETURN(BZ_DATA_ERROR); 1400 for (i = 0; i < nSelectors; i++) { 1401 j = 0; 1402 while (True) { 1403 GET_BIT(BZ_X_SELECTOR_3, uc); 1404 if (uc == 0) break; 1405 j++; 1406 if (j >= nGroups) RETURN(BZ_DATA_ERROR); 1407 } 1408 s->selectorMtf[i] = j; 1409 } 1410 1411 /*--- Undo the MTF values for the selectors. ---*/ 1412 { 1413 UChar pos[BZ_N_GROUPS], tmp, v; 1414 for (v = 0; v < nGroups; v++) pos[v] = v; 1415 1416 for (i = 0; i < nSelectors; i++) { 1417 v = s->selectorMtf[i]; 1418 tmp = pos[v]; 1419 while (v > 0) { pos[v] = pos[v-1]; v--; } 1420 pos[0] = tmp; 1421 s->selector[i] = tmp; 1422 } 1423 } 1424 1425 /*--- Now the coding tables ---*/ 1426 for (t = 0; t < nGroups; t++) { 1427 GET_BITS(BZ_X_CODING_1, curr, 5); 1428 for (i = 0; i < alphaSize; i++) { 1429 while (True) { 1430 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); 1431 GET_BIT(BZ_X_CODING_2, uc); 1432 if (uc == 0) break; 1433 GET_BIT(BZ_X_CODING_3, uc); 1434 if (uc == 0) curr++; else curr--; 1435 } 1436 s->len[t][i] = curr; 1437 } 1438 } 1439 1440 /*--- Create the Huffman decoding tables ---*/ 1441 for (t = 0; t < nGroups; t++) { 1442 minLen = 32; 1443 maxLen = 0; 1444 for (i = 0; i < alphaSize; i++) { 1445 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 1446 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 1447 } 1448 BZ2_hbCreateDecodeTables ( 1449 &(s->limit[t][0]), 1450 &(s->base[t][0]), 1451 &(s->perm[t][0]), 1452 &(s->len[t][0]), 1453 minLen, maxLen, alphaSize 1454 ); 1455 s->minLens[t] = minLen; 1456 } 1457 1458 /*--- Now the MTF values ---*/ 1459 1460 EOB = s->nInUse+1; 1461 nblockMAX = 100000 * s->blockSize100k; 1462 groupNo = -1; 1463 groupPos = 0; 1464 1465 for (i = 0; i <= 255; i++) s->unzftab[i] = 0; 1466 1467 /*-- MTF init --*/ 1468 { 1469 Int32 ii, jj, kk; 1470 kk = MTFA_SIZE-1; 1471 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { 1472 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 1473 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); 1474 kk--; 1475 } 1476 s->mtfbase[ii] = kk + 1; 1477 } 1478 } 1479 /*-- end MTF init --*/ 1480 1481 nblock = 0; 1482 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); 1483 1484 while (True) { 1485 1486 if (nextSym == EOB) break; 1487 1488 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { 1489 1490 es = -1; 1491 N = 1; 1492 do { 1493 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 1494 if (nextSym == BZ_RUNB) es = es + (1+1) * N; 1495 N = N * 2; 1496 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 1497 } 1498 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 1499 1500 es++; 1501 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 1502 s->unzftab[uc] += es; 1503 1504 if (s->smallDecompress) 1505 while (es > 0) { 1506 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 1507 s->ll16[nblock] = (UInt16)uc; 1508 nblock++; 1509 es--; 1510 } 1511 else 1512 while (es > 0) { 1513 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 1514 s->tt[nblock] = (UInt32)uc; 1515 nblock++; 1516 es--; 1517 }; 1518 1519 continue; 1520 1521 } else { 1522 1523 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); 1524 1525 /*-- uc = MTF ( nextSym-1 ) --*/ 1526 { 1527 Int32 ii, jj, kk, pp, lno, off; 1528 UInt32 nn; 1529 nn = (UInt32)(nextSym - 1); 1530 1531 if (nn < MTFL_SIZE) { 1532 /* avoid general-case expense */ 1533 pp = s->mtfbase[0]; 1534 uc = s->mtfa[pp+nn]; 1535 while (nn > 3) { 1536 Int32 z = pp+nn; 1537 s->mtfa[(z) ] = s->mtfa[(z)-1]; 1538 s->mtfa[(z)-1] = s->mtfa[(z)-2]; 1539 s->mtfa[(z)-2] = s->mtfa[(z)-3]; 1540 s->mtfa[(z)-3] = s->mtfa[(z)-4]; 1541 nn -= 4; 1542 } 1543 while (nn > 0) { 1544 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 1545 }; 1546 s->mtfa[pp] = uc; 1547 } else { 1548 /* general case */ 1549 lno = nn / MTFL_SIZE; 1550 off = nn % MTFL_SIZE; 1551 pp = s->mtfbase[lno] + off; 1552 uc = s->mtfa[pp]; 1553 while (pp > s->mtfbase[lno]) { 1554 s->mtfa[pp] = s->mtfa[pp-1]; pp--; 1555 }; 1556 s->mtfbase[lno]++; 1557 while (lno > 0) { 1558 s->mtfbase[lno]--; 1559 s->mtfa[s->mtfbase[lno]] 1560 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 1561 lno--; 1562 } 1563 s->mtfbase[0]--; 1564 s->mtfa[s->mtfbase[0]] = uc; 1565 if (s->mtfbase[0] == 0) { 1566 kk = MTFA_SIZE-1; 1567 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 1568 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 1569 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 1570 kk--; 1571 } 1572 s->mtfbase[ii] = kk + 1; 1573 } 1574 } 1575 } 1576 } 1577 /*-- end uc = MTF ( nextSym-1 ) --*/ 1578 1579 s->unzftab[s->seqToUnseq[uc]]++; 1580 if (s->smallDecompress) 1581 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 1582 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 1583 nblock++; 1584 1585 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 1586 continue; 1587 } 1588 } 1589 1590 /* Now we know what nblock is, we can do a better sanity 1591 check on s->origPtr. 1592 */ 1593 if (s->origPtr < 0 || s->origPtr >= nblock) 1594 RETURN(BZ_DATA_ERROR); 1595 1596 s->state_out_len = 0; 1597 s->state_out_ch = 0; 1598 BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 1599 s->state = BZ_X_OUTPUT; 1600 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 1601 1602 /*-- Set up cftab to facilitate generation of T^(-1) --*/ 1603 s->cftab[0] = 0; 1604 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 1605 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 1606 1607 if (s->smallDecompress) { 1608 1609 /*-- Make a copy of cftab, used in generation of T --*/ 1610 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 1611 1612 /*-- compute the T vector --*/ 1613 for (i = 0; i < nblock; i++) { 1614 uc = (UChar)(s->ll16[i]); 1615 SET_LL(i, s->cftabCopy[uc]); 1616 s->cftabCopy[uc]++; 1617 } 1618 1619 /*-- Compute T^(-1) by pointer reversal on T --*/ 1620 i = s->origPtr; 1621 j = GET_LL(i); 1622 do { 1623 Int32 tmp = GET_LL(j); 1624 SET_LL(j, i); 1625 i = j; 1626 j = tmp; 1627 } 1628 while (i != s->origPtr); 1629 1630 s->tPos = s->origPtr; 1631 s->nblock_used = 0; 1632 if (s->blockRandomised) { 1633 BZ_RAND_INIT_MASK; 1634 BZ_GET_SMALL(s->k0); s->nblock_used++; 1635 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 1636 } else { 1637 BZ_GET_SMALL(s->k0); s->nblock_used++; 1638 } 1639 1640 } else { 1641 1642 /*-- compute the T^(-1) vector --*/ 1643 for (i = 0; i < nblock; i++) { 1644 uc = (UChar)(s->tt[i] & 0xff); 1645 s->tt[s->cftab[uc]] |= (i << 8); 1646 s->cftab[uc]++; 1647 } 1648 1649 s->tPos = s->tt[s->origPtr] >> 8; 1650 s->nblock_used = 0; 1651 if (s->blockRandomised) { 1652 BZ_RAND_INIT_MASK; 1653 BZ_GET_FAST(s->k0); s->nblock_used++; 1654 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 1655 } else { 1656 BZ_GET_FAST(s->k0); s->nblock_used++; 1657 } 1658 1659 } 1660 1661 RETURN(BZ_OK); 1662 1663 1664 1665 endhdr_2: 1666 1667 GET_UCHAR(BZ_X_ENDHDR_2, uc); 1668 if (uc != 0x72) RETURN(BZ_DATA_ERROR); 1669 GET_UCHAR(BZ_X_ENDHDR_3, uc); 1670 if (uc != 0x45) RETURN(BZ_DATA_ERROR); 1671 GET_UCHAR(BZ_X_ENDHDR_4, uc); 1672 if (uc != 0x38) RETURN(BZ_DATA_ERROR); 1673 GET_UCHAR(BZ_X_ENDHDR_5, uc); 1674 if (uc != 0x50) RETURN(BZ_DATA_ERROR); 1675 GET_UCHAR(BZ_X_ENDHDR_6, uc); 1676 if (uc != 0x90) RETURN(BZ_DATA_ERROR); 1677 1678 s->storedCombinedCRC = 0; 1679 GET_UCHAR(BZ_X_CCRC_1, uc); 1680 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 1681 GET_UCHAR(BZ_X_CCRC_2, uc); 1682 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 1683 GET_UCHAR(BZ_X_CCRC_3, uc); 1684 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 1685 GET_UCHAR(BZ_X_CCRC_4, uc); 1686 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 1687 1688 s->state = BZ_X_IDLE; 1689 RETURN(BZ_STREAM_END); 1690 1691 default: AssertH ( False, 4001 ); } 1692 AssertH ( False, 4002 ); 1693 1694 save_state_and_return: 1695 1696 s->save_i = i; 1697 s->save_j = j; 1698 s->save_t = t; 1699 s->save_alphaSize = alphaSize; 1700 s->save_nGroups = nGroups; 1701 s->save_nSelectors = nSelectors; 1702 s->save_EOB = EOB; 1703 s->save_groupNo = groupNo; 1704 s->save_groupPos = groupPos; 1705 s->save_nextSym = nextSym; 1706 s->save_nblockMAX = nblockMAX; 1707 s->save_nblock = nblock; 1708 s->save_es = es; 1709 s->save_N = N; 1710 s->save_curr = curr; 1711 s->save_zt = zt; 1712 s->save_zn = zn; 1713 s->save_zvec = zvec; 1714 s->save_zj = zj; 1715 s->save_gSel = gSel; 1716 s->save_gMinlen = gMinlen; 1717 s->save_gLimit = gLimit; 1718 s->save_gBase = gBase; 1719 s->save_gPerm = gPerm; 1720 1721 return retVal; 1722} 1723 1724/*---------------------------------------------------*/ 1725#define WEIGHTOF(zz0) ((zz0) & 0xffffff00) 1726#define DEPTHOF(zz1) ((zz1) & 0x000000ff) 1727#define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3)) 1728 1729#define ADDWEIGHTS(zw1,zw2) \ 1730 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \ 1731 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2))) 1732 1733#define UPHEAP(z) \ 1734{ \ 1735 Int32 zz, tmp; \ 1736 zz = z; tmp = heap[zz]; \ 1737 while (weight[tmp] < weight[heap[zz >> 1]]) { \ 1738 heap[zz] = heap[zz >> 1]; \ 1739 zz >>= 1; \ 1740 } \ 1741 heap[zz] = tmp; \ 1742} 1743 1744#define DOWNHEAP(z) \ 1745{ \ 1746 Int32 zz, yy, tmp; \ 1747 zz = z; tmp = heap[zz]; \ 1748 while (True) { \ 1749 yy = zz << 1; \ 1750 if (yy > nHeap) break; \ 1751 if (yy < nHeap && \ 1752 weight[heap[yy+1]] < weight[heap[yy]]) \ 1753 yy++; \ 1754 if (weight[tmp] < weight[heap[yy]]) break; \ 1755 heap[zz] = heap[yy]; \ 1756 zz = yy; \ 1757 } \ 1758 heap[zz] = tmp; \ 1759} 1760 1761/*---------------------------------------------------*/ 1762void BZ2_hbMakeCodeLengths ( UChar *len, 1763 Int32 *freq, 1764 Int32 alphaSize, 1765 Int32 maxLen ) 1766{ 1767 /*-- 1768 Nodes and heap entries run from 1. Entry 0 1769 for both the heap and nodes is a sentinel. 1770 --*/ 1771 Int32 nNodes, nHeap, n1, n2, i, j, k; 1772 Bool tooLong; 1773 1774 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ]; 1775 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ]; 1776 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; 1777 1778 for (i = 0; i < alphaSize; i++) 1779 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8; 1780 1781 while (True) { 1782 1783 nNodes = alphaSize; 1784 nHeap = 0; 1785 1786 heap[0] = 0; 1787 weight[0] = 0; 1788 parent[0] = -2; 1789 1790 for (i = 1; i <= alphaSize; i++) { 1791 parent[i] = -1; 1792 nHeap++; 1793 heap[nHeap] = i; 1794 UPHEAP(nHeap); 1795 } 1796 1797 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 ); 1798 1799 while (nHeap > 1) { 1800 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 1801 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 1802 nNodes++; 1803 parent[n1] = parent[n2] = nNodes; 1804 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]); 1805 parent[nNodes] = -1; 1806 nHeap++; 1807 heap[nHeap] = nNodes; 1808 UPHEAP(nHeap); 1809 } 1810 1811 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 ); 1812 1813 tooLong = False; 1814 for (i = 1; i <= alphaSize; i++) { 1815 j = 0; 1816 k = i; 1817 while (parent[k] >= 0) { k = parent[k]; j++; } 1818 len[i-1] = j; 1819 if (j > maxLen) tooLong = True; 1820 } 1821 1822 if (! tooLong) break; 1823 1824 for (i = 1; i < alphaSize; i++) { 1825 j = weight[i] >> 8; 1826 j = 1 + (j / 2); 1827 weight[i] = j << 8; 1828 } 1829 } 1830} 1831 1832 1833/*---------------------------------------------------*/ 1834void BZ2_hbAssignCodes ( Int32 *code, 1835 UChar *length, 1836 Int32 minLen, 1837 Int32 maxLen, 1838 Int32 alphaSize ) 1839{ 1840 Int32 n, vec, i; 1841 1842 vec = 0; 1843 for (n = minLen; n <= maxLen; n++) { 1844 for (i = 0; i < alphaSize; i++) 1845 if (length[i] == n) { code[i] = vec; vec++; }; 1846 vec <<= 1; 1847 } 1848} 1849 1850/* the-end. */ 1851