Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

decompress.c File Reference

#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)


Define Documentation

#define GET_BIT lll,
uuu       GET_BITS(lll,uuu,1)
 

Definition at line 108 of file decompress.c.

Referenced by decompress().

#define GET_BITS lll,
vvv,
nnn   
 

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().

#define GET_MTF_VAL label1,
label2,
lval   
 

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().

#define GET_UCHAR lll,
uuu       GET_BITS(lll,uuu,8)
 

Definition at line 105 of file decompress.c.

Referenced by decompress().

#define RETURN rrr       { retVal = rrr; goto save_state_and_return; };
 

Definition at line 80 of file decompress.c.

Referenced by decompress().


Function Documentation

Int32 decompress DState   s
 

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 }

void makeMaps_d DState   s [static]
 

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 }


Generated on Sat Oct 13 16:08:47 2001 for XMILL by doxygen1.2.11.1 written by Dimitri van Heesch, © 1997-2001