Chris@4: Chris@4: /*-------------------------------------------------------------*/ Chris@4: /*--- Private header file for the library. ---*/ Chris@4: /*--- bzlib_private.h ---*/ Chris@4: /*-------------------------------------------------------------*/ Chris@4: Chris@4: /* ------------------------------------------------------------------ Chris@4: This file is part of bzip2/libbzip2, a program and library for Chris@4: lossless, block-sorting data compression. Chris@4: Chris@4: bzip2/libbzip2 version 1.0.6 of 6 September 2010 Chris@4: Copyright (C) 1996-2010 Julian Seward Chris@4: Chris@4: Please read the WARNING, DISCLAIMER and PATENTS sections in the Chris@4: README file. Chris@4: Chris@4: This program is released under the terms of the license contained Chris@4: in the file LICENSE. Chris@4: ------------------------------------------------------------------ */ Chris@4: Chris@4: Chris@4: #ifndef _BZLIB_PRIVATE_H Chris@4: #define _BZLIB_PRIVATE_H Chris@4: Chris@4: #include Chris@4: Chris@4: #ifndef BZ_NO_STDIO Chris@4: #include Chris@4: #include Chris@4: #include Chris@4: #endif Chris@4: Chris@4: #include "bzlib.h" Chris@4: Chris@4: Chris@4: Chris@4: /*-- General stuff. --*/ Chris@4: Chris@4: #define BZ_VERSION "1.0.6, 6-Sept-2010" Chris@4: Chris@4: typedef char Char; Chris@4: typedef unsigned char Bool; Chris@4: typedef unsigned char UChar; Chris@4: typedef int Int32; Chris@4: typedef unsigned int UInt32; Chris@4: typedef short Int16; Chris@4: typedef unsigned short UInt16; Chris@4: Chris@4: #define True ((Bool)1) Chris@4: #define False ((Bool)0) Chris@4: Chris@4: #ifndef __GNUC__ Chris@4: #define __inline__ /* */ Chris@4: #endif Chris@4: Chris@4: #ifndef BZ_NO_STDIO Chris@4: Chris@4: extern void BZ2_bz__AssertH__fail ( int errcode ); Chris@4: #define AssertH(cond,errcode) \ Chris@4: { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); } Chris@4: Chris@4: #if BZ_DEBUG Chris@4: #define AssertD(cond,msg) \ Chris@4: { if (!(cond)) { \ Chris@4: fprintf ( stderr, \ Chris@4: "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\ Chris@4: exit(1); \ Chris@4: }} Chris@4: #else Chris@4: #define AssertD(cond,msg) /* */ Chris@4: #endif Chris@4: Chris@4: #define VPrintf0(zf) \ Chris@4: fprintf(stderr,zf) Chris@4: #define VPrintf1(zf,za1) \ Chris@4: fprintf(stderr,zf,za1) Chris@4: #define VPrintf2(zf,za1,za2) \ Chris@4: fprintf(stderr,zf,za1,za2) Chris@4: #define VPrintf3(zf,za1,za2,za3) \ Chris@4: fprintf(stderr,zf,za1,za2,za3) Chris@4: #define VPrintf4(zf,za1,za2,za3,za4) \ Chris@4: fprintf(stderr,zf,za1,za2,za3,za4) Chris@4: #define VPrintf5(zf,za1,za2,za3,za4,za5) \ Chris@4: fprintf(stderr,zf,za1,za2,za3,za4,za5) Chris@4: Chris@4: #else Chris@4: Chris@4: extern void bz_internal_error ( int errcode ); Chris@4: #define AssertH(cond,errcode) \ Chris@4: { if (!(cond)) bz_internal_error ( errcode ); } Chris@4: #define AssertD(cond,msg) do { } while (0) Chris@4: #define VPrintf0(zf) do { } while (0) Chris@4: #define VPrintf1(zf,za1) do { } while (0) Chris@4: #define VPrintf2(zf,za1,za2) do { } while (0) Chris@4: #define VPrintf3(zf,za1,za2,za3) do { } while (0) Chris@4: #define VPrintf4(zf,za1,za2,za3,za4) do { } while (0) Chris@4: #define VPrintf5(zf,za1,za2,za3,za4,za5) do { } while (0) Chris@4: Chris@4: #endif Chris@4: Chris@4: Chris@4: #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1) Chris@4: #define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp)) Chris@4: Chris@4: Chris@4: /*-- Header bytes. --*/ Chris@4: Chris@4: #define BZ_HDR_B 0x42 /* 'B' */ Chris@4: #define BZ_HDR_Z 0x5a /* 'Z' */ Chris@4: #define BZ_HDR_h 0x68 /* 'h' */ Chris@4: #define BZ_HDR_0 0x30 /* '0' */ Chris@4: Chris@4: /*-- Constants for the back end. --*/ Chris@4: Chris@4: #define BZ_MAX_ALPHA_SIZE 258 Chris@4: #define BZ_MAX_CODE_LEN 23 Chris@4: Chris@4: #define BZ_RUNA 0 Chris@4: #define BZ_RUNB 1 Chris@4: Chris@4: #define BZ_N_GROUPS 6 Chris@4: #define BZ_G_SIZE 50 Chris@4: #define BZ_N_ITERS 4 Chris@4: Chris@4: #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) Chris@4: Chris@4: Chris@4: Chris@4: /*-- Stuff for randomising repetitive blocks. --*/ Chris@4: Chris@4: extern Int32 BZ2_rNums[512]; Chris@4: Chris@4: #define BZ_RAND_DECLS \ Chris@4: Int32 rNToGo; \ Chris@4: Int32 rTPos \ Chris@4: Chris@4: #define BZ_RAND_INIT_MASK \ Chris@4: s->rNToGo = 0; \ Chris@4: s->rTPos = 0 \ Chris@4: Chris@4: #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0) Chris@4: Chris@4: #define BZ_RAND_UPD_MASK \ Chris@4: if (s->rNToGo == 0) { \ Chris@4: s->rNToGo = BZ2_rNums[s->rTPos]; \ Chris@4: s->rTPos++; \ Chris@4: if (s->rTPos == 512) s->rTPos = 0; \ Chris@4: } \ Chris@4: s->rNToGo--; Chris@4: Chris@4: Chris@4: Chris@4: /*-- Stuff for doing CRCs. --*/ Chris@4: Chris@4: extern UInt32 BZ2_crc32Table[256]; Chris@4: Chris@4: #define BZ_INITIALISE_CRC(crcVar) \ Chris@4: { \ Chris@4: crcVar = 0xffffffffL; \ Chris@4: } Chris@4: Chris@4: #define BZ_FINALISE_CRC(crcVar) \ Chris@4: { \ Chris@4: crcVar = ~(crcVar); \ Chris@4: } Chris@4: Chris@4: #define BZ_UPDATE_CRC(crcVar,cha) \ Chris@4: { \ Chris@4: crcVar = (crcVar << 8) ^ \ Chris@4: BZ2_crc32Table[(crcVar >> 24) ^ \ Chris@4: ((UChar)cha)]; \ Chris@4: } Chris@4: Chris@4: Chris@4: Chris@4: /*-- States and modes for compression. --*/ Chris@4: Chris@4: #define BZ_M_IDLE 1 Chris@4: #define BZ_M_RUNNING 2 Chris@4: #define BZ_M_FLUSHING 3 Chris@4: #define BZ_M_FINISHING 4 Chris@4: Chris@4: #define BZ_S_OUTPUT 1 Chris@4: #define BZ_S_INPUT 2 Chris@4: Chris@4: #define BZ_N_RADIX 2 Chris@4: #define BZ_N_QSORT 12 Chris@4: #define BZ_N_SHELL 18 Chris@4: #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2) Chris@4: Chris@4: Chris@4: Chris@4: Chris@4: /*-- Structure holding all the compression-side stuff. --*/ Chris@4: Chris@4: typedef Chris@4: struct { Chris@4: /* pointer back to the struct bz_stream */ Chris@4: bz_stream* strm; Chris@4: Chris@4: /* mode this stream is in, and whether inputting */ Chris@4: /* or outputting data */ Chris@4: Int32 mode; Chris@4: Int32 state; Chris@4: Chris@4: /* remembers avail_in when flush/finish requested */ Chris@4: UInt32 avail_in_expect; Chris@4: Chris@4: /* for doing the block sorting */ Chris@4: UInt32* arr1; Chris@4: UInt32* arr2; Chris@4: UInt32* ftab; Chris@4: Int32 origPtr; Chris@4: Chris@4: /* aliases for arr1 and arr2 */ Chris@4: UInt32* ptr; Chris@4: UChar* block; Chris@4: UInt16* mtfv; Chris@4: UChar* zbits; Chris@4: Chris@4: /* for deciding when to use the fallback sorting algorithm */ Chris@4: Int32 workFactor; Chris@4: Chris@4: /* run-length-encoding of the input */ Chris@4: UInt32 state_in_ch; Chris@4: Int32 state_in_len; Chris@4: BZ_RAND_DECLS; Chris@4: Chris@4: /* input and output limits and current posns */ Chris@4: Int32 nblock; Chris@4: Int32 nblockMAX; Chris@4: Int32 numZ; Chris@4: Int32 state_out_pos; Chris@4: Chris@4: /* map of bytes used in block */ Chris@4: Int32 nInUse; Chris@4: Bool inUse[256]; Chris@4: UChar unseqToSeq[256]; Chris@4: Chris@4: /* the buffer for bit stream creation */ Chris@4: UInt32 bsBuff; Chris@4: Int32 bsLive; Chris@4: Chris@4: /* block and combined CRCs */ Chris@4: UInt32 blockCRC; Chris@4: UInt32 combinedCRC; Chris@4: Chris@4: /* misc administratium */ Chris@4: Int32 verbosity; Chris@4: Int32 blockNo; Chris@4: Int32 blockSize100k; Chris@4: Chris@4: /* stuff for coding the MTF values */ Chris@4: Int32 nMTF; Chris@4: Int32 mtfFreq [BZ_MAX_ALPHA_SIZE]; Chris@4: UChar selector [BZ_MAX_SELECTORS]; Chris@4: UChar selectorMtf[BZ_MAX_SELECTORS]; Chris@4: Chris@4: UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; Chris@4: Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; Chris@4: Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; Chris@4: /* second dimension: only 3 needed; 4 makes index calculations faster */ Chris@4: UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4]; Chris@4: Chris@4: } Chris@4: EState; Chris@4: Chris@4: Chris@4: Chris@4: /*-- externs for compression. --*/ Chris@4: Chris@4: extern void Chris@4: BZ2_blockSort ( EState* ); Chris@4: Chris@4: extern void Chris@4: BZ2_compressBlock ( EState*, Bool ); Chris@4: Chris@4: extern void Chris@4: BZ2_bsInitWrite ( EState* ); Chris@4: Chris@4: extern void Chris@4: BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 ); Chris@4: Chris@4: extern void Chris@4: BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 ); Chris@4: Chris@4: Chris@4: Chris@4: /*-- states for decompression. --*/ Chris@4: Chris@4: #define BZ_X_IDLE 1 Chris@4: #define BZ_X_OUTPUT 2 Chris@4: Chris@4: #define BZ_X_MAGIC_1 10 Chris@4: #define BZ_X_MAGIC_2 11 Chris@4: #define BZ_X_MAGIC_3 12 Chris@4: #define BZ_X_MAGIC_4 13 Chris@4: #define BZ_X_BLKHDR_1 14 Chris@4: #define BZ_X_BLKHDR_2 15 Chris@4: #define BZ_X_BLKHDR_3 16 Chris@4: #define BZ_X_BLKHDR_4 17 Chris@4: #define BZ_X_BLKHDR_5 18 Chris@4: #define BZ_X_BLKHDR_6 19 Chris@4: #define BZ_X_BCRC_1 20 Chris@4: #define BZ_X_BCRC_2 21 Chris@4: #define BZ_X_BCRC_3 22 Chris@4: #define BZ_X_BCRC_4 23 Chris@4: #define BZ_X_RANDBIT 24 Chris@4: #define BZ_X_ORIGPTR_1 25 Chris@4: #define BZ_X_ORIGPTR_2 26 Chris@4: #define BZ_X_ORIGPTR_3 27 Chris@4: #define BZ_X_MAPPING_1 28 Chris@4: #define BZ_X_MAPPING_2 29 Chris@4: #define BZ_X_SELECTOR_1 30 Chris@4: #define BZ_X_SELECTOR_2 31 Chris@4: #define BZ_X_SELECTOR_3 32 Chris@4: #define BZ_X_CODING_1 33 Chris@4: #define BZ_X_CODING_2 34 Chris@4: #define BZ_X_CODING_3 35 Chris@4: #define BZ_X_MTF_1 36 Chris@4: #define BZ_X_MTF_2 37 Chris@4: #define BZ_X_MTF_3 38 Chris@4: #define BZ_X_MTF_4 39 Chris@4: #define BZ_X_MTF_5 40 Chris@4: #define BZ_X_MTF_6 41 Chris@4: #define BZ_X_ENDHDR_2 42 Chris@4: #define BZ_X_ENDHDR_3 43 Chris@4: #define BZ_X_ENDHDR_4 44 Chris@4: #define BZ_X_ENDHDR_5 45 Chris@4: #define BZ_X_ENDHDR_6 46 Chris@4: #define BZ_X_CCRC_1 47 Chris@4: #define BZ_X_CCRC_2 48 Chris@4: #define BZ_X_CCRC_3 49 Chris@4: #define BZ_X_CCRC_4 50 Chris@4: Chris@4: Chris@4: Chris@4: /*-- Constants for the fast MTF decoder. --*/ Chris@4: Chris@4: #define MTFA_SIZE 4096 Chris@4: #define MTFL_SIZE 16 Chris@4: Chris@4: Chris@4: Chris@4: /*-- Structure holding all the decompression-side stuff. --*/ Chris@4: Chris@4: typedef Chris@4: struct { Chris@4: /* pointer back to the struct bz_stream */ Chris@4: bz_stream* strm; Chris@4: Chris@4: /* state indicator for this stream */ Chris@4: Int32 state; Chris@4: Chris@4: /* for doing the final run-length decoding */ Chris@4: UChar state_out_ch; Chris@4: Int32 state_out_len; Chris@4: Bool blockRandomised; Chris@4: BZ_RAND_DECLS; Chris@4: Chris@4: /* the buffer for bit stream reading */ Chris@4: UInt32 bsBuff; Chris@4: Int32 bsLive; Chris@4: Chris@4: /* misc administratium */ Chris@4: Int32 blockSize100k; Chris@4: Bool smallDecompress; Chris@4: Int32 currBlockNo; Chris@4: Int32 verbosity; Chris@4: Chris@4: /* for undoing the Burrows-Wheeler transform */ Chris@4: Int32 origPtr; Chris@4: UInt32 tPos; Chris@4: Int32 k0; Chris@4: Int32 unzftab[256]; Chris@4: Int32 nblock_used; Chris@4: Int32 cftab[257]; Chris@4: Int32 cftabCopy[257]; Chris@4: Chris@4: /* for undoing the Burrows-Wheeler transform (FAST) */ Chris@4: UInt32 *tt; Chris@4: Chris@4: /* for undoing the Burrows-Wheeler transform (SMALL) */ Chris@4: UInt16 *ll16; Chris@4: UChar *ll4; Chris@4: Chris@4: /* stored and calculated CRCs */ Chris@4: UInt32 storedBlockCRC; Chris@4: UInt32 storedCombinedCRC; Chris@4: UInt32 calculatedBlockCRC; Chris@4: UInt32 calculatedCombinedCRC; Chris@4: Chris@4: /* map of bytes used in block */ Chris@4: Int32 nInUse; Chris@4: Bool inUse[256]; Chris@4: Bool inUse16[16]; Chris@4: UChar seqToUnseq[256]; Chris@4: Chris@4: /* for decoding the MTF values */ Chris@4: UChar mtfa [MTFA_SIZE]; Chris@4: Int32 mtfbase[256 / MTFL_SIZE]; Chris@4: UChar selector [BZ_MAX_SELECTORS]; Chris@4: UChar selectorMtf[BZ_MAX_SELECTORS]; Chris@4: UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; Chris@4: Chris@4: Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; Chris@4: Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; Chris@4: Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; Chris@4: Int32 minLens[BZ_N_GROUPS]; Chris@4: Chris@4: /* save area for scalars in the main decompress code */ Chris@4: Int32 save_i; Chris@4: Int32 save_j; Chris@4: Int32 save_t; Chris@4: Int32 save_alphaSize; Chris@4: Int32 save_nGroups; Chris@4: Int32 save_nSelectors; Chris@4: Int32 save_EOB; Chris@4: Int32 save_groupNo; Chris@4: Int32 save_groupPos; Chris@4: Int32 save_nextSym; Chris@4: Int32 save_nblockMAX; Chris@4: Int32 save_nblock; Chris@4: Int32 save_es; Chris@4: Int32 save_N; Chris@4: Int32 save_curr; Chris@4: Int32 save_zt; Chris@4: Int32 save_zn; Chris@4: Int32 save_zvec; Chris@4: Int32 save_zj; Chris@4: Int32 save_gSel; Chris@4: Int32 save_gMinlen; Chris@4: Int32* save_gLimit; Chris@4: Int32* save_gBase; Chris@4: Int32* save_gPerm; Chris@4: Chris@4: } Chris@4: DState; Chris@4: Chris@4: Chris@4: Chris@4: /*-- Macros for decompression. --*/ Chris@4: Chris@4: #define BZ_GET_FAST(cccc) \ Chris@4: /* c_tPos is unsigned, hence test < 0 is pointless. */ \ Chris@4: if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \ Chris@4: s->tPos = s->tt[s->tPos]; \ Chris@4: cccc = (UChar)(s->tPos & 0xff); \ Chris@4: s->tPos >>= 8; Chris@4: Chris@4: #define BZ_GET_FAST_C(cccc) \ Chris@4: /* c_tPos is unsigned, hence test < 0 is pointless. */ \ Chris@4: if (c_tPos >= (UInt32)100000 * (UInt32)ro_blockSize100k) return True; \ Chris@4: c_tPos = c_tt[c_tPos]; \ Chris@4: cccc = (UChar)(c_tPos & 0xff); \ Chris@4: c_tPos >>= 8; Chris@4: Chris@4: #define SET_LL4(i,n) \ Chris@4: { if (((i) & 0x1) == 0) \ Chris@4: s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \ Chris@4: s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ Chris@4: } Chris@4: Chris@4: #define GET_LL4(i) \ Chris@4: ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF) Chris@4: Chris@4: #define SET_LL(i,n) \ Chris@4: { s->ll16[i] = (UInt16)(n & 0x0000ffff); \ Chris@4: SET_LL4(i, n >> 16); \ Chris@4: } Chris@4: Chris@4: #define GET_LL(i) \ Chris@4: (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16)) Chris@4: Chris@4: #define BZ_GET_SMALL(cccc) \ Chris@4: /* c_tPos is unsigned, hence test < 0 is pointless. */ \ Chris@4: if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \ Chris@4: cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \ Chris@4: s->tPos = GET_LL(s->tPos); Chris@4: Chris@4: Chris@4: /*-- externs for decompression. --*/ Chris@4: Chris@4: extern Int32 Chris@4: BZ2_indexIntoF ( Int32, Int32* ); Chris@4: Chris@4: extern Int32 Chris@4: BZ2_decompress ( DState* ); Chris@4: Chris@4: extern void Chris@4: BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*, Chris@4: Int32, Int32, Int32 ); Chris@4: Chris@4: Chris@4: #endif Chris@4: Chris@4: Chris@4: /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/ Chris@4: Chris@4: #ifdef BZ_NO_STDIO Chris@4: #ifndef NULL Chris@4: #define NULL 0 Chris@4: #endif Chris@4: #endif Chris@4: Chris@4: Chris@4: /*-------------------------------------------------------------*/ Chris@4: /*--- end bzlib_private.h ---*/ Chris@4: /*-------------------------------------------------------------*/