00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 #include "bzlib_private.h"
00063
00064
00065
00066 static
00067 void makeMaps_d ( DState* s )
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 }
00077
00078
00079
00080 #define RETURN(rrr) \
00081 { retVal = rrr; goto save_state_and_return; };
00082
00083 #define GET_BITS(lll,vvv,nnn) \
00084 case lll: s->state = lll; \
00085 while (True) { \
00086 if (s->bsLive >= nnn) { \
00087 UInt32 v; \
00088 v = (s->bsBuff >> \
00089 (s->bsLive-nnn)) & ((1 << nnn)-1); \
00090 s->bsLive -= nnn; \
00091 vvv = v; \
00092 break; \
00093 } \
00094 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
00095 s->bsBuff \
00096 = (s->bsBuff << 8) | \
00097 ((UInt32) \
00098 (*((UChar*)(s->strm->next_in)))); \
00099 s->bsLive += 8; \
00100 s->strm->next_in++; \
00101 s->strm->avail_in--; \
00102 s->strm->total_in++; \
00103 }
00104
00105 #define GET_UCHAR(lll,uuu) \
00106 GET_BITS(lll,uuu,8)
00107
00108 #define GET_BIT(lll,uuu) \
00109 GET_BITS(lll,uuu,1)
00110
00111
00112 #define GET_MTF_VAL(label1,label2,lval) \
00113 { \
00114 if (groupPos == 0) { \
00115 groupNo++; \
00116 groupPos = BZ_G_SIZE; \
00117 gSel = s->selector[groupNo]; \
00118 gMinlen = s->minLens[gSel]; \
00119 gLimit = &(s->limit[gSel][0]); \
00120 gPerm = &(s->perm[gSel][0]); \
00121 gBase = &(s->base[gSel][0]); \
00122 } \
00123 groupPos--; \
00124 zn = gMinlen; \
00125 GET_BITS(label1, zvec, zn); \
00126 while (zvec > gLimit[zn]) { \
00127 zn++; \
00128 GET_BIT(label2, zj); \
00129 zvec = (zvec << 1) | zj; \
00130 }; \
00131 lval = gPerm[zvec - gBase[zn]]; \
00132 }
00133
00134
00135
00136 Int32 decompress ( DState* s )
00137 {
00138 UChar uc;
00139 Int32 retVal;
00140 Int32 minLen, maxLen;
00141 bz_stream* strm = s->strm;
00142
00143
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
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
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
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
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
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
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
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
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
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
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
00439 {
00440 Int32 ii, jj, kk, pp, lno, off;
00441 UInt32 nn;
00442 nn = (UInt32)(nextSym - 1);
00443
00444 if (nn < MTFL_SIZE) {
00445
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
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
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
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
00517 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
00518
00519
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
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
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 }
00632
00633
00634
00635
00636
