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