#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "bzlib.h"
Go to the source code of this file.
Compounds | |
struct | DState |
struct | EState |
Defines | |
#define | BZ_VERSION "0.9.5a" |
#define | True ((Bool)1) |
#define | False ((Bool)0) |
#define | __inline__ |
#define | AssertH(cond, errcode) { if (!(cond)) bz__AssertH__fail ( errcode ); } |
#define | AssertD(cond, msg) |
#define | VPrintf0(zf) fprintf(stderr,zf) |
#define | VPrintf1(zf, za1) fprintf(stderr,zf,za1) |
#define | VPrintf2(zf, za1, za2) fprintf(stderr,zf,za1,za2) |
#define | VPrintf3(zf, za1, za2, za3) fprintf(stderr,zf,za1,za2,za3) |
#define | VPrintf4(zf, za1, za2, za3, za4) fprintf(stderr,zf,za1,za2,za3,za4) |
#define | VPrintf5(zf, za1, za2, za3, za4, za5) fprintf(stderr,zf,za1,za2,za3,za4,za5) |
#define | BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1) |
#define | BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp)) |
#define | BZ_MAX_ALPHA_SIZE 258 |
#define | BZ_MAX_CODE_LEN 23 |
#define | BZ_RUNA 0 |
#define | BZ_RUNB 1 |
#define | BZ_N_GROUPS 6 |
#define | BZ_G_SIZE 50 |
#define | BZ_N_ITERS 4 |
#define | BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) |
#define | BZ_RAND_DECLS |
#define | BZ_RAND_INIT_MASK |
#define | BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0) |
#define | BZ_RAND_UPD_MASK |
#define | BZ_INITIALISE_CRC(crcVar) |
#define | BZ_FINALISE_CRC(crcVar) |
#define | BZ_UPDATE_CRC(crcVar, cha) |
#define | BZ_M_IDLE 1 |
#define | BZ_M_RUNNING 2 |
#define | BZ_M_FLUSHING 3 |
#define | BZ_M_FINISHING 4 |
#define | BZ_S_OUTPUT 1 |
#define | BZ_S_INPUT 2 |
#define | BZ_N_RADIX 2 |
#define | BZ_N_QSORT 12 |
#define | BZ_N_SHELL 18 |
#define | BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2) |
#define | BZ_X_IDLE 1 |
#define | BZ_X_OUTPUT 2 |
#define | BZ_X_MAGIC_1 10 |
#define | BZ_X_MAGIC_2 11 |
#define | BZ_X_MAGIC_3 12 |
#define | BZ_X_MAGIC_4 13 |
#define | BZ_X_BLKHDR_1 14 |
#define | BZ_X_BLKHDR_2 15 |
#define | BZ_X_BLKHDR_3 16 |
#define | BZ_X_BLKHDR_4 17 |
#define | BZ_X_BLKHDR_5 18 |
#define | BZ_X_BLKHDR_6 19 |
#define | BZ_X_BCRC_1 20 |
#define | BZ_X_BCRC_2 21 |
#define | BZ_X_BCRC_3 22 |
#define | BZ_X_BCRC_4 23 |
#define | BZ_X_RANDBIT 24 |
#define | BZ_X_ORIGPTR_1 25 |
#define | BZ_X_ORIGPTR_2 26 |
#define | BZ_X_ORIGPTR_3 27 |
#define | BZ_X_MAPPING_1 28 |
#define | BZ_X_MAPPING_2 29 |
#define | BZ_X_SELECTOR_1 30 |
#define | BZ_X_SELECTOR_2 31 |
#define | BZ_X_SELECTOR_3 32 |
#define | BZ_X_CODING_1 33 |
#define | BZ_X_CODING_2 34 |
#define | BZ_X_CODING_3 35 |
#define | BZ_X_MTF_1 36 |
#define | BZ_X_MTF_2 37 |
#define | BZ_X_MTF_3 38 |
#define | BZ_X_MTF_4 39 |
#define | BZ_X_MTF_5 40 |
#define | BZ_X_MTF_6 41 |
#define | BZ_X_ENDHDR_2 42 |
#define | BZ_X_ENDHDR_3 43 |
#define | BZ_X_ENDHDR_4 44 |
#define | BZ_X_ENDHDR_5 45 |
#define | BZ_X_ENDHDR_6 46 |
#define | BZ_X_CCRC_1 47 |
#define | BZ_X_CCRC_2 48 |
#define | BZ_X_CCRC_3 49 |
#define | BZ_X_CCRC_4 50 |
#define | MTFA_SIZE 4096 |
#define | MTFL_SIZE 16 |
#define | BZ_GET_FAST(cccc) |
#define | BZ_GET_FAST_C(cccc) |
#define | SET_LL4(i, n) |
#define | GET_LL4(i) ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF) |
#define | SET_LL(i, n) |
#define | GET_LL(i) (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16)) |
#define | BZ_GET_SMALL(cccc) |
Typedefs | |
typedef char | Char |
typedef unsigned char | Bool |
typedef unsigned char | UChar |
typedef int | Int32 |
typedef unsigned int | UInt32 |
typedef short | Int16 |
typedef unsigned short | UInt16 |
Functions | |
void | bz__AssertH__fail (int errcode) |
void | blockSort (EState *) |
void | compressBlock (EState *, Bool) |
void | bsInitWrite (EState *) |
void | hbAssignCodes (Int32 *, UChar *, Int32, Int32, Int32) |
void | hbMakeCodeLengths (UChar *, Int32 *, Int32, Int32) |
Int32 | indexIntoF (Int32, Int32 *) |
Int32 | decompress (DState *) |
void | hbCreateDecodeTables (Int32 *, Int32 *, Int32 *, UChar *, Int32, Int32, Int32) |
Variables | |
Int32 | rNums [512] |
UInt32 | crc32Table [256] |
|
Definition at line 108 of file bzlib_private.h. Referenced by fallbackQSort3(), generateMTFValues(), mainGtU(), and mainQSort3().
|
|
Definition at line 98 of file bzlib_private.h. Referenced by blockSort(), decompress(), fallbackQSort3(), fallbackSort(), hbMakeCodeLengths(), mainQSort3(), mainSort(), and sendMTFValues().
|
|
Definition at line 136 of file bzlib_private.h. Referenced by BZ_API(), and decompress().
|
|
Definition at line 137 of file bzlib_private.h. Referenced by BZ_API().
|
|
Value: { \ crcVar = ~(crcVar); \ } Definition at line 189 of file bzlib_private.h. Referenced by compressBlock().
|
|
Value: s->tPos = s->tt[s->tPos]; \ cccc = (UChar)(s->tPos & 0xff); \ s->tPos >>= 8; Definition at line 469 of file bzlib_private.h. Referenced by decompress(), and unRLE_obuf_to_output_FAST().
|
|
Value: c_tPos = c_tt[c_tPos]; \ cccc = (UChar)(c_tPos & 0xff); \ c_tPos >>= 8; Definition at line 474 of file bzlib_private.h. Referenced by unRLE_obuf_to_output_FAST().
|
|
Value: cccc = indexIntoF ( s->tPos, s->cftab ); \ s->tPos = GET_LL(s->tPos); Definition at line 496 of file bzlib_private.h. Referenced by decompress(), and unRLE_obuf_to_output_SMALL().
|
|
Definition at line 149 of file bzlib_private.h. |
|
Value: { \ crcVar = 0xffffffffL; \ } Definition at line 184 of file bzlib_private.h. Referenced by decompress(), and prepare_new_block().
|
|
Definition at line 142 of file bzlib_private.h. |
|
Definition at line 143 of file bzlib_private.h. |
|
Definition at line 152 of file bzlib_private.h. |
|
Definition at line 208 of file bzlib_private.h. |
|
Definition at line 207 of file bzlib_private.h. |
|
Definition at line 205 of file bzlib_private.h. |
|
Definition at line 206 of file bzlib_private.h. |
|
Definition at line 148 of file bzlib_private.h. |
|
Definition at line 150 of file bzlib_private.h. |
|
Definition at line 216 of file bzlib_private.h. |
|
Definition at line 214 of file bzlib_private.h. |
|
Definition at line 213 of file bzlib_private.h. |
|
Definition at line 215 of file bzlib_private.h. |
|
Value: Int32 rNToGo; \ Int32 rTPos \ Definition at line 160 of file bzlib_private.h. |
|
Value: s->rNToGo = 0; \ s->rTPos = 0 \ Definition at line 164 of file bzlib_private.h. |
|
Definition at line 168 of file bzlib_private.h. |
|
Value: if (s->rNToGo == 0) { \ s->rNToGo = rNums[s->rTPos]; \ s->rTPos++; \ if (s->rTPos == 512) s->rTPos = 0; \ } \ s->rNToGo--; Definition at line 170 of file bzlib_private.h. |
|
Definition at line 145 of file bzlib_private.h. |
|
Definition at line 146 of file bzlib_private.h. |
|
Definition at line 211 of file bzlib_private.h. |
|
Definition at line 210 of file bzlib_private.h. |
|
Value: { \ crcVar = (crcVar << 8) ^ \ crc32Table[(crcVar >> 24) ^ \ ((UChar)cha)]; \ } Definition at line 194 of file bzlib_private.h. Referenced by add_pair_to_block(), unRLE_obuf_to_output_FAST(), and unRLE_obuf_to_output_SMALL().
|
|
Definition at line 79 of file bzlib_private.h. |
|
Definition at line 329 of file bzlib_private.h. |
|
Definition at line 330 of file bzlib_private.h. |
|
Definition at line 331 of file bzlib_private.h. |
|
Definition at line 332 of file bzlib_private.h. |
|
Definition at line 323 of file bzlib_private.h. |
|
Definition at line 324 of file bzlib_private.h. |
|
Definition at line 325 of file bzlib_private.h. |
|
Definition at line 326 of file bzlib_private.h. |
|
Definition at line 327 of file bzlib_private.h. |
|
Definition at line 328 of file bzlib_private.h. |
|
Definition at line 356 of file bzlib_private.h. |
|
Definition at line 357 of file bzlib_private.h. |
|
Definition at line 358 of file bzlib_private.h. |
|
Definition at line 359 of file bzlib_private.h. |
|
Definition at line 342 of file bzlib_private.h. |
|
Definition at line 343 of file bzlib_private.h. |
|
Definition at line 344 of file bzlib_private.h. |
|
Definition at line 351 of file bzlib_private.h. |
|
Definition at line 352 of file bzlib_private.h. |
|
Definition at line 353 of file bzlib_private.h. |
|
Definition at line 354 of file bzlib_private.h. |
|
Definition at line 355 of file bzlib_private.h. |
|
Definition at line 316 of file bzlib_private.h. |
|
Definition at line 319 of file bzlib_private.h. |
|
Definition at line 320 of file bzlib_private.h. |
|
Definition at line 321 of file bzlib_private.h. |
|
Definition at line 322 of file bzlib_private.h. |
|
Definition at line 337 of file bzlib_private.h. |
|
Definition at line 338 of file bzlib_private.h. |
|
Definition at line 345 of file bzlib_private.h. |
|
Definition at line 346 of file bzlib_private.h. |
|
Definition at line 347 of file bzlib_private.h. |
|
Definition at line 348 of file bzlib_private.h. |
|
Definition at line 349 of file bzlib_private.h. |
|
Definition at line 350 of file bzlib_private.h. |
|
Definition at line 334 of file bzlib_private.h. |
|
Definition at line 335 of file bzlib_private.h. |
|
Definition at line 336 of file bzlib_private.h. |
|
Definition at line 317 of file bzlib_private.h. |
|
Definition at line 333 of file bzlib_private.h. |
|
Definition at line 339 of file bzlib_private.h. |
|
Definition at line 340 of file bzlib_private.h. |
|
Definition at line 341 of file bzlib_private.h. |
|
Definition at line 90 of file bzlib_private.h. |
|
Definition at line 493 of file bzlib_private.h. Referenced by decompress().
|
|
Definition at line 485 of file bzlib_private.h. |
|
Definition at line 365 of file bzlib_private.h. |
|
Definition at line 366 of file bzlib_private.h. |
|
Value: { s->ll16[i] = (UInt16)(n & 0x0000ffff); \ SET_LL4(i, n >> 16); \ } Definition at line 488 of file bzlib_private.h. Referenced by decompress().
|
|
Value: { if (((i) & 0x1) == 0) \ s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \ s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ } Definition at line 479 of file bzlib_private.h. |
|
Definition at line 89 of file bzlib_private.h. |
|
Definition at line 110 of file bzlib_private.h. Referenced by blockSort(), decompress(), fallbackSort(), mainSort(), and sendMTFValues().
|
|
Definition at line 112 of file bzlib_private.h. Referenced by compressBlock(), decompress(), fallbackSort(), and sendMTFValues().
|
|
Definition at line 114 of file bzlib_private.h. Referenced by sendMTFValues().
|
|
Definition at line 116 of file bzlib_private.h. Referenced by blockSort(), mainSort(), and sendMTFValues().
|
|
Definition at line 118 of file bzlib_private.h. Referenced by compressBlock(), and mainSort().
|
|
Definition at line 120 of file bzlib_private.h. Referenced by sendMTFValues().
|
|
Definition at line 93 of file bzlib_private.h. |
|
Definition at line 82 of file bzlib_private.h. |
|
Definition at line 81 of file bzlib_private.h. |
|
Definition at line 86 of file bzlib_private.h. |
|
Definition at line 84 of file bzlib_private.h. |
|
Definition at line 83 of file bzlib_private.h. |
|
Definition at line 87 of file bzlib_private.h. |
|
Definition at line 85 of file bzlib_private.h. |
|
Definition at line 1017 of file blocksort.c. Referenced by compressBlock().
01018 { 01019 UInt32* ptr = s->ptr; 01020 UInt16* block = s->block; 01021 UInt32* ftab = s->ftab; 01022 Int32 nblock = s->nblock; 01023 Int32 verb = s->verbosity; 01024 Int32 wfact = s->workFactor; 01025 UInt16* quadrant; 01026 Int32 budget; 01027 Int32 budgetInit; 01028 Int32 i; 01029 01030 if (nblock < 10000) { 01031 for (i = 0; i < nblock; i++) block[i] <<= 8; 01032 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); 01033 } else { 01034 quadrant = &(block[nblock+BZ_N_OVERSHOOT]); 01035 01036 /* (wfact-1) / 3 puts the default-factor-30 01037 transition point at very roughly the same place as 01038 with v0.1 and v0.9.0. 01039 Not that it particularly matters any more, since the 01040 resulting compressed stream is now the same regardless 01041 of whether or not we use the main sort or fallback sort. 01042 */ 01043 if (wfact < 1 ) wfact = 1; 01044 if (wfact > 100) wfact = 100; 01045 budgetInit = nblock * ((wfact-1) / 3); 01046 budget = budgetInit; 01047 01048 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget ); 01049 if (verb >= 3) 01050 VPrintf3 ( " %d work, %d block, ratio %5.2f\n", 01051 budgetInit - budget, 01052 nblock, 01053 (float)(budgetInit - budget) / 01054 (float)(nblock==0 ? 1 : nblock) ); 01055 if (budget < 0) { 01056 if (verb >= 2) 01057 VPrintf0 ( " too repetitive; using fallback" 01058 " sorting algorithm\n" ); 01059 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); 01060 } 01061 } 01062 01063 s->origPtr = -1; 01064 for (i = 0; i < s->nblock; i++) 01065 if (ptr[i] == 0) 01066 { s->origPtr = i; break; }; 01067 01068 AssertH( s->origPtr != -1, 1003 ); 01069 } |
|
Definition at line 81 of file bzlib/compress.c. |
|
Definition at line 86 of file bzlib.c. 00087 { 00088 fprintf(stderr, 00089 "\n\nbzip2/libbzip2, v0.9.5a: internal error number %d.\n" 00090 "This is a bug in bzip2/libbzip2, v0.9.5a. Please report\n" 00091 "it to me at: jseward@acm.org. If this happened when\n" 00092 "you were using some program which uses libbzip2 as a\n" 00093 "component, you should also report this bug to the author(s)\n" 00094 "of that program. Please make an effort to report this bug;\n" 00095 "timely and accurate bug reports eventually lead to higher\n" 00096 "quality software. Thanks. Julian Seward, 24 May 1999.\n\n", 00097 errcode 00098 ); 00099 exit(3); 00100 } |
|
Definition at line 557 of file bzlib/compress.c. 00558 { 00559 if (s->nblock > 0) { 00560 00561 BZ_FINALISE_CRC ( s->blockCRC ); 00562 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); 00563 s->combinedCRC ^= s->blockCRC; 00564 if (s->blockNo > 1) s->numZ = 0; 00565 00566 if (s->verbosity >= 2) 00567 VPrintf4( " block %d: crc = 0x%8x, " 00568 "combined CRC = 0x%8x, size = %d\n", 00569 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock ); 00570 00571 blockSort ( s ); 00572 } 00573 00574 s->zbits = (UChar*) (&((UInt16*)s->arr2)[s->nblock]); 00575 00576 /*-- If this is the first block, create the stream header. --*/ 00577 if (s->blockNo == 1) { 00578 bsInitWrite ( s ); 00579 bsPutUChar ( s, 'B' ); 00580 bsPutUChar ( s, 'Z' ); 00581 bsPutUChar ( s, 'h' ); 00582 bsPutUChar ( s, '0' + s->blockSize100k ); 00583 } 00584 00585 if (s->nblock > 0) { 00586 00587 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 ); 00588 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 ); 00589 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 ); 00590 00591 /*-- Now the block's CRC, so it is in a known place. --*/ 00592 bsPutUInt32 ( s, s->blockCRC ); 00593 00594 /*-- 00595 Now a single bit indicating (non-)randomisation. 00596 As of version 0.9.5, we use a better sorting algorithm 00597 which makes randomisation unnecessary. So always set 00598 the randomised bit to 'no'. Of course, the decoder 00599 still needs to be able to handle randomised blocks 00600 so as to maintain backwards compatibility with 00601 older versions of bzip2. 00602 --*/ 00603 bsW(s,1,0); 00604 00605 bsW ( s, 24, s->origPtr ); 00606 generateMTFValues ( s ); 00607 sendMTFValues ( s ); 00608 } 00609 00610 00611 /*-- If this is the last block, add the stream trailer. --*/ 00612 if (is_last_block) { 00613 00614 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 ); 00615 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 ); 00616 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 ); 00617 bsPutUInt32 ( s, s->combinedCRC ); 00618 if (s->verbosity >= 2) 00619 VPrintf1( " final combined CRC = 0x%x\n ", s->combinedCRC ); 00620 bsFinishWrite ( s ); 00621 } 00622 } |
|
Definition at line 136 of file decompress.c. 00137 { 00138 UChar uc; 00139 Int32 retVal; 00140 Int32 minLen, maxLen; 00141 bz_stream* strm = s->strm; 00142 00143 /* stuff that needs to be saved/restored */ 00144 Int32 i; 00145 Int32 j; 00146 Int32 t; 00147 Int32 alphaSize; 00148 Int32 nGroups; 00149 Int32 nSelectors; 00150 Int32 EOB; 00151 Int32 groupNo; 00152 Int32 groupPos; 00153 Int32 nextSym; 00154 Int32 nblockMAX; 00155 Int32 nblock; 00156 Int32 es; 00157 Int32 N; 00158 Int32 curr; 00159 Int32 zt; 00160 Int32 zn; 00161 Int32 zvec; 00162 Int32 zj; 00163 Int32 gSel; 00164 Int32 gMinlen; 00165 Int32* gLimit; 00166 Int32* gBase; 00167 Int32* gPerm; 00168 00169 if (s->state == BZ_X_MAGIC_1) { 00170 /*initialise the save area*/ 00171 s->save_i = 0; 00172 s->save_j = 0; 00173 s->save_t = 0; 00174 s->save_alphaSize = 0; 00175 s->save_nGroups = 0; 00176 s->save_nSelectors = 0; 00177 s->save_EOB = 0; 00178 s->save_groupNo = 0; 00179 s->save_groupPos = 0; 00180 s->save_nextSym = 0; 00181 s->save_nblockMAX = 0; 00182 s->save_nblock = 0; 00183 s->save_es = 0; 00184 s->save_N = 0; 00185 s->save_curr = 0; 00186 s->save_zt = 0; 00187 s->save_zn = 0; 00188 s->save_zvec = 0; 00189 s->save_zj = 0; 00190 s->save_gSel = 0; 00191 s->save_gMinlen = 0; 00192 s->save_gLimit = NULL; 00193 s->save_gBase = NULL; 00194 s->save_gPerm = NULL; 00195 } 00196 00197 /*restore from the save area*/ 00198 i = s->save_i; 00199 j = s->save_j; 00200 t = s->save_t; 00201 alphaSize = s->save_alphaSize; 00202 nGroups = s->save_nGroups; 00203 nSelectors = s->save_nSelectors; 00204 EOB = s->save_EOB; 00205 groupNo = s->save_groupNo; 00206 groupPos = s->save_groupPos; 00207 nextSym = s->save_nextSym; 00208 nblockMAX = s->save_nblockMAX; 00209 nblock = s->save_nblock; 00210 es = s->save_es; 00211 N = s->save_N; 00212 curr = s->save_curr; 00213 zt = s->save_zt; 00214 zn = s->save_zn; 00215 zvec = s->save_zvec; 00216 zj = s->save_zj; 00217 gSel = s->save_gSel; 00218 gMinlen = s->save_gMinlen; 00219 gLimit = s->save_gLimit; 00220 gBase = s->save_gBase; 00221 gPerm = s->save_gPerm; 00222 00223 retVal = BZ_OK; 00224 00225 switch (s->state) { 00226 00227 GET_UCHAR(BZ_X_MAGIC_1, uc); 00228 if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC); 00229 00230 GET_UCHAR(BZ_X_MAGIC_2, uc); 00231 if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC); 00232 00233 GET_UCHAR(BZ_X_MAGIC_3, uc) 00234 if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC); 00235 00236 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) 00237 if (s->blockSize100k < '1' || 00238 s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC); 00239 s->blockSize100k -= '0'; 00240 00241 if (s->smallDecompress) { 00242 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); 00243 s->ll4 = BZALLOC( 00244 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) 00245 ); 00246 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); 00247 } else { 00248 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); 00249 if (s->tt == NULL) RETURN(BZ_MEM_ERROR); 00250 } 00251 00252 GET_UCHAR(BZ_X_BLKHDR_1, uc); 00253 00254 if (uc == 0x17) goto endhdr_2; 00255 if (uc != 0x31) RETURN(BZ_DATA_ERROR); 00256 GET_UCHAR(BZ_X_BLKHDR_2, uc); 00257 if (uc != 0x41) RETURN(BZ_DATA_ERROR); 00258 GET_UCHAR(BZ_X_BLKHDR_3, uc); 00259 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 00260 GET_UCHAR(BZ_X_BLKHDR_4, uc); 00261 if (uc != 0x26) RETURN(BZ_DATA_ERROR); 00262 GET_UCHAR(BZ_X_BLKHDR_5, uc); 00263 if (uc != 0x53) RETURN(BZ_DATA_ERROR); 00264 GET_UCHAR(BZ_X_BLKHDR_6, uc); 00265 if (uc != 0x59) RETURN(BZ_DATA_ERROR); 00266 00267 s->currBlockNo++; 00268 if (s->verbosity >= 2) 00269 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); 00270 00271 s->storedBlockCRC = 0; 00272 GET_UCHAR(BZ_X_BCRC_1, uc); 00273 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 00274 GET_UCHAR(BZ_X_BCRC_2, uc); 00275 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 00276 GET_UCHAR(BZ_X_BCRC_3, uc); 00277 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 00278 GET_UCHAR(BZ_X_BCRC_4, uc); 00279 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); 00280 00281 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); 00282 00283 s->origPtr = 0; 00284 GET_UCHAR(BZ_X_ORIGPTR_1, uc); 00285 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 00286 GET_UCHAR(BZ_X_ORIGPTR_2, uc); 00287 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 00288 GET_UCHAR(BZ_X_ORIGPTR_3, uc); 00289 s->origPtr = (s->origPtr << 8) | ((Int32)uc); 00290 00291 /*--- Receive the mapping table ---*/ 00292 for (i = 0; i < 16; i++) { 00293 GET_BIT(BZ_X_MAPPING_1, uc); 00294 if (uc == 1) 00295 s->inUse16[i] = True; else 00296 s->inUse16[i] = False; 00297 } 00298 00299 for (i = 0; i < 256; i++) s->inUse[i] = False; 00300 00301 for (i = 0; i < 16; i++) 00302 if (s->inUse16[i]) 00303 for (j = 0; j < 16; j++) { 00304 GET_BIT(BZ_X_MAPPING_2, uc); 00305 if (uc == 1) s->inUse[i * 16 + j] = True; 00306 } 00307 makeMaps_d ( s ); 00308 alphaSize = s->nInUse+2; 00309 00310 /*--- Now the selectors ---*/ 00311 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); 00312 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); 00313 for (i = 0; i < nSelectors; i++) { 00314 j = 0; 00315 while (True) { 00316 GET_BIT(BZ_X_SELECTOR_3, uc); 00317 if (uc == 0) break; 00318 j++; 00319 if (j > 5) RETURN(BZ_DATA_ERROR); 00320 } 00321 s->selectorMtf[i] = j; 00322 } 00323 00324 /*--- Undo the MTF values for the selectors. ---*/ 00325 { 00326 UChar pos[BZ_N_GROUPS], tmp, v; 00327 for (v = 0; v < nGroups; v++) pos[v] = v; 00328 00329 for (i = 0; i < nSelectors; i++) { 00330 v = s->selectorMtf[i]; 00331 tmp = pos[v]; 00332 while (v > 0) { pos[v] = pos[v-1]; v--; } 00333 pos[0] = tmp; 00334 s->selector[i] = tmp; 00335 } 00336 } 00337 00338 /*--- Now the coding tables ---*/ 00339 for (t = 0; t < nGroups; t++) { 00340 GET_BITS(BZ_X_CODING_1, curr, 5); 00341 for (i = 0; i < alphaSize; i++) { 00342 while (True) { 00343 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); 00344 GET_BIT(BZ_X_CODING_2, uc); 00345 if (uc == 0) break; 00346 GET_BIT(BZ_X_CODING_3, uc); 00347 if (uc == 0) curr++; else curr--; 00348 } 00349 s->len[t][i] = curr; 00350 } 00351 } 00352 00353 /*--- Create the Huffman decoding tables ---*/ 00354 for (t = 0; t < nGroups; t++) { 00355 minLen = 32; 00356 maxLen = 0; 00357 for (i = 0; i < alphaSize; i++) { 00358 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 00359 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 00360 } 00361 hbCreateDecodeTables ( 00362 &(s->limit[t][0]), 00363 &(s->base[t][0]), 00364 &(s->perm[t][0]), 00365 &(s->len[t][0]), 00366 minLen, maxLen, alphaSize 00367 ); 00368 s->minLens[t] = minLen; 00369 } 00370 00371 /*--- Now the MTF values ---*/ 00372 00373 EOB = s->nInUse+1; 00374 nblockMAX = 100000 * s->blockSize100k; 00375 groupNo = -1; 00376 groupPos = 0; 00377 00378 for (i = 0; i <= 255; i++) s->unzftab[i] = 0; 00379 00380 /*-- MTF init --*/ 00381 { 00382 Int32 ii, jj, kk; 00383 kk = MTFA_SIZE-1; 00384 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { 00385 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 00386 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); 00387 kk--; 00388 } 00389 s->mtfbase[ii] = kk + 1; 00390 } 00391 } 00392 /*-- end MTF init --*/ 00393 00394 nblock = 0; 00395 00396 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); 00397 00398 while (True) { 00399 00400 if (nextSym == EOB) break; 00401 00402 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { 00403 00404 es = -1; 00405 N = 1; 00406 do { 00407 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else 00408 if (nextSym == BZ_RUNB) es = es + (1+1) * N; 00409 N = N * 2; 00410 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); 00411 } 00412 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); 00413 00414 es++; 00415 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; 00416 s->unzftab[uc] += es; 00417 00418 if (s->smallDecompress) 00419 while (es > 0) { 00420 s->ll16[nblock] = (UInt16)uc; 00421 nblock++; 00422 es--; 00423 } 00424 else 00425 while (es > 0) { 00426 s->tt[nblock] = (UInt32)uc; 00427 nblock++; 00428 es--; 00429 }; 00430 00431 if (nblock > nblockMAX) RETURN(BZ_DATA_ERROR); 00432 continue; 00433 00434 } else { 00435 00436 if (nblock > nblockMAX) RETURN(BZ_DATA_ERROR); 00437 00438 /*-- uc = MTF ( nextSym-1 ) --*/ 00439 { 00440 Int32 ii, jj, kk, pp, lno, off; 00441 UInt32 nn; 00442 nn = (UInt32)(nextSym - 1); 00443 00444 if (nn < MTFL_SIZE) { 00445 /* avoid general-case expense */ 00446 pp = s->mtfbase[0]; 00447 uc = s->mtfa[pp+nn]; 00448 while (nn > 3) { 00449 Int32 z = pp+nn; 00450 s->mtfa[(z) ] = s->mtfa[(z)-1]; 00451 s->mtfa[(z)-1] = s->mtfa[(z)-2]; 00452 s->mtfa[(z)-2] = s->mtfa[(z)-3]; 00453 s->mtfa[(z)-3] = s->mtfa[(z)-4]; 00454 nn -= 4; 00455 } 00456 while (nn > 0) { 00457 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 00458 }; 00459 s->mtfa[pp] = uc; 00460 } else { 00461 /* general case */ 00462 lno = nn / MTFL_SIZE; 00463 off = nn % MTFL_SIZE; 00464 pp = s->mtfbase[lno] + off; 00465 uc = s->mtfa[pp]; 00466 while (pp > s->mtfbase[lno]) { 00467 s->mtfa[pp] = s->mtfa[pp-1]; pp--; 00468 }; 00469 s->mtfbase[lno]++; 00470 while (lno > 0) { 00471 s->mtfbase[lno]--; 00472 s->mtfa[s->mtfbase[lno]] 00473 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; 00474 lno--; 00475 } 00476 s->mtfbase[0]--; 00477 s->mtfa[s->mtfbase[0]] = uc; 00478 if (s->mtfbase[0] == 0) { 00479 kk = MTFA_SIZE-1; 00480 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { 00481 for (jj = MTFL_SIZE-1; jj >= 0; jj--) { 00482 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; 00483 kk--; 00484 } 00485 s->mtfbase[ii] = kk + 1; 00486 } 00487 } 00488 } 00489 } 00490 /*-- end uc = MTF ( nextSym-1 ) --*/ 00491 00492 s->unzftab[s->seqToUnseq[uc]]++; 00493 if (s->smallDecompress) 00494 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else 00495 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); 00496 nblock++; 00497 00498 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); 00499 continue; 00500 } 00501 } 00502 00503 s->state_out_len = 0; 00504 s->state_out_ch = 0; 00505 BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); 00506 s->state = BZ_X_OUTPUT; 00507 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); 00508 00509 /*-- Set up cftab to facilitate generation of T^(-1) --*/ 00510 s->cftab[0] = 0; 00511 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; 00512 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; 00513 00514 if (s->smallDecompress) { 00515 00516 /*-- Make a copy of cftab, used in generation of T --*/ 00517 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; 00518 00519 /*-- compute the T vector --*/ 00520 for (i = 0; i < nblock; i++) { 00521 uc = (UChar)(s->ll16[i]); 00522 SET_LL(i, s->cftabCopy[uc]); 00523 s->cftabCopy[uc]++; 00524 } 00525 00526 /*-- Compute T^(-1) by pointer reversal on T --*/ 00527 i = s->origPtr; 00528 j = GET_LL(i); 00529 do { 00530 Int32 tmp = GET_LL(j); 00531 SET_LL(j, i); 00532 i = j; 00533 j = tmp; 00534 } 00535 while (i != s->origPtr); 00536 00537 s->tPos = s->origPtr; 00538 s->nblock_used = 0; 00539 if (s->blockRandomised) { 00540 BZ_RAND_INIT_MASK; 00541 BZ_GET_SMALL(s->k0); s->nblock_used++; 00542 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 00543 } else { 00544 BZ_GET_SMALL(s->k0); s->nblock_used++; 00545 } 00546 00547 } else { 00548 00549 /*-- compute the T^(-1) vector --*/ 00550 for (i = 0; i < nblock; i++) { 00551 uc = (UChar)(s->tt[i] & 0xff); 00552 s->tt[s->cftab[uc]] |= (i << 8); 00553 s->cftab[uc]++; 00554 } 00555 00556 s->tPos = s->tt[s->origPtr] >> 8; 00557 s->nblock_used = 0; 00558 if (s->blockRandomised) { 00559 BZ_RAND_INIT_MASK; 00560 BZ_GET_FAST(s->k0); s->nblock_used++; 00561 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 00562 } else { 00563 BZ_GET_FAST(s->k0); s->nblock_used++; 00564 } 00565 00566 } 00567 00568 RETURN(BZ_OK); 00569 00570 00571 00572 endhdr_2: 00573 00574 GET_UCHAR(BZ_X_ENDHDR_2, uc); 00575 if (uc != 0x72) RETURN(BZ_DATA_ERROR); 00576 GET_UCHAR(BZ_X_ENDHDR_3, uc); 00577 if (uc != 0x45) RETURN(BZ_DATA_ERROR); 00578 GET_UCHAR(BZ_X_ENDHDR_4, uc); 00579 if (uc != 0x38) RETURN(BZ_DATA_ERROR); 00580 GET_UCHAR(BZ_X_ENDHDR_5, uc); 00581 if (uc != 0x50) RETURN(BZ_DATA_ERROR); 00582 GET_UCHAR(BZ_X_ENDHDR_6, uc); 00583 if (uc != 0x90) RETURN(BZ_DATA_ERROR); 00584 00585 s->storedCombinedCRC = 0; 00586 GET_UCHAR(BZ_X_CCRC_1, uc); 00587 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 00588 GET_UCHAR(BZ_X_CCRC_2, uc); 00589 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 00590 GET_UCHAR(BZ_X_CCRC_3, uc); 00591 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 00592 GET_UCHAR(BZ_X_CCRC_4, uc); 00593 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); 00594 00595 s->state = BZ_X_IDLE; 00596 RETURN(BZ_STREAM_END); 00597 00598 default: AssertH ( False, 4001 ); 00599 } 00600 00601 AssertH ( False, 4002 ); 00602 00603 save_state_and_return: 00604 00605 s->save_i = i; 00606 s->save_j = j; 00607 s->save_t = t; 00608 s->save_alphaSize = alphaSize; 00609 s->save_nGroups = nGroups; 00610 s->save_nSelectors = nSelectors; 00611 s->save_EOB = EOB; 00612 s->save_groupNo = groupNo; 00613 s->save_groupPos = groupPos; 00614 s->save_nextSym = nextSym; 00615 s->save_nblockMAX = nblockMAX; 00616 s->save_nblock = nblock; 00617 s->save_es = es; 00618 s->save_N = N; 00619 s->save_curr = curr; 00620 s->save_zt = zt; 00621 s->save_zn = zn; 00622 s->save_zvec = zvec; 00623 s->save_zj = zj; 00624 s->save_gSel = gSel; 00625 s->save_gMinlen = gMinlen; 00626 s->save_gLimit = gLimit; 00627 s->save_gBase = gBase; 00628 s->save_gPerm = gPerm; 00629 00630 return retVal; 00631 } |
|
Definition at line 175 of file huffman.c. 00180 { 00181 Int32 n, vec, i; 00182 00183 vec = 0; 00184 for (n = minLen; n <= maxLen; n++) { 00185 for (i = 0; i < alphaSize; i++) 00186 if (length[i] == n) { code[i] = vec; vec++; }; 00187 vec <<= 1; 00188 } 00189 } |
|
Definition at line 193 of file huffman.c. 00200 { 00201 Int32 pp, i, j, vec; 00202 00203 pp = 0; 00204 for (i = minLen; i <= maxLen; i++) 00205 for (j = 0; j < alphaSize; j++) 00206 if (length[j] == i) { perm[pp] = j; pp++; }; 00207 00208 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0; 00209 for (i = 0; i < alphaSize; i++) base[length[i]+1]++; 00210 00211 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1]; 00212 00213 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0; 00214 vec = 0; 00215 00216 for (i = minLen; i <= maxLen; i++) { 00217 vec += (base[i+1] - base[i]); 00218 limit[i] = vec-1; 00219 vec <<= 1; 00220 } 00221 for (i = minLen + 1; i <= maxLen; i++) 00222 base[i] = ((limit[i-1] + 1) << 1) - base[i]; 00223 } |
|
Definition at line 103 of file huffman.c. 00107 { 00108 /*-- 00109 Nodes and heap entries run from 1. Entry 0 00110 for both the heap and nodes is a sentinel. 00111 --*/ 00112 Int32 nNodes, nHeap, n1, n2, i, j, k; 00113 Bool tooLong; 00114 00115 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ]; 00116 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ]; 00117 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; 00118 00119 for (i = 0; i < alphaSize; i++) 00120 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8; 00121 00122 while (True) { 00123 00124 nNodes = alphaSize; 00125 nHeap = 0; 00126 00127 heap[0] = 0; 00128 weight[0] = 0; 00129 parent[0] = -2; 00130 00131 for (i = 1; i <= alphaSize; i++) { 00132 parent[i] = -1; 00133 nHeap++; 00134 heap[nHeap] = i; 00135 UPHEAP(nHeap); 00136 } 00137 00138 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 ); 00139 00140 while (nHeap > 1) { 00141 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 00142 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 00143 nNodes++; 00144 parent[n1] = parent[n2] = nNodes; 00145 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]); 00146 parent[nNodes] = -1; 00147 nHeap++; 00148 heap[nHeap] = nNodes; 00149 UPHEAP(nHeap); 00150 } 00151 00152 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 ); 00153 00154 tooLong = False; 00155 for (i = 1; i <= alphaSize; i++) { 00156 j = 0; 00157 k = i; 00158 while (parent[k] >= 0) { k = parent[k]; j++; } 00159 len[i-1] = j; 00160 if (j > maxLen) tooLong = True; 00161 } 00162 00163 if (! tooLong) break; 00164 00165 for (i = 1; i < alphaSize; i++) { 00166 j = weight[i] >> 8; 00167 j = 1 + (j / 2); 00168 weight[i] = j << 8; 00169 } 00170 } 00171 } |
|
Definition at line 662 of file bzlib.c. 00663 { 00664 Int32 nb, na, mid; 00665 nb = 0; 00666 na = 256; 00667 do { 00668 mid = (nb + na) >> 1; 00669 if (indx >= cftab[mid]) nb = mid; else na = mid; 00670 } 00671 while (na - nb != 1); 00672 return nb; 00673 } |
|
Definition at line 182 of file bzlib_private.h. |
|
Definition at line 158 of file bzlib_private.h. |