drivers/lib/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-2000 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.1, 23-June-2000"
  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 /*-- Constants for the back end. --*/
 141
 142 #define BZ_MAX_ALPHA_SIZE 258
 143 #define BZ_MAX_CODE_LEN    23
 144
 145 #define BZ_RUNA 0
 146 #define BZ_RUNB 1
 147
 148 #define BZ_N_GROUPS 6
 149 #define BZ_G_SIZE   50
 150 #define BZ_N_ITERS  4
 151
 152 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
 153
 154
 155
 156 /*-- Stuff for randomising repetitive blocks. --*/
 157
 158 extern Int32 BZ2_rNums[512];
 159
 160 #define BZ_RAND_DECLS                          \
 161    Int32 rNToGo;                               \
 162    Int32 rTPos                                 \
 163
 164 #define BZ_RAND_INIT_MASK                      \
 165    s->rNToGo = 0;                              \
 166    s->rTPos  = 0                               \
 167
 168 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
 169
 170 #define BZ_RAND_UPD_MASK                       \
 171    if (s->rNToGo == 0) {                       \
 172       s->rNToGo = BZ2_rNums[s->rTPos];         \
 173       s->rTPos++;                              \
 174       if (s->rTPos == 512) s->rTPos = 0;       \
 175    }                                           \
 176    s->rNToGo--;
 177
 178
 179
 180 /*-- Stuff for doing CRCs. --*/
 181
 182 extern UInt32 BZ2_crc32Table[256];
 183
 184 #define BZ_INITIALISE_CRC(crcVar)              \
 185 {                                              \
 186    crcVar = 0xffffffffL;                       \
 187 }
 188
 189 #define BZ_FINALISE_CRC(crcVar)                \
 190 {                                              \
 191    crcVar = ~(crcVar);                         \
 192 }
 193
 194 #define BZ_UPDATE_CRC(crcVar,cha)              \
 195 {                                              \
 196    crcVar = (crcVar << 8) ^                    \
 197             BZ2_crc32Table[(crcVar >> 24) ^    \
 198                            ((UChar)cha)];      \
 199 }
 200
 201
 202
 203 /*-- States and modes for compression. --*/
 204
 205 #define BZ_M_IDLE      1
 206 #define BZ_M_RUNNING   2
 207 #define BZ_M_FLUSHING  3
 208 #define BZ_M_FINISHING 4
 209
 210 #define BZ_S_OUTPUT    1
 211 #define BZ_S_INPUT     2
 212
 213 #define BZ_N_RADIX 2
 214 #define BZ_N_QSORT 12
 215 #define BZ_N_SHELL 18
 216 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
 217
 218
 219
 220
 221 /*-- Structure holding all the compression-side stuff. --*/
 222
 223 typedef
 224    struct {
 225       /* pointer back to the struct bz_stream */
 226       bz_stream* strm;
 227
 228       /* mode this stream is in, and whether inputting */
 229       /* or outputting data */
 230       Int32    mode;
 231       Int32    state;
 232
 233       /* remembers avail_in when flush/finish requested */
 234       UInt32   avail_in_expect;
 235
 236       /* for doing the block sorting */
 237       UInt32*  arr1;
 238       UInt32*  arr2;
 239       UInt32*  ftab;
 240       Int32    origPtr;
 241
 242       /* aliases for arr1 and arr2 */
 243       UInt32*  ptr;
 244       UChar*   block;
 245       UInt16*  mtfv;
 246       UChar*   zbits;
 247
 248       /* for deciding when to use the fallback sorting algorithm */
 249       Int32    workFactor;
 250
 251       /* run-length-encoding of the input */
 252       UInt32   state_in_ch;
 253       Int32    state_in_len;
 254       BZ_RAND_DECLS;
 255
 256       /* input and output limits and current posns */
 257       Int32    nblock;
 258       Int32    nblockMAX;
 259       Int32    numZ;
 260       Int32    state_out_pos;
 261
 262       /* map of bytes used in block */
 263       Int32    nInUse;
 264       Bool     inUse[256];
 265       UChar    unseqToSeq[256];
 266
 267       /* the buffer for bit stream creation */
 268       UInt32   bsBuff;
 269       Int32    bsLive;
 270
 271       /* block and combined CRCs */
 272       UInt32   blockCRC;
 273       UInt32   combinedCRC;
 274
 275       /* misc administratium */
 276       Int32    verbosity;
 277       Int32    blockNo;
 278       Int32    blockSize100k;
 279
 280       /* stuff for coding the MTF values */
 281       Int32    nMTF;
 282       Int32    mtfFreq    [BZ_MAX_ALPHA_SIZE];
 283       UChar    selector   [BZ_MAX_SELECTORS];
 284       UChar    selectorMtf[BZ_MAX_SELECTORS];
 285
 286       UChar    len     [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 287       Int32    code    [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 288       Int32    rfreq   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 289       /* second dimension: only 3 needed; 4 makes index calculations faster */
 290       UInt32   len_pack[BZ_MAX_ALPHA_SIZE][4];
 291
 292    }
 293    EState;
 294
 295
 296
 297 /*-- externs for compression. --*/
 298
 299 extern void
 300 BZ2_blockSort ( EState* );
 301
 302 extern void
 303 BZ2_compressBlock ( EState*, Bool );
 304
 305 extern void
 306 BZ2_bsInitWrite ( EState* );
 307
 308 extern void
 309 BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
 310
 311 extern void
 312 BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
 313
 314
 315
 316 /*-- states for decompression. --*/
 317
 318 #define BZ_X_IDLE        1
 319 #define BZ_X_OUTPUT      2
 320
 321 #define BZ_X_MAGIC_1     10
 322 #define BZ_X_MAGIC_2     11
 323 #define BZ_X_MAGIC_3     12
 324 #define BZ_X_MAGIC_4     13
 325 #define BZ_X_BLKHDR_1    14
 326 #define BZ_X_BLKHDR_2    15
 327 #define BZ_X_BLKHDR_3    16
 328 #define BZ_X_BLKHDR_4    17
 329 #define BZ_X_BLKHDR_5    18
 330 #define BZ_X_BLKHDR_6    19
 331 #define BZ_X_BCRC_1      20
 332 #define BZ_X_BCRC_2      21
 333 #define BZ_X_BCRC_3      22
 334 #define BZ_X_BCRC_4      23
 335 #define BZ_X_RANDBIT     24
 336 #define BZ_X_ORIGPTR_1   25
 337 #define BZ_X_ORIGPTR_2   26
 338 #define BZ_X_ORIGPTR_3   27
 339 #define BZ_X_MAPPING_1   28
 340 #define BZ_X_MAPPING_2   29
 341 #define BZ_X_SELECTOR_1  30
 342 #define BZ_X_SELECTOR_2  31
 343 #define BZ_X_SELECTOR_3  32
 344 #define BZ_X_CODING_1    33
 345 #define BZ_X_CODING_2    34
 346 #define BZ_X_CODING_3    35
 347 #define BZ_X_MTF_1       36
 348 #define BZ_X_MTF_2       37
 349 #define BZ_X_MTF_3       38
 350 #define BZ_X_MTF_4       39
 351 #define BZ_X_MTF_5       40
 352 #define BZ_X_MTF_6       41
 353 #define BZ_X_ENDHDR_2    42
 354 #define BZ_X_ENDHDR_3    43
 355 #define BZ_X_ENDHDR_4    44
 356 #define BZ_X_ENDHDR_5    45
 357 #define BZ_X_ENDHDR_6    46
 358 #define BZ_X_CCRC_1      47
 359 #define BZ_X_CCRC_2      48
 360 #define BZ_X_CCRC_3      49
 361 #define BZ_X_CCRC_4      50
 362
 363
 364
 365 /*-- Constants for the fast MTF decoder. --*/
 366
 367 #define MTFA_SIZE 4096
 368 #define MTFL_SIZE 16
 369
 370
 371
 372 /*-- Structure holding all the decompression-side stuff. --*/
 373
 374 typedef
 375    struct {
 376       /* pointer back to the struct bz_stream */
 377       bz_stream* strm;
 378
 379       /* state indicator for this stream */
 380       Int32    state;
 381
 382       /* for doing the final run-length decoding */
 383       UChar    state_out_ch;
 384       Int32    state_out_len;
 385       Bool     blockRandomised;
 386       BZ_RAND_DECLS;
 387
 388       /* the buffer for bit stream reading */
 389       UInt32   bsBuff;
 390       Int32    bsLive;
 391
 392       /* misc administratium */
 393       Int32    blockSize100k;
 394       Bool     smallDecompress;
 395       Int32    currBlockNo;
 396       Int32    verbosity;
 397
 398       /* for undoing the Burrows-Wheeler transform */
 399       Int32    origPtr;
 400       UInt32   tPos;
 401       Int32    k0;
 402       Int32    unzftab[256];
 403       Int32    nblock_used;
 404       Int32    cftab[257];
 405       Int32    cftabCopy[257];
 406
 407       /* for undoing the Burrows-Wheeler transform (FAST) */
 408       UInt32   *tt;
 409
 410       /* for undoing the Burrows-Wheeler transform (SMALL) */
 411       UInt16   *ll16;
 412       UChar    *ll4;
 413
 414       /* stored and calculated CRCs */
 415       UInt32   storedBlockCRC;
 416       UInt32   storedCombinedCRC;
 417       UInt32   calculatedBlockCRC;
 418       UInt32   calculatedCombinedCRC;
 419
 420       /* map of bytes used in block */
 421       Int32    nInUse;
 422       Bool     inUse[256];
 423       Bool     inUse16[16];
 424       UChar    seqToUnseq[256];
 425
 426       /* for decoding the MTF values */
 427       UChar    mtfa   [MTFA_SIZE];
 428       Int32    mtfbase[256 / MTFL_SIZE];
 429       UChar    selector   [BZ_MAX_SELECTORS];
 430       UChar    selectorMtf[BZ_MAX_SELECTORS];
 431       UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 432
 433       Int32    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 434       Int32    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 435       Int32    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 436       Int32    minLens[BZ_N_GROUPS];
 437
 438       /* save area for scalars in the main decompress code */
 439       Int32    save_i;
 440       Int32    save_j;
 441       Int32    save_t;
 442       Int32    save_alphaSize;
 443       Int32    save_nGroups;
 444       Int32    save_nSelectors;
 445       Int32    save_EOB;
 446       Int32    save_groupNo;
 447       Int32    save_groupPos;
 448       Int32    save_nextSym;
 449       Int32    save_nblockMAX;
 450       Int32    save_nblock;
 451       Int32    save_es;
 452       Int32    save_N;
 453       Int32    save_curr;
 454       Int32    save_zt;
 455       Int32    save_zn;
 456       Int32    save_zvec;
 457       Int32    save_zj;
 458       Int32    save_gSel;
 459       Int32    save_gMinlen;
 460       Int32*   save_gLimit;
 461       Int32*   save_gBase;
 462       Int32*   save_gPerm;
 463
 464    }
 465    DState;
 466
 467
 468
 469 /*-- Macros for decompression. --*/
 470
 471 #define BZ_GET_FAST(cccc)                     \
 472     s->tPos = s->tt[s->tPos];                 \
 473     cccc = (UChar)(s->tPos & 0xff);           \
 474     s->tPos >>= 8;
 475
 476 #define BZ_GET_FAST_C(cccc)                   \
 477     c_tPos = c_tt[c_tPos];                    \
 478     cccc = (UChar)(c_tPos & 0xff);            \
 479     c_tPos >>= 8;
 480
 481 #define SET_LL4(i,n)                                          \
 482    { if (((i) & 0x1) == 0)                                    \
 483         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
 484         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
 485    }
 486
 487 #define GET_LL4(i)                             \
 488    ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
 489
 490 #define SET_LL(i,n)                          \
 491    { s->ll16[i] = (UInt16)(n & 0x0000ffff);  \
 492      SET_LL4(i, n >> 16);                    \
 493    }
 494
 495 #define GET_LL(i) \
 496    (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
 497
 498 #define BZ_GET_SMALL(cccc)                            \
 499       cccc = BZ2_indexIntoF ( s->tPos, s->cftab );    \
 500       s->tPos = GET_LL(s->tPos);
 501
 502
 503 /*-- externs for decompression. --*/
 504
 505 extern Int32
 506 BZ2_indexIntoF ( Int32, Int32* );
 507
 508 extern Int32
 509 BZ2_decompress ( DState* );
 510
 511 extern void
 512 BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
 513                            Int32,  Int32, Int32 );
 514
 515
 516 #endif
 517
 518
 519 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
 520
 521 #ifdef BZ_NO_STDIO
 522 #ifndef NULL
 523 #define NULL 0
 524 #endif
 525 #endif
 526
 527
 528 /*-------------------------------------------------------------*/
 529 /*--- end                                   bzlib_private.h ---*/
 530 /*-------------------------------------------------------------*/