/*      $NetBSD: decompress.c,v 1.4 2019/07/21 11:52:14 maya Exp $      */


/*-------------------------------------------------------------*/
/*--- Decompression machinery                               ---*/
/*---                                          decompress.c ---*/
/*-------------------------------------------------------------*/

/* ------------------------------------------------------------------
  This file is part of bzip2/libbzip2, a program and library for
  lossless, block-sorting data compression.

  bzip2/libbzip2 version 1.0.8 of 13 July 2019
  Copyright (C) 1996-2019 Julian Seward <[email protected]>

  Please read the WARNING, DISCLAIMER and PATENTS sections in the
  README file.

  This program is released under the terms of the license contained
  in the file LICENSE.
  ------------------------------------------------------------------ */


#include "bzlib_private.h"


/*---------------------------------------------------*/
static
void makeMaps_d ( DState* s )
{
  Int32 i;
  s->nInUse = 0;
  for (i = 0; i < 256; i++)
     if (s->inUse[i]) {
        s->seqToUnseq[s->nInUse] = i;
        s->nInUse++;
     }
}


/*---------------------------------------------------*/
#define RETURN(rrr)                               \
  { retVal = rrr; goto save_state_and_return; };

#define GET_BITS(lll,vvv,nnn)                     \
  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_lo32++;                   \
     if (s->strm->total_in_lo32 == 0)            \
        s->strm->total_in_hi32++;                \
  }

#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)           \
{                                                 \
  if (groupPos == 0) {                           \
     groupNo++;                                  \
     if (groupNo >= nSelectors)                  \
        RETURN(BZ_DATA_ERROR);                   \
     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 (1) {                                    \
     if (zn > 20 /* the longest code */)         \
        RETURN(BZ_DATA_ERROR);                   \
     if (zvec <= gLimit[zn]) break;              \
     zn++;                                       \
     GET_BIT(label2, zj);                        \
     zvec = (zvec << 1) | zj;                    \
  };                                             \
  if (zvec - gBase[zn] < 0                       \
      || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE)  \
     RETURN(BZ_DATA_ERROR);                      \
  lval = gPerm[zvec - gBase[zn]];                \
}


/*---------------------------------------------------*/
Int32 BZ2_decompress ( DState* s )
{
  UChar      uc;
  Int32      retVal;
  Int32      minLen, maxLen;
  bz_stream* strm = s->strm;

  /* stuff that needs to be saved/restored */
  Int32  i;
  Int32  j;
  Int32  t;
  Int32  alphaSize;
  Int32  nGroups;
  Int32  nSelectors;
  Int32  EOB;
  Int32  groupNo;
  Int32  groupPos;
  Int32  nextSym;
  Int32  nblockMAX;
  Int32  nblock;
  Int32  es;
  Int32  N;
  Int32  curr;
  Int32  zt;
  Int32  zn;
  Int32  zvec;
  Int32  zj;
  Int32  gSel;
  Int32  gMinlen;
  Int32* gLimit;
  Int32* gBase;
  Int32* gPerm;

  if (s->state == BZ_X_MAGIC_1) {
     /*initialise the save area*/
     s->save_i           = 0;
     s->save_j           = 0;
     s->save_t           = 0;
     s->save_alphaSize   = 0;
     s->save_nGroups     = 0;
     s->save_nSelectors  = 0;
     s->save_EOB         = 0;
     s->save_groupNo     = 0;
     s->save_groupPos    = 0;
     s->save_nextSym     = 0;
     s->save_nblockMAX   = 0;
     s->save_nblock      = 0;
     s->save_es          = 0;
     s->save_N           = 0;
     s->save_curr        = 0;
     s->save_zt          = 0;
     s->save_zn          = 0;
     s->save_zvec        = 0;
     s->save_zj          = 0;
     s->save_gSel        = 0;
     s->save_gMinlen     = 0;
     s->save_gLimit      = NULL;
     s->save_gBase       = NULL;
     s->save_gPerm       = NULL;
  }

  /*restore from the save area*/
  i           = s->save_i;
  j           = s->save_j;
  t           = s->save_t;
  alphaSize   = s->save_alphaSize;
  nGroups     = s->save_nGroups;
  nSelectors  = s->save_nSelectors;
  EOB         = s->save_EOB;
  groupNo     = s->save_groupNo;
  groupPos    = s->save_groupPos;
  nextSym     = s->save_nextSym;
  nblockMAX   = s->save_nblockMAX;
  nblock      = s->save_nblock;
  es          = s->save_es;
  N           = s->save_N;
  curr        = s->save_curr;
  zt          = s->save_zt;
  zn          = s->save_zn;
  zvec        = s->save_zvec;
  zj          = s->save_zj;
  gSel        = s->save_gSel;
  gMinlen     = s->save_gMinlen;
  gLimit      = s->save_gLimit;
  gBase       = s->save_gBase;
  gPerm       = s->save_gPerm;

  retVal = BZ_OK;

  switch (s->state) {

     GET_UCHAR(BZ_X_MAGIC_1, uc);
     if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);

     GET_UCHAR(BZ_X_MAGIC_2, uc);
     if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);

     GET_UCHAR(BZ_X_MAGIC_3, uc)
     if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);

     GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
     if (s->blockSize100k < (BZ_HDR_0 + 1) ||
         s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
     s->blockSize100k -= BZ_HDR_0;

     if (s->smallDecompress) {
        s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
        s->ll4  = BZALLOC(
                     ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
                  );
        if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
     } else {
        s->tt  = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
        if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
     }

     GET_UCHAR(BZ_X_BLKHDR_1, uc);

     if (uc == 0x17) goto endhdr_2;
     if (uc != 0x31) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_BLKHDR_2, uc);
     if (uc != 0x41) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_BLKHDR_3, uc);
     if (uc != 0x59) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_BLKHDR_4, uc);
     if (uc != 0x26) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_BLKHDR_5, uc);
     if (uc != 0x53) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_BLKHDR_6, uc);
     if (uc != 0x59) RETURN(BZ_DATA_ERROR);

     s->currBlockNo++;
     if (s->verbosity >= 2)
        VPrintf1 ( "\n    [%d: huff+mtf ", s->currBlockNo );

     s->storedBlockCRC = 0;
     GET_UCHAR(BZ_X_BCRC_1, uc);
     s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
     GET_UCHAR(BZ_X_BCRC_2, uc);
     s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
     GET_UCHAR(BZ_X_BCRC_3, uc);
     s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
     GET_UCHAR(BZ_X_BCRC_4, uc);
     s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);

     GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);

     s->origPtr = 0;
     GET_UCHAR(BZ_X_ORIGPTR_1, uc);
     s->origPtr = (s->origPtr << 8) | ((Int32)uc);
     GET_UCHAR(BZ_X_ORIGPTR_2, uc);
     s->origPtr = (s->origPtr << 8) | ((Int32)uc);
     GET_UCHAR(BZ_X_ORIGPTR_3, uc);
     s->origPtr = (s->origPtr << 8) | ((Int32)uc);

     if (s->origPtr < 0)
        RETURN(BZ_DATA_ERROR);
     if (s->origPtr > 10 + 100000*s->blockSize100k)
        RETURN(BZ_DATA_ERROR);

     /*--- Receive the mapping table ---*/
     for (i = 0; i < 16; i++) {
        GET_BIT(BZ_X_MAPPING_1, uc);
        if (uc == 1)
           s->inUse16[i] = True; else
           s->inUse16[i] = False;
     }

     for (i = 0; i < 256; i++) s->inUse[i] = False;

     for (i = 0; i < 16; i++)
        if (s->inUse16[i])
           for (j = 0; j < 16; j++) {
              GET_BIT(BZ_X_MAPPING_2, uc);
              if (uc == 1) s->inUse[i * 16 + j] = True;
           }
     makeMaps_d ( s );
     if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
     alphaSize = s->nInUse+2;

     /*--- Now the selectors ---*/
     GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
     if (nGroups < 2 || nGroups > BZ_N_GROUPS) RETURN(BZ_DATA_ERROR);
     GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
     if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
     for (i = 0; i < nSelectors; i++) {
        j = 0;
        while (True) {
           GET_BIT(BZ_X_SELECTOR_3, uc);
           if (uc == 0) break;
           j++;
           if (j >= nGroups) RETURN(BZ_DATA_ERROR);
        }
        /* Having more than BZ_MAX_SELECTORS doesn't make much sense
           since they will never be used, but some implementations might
           "round up" the number of selectors, so just ignore those. */
        if (i < BZ_MAX_SELECTORS)
          s->selectorMtf[i] = j;
     }
     if (nSelectors > BZ_MAX_SELECTORS)
       nSelectors = BZ_MAX_SELECTORS;

     /*--- Undo the MTF values for the selectors. ---*/
     {
        UChar pos[BZ_N_GROUPS], tmp, v;
        for (v = 0; v < nGroups; v++) pos[v] = v;

        for (i = 0; i < nSelectors; i++) {
           v = s->selectorMtf[i];
           tmp = pos[v];
           while (v > 0) { pos[v] = pos[v-1]; v--; }
           pos[0] = tmp;
           s->selector[i] = tmp;
        }
     }

     /*--- Now the coding tables ---*/
     for (t = 0; t < nGroups; t++) {
        GET_BITS(BZ_X_CODING_1, curr, 5);
        for (i = 0; i < alphaSize; i++) {
           while (True) {
              if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
              GET_BIT(BZ_X_CODING_2, uc);
              if (uc == 0) break;
              GET_BIT(BZ_X_CODING_3, uc);
              if (uc == 0) curr++; else curr--;
           }
           s->len[t][i] = curr;
        }
     }

     /*--- Create the Huffman decoding tables ---*/
     for (t = 0; t < nGroups; t++) {
        minLen = 32;
        maxLen = 0;
        for (i = 0; i < alphaSize; i++) {
           if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
           if (s->len[t][i] < minLen) minLen = s->len[t][i];
        }
        BZ2_hbCreateDecodeTables (
           &(s->limit[t][0]),
           &(s->base[t][0]),
           &(s->perm[t][0]),
           &(s->len[t][0]),
           minLen, maxLen, alphaSize
        );
        s->minLens[t] = minLen;
     }

     /*--- Now the MTF values ---*/

     EOB      = s->nInUse+1;
     nblockMAX = 100000 * s->blockSize100k;
     groupNo  = -1;
     groupPos = 0;

     for (i = 0; i <= 255; i++) s->unzftab[i] = 0;

     /*-- MTF init --*/
     {
        Int32 ii, jj, kk;
        kk = MTFA_SIZE-1;
        for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
           for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
              s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
              kk--;
           }
           s->mtfbase[ii] = kk + 1;
        }
     }
     /*-- end MTF init --*/

     nblock = 0;
     GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);

     while (True) {

        if (nextSym == EOB) break;

        if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {

           es = -1;
           N = 1;
           do {
              /* Check that N doesn't get too big, so that es doesn't
                 go negative.  The maximum value that can be
                 RUNA/RUNB encoded is equal to the block size (post
                 the initial RLE), viz, 900k, so bounding N at 2
                 million should guard against overflow without
                 rejecting any legitimate inputs. */
              if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
              if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
              if (nextSym == BZ_RUNB) es = es + (1+1) * N;
              N = N * 2;
              GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
           }
              while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);

           es++;
           uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
           s->unzftab[uc] += es;

           if (s->smallDecompress)
              while (es > 0) {
                 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
                 s->ll16[nblock] = (UInt16)uc;
                 nblock++;
                 es--;
              }
           else
              while (es > 0) {
                 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
                 s->tt[nblock] = (UInt32)uc;
                 nblock++;
                 es--;
              };

           continue;

        } else {

           if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);

           /*-- uc = MTF ( nextSym-1 ) --*/
           {
              Int32 ii, jj, kk, pp, lno, off;
              UInt32 nn;
              nn = (UInt32)(nextSym - 1);

              if (nn < MTFL_SIZE) {
                 /* avoid general-case expense */
                 pp = s->mtfbase[0];
                 uc = s->mtfa[pp+nn];
                 while (nn > 3) {
                    Int32 z = pp+nn;
                    s->mtfa[(z)  ] = s->mtfa[(z)-1];
                    s->mtfa[(z)-1] = s->mtfa[(z)-2];
                    s->mtfa[(z)-2] = s->mtfa[(z)-3];
                    s->mtfa[(z)-3] = s->mtfa[(z)-4];
                    nn -= 4;
                 }
                 while (nn > 0) {
                    s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
                 };
                 s->mtfa[pp] = uc;
              } else {
                 /* general case */
                 lno = nn / MTFL_SIZE;
                 off = nn % MTFL_SIZE;
                 pp = s->mtfbase[lno] + off;
                 uc = s->mtfa[pp];
                 while (pp > s->mtfbase[lno]) {
                    s->mtfa[pp] = s->mtfa[pp-1]; pp--;
                 };
                 s->mtfbase[lno]++;
                 while (lno > 0) {
                    s->mtfbase[lno]--;
                    s->mtfa[s->mtfbase[lno]]
                       = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
                    lno--;
                 }
                 s->mtfbase[0]--;
                 s->mtfa[s->mtfbase[0]] = uc;
                 if (s->mtfbase[0] == 0) {
                    kk = MTFA_SIZE-1;
                    for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
                       for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
                          s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
                          kk--;
                       }
                       s->mtfbase[ii] = kk + 1;
                    }
                 }
              }
           }
           /*-- end uc = MTF ( nextSym-1 ) --*/

           s->unzftab[s->seqToUnseq[uc]]++;
           if (s->smallDecompress)
              s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
              s->tt[nblock]   = (UInt32)(s->seqToUnseq[uc]);
           nblock++;

           GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
           continue;
        }
     }

     /* Now we know what nblock is, we can do a better sanity
        check on s->origPtr.
     */
     if (s->origPtr < 0 || s->origPtr >= nblock)
        RETURN(BZ_DATA_ERROR);

     /*-- Set up cftab to facilitate generation of T^(-1) --*/
     /* Check: unzftab entries in range. */
     for (i = 0; i <= 255; i++) {
        if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)
           RETURN(BZ_DATA_ERROR);
     }
     /* Actually generate cftab. */
     s->cftab[0] = 0;
     for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
     for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
     /* Check: cftab entries in range. */
     for (i = 0; i <= 256; i++) {
        if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
           /* s->cftab[i] can legitimately be == nblock */
           RETURN(BZ_DATA_ERROR);
        }
     }
     /* Check: cftab entries non-descending. */
     for (i = 1; i <= 256; i++) {
        if (s->cftab[i-1] > s->cftab[i]) {
           RETURN(BZ_DATA_ERROR);
        }
     }

     s->state_out_len = 0;
     s->state_out_ch  = 0;
     BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
     s->state = BZ_X_OUTPUT;
     if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );

     if (s->smallDecompress) {

        /*-- Make a copy of cftab, used in generation of T --*/
        for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];

        /*-- compute the T vector --*/
        for (i = 0; i < nblock; i++) {
           uc = (UChar)(s->ll16[i]);
           SET_LL(i, s->cftabCopy[uc]);
           s->cftabCopy[uc]++;
        }

        /*-- Compute T^(-1) by pointer reversal on T --*/
        i = s->origPtr;
        j = GET_LL(i);
        do {
           Int32 tmp = GET_LL(j);
           SET_LL(j, i);
           i = j;
           j = tmp;
        }
           while (i != s->origPtr);

        s->tPos = s->origPtr;
        s->nblock_used = 0;
        if (s->blockRandomised) {
           BZ_RAND_INIT_MASK;
           BZ_GET_SMALL(s->k0); s->nblock_used++;
           BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
        } else {
           BZ_GET_SMALL(s->k0); s->nblock_used++;
        }

     } else {

        /*-- compute the T^(-1) vector --*/
        for (i = 0; i < nblock; i++) {
           uc = (UChar)(s->tt[i] & 0xff);
           s->tt[s->cftab[uc]] |= (i << 8);
           s->cftab[uc]++;
        }

        s->tPos = s->tt[s->origPtr] >> 8;
        s->nblock_used = 0;
        if (s->blockRandomised) {
           BZ_RAND_INIT_MASK;
           BZ_GET_FAST(s->k0); s->nblock_used++;
           BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
        } else {
           BZ_GET_FAST(s->k0); s->nblock_used++;
        }

     }

     RETURN(BZ_OK);



   endhdr_2:

     GET_UCHAR(BZ_X_ENDHDR_2, uc);
     if (uc != 0x72) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_ENDHDR_3, uc);
     if (uc != 0x45) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_ENDHDR_4, uc);
     if (uc != 0x38) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_ENDHDR_5, uc);
     if (uc != 0x50) RETURN(BZ_DATA_ERROR);
     GET_UCHAR(BZ_X_ENDHDR_6, uc);
     if (uc != 0x90) RETURN(BZ_DATA_ERROR);

     s->storedCombinedCRC = 0;
     GET_UCHAR(BZ_X_CCRC_1, uc);
     s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
     GET_UCHAR(BZ_X_CCRC_2, uc);
     s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
     GET_UCHAR(BZ_X_CCRC_3, uc);
     s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
     GET_UCHAR(BZ_X_CCRC_4, uc);
     s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);

     s->state = BZ_X_IDLE;
     RETURN(BZ_STREAM_END);

     default: AssertH ( False, 4001 );
  }

  AssertH ( False, 4002 );

  save_state_and_return:

  s->save_i           = i;
  s->save_j           = j;
  s->save_t           = t;
  s->save_alphaSize   = alphaSize;
  s->save_nGroups     = nGroups;
  s->save_nSelectors  = nSelectors;
  s->save_EOB         = EOB;
  s->save_groupNo     = groupNo;
  s->save_groupPos    = groupPos;
  s->save_nextSym     = nextSym;
  s->save_nblockMAX   = nblockMAX;
  s->save_nblock      = nblock;
  s->save_es          = es;
  s->save_N           = N;
  s->save_curr        = curr;
  s->save_zt          = zt;
  s->save_zn          = zn;
  s->save_zvec        = zvec;
  s->save_zj          = zj;
  s->save_gSel        = gSel;
  s->save_gMinlen     = gMinlen;
  s->save_gLimit      = gLimit;
  s->save_gBase       = gBase;
  s->save_gPerm       = gPerm;

  return retVal;
}


/*-------------------------------------------------------------*/
/*--- end                                      decompress.c ---*/
/*-------------------------------------------------------------*/

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.