You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
550 lines
14 KiB
550 lines
14 KiB
|
|
/*-------------------------------------------------------------*/
|
|
/*--- Private header file for the library. ---*/
|
|
/*--- bzlib_private.h ---*/
|
|
/*-------------------------------------------------------------*/
|
|
|
|
/*--
|
|
This file is a part of bzip2 and/or libbzip2, a program and
|
|
library for lossless, block-sorting data compression.
|
|
|
|
Copyright (C) 1996-2002 Julian R Seward. All rights reserved.
|
|
|
|
Redistribution and use in source and binary forms, with or without
|
|
modification, are permitted provided that the following conditions
|
|
are met:
|
|
|
|
1. Redistributions of source code must retain the above copyright
|
|
notice, this list of conditions and the following disclaimer.
|
|
|
|
2. The origin of this software must not be misrepresented; you must
|
|
not claim that you wrote the original software. If you use this
|
|
software in a product, an acknowledgment in the product
|
|
documentation would be appreciated but is not required.
|
|
|
|
3. Altered source versions must be plainly marked as such, and must
|
|
not be misrepresented as being the original software.
|
|
|
|
4. The name of the author may not be used to endorse or promote
|
|
products derived from this software without specific prior written
|
|
permission.
|
|
|
|
THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
|
|
OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
|
|
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
|
ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
|
|
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
|
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
|
|
GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
|
|
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
|
|
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
|
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
|
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
Julian Seward, Cambridge, UK.
|
|
[email protected]
|
|
bzip2/libbzip2 version 1.0 of 21 March 2000
|
|
|
|
This program is based on (at least) the work of:
|
|
Mike Burrows
|
|
David Wheeler
|
|
Peter Fenwick
|
|
Alistair Moffat
|
|
Radford Neal
|
|
Ian H. Witten
|
|
Robert Sedgewick
|
|
Jon L. Bentley
|
|
|
|
For more information on these sources, see the manual.
|
|
--*/
|
|
|
|
|
|
#ifndef _BZLIB_PRIVATE_H
|
|
#define _BZLIB_PRIVATE_H
|
|
|
|
#include <stdlib.h>
|
|
|
|
#ifndef BZ_NO_STDIO
|
|
#include <stdio.h>
|
|
#include <ctype.h>
|
|
#include <string.h>
|
|
#endif
|
|
|
|
#include "bzlib.h"
|
|
|
|
|
|
|
|
/*-- General stuff. --*/
|
|
|
|
#define BZ_VERSION "1.0.2, 30-Dec-2001"
|
|
|
|
typedef char Char;
|
|
typedef unsigned char Bool;
|
|
typedef unsigned char UChar;
|
|
typedef int Int32;
|
|
typedef unsigned int UInt32;
|
|
typedef short Int16;
|
|
typedef unsigned short UInt16;
|
|
|
|
#define True ((Bool)1)
|
|
#define False ((Bool)0)
|
|
|
|
#ifndef __GNUC__
|
|
#define __inline__ /* */
|
|
#endif
|
|
|
|
#ifndef BZ_NO_STDIO
|
|
extern void BZ2_bz__AssertH__fail ( int errcode );
|
|
#define AssertH(cond,errcode) \
|
|
{ if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }
|
|
#if BZ_DEBUG
|
|
#define AssertD(cond,msg) \
|
|
{ if (!(cond)) { \
|
|
fprintf ( stderr, \
|
|
"\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\
|
|
exit(1); \
|
|
}}
|
|
#else
|
|
#define AssertD(cond,msg) /* */
|
|
#endif
|
|
#define VPrintf0(zf) \
|
|
fprintf(stderr,zf)
|
|
#define VPrintf1(zf,za1) \
|
|
fprintf(stderr,zf,za1)
|
|
#define VPrintf2(zf,za1,za2) \
|
|
fprintf(stderr,zf,za1,za2)
|
|
#define VPrintf3(zf,za1,za2,za3) \
|
|
fprintf(stderr,zf,za1,za2,za3)
|
|
#define VPrintf4(zf,za1,za2,za3,za4) \
|
|
fprintf(stderr,zf,za1,za2,za3,za4)
|
|
#define VPrintf5(zf,za1,za2,za3,za4,za5) \
|
|
fprintf(stderr,zf,za1,za2,za3,za4,za5)
|
|
#else
|
|
extern void bz_internal_error ( int errcode );
|
|
#define AssertH(cond,errcode) \
|
|
{ if (!(cond)) bz_internal_error ( errcode ); }
|
|
#define AssertD(cond,msg) /* */
|
|
#define VPrintf0(zf) /* */
|
|
#define VPrintf1(zf,za1) /* */
|
|
#define VPrintf2(zf,za1,za2) /* */
|
|
#define VPrintf3(zf,za1,za2,za3) /* */
|
|
#define VPrintf4(zf,za1,za2,za3,za4) /* */
|
|
#define VPrintf5(zf,za1,za2,za3,za4,za5) /* */
|
|
#endif
|
|
|
|
|
|
#define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
|
|
#define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp))
|
|
|
|
|
|
/*-- Header bytes. --*/
|
|
|
|
#define BZ_HDR_B 0x42 /* 'B' */
|
|
#define BZ_HDR_Z 0x5a /* 'Z' */
|
|
#define BZ_HDR_h 0x68 /* 'h' */
|
|
#define BZ_HDR_0 0x30 /* '0' */
|
|
|
|
/*-- Constants for the back end. --*/
|
|
|
|
#define BZ_MAX_ALPHA_SIZE 258
|
|
#define BZ_MAX_CODE_LEN 23
|
|
|
|
#define BZ_RUNA 0
|
|
#define BZ_RUNB 1
|
|
|
|
#define BZ_N_GROUPS 6
|
|
#define BZ_G_SIZE 50
|
|
#define BZ_N_ITERS 4
|
|
|
|
#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
|
|
|
|
|
|
|
|
/*-- Stuff for randomising repetitive blocks. --*/
|
|
|
|
extern Int32 BZ2_rNums[512];
|
|
|
|
#define BZ_RAND_DECLS \
|
|
Int32 rNToGo; \
|
|
Int32 rTPos \
|
|
|
|
#define BZ_RAND_INIT_MASK \
|
|
s->rNToGo = 0; \
|
|
s->rTPos = 0 \
|
|
|
|
#define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
|
|
|
|
#define BZ_RAND_UPD_MASK \
|
|
if (s->rNToGo == 0) { \
|
|
s->rNToGo = BZ2_rNums[s->rTPos]; \
|
|
s->rTPos++; \
|
|
if (s->rTPos == 512) s->rTPos = 0; \
|
|
} \
|
|
s->rNToGo--;
|
|
|
|
|
|
|
|
/*-- Stuff for doing CRCs. --*/
|
|
|
|
extern UInt32 BZ2_crc32Table[256];
|
|
|
|
#define BZ_INITIALISE_CRC(crcVar) \
|
|
{ \
|
|
crcVar = 0xffffffffL; \
|
|
}
|
|
|
|
#define BZ_FINALISE_CRC(crcVar) \
|
|
{ \
|
|
crcVar = ~(crcVar); \
|
|
}
|
|
|
|
#define BZ_UPDATE_CRC(crcVar,cha) \
|
|
{ \
|
|
crcVar = (crcVar << 8) ^ \
|
|
BZ2_crc32Table[(crcVar >> 24) ^ \
|
|
((UChar)cha)]; \
|
|
}
|
|
|
|
|
|
|
|
/*-- States and modes for compression. --*/
|
|
|
|
#define BZ_M_IDLE 1
|
|
#define BZ_M_RUNNING 2
|
|
#define BZ_M_FLUSHING 3
|
|
#define BZ_M_FINISHING 4
|
|
|
|
#define BZ_S_OUTPUT 1
|
|
#define BZ_S_INPUT 2
|
|
|
|
#define BZ_N_RADIX 2
|
|
#define BZ_N_QSORT 12
|
|
#define BZ_N_SHELL 18
|
|
#define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
|
|
|
|
|
|
|
|
|
|
/*-- Structure holding all the compression-side stuff. --*/
|
|
|
|
typedef
|
|
struct {
|
|
/* pointer back to the struct bz_stream */
|
|
bz_stream* strm;
|
|
|
|
/* mode this stream is in, and whether inputting */
|
|
/* or outputting data */
|
|
Int32 mode;
|
|
Int32 state;
|
|
|
|
/* remembers avail_in when flush/finish requested */
|
|
UInt32 avail_in_expect;
|
|
|
|
/* for doing the block sorting */
|
|
UInt32* arr1;
|
|
UInt32* arr2;
|
|
UInt32* ftab;
|
|
Int32 origPtr;
|
|
|
|
/* aliases for arr1 and arr2 */
|
|
UInt32* ptr;
|
|
UChar* block;
|
|
UInt16* mtfv;
|
|
UChar* zbits;
|
|
|
|
/* for deciding when to use the fallback sorting algorithm */
|
|
Int32 workFactor;
|
|
|
|
/* run-length-encoding of the input */
|
|
UInt32 state_in_ch;
|
|
Int32 state_in_len;
|
|
BZ_RAND_DECLS;
|
|
|
|
/* input and output limits and current posns */
|
|
Int32 nblock;
|
|
Int32 nblockMAX;
|
|
Int32 numZ;
|
|
Int32 state_out_pos;
|
|
|
|
/* map of bytes used in block */
|
|
Int32 nInUse;
|
|
Bool inUse[256];
|
|
UChar unseqToSeq[256];
|
|
|
|
/* the buffer for bit stream creation */
|
|
UInt32 bsBuff;
|
|
Int32 bsLive;
|
|
|
|
/* block and combined CRCs */
|
|
UInt32 blockCRC;
|
|
UInt32 combinedCRC;
|
|
|
|
/* misc administratium */
|
|
Int32 verbosity;
|
|
Int32 blockNo;
|
|
Int32 blockSize100k;
|
|
|
|
/* stuff for coding the MTF values */
|
|
Int32 nMTF;
|
|
Int32 mtfFreq [BZ_MAX_ALPHA_SIZE];
|
|
UChar selector [BZ_MAX_SELECTORS];
|
|
UChar selectorMtf[BZ_MAX_SELECTORS];
|
|
|
|
UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
|
|
Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
|
|
Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
|
|
/* second dimension: only 3 needed; 4 makes index calculations faster */
|
|
UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4];
|
|
|
|
}
|
|
EState;
|
|
|
|
|
|
|
|
/*-- externs for compression. --*/
|
|
|
|
extern void
|
|
BZ2_blockSort ( EState* );
|
|
|
|
extern void
|
|
BZ2_compressBlock ( EState*, Bool );
|
|
|
|
extern void
|
|
BZ2_bsInitWrite ( EState* );
|
|
|
|
extern void
|
|
BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
|
|
|
|
extern void
|
|
BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
|
|
|
|
|
|
|
|
/*-- states for decompression. --*/
|
|
|
|
#define BZ_X_IDLE 1
|
|
#define BZ_X_OUTPUT 2
|
|
|
|
#define BZ_X_MAGIC_1 10
|
|
#define BZ_X_MAGIC_2 11
|
|
#define BZ_X_MAGIC_3 12
|
|
#define BZ_X_MAGIC_4 13
|
|
#define BZ_X_BLKHDR_1 14
|
|
#define BZ_X_BLKHDR_2 15
|
|
#define BZ_X_BLKHDR_3 16
|
|
#define BZ_X_BLKHDR_4 17
|
|
#define BZ_X_BLKHDR_5 18
|
|
#define BZ_X_BLKHDR_6 19
|
|
#define BZ_X_BCRC_1 20
|
|
#define BZ_X_BCRC_2 21
|
|
#define BZ_X_BCRC_3 22
|
|
#define BZ_X_BCRC_4 23
|
|
#define BZ_X_RANDBIT 24
|
|
#define BZ_X_ORIGPTR_1 25
|
|
#define BZ_X_ORIGPTR_2 26
|
|
#define BZ_X_ORIGPTR_3 27
|
|
#define BZ_X_MAPPING_1 28
|
|
#define BZ_X_MAPPING_2 29
|
|
#define BZ_X_SELECTOR_1 30
|
|
#define BZ_X_SELECTOR_2 31
|
|
#define BZ_X_SELECTOR_3 32
|
|
#define BZ_X_CODING_1 33
|
|
#define BZ_X_CODING_2 34
|
|
#define BZ_X_CODING_3 35
|
|
#define BZ_X_MTF_1 36
|
|
#define BZ_X_MTF_2 37
|
|
#define BZ_X_MTF_3 38
|
|
#define BZ_X_MTF_4 39
|
|
#define BZ_X_MTF_5 40
|
|
#define BZ_X_MTF_6 41
|
|
#define BZ_X_ENDHDR_2 42
|
|
#define BZ_X_ENDHDR_3 43
|
|
#define BZ_X_ENDHDR_4 44
|
|
#define BZ_X_ENDHDR_5 45
|
|
#define BZ_X_ENDHDR_6 46
|
|
#define BZ_X_CCRC_1 47
|
|
#define BZ_X_CCRC_2 48
|
|
#define BZ_X_CCRC_3 49
|
|
#define BZ_X_CCRC_4 50
|
|
|
|
|
|
|
|
/*-- Constants for the fast MTF decoder. --*/
|
|
|
|
#define MTFA_SIZE 4096
|
|
#define MTFL_SIZE 16
|
|
|
|
|
|
|
|
/*-- Structure holding all the decompression-side stuff. --*/
|
|
|
|
typedef
|
|
struct {
|
|
/* pointer back to the struct bz_stream */
|
|
bz_stream* strm;
|
|
|
|
/* state indicator for this stream */
|
|
Int32 state;
|
|
|
|
/* for doing the final run-length decoding */
|
|
UChar state_out_ch;
|
|
Int32 state_out_len;
|
|
Bool blockRandomised;
|
|
BZ_RAND_DECLS;
|
|
|
|
/* the buffer for bit stream reading */
|
|
UInt32 bsBuff;
|
|
Int32 bsLive;
|
|
|
|
/* misc administratium */
|
|
Int32 blockSize100k;
|
|
Bool smallDecompress;
|
|
Int32 currBlockNo;
|
|
Int32 verbosity;
|
|
|
|
/* for undoing the Burrows-Wheeler transform */
|
|
Int32 origPtr;
|
|
UInt32 tPos;
|
|
Int32 k0;
|
|
Int32 unzftab[256];
|
|
Int32 nblock_used;
|
|
Int32 cftab[257];
|
|
Int32 cftabCopy[257];
|
|
|
|
/* for undoing the Burrows-Wheeler transform (FAST) */
|
|
UInt32 *tt;
|
|
|
|
/* for undoing the Burrows-Wheeler transform (SMALL) */
|
|
UInt16 *ll16;
|
|
UChar *ll4;
|
|
|
|
/* stored and calculated CRCs */
|
|
UInt32 storedBlockCRC;
|
|
UInt32 storedCombinedCRC;
|
|
UInt32 calculatedBlockCRC;
|
|
UInt32 calculatedCombinedCRC;
|
|
|
|
/* map of bytes used in block */
|
|
Int32 nInUse;
|
|
Bool inUse[256];
|
|
Bool inUse16[16];
|
|
UChar seqToUnseq[256];
|
|
|
|
/* for decoding the MTF values */
|
|
UChar mtfa [MTFA_SIZE];
|
|
Int32 mtfbase[256 / MTFL_SIZE];
|
|
UChar selector [BZ_MAX_SELECTORS];
|
|
UChar selectorMtf[BZ_MAX_SELECTORS];
|
|
UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
|
|
|
|
Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
|
|
Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
|
|
Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
|
|
Int32 minLens[BZ_N_GROUPS];
|
|
|
|
/* save area for scalars in the main decompress code */
|
|
Int32 save_i;
|
|
Int32 save_j;
|
|
Int32 save_t;
|
|
Int32 save_alphaSize;
|
|
Int32 save_nGroups;
|
|
Int32 save_nSelectors;
|
|
Int32 save_EOB;
|
|
Int32 save_groupNo;
|
|
Int32 save_groupPos;
|
|
Int32 save_nextSym;
|
|
Int32 save_nblockMAX;
|
|
Int32 save_nblock;
|
|
Int32 save_es;
|
|
Int32 save_N;
|
|
Int32 save_curr;
|
|
Int32 save_zt;
|
|
Int32 save_zn;
|
|
Int32 save_zvec;
|
|
Int32 save_zj;
|
|
Int32 save_gSel;
|
|
Int32 save_gMinlen;
|
|
Int32* save_gLimit;
|
|
Int32* save_gBase;
|
|
Int32* save_gPerm;
|
|
|
|
}
|
|
DState;
|
|
|
|
|
|
|
|
/*-- Macros for decompression. --*/
|
|
|
|
#define BZ_GET_FAST(cccc) \
|
|
s->tPos = s->tt[s->tPos]; \
|
|
cccc = (UChar)(s->tPos & 0xff); \
|
|
s->tPos >>= 8;
|
|
|
|
#define BZ_GET_FAST_C(cccc) \
|
|
c_tPos = c_tt[c_tPos]; \
|
|
cccc = (UChar)(c_tPos & 0xff); \
|
|
c_tPos >>= 8;
|
|
|
|
#define SET_LL4(i,n) \
|
|
{ if (((i) & 0x1) == 0) \
|
|
s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \
|
|
s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \
|
|
}
|
|
|
|
#define GET_LL4(i) \
|
|
((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
|
|
|
|
#define SET_LL(i,n) \
|
|
{ s->ll16[i] = (UInt16)(n & 0x0000ffff); \
|
|
SET_LL4(i, n >> 16); \
|
|
}
|
|
|
|
#define GET_LL(i) \
|
|
(((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
|
|
|
|
#define BZ_GET_SMALL(cccc) \
|
|
cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \
|
|
s->tPos = GET_LL(s->tPos);
|
|
|
|
|
|
/*-- externs for decompression. --*/
|
|
|
|
extern Int32
|
|
BZ2_indexIntoF ( Int32, Int32* );
|
|
|
|
extern Int32
|
|
BZ2_decompress ( DState* );
|
|
|
|
extern void
|
|
BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
|
|
Int32, Int32, Int32 );
|
|
|
|
|
|
#endif
|
|
|
|
|
|
/*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
|
|
|
|
#ifdef BZ_NO_STDIO
|
|
#ifndef NULL
|
|
#define NULL 0
|
|
#endif
|
|
#endif
|
|
|
|
|
|
// turn off some compiler warnings - imported from tier0/platform.h
|
|
|
|
#ifdef _MSC_VER
|
|
#pragma warning(disable : 4127) // warning C4127: conditional expression is constant
|
|
#pragma warning(disable : 4702) // warning C4702: unreachable code
|
|
#pragma warning(disable : 4244) // type conversion warning.
|
|
#pragma warning(disable : 4100) // warning C4100: 'hwnd' : unreferenced formal parameter
|
|
#pragma warning( disable : 4267 ) // conversion from 'size_t' to 'int', possible loss of data
|
|
#endif
|
|
|
|
// We use this Valve func as an optimization:
|
|
extern int V_isspace(int c);
|
|
|
|
/*-------------------------------------------------------------*/
|
|
/*--- end bzlib_private.h ---*/
|
|
/*-------------------------------------------------------------*/
|