decompress.c

   1
   2 /*-------------------------------------------------------------*/
   3 /*--- Decompression machinery                               ---*/
   4 /*---                                          decompress.c ---*/
   5 /*-------------------------------------------------------------*/
   6
   7 /* ------------------------------------------------------------------
   8    This file is part of bzip2/libbzip2, a program and library for
   9    lossless, block-sorting data compression.
  10
  11    bzip2/libbzip2 version 1.0.6 of 6 September 2010
  12    Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
  13
  14    Please read the WARNING, DISCLAIMER and PATENTS sections in the
  15    README file.
  16
  17    This program is released under the terms of the license contained
  18    in the file LICENSE.
  19    ------------------------------------------------------------------ */
  20
  21
  22 #include "bzlib_private.h"
  23
  24
  25 /*---------------------------------------------------*/
  26 static
  27 void makeMaps_d ( DState* s )
  28 {
  29    Int32 i;
  30    s->nInUse = 0;
  31    for (i = 0; i < 256; i++)
  32       if (s->inUse[i]) {
  33          s->seqToUnseq[s->nInUse] = i;
  34          s->nInUse++;
  35       }
  36 }
  37
  38
  39 /*---------------------------------------------------*/
  40 #define RETURN(rrr)                               \
  41    { retVal = rrr; goto save_state_and_return; };
  42
  43 #define GET_BITS(lll,vvv,nnn)                     \
  44    case lll: s->state = lll;                      \
  45    while (True) {                                 \
  46       if (s->bsLive >= nnn) {                     \
  47          UInt32 v;                                \
  48          v = (s->bsBuff >>                        \
  49              (s->bsLive-nnn)) & ((1 << nnn)-1);   \
  50          s->bsLive -= nnn;                        \
  51          vvv = v;                                 \
  52          break;                                   \
  53       }                                           \
  54       if (s->strm->avail_in == 0) RETURN(BZ_OK);  \
  55       s->bsBuff                                   \
  56          = (s->bsBuff << 8) |                     \
  57            ((UInt32)                              \
  58               (*((UChar*)(s->strm->next_in))));   \
  59       s->bsLive += 8;                             \
  60       s->strm->next_in++;                         \
  61       s->strm->avail_in--;                        \
  62       s->strm->total_in_lo32++;                   \
  63       if (s->strm->total_in_lo32 == 0)            \
  64          s->strm->total_in_hi32++;                \
  65    }
  66
  67 #define UNGET_BITS(nnn)                           \
  68    s->bsLive += nnn
  69
  70 #define GET_UCHAR(lll,uuu)                        \
  71    GET_BITS(lll,uuu,8)
  72
  73 #define GET_BIT(lll,uuu)                          \
  74    GET_BITS(lll,uuu,1)
  75
  76 /*---------------------------------------------------*/
  77 #define GET_MTF_VAL(label1,label2,lval)           \
  78 {                                                 \
  79    if (groupPos == 0) {                           \
  80       groupNo++;                                  \
  81       if (groupNo >= nSelectors)                  \
  82          RETURN(BZ_DATA_ERROR);                   \
  83       groupPos = BZ_G_SIZE;                       \
  84       gSel = s->selector[groupNo];                \
  85       gMinlen = s->minLens[gSel];                 \
  86       gLimit = &(s->limit[gSel][0]);              \
  87       gPerm = &(s->perm[gSel][0]);                \
  88       gBase = &(s->base[gSel][0]);                \
  89       gHufCode = &(s->hufcode[gSel][0]);          \
  90    }                                              \
  91    groupPos--;                                    \
  92    zn = HUFCODE_SIZE;                             \
  93    GET_BITS(label1, zvec, zn);                    \
  94    if (gHufCode[zvec]) {                          \
  95       UNGET_BITS(gHufCode[zvec] >> 10);           \
  96       lval = gHufCode[zvec] & 511;                \
  97    } else {                                       \
  98       while (1) {                                 \
  99          if (zn > 20 /* the longest code */)      \
 100             RETURN(BZ_DATA_ERROR);                \
 101          if (zvec <= gLimit[zn]) break;           \
 102          zn++;                                    \
 103          GET_BIT(label2, zj);                     \
 104          zvec = (zvec << 1) | zj;                 \
 105       };                                          \
 106       if (zvec - gBase[zn] < 0                    \
 107        || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE)  \
 108          RETURN(BZ_DATA_ERROR);                   \
 109       lval = gPerm[zvec - gBase[zn]];             \
 110    }                                              \
 111 }                                                 \
 112
 113
 114 /*---------------------------------------------------*/
 115 Int32 BZ2_decompress ( DState* s )
 116 {
 117    UChar      uc;
 118    Int32      retVal;
 119    Int32      minLen, maxLen;
 120    bz_stream* strm = s->strm;
 121
 122    /* stuff that needs to be saved/restored */
 123    Int32  i;
 124    Int32  j;
 125    Int32  t;
 126    Int32  alphaSize;
 127    Int32  nGroups;
 128    Int32  nSelectors;
 129    Int32  EOB;
 130    Int32  groupNo;
 131    Int32  groupPos;
 132    Int32  nextSym;
 133    Int32  nblockMAX;
 134    Int32  nblock;
 135    Int32  es;
 136    Int32  N;
 137    Int32  curr;
 138    Int32  zt;
 139    Int32  zn;
 140    Int32  zvec;
 141    Int32  zj;
 142    Int32  gSel;
 143    Int32  gMinlen;
 144    Int32* gLimit;
 145    Int32* gBase;
 146    Int32* gPerm;
 147    Int16* gHufCode;
 148
 149    if (s->state == BZ_X_MAGIC_1) {
 150       /*initialise the save area*/
 151       s->save_i           = 0;
 152       s->save_j           = 0;
 153       s->save_t           = 0;
 154       s->save_alphaSize   = 0;
 155       s->save_nGroups     = 0;
 156       s->save_nSelectors  = 0;
 157       s->save_EOB         = 0;
 158       s->save_groupNo     = 0;
 159       s->save_groupPos    = 0;
 160       s->save_nextSym     = 0;
 161       s->save_nblockMAX   = 0;
 162       s->save_nblock      = 0;
 163       s->save_es          = 0;
 164       s->save_N           = 0;
 165       s->save_curr        = 0;
 166       s->save_zt          = 0;
 167       s->save_zn          = 0;
 168       s->save_zvec        = 0;
 169       s->save_zj          = 0;
 170       s->save_gSel        = 0;
 171       s->save_gMinlen     = 0;
 172       s->save_gLimit      = NULL;
 173       s->save_gBase       = NULL;
 174       s->save_gPerm       = NULL;
 175       s->save_gHufCode    = NULL;
 176    }
 177
 178    /*restore from the save area*/
 179    i           = s->save_i;
 180    j           = s->save_j;
 181    t           = s->save_t;
 182    alphaSize   = s->save_alphaSize;
 183    nGroups     = s->save_nGroups;
 184    nSelectors  = s->save_nSelectors;
 185    EOB         = s->save_EOB;
 186    groupNo     = s->save_groupNo;
 187    groupPos    = s->save_groupPos;
 188    nextSym     = s->save_nextSym;
 189    nblockMAX   = s->save_nblockMAX;
 190    nblock      = s->save_nblock;
 191    es          = s->save_es;
 192    N           = s->save_N;
 193    curr        = s->save_curr;
 194    zt          = s->save_zt;
 195    zn          = s->save_zn;
 196    zvec        = s->save_zvec;
 197    zj          = s->save_zj;
 198    gSel        = s->save_gSel;
 199    gMinlen     = s->save_gMinlen;
 200    gLimit      = s->save_gLimit;
 201    gBase       = s->save_gBase;
 202    gPerm       = s->save_gPerm;
 203    gHufCode    = s->save_gHufCode;
 204
 205    retVal = BZ_OK;
 206
 207    switch (s->state) {
 208
 209       GET_UCHAR(BZ_X_MAGIC_1, uc);
 210       if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
 211
 212       GET_UCHAR(BZ_X_MAGIC_2, uc);
 213       if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
 214
 215       GET_UCHAR(BZ_X_MAGIC_3, uc)
 216       if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
 217
 218       GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
 219       if (s->blockSize100k < (BZ_HDR_0 + 1) ||
 220           s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
 221       s->blockSize100k -= BZ_HDR_0;
 222
 223       if (s->smallDecompress) {
 224          s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
 225          s->ll4  = BZALLOC(
 226                       ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
 227                    );
 228          if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
 229       } else {
 230          s->tt  = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
 231          if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
 232       }
 233
 234       GET_UCHAR(BZ_X_BLKHDR_1, uc);
 235
 236       if (uc == 0x17) goto endhdr_2;
 237       if (uc != 0x31) RETURN(BZ_DATA_ERROR);
 238       GET_UCHAR(BZ_X_BLKHDR_2, uc);
 239       if (uc != 0x41) RETURN(BZ_DATA_ERROR);
 240       GET_UCHAR(BZ_X_BLKHDR_3, uc);
 241       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
 242       GET_UCHAR(BZ_X_BLKHDR_4, uc);
 243       if (uc != 0x26) RETURN(BZ_DATA_ERROR);
 244       GET_UCHAR(BZ_X_BLKHDR_5, uc);
 245       if (uc != 0x53) RETURN(BZ_DATA_ERROR);
 246       GET_UCHAR(BZ_X_BLKHDR_6, uc);
 247       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
 248
 249       s->currBlockNo++;
 250       if (s->verbosity >= 2)
 251          VPrintf1 ( "\n    [%d: huff+mtf ", s->currBlockNo );
 252
 253       s->storedBlockCRC = 0;
 254       GET_UCHAR(BZ_X_BCRC_1, uc);
 255       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
 256       GET_UCHAR(BZ_X_BCRC_2, uc);
 257       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
 258       GET_UCHAR(BZ_X_BCRC_3, uc);
 259       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
 260       GET_UCHAR(BZ_X_BCRC_4, uc);
 261       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
 262
 263       GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
 264
 265       s->origPtr = 0;
 266       GET_UCHAR(BZ_X_ORIGPTR_1, uc);
 267       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
 268       GET_UCHAR(BZ_X_ORIGPTR_2, uc);
 269       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
 270       GET_UCHAR(BZ_X_ORIGPTR_3, uc);
 271       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
 272
 273       if (s->origPtr < 0)
 274          RETURN(BZ_DATA_ERROR);
 275       if (s->origPtr > 10 + 100000*s->blockSize100k)
 276          RETURN(BZ_DATA_ERROR);
 277
 278       /*--- Receive the mapping table ---*/
 279       for (i = 0; i < 16; i++) {
 280          GET_BIT(BZ_X_MAPPING_1, uc);
 281          if (uc == 1)
 282             s->inUse16[i] = True; else
 283             s->inUse16[i] = False;
 284       }
 285
 286       for (i = 0; i < 256; i++) s->inUse[i] = False;
 287
 288       for (i = 0; i < 16; i++)
 289          if (s->inUse16[i])
 290             for (j = 0; j < 16; j++) {
 291                GET_BIT(BZ_X_MAPPING_2, uc);
 292                if (uc == 1) s->inUse[i * 16 + j] = True;
 293             }
 294       makeMaps_d ( s );
 295       if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
 296       alphaSize = s->nInUse+2;
 297
 298       /*--- Now the selectors ---*/
 299       GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
 300       if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
 301       GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
 302       if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
 303       for (i = 0; i < nSelectors; i++) {
 304          j = 0;
 305          while (True) {
 306             GET_BIT(BZ_X_SELECTOR_3, uc);
 307             if (uc == 0) break;
 308             j++;
 309             if (j >= nGroups) RETURN(BZ_DATA_ERROR);
 310          }
 311          s->selectorMtf[i] = j;
 312       }
 313
 314       /*--- Undo the MTF values for the selectors. ---*/
 315       {
 316          UChar pos[BZ_N_GROUPS], tmp, v;
 317          for (v = 0; v < nGroups; v++) pos[v] = v;
 318
 319          for (i = 0; i < nSelectors; i++) {
 320             v = s->selectorMtf[i];
 321             tmp = pos[v];
 322             while (v > 0) { pos[v] = pos[v-1]; v--; }
 323             pos[0] = tmp;
 324             s->selector[i] = tmp;
 325          }
 326       }
 327
 328       /*--- Now the coding tables ---*/
 329       for (t = 0; t < nGroups; t++) {
 330          GET_BITS(BZ_X_CODING_1, curr, 5);
 331          for (i = 0; i < alphaSize; i++) {
 332             while (True) {
 333                if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
 334                GET_BIT(BZ_X_CODING_2, uc);
 335                if (uc == 0) break;
 336                GET_BIT(BZ_X_CODING_3, uc);
 337                if (uc == 0) curr++; else curr--;
 338             }
 339             s->len[t][i] = curr;
 340          }
 341       }
 342
 343       /*--- Create the Huffman decoding tables ---*/
 344       for (t = 0; t < nGroups; t++) {
 345          minLen = 32;
 346          maxLen = 0;
 347          for (i = 0; i < alphaSize; i++) {
 348             if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
 349             if (s->len[t][i] < minLen) minLen = s->len[t][i];
 350          }
 351          BZ2_hbCreateDecodeTables (
 352             &(s->limit[t][0]),
 353             &(s->base[t][0]),
 354             &(s->perm[t][0]),
 355             &(s->hufcode[t][0]),
 356             &(s->len[t][0]),
 357             minLen, maxLen, alphaSize
 358          );
 359          s->minLens[t] = minLen;
 360       }
 361
 362       /*--- Now the MTF values ---*/
 363
 364       EOB      = s->nInUse+1;
 365       nblockMAX = 100000 * s->blockSize100k;
 366       groupNo  = -1;
 367       groupPos = 0;
 368
 369       for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
 370
 371       /*-- MTF init --*/
 372       {
 373          Int32 ii, jj, kk;
 374          kk = MTFA_SIZE-1;
 375          for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
 376             for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
 377                s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
 378                kk--;
 379             }
 380             s->mtfbase[ii] = kk + 1;
 381          }
 382       }
 383       /*-- end MTF init --*/
 384
 385       nblock = 0;
 386       GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
 387
 388       while (True) {
 389
 390          if (nextSym == EOB) break;
 391
 392          if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
 393
 394             es = -1;
 395             N = 1;
 396             do {
 397                /* Check that N doesn't get too big, so that es doesn't
 398                   go negative.  The maximum value that can be
 399                   RUNA/RUNB encoded is equal to the block size (post
 400                   the initial RLE), viz, 900k, so bounding N at 2
 401                   million should guard against overflow without
 402                   rejecting any legitimate inputs. */
 403                if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
 404                if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
 405                if (nextSym == BZ_RUNB) es = es + (1+1) * N;
 406                N = N * 2;
 407                GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
 408             }
 409                while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
 410
 411             es++;
 412             uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
 413             s->unzftab[uc] += es;
 414
 415             if (s->smallDecompress)
 416                while (es > 0) {
 417                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
 418                   s->ll16[nblock] = (UInt16)uc;
 419                   nblock++;
 420                   es--;
 421                }
 422             else
 423                while (es > 0) {
 424                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
 425                   s->tt[nblock] = (UInt32)uc;
 426                   nblock++;
 427                   es--;
 428                };
 429
 430             continue;
 431
 432          } else {
 433
 434             if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
 435
 436             /*-- uc = MTF ( nextSym-1 ) --*/
 437 #if MTFL_SIZE == 16
 438             {
 439                unsigned char *ppx = s->mtfa + s->mtfbase[0];
 440                int lno = 0;
 441
 442                nextSym--;
 443                if (nextSym >= MTFL_SIZE) {
 444                   lno = nextSym / MTFL_SIZE;
 445                   nextSym %= MTFL_SIZE;
 446                   ppx = s->mtfa + s->mtfbase[lno];
 447                }
 448                uc = ppx[nextSym];
 449                switch(nextSym) {
 450                   case 9:  ppx[9]  = ppx[10];
 451                   case 10: ppx[10] = ppx[11];
 452                   case 11: ppx[11] = ppx[12];
 453                   case 12: ppx[12] = ppx[13];
 454                   case 13: ppx[13] = ppx[14];
 455                   case 14: ppx[14] = ppx[15];
 456                   case 15: goto copy;
 457
 458                   case 8: ppx[8] = ppx[7];
 459                   case 7: ppx[7] = ppx[6];
 460                   case 6: ppx[6] = ppx[5];
 461                   case 5: ppx[5] = ppx[4];
 462                   case 4: ppx[4] = ppx[3];
 463                   case 3: ppx[3] = ppx[2];
 464                   case 2: ppx[2] = ppx[1];
 465                   case 1: ppx[1] = ppx[0];
 466                   default: break;
 467                }
 468                if (lno) {
 469                   s->mtfbase[lno]++;
 470                copy:
 471                   while (lno > 0) {
 472                      s->mtfbase[lno]--;
 473                      s->mtfa[s->mtfbase[lno]] = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
 474                      lno--;
 475                   }
 476                   s->mtfbase[0]--;
 477                   if (s->mtfbase[0] == 0) {
 478                      int ii, jj, kk;
 479                      s->mtfa[0] = uc;
 480                      kk = MTFA_SIZE-1;
 481                      for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
 482                         for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
 483                            s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
 484                            kk--;
 485                         }
 486                         s->mtfbase[ii] = kk + 1;
 487                      }
 488                   }
 489                }
 490                s->mtfa[s->mtfbase[0]] = uc;
 491             }
 492 #else
 493             {
 494                Int32 ii, jj, kk, pp, lno, off;
 495                UInt32 nn;
 496                nn = (UInt32)(nextSym - 1);
 497
 498                if (nn < MTFL_SIZE) {
 499                   /* avoid general-case expense */
 500                   pp = s->mtfbase[0];
 501                   uc = s->mtfa[pp+nn];
 502                   while (nn > 3) {
 503                      Int32 z = pp+nn;
 504                      s->mtfa[(z)  ] = s->mtfa[(z)-1];
 505                      s->mtfa[(z)-1] = s->mtfa[(z)-2];
 506                      s->mtfa[(z)-2] = s->mtfa[(z)-3];
 507                      s->mtfa[(z)-3] = s->mtfa[(z)-4];
 508                      nn -= 4;
 509                   }
 510                   while (nn > 0) {
 511                      s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
 512                   };
 513                   s->mtfa[pp] = uc;
 514                } else {
 515                   /* general case */
 516                   lno = nn / MTFL_SIZE;
 517                   off = nn % MTFL_SIZE;
 518                   pp = s->mtfbase[lno] + off;
 519                   uc = s->mtfa[pp];
 520                   while (pp > s->mtfbase[lno]) {
 521                      s->mtfa[pp] = s->mtfa[pp-1]; pp--;
 522                   };
 523                   s->mtfbase[lno]++;
 524                   while (lno > 0) {
 525                      s->mtfbase[lno]--;
 526                      s->mtfa[s->mtfbase[lno]]
 527                         = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
 528                      lno--;
 529                   }
 530                   s->mtfbase[0]--;
 531                   s->mtfa[s->mtfbase[0]] = uc;
 532                   if (s->mtfbase[0] == 0) {
 533                      kk = MTFA_SIZE-1;
 534                      for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
 535                         for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
 536                            s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
 537                            kk--;
 538                         }
 539                         s->mtfbase[ii] = kk + 1;
 540                      }
 541                   }
 542                }
 543             }
 544 #endif
 545             /*-- end uc = MTF ( nextSym-1 ) --*/
 546
 547             s->unzftab[s->seqToUnseq[uc]]++;
 548             if (s->smallDecompress)
 549                s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
 550                s->tt[nblock]   = (UInt32)(s->seqToUnseq[uc]);
 551             nblock++;
 552
 553             GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
 554             continue;
 555          }
 556       }
 557
 558       /* Now we know what nblock is, we can do a better sanity
 559          check on s->origPtr.
 560       */
 561       if (s->origPtr < 0 || s->origPtr >= nblock)
 562          RETURN(BZ_DATA_ERROR);
 563
 564       /*-- Set up cftab to facilitate generation of T^(-1) --*/
 565       /* Check: unzftab entries in range. */
 566       for (i = 0; i <= 255; i++) {
 567          if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)
 568             RETURN(BZ_DATA_ERROR);
 569       }
 570       /* Actually generate cftab. */
 571       s->cftab[0] = 0;
 572       for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
 573       for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
 574       /* Check: cftab entries in range. */
 575       for (i = 0; i <= 256; i++) {
 576          if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
 577             /* s->cftab[i] can legitimately be == nblock */
 578             RETURN(BZ_DATA_ERROR);
 579          }
 580       }
 581       /* Check: cftab entries non-descending. */
 582       for (i = 1; i <= 256; i++) {
 583          if (s->cftab[i-1] > s->cftab[i]) {
 584             RETURN(BZ_DATA_ERROR);
 585          }
 586       }
 587
 588       s->state_out_len = 0;
 589       s->state_out_ch  = 0;
 590       BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
 591       s->state = BZ_X_OUTPUT;
 592       if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
 593
 594       if (s->smallDecompress) {
 595
 596          /*-- Make a copy of cftab, used in generation of T --*/
 597          for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
 598
 599          /*-- compute the T vector --*/
 600          for (i = 0; i < nblock; i++) {
 601             uc = (UChar)(s->ll16[i]);
 602             SET_LL(i, s->cftabCopy[uc]);
 603             s->cftabCopy[uc]++;
 604          }
 605
 606          /*-- Compute T^(-1) by pointer reversal on T --*/
 607          i = s->origPtr;
 608          j = GET_LL(i);
 609          do {
 610             Int32 tmp = GET_LL(j);
 611             SET_LL(j, i);
 612             i = j;
 613             j = tmp;
 614          }
 615             while (i != s->origPtr);
 616
 617          s->tPos = s->origPtr;
 618          s->nblock_used = 0;
 619          if (s->blockRandomised) {
 620             BZ_RAND_INIT_MASK;
 621             BZ_GET_SMALL(s->k0); s->nblock_used++;
 622             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
 623          } else {
 624             BZ_GET_SMALL(s->k0); s->nblock_used++;
 625          }
 626
 627       } else {
 628
 629          /*-- compute the T^(-1) vector --*/
 630          for (i = 0; i < nblock; i++) {
 631             uc = (UChar)(s->tt[i] & 0xff);
 632             s->tt[s->cftab[uc]] |= (i << 8);
 633             s->cftab[uc]++;
 634          }
 635
 636          s->tPos = s->tt[s->origPtr] >> 8;
 637          s->nblock_used = 0;
 638          if (s->blockRandomised) {
 639             BZ_RAND_INIT_MASK;
 640             BZ_GET_FAST(s->k0); s->nblock_used++;
 641             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
 642          } else {
 643             BZ_GET_FAST(s->k0); s->nblock_used++;
 644          }
 645
 646       }
 647
 648       RETURN(BZ_OK);
 649
 650
 651
 652     endhdr_2:
 653
 654       GET_UCHAR(BZ_X_ENDHDR_2, uc);
 655       if (uc != 0x72) RETURN(BZ_DATA_ERROR);
 656       GET_UCHAR(BZ_X_ENDHDR_3, uc);
 657       if (uc != 0x45) RETURN(BZ_DATA_ERROR);
 658       GET_UCHAR(BZ_X_ENDHDR_4, uc);
 659       if (uc != 0x38) RETURN(BZ_DATA_ERROR);
 660       GET_UCHAR(BZ_X_ENDHDR_5, uc);
 661       if (uc != 0x50) RETURN(BZ_DATA_ERROR);
 662       GET_UCHAR(BZ_X_ENDHDR_6, uc);
 663       if (uc != 0x90) RETURN(BZ_DATA_ERROR);
 664
 665       s->storedCombinedCRC = 0;
 666       GET_UCHAR(BZ_X_CCRC_1, uc);
 667       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
 668       GET_UCHAR(BZ_X_CCRC_2, uc);
 669       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
 670       GET_UCHAR(BZ_X_CCRC_3, uc);
 671       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
 672       GET_UCHAR(BZ_X_CCRC_4, uc);
 673       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
 674
 675       s->state = BZ_X_IDLE;
 676       RETURN(BZ_STREAM_END);
 677
 678       default: AssertH ( False, 4001 );
 679    }
 680
 681    AssertH ( False, 4002 );
 682
 683    save_state_and_return:
 684
 685    s->save_i           = i;
 686    s->save_j           = j;
 687    s->save_t           = t;
 688    s->save_alphaSize   = alphaSize;
 689    s->save_nGroups     = nGroups;
 690    s->save_nSelectors  = nSelectors;
 691    s->save_EOB         = EOB;
 692    s->save_groupNo     = groupNo;
 693    s->save_groupPos    = groupPos;
 694    s->save_nextSym     = nextSym;
 695    s->save_nblockMAX   = nblockMAX;
 696    s->save_nblock      = nblock;
 697    s->save_es          = es;
 698    s->save_N           = N;
 699    s->save_curr        = curr;
 700    s->save_zt          = zt;
 701    s->save_zn          = zn;
 702    s->save_zvec        = zvec;
 703    s->save_zj          = zj;
 704    s->save_gSel        = gSel;
 705    s->save_gMinlen     = gMinlen;
 706    s->save_gLimit      = gLimit;
 707    s->save_gBase       = gBase;
 708    s->save_gPerm       = gPerm;
 709    s->save_gHufCode    = gHufCode;
 710
 711    return retVal;
 712 }
 713
 714
 715 /*-------------------------------------------------------------*/
 716 /*--- end                                      decompress.c ---*/
 717 /*-------------------------------------------------------------*/