lib/Support/bzip2/bzlib_private.h

   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-2002 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@acm.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.2, 30-Dec-2001"
  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 /*-------------------------------------------------------------*/