Back to index

avfs  1.0.1
bzlib_private.h
Go to the documentation of this file.
00001 /* IMPORTANT NOTE: This is not the original bzip2 distribution.
00002 
00003    The modifications are copyright (C) 2001 Miklos Szeredi
00004    <miklos@szeredi.hu>
00005 
00006    The modified software can be distributed under the same licence as
00007    the original software (see bellow).
00008 */
00009 
00010 /*-------------------------------------------------------------*/
00011 /*--- Private header file for the library.                  ---*/
00012 /*---                                       bzlib_private.h ---*/
00013 /*-------------------------------------------------------------*/
00014 
00015 /* ------------------------------------------------------------------
00016    This file is part of bzip2/libbzip2, a program and library for
00017    lossless, block-sorting data compression.
00018 
00019    bzip2/libbzip2 version 1.0.6 of 6 September 2010
00020    Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
00021 
00022    Please read the WARNING, DISCLAIMER and PATENTS sections in the 
00023    README file.
00024 
00025    This program is released under the terms of the license contained
00026    in the file LICENSE.
00027    ------------------------------------------------------------------ */
00028 
00029 
00030 #ifndef _BZLIB_PRIVATE_H
00031 #define _BZLIB_PRIVATE_H
00032 
00033 #include <stdlib.h>
00034 
00035 #ifndef BZ_NO_STDIO
00036 #include <stdio.h>
00037 #include <ctype.h>
00038 #include <string.h>
00039 #endif
00040 
00041 #include "bzlib.h"
00042 
00043 
00044 
00045 /*-- General stuff. --*/
00046 
00047 #define BZ_VERSION  "1.0.6, 6-Sept-2010"
00048 
00049 typedef char            Char;
00050 typedef unsigned char   Bool;
00051 typedef unsigned char   UChar;
00052 typedef int             Int32;
00053 typedef unsigned int    UInt32;
00054 typedef short           Int16;
00055 typedef unsigned short  UInt16;
00056 
00057 #define True  ((Bool)1)
00058 #define False ((Bool)0)
00059 
00060 #ifndef __GNUC__
00061 #define __inline__  /* */
00062 #endif 
00063 
00064 #ifndef BZ_NO_STDIO
00065 
00066 extern void BZ2_bz__AssertH__fail ( int errcode );
00067 #define AssertH(cond,errcode) \
00068    { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }
00069 
00070 #if BZ_DEBUG
00071 #define AssertD(cond,msg) \
00072    { if (!(cond)) {       \
00073       fprintf ( stderr,   \
00074         "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\
00075       exit(1); \
00076    }}
00077 #else
00078 #define AssertD(cond,msg) /* */
00079 #endif
00080 
00081 #define VPrintf0(zf) \
00082    fprintf(stderr,zf)
00083 #define VPrintf1(zf,za1) \
00084    fprintf(stderr,zf,za1)
00085 #define VPrintf2(zf,za1,za2) \
00086    fprintf(stderr,zf,za1,za2)
00087 #define VPrintf3(zf,za1,za2,za3) \
00088    fprintf(stderr,zf,za1,za2,za3)
00089 #define VPrintf4(zf,za1,za2,za3,za4) \
00090    fprintf(stderr,zf,za1,za2,za3,za4)
00091 #define VPrintf5(zf,za1,za2,za3,za4,za5) \
00092    fprintf(stderr,zf,za1,za2,za3,za4,za5)
00093 
00094 #else
00095 
00096 extern void bz_internal_error ( int errcode );
00097 #define AssertH(cond,errcode) \
00098    { if (!(cond)) bz_internal_error ( errcode ); }
00099 #define AssertD(cond,msg)                do { } while (0)
00100 #define VPrintf0(zf)                     do { } while (0)
00101 #define VPrintf1(zf,za1)                 do { } while (0)
00102 #define VPrintf2(zf,za1,za2)             do { } while (0)
00103 #define VPrintf3(zf,za1,za2,za3)         do { } while (0)
00104 #define VPrintf4(zf,za1,za2,za3,za4)     do { } while (0)
00105 #define VPrintf5(zf,za1,za2,za3,za4,za5) do { } while (0)
00106 
00107 #endif
00108 
00109 
00110 #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
00111 #define BZFREE(ppp)  (strm->bzfree)(strm->opaque,(ppp))
00112 
00113 
00114 /*-- Header bytes. --*/
00115 
00116 #define BZ_HDR_B 0x42   /* 'B' */
00117 #define BZ_HDR_Z 0x5a   /* 'Z' */
00118 #define BZ_HDR_h 0x68   /* 'h' */
00119 #define BZ_HDR_0 0x30   /* '0' */
00120   
00121 /*-- Constants for the back end. --*/
00122 
00123 #define BZ_MAX_ALPHA_SIZE 258
00124 #define BZ_MAX_CODE_LEN    23
00125 
00126 #define BZ_RUNA 0
00127 #define BZ_RUNB 1
00128 
00129 #define BZ_N_GROUPS 6
00130 #define BZ_G_SIZE   50
00131 #define BZ_N_ITERS  4
00132 
00133 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
00134 
00135 
00136 
00137 /*-- Stuff for randomising repetitive blocks. --*/
00138 
00139 extern Int32 BZ2_rNums[512];
00140 
00141 #define BZ_RAND_DECLS                          \
00142    Int32 rNToGo;                               \
00143    Int32 rTPos                                 \
00144 
00145 #define BZ_RAND_INIT_MASK                      \
00146    s->rNToGo = 0;                              \
00147    s->rTPos  = 0                               \
00148 
00149 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
00150 
00151 #define BZ_RAND_UPD_MASK                       \
00152    if (s->rNToGo == 0) {                       \
00153       s->rNToGo = BZ2_rNums[s->rTPos];         \
00154       s->rTPos++;                              \
00155       if (s->rTPos == 512) s->rTPos = 0;       \
00156    }                                           \
00157    s->rNToGo--;
00158 
00159 
00160 
00161 /*-- Stuff for doing CRCs. --*/
00162 
00163 extern UInt32 BZ2_crc32Table[256];
00164 
00165 #define BZ_INITIALISE_CRC(crcVar)              \
00166 {                                              \
00167    crcVar = 0xffffffffL;                       \
00168 }
00169 
00170 #define BZ_FINALISE_CRC(crcVar)                \
00171 {                                              \
00172    crcVar = ~(crcVar);                         \
00173 }
00174 
00175 #define BZ_UPDATE_CRC(crcVar,cha)              \
00176 {                                              \
00177    crcVar = (crcVar << 8) ^                    \
00178             BZ2_crc32Table[(crcVar >> 24) ^    \
00179                            ((UChar)cha)];      \
00180 }
00181 
00182 
00183 
00184 /*-- States and modes for compression. --*/
00185 
00186 #define BZ_M_IDLE      1
00187 #define BZ_M_RUNNING   2
00188 #define BZ_M_FLUSHING  3
00189 #define BZ_M_FINISHING 4
00190 
00191 #define BZ_S_OUTPUT    1
00192 #define BZ_S_INPUT     2
00193 
00194 #define BZ_N_RADIX 2
00195 #define BZ_N_QSORT 12
00196 #define BZ_N_SHELL 18
00197 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
00198 
00199 
00200 
00201 
00202 /*-- Structure holding all the compression-side stuff. --*/
00203 
00204 typedef
00205    struct {
00206       /* pointer back to the struct bz_stream */
00207       bz_stream* strm;
00208 
00209       /* mode this stream is in, and whether inputting */
00210       /* or outputting data */
00211       Int32    mode;
00212       Int32    state;
00213 
00214       /* remembers avail_in when flush/finish requested */
00215       UInt32   avail_in_expect;
00216 
00217       /* for doing the block sorting */
00218       UInt32*  arr1;
00219       UInt32*  arr2;
00220       UInt32*  ftab;
00221       Int32    origPtr;
00222 
00223       /* aliases for arr1 and arr2 */
00224       UInt32*  ptr;
00225       UChar*   block;
00226       UInt16*  mtfv;
00227       UChar*   zbits;
00228 
00229       /* for deciding when to use the fallback sorting algorithm */
00230       Int32    workFactor;
00231 
00232       /* run-length-encoding of the input */
00233       UInt32   state_in_ch;
00234       Int32    state_in_len;
00235       BZ_RAND_DECLS;
00236 
00237       /* input and output limits and current posns */
00238       Int32    nblock;
00239       Int32    nblockMAX;
00240       Int32    numZ;
00241       Int32    state_out_pos;
00242 
00243       /* map of bytes used in block */
00244       Int32    nInUse;
00245       Bool     inUse[256];
00246       UChar    unseqToSeq[256];
00247 
00248       /* the buffer for bit stream creation */
00249       UInt32   bsBuff;
00250       Int32    bsLive;
00251 
00252       /* block and combined CRCs */
00253       UInt32   blockCRC;
00254       UInt32   combinedCRC;
00255 
00256       /* misc administratium */
00257       Int32    verbosity;
00258       Int32    blockNo;
00259       Int32    blockSize100k;
00260 
00261       /* stuff for coding the MTF values */
00262       Int32    nMTF;
00263       Int32    mtfFreq    [BZ_MAX_ALPHA_SIZE];
00264       UChar    selector   [BZ_MAX_SELECTORS];
00265       UChar    selectorMtf[BZ_MAX_SELECTORS];
00266 
00267       UChar    len     [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00268       Int32    code    [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00269       Int32    rfreq   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00270       /* second dimension: only 3 needed; 4 makes index calculations faster */
00271       UInt32   len_pack[BZ_MAX_ALPHA_SIZE][4];
00272 
00273    }
00274    EState;
00275 
00276 
00277 
00278 /*-- externs for compression. --*/
00279 
00280 extern void 
00281 BZ2_blockSort ( EState* );
00282 
00283 extern void 
00284 BZ2_compressBlock ( EState*, Bool );
00285 
00286 extern void 
00287 BZ2_bsInitWrite ( EState* );
00288 
00289 extern void 
00290 BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
00291 
00292 extern void 
00293 BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
00294 
00295 
00296 
00297 /*-- states for decompression. --*/
00298 
00299 #define BZ_X_IDLE        1
00300 #define BZ_X_OUTPUT      2
00301 
00302 #define BZ_X_MAGIC_1     10
00303 #define BZ_X_MAGIC_2     11
00304 #define BZ_X_MAGIC_3     12
00305 #define BZ_X_MAGIC_4     13
00306 #define BZ_X_BLKHDR_1    14
00307 #define BZ_X_BLKHDR_2    15
00308 #define BZ_X_BLKHDR_3    16
00309 #define BZ_X_BLKHDR_4    17
00310 #define BZ_X_BLKHDR_5    18
00311 #define BZ_X_BLKHDR_6    19
00312 #define BZ_X_BCRC_1      20
00313 #define BZ_X_BCRC_2      21
00314 #define BZ_X_BCRC_3      22
00315 #define BZ_X_BCRC_4      23
00316 #define BZ_X_RANDBIT     24
00317 #define BZ_X_ORIGPTR_1   25
00318 #define BZ_X_ORIGPTR_2   26
00319 #define BZ_X_ORIGPTR_3   27
00320 #define BZ_X_MAPPING_1   28
00321 #define BZ_X_MAPPING_2   29
00322 #define BZ_X_SELECTOR_1  30
00323 #define BZ_X_SELECTOR_2  31
00324 #define BZ_X_SELECTOR_3  32
00325 #define BZ_X_CODING_1    33
00326 #define BZ_X_CODING_2    34
00327 #define BZ_X_CODING_3    35
00328 #define BZ_X_MTF_1       36
00329 #define BZ_X_MTF_2       37
00330 #define BZ_X_MTF_3       38
00331 #define BZ_X_MTF_4       39
00332 #define BZ_X_MTF_5       40
00333 #define BZ_X_MTF_6       41
00334 #define BZ_X_ENDHDR_2    42
00335 #define BZ_X_ENDHDR_3    43
00336 #define BZ_X_ENDHDR_4    44
00337 #define BZ_X_ENDHDR_5    45
00338 #define BZ_X_ENDHDR_6    46
00339 #define BZ_X_CCRC_1      47
00340 #define BZ_X_CCRC_2      48
00341 #define BZ_X_CCRC_3      49
00342 #define BZ_X_CCRC_4      50
00343 
00344 
00345 
00346 /*-- Constants for the fast MTF decoder. --*/
00347 
00348 #define MTFA_SIZE 4096
00349 #define MTFL_SIZE 16
00350 
00351 
00352 
00353 /*-- Structure holding all the decompression-side stuff. --*/
00354 
00355 typedef
00356    struct {
00357       /* pointer back to the struct bz_stream */
00358       bz_stream* strm;
00359 
00360       /* state indicator for this stream */
00361       Int32    state;
00362 
00363       /* for doing the final run-length decoding */
00364       UChar    state_out_ch;
00365       Int32    state_out_len;
00366       Bool     blockRandomised;
00367       BZ_RAND_DECLS;
00368 
00369       /* the buffer for bit stream reading */
00370       UInt32   bsBuff;
00371       Int32    bsLive;
00372 
00373       /* misc administratium */
00374       Int32    blockSize100k;
00375       Bool     smallDecompress;
00376       Int32    currBlockNo;
00377       Int32    verbosity;
00378 
00379       /* for undoing the Burrows-Wheeler transform */
00380       Int32    origPtr;
00381       UInt32   tPos;
00382       Int32    k0;
00383       Int32    unzftab[256];
00384       Int32    nblock_used;
00385       Int32    cftab[257];
00386       Int32    cftabCopy[257];
00387 
00388       /* for undoing the Burrows-Wheeler transform (FAST) */
00389       UInt32   *tt;
00390 
00391       /* for undoing the Burrows-Wheeler transform (SMALL) */
00392       UInt16   *ll16;
00393       UChar    *ll4;
00394 
00395       /* stored and calculated CRCs */
00396       UInt32   storedBlockCRC;
00397       UInt32   storedCombinedCRC;
00398       UInt32   calculatedBlockCRC;
00399       UInt32   calculatedCombinedCRC;
00400 
00401       /* map of bytes used in block */
00402       Int32    nInUse;
00403       Bool     inUse[256];
00404       Bool     inUse16[16];
00405       UChar    seqToUnseq[256];
00406 
00407       /* for decoding the MTF values */
00408       UChar    mtfa   [MTFA_SIZE];
00409       Int32    mtfbase[256 / MTFL_SIZE];
00410       UChar    selector   [BZ_MAX_SELECTORS];
00411       UChar    selectorMtf[BZ_MAX_SELECTORS];
00412       UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00413 
00414       Int32    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00415       Int32    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00416       Int32    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00417       Int32    minLens[BZ_N_GROUPS];
00418 
00419       /* block end handler */
00420       void (*blockEndHandler) (void *, bz_stream *, unsigned int, unsigned int,
00421                                unsigned int, unsigned int);
00422       void *   blockEndHandlerData;
00423 
00424       /* save area for scalars in the main decompress code */
00425       Int32    save_i;
00426       Int32    save_j;
00427       Int32    save_t;
00428       Int32    save_alphaSize;
00429       Int32    save_nGroups;
00430       Int32    save_nSelectors;
00431       Int32    save_EOB;
00432       Int32    save_groupNo;
00433       Int32    save_groupPos;
00434       Int32    save_nextSym;
00435       Int32    save_nblockMAX;
00436       Int32    save_nblock;
00437       Int32    save_es;
00438       Int32    save_N;
00439       Int32    save_curr;
00440       Int32    save_zt;
00441       Int32    save_zn; 
00442       Int32    save_zvec;
00443       Int32    save_zj;
00444       Int32    save_gSel;
00445       Int32    save_gMinlen;
00446       Int32*   save_gLimit;
00447       Int32*   save_gBase;
00448       Int32*   save_gPerm;
00449 
00450    }
00451    DState;
00452 
00453 
00454 
00455 /*-- Macros for decompression. --*/
00456 
00457 #define BZ_GET_FAST(cccc)                     \
00458     /* c_tPos is unsigned, hence test < 0 is pointless. */ \
00459     if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \
00460     s->tPos = s->tt[s->tPos];                 \
00461     cccc = (UChar)(s->tPos & 0xff);           \
00462     s->tPos >>= 8;
00463 
00464 #define BZ_GET_FAST_C(cccc)                   \
00465     /* c_tPos is unsigned, hence test < 0 is pointless. */ \
00466     if (c_tPos >= (UInt32)100000 * (UInt32)ro_blockSize100k) return True; \
00467     c_tPos = c_tt[c_tPos];                    \
00468     cccc = (UChar)(c_tPos & 0xff);            \
00469     c_tPos >>= 8;
00470 
00471 #define SET_LL4(i,n)                                          \
00472    { if (((i) & 0x1) == 0)                                    \
00473         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
00474         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
00475    }
00476 
00477 #define GET_LL4(i)                             \
00478    ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
00479 
00480 #define SET_LL(i,n)                          \
00481    { s->ll16[i] = (UInt16)(n & 0x0000ffff);  \
00482      SET_LL4(i, n >> 16);                    \
00483    }
00484 
00485 #define GET_LL(i) \
00486    (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
00487 
00488 #define BZ_GET_SMALL(cccc)                            \
00489     /* c_tPos is unsigned, hence test < 0 is pointless. */ \
00490     if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \
00491     cccc = BZ2_indexIntoF ( s->tPos, s->cftab );    \
00492     s->tPos = GET_LL(s->tPos);
00493 
00494 
00495 /*-- externs for decompression. --*/
00496 
00497 extern Int32 
00498 BZ2_indexIntoF ( Int32, Int32* );
00499 
00500 extern Int32 
00501 BZ2_decompress ( DState* );
00502 
00503 extern void 
00504 BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
00505                            Int32,  Int32, Int32 );
00506 
00507 
00508 #endif
00509 
00510 
00511 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
00512 
00513 #ifdef BZ_NO_STDIO
00514 #ifndef NULL
00515 #define NULL 0
00516 #endif
00517 #endif
00518 
00519 
00520 /*-------------------------------------------------------------*/
00521 /*--- end                                   bzlib_private.h ---*/
00522 /*-------------------------------------------------------------*/