vx32

Local 9vx git repository for patches.
git clone git://r-36.net/vx32
Log | Files | Refs

bzlib_private.h (14257B)


      1 
      2 /*-------------------------------------------------------------*/
      3 /*--- Private header file for the library.                  ---*/
      4 /*---                                       bzlib_private.h ---*/
      5 /*-------------------------------------------------------------*/
      6 
      7 /*--
      8   This file is a part of bzip2 and/or libbzip2, a program and
      9   library for lossless, block-sorting data compression.
     10 
     11   Copyright (C) 1996-2005 Julian R Seward.  All rights reserved.
     12 
     13   Redistribution and use in source and binary forms, with or without
     14   modification, are permitted provided that the following conditions
     15   are met:
     16 
     17   1. Redistributions of source code must retain the above copyright
     18      notice, this list of conditions and the following disclaimer.
     19 
     20   2. The origin of this software must not be misrepresented; you must 
     21      not claim that you wrote the original software.  If you use this 
     22      software in a product, an acknowledgment in the product 
     23      documentation would be appreciated but is not required.
     24 
     25   3. Altered source versions must be plainly marked as such, and must
     26      not be misrepresented as being the original software.
     27 
     28   4. The name of the author may not be used to endorse or promote 
     29      products derived from this software without specific prior written 
     30      permission.
     31 
     32   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
     33   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
     34   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     35   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
     36   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     37   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
     38   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     39   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
     40   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
     41   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
     42   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     43 
     44   Julian Seward, Cambridge, UK.
     45   jseward@bzip.org
     46   bzip2/libbzip2 version 1.0 of 21 March 2000
     47 
     48   This program is based on (at least) the work of:
     49      Mike Burrows
     50      David Wheeler
     51      Peter Fenwick
     52      Alistair Moffat
     53      Radford Neal
     54      Ian H. Witten
     55      Robert Sedgewick
     56      Jon L. Bentley
     57 
     58   For more information on these sources, see the manual.
     59 --*/
     60 
     61 
     62 #ifndef _BZLIB_PRIVATE_H
     63 #define _BZLIB_PRIVATE_H
     64 
     65 #include <stdlib.h>
     66 
     67 #ifndef BZ_NO_STDIO
     68 #include <stdio.h>
     69 #include <ctype.h>
     70 #include <string.h>
     71 #endif
     72 
     73 #include "bzlib.h"
     74 
     75 
     76 
     77 /*-- General stuff. --*/
     78 
     79 #define BZ_VERSION  "1.0.3, 15-Feb-2005"
     80 
     81 typedef char            Char;
     82 typedef unsigned char   Bool;
     83 typedef unsigned char   UChar;
     84 typedef int             Int32;
     85 typedef unsigned int    UInt32;
     86 typedef short           Int16;
     87 typedef unsigned short  UInt16;
     88 
     89 #define True  ((Bool)1)
     90 #define False ((Bool)0)
     91 
     92 #ifndef __GNUC__
     93 #define __inline__  /* */
     94 #endif 
     95 
     96 #ifndef BZ_NO_STDIO
     97 extern void BZ2_bz__AssertH__fail ( int errcode );
     98 #define AssertH(cond,errcode) \
     99    { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }
    100 #if BZ_DEBUG
    101 #define AssertD(cond,msg) \
    102    { if (!(cond)) {       \
    103       fprintf ( stderr,   \
    104         "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\
    105       exit(1); \
    106    }}
    107 #else
    108 #define AssertD(cond,msg) /* */
    109 #endif
    110 #define VPrintf0(zf) \
    111    fprintf(stderr,zf)
    112 #define VPrintf1(zf,za1) \
    113    fprintf(stderr,zf,za1)
    114 #define VPrintf2(zf,za1,za2) \
    115    fprintf(stderr,zf,za1,za2)
    116 #define VPrintf3(zf,za1,za2,za3) \
    117    fprintf(stderr,zf,za1,za2,za3)
    118 #define VPrintf4(zf,za1,za2,za3,za4) \
    119    fprintf(stderr,zf,za1,za2,za3,za4)
    120 #define VPrintf5(zf,za1,za2,za3,za4,za5) \
    121    fprintf(stderr,zf,za1,za2,za3,za4,za5)
    122 #else
    123 extern void bz_internal_error ( int errcode );
    124 #define AssertH(cond,errcode) \
    125    { if (!(cond)) bz_internal_error ( errcode ); }
    126 #define AssertD(cond,msg) /* */
    127 #define VPrintf0(zf) /* */
    128 #define VPrintf1(zf,za1) /* */
    129 #define VPrintf2(zf,za1,za2) /* */
    130 #define VPrintf3(zf,za1,za2,za3) /* */
    131 #define VPrintf4(zf,za1,za2,za3,za4) /* */
    132 #define VPrintf5(zf,za1,za2,za3,za4,za5) /* */
    133 #endif
    134 
    135 
    136 #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
    137 #define BZFREE(ppp)  (strm->bzfree)(strm->opaque,(ppp))
    138 
    139 
    140 /*-- Header bytes. --*/
    141 
    142 #define BZ_HDR_B 0x42   /* 'B' */
    143 #define BZ_HDR_Z 0x5a   /* 'Z' */
    144 #define BZ_HDR_h 0x68   /* 'h' */
    145 #define BZ_HDR_0 0x30   /* '0' */
    146   
    147 /*-- Constants for the back end. --*/
    148 
    149 #define BZ_MAX_ALPHA_SIZE 258
    150 #define BZ_MAX_CODE_LEN    23
    151 
    152 #define BZ_RUNA 0
    153 #define BZ_RUNB 1
    154 
    155 #define BZ_N_GROUPS 6
    156 #define BZ_G_SIZE   50
    157 #define BZ_N_ITERS  4
    158 
    159 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
    160 
    161 
    162 
    163 /*-- Stuff for randomising repetitive blocks. --*/
    164 
    165 extern Int32 BZ2_rNums[512];
    166 
    167 #define BZ_RAND_DECLS                          \
    168    Int32 rNToGo;                               \
    169    Int32 rTPos                                 \
    170 
    171 #define BZ_RAND_INIT_MASK                      \
    172    s->rNToGo = 0;                              \
    173    s->rTPos  = 0                               \
    174 
    175 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
    176 
    177 #define BZ_RAND_UPD_MASK                       \
    178    if (s->rNToGo == 0) {                       \
    179       s->rNToGo = BZ2_rNums[s->rTPos];         \
    180       s->rTPos++;                              \
    181       if (s->rTPos == 512) s->rTPos = 0;       \
    182    }                                           \
    183    s->rNToGo--;
    184 
    185 
    186 
    187 /*-- Stuff for doing CRCs. --*/
    188 
    189 extern UInt32 BZ2_crc32Table[256];
    190 
    191 #define BZ_INITIALISE_CRC(crcVar)              \
    192 {                                              \
    193    crcVar = 0xffffffffL;                       \
    194 }
    195 
    196 #define BZ_FINALISE_CRC(crcVar)                \
    197 {                                              \
    198    crcVar = ~(crcVar);                         \
    199 }
    200 
    201 #define BZ_UPDATE_CRC(crcVar,cha)              \
    202 {                                              \
    203    crcVar = (crcVar << 8) ^                    \
    204             BZ2_crc32Table[(crcVar >> 24) ^    \
    205                            ((UChar)cha)];      \
    206 }
    207 
    208 
    209 
    210 /*-- States and modes for compression. --*/
    211 
    212 #define BZ_M_IDLE      1
    213 #define BZ_M_RUNNING   2
    214 #define BZ_M_FLUSHING  3
    215 #define BZ_M_FINISHING 4
    216 
    217 #define BZ_S_OUTPUT    1
    218 #define BZ_S_INPUT     2
    219 
    220 #define BZ_N_RADIX 2
    221 #define BZ_N_QSORT 12
    222 #define BZ_N_SHELL 18
    223 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
    224 
    225 
    226 
    227 
    228 /*-- Structure holding all the compression-side stuff. --*/
    229 
    230 typedef
    231    struct {
    232       /* pointer back to the struct bz_stream */
    233       bz_stream* strm;
    234 
    235       /* mode this stream is in, and whether inputting */
    236       /* or outputting data */
    237       Int32    mode;
    238       Int32    state;
    239 
    240       /* remembers avail_in when flush/finish requested */
    241       UInt32   avail_in_expect;
    242 
    243       /* for doing the block sorting */
    244       UInt32*  arr1;
    245       UInt32*  arr2;
    246       UInt32*  ftab;
    247       Int32    origPtr;
    248 
    249       /* aliases for arr1 and arr2 */
    250       UInt32*  ptr;
    251       UChar*   block;
    252       UInt16*  mtfv;
    253       UChar*   zbits;
    254 
    255       /* for deciding when to use the fallback sorting algorithm */
    256       Int32    workFactor;
    257 
    258       /* run-length-encoding of the input */
    259       UInt32   state_in_ch;
    260       Int32    state_in_len;
    261       BZ_RAND_DECLS;
    262 
    263       /* input and output limits and current posns */
    264       Int32    nblock;
    265       Int32    nblockMAX;
    266       Int32    numZ;
    267       Int32    state_out_pos;
    268 
    269       /* map of bytes used in block */
    270       Int32    nInUse;
    271       Bool     inUse[256];
    272       UChar    unseqToSeq[256];
    273 
    274       /* the buffer for bit stream creation */
    275       UInt32   bsBuff;
    276       Int32    bsLive;
    277 
    278       /* block and combined CRCs */
    279       UInt32   blockCRC;
    280       UInt32   combinedCRC;
    281 
    282       /* misc administratium */
    283       Int32    verbosity;
    284       Int32    blockNo;
    285       Int32    blockSize100k;
    286 
    287       /* stuff for coding the MTF values */
    288       Int32    nMTF;
    289       Int32    mtfFreq    [BZ_MAX_ALPHA_SIZE];
    290       UChar    selector   [BZ_MAX_SELECTORS];
    291       UChar    selectorMtf[BZ_MAX_SELECTORS];
    292 
    293       UChar    len     [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
    294       Int32    code    [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
    295       Int32    rfreq   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
    296       /* second dimension: only 3 needed; 4 makes index calculations faster */
    297       UInt32   len_pack[BZ_MAX_ALPHA_SIZE][4];
    298 
    299    }
    300    EState;
    301 
    302 
    303 
    304 /*-- externs for compression. --*/
    305 
    306 extern void 
    307 BZ2_blockSort ( EState* );
    308 
    309 extern void 
    310 BZ2_compressBlock ( EState*, Bool );
    311 
    312 extern void 
    313 BZ2_bsInitWrite ( EState* );
    314 
    315 extern void 
    316 BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
    317 
    318 extern void 
    319 BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
    320 
    321 
    322 
    323 /*-- states for decompression. --*/
    324 
    325 #define BZ_X_IDLE        1
    326 #define BZ_X_OUTPUT      2
    327 
    328 #define BZ_X_MAGIC_1     10
    329 #define BZ_X_MAGIC_2     11
    330 #define BZ_X_MAGIC_3     12
    331 #define BZ_X_MAGIC_4     13
    332 #define BZ_X_BLKHDR_1    14
    333 #define BZ_X_BLKHDR_2    15
    334 #define BZ_X_BLKHDR_3    16
    335 #define BZ_X_BLKHDR_4    17
    336 #define BZ_X_BLKHDR_5    18
    337 #define BZ_X_BLKHDR_6    19
    338 #define BZ_X_BCRC_1      20
    339 #define BZ_X_BCRC_2      21
    340 #define BZ_X_BCRC_3      22
    341 #define BZ_X_BCRC_4      23
    342 #define BZ_X_RANDBIT     24
    343 #define BZ_X_ORIGPTR_1   25
    344 #define BZ_X_ORIGPTR_2   26
    345 #define BZ_X_ORIGPTR_3   27
    346 #define BZ_X_MAPPING_1   28
    347 #define BZ_X_MAPPING_2   29
    348 #define BZ_X_SELECTOR_1  30
    349 #define BZ_X_SELECTOR_2  31
    350 #define BZ_X_SELECTOR_3  32
    351 #define BZ_X_CODING_1    33
    352 #define BZ_X_CODING_2    34
    353 #define BZ_X_CODING_3    35
    354 #define BZ_X_MTF_1       36
    355 #define BZ_X_MTF_2       37
    356 #define BZ_X_MTF_3       38
    357 #define BZ_X_MTF_4       39
    358 #define BZ_X_MTF_5       40
    359 #define BZ_X_MTF_6       41
    360 #define BZ_X_ENDHDR_2    42
    361 #define BZ_X_ENDHDR_3    43
    362 #define BZ_X_ENDHDR_4    44
    363 #define BZ_X_ENDHDR_5    45
    364 #define BZ_X_ENDHDR_6    46
    365 #define BZ_X_CCRC_1      47
    366 #define BZ_X_CCRC_2      48
    367 #define BZ_X_CCRC_3      49
    368 #define BZ_X_CCRC_4      50
    369 
    370 
    371 
    372 /*-- Constants for the fast MTF decoder. --*/
    373 
    374 #define MTFA_SIZE 4096
    375 #define MTFL_SIZE 16
    376 
    377 
    378 
    379 /*-- Structure holding all the decompression-side stuff. --*/
    380 
    381 typedef
    382    struct {
    383       /* pointer back to the struct bz_stream */
    384       bz_stream* strm;
    385 
    386       /* state indicator for this stream */
    387       Int32    state;
    388 
    389       /* for doing the final run-length decoding */
    390       UChar    state_out_ch;
    391       Int32    state_out_len;
    392       Bool     blockRandomised;
    393       BZ_RAND_DECLS;
    394 
    395       /* the buffer for bit stream reading */
    396       UInt32   bsBuff;
    397       Int32    bsLive;
    398 
    399       /* misc administratium */
    400       Int32    blockSize100k;
    401       Bool     smallDecompress;
    402       Int32    currBlockNo;
    403       Int32    verbosity;
    404 
    405       /* for undoing the Burrows-Wheeler transform */
    406       Int32    origPtr;
    407       UInt32   tPos;
    408       Int32    k0;
    409       Int32    unzftab[256];
    410       Int32    nblock_used;
    411       Int32    cftab[257];
    412       Int32    cftabCopy[257];
    413 
    414       /* for undoing the Burrows-Wheeler transform (FAST) */
    415       UInt32   *tt;
    416 
    417       /* for undoing the Burrows-Wheeler transform (SMALL) */
    418       UInt16   *ll16;
    419       UChar    *ll4;
    420 
    421       /* stored and calculated CRCs */
    422       UInt32   storedBlockCRC;
    423       UInt32   storedCombinedCRC;
    424       UInt32   calculatedBlockCRC;
    425       UInt32   calculatedCombinedCRC;
    426 
    427       /* map of bytes used in block */
    428       Int32    nInUse;
    429       Bool     inUse[256];
    430       Bool     inUse16[16];
    431       UChar    seqToUnseq[256];
    432 
    433       /* for decoding the MTF values */
    434       UChar    mtfa   [MTFA_SIZE];
    435       Int32    mtfbase[256 / MTFL_SIZE];
    436       UChar    selector   [BZ_MAX_SELECTORS];
    437       UChar    selectorMtf[BZ_MAX_SELECTORS];
    438       UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
    439 
    440       Int32    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
    441       Int32    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
    442       Int32    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
    443       Int32    minLens[BZ_N_GROUPS];
    444 
    445       /* save area for scalars in the main decompress code */
    446       Int32    save_i;
    447       Int32    save_j;
    448       Int32    save_t;
    449       Int32    save_alphaSize;
    450       Int32    save_nGroups;
    451       Int32    save_nSelectors;
    452       Int32    save_EOB;
    453       Int32    save_groupNo;
    454       Int32    save_groupPos;
    455       Int32    save_nextSym;
    456       Int32    save_nblockMAX;
    457       Int32    save_nblock;
    458       Int32    save_es;
    459       Int32    save_N;
    460       Int32    save_curr;
    461       Int32    save_zt;
    462       Int32    save_zn; 
    463       Int32    save_zvec;
    464       Int32    save_zj;
    465       Int32    save_gSel;
    466       Int32    save_gMinlen;
    467       Int32*   save_gLimit;
    468       Int32*   save_gBase;
    469       Int32*   save_gPerm;
    470 
    471    }
    472    DState;
    473 
    474 
    475 
    476 /*-- Macros for decompression. --*/
    477 
    478 #define BZ_GET_FAST(cccc)                     \
    479     s->tPos = s->tt[s->tPos];                 \
    480     cccc = (UChar)(s->tPos & 0xff);           \
    481     s->tPos >>= 8;
    482 
    483 #define BZ_GET_FAST_C(cccc)                   \
    484     c_tPos = c_tt[c_tPos];                    \
    485     cccc = (UChar)(c_tPos & 0xff);            \
    486     c_tPos >>= 8;
    487 
    488 #define SET_LL4(i,n)                                          \
    489    { if (((i) & 0x1) == 0)                                    \
    490         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
    491         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
    492    }
    493 
    494 #define GET_LL4(i)                             \
    495    ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
    496 
    497 #define SET_LL(i,n)                          \
    498    { s->ll16[i] = (UInt16)(n & 0x0000ffff);  \
    499      SET_LL4(i, n >> 16);                    \
    500    }
    501 
    502 #define GET_LL(i) \
    503    (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
    504 
    505 #define BZ_GET_SMALL(cccc)                            \
    506       cccc = BZ2_indexIntoF ( s->tPos, s->cftab );    \
    507       s->tPos = GET_LL(s->tPos);
    508 
    509 
    510 /*-- externs for decompression. --*/
    511 
    512 extern Int32 
    513 BZ2_indexIntoF ( Int32, Int32* );
    514 
    515 extern Int32 
    516 BZ2_decompress ( DState* );
    517 
    518 extern void 
    519 BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
    520                            Int32,  Int32, Int32 );
    521 
    522 
    523 #endif
    524 
    525 
    526 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
    527 
    528 #ifdef BZ_NO_STDIO
    529 #ifndef NULL
    530 #define NULL 0
    531 #endif
    532 #endif
    533 
    534 
    535 /*-------------------------------------------------------------*/
    536 /*--- end                                   bzlib_private.h ---*/
    537 /*-------------------------------------------------------------*/