sys/src/cmd/bzfs/unbzip.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <bio.h>
   4 #include "bzfs.h"
   5
   6 /*
   7  * THIS FILE IS NOT IDENTICAL TO THE ORIGINAL
   8  * FROM THE BZIP2 DISTRIBUTION.
   9  *
  10  * It has been modified, mainly to break the library
  11  * into smaller pieces.
  12  *
  13  * Russ Cox
  14  * rsc@plan9.bell-labs.com
  15  * July 2000
  16  */
  17
  18 /*---------------------------------------------*/
  19 /*--
  20   Place a 1 beside your platform, and 0 elsewhere.
  21   Attempts to autosniff this even if you don't.
  22 --*/
  23
  24
  25 /*--
  26   Plan 9 from Bell Labs
  27 --*/
  28 #define BZ_PLAN9     1
  29 #define BZ_UNIX 0
  30
  31 #define exit(x) exits((x) ? "whoops" : nil)
  32 #define size_t ulong
  33
  34 #ifdef __GNUC__
  35 #   define NORETURN __attribute__ ((noreturn))
  36 #else
  37 #   define NORETURN /**/
  38 #endif
  39
  40 /*--
  41   Some more stuff for all platforms :-)
  42   This might have to get moved into the platform-specific
  43   header files if we encounter a machine with different sizes.
  44 --*/
  45
  46 typedef char            Char;
  47 typedef unsigned char   Bool;
  48 typedef unsigned char   UChar;
  49 typedef int             Int32;
  50 typedef unsigned int    UInt32;
  51 typedef short           Int16;
  52 typedef unsigned short  UInt16;
  53
  54 #define True  ((Bool)1)
  55 #define False ((Bool)0)
  56
  57 /*--
  58   IntNative is your platform's `native' int size.
  59   Only here to avoid probs with 64-bit platforms.
  60 --*/
  61 typedef int IntNative;
  62
  63 #include "bzfs.h"
  64 #include "bzlib.h"
  65 #include "bzlib_private.h"
  66
  67 static int
  68 bunzip(int ofd, char *ofile, Biobuf *bin)
  69 {
  70         int e, n, done, onemore;
  71         char buf[8192];
  72         char obuf[8192];
  73         Biobuf bout;
  74         bz_stream strm;
  75
  76         USED(ofile);
  77
  78         memset(&strm, 0, sizeof strm);
  79         BZ2_bzDecompressInit(&strm, 0, 0);
  80
  81         strm.next_in = buf;
  82         strm.avail_in = 0;
  83         strm.next_out = obuf;
  84         strm.avail_out = sizeof obuf;
  85
  86         done = 0;
  87         Binit(&bout, ofd, OWRITE);
  88
  89         /*
  90          * onemore is a crummy hack to go 'round the loop
  91          * once after we finish, to flush the output buffer.
  92          */
  93         onemore = 1;
  94         SET(e);
  95         do {
  96                 if(!done && strm.avail_in < sizeof buf) {
  97                         if(strm.avail_in)
  98                                 memmove(buf, strm.next_in, strm.avail_in);
  99
 100                         n = Bread(bin, buf+strm.avail_in, sizeof(buf)-strm.avail_in);
 101                         if(n <= 0)
 102                                 done = 1;
 103                         else
 104                                 strm.avail_in += n;
 105                         strm.next_in = buf;
 106                 }
 107                 if(strm.avail_out < sizeof obuf) {
 108                         Bwrite(&bout, obuf, sizeof(obuf)-strm.avail_out);
 109                         strm.next_out = obuf;
 110                         strm.avail_out = sizeof obuf;
 111                 }
 112
 113                 if(onemore == 0)
 114                         break;
 115         } while((e=BZ2_bzDecompress(&strm)) == BZ_OK || onemore--);
 116
 117         if(e != BZ_STREAM_END) {
 118                 fprint(2, "bunzip2: decompress failed\n");
 119                 return 0;
 120         }
 121
 122         if(BZ2_bzDecompressEnd(&strm) != BZ_OK) {
 123                 fprint(2, "bunzip2: decompress end failed (can't happen)\n");
 124                 return 0;
 125         }
 126
 127         Bterm(&bout);
 128
 129         return 1;
 130 }
 131
 132 void
 133 _unbzip(int in, int out)
 134 {
 135         Biobuf bin;
 136
 137         Binit(&bin, in, OREAD);
 138         if(bunzip(out, nil, &bin) != 1) {
 139                 fprint(2, "bunzip2 failed\n");
 140                 _exits("bunzip2");
 141         }
 142 }
 143
 144 int
 145 unbzip(int in)
 146 {
 147         int rv, out, p[2];
 148
 149         if(pipe(p) < 0)
 150                 sysfatal("pipe: %r");
 151
 152         rv = p[0];
 153         out = p[1];
 154         switch(rfork(RFPROC|RFFDG|RFNOTEG|RFMEM)){
 155         case -1:
 156                 sysfatal("fork: %r");
 157         case 0:
 158                 close(rv);
 159                 break;
 160         default:
 161                 close(in);
 162                 close(out);
 163                 return rv;
 164         }
 165
 166         _unbzip(in, out);
 167         _exits(0);
 168         return -1;      /* not reached */
 169 }
 170
 171 int bz_config_ok ( void )
 172 {
 173    if (sizeof(int)   != 4) return 0;
 174    if (sizeof(short) != 2) return 0;
 175    if (sizeof(char)  != 1) return 0;
 176    return 1;
 177 }
 178
 179 void* default_bzalloc(void *o, int items, int size)
 180 {
 181         USED(o);
 182         return sbrk(items*size);
 183 }
 184
 185 void default_bzfree(void*, void*)
 186 {
 187 }
 188
 189 void
 190 bz_internal_error(int)
 191 {
 192         abort();
 193 }
 194
 195 /*-------------------------------------------------------------*/
 196 /*--- Decompression machinery                               ---*/
 197 /*---                                          decompress.c ---*/
 198 /*-------------------------------------------------------------*/
 199
 200 /*--
 201   This file is a part of bzip2 and/or libbzip2, a program and
 202   library for lossless, block-sorting data compression.
 203
 204   Copyright (C) 1996-2000 Julian R Seward.  All rights reserved.
 205
 206   Redistribution and use in source and binary forms, with or without
 207   modification, are permitted provided that the following conditions
 208   are met:
 209
 210   1. Redistributions of source code must retain the above copyright
 211      notice, this list of conditions and the following disclaimer.
 212
 213   2. The origin of this software must not be misrepresented; you must
 214      not claim that you wrote the original software.  If you use this
 215      software in a product, an acknowledgment in the product
 216      documentation would be appreciated but is not required.
 217
 218   3. Altered source versions must be plainly marked as such, and must
 219      not be misrepresented as being the original software.
 220
 221   4. The name of the author may not be used to endorse or promote
 222      products derived from this software without specific prior written
 223      permission.
 224
 225   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
 226   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 227   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 228   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 229   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 230   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 231   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 232   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 233   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 234   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 235   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 236
 237   Julian Seward, Cambridge, UK.
 238   jseward@acm.org
 239   bzip2/libbzip2 version 1.0 of 21 March 2000
 240
 241   This program is based on (at least) the work of:
 242      Mike Burrows
 243      David Wheeler
 244      Peter Fenwick
 245      Alistair Moffat
 246      Radford Neal
 247      Ian H. Witten
 248      Robert Sedgewick
 249      Jon L. Bentley
 250
 251   For more information on these sources, see the manual.
 252 --*/
 253
 254
 255
 256 /*---------------------------------------------------*/
 257 static
 258 void makeMaps_d ( DState* s )
 259 {
 260    Int32 i;
 261    s->nInUse = 0;
 262    for (i = 0; i < 256; i++)
 263       if (s->inUse[i]) {
 264          s->seqToUnseq[s->nInUse] = i;
 265          s->nInUse++;
 266       }
 267 }
 268
 269
 270 /*---------------------------------------------------*/
 271 #define RETURN(rrr)                               \
 272    { retVal = rrr; goto save_state_and_return; };
 273
 274 #define GET_BITS(lll,vvv,nnn)                     \
 275         case lll: \
 276                 { int x; if((retVal = getbits(s, lll, &x, nnn)) != 99) \
 277                         goto save_state_and_return; vvv=x; }\
 278
 279 int
 280 getbits(DState *s, int lll, int *vvv, int nnn)
 281 {
 282         s->state = lll;
 283
 284         for(;;) {
 285                 if (s->bsLive >= nnn) {
 286                         UInt32 v;
 287                         v = (s->bsBuff >>
 288                                  (s->bsLive-nnn)) & ((1 << nnn)-1);
 289                         s->bsLive -= nnn;
 290                         *vvv = v;
 291                         return 99;
 292                 }
 293                 if (s->strm->avail_in == 0) return BZ_OK;
 294                 s->bsBuff
 295                         = (s->bsBuff << 8) |
 296                           ((UInt32)
 297                                   (*((UChar*)(s->strm->next_in))));
 298                 s->bsLive += 8;
 299                 s->strm->next_in++;
 300                 s->strm->avail_in--;
 301                 s->strm->total_in_lo32++;
 302                 if (s->strm->total_in_lo32 == 0)
 303                         s->strm->total_in_hi32++;
 304         }
 305 }
 306
 307 #define GET_UCHAR(lll,uuu)                        \
 308    GET_BITS(lll,uuu,8)
 309
 310 #define GET_BIT(lll,uuu)                          \
 311    GET_BITS(lll,uuu,1)
 312
 313 /*---------------------------------------------------*/
 314 #define GET_MTF_VAL(label1,label2,lval)           \
 315 {                                                 \
 316    if (groupPos == 0) {                           \
 317       groupNo++;                                  \
 318       if (groupNo >= nSelectors)                  \
 319          RETURN(BZ_DATA_ERROR);                   \
 320       groupPos = BZ_G_SIZE;                       \
 321       gSel = s->selector[groupNo];                \
 322       gMinlen = s->minLens[gSel];                 \
 323       gLimit = &(s->limit[gSel][0]);              \
 324       gPerm = &(s->perm[gSel][0]);                \
 325       gBase = &(s->base[gSel][0]);                \
 326    }                                              \
 327    groupPos--;                                    \
 328    zn = gMinlen;                                  \
 329    GET_BITS(label1, zvec, zn);                    \
 330    while (1) {                                    \
 331       if (zn > 20 /* the longest code */)         \
 332          RETURN(BZ_DATA_ERROR);                   \
 333       if (zvec <= gLimit[zn]) break;              \
 334       zn++;                                       \
 335       GET_BIT(label2, zj);                        \
 336       zvec = (zvec << 1) | zj;                    \
 337    };                                             \
 338    if (zvec - gBase[zn] < 0                       \
 339        || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE)  \
 340       RETURN(BZ_DATA_ERROR);                      \
 341    lval = gPerm[zvec - gBase[zn]];                \
 342 }
 343
 344
 345 /*---------------------------------------------------*/
 346 Int32 BZ2_decompress ( DState* s )
 347 {
 348    UChar      uc;
 349    Int32      retVal;
 350    Int32      minLen, maxLen;
 351    bz_stream* strm = s->strm;
 352
 353    /* stuff that needs to be saved/restored */
 354    Int32  i;
 355    Int32  j;
 356    Int32  t;
 357    Int32  alphaSize;
 358    Int32  nGroups;
 359    Int32  nSelectors;
 360    Int32  EOB;
 361    Int32  groupNo;
 362    Int32  groupPos;
 363    Int32  nextSym;
 364    Int32  nblockMAX;
 365    Int32  nblock;
 366    Int32  es;
 367    Int32  N;
 368    Int32  curr;
 369    Int32  zt;
 370    Int32  zn;
 371    Int32  zvec;
 372    Int32  zj;
 373    Int32  gSel;
 374    Int32  gMinlen;
 375    Int32* gLimit;
 376    Int32* gBase;
 377    Int32* gPerm;
 378
 379    if (s->state == BZ_X_MAGIC_1) {
 380       /*initialise the save area*/
 381       s->save_i           = 0;
 382       s->save_j           = 0;
 383       s->save_t           = 0;
 384       s->save_alphaSize   = 0;
 385       s->save_nGroups     = 0;
 386       s->save_nSelectors  = 0;
 387       s->save_EOB         = 0;
 388       s->save_groupNo     = 0;
 389       s->save_groupPos    = 0;
 390       s->save_nextSym     = 0;
 391       s->save_nblockMAX   = 0;
 392       s->save_nblock      = 0;
 393       s->save_es          = 0;
 394       s->save_N           = 0;
 395       s->save_curr        = 0;
 396       s->save_zt          = 0;
 397       s->save_zn          = 0;
 398       s->save_zvec        = 0;
 399       s->save_zj          = 0;
 400       s->save_gSel        = 0;
 401       s->save_gMinlen     = 0;
 402       s->save_gLimit      = NULL;
 403       s->save_gBase       = NULL;
 404       s->save_gPerm       = NULL;
 405    }
 406
 407    /*restore from the save area*/
 408    i           = s->save_i;
 409    j           = s->save_j;
 410    t           = s->save_t;
 411    alphaSize   = s->save_alphaSize;
 412    nGroups     = s->save_nGroups;
 413    nSelectors  = s->save_nSelectors;
 414    EOB         = s->save_EOB;
 415    groupNo     = s->save_groupNo;
 416    groupPos    = s->save_groupPos;
 417    nextSym     = s->save_nextSym;
 418    nblockMAX   = s->save_nblockMAX;
 419    nblock      = s->save_nblock;
 420    es          = s->save_es;
 421    N           = s->save_N;
 422    curr        = s->save_curr;
 423    zt          = s->save_zt;
 424    zn          = s->save_zn;
 425    zvec        = s->save_zvec;
 426    zj          = s->save_zj;
 427    gSel        = s->save_gSel;
 428    gMinlen     = s->save_gMinlen;
 429    gLimit      = s->save_gLimit;
 430    gBase       = s->save_gBase;
 431    gPerm       = s->save_gPerm;
 432
 433    retVal = BZ_OK;
 434
 435    switch (s->state) {
 436
 437       GET_UCHAR(BZ_X_MAGIC_1, uc);
 438       if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC);
 439
 440       GET_UCHAR(BZ_X_MAGIC_2, uc);
 441       if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC);
 442
 443       GET_UCHAR(BZ_X_MAGIC_3, uc)
 444       if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC);
 445
 446       GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
 447       if (s->blockSize100k < '1' ||
 448           s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC);
 449       s->blockSize100k -= '0';
 450
 451       if (0 && s->smallDecompress) {
 452          s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
 453          s->ll4  = BZALLOC(
 454                       ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
 455                    );
 456          if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
 457       } else {
 458          s->tt  = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
 459          if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
 460       }
 461
 462       GET_UCHAR(BZ_X_BLKHDR_1, uc);
 463
 464       if (uc == 0x17) goto endhdr_2;
 465       if (uc != 0x31) RETURN(BZ_DATA_ERROR);
 466       GET_UCHAR(BZ_X_BLKHDR_2, uc);
 467       if (uc != 0x41) RETURN(BZ_DATA_ERROR);
 468       GET_UCHAR(BZ_X_BLKHDR_3, uc);
 469       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
 470       GET_UCHAR(BZ_X_BLKHDR_4, uc);
 471       if (uc != 0x26) RETURN(BZ_DATA_ERROR);
 472       GET_UCHAR(BZ_X_BLKHDR_5, uc);
 473       if (uc != 0x53) RETURN(BZ_DATA_ERROR);
 474       GET_UCHAR(BZ_X_BLKHDR_6, uc);
 475       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
 476
 477       s->currBlockNo++;
 478     //  if (s->verbosity >= 2)
 479     //     VPrintf1 ( "\n    [%d: huff+mtf ", s->currBlockNo );
 480
 481       s->storedBlockCRC = 0;
 482       GET_UCHAR(BZ_X_BCRC_1, uc);
 483       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
 484       GET_UCHAR(BZ_X_BCRC_2, uc);
 485       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
 486       GET_UCHAR(BZ_X_BCRC_3, uc);
 487       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
 488       GET_UCHAR(BZ_X_BCRC_4, uc);
 489       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
 490
 491       GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
 492
 493       s->origPtr = 0;
 494       GET_UCHAR(BZ_X_ORIGPTR_1, uc);
 495       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
 496       GET_UCHAR(BZ_X_ORIGPTR_2, uc);
 497       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
 498       GET_UCHAR(BZ_X_ORIGPTR_3, uc);
 499       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
 500
 501       if (s->origPtr < 0)
 502          RETURN(BZ_DATA_ERROR);
 503       if (s->origPtr > 10 + 100000*s->blockSize100k)
 504          RETURN(BZ_DATA_ERROR);
 505
 506       /*--- Receive the mapping table ---*/
 507       for (i = 0; i < 16; i++) {
 508          GET_BIT(BZ_X_MAPPING_1, uc);
 509          if (uc == 1)
 510             s->inUse16[i] = True; else
 511             s->inUse16[i] = False;
 512       }
 513
 514       for (i = 0; i < 256; i++) s->inUse[i] = False;
 515
 516       for (i = 0; i < 16; i++)
 517          if (s->inUse16[i])
 518             for (j = 0; j < 16; j++) {
 519                GET_BIT(BZ_X_MAPPING_2, uc);
 520                if (uc == 1) s->inUse[i * 16 + j] = True;
 521             }
 522       makeMaps_d ( s );
 523       if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
 524       alphaSize = s->nInUse+2;
 525
 526       /*--- Now the selectors ---*/
 527       GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
 528       if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
 529       GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
 530       if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
 531       for (i = 0; i < nSelectors; i++) {
 532          j = 0;
 533          while (True) {
 534             GET_BIT(BZ_X_SELECTOR_3, uc);
 535             if (uc == 0) break;
 536             j++;
 537             if (j >= nGroups) RETURN(BZ_DATA_ERROR);
 538          }
 539          s->selectorMtf[i] = j;
 540       }
 541
 542       /*--- Undo the MTF values for the selectors. ---*/
 543       {
 544          UChar pos[BZ_N_GROUPS], tmp, v;
 545          for (v = 0; v < nGroups; v++) pos[v] = v;
 546
 547          for (i = 0; i < nSelectors; i++) {
 548             v = s->selectorMtf[i];
 549             tmp = pos[v];
 550             while (v > 0) { pos[v] = pos[v-1]; v--; }
 551             pos[0] = tmp;
 552             s->selector[i] = tmp;
 553          }
 554       }
 555
 556       /*--- Now the coding tables ---*/
 557       for (t = 0; t < nGroups; t++) {
 558          GET_BITS(BZ_X_CODING_1, curr, 5);
 559          for (i = 0; i < alphaSize; i++) {
 560             while (True) {
 561                if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
 562                GET_BIT(BZ_X_CODING_2, uc);
 563                if (uc == 0) break;
 564                GET_BIT(BZ_X_CODING_3, uc);
 565                if (uc == 0) curr++; else curr--;
 566             }
 567             s->len[t][i] = curr;
 568          }
 569       }
 570
 571       /*--- Create the Huffman decoding tables ---*/
 572       for (t = 0; t < nGroups; t++) {
 573          minLen = 32;
 574          maxLen = 0;
 575          for (i = 0; i < alphaSize; i++) {
 576             if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
 577             if (s->len[t][i] < minLen) minLen = s->len[t][i];
 578          }
 579          BZ2_hbCreateDecodeTables (
 580             &(s->limit[t][0]),
 581             &(s->base[t][0]),
 582             &(s->perm[t][0]),
 583             &(s->len[t][0]),
 584             minLen, maxLen, alphaSize
 585          );
 586          s->minLens[t] = minLen;
 587       }
 588
 589       /*--- Now the MTF values ---*/
 590
 591       EOB      = s->nInUse+1;
 592       nblockMAX = 100000 * s->blockSize100k;
 593       groupNo  = -1;
 594       groupPos = 0;
 595
 596       for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
 597
 598       /*-- MTF init --*/
 599       {
 600          Int32 ii, jj, kk;
 601          kk = MTFA_SIZE-1;
 602          for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
 603             for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
 604                s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
 605                kk--;
 606             }
 607             s->mtfbase[ii] = kk + 1;
 608          }
 609       }
 610       /*-- end MTF init --*/
 611
 612       nblock = 0;
 613       GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
 614
 615       while (True) {
 616
 617          if (nextSym == EOB) break;
 618
 619          if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
 620
 621             es = -1;
 622             N = 1;
 623             do {
 624                if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
 625                if (nextSym == BZ_RUNB) es = es + (1+1) * N;
 626                N = N * 2;
 627                GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
 628             }
 629                while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
 630
 631             es++;
 632             uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
 633             s->unzftab[uc] += es;
 634
 635             if (0 && s->smallDecompress)
 636                while (es > 0) {
 637                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
 638                   s->ll16[nblock] = (UInt16)uc;
 639                   nblock++;
 640                   es--;
 641                }
 642             else
 643                while (es > 0) {
 644                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
 645                   s->tt[nblock] = (UInt32)uc;
 646                   nblock++;
 647                   es--;
 648                };
 649
 650             continue;
 651
 652          } else {
 653
 654             if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
 655
 656             /*-- uc = MTF ( nextSym-1 ) --*/
 657             {
 658                Int32 ii, jj, kk, pp, lno, off;
 659                UInt32 nn;
 660                nn = (UInt32)(nextSym - 1);
 661
 662                if (nn < MTFL_SIZE) {
 663                   /* avoid general-case expense */
 664                   pp = s->mtfbase[0];
 665                   uc = s->mtfa[pp+nn];
 666                   while (nn > 3) {
 667                      Int32 z = pp+nn;
 668                      s->mtfa[(z)  ] = s->mtfa[(z)-1];
 669                      s->mtfa[(z)-1] = s->mtfa[(z)-2];
 670                      s->mtfa[(z)-2] = s->mtfa[(z)-3];
 671                      s->mtfa[(z)-3] = s->mtfa[(z)-4];
 672                      nn -= 4;
 673                   }
 674                   while (nn > 0) {
 675                      s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
 676                   };
 677                   s->mtfa[pp] = uc;
 678                } else {
 679                   /* general case */
 680                   lno = nn / MTFL_SIZE;
 681                   off = nn % MTFL_SIZE;
 682                   pp = s->mtfbase[lno] + off;
 683                   uc = s->mtfa[pp];
 684                   while (pp > s->mtfbase[lno]) {
 685                      s->mtfa[pp] = s->mtfa[pp-1]; pp--;
 686                   };
 687                   s->mtfbase[lno]++;
 688                   while (lno > 0) {
 689                      s->mtfbase[lno]--;
 690                      s->mtfa[s->mtfbase[lno]]
 691                         = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
 692                      lno--;
 693                   }
 694                   s->mtfbase[0]--;
 695                   s->mtfa[s->mtfbase[0]] = uc;
 696                   if (s->mtfbase[0] == 0) {
 697                      kk = MTFA_SIZE-1;
 698                      for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
 699                         for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
 700                            s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
 701                            kk--;
 702                         }
 703                         s->mtfbase[ii] = kk + 1;
 704                      }
 705                   }
 706                }
 707             }
 708             /*-- end uc = MTF ( nextSym-1 ) --*/
 709
 710             s->unzftab[s->seqToUnseq[uc]]++;
 711             if (0 && s->smallDecompress)
 712                s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
 713                s->tt[nblock]   = (UInt32)(s->seqToUnseq[uc]);
 714             nblock++;
 715
 716             GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
 717             continue;
 718          }
 719       }
 720
 721       /* Now we know what nblock is, we can do a better sanity
 722          check on s->origPtr.
 723       */
 724       if (s->origPtr < 0 || s->origPtr >= nblock)
 725          RETURN(BZ_DATA_ERROR);
 726
 727       s->state_out_len = 0;
 728       s->state_out_ch  = 0;
 729       BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
 730       s->state = BZ_X_OUTPUT;
 731     //  if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
 732
 733       /*-- Set up cftab to facilitate generation of T^(-1) --*/
 734       s->cftab[0] = 0;
 735       for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
 736       for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
 737
 738       if (0 && s->smallDecompress) {
 739
 740          /*-- Make a copy of cftab, used in generation of T --*/
 741          for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
 742
 743          /*-- compute the T vector --*/
 744          for (i = 0; i < nblock; i++) {
 745             uc = (UChar)(s->ll16[i]);
 746             SET_LL(i, s->cftabCopy[uc]);
 747             s->cftabCopy[uc]++;
 748          }
 749
 750          /*-- Compute T^(-1) by pointer reversal on T --*/
 751          i = s->origPtr;
 752          j = GET_LL(i);
 753          do {
 754             Int32 tmp = GET_LL(j);
 755             SET_LL(j, i);
 756             i = j;
 757             j = tmp;
 758          }
 759             while (i != s->origPtr);
 760
 761          s->tPos = s->origPtr;
 762          s->nblock_used = 0;
 763          if (s->blockRandomised) {
 764             BZ_RAND_INIT_MASK;
 765             BZ_GET_SMALL(s->k0); s->nblock_used++;
 766             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
 767          } else {
 768             BZ_GET_SMALL(s->k0); s->nblock_used++;
 769          }
 770
 771       } else {
 772
 773          /*-- compute the T^(-1) vector --*/
 774          for (i = 0; i < nblock; i++) {
 775             uc = (UChar)(s->tt[i] & 0xff);
 776             s->tt[s->cftab[uc]] |= (i << 8);
 777             s->cftab[uc]++;
 778          }
 779
 780          s->tPos = s->tt[s->origPtr] >> 8;
 781          s->nblock_used = 0;
 782          if (s->blockRandomised) {
 783             BZ_RAND_INIT_MASK;
 784             BZ_GET_FAST(s->k0); s->nblock_used++;
 785             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
 786          } else {
 787             BZ_GET_FAST(s->k0); s->nblock_used++;
 788          }
 789
 790       }
 791
 792       RETURN(BZ_OK);
 793
 794
 795
 796     endhdr_2:
 797
 798       GET_UCHAR(BZ_X_ENDHDR_2, uc);
 799       if (uc != 0x72) RETURN(BZ_DATA_ERROR);
 800       GET_UCHAR(BZ_X_ENDHDR_3, uc);
 801       if (uc != 0x45) RETURN(BZ_DATA_ERROR);
 802       GET_UCHAR(BZ_X_ENDHDR_4, uc);
 803       if (uc != 0x38) RETURN(BZ_DATA_ERROR);
 804       GET_UCHAR(BZ_X_ENDHDR_5, uc);
 805       if (uc != 0x50) RETURN(BZ_DATA_ERROR);
 806       GET_UCHAR(BZ_X_ENDHDR_6, uc);
 807       if (uc != 0x90) RETURN(BZ_DATA_ERROR);
 808
 809       s->storedCombinedCRC = 0;
 810       GET_UCHAR(BZ_X_CCRC_1, uc);
 811       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
 812       GET_UCHAR(BZ_X_CCRC_2, uc);
 813       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
 814       GET_UCHAR(BZ_X_CCRC_3, uc);
 815       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
 816       GET_UCHAR(BZ_X_CCRC_4, uc);
 817       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
 818
 819       s->state = BZ_X_IDLE;
 820       RETURN(BZ_STREAM_END);
 821
 822       default: AssertH ( False, 4001 );
 823    }
 824
 825    AssertH ( False, 4002 );
 826
 827    save_state_and_return:
 828
 829    s->save_i           = i;
 830    s->save_j           = j;
 831    s->save_t           = t;
 832    s->save_alphaSize   = alphaSize;
 833    s->save_nGroups     = nGroups;
 834    s->save_nSelectors  = nSelectors;
 835    s->save_EOB         = EOB;
 836    s->save_groupNo     = groupNo;
 837    s->save_groupPos    = groupPos;
 838    s->save_nextSym     = nextSym;
 839    s->save_nblockMAX   = nblockMAX;
 840    s->save_nblock      = nblock;
 841    s->save_es          = es;
 842    s->save_N           = N;
 843    s->save_curr        = curr;
 844    s->save_zt          = zt;
 845    s->save_zn          = zn;
 846    s->save_zvec        = zvec;
 847    s->save_zj          = zj;
 848    s->save_gSel        = gSel;
 849    s->save_gMinlen     = gMinlen;
 850    s->save_gLimit      = gLimit;
 851    s->save_gBase       = gBase;
 852    s->save_gPerm       = gPerm;
 853
 854    return retVal;
 855 }
 856
 857
 858 /*-------------------------------------------------------------*/
 859 /*--- end                                      decompress.c ---*/
 860 /*-------------------------------------------------------------*/