The Android Open Source Project | cfb3b27 | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 1 | |
| 2 | /*-------------------------------------------------------------*/ |
| 3 | /*--- Private header file for the library. ---*/ |
| 4 | /*--- bzlib_private.h ---*/ |
| 5 | /*-------------------------------------------------------------*/ |
| 6 | |
| 7 | /* ------------------------------------------------------------------ |
| 8 | This file is part of bzip2/libbzip2, a program and library for |
| 9 | lossless, block-sorting data compression. |
| 10 | |
Nick Kralevich | 172b266 | 2010-09-20 17:21:30 -0700 | [diff] [blame] | 11 | bzip2/libbzip2 version 1.0.6 of 6 September 2010 |
| 12 | Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org> |
The Android Open Source Project | cfb3b27 | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 13 | |
| 14 | Please read the WARNING, DISCLAIMER and PATENTS sections in the |
| 15 | README file. |
| 16 | |
| 17 | This program is released under the terms of the license contained |
| 18 | in the file LICENSE. |
| 19 | ------------------------------------------------------------------ */ |
| 20 | |
| 21 | |
| 22 | #ifndef _BZLIB_PRIVATE_H |
| 23 | #define _BZLIB_PRIVATE_H |
| 24 | |
| 25 | #include <stdlib.h> |
| 26 | |
| 27 | #ifndef BZ_NO_STDIO |
| 28 | #include <stdio.h> |
| 29 | #include <ctype.h> |
| 30 | #include <string.h> |
| 31 | #endif |
| 32 | |
| 33 | #include "bzlib.h" |
| 34 | |
| 35 | |
| 36 | |
| 37 | /*-- General stuff. --*/ |
| 38 | |
Nick Kralevich | 172b266 | 2010-09-20 17:21:30 -0700 | [diff] [blame] | 39 | #define BZ_VERSION "1.0.6, 6-Sept-2010" |
The Android Open Source Project | cfb3b27 | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 40 | |
| 41 | typedef char Char; |
| 42 | typedef unsigned char Bool; |
| 43 | typedef unsigned char UChar; |
| 44 | typedef int Int32; |
| 45 | typedef unsigned int UInt32; |
| 46 | typedef short Int16; |
| 47 | typedef unsigned short UInt16; |
| 48 | |
| 49 | #define True ((Bool)1) |
| 50 | #define False ((Bool)0) |
| 51 | |
| 52 | #ifndef __GNUC__ |
| 53 | #define __inline__ /* */ |
| 54 | #endif |
| 55 | |
| 56 | #ifndef BZ_NO_STDIO |
| 57 | |
| 58 | extern void BZ2_bz__AssertH__fail ( int errcode ); |
| 59 | #define AssertH(cond,errcode) \ |
| 60 | { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); } |
| 61 | |
| 62 | #if BZ_DEBUG |
| 63 | #define AssertD(cond,msg) \ |
| 64 | { if (!(cond)) { \ |
| 65 | fprintf ( stderr, \ |
| 66 | "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\ |
| 67 | exit(1); \ |
| 68 | }} |
| 69 | #else |
| 70 | #define AssertD(cond,msg) /* */ |
| 71 | #endif |
| 72 | |
| 73 | #define VPrintf0(zf) \ |
| 74 | fprintf(stderr,zf) |
| 75 | #define VPrintf1(zf,za1) \ |
| 76 | fprintf(stderr,zf,za1) |
| 77 | #define VPrintf2(zf,za1,za2) \ |
| 78 | fprintf(stderr,zf,za1,za2) |
| 79 | #define VPrintf3(zf,za1,za2,za3) \ |
| 80 | fprintf(stderr,zf,za1,za2,za3) |
| 81 | #define VPrintf4(zf,za1,za2,za3,za4) \ |
| 82 | fprintf(stderr,zf,za1,za2,za3,za4) |
| 83 | #define VPrintf5(zf,za1,za2,za3,za4,za5) \ |
| 84 | fprintf(stderr,zf,za1,za2,za3,za4,za5) |
| 85 | |
| 86 | #else |
| 87 | |
| 88 | extern void bz_internal_error ( int errcode ); |
| 89 | #define AssertH(cond,errcode) \ |
| 90 | { if (!(cond)) bz_internal_error ( errcode ); } |
| 91 | #define AssertD(cond,msg) do { } while (0) |
| 92 | #define VPrintf0(zf) do { } while (0) |
| 93 | #define VPrintf1(zf,za1) do { } while (0) |
| 94 | #define VPrintf2(zf,za1,za2) do { } while (0) |
| 95 | #define VPrintf3(zf,za1,za2,za3) do { } while (0) |
| 96 | #define VPrintf4(zf,za1,za2,za3,za4) do { } while (0) |
| 97 | #define VPrintf5(zf,za1,za2,za3,za4,za5) do { } while (0) |
| 98 | |
| 99 | #endif |
| 100 | |
| 101 | |
| 102 | #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1) |
| 103 | #define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp)) |
| 104 | |
| 105 | |
| 106 | /*-- Header bytes. --*/ |
| 107 | |
| 108 | #define BZ_HDR_B 0x42 /* 'B' */ |
| 109 | #define BZ_HDR_Z 0x5a /* 'Z' */ |
| 110 | #define BZ_HDR_h 0x68 /* 'h' */ |
| 111 | #define BZ_HDR_0 0x30 /* '0' */ |
| 112 | |
| 113 | /*-- Constants for the back end. --*/ |
| 114 | |
| 115 | #define BZ_MAX_ALPHA_SIZE 258 |
| 116 | #define BZ_MAX_CODE_LEN 23 |
| 117 | |
| 118 | #define BZ_RUNA 0 |
| 119 | #define BZ_RUNB 1 |
| 120 | |
| 121 | #define BZ_N_GROUPS 6 |
| 122 | #define BZ_G_SIZE 50 |
| 123 | #define BZ_N_ITERS 4 |
| 124 | |
| 125 | #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) |
| 126 | |
| 127 | |
| 128 | |
| 129 | /*-- Stuff for randomising repetitive blocks. --*/ |
| 130 | |
| 131 | extern Int32 BZ2_rNums[512]; |
| 132 | |
| 133 | #define BZ_RAND_DECLS \ |
| 134 | Int32 rNToGo; \ |
| 135 | Int32 rTPos \ |
| 136 | |
| 137 | #define BZ_RAND_INIT_MASK \ |
| 138 | s->rNToGo = 0; \ |
| 139 | s->rTPos = 0 \ |
| 140 | |
| 141 | #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0) |
| 142 | |
| 143 | #define BZ_RAND_UPD_MASK \ |
| 144 | if (s->rNToGo == 0) { \ |
| 145 | s->rNToGo = BZ2_rNums[s->rTPos]; \ |
| 146 | s->rTPos++; \ |
| 147 | if (s->rTPos == 512) s->rTPos = 0; \ |
| 148 | } \ |
| 149 | s->rNToGo--; |
| 150 | |
| 151 | |
| 152 | |
| 153 | /*-- Stuff for doing CRCs. --*/ |
| 154 | |
| 155 | extern UInt32 BZ2_crc32Table[256]; |
| 156 | |
| 157 | #define BZ_INITIALISE_CRC(crcVar) \ |
| 158 | { \ |
| 159 | crcVar = 0xffffffffL; \ |
| 160 | } |
| 161 | |
| 162 | #define BZ_FINALISE_CRC(crcVar) \ |
| 163 | { \ |
| 164 | crcVar = ~(crcVar); \ |
| 165 | } |
| 166 | |
| 167 | #define BZ_UPDATE_CRC(crcVar,cha) \ |
| 168 | { \ |
| 169 | crcVar = (crcVar << 8) ^ \ |
| 170 | BZ2_crc32Table[(crcVar >> 24) ^ \ |
| 171 | ((UChar)cha)]; \ |
| 172 | } |
| 173 | |
| 174 | |
| 175 | |
| 176 | /*-- States and modes for compression. --*/ |
| 177 | |
| 178 | #define BZ_M_IDLE 1 |
| 179 | #define BZ_M_RUNNING 2 |
| 180 | #define BZ_M_FLUSHING 3 |
| 181 | #define BZ_M_FINISHING 4 |
| 182 | |
| 183 | #define BZ_S_OUTPUT 1 |
| 184 | #define BZ_S_INPUT 2 |
| 185 | |
| 186 | #define BZ_N_RADIX 2 |
| 187 | #define BZ_N_QSORT 12 |
| 188 | #define BZ_N_SHELL 18 |
| 189 | #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2) |
| 190 | |
| 191 | |
| 192 | |
| 193 | |
| 194 | /*-- Structure holding all the compression-side stuff. --*/ |
| 195 | |
| 196 | typedef |
| 197 | struct { |
| 198 | /* pointer back to the struct bz_stream */ |
| 199 | bz_stream* strm; |
| 200 | |
| 201 | /* mode this stream is in, and whether inputting */ |
| 202 | /* or outputting data */ |
| 203 | Int32 mode; |
| 204 | Int32 state; |
| 205 | |
| 206 | /* remembers avail_in when flush/finish requested */ |
| 207 | UInt32 avail_in_expect; |
| 208 | |
| 209 | /* for doing the block sorting */ |
| 210 | UInt32* arr1; |
| 211 | UInt32* arr2; |
| 212 | UInt32* ftab; |
| 213 | Int32 origPtr; |
| 214 | |
| 215 | /* aliases for arr1 and arr2 */ |
| 216 | UInt32* ptr; |
| 217 | UChar* block; |
| 218 | UInt16* mtfv; |
| 219 | UChar* zbits; |
| 220 | |
| 221 | /* for deciding when to use the fallback sorting algorithm */ |
| 222 | Int32 workFactor; |
| 223 | |
| 224 | /* run-length-encoding of the input */ |
| 225 | UInt32 state_in_ch; |
| 226 | Int32 state_in_len; |
| 227 | BZ_RAND_DECLS; |
| 228 | |
| 229 | /* input and output limits and current posns */ |
| 230 | Int32 nblock; |
| 231 | Int32 nblockMAX; |
| 232 | Int32 numZ; |
| 233 | Int32 state_out_pos; |
| 234 | |
| 235 | /* map of bytes used in block */ |
| 236 | Int32 nInUse; |
| 237 | Bool inUse[256]; |
| 238 | UChar unseqToSeq[256]; |
| 239 | |
| 240 | /* the buffer for bit stream creation */ |
| 241 | UInt32 bsBuff; |
| 242 | Int32 bsLive; |
| 243 | |
| 244 | /* block and combined CRCs */ |
| 245 | UInt32 blockCRC; |
| 246 | UInt32 combinedCRC; |
| 247 | |
| 248 | /* misc administratium */ |
| 249 | Int32 verbosity; |
| 250 | Int32 blockNo; |
| 251 | Int32 blockSize100k; |
| 252 | |
| 253 | /* stuff for coding the MTF values */ |
| 254 | Int32 nMTF; |
| 255 | Int32 mtfFreq [BZ_MAX_ALPHA_SIZE]; |
| 256 | UChar selector [BZ_MAX_SELECTORS]; |
| 257 | UChar selectorMtf[BZ_MAX_SELECTORS]; |
| 258 | |
| 259 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; |
| 260 | Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; |
| 261 | Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; |
| 262 | /* second dimension: only 3 needed; 4 makes index calculations faster */ |
| 263 | UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4]; |
| 264 | |
| 265 | } |
| 266 | EState; |
| 267 | |
| 268 | |
| 269 | |
| 270 | /*-- externs for compression. --*/ |
| 271 | |
| 272 | extern void |
| 273 | BZ2_blockSort ( EState* ); |
| 274 | |
| 275 | extern void |
| 276 | BZ2_compressBlock ( EState*, Bool ); |
| 277 | |
| 278 | extern void |
| 279 | BZ2_bsInitWrite ( EState* ); |
| 280 | |
| 281 | extern void |
| 282 | BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 ); |
| 283 | |
| 284 | extern void |
| 285 | BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 ); |
| 286 | |
| 287 | |
| 288 | |
| 289 | /*-- states for decompression. --*/ |
| 290 | |
| 291 | #define BZ_X_IDLE 1 |
| 292 | #define BZ_X_OUTPUT 2 |
| 293 | |
| 294 | #define BZ_X_MAGIC_1 10 |
| 295 | #define BZ_X_MAGIC_2 11 |
| 296 | #define BZ_X_MAGIC_3 12 |
| 297 | #define BZ_X_MAGIC_4 13 |
| 298 | #define BZ_X_BLKHDR_1 14 |
| 299 | #define BZ_X_BLKHDR_2 15 |
| 300 | #define BZ_X_BLKHDR_3 16 |
| 301 | #define BZ_X_BLKHDR_4 17 |
| 302 | #define BZ_X_BLKHDR_5 18 |
| 303 | #define BZ_X_BLKHDR_6 19 |
| 304 | #define BZ_X_BCRC_1 20 |
| 305 | #define BZ_X_BCRC_2 21 |
| 306 | #define BZ_X_BCRC_3 22 |
| 307 | #define BZ_X_BCRC_4 23 |
| 308 | #define BZ_X_RANDBIT 24 |
| 309 | #define BZ_X_ORIGPTR_1 25 |
| 310 | #define BZ_X_ORIGPTR_2 26 |
| 311 | #define BZ_X_ORIGPTR_3 27 |
| 312 | #define BZ_X_MAPPING_1 28 |
| 313 | #define BZ_X_MAPPING_2 29 |
| 314 | #define BZ_X_SELECTOR_1 30 |
| 315 | #define BZ_X_SELECTOR_2 31 |
| 316 | #define BZ_X_SELECTOR_3 32 |
| 317 | #define BZ_X_CODING_1 33 |
| 318 | #define BZ_X_CODING_2 34 |
| 319 | #define BZ_X_CODING_3 35 |
| 320 | #define BZ_X_MTF_1 36 |
| 321 | #define BZ_X_MTF_2 37 |
| 322 | #define BZ_X_MTF_3 38 |
| 323 | #define BZ_X_MTF_4 39 |
| 324 | #define BZ_X_MTF_5 40 |
| 325 | #define BZ_X_MTF_6 41 |
| 326 | #define BZ_X_ENDHDR_2 42 |
| 327 | #define BZ_X_ENDHDR_3 43 |
| 328 | #define BZ_X_ENDHDR_4 44 |
| 329 | #define BZ_X_ENDHDR_5 45 |
| 330 | #define BZ_X_ENDHDR_6 46 |
| 331 | #define BZ_X_CCRC_1 47 |
| 332 | #define BZ_X_CCRC_2 48 |
| 333 | #define BZ_X_CCRC_3 49 |
| 334 | #define BZ_X_CCRC_4 50 |
| 335 | |
| 336 | |
| 337 | |
| 338 | /*-- Constants for the fast MTF decoder. --*/ |
| 339 | |
| 340 | #define MTFA_SIZE 4096 |
| 341 | #define MTFL_SIZE 16 |
| 342 | |
| 343 | |
| 344 | |
| 345 | /*-- Structure holding all the decompression-side stuff. --*/ |
| 346 | |
| 347 | typedef |
| 348 | struct { |
| 349 | /* pointer back to the struct bz_stream */ |
| 350 | bz_stream* strm; |
| 351 | |
| 352 | /* state indicator for this stream */ |
| 353 | Int32 state; |
| 354 | |
| 355 | /* for doing the final run-length decoding */ |
| 356 | UChar state_out_ch; |
| 357 | Int32 state_out_len; |
| 358 | Bool blockRandomised; |
| 359 | BZ_RAND_DECLS; |
| 360 | |
| 361 | /* the buffer for bit stream reading */ |
| 362 | UInt32 bsBuff; |
| 363 | Int32 bsLive; |
| 364 | |
| 365 | /* misc administratium */ |
| 366 | Int32 blockSize100k; |
| 367 | Bool smallDecompress; |
| 368 | Int32 currBlockNo; |
| 369 | Int32 verbosity; |
| 370 | |
| 371 | /* for undoing the Burrows-Wheeler transform */ |
| 372 | Int32 origPtr; |
| 373 | UInt32 tPos; |
| 374 | Int32 k0; |
| 375 | Int32 unzftab[256]; |
| 376 | Int32 nblock_used; |
| 377 | Int32 cftab[257]; |
| 378 | Int32 cftabCopy[257]; |
| 379 | |
| 380 | /* for undoing the Burrows-Wheeler transform (FAST) */ |
| 381 | UInt32 *tt; |
| 382 | |
| 383 | /* for undoing the Burrows-Wheeler transform (SMALL) */ |
| 384 | UInt16 *ll16; |
| 385 | UChar *ll4; |
| 386 | |
| 387 | /* stored and calculated CRCs */ |
| 388 | UInt32 storedBlockCRC; |
| 389 | UInt32 storedCombinedCRC; |
| 390 | UInt32 calculatedBlockCRC; |
| 391 | UInt32 calculatedCombinedCRC; |
| 392 | |
| 393 | /* map of bytes used in block */ |
| 394 | Int32 nInUse; |
| 395 | Bool inUse[256]; |
| 396 | Bool inUse16[16]; |
| 397 | UChar seqToUnseq[256]; |
| 398 | |
| 399 | /* for decoding the MTF values */ |
| 400 | UChar mtfa [MTFA_SIZE]; |
| 401 | Int32 mtfbase[256 / MTFL_SIZE]; |
| 402 | UChar selector [BZ_MAX_SELECTORS]; |
| 403 | UChar selectorMtf[BZ_MAX_SELECTORS]; |
| 404 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; |
| 405 | |
| 406 | Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; |
| 407 | Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; |
| 408 | Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; |
| 409 | Int32 minLens[BZ_N_GROUPS]; |
| 410 | |
| 411 | /* save area for scalars in the main decompress code */ |
| 412 | Int32 save_i; |
| 413 | Int32 save_j; |
| 414 | Int32 save_t; |
| 415 | Int32 save_alphaSize; |
| 416 | Int32 save_nGroups; |
| 417 | Int32 save_nSelectors; |
| 418 | Int32 save_EOB; |
| 419 | Int32 save_groupNo; |
| 420 | Int32 save_groupPos; |
| 421 | Int32 save_nextSym; |
| 422 | Int32 save_nblockMAX; |
| 423 | Int32 save_nblock; |
| 424 | Int32 save_es; |
| 425 | Int32 save_N; |
| 426 | Int32 save_curr; |
| 427 | Int32 save_zt; |
| 428 | Int32 save_zn; |
| 429 | Int32 save_zvec; |
| 430 | Int32 save_zj; |
| 431 | Int32 save_gSel; |
| 432 | Int32 save_gMinlen; |
| 433 | Int32* save_gLimit; |
| 434 | Int32* save_gBase; |
| 435 | Int32* save_gPerm; |
| 436 | |
| 437 | } |
| 438 | DState; |
| 439 | |
| 440 | |
| 441 | |
| 442 | /*-- Macros for decompression. --*/ |
| 443 | |
| 444 | #define BZ_GET_FAST(cccc) \ |
| 445 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ |
| 446 | if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \ |
| 447 | s->tPos = s->tt[s->tPos]; \ |
| 448 | cccc = (UChar)(s->tPos & 0xff); \ |
| 449 | s->tPos >>= 8; |
| 450 | |
| 451 | #define BZ_GET_FAST_C(cccc) \ |
| 452 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ |
| 453 | if (c_tPos >= (UInt32)100000 * (UInt32)ro_blockSize100k) return True; \ |
| 454 | c_tPos = c_tt[c_tPos]; \ |
| 455 | cccc = (UChar)(c_tPos & 0xff); \ |
| 456 | c_tPos >>= 8; |
| 457 | |
| 458 | #define SET_LL4(i,n) \ |
| 459 | { if (((i) & 0x1) == 0) \ |
| 460 | s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \ |
| 461 | s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ |
| 462 | } |
| 463 | |
| 464 | #define GET_LL4(i) \ |
| 465 | ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF) |
| 466 | |
| 467 | #define SET_LL(i,n) \ |
| 468 | { s->ll16[i] = (UInt16)(n & 0x0000ffff); \ |
| 469 | SET_LL4(i, n >> 16); \ |
| 470 | } |
| 471 | |
| 472 | #define GET_LL(i) \ |
| 473 | (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16)) |
| 474 | |
| 475 | #define BZ_GET_SMALL(cccc) \ |
| 476 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ |
| 477 | if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \ |
| 478 | cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \ |
| 479 | s->tPos = GET_LL(s->tPos); |
| 480 | |
| 481 | |
| 482 | /*-- externs for decompression. --*/ |
| 483 | |
| 484 | extern Int32 |
| 485 | BZ2_indexIntoF ( Int32, Int32* ); |
| 486 | |
| 487 | extern Int32 |
| 488 | BZ2_decompress ( DState* ); |
| 489 | |
| 490 | extern void |
| 491 | BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*, |
| 492 | Int32, Int32, Int32 ); |
| 493 | |
| 494 | |
| 495 | #endif |
| 496 | |
| 497 | |
| 498 | /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/ |
| 499 | |
| 500 | #ifdef BZ_NO_STDIO |
| 501 | #ifndef NULL |
| 502 | #define NULL 0 |
| 503 | #endif |
| 504 | #endif |
| 505 | |
| 506 | |
| 507 | /*-------------------------------------------------------------*/ |
| 508 | /*--- end bzlib_private.h ---*/ |
| 509 | /*-------------------------------------------------------------*/ |