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