[u-boot.git] / lib / bzlib_decompress.c

#include <config.h>
#include <common.h>
#include <watchdog.h>

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

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

  Copyright (C) 1996-2002 Julian R Seward.  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions
  are met:

  1. Redistributions of source code must retain the above copyright
     notice, this list of conditions and the following disclaimer.

  2. The origin of this software must not be misrepresented; you must
     not claim that you wrote the original software.  If you use this
     software in a product, an acknowledgment in the product
     documentation would be appreciated but is not required.

  3. Altered source versions must be plainly marked as such, and must
     not be misrepresented as being the original software.

  4. The name of the author may not be used to endorse or promote
     products derived from this software without specific prior written
     permission.

  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  Julian Seward, Cambridge, UK.
  [email protected]
  bzip2/libbzip2 version 1.0 of 21 March 2000

  This program is based on (at least) the work of:
     Mike Burrows
     David Wheeler
     Peter Fenwick
     Alistair Moffat
     Radford Neal
     Ian H. Witten
     Robert Sedgewick
     Jon L. Bentley

  For more information on these sources, see the manual.
--*/


#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 > 6) 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);
	 }
	 s->selectorMtf[i] = j;
      }

      /*--- 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 defined(CONFIG_HW_WATCHDOG) || defined(CONFIG_WATCHDOG)
	WATCHDOG_RESET();
#endif
	 if (nextSym == EOB) break;

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

	    es = -1;
	    N = 1;
	    do {
	       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--) {
#if defined(CONFIG_HW_WATCHDOG) || defined(CONFIG_WATCHDOG)
			WATCHDOG_RESET();
#endif
			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);

      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" );

      /*-- Set up cftab to facilitate generation of T^(-1) --*/
      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];

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

#if defined(CONFIG_HW_WATCHDOG) || defined(CONFIG_WATCHDOG)
	WATCHDOG_RESET();
#endif
	 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 {

#if defined(CONFIG_HW_WATCHDOG) || defined(CONFIG_WATCHDOG)
	WATCHDOG_RESET();
#endif
	 /*-- 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 ---*/
/*-------------------------------------------------------------*/
Commit	Line	Data
c29fdfc1	1	#include <config.h>
2ee66533 WD	2	#include <common.h>
2ee66533 WD	3	#include <watchdog.h>
c29fdfc1 WD	4
	5	/-------------------------------------------------------------/
	6	/--- Decompression machinery ---/
	7	/--- decompress.c ---/
	8	/-------------------------------------------------------------/
	9
	10	/*--
	11	This file is a part of bzip2 and/or libbzip2, a program and
	12	library for lossless, block-sorting data compression.
	13
	14	Copyright (C) 1996-2002 Julian R Seward. All rights reserved.
	15
	16	Redistribution and use in source and binary forms, with or without
	17	modification, are permitted provided that the following conditions
	18	are met:
	19
	20	1. Redistributions of source code must retain the above copyright
	21	notice, this list of conditions and the following disclaimer.
	22
	23	2. The origin of this software must not be misrepresented; you must
	24	not claim that you wrote the original software. If you use this
	25	software in a product, an acknowledgment in the product
	26	documentation would be appreciated but is not required.
	27
	28	3. Altered source versions must be plainly marked as such, and must
	29	not be misrepresented as being the original software.
	30
	31	4. The name of the author may not be used to endorse or promote
	32	products derived from this software without specific prior written
	33	permission.
	34
	35	THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
	36	OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
	37	WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	38	ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
	39	DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	40	DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
	41	GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	42	INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
	43	WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
	44	NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
	45	SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	46
	47	Julian Seward, Cambridge, UK.
	48	[email protected]
	49	bzip2/libbzip2 version 1.0 of 21 March 2000
	50
	51	This program is based on (at least) the work of:
	52	Mike Burrows
	53	David Wheeler
	54	Peter Fenwick
	55	Alistair Moffat
	56	Radford Neal
	57	Ian H. Witten
	58	Robert Sedgewick
	59	Jon L. Bentley
	60
	61	For more information on these sources, see the manual.
	62	--*/
	63
	64
	65	#include "bzlib_private.h"
	66
	67
68	/---------------------------------------------------/
69	static
70	void makeMaps_d ( DState* s )
71	{
72	Int32 i;
73	s->nInUse = 0;
74	for (i = 0; i < 256; i++)
75	if (s->inUse[i]) {
42d1f039 WD	76	s->seqToUnseq[s->nInUse] = i;
42d1f039 WD	77	s->nInUse++;
c29fdfc1 WD	78	}
	79	}
	80
	81
	82	/---------------------------------------------------/
	83	#define RETURN(rrr) \
	84	{ retVal = rrr; goto save_state_and_return; };
	85
	86	#define GET_BITS(lll,vvv,nnn) \
	87	case lll: s->state = lll; \
	88	while (True) { \
	89	if (s->bsLive >= nnn) { \
42d1f039 WD	90	UInt32 v; \
	91	v = (s->bsBuff >> \
	92	(s->bsLive-nnn)) & ((1 << nnn)-1); \
	93	s->bsLive -= nnn; \
	94	vvv = v; \
	95	break; \
c29fdfc1 WD	96	} \
	97	if (s->strm->avail_in == 0) RETURN(BZ_OK); \
	98	s->bsBuff \
42d1f039 WD	99	= (s->bsBuff << 8) \| \
	100	((UInt32) \
	101	(((UChar)(s->strm->next_in)))); \
c29fdfc1 WD	102	s->bsLive += 8; \
	103	s->strm->next_in++; \
	104	s->strm->avail_in--; \
	105	s->strm->total_in_lo32++; \
	106	if (s->strm->total_in_lo32 == 0) \
42d1f039	107	s->strm->total_in_hi32++; \
c29fdfc1 WD	108	}
	109
	110	#define GET_UCHAR(lll,uuu) \
	111	GET_BITS(lll,uuu,8)
	112
	113	#define GET_BIT(lll,uuu) \
	114	GET_BITS(lll,uuu,1)
	115
	116	/---------------------------------------------------/
	117	#define GET_MTF_VAL(label1,label2,lval) \
	118	{ \
	119	if (groupPos == 0) { \
	120	groupNo++; \
	121	if (groupNo >= nSelectors) \
42d1f039	122	RETURN(BZ_DATA_ERROR); \
c29fdfc1 WD	123	groupPos = BZ_G_SIZE; \
	124	gSel = s->selector[groupNo]; \
	125	gMinlen = s->minLens[gSel]; \
	126	gLimit = &(s->limit[gSel][0]); \
	127	gPerm = &(s->perm[gSel][0]); \
	128	gBase = &(s->base[gSel][0]); \
	129	} \
	130	groupPos--; \
	131	zn = gMinlen; \
	132	GET_BITS(label1, zvec, zn); \
	133	while (1) { \
	134	if (zn > 20 /* the longest code */) \
42d1f039	135	RETURN(BZ_DATA_ERROR); \
c29fdfc1 WD	136	if (zvec <= gLimit[zn]) break; \
	137	zn++; \
	138	GET_BIT(label2, zj); \
	139	zvec = (zvec << 1) \| zj; \
	140	}; \
	141	if (zvec - gBase[zn] < 0 \
	142	\|\| zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
	143	RETURN(BZ_DATA_ERROR); \
	144	lval = gPerm[zvec - gBase[zn]]; \
	145	}
	146
	147
	148	/---------------------------------------------------/
	149	Int32 BZ2_decompress ( DState* s )
	150	{
	151	UChar uc;
	152	Int32 retVal;
	153	Int32 minLen, maxLen;
	154	bz_stream* strm = s->strm;
	155
	156	/* stuff that needs to be saved/restored */
	157	Int32 i;
	158	Int32 j;
	159	Int32 t;
	160	Int32 alphaSize;
	161	Int32 nGroups;
	162	Int32 nSelectors;
	163	Int32 EOB;
	164	Int32 groupNo;
	165	Int32 groupPos;
	166	Int32 nextSym;
	167	Int32 nblockMAX;
	168	Int32 nblock;
	169	Int32 es;
	170	Int32 N;
	171	Int32 curr;
	172	Int32 zt;
	173	Int32 zn;
	174	Int32 zvec;
	175	Int32 zj;
	176	Int32 gSel;
	177	Int32 gMinlen;
	178	Int32* gLimit;
	179	Int32* gBase;
	180	Int32* gPerm;
	181
	182	if (s->state == BZ_X_MAGIC_1) {
	183	/initialise the save area/
	184	s->save_i = 0;
	185	s->save_j = 0;
	186	s->save_t = 0;
	187	s->save_alphaSize = 0;
	188	s->save_nGroups = 0;
	189	s->save_nSelectors = 0;
	190	s->save_EOB = 0;
	191	s->save_groupNo = 0;
	192	s->save_groupPos = 0;
	193	s->save_nextSym = 0;
	194	s->save_nblockMAX = 0;
	195	s->save_nblock = 0;
	196	s->save_es = 0;
	197	s->save_N = 0;
	198	s->save_curr = 0;
	199	s->save_zt = 0;
200	s->save_zn = 0;
201	s->save_zvec = 0;
202	s->save_zj = 0;
203	s->save_gSel = 0;
204	s->save_gMinlen = 0;
205	s->save_gLimit = NULL;
206	s->save_gBase = NULL;
207	s->save_gPerm = NULL;
208	}
209
210	/restore from the save area/
211	i = s->save_i;
212	j = s->save_j;
213	t = s->save_t;
214	alphaSize = s->save_alphaSize;
215	nGroups = s->save_nGroups;
216	nSelectors = s->save_nSelectors;
217	EOB = s->save_EOB;
218	groupNo = s->save_groupNo;
219	groupPos = s->save_groupPos;
220	nextSym = s->save_nextSym;
221	nblockMAX = s->save_nblockMAX;
222	nblock = s->save_nblock;
223	es = s->save_es;
224	N = s->save_N;
225	curr = s->save_curr;
226	zt = s->save_zt;
227	zn = s->save_zn;
228	zvec = s->save_zvec;
229	zj = s->save_zj;
230	gSel = s->save_gSel;
231	gMinlen = s->save_gMinlen;
232	gLimit = s->save_gLimit;
233	gBase = s->save_gBase;
234	gPerm = s->save_gPerm;
235
236	retVal = BZ_OK;
237
238	switch (s->state) {
239
240	GET_UCHAR(BZ_X_MAGIC_1, uc);
241	if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
242
243	GET_UCHAR(BZ_X_MAGIC_2, uc);
244	if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
245
246	GET_UCHAR(BZ_X_MAGIC_3, uc)
247	if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
248
249	GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
250	if (s->blockSize100k < (BZ_HDR_0 + 1) \|\|
42d1f039	251	s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
c29fdfc1 WD	252	s->blockSize100k -= BZ_HDR_0;
	253
	254	if (s->smallDecompress) {
42d1f039 WD	255	s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
	256	s->ll4 = BZALLOC(
	257	((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
	258	);
	259	if (s->ll16 == NULL \|\| s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
c29fdfc1	260	} else {
42d1f039 WD	261	s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
42d1f039 WD	262	if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
c29fdfc1 WD	263	}
	264
	265	GET_UCHAR(BZ_X_BLKHDR_1, uc);
	266
	267	if (uc == 0x17) goto endhdr_2;
	268	if (uc != 0x31) RETURN(BZ_DATA_ERROR);
	269	GET_UCHAR(BZ_X_BLKHDR_2, uc);
	270	if (uc != 0x41) RETURN(BZ_DATA_ERROR);
	271	GET_UCHAR(BZ_X_BLKHDR_3, uc);
	272	if (uc != 0x59) RETURN(BZ_DATA_ERROR);
	273	GET_UCHAR(BZ_X_BLKHDR_4, uc);
	274	if (uc != 0x26) RETURN(BZ_DATA_ERROR);
	275	GET_UCHAR(BZ_X_BLKHDR_5, uc);
	276	if (uc != 0x53) RETURN(BZ_DATA_ERROR);
	277	GET_UCHAR(BZ_X_BLKHDR_6, uc);
	278	if (uc != 0x59) RETURN(BZ_DATA_ERROR);
	279
	280	s->currBlockNo++;
	281	if (s->verbosity >= 2)
42d1f039	282	VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
c29fdfc1 WD	283
	284	s->storedBlockCRC = 0;
	285	GET_UCHAR(BZ_X_BCRC_1, uc);
	286	s->storedBlockCRC = (s->storedBlockCRC << 8) \| ((UInt32)uc);
	287	GET_UCHAR(BZ_X_BCRC_2, uc);
	288	s->storedBlockCRC = (s->storedBlockCRC << 8) \| ((UInt32)uc);
	289	GET_UCHAR(BZ_X_BCRC_3, uc);
	290	s->storedBlockCRC = (s->storedBlockCRC << 8) \| ((UInt32)uc);
	291	GET_UCHAR(BZ_X_BCRC_4, uc);
	292	s->storedBlockCRC = (s->storedBlockCRC << 8) \| ((UInt32)uc);
	293
	294	GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
	295
	296	s->origPtr = 0;
	297	GET_UCHAR(BZ_X_ORIGPTR_1, uc);
	298	s->origPtr = (s->origPtr << 8) \| ((Int32)uc);
	299	GET_UCHAR(BZ_X_ORIGPTR_2, uc);
	300	s->origPtr = (s->origPtr << 8) \| ((Int32)uc);
	301	GET_UCHAR(BZ_X_ORIGPTR_3, uc);
	302	s->origPtr = (s->origPtr << 8) \| ((Int32)uc);
	303
	304	if (s->origPtr < 0)
42d1f039	305	RETURN(BZ_DATA_ERROR);
c29fdfc1	306	if (s->origPtr > 10 + 100000*s->blockSize100k)
42d1f039	307	RETURN(BZ_DATA_ERROR);
c29fdfc1 WD	308
	309	/--- Receive the mapping table ---/
	310	for (i = 0; i < 16; i++) {
42d1f039 WD	311	GET_BIT(BZ_X_MAPPING_1, uc);
	312	if (uc == 1)
	313	s->inUse16[i] = True; else
	314	s->inUse16[i] = False;
c29fdfc1 WD	315	}
	316
	317	for (i = 0; i < 256; i++) s->inUse[i] = False;
	318
	319	for (i = 0; i < 16; i++)
42d1f039 WD	320	if (s->inUse16[i])
	321	for (j = 0; j < 16; j++) {
	322	GET_BIT(BZ_X_MAPPING_2, uc);
	323	if (uc == 1) s->inUse[i * 16 + j] = True;
	324	}
c29fdfc1 WD	325	makeMaps_d ( s );
	326	if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
	327	alphaSize = s->nInUse+2;
	328
	329	/--- Now the selectors ---/
	330	GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
	331	if (nGroups < 2 \|\| nGroups > 6) RETURN(BZ_DATA_ERROR);
	332	GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
	333	if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
	334	for (i = 0; i < nSelectors; i++) {
42d1f039 WD	335	j = 0;
	336	while (True) {
	337	GET_BIT(BZ_X_SELECTOR_3, uc);
	338	if (uc == 0) break;
	339	j++;
	340	if (j >= nGroups) RETURN(BZ_DATA_ERROR);
	341	}
	342	s->selectorMtf[i] = j;
c29fdfc1 WD	343	}
	344
	345	/--- Undo the MTF values for the selectors. ---/
	346	{
42d1f039 WD	347	UChar pos[BZ_N_GROUPS], tmp, v;
	348	for (v = 0; v < nGroups; v++) pos[v] = v;
	349
	350	for (i = 0; i < nSelectors; i++) {
	351	v = s->selectorMtf[i];
	352	tmp = pos[v];
	353	while (v > 0) { pos[v] = pos[v-1]; v--; }
	354	pos[0] = tmp;
	355	s->selector[i] = tmp;
	356	}
c29fdfc1 WD	357	}
	358
	359	/--- Now the coding tables ---/
	360	for (t = 0; t < nGroups; t++) {
42d1f039 WD	361	GET_BITS(BZ_X_CODING_1, curr, 5);
	362	for (i = 0; i < alphaSize; i++) {
	363	while (True) {
	364	if (curr < 1 \|\| curr > 20) RETURN(BZ_DATA_ERROR);
	365	GET_BIT(BZ_X_CODING_2, uc);
	366	if (uc == 0) break;
	367	GET_BIT(BZ_X_CODING_3, uc);
	368	if (uc == 0) curr++; else curr--;
	369	}
	370	s->len[t][i] = curr;
	371	}
c29fdfc1 WD	372	}
	373
	374	/--- Create the Huffman decoding tables ---/
	375	for (t = 0; t < nGroups; t++) {
42d1f039 WD	376	minLen = 32;
	377	maxLen = 0;
	378	for (i = 0; i < alphaSize; i++) {
	379	if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
	380	if (s->len[t][i] < minLen) minLen = s->len[t][i];
	381	}
	382	BZ2_hbCreateDecodeTables (
	383	&(s->limit[t][0]),
	384	&(s->base[t][0]),
	385	&(s->perm[t][0]),
	386	&(s->len[t][0]),
	387	minLen, maxLen, alphaSize
	388	);
	389	s->minLens[t] = minLen;
c29fdfc1 WD	390	}
	391
	392	/--- Now the MTF values ---/
	393
	394	EOB = s->nInUse+1;
	395	nblockMAX = 100000 * s->blockSize100k;
	396	groupNo = -1;
	397	groupPos = 0;
	398
	399	for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
	400
	401	/-- MTF init --/
	402	{
42d1f039 WD	403	Int32 ii, jj, kk;
	404	kk = MTFA_SIZE-1;
	405	for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
	406	for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
	407	s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
	408	kk--;
	409	}
	410	s->mtfbase[ii] = kk + 1;
	411	}
c29fdfc1 WD	412	}
	413	/-- end MTF init --/
	414
	415	nblock = 0;
	416	GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
	417
	418	while (True) {
	419
2ee66533 WD	420	#if defined(CONFIG_HW_WATCHDOG) \|\| defined(CONFIG_WATCHDOG)
	421	WATCHDOG_RESET();
	422	#endif
42d1f039 WD	423	if (nextSym == EOB) break;
	424
	425	if (nextSym == BZ_RUNA \|\| nextSym == BZ_RUNB) {
	426
	427	es = -1;
	428	N = 1;
	429	do {
	430	if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
	431	if (nextSym == BZ_RUNB) es = es + (1+1) * N;
	432	N = N * 2;
	433	GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
	434	}
	435	while (nextSym == BZ_RUNA \|\| nextSym == BZ_RUNB);
	436
	437	es++;
	438	uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
	439	s->unzftab[uc] += es;
	440
	441	if (s->smallDecompress)
	442	while (es > 0) {
	443	if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
	444	s->ll16[nblock] = (UInt16)uc;
	445	nblock++;
	446	es--;
	447	}
	448	else
	449	while (es > 0) {
	450	if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
	451	s->tt[nblock] = (UInt32)uc;
	452	nblock++;
	453	es--;
	454	};
	455
	456	continue;
	457
	458	} else {
	459
	460	if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
	461
	462	/-- uc = MTF ( nextSym-1 ) --/
	463	{
	464	Int32 ii, jj, kk, pp, lno, off;
	465	UInt32 nn;
	466	nn = (UInt32)(nextSym - 1);
	467
	468	if (nn < MTFL_SIZE) {
	469	/* avoid general-case expense */
	470	pp = s->mtfbase[0];
	471	uc = s->mtfa[pp+nn];
	472	while (nn > 3) {
	473	Int32 z = pp+nn;
	474	s->mtfa[(z) ] = s->mtfa[(z)-1];
	475	s->mtfa[(z)-1] = s->mtfa[(z)-2];
	476	s->mtfa[(z)-2] = s->mtfa[(z)-3];
	477	s->mtfa[(z)-3] = s->mtfa[(z)-4];
	478	nn -= 4;
	479	}
	480	while (nn > 0) {
	481	s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
	482	};
	483	s->mtfa[pp] = uc;
	484	} else {
	485	/* general case */
	486	lno = nn / MTFL_SIZE;
487	off = nn % MTFL_SIZE;
488	pp = s->mtfbase[lno] + off;
489	uc = s->mtfa[pp];
490	while (pp > s->mtfbase[lno]) {
491	s->mtfa[pp] = s->mtfa[pp-1]; pp--;
492	};
493	s->mtfbase[lno]++;
494	while (lno > 0) {
495	s->mtfbase[lno]--;
496	s->mtfa[s->mtfbase[lno]]
497	= s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
498	lno--;
499	}
500	s->mtfbase[0]--;
501	s->mtfa[s->mtfbase[0]] = uc;
502	if (s->mtfbase[0] == 0) {
503	kk = MTFA_SIZE-1;
504	for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
2ee66533 WD	505	#if defined(CONFIG_HW_WATCHDOG) \|\| defined(CONFIG_WATCHDOG)
	506	WATCHDOG_RESET();
	507	#endif
42d1f039 WD	508	for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
	509	s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
	510	kk--;
	511	}
	512	s->mtfbase[ii] = kk + 1;
	513	}
	514	}
	515	}
	516	}
	517	/-- end uc = MTF ( nextSym-1 ) --/
	518
	519	s->unzftab[s->seqToUnseq[uc]]++;
	520	if (s->smallDecompress)
	521	s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
	522	s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
	523	nblock++;
	524
	525	GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
	526	continue;
	527	}
c29fdfc1 WD	528	}
	529
	530	/* Now we know what nblock is, we can do a better sanity
42d1f039	531	check on s->origPtr.
c29fdfc1 WD	532	*/
c29fdfc1 WD	533	if (s->origPtr < 0 \|\| s->origPtr >= nblock)
42d1f039	534	RETURN(BZ_DATA_ERROR);
c29fdfc1 WD	535
	536	s->state_out_len = 0;
	537	s->state_out_ch = 0;
	538	BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
	539	s->state = BZ_X_OUTPUT;
	540	if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
	541
	542	/-- Set up cftab to facilitate generation of T^(-1) --/
	543	s->cftab[0] = 0;
	544	for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
	545	for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
	546
	547	if (s->smallDecompress) {
	548
42d1f039 WD	549	/-- Make a copy of cftab, used in generation of T --/
	550	for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
	551
	552	/-- compute the T vector --/
	553	for (i = 0; i < nblock; i++) {
	554	uc = (UChar)(s->ll16[i]);
	555	SET_LL(i, s->cftabCopy[uc]);
	556	s->cftabCopy[uc]++;
	557	}
	558
	559	/-- Compute T^(-1) by pointer reversal on T --/
	560	i = s->origPtr;
	561	j = GET_LL(i);
	562	do {
	563	Int32 tmp = GET_LL(j);
	564	SET_LL(j, i);
	565	i = j;
	566	j = tmp;
	567	}
	568	while (i != s->origPtr);
	569
2ee66533 WD	570	#if defined(CONFIG_HW_WATCHDOG) \|\| defined(CONFIG_WATCHDOG)
	571	WATCHDOG_RESET();
	572	#endif
42d1f039 WD	573	s->tPos = s->origPtr;
	574	s->nblock_used = 0;
	575	if (s->blockRandomised) {
	576	BZ_RAND_INIT_MASK;
	577	BZ_GET_SMALL(s->k0); s->nblock_used++;
	578	BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
	579	} else {
	580	BZ_GET_SMALL(s->k0); s->nblock_used++;
	581	}
c29fdfc1 WD	582
	583	} else {
	584
2ee66533 WD	585	#if defined(CONFIG_HW_WATCHDOG) \|\| defined(CONFIG_WATCHDOG)
	586	WATCHDOG_RESET();
	587	#endif
42d1f039 WD	588	/-- compute the T^(-1) vector --/
	589	for (i = 0; i < nblock; i++) {
	590	uc = (UChar)(s->tt[i] & 0xff);
	591	s->tt[s->cftab[uc]] \|= (i << 8);
	592	s->cftab[uc]++;
	593	}
	594
	595	s->tPos = s->tt[s->origPtr] >> 8;
	596	s->nblock_used = 0;
	597	if (s->blockRandomised) {
	598	BZ_RAND_INIT_MASK;
	599	BZ_GET_FAST(s->k0); s->nblock_used++;
	600	BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
	601	} else {
	602	BZ_GET_FAST(s->k0); s->nblock_used++;
	603	}
c29fdfc1 WD	604
	605	}
	606
	607	RETURN(BZ_OK);
	608
	609
c29fdfc1 WD	610	endhdr_2:
	611
	612	GET_UCHAR(BZ_X_ENDHDR_2, uc);
	613	if (uc != 0x72) RETURN(BZ_DATA_ERROR);
	614	GET_UCHAR(BZ_X_ENDHDR_3, uc);
	615	if (uc != 0x45) RETURN(BZ_DATA_ERROR);
	616	GET_UCHAR(BZ_X_ENDHDR_4, uc);
	617	if (uc != 0x38) RETURN(BZ_DATA_ERROR);
	618	GET_UCHAR(BZ_X_ENDHDR_5, uc);
	619	if (uc != 0x50) RETURN(BZ_DATA_ERROR);
	620	GET_UCHAR(BZ_X_ENDHDR_6, uc);
	621	if (uc != 0x90) RETURN(BZ_DATA_ERROR);
	622
	623	s->storedCombinedCRC = 0;
	624	GET_UCHAR(BZ_X_CCRC_1, uc);
	625	s->storedCombinedCRC = (s->storedCombinedCRC << 8) \| ((UInt32)uc);
	626	GET_UCHAR(BZ_X_CCRC_2, uc);
	627	s->storedCombinedCRC = (s->storedCombinedCRC << 8) \| ((UInt32)uc);
	628	GET_UCHAR(BZ_X_CCRC_3, uc);
	629	s->storedCombinedCRC = (s->storedCombinedCRC << 8) \| ((UInt32)uc);
	630	GET_UCHAR(BZ_X_CCRC_4, uc);
	631	s->storedCombinedCRC = (s->storedCombinedCRC << 8) \| ((UInt32)uc);
	632
	633	s->state = BZ_X_IDLE;
	634	RETURN(BZ_STREAM_END);
	635
	636	default: AssertH ( False, 4001 );
	637	}
	638
	639	AssertH ( False, 4002 );
	640
	641	save_state_and_return:
	642
	643	s->save_i = i;
	644	s->save_j = j;
	645	s->save_t = t;
	646	s->save_alphaSize = alphaSize;
	647	s->save_nGroups = nGroups;
	648	s->save_nSelectors = nSelectors;
	649	s->save_EOB = EOB;
	650	s->save_groupNo = groupNo;
	651	s->save_groupPos = groupPos;
	652	s->save_nextSym = nextSym;
	653	s->save_nblockMAX = nblockMAX;
	654	s->save_nblock = nblock;
	655	s->save_es = es;
	656	s->save_N = N;
	657	s->save_curr = curr;
	658	s->save_zt = zt;
	659	s->save_zn = zn;
	660	s->save_zvec = zvec;
	661	s->save_zj = zj;
	662	s->save_gSel = gSel;
	663	s->save_gMinlen = gMinlen;
	664	s->save_gLimit = gLimit;
	665	s->save_gBase = gBase;
	666	s->save_gPerm = gPerm;
	667
	668	return retVal;
	669	}
	670
	671
	672	/-------------------------------------------------------------/
	673	/--- end decompress.c ---/
674	/-------------------------------------------------------------/