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