archival/libunarchive/decompress_bunzip2.c

   1 /*--
   2   This file is a part of bzip2 and/or libbzip2, a program and
   3   library for lossless, block-sorting data compression.
   4
   5   Copyright (C) 1996-2000 Julian R Seward.  All rights reserved.
   6
   7   Redistribution and use in source and binary forms, with or without
   8   modification, are permitted provided that the following conditions
   9   are met:
  10
  11   1. Redistributions of source code must retain the above copyright
  12      notice, this list of conditions and the following disclaimer.
  13
  14   2. The origin of this software must not be misrepresented; you must
  15      not claim that you wrote the original software.  If you use this
  16      software in a product, an acknowledgment in the product
  17      documentation would be appreciated but is not required.
  18
  19   3. Altered source versions must be plainly marked as such, and must
  20      not be misrepresented as being the original software.
  21
  22   4. The name of the author may not be used to endorse or promote
  23      products derived from this software without specific prior written
  24      permission.
  25
  26   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  27   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  28   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  30   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  32   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  33   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  34   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  35   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  36   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37
  38   Julian Seward, Cambridge, UK.
  39   jseward@acm.org
  40   bzip2/libbzip2 version 1.0 of 21 March 2000
  41
  42   This program is based on (at least) the work of:
  43      Mike Burrows
  44      David Wheeler
  45      Peter Fenwick
  46      Alistair Moffat
  47      Radford Neal
  48      Ian H. Witten
  49      Robert Sedgewick
  50      Jon L. Bentley
  51
  52   For more information on these sources, see the manual.
  53 --*/
  54
  55 #include <stdlib.h>
  56 #include <stdio.h>
  57 #include <string.h>
  58 #include <getopt.h>
  59 #include <unistd.h>
  60
  61 #include "busybox.h"
  62
  63 #define MTFA_SIZE 4096
  64 #define MTFL_SIZE 16
  65 #define BZ_N_GROUPS 6
  66 #define BZ_G_SIZE   50
  67 #define BZ_MAX_ALPHA_SIZE 258
  68
  69 #define BZ_OK                0
  70 #define BZ_STREAM_END        4
  71 #define BZ_SEQUENCE_ERROR    (-1)
  72 #define BZ_DATA_ERROR        (-4)
  73 #define BZ_DATA_ERROR_MAGIC  (-5)
  74 #define BZ_IO_ERROR          (-6)
  75 #define BZ_UNEXPECTED_EOF    (-7)
  76
  77 #define BZ_RUNA 0
  78 #define BZ_RUNB 1
  79
  80 #define BZ_MAX_UNUSED 5000
  81 #define FILE_NAME_LEN 1034
  82 /*-- states for decompression. --*/
  83
  84 #define BZ_X_IDLE        1
  85 #define BZ_X_OUTPUT      2
  86
  87 #define BZ_X_MAGIC_1     10
  88 #define BZ_X_MAGIC_2     11
  89 #define BZ_X_MAGIC_3     12
  90 #define BZ_X_MAGIC_4     13
  91 #define BZ_X_BLKHDR_1    14
  92 #define BZ_X_BLKHDR_2    15
  93 #define BZ_X_BLKHDR_3    16
  94 #define BZ_X_BLKHDR_4    17
  95 #define BZ_X_BLKHDR_5    18
  96 #define BZ_X_BLKHDR_6    19
  97 #define BZ_X_BCRC_1      20
  98 #define BZ_X_BCRC_2      21
  99 #define BZ_X_BCRC_3      22
 100 #define BZ_X_BCRC_4      23
 101 #define BZ_X_RANDBIT     24
 102 #define BZ_X_ORIGPTR_1   25
 103 #define BZ_X_ORIGPTR_2   26
 104 #define BZ_X_ORIGPTR_3   27
 105 #define BZ_X_MAPPING_1   28
 106 #define BZ_X_MAPPING_2   29
 107 #define BZ_X_SELECTOR_1  30
 108 #define BZ_X_SELECTOR_2  31
 109 #define BZ_X_SELECTOR_3  32
 110 #define BZ_X_CODING_1    33
 111 #define BZ_X_CODING_2    34
 112 #define BZ_X_CODING_3    35
 113 #define BZ_X_MTF_1       36
 114 #define BZ_X_MTF_2       37
 115 #define BZ_X_MTF_3       38
 116 #define BZ_X_MTF_4       39
 117 #define BZ_X_MTF_5       40
 118 #define BZ_X_MTF_6       41
 119 #define BZ_X_ENDHDR_2    42
 120 #define BZ_X_ENDHDR_3    43
 121 #define BZ_X_ENDHDR_4    44
 122 #define BZ_X_ENDHDR_5    45
 123 #define BZ_X_ENDHDR_6    46
 124 #define BZ_X_CCRC_1      47
 125 #define BZ_X_CCRC_2      48
 126 #define BZ_X_CCRC_3      49
 127 #define BZ_X_CCRC_4      50
 128
 129 #define BZ_MAX_CODE_LEN    23
 130 #define OM_TEST          3
 131
 132 typedef struct {
 133         char *next_in;
 134         unsigned int avail_in;
 135
 136         char *next_out;
 137         unsigned int avail_out;
 138
 139         void *state;
 140
 141 } bz_stream;
 142
 143 #define BZ_MAX_UNUSED 5000
 144 typedef struct {
 145         bz_stream       strm;
 146         int                     fd;
 147     unsigned char       initialisedOk;
 148         char    buf[BZ_MAX_UNUSED];
 149         int             lastErr;
 150         int             bufN;
 151 } bzFile;
 152
 153 /*-- Structure holding all the decompression-side stuff. --*/
 154 typedef struct {
 155         /* pointer back to the struct bz_stream */
 156         bz_stream* strm;
 157
 158         /* state indicator for this stream */
 159         int     state;
 160
 161         /* for doing the final run-length decoding */
 162         unsigned char    state_out_ch;
 163         int    state_out_len;
 164         unsigned char     blockRandomised;
 165         int rNToGo;
 166         int rTPos;
 167
 168         /* the buffer for bit stream reading */
 169         unsigned int   bsBuff;
 170         int    bsLive;
 171
 172         /* misc administratium */
 173         int    blockSize100k;
 174         int    currBlockNo;
 175
 176         /* for undoing the Burrows-Wheeler transform */
 177         int    origPtr;
 178         unsigned int   tPos;
 179         int    k0;
 180         int    unzftab[256];
 181         int    nblock_used;
 182         int    cftab[257];
 183         int    cftabCopy[257];
 184
 185         /* for undoing the Burrows-Wheeler transform (FAST) */
 186         unsigned int *tt;
 187
 188         /* stored and calculated CRCs */
 189         unsigned int   storedBlockCRC;
 190         unsigned int   storedCombinedCRC;
 191         unsigned int   calculatedBlockCRC;
 192         unsigned int   calculatedCombinedCRC;
 193
 194         /* map of bytes used in block */
 195         int    nInUse;
 196         unsigned char     inUse[256];
 197         unsigned char     inUse16[16];
 198         unsigned char    seqToUnseq[256];
 199
 200         /* for decoding the MTF values */
 201         unsigned char    mtfa   [MTFA_SIZE];
 202         unsigned char    selector   [2 + (900000 / BZ_G_SIZE)];
 203         unsigned char    selectorMtf[2 + (900000 / BZ_G_SIZE)];
 204         unsigned char    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 205         int    mtfbase[256 / MTFL_SIZE];
 206
 207         int    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 208         int    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 209         int    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 210         int    minLens[BZ_N_GROUPS];
 211
 212         /* save area for scalars in the main decompress code */
 213         int    save_i;
 214         int    save_j;
 215         int    save_t;
 216         int    save_alphaSize;
 217         int    save_nGroups;
 218         int    save_nSelectors;
 219         int    save_EOB;
 220         int    save_groupNo;
 221         int    save_groupPos;
 222         int    save_nextSym;
 223         int    save_nblockMAX;
 224         int    save_nblock;
 225         int    save_es;
 226         int    save_N;
 227         int    save_curr;
 228         int    save_zt;
 229         int    save_zn;
 230         int    save_zvec;
 231         int    save_zj;
 232         int    save_gSel;
 233         int    save_gMinlen;
 234         int     *save_gLimit;
 235         int     *save_gBase;
 236         int     *save_gPerm;
 237 } DState;
 238
 239 static int BZ2_rNums[512];
 240 static bzFile *bzf;
 241 static int bzerr = BZ_OK;
 242
 243 static const unsigned int BZ2_crc32Table[256] = {
 244
 245    /*-- Ugly, innit? --*/
 246
 247    0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
 248    0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
 249    0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
 250    0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
 251    0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
 252    0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
 253    0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
 254    0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
 255    0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
 256    0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
 257    0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
 258    0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
 259    0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
 260    0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
 261    0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
 262    0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
 263    0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
 264    0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
 265    0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
 266    0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
 267    0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
 268    0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
 269    0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
 270    0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
 271    0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
 272    0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
 273    0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
 274    0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
 275    0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
 276    0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
 277    0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
 278    0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
 279    0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
 280    0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
 281    0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
 282    0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
 283    0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
 284    0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
 285    0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
 286    0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
 287    0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
 288    0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
 289    0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
 290    0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
 291    0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
 292    0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
 293    0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
 294    0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
 295    0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
 296    0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
 297    0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
 298    0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
 299    0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
 300    0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
 301    0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
 302    0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
 303    0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
 304    0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
 305    0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
 306    0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
 307    0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
 308    0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
 309    0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
 310    0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
 311 };
 312
 313 static void bz_rand_udp_mask(DState *s)
 314 {
 315         if (s->rNToGo == 0) {
 316                 s->rNToGo = BZ2_rNums[s->rTPos];
 317                 s->rTPos++;
 318                 if (s->rTPos == 512) {
 319                         s->rTPos = 0;
 320                 }
 321         }
 322         s->rNToGo--;
 323 }
 324
 325 static void BZ2_hbCreateDecodeTables(int *limit, int *base, int *perm, unsigned char *length, int minLen, int maxLen, int alphaSize )
 326 {
 327         int pp, i, j, vec;
 328
 329         pp = 0;
 330         for (i = minLen; i <= maxLen; i++) {
 331                 for (j = 0; j < alphaSize; j++) {
 332                         if (length[j] == i) {
 333                                 perm[pp] = j;
 334                                 pp++;
 335                         }
 336                 }
 337         }
 338
 339         for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
 340                 base[i] = 0;
 341         }
 342
 343         for (i = 0; i < alphaSize; i++) {
 344                 base[length[i]+1]++;
 345         }
 346
 347         for (i = 1; i < BZ_MAX_CODE_LEN; i++) {
 348                 base[i] += base[i-1];
 349         }
 350
 351         for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
 352                 limit[i] = 0;
 353         }
 354         vec = 0;
 355
 356         for (i = minLen; i <= maxLen; i++) {
 357                 vec += (base[i+1] - base[i]);
 358                 limit[i] = vec-1;
 359                 vec <<= 1;
 360         }
 361         for (i = minLen + 1; i <= maxLen; i++) {
 362                 base[i] = ((limit[i-1] + 1) << 1) - base[i];
 363         }
 364 }
 365
 366
 367 static int get_bits(DState *s, int *vvv, char nnn)
 368 {
 369         while (1) {
 370                 if (s->bsLive >= nnn) {
 371                         *vvv = (s->bsBuff >> (s->bsLive-nnn)) & ((1 << nnn)-1);
 372                         s->bsLive -= nnn;
 373                         break;
 374                 }
 375                 if (s->strm->avail_in == 0) {
 376                         return(FALSE);
 377                 }
 378                 s->bsBuff = (s->bsBuff << 8) | ((unsigned int) (*((unsigned char*)(s->strm->next_in))));
 379                 s->bsLive += 8;
 380                 s->strm->next_in++;
 381                 s->strm->avail_in--;
 382         }
 383         return(TRUE);
 384 }
 385
 386 static int bz_get_fast(DState *s)
 387 {
 388         int cccc;
 389         s->tPos = s->tt[s->tPos];
 390         cccc = (unsigned char)(s->tPos & 0xff);
 391         s->tPos >>= 8;
 392         return(cccc);
 393 }
 394
 395 /*---------------------------------------------------*/
 396 static inline int BZ2_decompress(DState *s)
 397 {
 398         int uc = 0;
 399         int     retVal;
 400         int     minLen, maxLen;
 401
 402         /* stuff that needs to be saved/restored */
 403         int  i;
 404         int  j;
 405         int  t;
 406         int  alphaSize;
 407         int  nGroups;
 408         int  nSelectors;
 409         int  EOB;
 410         int  groupNo;
 411         int  groupPos;
 412         int  nextSym;
 413         int  nblockMAX;
 414         int  nblock;
 415         int  es;
 416         int  N;
 417         int  curr;
 418         int  zt;
 419         int  zn;
 420         int  zvec;
 421         int  zj;
 422         int  gSel;
 423         int  gMinlen;
 424         int *gLimit;
 425         int *gBase;
 426         int *gPerm;
 427         int switch_val;
 428
 429         int get_mtf_val_init(void)
 430         {
 431                 if (groupPos == 0) {
 432                         groupNo++;
 433                         if (groupNo >= nSelectors) {
 434                                 retVal = BZ_DATA_ERROR;
 435                                 return(FALSE);
 436                         }
 437                         groupPos = BZ_G_SIZE;
 438                         gSel = s->selector[groupNo];
 439                         gMinlen = s->minLens[gSel];
 440                         gLimit = &(s->limit[gSel][0]);
 441                         gPerm = &(s->perm[gSel][0]);
 442                         gBase = &(s->base[gSel][0]);
 443                 }
 444                 groupPos--;
 445                 zn = gMinlen;
 446                 return(TRUE);
 447         }
 448
 449         if (s->state == BZ_X_MAGIC_1) {
 450                 /*initialise the save area*/
 451                 s->save_i           = 0;
 452                 s->save_j           = 0;
 453                 s->save_t           = 0;
 454                 s->save_alphaSize   = 0;
 455                 s->save_nGroups     = 0;
 456                 s->save_nSelectors  = 0;
 457                 s->save_EOB         = 0;
 458                 s->save_groupNo     = 0;
 459                 s->save_groupPos    = 0;
 460                 s->save_nextSym     = 0;
 461                 s->save_nblockMAX   = 0;
 462                 s->save_nblock      = 0;
 463                 s->save_es          = 0;
 464                 s->save_N           = 0;
 465                 s->save_curr        = 0;
 466                 s->save_zt          = 0;
 467                 s->save_zn          = 0;
 468                 s->save_zvec        = 0;
 469                 s->save_zj          = 0;
 470                 s->save_gSel        = 0;
 471                 s->save_gMinlen     = 0;
 472                 s->save_gLimit      = NULL;
 473                 s->save_gBase       = NULL;
 474                 s->save_gPerm       = NULL;
 475         }
 476
 477         /*restore from the save area*/
 478         i           = s->save_i;
 479         j           = s->save_j;
 480         t           = s->save_t;
 481         alphaSize   = s->save_alphaSize;
 482         nGroups     = s->save_nGroups;
 483         nSelectors  = s->save_nSelectors;
 484         EOB         = s->save_EOB;
 485         groupNo     = s->save_groupNo;
 486         groupPos    = s->save_groupPos;
 487         nextSym     = s->save_nextSym;
 488         nblockMAX   = s->save_nblockMAX;
 489         nblock      = s->save_nblock;
 490         es          = s->save_es;
 491         N           = s->save_N;
 492         curr        = s->save_curr;
 493         zt          = s->save_zt;
 494         zn          = s->save_zn;
 495         zvec        = s->save_zvec;
 496         zj          = s->save_zj;
 497         gSel        = s->save_gSel;
 498         gMinlen     = s->save_gMinlen;
 499         gLimit      = s->save_gLimit;
 500         gBase       = s->save_gBase;
 501         gPerm       = s->save_gPerm;
 502
 503         retVal = BZ_OK;
 504         switch_val = s->state;
 505         switch (switch_val) {
 506                 case BZ_X_MAGIC_1:
 507                         s->state = BZ_X_MAGIC_1;
 508                         if (! get_bits(s, &uc, 8)) {
 509                                 retVal = BZ_OK;
 510                                 goto save_state_and_return;
 511                         }
 512                         if (uc != 'B') {
 513                                 retVal = BZ_DATA_ERROR_MAGIC;
 514                                 goto save_state_and_return;
 515                         }
 516
 517                 case BZ_X_MAGIC_2:
 518                         s->state = BZ_X_MAGIC_2;
 519                         if (! get_bits(s, &uc, 8)) {
 520                                 retVal = BZ_OK;
 521                                 goto save_state_and_return;
 522                         }
 523                         if (uc != 'Z') {
 524                                 retVal = BZ_DATA_ERROR_MAGIC;
 525                                 goto save_state_and_return;
 526                         }
 527
 528                 case BZ_X_MAGIC_3:
 529                         s->state = BZ_X_MAGIC_3;
 530                         if (! get_bits(s, &uc, 8)) {
 531                                 retVal = BZ_OK;
 532                                 goto save_state_and_return;
 533                         }
 534                         if (uc != 'h') {
 535                                 retVal = BZ_DATA_ERROR_MAGIC;
 536                                 goto save_state_and_return;
 537                         }
 538
 539                 case BZ_X_MAGIC_4:
 540                         s->state = BZ_X_MAGIC_4;
 541                         if (! get_bits(s, &s->blockSize100k, 8)) {
 542                                 retVal = BZ_OK;
 543                                 goto save_state_and_return;
 544                         }
 545                         if ((s->blockSize100k < '1') || (s->blockSize100k > '9')) {
 546                                 retVal = BZ_DATA_ERROR_MAGIC;
 547                                 goto save_state_and_return;
 548                         }
 549                         s->blockSize100k -= '0';
 550
 551                         s->tt = xmalloc(s->blockSize100k * 100000 * sizeof(int));
 552
 553                 case BZ_X_BLKHDR_1:
 554                         s->state = BZ_X_BLKHDR_1;
 555                         if (! get_bits(s, &uc, 8)) {
 556                                 retVal = BZ_OK;
 557                                 goto save_state_and_return;
 558                         }
 559
 560                         if (uc == 0x17) {
 561                                 goto endhdr_2;
 562                         }
 563                         if (uc != 0x31) {
 564                                 retVal = BZ_DATA_ERROR;
 565                                 goto save_state_and_return;
 566                         }
 567
 568                 case BZ_X_BLKHDR_2:
 569                         s->state = BZ_X_BLKHDR_2;
 570                         if (! get_bits(s, &uc, 8)) {
 571                                 retVal = BZ_OK;
 572                                 goto save_state_and_return;
 573                         }
 574                         if (uc != 0x41) {
 575                                 retVal = BZ_DATA_ERROR;
 576                                 goto save_state_and_return;
 577                         }
 578
 579                 case BZ_X_BLKHDR_3:
 580                         s->state = BZ_X_BLKHDR_3;
 581                         if (! get_bits(s, &uc, 8)) {
 582                                 retVal = BZ_OK;
 583                                 goto save_state_and_return;
 584                         }
 585                         if (uc != 0x59) {
 586                                 retVal = BZ_DATA_ERROR;
 587                                 goto save_state_and_return;
 588                         }
 589
 590                 case BZ_X_BLKHDR_4:
 591                         s->state = BZ_X_BLKHDR_4;
 592                         if (! get_bits(s, &uc, 8)) {
 593                                 retVal = BZ_OK;
 594                                 goto save_state_and_return;
 595                         }
 596                         if (uc != 0x26) {
 597                                 retVal = BZ_DATA_ERROR;
 598                                 goto save_state_and_return;
 599                         }
 600
 601                 case BZ_X_BLKHDR_5:
 602                         s->state = BZ_X_BLKHDR_5;
 603                         if (! get_bits(s, &uc, 8)) {
 604                                 retVal = BZ_OK;
 605                                 goto save_state_and_return;
 606                         }
 607                         if (uc != 0x53) {
 608                                 retVal = BZ_DATA_ERROR;
 609                                 goto save_state_and_return;
 610                         }
 611
 612                 case BZ_X_BLKHDR_6:
 613                         s->state = BZ_X_BLKHDR_6;
 614                         if (! get_bits(s, &uc, 8)) {
 615                                 retVal = BZ_OK;
 616                                 goto save_state_and_return;
 617                         }
 618                         if (uc != 0x59) {
 619                                 retVal = BZ_DATA_ERROR;
 620                                 goto save_state_and_return;
 621                         }
 622
 623                 s->currBlockNo++;
 624                 s->storedBlockCRC = 0;
 625
 626                 case BZ_X_BCRC_1:
 627                         s->state = BZ_X_BCRC_1;
 628                         if (! get_bits(s, &uc, 8)) {
 629                                 retVal = BZ_OK;
 630                                 goto save_state_and_return;
 631                         }
 632                         s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
 633
 634                 case BZ_X_BCRC_2:
 635                         s->state = BZ_X_BCRC_2;
 636                         if (! get_bits(s, &uc, 8)) {
 637                                 retVal = BZ_OK;
 638                                 goto save_state_and_return;
 639                         }
 640                         s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
 641
 642                 case BZ_X_BCRC_3:
 643                         s->state = BZ_X_BCRC_3;
 644                         if (! get_bits(s, &uc, 8)) {
 645                                 retVal = BZ_OK;
 646                                 goto save_state_and_return;
 647                         }
 648                         s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
 649
 650                 case BZ_X_BCRC_4:
 651                         s->state = BZ_X_BCRC_4;
 652                         if (! get_bits(s, &uc, 8)) {
 653                                 retVal = BZ_OK;
 654                                 goto save_state_and_return;
 655                         }
 656                         s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
 657
 658                 case BZ_X_RANDBIT:
 659                         s->state = BZ_X_RANDBIT;
 660                         {
 661                                 int tmp = s->blockRandomised;
 662                                 const int ret = get_bits(s, &tmp, 1);
 663                                 s->blockRandomised = tmp;
 664                                 if (! ret) {
 665                                         retVal = BZ_OK;
 666                                         goto save_state_and_return;
 667                                 }
 668                         }
 669
 670                         s->origPtr = 0;
 671
 672                 case BZ_X_ORIGPTR_1:
 673                         s->state = BZ_X_ORIGPTR_1;
 674                         if (! get_bits(s, &uc, 8)) {
 675                                 retVal = BZ_OK;
 676                                 goto save_state_and_return;
 677                         }
 678                         s->origPtr = (s->origPtr << 8) | ((int)uc);
 679
 680                 case BZ_X_ORIGPTR_2:
 681                         s->state = BZ_X_ORIGPTR_2;
 682                         if (! get_bits(s, &uc, 8)) {
 683                                 retVal = BZ_OK;
 684                                 goto save_state_and_return;
 685                         }
 686                         s->origPtr = (s->origPtr << 8) | ((int)uc);
 687
 688                 case BZ_X_ORIGPTR_3:
 689                         s->state = BZ_X_ORIGPTR_3;
 690                         if (! get_bits(s, &uc, 8)) {
 691                                 retVal = BZ_OK;
 692                                 goto save_state_and_return;
 693                         }
 694                         s->origPtr = (s->origPtr << 8) | ((int)uc);
 695
 696                         if (s->origPtr < 0) {
 697                                 retVal = BZ_DATA_ERROR;
 698                                 goto save_state_and_return;
 699                         }
 700                         if (s->origPtr > 10 + 100000*s->blockSize100k) {
 701                                 retVal = BZ_DATA_ERROR;
 702                                 goto save_state_and_return;
 703                         }
 704
 705                         /*--- Receive the mapping table ---*/
 706                 case BZ_X_MAPPING_1:
 707                         for (i = 0; i < 16; i++) {
 708                                 s->state = BZ_X_MAPPING_1;
 709                                 if (! get_bits(s, &uc, 1)) {
 710                                         retVal = BZ_OK;
 711                                         goto save_state_and_return;
 712                                 }
 713                                 if (uc == 1) {
 714                                         s->inUse16[i] = TRUE;
 715                                 } else {
 716                                         s->inUse16[i] = FALSE;
 717                                 }
 718                         }
 719
 720                         for (i = 0; i < 256; i++) {
 721                                 s->inUse[i] = FALSE;
 722                         }
 723
 724                         for (i = 0; i < 16; i++) {
 725                                 if (s->inUse16[i]) {
 726                                         for (j = 0; j < 16; j++) {
 727                                         case BZ_X_MAPPING_2:
 728                                                 s->state = BZ_X_MAPPING_2;
 729                                                 if (! get_bits(s, &uc, 1)) {
 730                                                         retVal = BZ_OK;
 731                                                         goto save_state_and_return;
 732                                                 }
 733                                                 if (uc == 1) {
 734                                                         s->inUse[i * 16 + j] = TRUE;
 735                                                 }
 736                                         }
 737                                 }
 738                         }
 739
 740                         s->nInUse = 0;
 741                         for (i = 0; i < 256; i++) {
 742                                 if (s->inUse[i]) {
 743                                         s->seqToUnseq[s->nInUse] = i;
 744                                         s->nInUse++;
 745                                 }
 746                         }
 747                         if (s->nInUse == 0) {
 748                                 retVal = BZ_DATA_ERROR;
 749                                 goto save_state_and_return;
 750                         }
 751                         alphaSize = s->nInUse+2;
 752
 753                 /*--- Now the selectors ---*/
 754                 case BZ_X_SELECTOR_1:
 755                         s->state = BZ_X_SELECTOR_1;
 756                         if (! get_bits(s, &nGroups, 3)) {
 757                                 retVal = BZ_OK;
 758                                 goto save_state_and_return;
 759                         }
 760                         if (nGroups < 2 || nGroups > 6) {
 761                                 retVal = BZ_DATA_ERROR;
 762                                 goto save_state_and_return;
 763                         }
 764
 765                 case BZ_X_SELECTOR_2:
 766                         s->state = BZ_X_SELECTOR_2;
 767                         if (! get_bits(s, &nSelectors, 15)) {
 768                                 retVal = BZ_OK;
 769                                 goto save_state_and_return;
 770                         }
 771                         if (nSelectors < 1) {
 772                                 retVal = BZ_DATA_ERROR;
 773                                 goto save_state_and_return;
 774                         }
 775
 776
 777
 778                         for (i = 0; i < nSelectors; i++) {
 779                                 j = 0;
 780                                 while (1) {
 781                                         case BZ_X_SELECTOR_3:
 782                                         s->state = BZ_X_SELECTOR_3;
 783                                         if (! get_bits(s, &uc, 1)) {
 784                                                 retVal = BZ_OK;
 785                                                 goto save_state_and_return;
 786                                         }
 787                                         if (uc == 0) {
 788                                                 break;
 789                                         }
 790                                         j++;
 791                                         if (j >= nGroups) {
 792                                                 retVal = BZ_DATA_ERROR;
 793                                                 goto save_state_and_return;
 794                                         }
 795                                 }
 796                                 s->selectorMtf[i] = j;
 797                         }
 798
 799                         /*--- Undo the MTF values for the selectors. ---*/
 800                         {
 801                                 unsigned char pos[BZ_N_GROUPS], tmp, v;
 802                                 for (v = 0; v < nGroups; v++) {
 803                                         pos[v] = v;
 804                                 }
 805                                 for (i = 0; i < nSelectors; i++) {
 806                                         v = s->selectorMtf[i];
 807                                         tmp = pos[v];
 808                                         while (v > 0) {
 809                                                 pos[v] = pos[v-1];
 810                                                 v--;
 811                                         }
 812                                         pos[0] = tmp;
 813                                         s->selector[i] = tmp;
 814                                 }
 815                         }
 816
 817                         /*--- Now the coding tables ---*/
 818                         for (t = 0; t < nGroups; t++) {
 819                         case BZ_X_CODING_1:
 820                                 s->state = BZ_X_CODING_1;
 821                                 if (! get_bits(s, &curr, 5)) {
 822                                         retVal = BZ_OK;
 823                                         goto save_state_and_return;
 824                                 }
 825                         for (i = 0; i < alphaSize; i++) {
 826                                 while (TRUE) {
 827                                         if (curr < 1 || curr > 20) {
 828                                                 retVal = BZ_DATA_ERROR;
 829                                                 goto save_state_and_return;
 830                                         }
 831
 832                                         case BZ_X_CODING_2:
 833                                                 s->state = BZ_X_CODING_2;
 834                                                 if (! get_bits(s, &uc, 1)) {
 835                                                         retVal = BZ_OK;
 836                                                         goto save_state_and_return;
 837                                                 }
 838                                                 if (uc == 0) {
 839                                                         break;
 840                                                 }
 841
 842                                         case BZ_X_CODING_3:
 843                                                 s->state = BZ_X_CODING_3;
 844                                                 if (! get_bits(s, &uc, 1)) {
 845                                                         retVal = BZ_OK;
 846                                                         goto save_state_and_return;
 847                                                 }
 848                                                 if (uc == 0) {
 849                                                         curr++;
 850                                                 } else {
 851                                                         curr--;
 852                                                 }
 853                                 }
 854                                 s->len[t][i] = curr;
 855                         }
 856                 }
 857
 858                 /*--- Create the Huffman decoding tables ---*/
 859                 for (t = 0; t < nGroups; t++) {
 860                         minLen = 32;
 861                         maxLen = 0;
 862                         for (i = 0; i < alphaSize; i++) {
 863                                 if (s->len[t][i] > maxLen) {
 864                                         maxLen = s->len[t][i];
 865                                 }
 866                                 if (s->len[t][i] < minLen) {
 867                                         minLen = s->len[t][i];
 868                                 }
 869                         }
 870
 871                         BZ2_hbCreateDecodeTables (
 872                                 &(s->limit[t][0]),
 873                                 &(s->base[t][0]),
 874                                 &(s->perm[t][0]),
 875                                 &(s->len[t][0]),
 876                                 minLen, maxLen, alphaSize
 877                                 );
 878
 879
 880                         s->minLens[t] = minLen;
 881                 }
 882
 883                 /*--- Now the MTF values ---*/
 884
 885                 EOB      = s->nInUse+1;
 886                 nblockMAX = 100000 * s->blockSize100k;
 887                 groupNo  = -1;
 888                 groupPos = 0;
 889
 890                 for (i = 0; i <= 255; i++) {
 891                         s->unzftab[i] = 0;
 892                 }
 893                 /*-- MTF init --*/
 894                 {
 895                         int ii, jj, kk;
 896                         kk = MTFA_SIZE-1;
 897                         for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
 898                                 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
 899                                         s->mtfa[kk] = (unsigned char)(ii * MTFL_SIZE + jj);
 900                                         kk--;
 901                                 }
 902                                 s->mtfbase[ii] = kk + 1;
 903                         }
 904                 }
 905                 /*-- end MTF init --*/
 906
 907                 nblock = 0;
 908
 909                 if (! get_mtf_val_init()) {
 910                         goto save_state_and_return;
 911                 }
 912                 case BZ_X_MTF_1:
 913                         s->state = BZ_X_MTF_1;
 914                         if (! get_bits(s, &zvec, zn)) {
 915                                 retVal = BZ_OK;
 916                                 goto save_state_and_return;
 917                         }
 918                         while (1) {
 919                                 if (zn > 20 /* the longest code */) {
 920                                         retVal = BZ_DATA_ERROR;
 921                                         goto save_state_and_return;
 922                                 }
 923                                 if (zvec <= gLimit[zn]) {
 924                                         break;
 925                                 }
 926                                 zn++;
 927
 928                                 case BZ_X_MTF_2:
 929                                         s->state = BZ_X_MTF_2;
 930                                         if (! get_bits(s, &zj, 1)) {
 931                                                 retVal = BZ_OK;
 932                                                 goto save_state_and_return;
 933                                         }
 934                                         zvec = (zvec << 1) | zj;
 935                         }
 936                         if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
 937                                 retVal = BZ_DATA_ERROR;
 938                                 goto save_state_and_return;
 939                         }
 940                         nextSym = gPerm[zvec - gBase[zn]];
 941
 942                 while (1) {
 943                         if (nextSym == EOB) {
 944                                 break;
 945                         }
 946
 947                 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
 948                         es = -1;
 949                         N = 1;
 950                         do {
 951                                 if (nextSym == BZ_RUNA) {
 952                                         es = es + (0+1) * N;
 953                                 } else {
 954                                         if (nextSym == BZ_RUNB) {
 955                                                 es = es + (1+1) * N;
 956                                         }
 957                                 }
 958                                 N = N * 2;
 959                                 if (! get_mtf_val_init()) {
 960                                         goto save_state_and_return;
 961                                 }
 962                                 case BZ_X_MTF_3:
 963                                         s->state = BZ_X_MTF_3;
 964                                         if (! get_bits(s, &zvec, zn)) {
 965                                                 retVal = BZ_OK;
 966                                                 goto save_state_and_return;
 967                                         }
 968                                         while (1) {
 969                                                 if (zn > 20 /* the longest code */) {
 970                                                         retVal = BZ_DATA_ERROR;
 971                                                         goto save_state_and_return;
 972                                                 }
 973                                                 if (zvec <= gLimit[zn]) {
 974                                                         break;
 975                                                 }
 976                                                 zn++;
 977
 978                                                 case BZ_X_MTF_4:
 979                                                         s->state = BZ_X_MTF_4;
 980                                                         if (! get_bits(s, &zj, 1)) {
 981                                                                 retVal = BZ_OK;
 982                                                                 goto save_state_and_return;
 983                                                         }
 984                                                         zvec = (zvec << 1) | zj;
 985                                         }
 986                                         if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
 987                                                 retVal = BZ_DATA_ERROR;
 988                                                 goto save_state_and_return;
 989
 990                                         }
 991                                         nextSym = gPerm[zvec - gBase[zn]];
 992                         }
 993                         while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
 994
 995                         es++;
 996                         uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
 997                         s->unzftab[uc] += es;
 998
 999                         while (es > 0) {
1000                                 if (nblock >= nblockMAX) {
1001                                         retVal = BZ_DATA_ERROR;
1002                                         goto save_state_and_return;
1003                                 }
1004                                 s->tt[nblock] = (unsigned int)uc;
1005                                 nblock++;
1006                                 es--;
1007                         }
1008                         continue;
1009                 } else {
1010                         if (nblock >= nblockMAX) {
1011                                 retVal = BZ_DATA_ERROR;
1012                                 goto save_state_and_return;
1013                         }
1014                         /*-- uc = MTF ( nextSym-1 ) --*/
1015                         {
1016                                 int ii, jj, kk, pp, lno, off;
1017                                 unsigned int nn;
1018                                 nn = (unsigned int)(nextSym - 1);
1019
1020                                 if (nn < MTFL_SIZE) {
1021                                         /* avoid general-case expense */
1022                                         pp = s->mtfbase[0];
1023                                         uc = s->mtfa[pp+nn];
1024                                         while (nn > 3) {
1025                                                 int z = pp+nn;
1026                                                 s->mtfa[(z)  ] = s->mtfa[(z)-1];
1027                                                 s->mtfa[(z)-1] = s->mtfa[(z)-2];
1028                                                 s->mtfa[(z)-2] = s->mtfa[(z)-3];
1029                                                 s->mtfa[(z)-3] = s->mtfa[(z)-4];
1030                                                 nn -= 4;
1031                                         }
1032                                         while (nn > 0) {
1033                                                 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1034                                         }
1035                                         s->mtfa[pp] = uc;
1036                                 } else {
1037                                         /* general case */
1038                                         lno = nn / MTFL_SIZE;
1039                                         off = nn % MTFL_SIZE;
1040                                         pp = s->mtfbase[lno] + off;
1041                                         uc = s->mtfa[pp];
1042                                         while (pp > s->mtfbase[lno]) {
1043                                                 s->mtfa[pp] = s->mtfa[pp-1];
1044                                                 pp--;
1045                                         }
1046                                         s->mtfbase[lno]++;
1047                                         while (lno > 0) {
1048                                                 s->mtfbase[lno]--;
1049                                                 s->mtfa[s->mtfbase[lno]] = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1050                                                 lno--;
1051                                         }
1052                                         s->mtfbase[0]--;
1053                                         s->mtfa[s->mtfbase[0]] = uc;
1054                                         if (s->mtfbase[0] == 0) {
1055                                                 kk = MTFA_SIZE-1;
1056                                                 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1057                                                         for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1058                                                                 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1059                                                                 kk--;
1060                                                         }
1061                                                         s->mtfbase[ii] = kk + 1;
1062                                                 }
1063                                         }
1064                                 }
1065                         }
1066                         /*-- end uc = MTF ( nextSym-1 ) --*/
1067
1068                         s->unzftab[s->seqToUnseq[uc]]++;
1069                         s->tt[nblock]   = (unsigned int)(s->seqToUnseq[uc]);
1070                         nblock++;
1071
1072                         if (! get_mtf_val_init()) {
1073                                 goto save_state_and_return;
1074                         }
1075                         case BZ_X_MTF_5:
1076                                 s->state = BZ_X_MTF_5;
1077                                 if (! get_bits(s, &zvec, zn)) {
1078                                         retVal = BZ_OK;
1079                                         goto save_state_and_return;
1080                                 }
1081                                 while (1) {
1082                                         if (zn > 20 /* the longest code */) {
1083                                                 retVal = BZ_DATA_ERROR;
1084                                                 goto save_state_and_return;
1085                                         }
1086                                         if (zvec <= gLimit[zn]) {
1087                                                 break;
1088                                         }
1089                                         zn++;
1090
1091                                         case BZ_X_MTF_6:
1092                                                 s->state = BZ_X_MTF_6;
1093                                                 if (! get_bits(s, &zj, 1)) {
1094                                                         retVal = BZ_OK;
1095                                                         goto save_state_and_return;
1096                                                 }
1097                                                 zvec = (zvec << 1) | zj;
1098                                 }
1099                         if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1100                                 retVal = BZ_DATA_ERROR;
1101                                 goto save_state_and_return;
1102                         }
1103                         nextSym = gPerm[zvec - gBase[zn]];
1104                         continue;
1105                 }
1106         }
1107
1108         /* Now we know what nblock is, we can do a better sanity
1109                 check on s->origPtr.
1110         */
1111         if (s->origPtr < 0 || s->origPtr >= nblock) {
1112                 retVal = BZ_DATA_ERROR;
1113                 goto save_state_and_return;
1114         }
1115         s->state_out_len = 0;
1116         s->state_out_ch  = 0;
1117         s->calculatedBlockCRC = 0xffffffffL;
1118         s->state = BZ_X_OUTPUT;
1119
1120         /*-- Set up cftab to facilitate generation of T^(-1) --*/
1121         s->cftab[0] = 0;
1122         for (i = 1; i <= 256; i++) {
1123                 s->cftab[i] = s->unzftab[i-1];
1124         }
1125         for (i = 1; i <= 256; i++) {
1126                 s->cftab[i] += s->cftab[i-1];
1127         }
1128
1129         /*-- compute the T^(-1) vector --*/
1130         for (i = 0; i < nblock; i++) {
1131                 uc = (unsigned char)(s->tt[i] & 0xff);
1132                 s->tt[s->cftab[uc]] |= (i << 8);
1133                 s->cftab[uc]++;
1134         }
1135
1136         s->tPos = s->tt[s->origPtr] >> 8;
1137         s->nblock_used = 0;
1138         if (s->blockRandomised) {
1139                 s->rNToGo = 0;
1140                 s->rTPos  = 0;
1141                 s->k0 = bz_get_fast(s);
1142
1143                 s->nblock_used++;
1144                 bz_rand_udp_mask(s);
1145                 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1146         } else {
1147                 s->k0 = bz_get_fast(s);
1148                 s->nblock_used++;
1149         }
1150
1151                 retVal = BZ_OK;
1152                 goto save_state_and_return;
1153
1154 endhdr_2:
1155                 case BZ_X_ENDHDR_2:
1156                         s->state = BZ_X_ENDHDR_2;
1157                         if (! get_bits(s, &uc, 8)) {
1158                                 retVal = BZ_OK;
1159                                 goto save_state_and_return;
1160                         }
1161                         if (uc != 0x72) {
1162                                 retVal = BZ_DATA_ERROR;
1163                                 goto save_state_and_return;
1164                         }
1165
1166                 case BZ_X_ENDHDR_3:
1167                         s->state = BZ_X_ENDHDR_3;
1168                         if (! get_bits(s, &uc, 8)) {
1169                                 retVal = BZ_OK;
1170                                 goto save_state_and_return;
1171                         }
1172                         if (uc != 0x45) {
1173                                 retVal = BZ_DATA_ERROR;
1174                                 goto save_state_and_return;
1175                         }
1176
1177                 case BZ_X_ENDHDR_4:
1178                         s->state = BZ_X_ENDHDR_4;
1179                         if (! get_bits(s, &uc, 8)) {
1180                                 retVal = BZ_OK;
1181                                 goto save_state_and_return;
1182                         }
1183                         if (uc != 0x38) {
1184                                 retVal = BZ_DATA_ERROR;
1185                                 goto save_state_and_return;
1186                         }
1187
1188                 case BZ_X_ENDHDR_5:
1189                         s->state = BZ_X_ENDHDR_5;
1190                         if (! get_bits(s, &uc, 8)) {
1191                                 retVal = BZ_OK;
1192                                 goto save_state_and_return;
1193                         }
1194                         if (uc != 0x50) {
1195                                 retVal = BZ_DATA_ERROR;
1196                                 goto save_state_and_return;
1197                         }
1198
1199                 case BZ_X_ENDHDR_6:
1200                         s->state = BZ_X_ENDHDR_6;
1201                         if (! get_bits(s, &uc, 8)) {
1202                                 retVal = BZ_OK;
1203                                 goto save_state_and_return;
1204                         }
1205                         if (uc != 0x90) {
1206                                 retVal = BZ_DATA_ERROR;
1207                                 goto save_state_and_return;
1208                         }
1209                         s->storedCombinedCRC = 0;
1210
1211                 case BZ_X_CCRC_1:
1212                         s->state = BZ_X_CCRC_1;
1213                         if (! get_bits(s, &uc, 8)) {
1214                                 retVal = BZ_OK;
1215                                 goto save_state_and_return;
1216                         }
1217                         s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1218                 case BZ_X_CCRC_2:
1219                         s->state = BZ_X_CCRC_2;
1220                         if (! get_bits(s, &uc, 8)) {
1221                                 retVal = BZ_OK;
1222                                 goto save_state_and_return;
1223                         }
1224                         s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1225
1226                 case BZ_X_CCRC_3:
1227                         s->state = BZ_X_CCRC_3;
1228                         if (! get_bits(s, &uc, 8)) {
1229                                 retVal = BZ_OK;
1230                                 goto save_state_and_return;
1231                         }
1232                         s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1233
1234                 case BZ_X_CCRC_4:
1235                         s->state = BZ_X_CCRC_4;
1236                         if (! get_bits(s, &uc, 8)) {
1237                                 retVal = BZ_OK;
1238                                 goto save_state_and_return;
1239                         }
1240                         s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1241
1242                 s->state = BZ_X_IDLE;
1243                 retVal = BZ_STREAM_END;
1244                 goto save_state_and_return;
1245
1246         }
1247
1248 save_state_and_return:
1249         s->save_i           = i;
1250         s->save_j           = j;
1251         s->save_t           = t;
1252         s->save_alphaSize   = alphaSize;
1253         s->save_nGroups     = nGroups;
1254         s->save_nSelectors  = nSelectors;
1255         s->save_EOB         = EOB;
1256         s->save_groupNo     = groupNo;
1257         s->save_groupPos    = groupPos;
1258         s->save_nextSym     = nextSym;
1259         s->save_nblockMAX   = nblockMAX;
1260         s->save_nblock      = nblock;
1261         s->save_es          = es;
1262         s->save_N           = N;
1263         s->save_curr        = curr;
1264         s->save_zt          = zt;
1265         s->save_zn          = zn;
1266         s->save_zvec        = zvec;
1267         s->save_zj          = zj;
1268         s->save_gSel        = gSel;
1269         s->save_gMinlen     = gMinlen;
1270         s->save_gLimit      = gLimit;
1271         s->save_gBase       = gBase;
1272         s->save_gPerm       = gPerm;
1273
1274         return retVal;
1275 }
1276
1277 extern void BZ2_bzReadClose(void)
1278 {
1279         if (bzf->initialisedOk) {
1280                 bz_stream *strm = &(bzf->strm);
1281                 DState *s;
1282                 if (strm == NULL) {
1283                         return;
1284                 }
1285                 s = strm->state;
1286                 if ((s == NULL) || (s->strm != strm)) {
1287                         return;
1288                 }
1289                 free(s->tt);
1290                 free(strm->state);
1291                 strm->state = NULL;
1292                 return;
1293         }
1294         free(bzf);
1295 }
1296
1297 static void unRLE_obuf_to_output_FAST(DState *s)
1298 {
1299         unsigned char k1;
1300
1301         if (s->blockRandomised) {
1302                 while (1) {
1303                         /* try to finish existing run */
1304                         while (1) {
1305                                 if (s->strm->avail_out == 0) {
1306                                         return;
1307                                 }
1308                                 if (s->state_out_len == 0) {
1309                                         break;
1310                                 }
1311                                 *((unsigned char *)(s->strm->next_out)) = s->state_out_ch;
1312                                 s->calculatedBlockCRC = (s->calculatedBlockCRC << 8) ^
1313                                         BZ2_crc32Table[(s->calculatedBlockCRC >> 24) ^
1314                                         ((unsigned char)s->state_out_ch)];
1315                                 s->state_out_len--;
1316                                 s->strm->next_out++;
1317                                 s->strm->avail_out--;
1318                         }
1319
1320                         /* can a new run be started? */
1321                         if (s->nblock_used == s->save_nblock+1) {
1322                                 return;
1323                         }
1324                         s->state_out_len = 1;
1325                         s->state_out_ch = s->k0;
1326                         k1 = bz_get_fast(s);
1327                         bz_rand_udp_mask(s);
1328                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1329                         s->nblock_used++;
1330                         if (s->nblock_used == s->save_nblock+1) {
1331                                 continue;
1332                         }
1333                         if (k1 != s->k0) {
1334                                 s->k0 = k1;
1335                                 continue;
1336                         }
1337
1338                         s->state_out_len = 2;
1339                         k1 = bz_get_fast(s);
1340                         bz_rand_udp_mask(s);
1341                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1342                         s->nblock_used++;
1343                         if (s->nblock_used == s->save_nblock+1) {
1344                                 continue;
1345                         }
1346                         if (k1 != s->k0) {
1347                                 s->k0 = k1;
1348                                 continue;
1349                         }
1350                         s->state_out_len = 3;
1351                         k1 = bz_get_fast(s);
1352                         bz_rand_udp_mask(s);
1353                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1354                         s->nblock_used++;
1355                         if (s->nblock_used == s->save_nblock+1) {
1356                                 continue;
1357                         }
1358                         if (k1 != s->k0) {
1359                                 s->k0 = k1;
1360                                 continue;
1361                         }
1362
1363                         k1 = bz_get_fast(s);
1364                         bz_rand_udp_mask(s);
1365                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1366                         s->nblock_used++;
1367                         s->state_out_len = ((int)k1) + 4;
1368                         s->k0 = bz_get_fast(s);
1369                         bz_rand_udp_mask(s);
1370                         s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1371                         s->nblock_used++;
1372                 }
1373         } else {
1374                 /* restore */
1375                 unsigned int c_calculatedBlockCRC = s->calculatedBlockCRC;
1376                 unsigned char c_state_out_ch       = s->state_out_ch;
1377                 int c_state_out_len      = s->state_out_len;
1378                 int c_nblock_used        = s->nblock_used;
1379                 int c_k0                 = s->k0;
1380                 unsigned int    *c_tt                 = s->tt;
1381                 unsigned int    c_tPos               = s->tPos;
1382                 char    *cs_next_out          = s->strm->next_out;
1383                 unsigned int  cs_avail_out         = s->strm->avail_out;
1384                 /* end restore */
1385
1386                 int        s_save_nblockPP = s->save_nblock+1;
1387
1388                 while (1) {
1389                         /* try to finish existing run */
1390                         if (c_state_out_len > 0) {
1391                                 while (TRUE) {
1392                                         if (cs_avail_out == 0) {
1393                                                 goto return_notr;
1394                                         }
1395                                         if (c_state_out_len == 1) {
1396                                                 break;
1397                                         }
1398                                         *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1399                                         c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1400                                                 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1401                                                 ((unsigned char)c_state_out_ch)];
1402                                         c_state_out_len--;
1403                                         cs_next_out++;
1404                                         cs_avail_out--;
1405                                 }
1406 s_state_out_len_eq_one:
1407                                 {
1408                                         if (cs_avail_out == 0) {
1409                                                 c_state_out_len = 1;
1410                                                 goto return_notr;
1411                                         }
1412                                         *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1413                                         c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1414                                                 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1415                                                 ((unsigned char)c_state_out_ch)];
1416                                         cs_next_out++;
1417                                         cs_avail_out--;
1418                                 }
1419                         }
1420                         /* can a new run be started? */
1421                         if (c_nblock_used == s_save_nblockPP) {
1422                                 c_state_out_len = 0; goto return_notr;
1423                         }
1424                         c_state_out_ch = c_k0;
1425                         c_tPos = c_tt[c_tPos];
1426                         k1 = (unsigned char)(c_tPos & 0xff);
1427                         c_tPos >>= 8;
1428
1429                         c_nblock_used++;
1430
1431                         if (k1 != c_k0) {
1432                                 c_k0 = k1;
1433                                 goto s_state_out_len_eq_one;
1434                         }
1435
1436                         if (c_nblock_used == s_save_nblockPP) {
1437                                 goto s_state_out_len_eq_one;
1438                         }
1439
1440                         c_state_out_len = 2;
1441                         c_tPos = c_tt[c_tPos];
1442                         k1 = (unsigned char)(c_tPos & 0xff);
1443                         c_tPos >>= 8;
1444
1445                         c_nblock_used++;
1446                         if (c_nblock_used == s_save_nblockPP) {
1447                                 continue;
1448                         }
1449                         if (k1 != c_k0) {
1450                                 c_k0 = k1;
1451                                 continue;
1452                         }
1453
1454                         c_state_out_len = 3;
1455                         c_tPos = c_tt[c_tPos];
1456                         k1 = (unsigned char)(c_tPos & 0xff);
1457                         c_tPos >>= 8;
1458
1459                         c_nblock_used++;
1460                         if (c_nblock_used == s_save_nblockPP) {
1461                                 continue;
1462                         }
1463                         if (k1 != c_k0) {
1464                                 c_k0 = k1;
1465                                 continue;
1466                         }
1467
1468                         c_tPos = c_tt[c_tPos];
1469                         k1 = (unsigned char)(c_tPos & 0xff);
1470                         c_tPos >>= 8;
1471
1472                         c_nblock_used++;
1473                         c_state_out_len = ((int)k1) + 4;
1474
1475                         c_tPos = c_tt[c_tPos];
1476                         c_k0 = (unsigned char)(c_tPos & 0xff);
1477                         c_tPos >>= 8;
1478
1479                         c_nblock_used++;
1480                 }
1481
1482 return_notr:
1483
1484                 /* save */
1485                 s->calculatedBlockCRC = c_calculatedBlockCRC;
1486                 s->state_out_ch       = c_state_out_ch;
1487                 s->state_out_len      = c_state_out_len;
1488                 s->nblock_used        = c_nblock_used;
1489                 s->k0                 = c_k0;
1490                 s->tt                 = c_tt;
1491                 s->tPos               = c_tPos;
1492                 s->strm->next_out     = cs_next_out;
1493                 s->strm->avail_out    = cs_avail_out;
1494                 /* end save */
1495         }
1496 }
1497 static inline
1498 int BZ2_bzDecompress(bz_stream *strm)
1499 {
1500         DState* s;
1501         s = strm->state;
1502
1503         while (1) {
1504                 if (s->state == BZ_X_IDLE) {
1505                         return BZ_SEQUENCE_ERROR;
1506                 }
1507                 if (s->state == BZ_X_OUTPUT) {
1508                         unRLE_obuf_to_output_FAST(s);
1509                         if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
1510                                 s->calculatedBlockCRC = ~(s->calculatedBlockCRC);
1511                                 if (s->calculatedBlockCRC != s->storedBlockCRC) {
1512                                         return BZ_DATA_ERROR;
1513                                 }
1514                                 s->calculatedCombinedCRC = (s->calculatedCombinedCRC << 1) | (s->calculatedCombinedCRC >> 31);
1515                                 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
1516                                 s->state = BZ_X_BLKHDR_1;
1517                         } else {
1518                                 return BZ_OK;
1519                         }
1520                 }
1521                 if (s->state >= BZ_X_MAGIC_1) {
1522                         int r = BZ2_decompress(s);
1523                         if (r == BZ_STREAM_END) {
1524                                 if (s->calculatedCombinedCRC != s->storedCombinedCRC) {
1525                                         return BZ_DATA_ERROR;
1526                                 }
1527                                 return r;
1528                         }
1529                         if (s->state != BZ_X_OUTPUT) {
1530                                 return r;
1531                         }
1532                 }
1533         }
1534
1535         return(0);  /*NOTREACHED*/
1536 }
1537
1538 extern ssize_t read_bz2(int fd, void *buf, size_t count)
1539 {
1540         int n, ret;
1541
1542         bzerr = BZ_OK;
1543         if (count == 0) {
1544                 return(0);
1545         }
1546         bzf->strm.avail_out = count;
1547         bzf->strm.next_out = buf;
1548
1549         while (1) {
1550                 if (bzf->strm.avail_in == 0) {
1551                         n = bb_xread(bzf->fd, bzf->buf, BZ_MAX_UNUSED);
1552                         if (n == 0) {
1553                                 break;
1554                         }
1555                         bzf->bufN = n;
1556                         bzf->strm.avail_in = bzf->bufN;
1557                         bzf->strm.next_in = bzf->buf;
1558                 }
1559
1560                 ret = BZ2_bzDecompress(&(bzf->strm));
1561
1562                 if ((ret != BZ_OK) && (ret != BZ_STREAM_END)) {
1563                         bb_error_msg_and_die("Error decompressing");
1564                 }
1565
1566                 if (ret == BZ_STREAM_END) {
1567                         bzerr = BZ_STREAM_END;
1568                         return(count - bzf->strm.avail_out);
1569                 }
1570                 if (bzf->strm.avail_out == 0) {
1571                         bzerr = BZ_OK;
1572                         return(count);
1573                 }
1574         }
1575         return(0);
1576 }
1577
1578 extern void BZ2_bzReadOpen(int fd, void *unused, int nUnused)
1579 {
1580         DState *s;
1581
1582         bzf = xmalloc(sizeof(bzFile));
1583         bzf->initialisedOk = FALSE;
1584         bzf->fd        = fd;
1585         bzf->bufN      = 0;
1586
1587         s = xmalloc(sizeof(DState));
1588         s->strm = &bzf->strm;
1589         s->state = BZ_X_MAGIC_1;
1590         s->bsLive = 0;
1591         s->bsBuff = 0;
1592         s->calculatedCombinedCRC = 0;
1593         s->tt = NULL;
1594         s->currBlockNo = 0;
1595         bzf->strm.state = s;
1596
1597         while (nUnused > 0) {
1598                 bzf->buf[bzf->bufN] = *((unsigned char *)(unused));
1599                 bzf->bufN++;
1600                 unused = ((void *)( 1 + ((unsigned char *)(unused))  ));
1601                 nUnused--;
1602         }
1603         bzf->strm.avail_in = bzf->bufN;
1604         bzf->strm.next_in  = bzf->buf;
1605
1606         bzf->initialisedOk = TRUE;
1607
1608         return;
1609 }
1610
1611 extern unsigned char uncompressStream(int src_fd, int dst_fd)
1612 {
1613         unsigned char unused[BZ_MAX_UNUSED];
1614         unsigned char *unusedTmp;
1615         unsigned char obuf[5000];
1616         int nread;
1617         int nUnused;
1618         int streamNo;
1619         int i;
1620
1621         nUnused = 0;
1622         streamNo = 0;
1623
1624         while(1) {
1625                 BZ2_bzReadOpen(src_fd, unused, nUnused);
1626                 streamNo++;
1627
1628                 while (bzerr == BZ_OK) {
1629                         nread = read_bz2(src_fd, obuf, 5000);
1630                         if (bzerr == BZ_DATA_ERROR_MAGIC) {
1631                                 bb_error_msg_and_die("invalid magic");
1632                         }
1633                         if (((bzerr == BZ_OK) || (bzerr == BZ_STREAM_END)) && (nread > 0)) {
1634                                 if (write(dst_fd, obuf, nread) != nread) {
1635                                         BZ2_bzReadClose();
1636                                         bb_perror_msg_and_die("Couldnt write to file");
1637                                 }
1638                         }
1639                 }
1640                 nUnused = bzf->strm.avail_in;
1641                 unusedTmp = bzf->strm.next_in;
1642
1643                 for (i = 0; i < nUnused; i++) {
1644                         unused[i] = unusedTmp[i];
1645                 }
1646                 BZ2_bzReadClose();
1647                 if (nUnused == 0) {
1648                         break;
1649                 }
1650         }
1651
1652         close(src_fd);
1653         if (dst_fd != fileno(stdout)) {
1654                 close(dst_fd);
1655         }
1656         return TRUE;
1657 }
1658