bzlib_private.h Source File

00001 
00002 /*-------------------------------------------------------------*/
00003 /*--- Private header file for the library.                  ---*/
00004 /*---                                       bzlib_private.h ---*/
00005 /*-------------------------------------------------------------*/
00006 
00007 /*--
00008   This file is a part of bzip2 and/or libbzip2, a program and
00009   library for lossless, block-sorting data compression.
00010 
00011   Copyright (C) 1996-1999 Julian R Seward.  All rights reserved.
00012 
00013   Redistribution and use in source and binary forms, with or without
00014   modification, are permitted provided that the following conditions
00015   are met:
00016 
00017   1. Redistributions of source code must retain the above copyright
00018      notice, this list of conditions and the following disclaimer.
00019 
00020   2. The origin of this software must not be misrepresented; you must 
00021      not claim that you wrote the original software.  If you use this 
00022      software in a product, an acknowledgment in the product 
00023      documentation would be appreciated but is not required.
00024 
00025   3. Altered source versions must be plainly marked as such, and must
00026      not be misrepresented as being the original software.
00027 
00028   4. The name of the author may not be used to endorse or promote 
00029      products derived from this software without specific prior written 
00030      permission.
00031 
00032   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
00033   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00034   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00035   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
00036   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00037   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
00038   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00039   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
00040   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00041   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00042   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00043 
00044   Julian Seward, Cambridge, UK.
00045   jseward@acm.org
00046   bzip2/libbzip2 version 0.9.5 of 24 May 1999
00047 
00048   This program is based on (at least) the work of:
00049      Mike Burrows
00050      David Wheeler
00051      Peter Fenwick
00052      Alistair Moffat
00053      Radford Neal
00054      Ian H. Witten
00055      Robert Sedgewick
00056      Jon L. Bentley
00057 
00058   For more information on these sources, see the manual.
00059 --*/
00060 
00061 
00062 #ifndef _BZLIB_PRIVATE_H
00063 #define _BZLIB_PRIVATE_H
00064 
00065 #include <stdlib.h>
00066 
00067 #ifndef BZ_NO_STDIO
00068 #include <stdio.h>
00069 #include <ctype.h>
00070 #include <string.h>
00071 #endif
00072 
00073 #include "bzlib.h"
00074 
00075 
00076 
00077 /*-- General stuff. --*/
00078 
00079 #define BZ_VERSION  "0.9.5a"
00080 
00081 typedef char            Char;
00082 typedef unsigned char   Bool;
00083 typedef unsigned char   UChar;
00084 typedef int             Int32;
00085 typedef unsigned int    UInt32;
00086 typedef short           Int16;
00087 typedef unsigned short  UInt16;
00088 
00089 #define True  ((Bool)1)
00090 #define False ((Bool)0)
00091 
00092 #ifndef __GNUC__
00093 #define __inline__  /* */
00094 #endif 
00095 
00096 #ifndef BZ_NO_STDIO
00097 extern void bz__AssertH__fail ( int errcode );
00098 #define AssertH(cond,errcode) \
00099    { if (!(cond)) bz__AssertH__fail ( errcode ); }
00100 #if BZ_DEBUG
00101 #define AssertD(cond,msg) \
00102    { if (!(cond)) {       \
00103       fprintf ( stderr,   \
00104         "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\
00105       exit(1); \
00106    }}
00107 #else
00108 #define AssertD(cond,msg) /* */
00109 #endif
00110 #define VPrintf0(zf) \
00111    fprintf(stderr,zf)
00112 #define VPrintf1(zf,za1) \
00113    fprintf(stderr,zf,za1)
00114 #define VPrintf2(zf,za1,za2) \
00115    fprintf(stderr,zf,za1,za2)
00116 #define VPrintf3(zf,za1,za2,za3) \
00117    fprintf(stderr,zf,za1,za2,za3)
00118 #define VPrintf4(zf,za1,za2,za3,za4) \
00119    fprintf(stderr,zf,za1,za2,za3,za4)
00120 #define VPrintf5(zf,za1,za2,za3,za4,za5) \
00121    fprintf(stderr,zf,za1,za2,za3,za4,za5)
00122 #else
00123 extern void bz_internal_error ( int errcode );
00124 #define AssertH(cond,errcode) \
00125    { if (!(cond)) bz_internal_error ( errcode ); }
00126 #define AssertD(cond,msg) /* */
00127 #define VPrintf0(zf) /* */
00128 #define VPrintf1(zf,za1) /* */
00129 #define VPrintf2(zf,za1,za2) /* */
00130 #define VPrintf3(zf,za1,za2,za3) /* */
00131 #define VPrintf4(zf,za1,za2,za3,za4) /* */
00132 #define VPrintf5(zf,za1,za2,za3,za4,za5) /* */
00133 #endif
00134 
00135 
00136 #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
00137 #define BZFREE(ppp)  (strm->bzfree)(strm->opaque,(ppp))
00138 
00139 
00140 /*-- Constants for the back end. --*/
00141 
00142 #define BZ_MAX_ALPHA_SIZE 258
00143 #define BZ_MAX_CODE_LEN    23
00144 
00145 #define BZ_RUNA 0
00146 #define BZ_RUNB 1
00147 
00148 #define BZ_N_GROUPS 6
00149 #define BZ_G_SIZE   50
00150 #define BZ_N_ITERS  4
00151 
00152 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
00153 
00154 
00155 
00156 /*-- Stuff for randomising repetitive blocks. --*/
00157 
00158 extern Int32 rNums[512];
00159 
00160 #define BZ_RAND_DECLS                          \
00161    Int32 rNToGo;                               \
00162    Int32 rTPos                                 \
00163 
00164 #define BZ_RAND_INIT_MASK                      \
00165    s->rNToGo = 0;                              \
00166    s->rTPos  = 0                               \
00167 
00168 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
00169 
00170 #define BZ_RAND_UPD_MASK                       \
00171    if (s->rNToGo == 0) {                       \
00172       s->rNToGo = rNums[s->rTPos];             \
00173       s->rTPos++;                              \
00174       if (s->rTPos == 512) s->rTPos = 0;       \
00175    }                                           \
00176    s->rNToGo--;
00177 
00178 
00179 
00180 /*-- Stuff for doing CRCs. --*/
00181 
00182 extern UInt32 crc32Table[256];
00183 
00184 #define BZ_INITIALISE_CRC(crcVar)              \
00185 {                                              \
00186    crcVar = 0xffffffffL;                       \
00187 }
00188 
00189 #define BZ_FINALISE_CRC(crcVar)                \
00190 {                                              \
00191    crcVar = ~(crcVar);                         \
00192 }
00193 
00194 #define BZ_UPDATE_CRC(crcVar,cha)              \
00195 {                                              \
00196    crcVar = (crcVar << 8) ^                    \
00197             crc32Table[(crcVar >> 24) ^        \
00198                        ((UChar)cha)];          \
00199 }
00200 
00201 
00202 
00203 /*-- States and modes for compression. --*/
00204 
00205 #define BZ_M_IDLE      1
00206 #define BZ_M_RUNNING   2
00207 #define BZ_M_FLUSHING  3
00208 #define BZ_M_FINISHING 4
00209 
00210 #define BZ_S_OUTPUT    1
00211 #define BZ_S_INPUT     2
00212 
00213 #define BZ_N_RADIX 2
00214 #define BZ_N_QSORT 12
00215 #define BZ_N_SHELL 18
00216 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
00217 
00218 
00219 
00220 
00221 /*-- Structure holding all the compression-side stuff. --*/
00222 
00223 typedef
00224    struct {
00225       /* pointer back to the struct bz_stream */
00226       bz_stream* strm;
00227 
00228       /* mode this stream is in, and whether inputting */
00229       /* or outputting data */
00230       Int32    mode;
00231       Int32    state;
00232 
00233       /* remembers avail_in when flush/finish requested */
00234       UInt32   avail_in_expect;
00235 
00236       /* for doing the block sorting */
00237       UInt32*  arr1;
00238       UInt32*  arr2;
00239       UInt32*  ftab;
00240       Int32    origPtr;
00241 
00242       /* aliases for arr1 and arr2 */
00243       UInt32*  ptr;
00244       UInt16*  block;
00245       UInt16*  mtfv;
00246       UChar*   zbits;
00247 
00248       /* for deciding when to use the fallback sorting algorithm */
00249       Int32    workFactor;
00250 
00251       /* run-length-encoding of the input */
00252       UInt32   state_in_ch;
00253       Int32    state_in_len;
00254       BZ_RAND_DECLS;
00255 
00256       /* input and output limits and current posns */
00257       Int32    nblock;
00258       Int32    nblockMAX;
00259       Int32    numZ;
00260       Int32    state_out_pos;
00261 
00262       /* map of bytes used in block */
00263       Int32    nInUse;
00264       Bool     inUse[256];
00265       UChar    unseqToSeq[256];
00266 
00267       /* the buffer for bit stream creation */
00268       UInt32   bsBuff;
00269       Int32    bsLive;
00270 
00271       /* block and combined CRCs */
00272       UInt32   blockCRC;
00273       UInt32   combinedCRC;
00274 
00275       /* misc administratium */
00276       Int32    verbosity;
00277       Int32    blockNo;
00278       Int32    blockSize100k;
00279 
00280       /* stuff for coding the MTF values */
00281       Int32    nMTF;
00282       Int32    mtfFreq    [BZ_MAX_ALPHA_SIZE];
00283       UChar    selector   [BZ_MAX_SELECTORS];
00284       UChar    selectorMtf[BZ_MAX_SELECTORS];
00285 
00286       UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00287       Int32    code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00288       Int32    rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00289 
00290    }
00291    EState;
00292 
00293 
00294 
00295 /*-- externs for compression. --*/
00296 
00297 extern void 
00298 blockSort ( EState* );
00299 
00300 extern void 
00301 compressBlock ( EState*, Bool );
00302 
00303 extern void 
00304 bsInitWrite ( EState* );
00305 
00306 extern void 
00307 hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
00308 
00309 extern void 
00310 hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
00311 
00312 
00313 
00314 /*-- states for decompression. --*/
00315 
00316 #define BZ_X_IDLE        1
00317 #define BZ_X_OUTPUT      2
00318 
00319 #define BZ_X_MAGIC_1     10
00320 #define BZ_X_MAGIC_2     11
00321 #define BZ_X_MAGIC_3     12
00322 #define BZ_X_MAGIC_4     13
00323 #define BZ_X_BLKHDR_1    14
00324 #define BZ_X_BLKHDR_2    15
00325 #define BZ_X_BLKHDR_3    16
00326 #define BZ_X_BLKHDR_4    17
00327 #define BZ_X_BLKHDR_5    18
00328 #define BZ_X_BLKHDR_6    19
00329 #define BZ_X_BCRC_1      20
00330 #define BZ_X_BCRC_2      21
00331 #define BZ_X_BCRC_3      22
00332 #define BZ_X_BCRC_4      23
00333 #define BZ_X_RANDBIT     24
00334 #define BZ_X_ORIGPTR_1   25
00335 #define BZ_X_ORIGPTR_2   26
00336 #define BZ_X_ORIGPTR_3   27
00337 #define BZ_X_MAPPING_1   28
00338 #define BZ_X_MAPPING_2   29
00339 #define BZ_X_SELECTOR_1  30
00340 #define BZ_X_SELECTOR_2  31
00341 #define BZ_X_SELECTOR_3  32
00342 #define BZ_X_CODING_1    33
00343 #define BZ_X_CODING_2    34
00344 #define BZ_X_CODING_3    35
00345 #define BZ_X_MTF_1       36
00346 #define BZ_X_MTF_2       37
00347 #define BZ_X_MTF_3       38
00348 #define BZ_X_MTF_4       39
00349 #define BZ_X_MTF_5       40
00350 #define BZ_X_MTF_6       41
00351 #define BZ_X_ENDHDR_2    42
00352 #define BZ_X_ENDHDR_3    43
00353 #define BZ_X_ENDHDR_4    44
00354 #define BZ_X_ENDHDR_5    45
00355 #define BZ_X_ENDHDR_6    46
00356 #define BZ_X_CCRC_1      47
00357 #define BZ_X_CCRC_2      48
00358 #define BZ_X_CCRC_3      49
00359 #define BZ_X_CCRC_4      50
00360 
00361 
00362 
00363 /*-- Constants for the fast MTF decoder. --*/
00364 
00365 #define MTFA_SIZE 4096
00366 #define MTFL_SIZE 16
00367 
00368 
00369 
00370 /*-- Structure holding all the decompression-side stuff. --*/
00371 
00372 typedef
00373    struct {
00374       /* pointer back to the struct bz_stream */
00375       bz_stream* strm;
00376 
00377       /* state indicator for this stream */
00378       Int32    state;
00379 
00380       /* for doing the final run-length decoding */
00381       UChar    state_out_ch;
00382       Int32    state_out_len;
00383       Bool     blockRandomised;
00384       BZ_RAND_DECLS;
00385 
00386       /* the buffer for bit stream reading */
00387       UInt32   bsBuff;
00388       Int32    bsLive;
00389 
00390       /* misc administratium */
00391       Int32    blockSize100k;
00392       Bool     smallDecompress;
00393       Int32    currBlockNo;
00394       Int32    verbosity;
00395 
00396       /* for undoing the Burrows-Wheeler transform */
00397       Int32    origPtr;
00398       UInt32   tPos;
00399       Int32    k0;
00400       Int32    unzftab[256];
00401       Int32    nblock_used;
00402       Int32    cftab[257];
00403       Int32    cftabCopy[257];
00404 
00405       /* for undoing the Burrows-Wheeler transform (FAST) */
00406       UInt32   *tt;
00407 
00408       /* for undoing the Burrows-Wheeler transform (SMALL) */
00409       UInt16   *ll16;
00410       UChar    *ll4;
00411 
00412       /* stored and calculated CRCs */
00413       UInt32   storedBlockCRC;
00414       UInt32   storedCombinedCRC;
00415       UInt32   calculatedBlockCRC;
00416       UInt32   calculatedCombinedCRC;
00417 
00418       /* map of bytes used in block */
00419       Int32    nInUse;
00420       Bool     inUse[256];
00421       Bool     inUse16[16];
00422       UChar    seqToUnseq[256];
00423 
00424       /* for decoding the MTF values */
00425       UChar    mtfa   [MTFA_SIZE];
00426       Int32    mtfbase[256 / MTFL_SIZE];
00427       UChar    selector   [BZ_MAX_SELECTORS];
00428       UChar    selectorMtf[BZ_MAX_SELECTORS];
00429       UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00430 
00431       Int32    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00432       Int32    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00433       Int32    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00434       Int32    minLens[BZ_N_GROUPS];
00435 
00436       /* save area for scalars in the main decompress code */
00437       Int32    save_i;
00438       Int32    save_j;
00439       Int32    save_t;
00440       Int32    save_alphaSize;
00441       Int32    save_nGroups;
00442       Int32    save_nSelectors;
00443       Int32    save_EOB;
00444       Int32    save_groupNo;
00445       Int32    save_groupPos;
00446       Int32    save_nextSym;
00447       Int32    save_nblockMAX;
00448       Int32    save_nblock;
00449       Int32    save_es;
00450       Int32    save_N;
00451       Int32    save_curr;
00452       Int32    save_zt;
00453       Int32    save_zn; 
00454       Int32    save_zvec;
00455       Int32    save_zj;
00456       Int32    save_gSel;
00457       Int32    save_gMinlen;
00458       Int32*   save_gLimit;
00459       Int32*   save_gBase;
00460       Int32*   save_gPerm;
00461 
00462    }
00463    DState;
00464 
00465 
00466 
00467 /*-- Macros for decompression. --*/
00468 
00469 #define BZ_GET_FAST(cccc)                     \
00470     s->tPos = s->tt[s->tPos];                 \
00471     cccc = (UChar)(s->tPos & 0xff);           \
00472     s->tPos >>= 8;
00473 
00474 #define BZ_GET_FAST_C(cccc)                   \
00475     c_tPos = c_tt[c_tPos];                    \
00476     cccc = (UChar)(c_tPos & 0xff);            \
00477     c_tPos >>= 8;
00478 
00479 #define SET_LL4(i,n)                                          \
00480    { if (((i) & 0x1) == 0)                                    \
00481         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
00482         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
00483    }
00484 
00485 #define GET_LL4(i)                             \
00486    ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
00487 
00488 #define SET_LL(i,n)                          \
00489    { s->ll16[i] = (UInt16)(n & 0x0000ffff);  \
00490      SET_LL4(i, n >> 16);                    \
00491    }
00492 
00493 #define GET_LL(i) \
00494    (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
00495 
00496 #define BZ_GET_SMALL(cccc)                        \
00497       cccc = indexIntoF ( s->tPos, s->cftab );    \
00498       s->tPos = GET_LL(s->tPos);
00499 
00500 
00501 /*-- externs for decompression. --*/
00502 
00503 extern Int32 
00504 indexIntoF ( Int32, Int32* );
00505 
00506 extern Int32 
00507 decompress ( DState* );
00508 
00509 extern void 
00510 hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
00511                        Int32,  Int32, Int32 );
00512 
00513 
00514 #endif
00515 
00516 
00517 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
00518 
00519 #ifdef BZ_NO_STDIO
00520 #ifndef NULL
00521 #define NULL 0
00522 #endif
00523 #endif
00524 
00525 
00526 /*-------------------------------------------------------------*/
00527 /*--- end                                   bzlib_private.h ---*/
00528 /*-------------------------------------------------------------*/