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