/*-------------------------------------------------------------*/

/*--- 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 <jseward@acm.org>

   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 ---*/

/*-------------------------------------------------------------*/