Back to index

lightning-sunbird  0.9+nobinonly
bzlib_private.h
Go to the documentation of this 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-2005 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@bzip.org
00046   bzip2/libbzip2 version 1.0 of 21 March 2000
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  "1.0.3, 15-Feb-2005"
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 BZ2_bz__AssertH__fail ( int errcode );
00098 #define AssertH(cond,errcode) \
00099    { if (!(cond)) BZ2_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 /*-- Header bytes. --*/
00141 
00142 #define BZ_HDR_B 0x42   /* 'B' */
00143 #define BZ_HDR_Z 0x5a   /* 'Z' */
00144 #define BZ_HDR_h 0x68   /* 'h' */
00145 #define BZ_HDR_0 0x30   /* '0' */
00146   
00147 /*-- Constants for the back end. --*/
00148 
00149 #define BZ_MAX_ALPHA_SIZE 258
00150 #define BZ_MAX_CODE_LEN    23
00151 
00152 #define BZ_RUNA 0
00153 #define BZ_RUNB 1
00154 
00155 #define BZ_N_GROUPS 6
00156 #define BZ_G_SIZE   50
00157 #define BZ_N_ITERS  4
00158 
00159 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
00160 
00161 
00162 
00163 /*-- Stuff for randomising repetitive blocks. --*/
00164 
00165 extern Int32 BZ2_rNums[512];
00166 
00167 #define BZ_RAND_DECLS                          \
00168    Int32 rNToGo;                               \
00169    Int32 rTPos                                 \
00170 
00171 #define BZ_RAND_INIT_MASK                      \
00172    s->rNToGo = 0;                              \
00173    s->rTPos  = 0                               \
00174 
00175 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
00176 
00177 #define BZ_RAND_UPD_MASK                       \
00178    if (s->rNToGo == 0) {                       \
00179       s->rNToGo = BZ2_rNums[s->rTPos];         \
00180       s->rTPos++;                              \
00181       if (s->rTPos == 512) s->rTPos = 0;       \
00182    }                                           \
00183    s->rNToGo--;
00184 
00185 
00186 
00187 /*-- Stuff for doing CRCs. --*/
00188 
00189 extern UInt32 BZ2_crc32Table[256];
00190 
00191 #define BZ_INITIALISE_CRC(crcVar)              \
00192 {                                              \
00193    crcVar = 0xffffffffL;                       \
00194 }
00195 
00196 #define BZ_FINALISE_CRC(crcVar)                \
00197 {                                              \
00198    crcVar = ~(crcVar);                         \
00199 }
00200 
00201 #define BZ_UPDATE_CRC(crcVar,cha)              \
00202 {                                              \
00203    crcVar = (crcVar << 8) ^                    \
00204             BZ2_crc32Table[(crcVar >> 24) ^    \
00205                            ((UChar)cha)];      \
00206 }
00207 
00208 
00209 
00210 /*-- States and modes for compression. --*/
00211 
00212 #define BZ_M_IDLE      1
00213 #define BZ_M_RUNNING   2
00214 #define BZ_M_FLUSHING  3
00215 #define BZ_M_FINISHING 4
00216 
00217 #define BZ_S_OUTPUT    1
00218 #define BZ_S_INPUT     2
00219 
00220 #define BZ_N_RADIX 2
00221 #define BZ_N_QSORT 12
00222 #define BZ_N_SHELL 18
00223 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
00224 
00225 
00226 
00227 
00228 /*-- Structure holding all the compression-side stuff. --*/
00229 
00230 typedef
00231    struct {
00232       /* pointer back to the struct bz_stream */
00233       bz_stream* strm;
00234 
00235       /* mode this stream is in, and whether inputting */
00236       /* or outputting data */
00237       Int32    mode;
00238       Int32    state;
00239 
00240       /* remembers avail_in when flush/finish requested */
00241       UInt32   avail_in_expect;
00242 
00243       /* for doing the block sorting */
00244       UInt32*  arr1;
00245       UInt32*  arr2;
00246       UInt32*  ftab;
00247       Int32    origPtr;
00248 
00249       /* aliases for arr1 and arr2 */
00250       UInt32*  ptr;
00251       UChar*   block;
00252       UInt16*  mtfv;
00253       UChar*   zbits;
00254 
00255       /* for deciding when to use the fallback sorting algorithm */
00256       Int32    workFactor;
00257 
00258       /* run-length-encoding of the input */
00259       UInt32   state_in_ch;
00260       Int32    state_in_len;
00261       BZ_RAND_DECLS;
00262 
00263       /* input and output limits and current posns */
00264       Int32    nblock;
00265       Int32    nblockMAX;
00266       Int32    numZ;
00267       Int32    state_out_pos;
00268 
00269       /* map of bytes used in block */
00270       Int32    nInUse;
00271       Bool     inUse[256];
00272       UChar    unseqToSeq[256];
00273 
00274       /* the buffer for bit stream creation */
00275       UInt32   bsBuff;
00276       Int32    bsLive;
00277 
00278       /* block and combined CRCs */
00279       UInt32   blockCRC;
00280       UInt32   combinedCRC;
00281 
00282       /* misc administratium */
00283       Int32    verbosity;
00284       Int32    blockNo;
00285       Int32    blockSize100k;
00286 
00287       /* stuff for coding the MTF values */
00288       Int32    nMTF;
00289       Int32    mtfFreq    [BZ_MAX_ALPHA_SIZE];
00290       UChar    selector   [BZ_MAX_SELECTORS];
00291       UChar    selectorMtf[BZ_MAX_SELECTORS];
00292 
00293       UChar    len     [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00294       Int32    code    [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00295       Int32    rfreq   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00296       /* second dimension: only 3 needed; 4 makes index calculations faster */
00297       UInt32   len_pack[BZ_MAX_ALPHA_SIZE][4];
00298 
00299    }
00300    EState;
00301 
00302 
00303 
00304 /*-- externs for compression. --*/
00305 
00306 extern void 
00307 BZ2_blockSort ( EState* );
00308 
00309 extern void 
00310 BZ2_compressBlock ( EState*, Bool );
00311 
00312 extern void 
00313 BZ2_bsInitWrite ( EState* );
00314 
00315 extern void 
00316 BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
00317 
00318 extern void 
00319 BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
00320 
00321 
00322 
00323 /*-- states for decompression. --*/
00324 
00325 #define BZ_X_IDLE        1
00326 #define BZ_X_OUTPUT      2
00327 
00328 #define BZ_X_MAGIC_1     10
00329 #define BZ_X_MAGIC_2     11
00330 #define BZ_X_MAGIC_3     12
00331 #define BZ_X_MAGIC_4     13
00332 #define BZ_X_BLKHDR_1    14
00333 #define BZ_X_BLKHDR_2    15
00334 #define BZ_X_BLKHDR_3    16
00335 #define BZ_X_BLKHDR_4    17
00336 #define BZ_X_BLKHDR_5    18
00337 #define BZ_X_BLKHDR_6    19
00338 #define BZ_X_BCRC_1      20
00339 #define BZ_X_BCRC_2      21
00340 #define BZ_X_BCRC_3      22
00341 #define BZ_X_BCRC_4      23
00342 #define BZ_X_RANDBIT     24
00343 #define BZ_X_ORIGPTR_1   25
00344 #define BZ_X_ORIGPTR_2   26
00345 #define BZ_X_ORIGPTR_3   27
00346 #define BZ_X_MAPPING_1   28
00347 #define BZ_X_MAPPING_2   29
00348 #define BZ_X_SELECTOR_1  30
00349 #define BZ_X_SELECTOR_2  31
00350 #define BZ_X_SELECTOR_3  32
00351 #define BZ_X_CODING_1    33
00352 #define BZ_X_CODING_2    34
00353 #define BZ_X_CODING_3    35
00354 #define BZ_X_MTF_1       36
00355 #define BZ_X_MTF_2       37
00356 #define BZ_X_MTF_3       38
00357 #define BZ_X_MTF_4       39
00358 #define BZ_X_MTF_5       40
00359 #define BZ_X_MTF_6       41
00360 #define BZ_X_ENDHDR_2    42
00361 #define BZ_X_ENDHDR_3    43
00362 #define BZ_X_ENDHDR_4    44
00363 #define BZ_X_ENDHDR_5    45
00364 #define BZ_X_ENDHDR_6    46
00365 #define BZ_X_CCRC_1      47
00366 #define BZ_X_CCRC_2      48
00367 #define BZ_X_CCRC_3      49
00368 #define BZ_X_CCRC_4      50
00369 
00370 
00371 
00372 /*-- Constants for the fast MTF decoder. --*/
00373 
00374 #define MTFA_SIZE 4096
00375 #define MTFL_SIZE 16
00376 
00377 
00378 
00379 /*-- Structure holding all the decompression-side stuff. --*/
00380 
00381 typedef
00382    struct {
00383       /* pointer back to the struct bz_stream */
00384       bz_stream* strm;
00385 
00386       /* state indicator for this stream */
00387       Int32    state;
00388 
00389       /* for doing the final run-length decoding */
00390       UChar    state_out_ch;
00391       Int32    state_out_len;
00392       Bool     blockRandomised;
00393       BZ_RAND_DECLS;
00394 
00395       /* the buffer for bit stream reading */
00396       UInt32   bsBuff;
00397       Int32    bsLive;
00398 
00399       /* misc administratium */
00400       Int32    blockSize100k;
00401       Bool     smallDecompress;
00402       Int32    currBlockNo;
00403       Int32    verbosity;
00404 
00405       /* for undoing the Burrows-Wheeler transform */
00406       Int32    origPtr;
00407       UInt32   tPos;
00408       Int32    k0;
00409       Int32    unzftab[256];
00410       Int32    nblock_used;
00411       Int32    cftab[257];
00412       Int32    cftabCopy[257];
00413 
00414       /* for undoing the Burrows-Wheeler transform (FAST) */
00415       UInt32   *tt;
00416 
00417       /* for undoing the Burrows-Wheeler transform (SMALL) */
00418       UInt16   *ll16;
00419       UChar    *ll4;
00420 
00421       /* stored and calculated CRCs */
00422       UInt32   storedBlockCRC;
00423       UInt32   storedCombinedCRC;
00424       UInt32   calculatedBlockCRC;
00425       UInt32   calculatedCombinedCRC;
00426 
00427       /* map of bytes used in block */
00428       Int32    nInUse;
00429       Bool     inUse[256];
00430       Bool     inUse16[16];
00431       UChar    seqToUnseq[256];
00432 
00433       /* for decoding the MTF values */
00434       UChar    mtfa   [MTFA_SIZE];
00435       Int32    mtfbase[256 / MTFL_SIZE];
00436       UChar    selector   [BZ_MAX_SELECTORS];
00437       UChar    selectorMtf[BZ_MAX_SELECTORS];
00438       UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00439 
00440       Int32    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00441       Int32    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00442       Int32    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00443       Int32    minLens[BZ_N_GROUPS];
00444 
00445       /* save area for scalars in the main decompress code */
00446       Int32    save_i;
00447       Int32    save_j;
00448       Int32    save_t;
00449       Int32    save_alphaSize;
00450       Int32    save_nGroups;
00451       Int32    save_nSelectors;
00452       Int32    save_EOB;
00453       Int32    save_groupNo;
00454       Int32    save_groupPos;
00455       Int32    save_nextSym;
00456       Int32    save_nblockMAX;
00457       Int32    save_nblock;
00458       Int32    save_es;
00459       Int32    save_N;
00460       Int32    save_curr;
00461       Int32    save_zt;
00462       Int32    save_zn; 
00463       Int32    save_zvec;
00464       Int32    save_zj;
00465       Int32    save_gSel;
00466       Int32    save_gMinlen;
00467       Int32*   save_gLimit;
00468       Int32*   save_gBase;
00469       Int32*   save_gPerm;
00470 
00471    }
00472    DState;
00473 
00474 
00475 
00476 /*-- Macros for decompression. --*/
00477 
00478 #define BZ_GET_FAST(cccc)                     \
00479     s->tPos = s->tt[s->tPos];                 \
00480     cccc = (UChar)(s->tPos & 0xff);           \
00481     s->tPos >>= 8;
00482 
00483 #define BZ_GET_FAST_C(cccc)                   \
00484     c_tPos = c_tt[c_tPos];                    \
00485     cccc = (UChar)(c_tPos & 0xff);            \
00486     c_tPos >>= 8;
00487 
00488 #define SET_LL4(i,n)                                          \
00489    { if (((i) & 0x1) == 0)                                    \
00490         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
00491         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
00492    }
00493 
00494 #define GET_LL4(i)                             \
00495    ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
00496 
00497 #define SET_LL(i,n)                          \
00498    { s->ll16[i] = (UInt16)(n & 0x0000ffff);  \
00499      SET_LL4(i, n >> 16);                    \
00500    }
00501 
00502 #define GET_LL(i) \
00503    (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
00504 
00505 #define BZ_GET_SMALL(cccc)                            \
00506       cccc = BZ2_indexIntoF ( s->tPos, s->cftab );    \
00507       s->tPos = GET_LL(s->tPos);
00508 
00509 
00510 /*-- externs for decompression. --*/
00511 
00512 extern Int32 
00513 BZ2_indexIntoF ( Int32, Int32* );
00514 
00515 extern Int32 
00516 BZ2_decompress ( DState* );
00517 
00518 extern void 
00519 BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
00520                            Int32,  Int32, Int32 );
00521 
00522 
00523 #endif
00524 
00525 
00526 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
00527 
00528 #ifdef BZ_NO_STDIO
00529 #ifndef NULL
00530 #define NULL 0
00531 #endif
00532 #endif
00533 
00534 
00535 /*-------------------------------------------------------------*/
00536 /*--- end                                   bzlib_private.h ---*/
00537 /*-------------------------------------------------------------*/