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