release/src/router/busybox/archival/libarchive/bz/bzlib_private.h

   1 /*
   2  * bzip2 is written by Julian Seward <jseward@bzip.org>.
   3  * Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>.
   4  * See README and LICENSE files in this directory for more information.
   5  */
   6
   7 /*-------------------------------------------------------------*/
   8 /*--- Private header file for the library.                  ---*/
   9 /*---                                       bzlib_private.h ---*/
  10 /*-------------------------------------------------------------*/
  11
  12 /* ------------------------------------------------------------------
  13 This file is part of bzip2/libbzip2, a program and library for
  14 lossless, block-sorting data compression.
  15
  16 bzip2/libbzip2 version 1.0.4 of 20 December 2006
  17 Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
  18
  19 Please read the WARNING, DISCLAIMER and PATENTS sections in the
  20 README file.
  21
  22 This program is released under the terms of the license contained
  23 in the file LICENSE.
  24 ------------------------------------------------------------------ */
  25
  26 /* #include "bzlib.h" */
  27
  28 /*-- General stuff. --*/
  29
  30 typedef unsigned char Bool;
  31
  32 #define True  ((Bool)1)
  33 #define False ((Bool)0)
  34
  35 #if BZ_LIGHT_DEBUG
  36 static void bz_assert_fail(int errcode) NORETURN;
  37 #define AssertH(cond, errcode) \
  38 do { \
  39         if (!(cond)) \
  40                 bz_assert_fail(errcode); \
  41 } while (0)
  42 #else
  43 #define AssertH(cond, msg) do { } while (0)
  44 #endif
  45
  46 #if BZ_DEBUG
  47 #define AssertD(cond, msg) \
  48 do { \
  49         if (!(cond)) \
  50                 bb_error_msg_and_die("(debug build): internal error %s", msg); \
  51 } while (0)
  52 #else
  53 #define AssertD(cond, msg) do { } while (0)
  54 #endif
  55
  56
  57 /*-- Header bytes. --*/
  58
  59 #define BZ_HDR_B 0x42   /* 'B' */
  60 #define BZ_HDR_Z 0x5a   /* 'Z' */
  61 #define BZ_HDR_h 0x68   /* 'h' */
  62 #define BZ_HDR_0 0x30   /* '0' */
  63
  64 #define BZ_HDR_BZh0 0x425a6830
  65
  66 /*-- Constants for the back end. --*/
  67
  68 #define BZ_MAX_ALPHA_SIZE 258
  69 #define BZ_MAX_CODE_LEN    23
  70
  71 #define BZ_RUNA 0
  72 #define BZ_RUNB 1
  73
  74 #define BZ_N_GROUPS 6
  75 #define BZ_G_SIZE   50
  76 #define BZ_N_ITERS  4
  77
  78 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
  79
  80
  81 /*-- Stuff for doing CRCs. --*/
  82
  83 #define BZ_INITIALISE_CRC(crcVar) \
  84 { \
  85         crcVar = 0xffffffffL; \
  86 }
  87
  88 #define BZ_FINALISE_CRC(crcVar) \
  89 { \
  90         crcVar = ~(crcVar); \
  91 }
  92
  93 #define BZ_UPDATE_CRC(s, crcVar, cha) \
  94 { \
  95         crcVar = (crcVar << 8) ^ s->crc32table[(crcVar >> 24) ^ ((uint8_t)cha)]; \
  96 }
  97
  98
  99 /*-- States and modes for compression. --*/
 100
 101 #define BZ_M_IDLE      1
 102 #define BZ_M_RUNNING   2
 103 #define BZ_M_FLUSHING  3
 104 #define BZ_M_FINISHING 4
 105
 106 #define BZ_S_OUTPUT    1
 107 #define BZ_S_INPUT     2
 108
 109 #define BZ_N_RADIX 2
 110 #define BZ_N_QSORT 12
 111 #define BZ_N_SHELL 18
 112 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
 113
 114
 115 /*-- Structure holding all the compression-side stuff. --*/
 116
 117 typedef struct EState {
 118         /* pointer back to the struct bz_stream */
 119         bz_stream *strm;
 120
 121         /* mode this stream is in, and whether inputting */
 122         /* or outputting data */
 123         int32_t  mode;
 124         int32_t  state;
 125
 126         /* remembers avail_in when flush/finish requested */
 127 /* bbox: not needed, strm->avail_in always has the same value */
 128 /* commented out with '//#' throughout the code */
 129         /* uint32_t avail_in_expect; */
 130
 131         /* for doing the block sorting */
 132         int32_t  origPtr;
 133         uint32_t *arr1;
 134         uint32_t *arr2;
 135         uint32_t *ftab;
 136
 137         /* aliases for arr1 and arr2 */
 138         uint32_t *ptr;
 139         uint8_t  *block;
 140         uint16_t *mtfv;
 141         uint8_t  *zbits;
 142
 143         /* guess what */
 144         uint32_t *crc32table;
 145
 146         /* run-length-encoding of the input */
 147         uint32_t state_in_ch;
 148         int32_t  state_in_len;
 149
 150         /* input and output limits and current posns */
 151         int32_t  nblock;
 152         int32_t  nblockMAX;
 153         int32_t  numZ;
 154         int32_t  state_out_pos;
 155
 156         /* the buffer for bit stream creation */
 157         uint32_t bsBuff;
 158         int32_t  bsLive;
 159
 160         /* block and combined CRCs */
 161         uint32_t blockCRC;
 162         uint32_t combinedCRC;
 163
 164         /* misc administratium */
 165         int32_t  blockNo;
 166         int32_t  blockSize100k;
 167
 168         /* stuff for coding the MTF values */
 169         int32_t  nMTF;
 170
 171         /* map of bytes used in block */
 172         int32_t  nInUse;
 173         Bool     inUse[256] ALIGNED(sizeof(long));
 174         uint8_t  unseqToSeq[256];
 175
 176         /* stuff for coding the MTF values */
 177         int32_t  mtfFreq    [BZ_MAX_ALPHA_SIZE];
 178         uint8_t  selector   [BZ_MAX_SELECTORS];
 179         uint8_t  selectorMtf[BZ_MAX_SELECTORS];
 180
 181         uint8_t  len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 182
 183         /* stack-saving measures: these can be local, but they are too big */
 184         int32_t  sendMTFValues__code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 185         int32_t  sendMTFValues__rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 186 #if CONFIG_BZIP2_FAST >= 5
 187         /* second dimension: only 3 needed; 4 makes index calculations faster */
 188         uint32_t sendMTFValues__len_pack[BZ_MAX_ALPHA_SIZE][4];
 189 #endif
 190         int32_t  BZ2_hbMakeCodeLengths__heap  [BZ_MAX_ALPHA_SIZE + 2];
 191         int32_t  BZ2_hbMakeCodeLengths__weight[BZ_MAX_ALPHA_SIZE * 2];
 192         int32_t  BZ2_hbMakeCodeLengths__parent[BZ_MAX_ALPHA_SIZE * 2];
 193
 194         int32_t  mainSort__runningOrder[256];
 195         int32_t  mainSort__copyStart[256];
 196         int32_t  mainSort__copyEnd[256];
 197 } EState;
 198
 199
 200 /*-- compression. --*/
 201
 202 static void
 203 BZ2_blockSort(EState*);
 204
 205 static void
 206 BZ2_compressBlock(EState*, int);
 207
 208 static void
 209 BZ2_bsInitWrite(EState*);
 210
 211 static void
 212 BZ2_hbAssignCodes(int32_t*, uint8_t*, int32_t, int32_t, int32_t);
 213
 214 static void
 215 BZ2_hbMakeCodeLengths(EState*, uint8_t*, int32_t*, int32_t, int32_t);
 216
 217 /*-------------------------------------------------------------*/
 218 /*--- end                                   bzlib_private.h ---*/
 219 /*-------------------------------------------------------------*/