[people/ms/u-boot.git] / lib_generic / bzlib_decompress.c

#include <config.h>
#ifdef CONFIG_BZIP2

/*-------------------------------------------------------------*/
/*--- 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.
  jseward@acm.org
  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 (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--) {
			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);

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

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