LXR uboot/lib/bzip2/bzlib

   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/*-- General stuff. --*/
  81
  82#define BZ_VERSION  "1.0.2, 30-Dec-2001"
  83
  84typedef char            Char;
  85typedef unsigned char   Bool;
  86typedef unsigned char   UChar;
  87typedef int             Int32;
  88typedef unsigned int    UInt32;
  89typedef short           Int16;
  90typedef unsigned short  UInt16;
  91
  92#define True  ((Bool)1)
  93#define False ((Bool)0)
  94
  95#ifndef __GNUC__
  96#define __inline__  /* */
  97#endif
  98
  99#ifndef BZ_NO_STDIO
 100extern void BZ2_bz__AssertH__fail ( int errcode );
 101#define AssertH(cond,errcode) \
 102   { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }
 103#if BZ_DEBUG
 104#define AssertD(cond,msg) \
 105   { if (!(cond)) {       \
 106      fprintf ( stderr,   \
 107        "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\
 108      exit(1); \
 109   }}
 110#else
 111#define AssertD(cond,msg) /* */
 112#endif
 113#define VPrintf0(zf) \
 114   fprintf(stderr,zf)
 115#define VPrintf1(zf,za1) \
 116   fprintf(stderr,zf,za1)
 117#define VPrintf2(zf,za1,za2) \
 118   fprintf(stderr,zf,za1,za2)
 119#define VPrintf3(zf,za1,za2,za3) \
 120   fprintf(stderr,zf,za1,za2,za3)
 121#define VPrintf4(zf,za1,za2,za3,za4) \
 122   fprintf(stderr,zf,za1,za2,za3,za4)
 123#define VPrintf5(zf,za1,za2,za3,za4,za5) \
 124   fprintf(stderr,zf,za1,za2,za3,za4,za5)
 125#else
 126extern void bz_internal_error ( int errcode );
 127#define AssertH(cond,errcode) \
 128   { if (!(cond)) bz_internal_error ( errcode ); }
 129#define AssertD(cond,msg) /* */
 130#define VPrintf0(zf) /* */
 131#define VPrintf1(zf,za1) /* */
 132#define VPrintf2(zf,za1,za2) /* */
 133#define VPrintf3(zf,za1,za2,za3) /* */
 134#define VPrintf4(zf,za1,za2,za3,za4) /* */
 135#define VPrintf5(zf,za1,za2,za3,za4,za5) /* */
 136#endif
 137
 138
 139#define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
 140#define BZFREE(ppp)  (strm->bzfree)(strm->opaque,(ppp))
 141
 142
 143/*-- Header bytes. --*/
 144
 145#define BZ_HDR_B 0x42   /* 'B' */
 146#define BZ_HDR_Z 0x5a   /* 'Z' */
 147#define BZ_HDR_h 0x68   /* 'h' */
 148#define BZ_HDR_0 0x30   /* '0' */
 149
 150/*-- Constants for the back end. --*/
 151
 152#define BZ_MAX_ALPHA_SIZE 258
 153#define BZ_MAX_CODE_LEN    23
 154
 155#define BZ_RUNA 0
 156#define BZ_RUNB 1
 157
 158#define BZ_N_GROUPS 6
 159#define BZ_G_SIZE   50
 160#define BZ_N_ITERS  4
 161
 162#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
 163
 164
 165/*-- Stuff for randomising repetitive blocks. --*/
 166
 167extern Int32 BZ2_rNums[512];
 168
 169#define BZ_RAND_DECLS                          \
 170   Int32 rNToGo;                               \
 171   Int32 rTPos                                 \
 172
 173#define BZ_RAND_INIT_MASK                      \
 174   s->rNToGo = 0;                              \
 175   s->rTPos  = 0                               \
 176
 177#define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
 178
 179#define BZ_RAND_UPD_MASK                       \
 180   if (s->rNToGo == 0) {                       \
 181      s->rNToGo = BZ2_rNums[s->rTPos];         \
 182      s->rTPos++;                              \
 183      if (s->rTPos == 512) s->rTPos = 0;       \
 184   }                                           \
 185   s->rNToGo--;
 186
 187
 188/*-- Stuff for doing CRCs. --*/
 189
 190extern UInt32 BZ2_crc32Table[256];
 191
 192#define BZ_INITIALISE_CRC(crcVar)              \
 193{                                              \
 194   crcVar = 0xffffffffL;                       \
 195}
 196
 197#define BZ_FINALISE_CRC(crcVar)                \
 198{                                              \
 199   crcVar = ~(crcVar);                         \
 200}
 201
 202#define BZ_UPDATE_CRC(crcVar,cha)              \
 203{                                              \
 204   crcVar = (crcVar << 8) ^                    \
 205            BZ2_crc32Table[(crcVar >> 24) ^    \
 206                           ((UChar)cha)];      \
 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/*-- Structure holding all the compression-side stuff. --*/
 227
 228typedef
 229   struct {
 230      /* pointer back to the struct bz_stream */
 231      bz_stream* strm;
 232
 233      /* mode this stream is in, and whether inputting */
 234      /* or outputting data */
 235      Int32    mode;
 236      Int32    state;
 237
 238      /* remembers avail_in when flush/finish requested */
 239      UInt32   avail_in_expect;
 240
 241      /* for doing the block sorting */
 242      UInt32*  arr1;
 243      UInt32*  arr2;
 244      UInt32*  ftab;
 245      Int32    origPtr;
 246
 247      /* aliases for arr1 and arr2 */
 248      UInt32*  ptr;
 249      UChar*   block;
 250      UInt16*  mtfv;
 251      UChar*   zbits;
 252
 253      /* for deciding when to use the fallback sorting algorithm */
 254      Int32    workFactor;
 255
 256      /* run-length-encoding of the input */
 257      UInt32   state_in_ch;
 258      Int32    state_in_len;
 259      BZ_RAND_DECLS;
 260
 261      /* input and output limits and current posns */
 262      Int32    nblock;
 263      Int32    nblockMAX;
 264      Int32    numZ;
 265      Int32    state_out_pos;
 266
 267      /* map of bytes used in block */
 268      Int32    nInUse;
 269      Bool     inUse[256];
 270      UChar    unseqToSeq[256];
 271
 272      /* the buffer for bit stream creation */
 273      UInt32   bsBuff;
 274      Int32    bsLive;
 275
 276      /* block and combined CRCs */
 277      UInt32   blockCRC;
 278      UInt32   combinedCRC;
 279
 280      /* misc administratium */
 281      Int32    verbosity;
 282      Int32    blockNo;
 283      Int32    blockSize100k;
 284
 285      /* stuff for coding the MTF values */
 286      Int32    nMTF;
 287      Int32    mtfFreq    [BZ_MAX_ALPHA_SIZE];
 288      UChar    selector   [BZ_MAX_SELECTORS];
 289      UChar    selectorMtf[BZ_MAX_SELECTORS];
 290
 291      UChar    len     [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 292      Int32    code    [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 293      Int32    rfreq   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 294      /* second dimension: only 3 needed; 4 makes index calculations faster */
 295      UInt32   len_pack[BZ_MAX_ALPHA_SIZE][4];
 296
 297   }
 298   EState;
 299
 300
 301/*-- externs for compression. --*/
 302
 303extern void
 304BZ2_blockSort ( EState* );
 305
 306extern void
 307BZ2_compressBlock ( EState*, Bool );
 308
 309extern void
 310BZ2_bsInitWrite ( EState* );
 311
 312extern void
 313BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
 314
 315extern void
 316BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
 317
 318
 319/*-- states for decompression. --*/
 320
 321#define BZ_X_IDLE        1
 322#define BZ_X_OUTPUT      2
 323
 324#define BZ_X_MAGIC_1     10
 325#define BZ_X_MAGIC_2     11
 326#define BZ_X_MAGIC_3     12
 327#define BZ_X_MAGIC_4     13
 328#define BZ_X_BLKHDR_1    14
 329#define BZ_X_BLKHDR_2    15
 330#define BZ_X_BLKHDR_3    16
 331#define BZ_X_BLKHDR_4    17
 332#define BZ_X_BLKHDR_5    18
 333#define BZ_X_BLKHDR_6    19
 334#define BZ_X_BCRC_1      20
 335#define BZ_X_BCRC_2      21
 336#define BZ_X_BCRC_3      22
 337#define BZ_X_BCRC_4      23
 338#define BZ_X_RANDBIT     24
 339#define BZ_X_ORIGPTR_1   25
 340#define BZ_X_ORIGPTR_2   26
 341#define BZ_X_ORIGPTR_3   27
 342#define BZ_X_MAPPING_1   28
 343#define BZ_X_MAPPING_2   29
 344#define BZ_X_SELECTOR_1  30
 345#define BZ_X_SELECTOR_2  31
 346#define BZ_X_SELECTOR_3  32
 347#define BZ_X_CODING_1    33
 348#define BZ_X_CODING_2    34
 349#define BZ_X_CODING_3    35
 350#define BZ_X_MTF_1       36
 351#define BZ_X_MTF_2       37
 352#define BZ_X_MTF_3       38
 353#define BZ_X_MTF_4       39
 354#define BZ_X_MTF_5       40
 355#define BZ_X_MTF_6       41
 356#define BZ_X_ENDHDR_2    42
 357#define BZ_X_ENDHDR_3    43
 358#define BZ_X_ENDHDR_4    44
 359#define BZ_X_ENDHDR_5    45
 360#define BZ_X_ENDHDR_6    46
 361#define BZ_X_CCRC_1      47
 362#define BZ_X_CCRC_2      48
 363#define BZ_X_CCRC_3      49
 364#define BZ_X_CCRC_4      50
 365
 366
 367/*-- Constants for the fast MTF decoder. --*/
 368
 369#define MTFA_SIZE 4096
 370#define MTFL_SIZE 16
 371
 372
 373/*-- Structure holding all the decompression-side stuff. --*/
 374
 375typedef
 376   struct {
 377      /* pointer back to the struct bz_stream */
 378      bz_stream* strm;
 379
 380      /* state indicator for this stream */
 381      Int32    state;
 382
 383      /* for doing the final run-length decoding */
 384      UChar    state_out_ch;
 385      Int32    state_out_len;
 386      Bool     blockRandomised;
 387      BZ_RAND_DECLS;
 388
 389      /* the buffer for bit stream reading */
 390      UInt32   bsBuff;
 391      Int32    bsLive;
 392
 393      /* misc administratium */
 394      Int32    blockSize100k;
 395      Bool     smallDecompress;
 396      Int32    currBlockNo;
 397      Int32    verbosity;
 398
 399      /* for undoing the Burrows-Wheeler transform */
 400      Int32    origPtr;
 401      UInt32   tPos;
 402      Int32    k0;
 403      Int32    unzftab[256];
 404      Int32    nblock_used;
 405      Int32    cftab[257];
 406      Int32    cftabCopy[257];
 407
 408      /* for undoing the Burrows-Wheeler transform (FAST) */
 409      UInt32   *tt;
 410
 411      /* for undoing the Burrows-Wheeler transform (SMALL) */
 412      UInt16   *ll16;
 413      UChar    *ll4;
 414
 415      /* stored and calculated CRCs */
 416      UInt32   storedBlockCRC;
 417      UInt32   storedCombinedCRC;
 418      UInt32   calculatedBlockCRC;
 419      UInt32   calculatedCombinedCRC;
 420
 421      /* map of bytes used in block */
 422      Int32    nInUse;
 423      Bool     inUse[256];
 424      Bool     inUse16[16];
 425      UChar    seqToUnseq[256];
 426
 427      /* for decoding the MTF values */
 428      UChar    mtfa   [MTFA_SIZE];
 429      Int32    mtfbase[256 / MTFL_SIZE];
 430      UChar    selector   [BZ_MAX_SELECTORS];
 431      UChar    selectorMtf[BZ_MAX_SELECTORS];
 432      UChar    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 433
 434      Int32    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 435      Int32    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 436      Int32    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 437      Int32    minLens[BZ_N_GROUPS];
 438
 439      /* save area for scalars in the main decompress code */
 440      Int32    save_i;
 441      Int32    save_j;
 442      Int32    save_t;
 443      Int32    save_alphaSize;
 444      Int32    save_nGroups;
 445      Int32    save_nSelectors;
 446      Int32    save_EOB;
 447      Int32    save_groupNo;
 448      Int32    save_groupPos;
 449      Int32    save_nextSym;
 450      Int32    save_nblockMAX;
 451      Int32    save_nblock;
 452      Int32    save_es;
 453      Int32    save_N;
 454      Int32    save_curr;
 455      Int32    save_zt;
 456      Int32    save_zn;
 457      Int32    save_zvec;
 458      Int32    save_zj;
 459      Int32    save_gSel;
 460      Int32    save_gMinlen;
 461      Int32*   save_gLimit;
 462      Int32*   save_gBase;
 463      Int32*   save_gPerm;
 464
 465   }
 466   DState;
 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
 505extern Int32
 506BZ2_indexIntoF ( Int32, Int32* );
 507
 508extern Int32
 509BZ2_decompress ( DState* );
 510
 511extern void
 512BZ2_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/*-------------------------------------------------------------*/
 531