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