LLVM API Documentation
00001 00002 /*-------------------------------------------------------------*/ 00003 /*--- Private header file for the library. ---*/ 00004 /*--- bzlib_private.h ---*/ 00005 /*-------------------------------------------------------------*/ 00006 00007 /*-- 00008 This file is a part of bzip2 and/or libbzip2, a program and 00009 library for lossless, block-sorting data compression. 00010 00011 Copyright (C) 1996-2002 Julian R Seward. All rights reserved. 00012 00013 Redistribution and use in source and binary forms, with or without 00014 modification, are permitted provided that the following conditions 00015 are met: 00016 00017 1. Redistributions of source code must retain the above copyright 00018 notice, this list of conditions and the following disclaimer. 00019 00020 2. The origin of this software must not be misrepresented; you must 00021 not claim that you wrote the original software. If you use this 00022 software in a product, an acknowledgment in the product 00023 documentation would be appreciated but is not required. 00024 00025 3. Altered source versions must be plainly marked as such, and must 00026 not be misrepresented as being the original software. 00027 00028 4. The name of the author may not be used to endorse or promote 00029 products derived from this software without specific prior written 00030 permission. 00031 00032 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 00033 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 00034 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00035 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 00036 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00037 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 00038 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 00039 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 00040 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00041 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00042 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00043 00044 Julian Seward, Cambridge, UK. 00045 jseward@acm.org 00046 bzip2/libbzip2 version 1.0 of 21 March 2000 00047 00048 This program is based on (at least) the work of: 00049 Mike Burrows 00050 David Wheeler 00051 Peter Fenwick 00052 Alistair Moffat 00053 Radford Neal 00054 Ian H. Witten 00055 Robert Sedgewick 00056 Jon L. Bentley 00057 00058 For more information on these sources, see the manual. 00059 --*/ 00060 00061 00062 #ifndef _BZLIB_PRIVATE_H 00063 #define _BZLIB_PRIVATE_H 00064 00065 #include <stdlib.h> 00066 00067 #ifndef BZ_NO_STDIO 00068 #include <stdio.h> 00069 #include <ctype.h> 00070 #include <string.h> 00071 #endif 00072 00073 #include "bzlib.h" 00074 00075 00076 00077 /*-- General stuff. --*/ 00078 00079 #define BZ_VERSION "1.0.2, 30-Dec-2001" 00080 00081 typedef char Char; 00082 typedef unsigned char Bool; 00083 typedef unsigned char UChar; 00084 typedef int Int32; 00085 typedef unsigned int UInt32; 00086 typedef short Int16; 00087 typedef unsigned short UInt16; 00088 00089 #define True ((Bool)1) 00090 #define False ((Bool)0) 00091 00092 #ifndef __GNUC__ 00093 #define __inline__ /* */ 00094 #endif 00095 00096 #ifndef BZ_NO_STDIO 00097 extern void BZ2_bz__AssertH__fail ( int errcode ); 00098 #define AssertH(cond,errcode) \ 00099 { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); } 00100 #if BZ_DEBUG 00101 #define AssertD(cond,msg) \ 00102 { if (!(cond)) { \ 00103 fprintf ( stderr, \ 00104 "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\ 00105 exit(1); \ 00106 }} 00107 #else 00108 #define AssertD(cond,msg) /* */ 00109 #endif 00110 #define VPrintf0(zf) \ 00111 fprintf(stderr,zf) 00112 #define VPrintf1(zf,za1) \ 00113 fprintf(stderr,zf,za1) 00114 #define VPrintf2(zf,za1,za2) \ 00115 fprintf(stderr,zf,za1,za2) 00116 #define VPrintf3(zf,za1,za2,za3) \ 00117 fprintf(stderr,zf,za1,za2,za3) 00118 #define VPrintf4(zf,za1,za2,za3,za4) \ 00119 fprintf(stderr,zf,za1,za2,za3,za4) 00120 #define VPrintf5(zf,za1,za2,za3,za4,za5) \ 00121 fprintf(stderr,zf,za1,za2,za3,za4,za5) 00122 #else 00123 extern void bz_internal_error ( int errcode ); 00124 #define AssertH(cond,errcode) \ 00125 { if (!(cond)) bz_internal_error ( errcode ); } 00126 #define AssertD(cond,msg) /* */ 00127 #define VPrintf0(zf) /* */ 00128 #define VPrintf1(zf,za1) /* */ 00129 #define VPrintf2(zf,za1,za2) /* */ 00130 #define VPrintf3(zf,za1,za2,za3) /* */ 00131 #define VPrintf4(zf,za1,za2,za3,za4) /* */ 00132 #define VPrintf5(zf,za1,za2,za3,za4,za5) /* */ 00133 #endif 00134 00135 00136 #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1) 00137 #define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp)) 00138 00139 00140 /*-- Header bytes. --*/ 00141 00142 #define BZ_HDR_B 0x42 /* 'B' */ 00143 #define BZ_HDR_Z 0x5a /* 'Z' */ 00144 #define BZ_HDR_h 0x68 /* 'h' */ 00145 #define BZ_HDR_0 0x30 /* '0' */ 00146 00147 /*-- Constants for the back end. --*/ 00148 00149 #define BZ_MAX_ALPHA_SIZE 258 00150 #define BZ_MAX_CODE_LEN 23 00151 00152 #define BZ_RUNA 0 00153 #define BZ_RUNB 1 00154 00155 #define BZ_N_GROUPS 6 00156 #define BZ_G_SIZE 50 00157 #define BZ_N_ITERS 4 00158 00159 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) 00160 00161 00162 00163 /*-- Stuff for randomising repetitive blocks. --*/ 00164 00165 extern Int32 BZ2_rNums[512]; 00166 00167 #define BZ_RAND_DECLS \ 00168 Int32 rNToGo; \ 00169 Int32 rTPos \ 00170 00171 #define BZ_RAND_INIT_MASK \ 00172 s->rNToGo = 0; \ 00173 s->rTPos = 0 \ 00174 00175 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0) 00176 00177 #define BZ_RAND_UPD_MASK \ 00178 if (s->rNToGo == 0) { \ 00179 s->rNToGo = BZ2_rNums[s->rTPos]; \ 00180 s->rTPos++; \ 00181 if (s->rTPos == 512) s->rTPos = 0; \ 00182 } \ 00183 s->rNToGo--; 00184 00185 00186 00187 /*-- Stuff for doing CRCs. --*/ 00188 00189 extern UInt32 BZ2_crc32Table[256]; 00190 00191 #define BZ_INITIALISE_CRC(crcVar) \ 00192 { \ 00193 crcVar = 0xffffffffL; \ 00194 } 00195 00196 #define BZ_FINALISE_CRC(crcVar) \ 00197 { \ 00198 crcVar = ~(crcVar); \ 00199 } 00200 00201 #define BZ_UPDATE_CRC(crcVar,cha) \ 00202 { \ 00203 crcVar = (crcVar << 8) ^ \ 00204 BZ2_crc32Table[(crcVar >> 24) ^ \ 00205 ((UChar)cha)]; \ 00206 } 00207 00208 00209 00210 /*-- States and modes for compression. --*/ 00211 00212 #define BZ_M_IDLE 1 00213 #define BZ_M_RUNNING 2 00214 #define BZ_M_FLUSHING 3 00215 #define BZ_M_FINISHING 4 00216 00217 #define BZ_S_OUTPUT 1 00218 #define BZ_S_INPUT 2 00219 00220 #define BZ_N_RADIX 2 00221 #define BZ_N_QSORT 12 00222 #define BZ_N_SHELL 18 00223 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2) 00224 00225 00226 00227 00228 /*-- Structure holding all the compression-side stuff. --*/ 00229 00230 typedef 00231 struct { 00232 /* pointer back to the struct bz_stream */ 00233 bz_stream* strm; 00234 00235 /* mode this stream is in, and whether inputting */ 00236 /* or outputting data */ 00237 Int32 mode; 00238 Int32 state; 00239 00240 /* remembers avail_in when flush/finish requested */ 00241 UInt32 avail_in_expect; 00242 00243 /* for doing the block sorting */ 00244 UInt32* arr1; 00245 UInt32* arr2; 00246 UInt32* ftab; 00247 Int32 origPtr; 00248 00249 /* aliases for arr1 and arr2 */ 00250 UInt32* ptr; 00251 UChar* block; 00252 UInt16* mtfv; 00253 UChar* zbits; 00254 00255 /* for deciding when to use the fallback sorting algorithm */ 00256 Int32 workFactor; 00257 00258 /* run-length-encoding of the input */ 00259 UInt32 state_in_ch; 00260 Int32 state_in_len; 00261 BZ_RAND_DECLS; 00262 00263 /* input and output limits and current posns */ 00264 Int32 nblock; 00265 Int32 nblockMAX; 00266 Int32 numZ; 00267 Int32 state_out_pos; 00268 00269 /* map of bytes used in block */ 00270 Int32 nInUse; 00271 Bool inUse[256]; 00272 UChar unseqToSeq[256]; 00273 00274 /* the buffer for bit stream creation */ 00275 UInt32 bsBuff; 00276 Int32 bsLive; 00277 00278 /* block and combined CRCs */ 00279 UInt32 blockCRC; 00280 UInt32 combinedCRC; 00281 00282 /* misc administratium */ 00283 Int32 verbosity; 00284 Int32 blockNo; 00285 Int32 blockSize100k; 00286 00287 /* stuff for coding the MTF values */ 00288 Int32 nMTF; 00289 Int32 mtfFreq [BZ_MAX_ALPHA_SIZE]; 00290 UChar selector [BZ_MAX_SELECTORS]; 00291 UChar selectorMtf[BZ_MAX_SELECTORS]; 00292 00293 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00294 Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00295 Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00296 /* second dimension: only 3 needed; 4 makes index calculations faster */ 00297 UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4]; 00298 00299 } 00300 EState; 00301 00302 00303 00304 /*-- externs for compression. --*/ 00305 00306 extern void 00307 BZ2_blockSort ( EState* ); 00308 00309 extern void 00310 BZ2_compressBlock ( EState*, Bool ); 00311 00312 extern void 00313 BZ2_bsInitWrite ( EState* ); 00314 00315 extern void 00316 BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 ); 00317 00318 extern void 00319 BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 ); 00320 00321 00322 00323 /*-- states for decompression. --*/ 00324 00325 #define BZ_X_IDLE 1 00326 #define BZ_X_OUTPUT 2 00327 00328 #define BZ_X_MAGIC_1 10 00329 #define BZ_X_MAGIC_2 11 00330 #define BZ_X_MAGIC_3 12 00331 #define BZ_X_MAGIC_4 13 00332 #define BZ_X_BLKHDR_1 14 00333 #define BZ_X_BLKHDR_2 15 00334 #define BZ_X_BLKHDR_3 16 00335 #define BZ_X_BLKHDR_4 17 00336 #define BZ_X_BLKHDR_5 18 00337 #define BZ_X_BLKHDR_6 19 00338 #define BZ_X_BCRC_1 20 00339 #define BZ_X_BCRC_2 21 00340 #define BZ_X_BCRC_3 22 00341 #define BZ_X_BCRC_4 23 00342 #define BZ_X_RANDBIT 24 00343 #define BZ_X_ORIGPTR_1 25 00344 #define BZ_X_ORIGPTR_2 26 00345 #define BZ_X_ORIGPTR_3 27 00346 #define BZ_X_MAPPING_1 28 00347 #define BZ_X_MAPPING_2 29 00348 #define BZ_X_SELECTOR_1 30 00349 #define BZ_X_SELECTOR_2 31 00350 #define BZ_X_SELECTOR_3 32 00351 #define BZ_X_CODING_1 33 00352 #define BZ_X_CODING_2 34 00353 #define BZ_X_CODING_3 35 00354 #define BZ_X_MTF_1 36 00355 #define BZ_X_MTF_2 37 00356 #define BZ_X_MTF_3 38 00357 #define BZ_X_MTF_4 39 00358 #define BZ_X_MTF_5 40 00359 #define BZ_X_MTF_6 41 00360 #define BZ_X_ENDHDR_2 42 00361 #define BZ_X_ENDHDR_3 43 00362 #define BZ_X_ENDHDR_4 44 00363 #define BZ_X_ENDHDR_5 45 00364 #define BZ_X_ENDHDR_6 46 00365 #define BZ_X_CCRC_1 47 00366 #define BZ_X_CCRC_2 48 00367 #define BZ_X_CCRC_3 49 00368 #define BZ_X_CCRC_4 50 00369 00370 00371 00372 /*-- Constants for the fast MTF decoder. --*/ 00373 00374 #define MTFA_SIZE 4096 00375 #define MTFL_SIZE 16 00376 00377 00378 00379 /*-- Structure holding all the decompression-side stuff. --*/ 00380 00381 typedef 00382 struct { 00383 /* pointer back to the struct bz_stream */ 00384 bz_stream* strm; 00385 00386 /* state indicator for this stream */ 00387 Int32 state; 00388 00389 /* for doing the final run-length decoding */ 00390 UChar state_out_ch; 00391 Int32 state_out_len; 00392 Bool blockRandomised; 00393 BZ_RAND_DECLS; 00394 00395 /* the buffer for bit stream reading */ 00396 UInt32 bsBuff; 00397 Int32 bsLive; 00398 00399 /* misc administratium */ 00400 Int32 blockSize100k; 00401 Bool smallDecompress; 00402 Int32 currBlockNo; 00403 Int32 verbosity; 00404 00405 /* for undoing the Burrows-Wheeler transform */ 00406 Int32 origPtr; 00407 UInt32 tPos; 00408 Int32 k0; 00409 Int32 unzftab[256]; 00410 Int32 nblock_used; 00411 Int32 cftab[257]; 00412 Int32 cftabCopy[257]; 00413 00414 /* for undoing the Burrows-Wheeler transform (FAST) */ 00415 UInt32 *tt; 00416 00417 /* for undoing the Burrows-Wheeler transform (SMALL) */ 00418 UInt16 *ll16; 00419 UChar *ll4; 00420 00421 /* stored and calculated CRCs */ 00422 UInt32 storedBlockCRC; 00423 UInt32 storedCombinedCRC; 00424 UInt32 calculatedBlockCRC; 00425 UInt32 calculatedCombinedCRC; 00426 00427 /* map of bytes used in block */ 00428 Int32 nInUse; 00429 Bool inUse[256]; 00430 Bool inUse16[16]; 00431 UChar seqToUnseq[256]; 00432 00433 /* for decoding the MTF values */ 00434 UChar mtfa [MTFA_SIZE]; 00435 Int32 mtfbase[256 / MTFL_SIZE]; 00436 UChar selector [BZ_MAX_SELECTORS]; 00437 UChar selectorMtf[BZ_MAX_SELECTORS]; 00438 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00439 00440 Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00441 Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00442 Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00443 Int32 minLens[BZ_N_GROUPS]; 00444 00445 /* save area for scalars in the main decompress code */ 00446 Int32 save_i; 00447 Int32 save_j; 00448 Int32 save_t; 00449 Int32 save_alphaSize; 00450 Int32 save_nGroups; 00451 Int32 save_nSelectors; 00452 Int32 save_EOB; 00453 Int32 save_groupNo; 00454 Int32 save_groupPos; 00455 Int32 save_nextSym; 00456 Int32 save_nblockMAX; 00457 Int32 save_nblock; 00458 Int32 save_es; 00459 Int32 save_N; 00460 Int32 save_curr; 00461 Int32 save_zt; 00462 Int32 save_zn; 00463 Int32 save_zvec; 00464 Int32 save_zj; 00465 Int32 save_gSel; 00466 Int32 save_gMinlen; 00467 Int32* save_gLimit; 00468 Int32* save_gBase; 00469 Int32* save_gPerm; 00470 00471 } 00472 DState; 00473 00474 00475 00476 /*-- Macros for decompression. --*/ 00477 00478 #define BZ_GET_FAST(cccc) \ 00479 s->tPos = s->tt[s->tPos]; \ 00480 cccc = (UChar)(s->tPos & 0xff); \ 00481 s->tPos >>= 8; 00482 00483 #define BZ_GET_FAST_C(cccc) \ 00484 c_tPos = c_tt[c_tPos]; \ 00485 cccc = (UChar)(c_tPos & 0xff); \ 00486 c_tPos >>= 8; 00487 00488 #define SET_LL4(i,n) \ 00489 { if (((i) & 0x1) == 0) \ 00490 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \ 00491 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ 00492 } 00493 00494 #define GET_LL4(i) \ 00495 ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF) 00496 00497 #define SET_LL(i,n) \ 00498 { s->ll16[i] = (UInt16)(n & 0x0000ffff); \ 00499 SET_LL4(i, n >> 16); \ 00500 } 00501 00502 #define GET_LL(i) \ 00503 (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16)) 00504 00505 #define BZ_GET_SMALL(cccc) \ 00506 cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \ 00507 s->tPos = GET_LL(s->tPos); 00508 00509 00510 /*-- externs for decompression. --*/ 00511 00512 extern Int32 00513 BZ2_indexIntoF ( Int32, Int32* ); 00514 00515 extern Int32 00516 BZ2_decompress ( DState* ); 00517 00518 extern void 00519 BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*, 00520 Int32, Int32, Int32 ); 00521 00522 00523 #endif 00524 00525 00526 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/ 00527 00528 #ifdef BZ_NO_STDIO 00529 #ifndef NULL 00530 #define NULL 0 00531 #endif 00532 #endif 00533 00534 00535 /*-------------------------------------------------------------*/ 00536 /*--- end bzlib_private.h ---*/ 00537 /*-------------------------------------------------------------*/