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/* ------------------------------------------------------------------ 13This file is part of bzip2/libbzip2, a program and library for 14lossless, block-sorting data compression. 15 16bzip2/libbzip2 version 1.0.4 of 20 December 2006 17Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org> 18 19Please read the WARNING, DISCLAIMER and PATENTS sections in the 20README file. 21 22This program is released under the terms of the license contained 23in the file LICENSE. 24------------------------------------------------------------------ */ 25 26/* #include "bzlib.h" */ 27 28/*-- General stuff. --*/ 29 30typedef unsigned char Bool; 31 32#define True ((Bool)1) 33#define False ((Bool)0) 34 35#if BZ_LIGHT_DEBUG 36static void bz_assert_fail(int errcode) NORETURN; 37#define AssertH(cond, errcode) \ 38do { \ 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) \ 48do { \ 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 117typedef 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_FEATURE_SPEED >= 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 202static void 203BZ2_blockSort(EState*); 204 205static void 206BZ2_compressBlock(EState*, int); 207 208static void 209BZ2_bsInitWrite(EState*); 210 211static void 212BZ2_hbAssignCodes(int32_t*, uint8_t*, int32_t, int32_t, int32_t); 213 214static void 215BZ2_hbMakeCodeLengths(EState*, uint8_t*, int32_t*, int32_t, int32_t); 216 217/*-------------------------------------------------------------*/ 218/*--- end bzlib_private.h ---*/ 219/*-------------------------------------------------------------*/ 220