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 /*-------------------------------------------------------------*/ 220