lib_generic/bzlib_private.h

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