#include "bzlib_private.h"
Go to the source code of this file.
Defines | |
#define | RETURN(rrr) { retVal = rrr; goto save_state_and_return; }; |
#define | GET_BITS(lll, vvv, nnn) |
#define | GET_UCHAR(lll, uuu) GET_BITS(lll,uuu,8) |
#define | GET_BIT(lll, uuu) GET_BITS(lll,uuu,1) |
#define | GET_MTF_VAL(label1, label2, lval) |
Functions | |
void | makeMaps_d (DState *s) |
Int32 | decompress (DState *s) |
|
Definition at line 108 of file decompress.c. Referenced by decompress().
|
|
Value: case lll: s->state = lll; \ while (True) { \ if (s->bsLive >= nnn) { \ UInt32 v; \ v = (s->bsBuff >> \ (s->bsLive-nnn)) & ((1 << nnn)-1); \ s->bsLive -= nnn; \ vvv = v; \ break; \ } \ if (s->strm->avail_in == 0) RETURN(BZ_OK); \ s->bsBuff \ = (s->bsBuff << 8) | \ ((UInt32) \ (*((UChar*)(s->strm->next_in)))); \ s->bsLive += 8; \ s->strm->next_in++; \ s->strm->avail_in--; \ s->strm->total_in++; \ } Definition at line 83 of file decompress.c. Referenced by decompress().
|
|
Value: { \ if (groupPos == 0) { \ groupNo++; \ groupPos = BZ_G_SIZE; \ gSel = s->selector[groupNo]; \ gMinlen = s->minLens[gSel]; \ gLimit = &(s->limit[gSel][0]); \ gPerm = &(s->perm[gSel][0]); \ gBase = &(s->base[gSel][0]); \ } \ groupPos--; \ zn = gMinlen; \ GET_BITS(label1, zvec, zn); \ while (zvec > gLimit[zn]) { \ zn++; \ GET_BIT(label2, zj); \ zvec = (zvec << 1) | zj; \ }; \ lval = gPerm[zvec - gBase[zn]]; \ } Definition at line 112 of file decompress.c. Referenced by decompress().
|
|
Definition at line 105 of file decompress.c. Referenced by decompress().
|
|
Definition at line 80 of file decompress.c. Referenced by decompress().
|
|
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 67 of file decompress.c. Referenced by decompress().
00068 { 00069 Int32 i; 00070 s->nInUse = 0; 00071 for (i = 0; i < 256; i++) 00072 if (s->inUse[i]) { 00073 s->seqToUnseq[s->nInUse] = i; 00074 s->nInUse++; 00075 } 00076 } |