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 11 bzip2/libbzip2 version 1.0.6 of 6 September 2010 12 Copyright (C) 1996-2010 Julian Seward <jseward (at) bzip.org> 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 39 #define BZ_VERSION "1.0.6, 6-Sept-2010" 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 /*-------------------------------------------------------------*/ 510
