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 uint8_t mode; 124 uint8_t state; 125 126 /* misc administratium */ 127 uint8_t blockSize100k; 128 129 /* remembers avail_in when flush/finish requested */ 130 /* bbox: not needed, strm->avail_in always has the same value */ 131 /* commented out with '//#' throughout the code */ 132 /* uint32_t avail_in_expect; */ 133 134 /* for doing the block sorting */ 135 uint32_t *arr1; 136 uint32_t *arr2; 137 //uint32_t *ftab; //moved into this struct, see below 138 139 uint16_t *quadrant; 140 int32_t budget; 141 142 /* aliases for arr1 and arr2 */ 143 uint32_t *ptr; 144 uint8_t *block; 145 uint16_t *mtfv; 146 uint8_t *zbits; 147 148 /* run-length-encoding of the input */ 149 uint32_t state_in_ch; 150 int32_t state_in_len; 151 152 /* input and output limits and current posns */ 153 int32_t nblock; 154 int32_t nblockMAX; 155 //int32_t numZ; // index into s->zbits[], replaced by pointer: 156 uint8_t *posZ; 157 uint8_t *state_out_pos; 158 159 /* the buffer for bit stream creation */ 160 uint32_t bsBuff; 161 int32_t bsLive; 162 163 /* block and combined CRCs */ 164 uint32_t blockCRC; 165 uint32_t combinedCRC; 166 167 /* misc administratium */ 168 int32_t blockNo; 169 170 /* stuff for coding the MTF values */ 171 int32_t nMTF; 172 173 /* map of bytes used in block */ 174 int32_t nInUse; 175 Bool inUse[256] ALIGNED(sizeof(long)); 176 uint8_t unseqToSeq[256]; 177 178 /* stuff for coding the MTF values */ 179 int32_t mtfFreq [BZ_MAX_ALPHA_SIZE]; 180 uint8_t selector [BZ_MAX_SELECTORS]; 181 uint8_t selectorMtf[BZ_MAX_SELECTORS]; 182 183 uint8_t len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 184 185 /* guess what */ 186 uint32_t crc32table[256]; 187 188 /* for doing the block sorting */ 189 uint32_t ftab[65537]; 190 191 /* stack-saving measures: these can be local, but they are too big */ 192 int32_t sendMTFValues__code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 193 int32_t sendMTFValues__rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 194 #if BZIP2_SPEED >= 5 195 /* second dimension: only 3 needed; 4 makes index calculations faster */ 196 uint32_t sendMTFValues__len_pack[BZ_MAX_ALPHA_SIZE][4]; 197 #endif 198 int32_t BZ2_hbMakeCodeLengths__heap [BZ_MAX_ALPHA_SIZE + 2]; 199 int32_t BZ2_hbMakeCodeLengths__weight[BZ_MAX_ALPHA_SIZE * 2]; 200 int32_t BZ2_hbMakeCodeLengths__parent[BZ_MAX_ALPHA_SIZE * 2]; 201 202 int32_t mainSort__copyStart[256]; 203 int32_t mainSort__copyEnd[256]; 204 } EState; 205 206 207 /*-- compression. --*/ 208 209 static int32_t 210 BZ2_blockSort(EState*); 211 212 static void 213 BZ2_compressBlock(EState*, int); 214 215 static void 216 BZ2_bsInitWrite(EState*); 217 218 static void 219 BZ2_hbAssignCodes(int32_t*, uint8_t*, int32_t, int32_t, int32_t); 220 221 static void 222 BZ2_hbMakeCodeLengths(EState*, uint8_t*, int32_t*, int32_t, int32_t); 223 224 /*-------------------------------------------------------------*/ 225 /*--- end bzlib_private.h ---*/ 226 /*-------------------------------------------------------------*/ 227