external/bsd/bzip2/dist/bzlib_private.h

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