archival/bunzip2.c

   1 /* Modified for busybox by Glenn McGrath <bug1@optushome.com.au> */
   2 /* Added support output to stdout by Thomas Lundquist <thomasez@zelow.no> */
   3 /*--
   4   This file is a part of bzip2 and/or libbzip2, a program and
   5   library for lossless, block-sorting data compression.
   6
   7   Copyright (C) 1996-2000 Julian R Seward.  All rights reserved.
   8
   9   Redistribution and use in source and binary forms, with or without
  10   modification, are permitted provided that the following conditions
  11   are met:
  12
  13   1. Redistributions of source code must retain the above copyright
  14      notice, this list of conditions and the following disclaimer.
  15
  16   2. The origin of this software must not be misrepresented; you must
  17      not claim that you wrote the original software.  If you use this
  18      software in a product, an acknowledgment in the product
  19      documentation would be appreciated but is not required.
  20
  21   3. Altered source versions must be plainly marked as such, and must
  22      not be misrepresented as being the original software.
  23
  24   4. The name of the author may not be used to endorse or promote
  25      products derived from this software without specific prior written
  26      permission.
  27
  28   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  29   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  30   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  31   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  32   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  33   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  34   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  35   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  36   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  37   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  38   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39
  40   Julian Seward, Cambridge, UK.
  41   jseward@acm.org
  42   bzip2/libbzip2 version 1.0 of 21 March 2000
  43
  44   This program is based on (at least) the work of:
  45      Mike Burrows
  46      David Wheeler
  47      Peter Fenwick
  48      Alistair Moffat
  49      Radford Neal
  50      Ian H. Witten
  51      Robert Sedgewick
  52      Jon L. Bentley
  53
  54   For more information on these sources, see the manual.
  55 --*/
  56
  57 #include <stdlib.h>
  58 #include <stdio.h>
  59 #include <string.h>
  60 #include <getopt.h>
  61 #include <unistd.h>
  62 #include <busybox.h>
  63
  64 //#define TRUE 1
  65 //#define FALSE 0
  66
  67 #define MTFA_SIZE 4096
  68 #define MTFL_SIZE 16
  69 #define BZ_N_GROUPS 6
  70 #define BZ_G_SIZE   50
  71 #define BZ_MAX_ALPHA_SIZE 258
  72
  73 #define BZ_OK                0
  74 #define BZ_RUN_OK            1
  75 #define BZ_FLUSH_OK          2
  76 #define BZ_FINISH_OK         3
  77 #define BZ_STREAM_END        4
  78 #define BZ_SEQUENCE_ERROR    (-1)
  79 #define BZ_PARAM_ERROR       (-2)
  80 #define BZ_MEM_ERROR         (-3)
  81 #define BZ_DATA_ERROR        (-4)
  82 #define BZ_DATA_ERROR_MAGIC  (-5)
  83 #define BZ_IO_ERROR          (-6)
  84 #define BZ_UNEXPECTED_EOF    (-7)
  85 #define BZ_OUTBUFF_FULL      (-8)
  86 #define BZ_CONFIG_ERROR      (-9)
  87
  88 #define BZ_RUNA 0
  89 #define BZ_RUNB 1
  90
  91 #define BZ_MAX_UNUSED 5000
  92 #define FILE_NAME_LEN 1034
  93 /*-- states for decompression. --*/
  94
  95 #define BZ_X_IDLE        1
  96 #define BZ_X_OUTPUT      2
  97
  98 #define BZ_X_MAGIC_1     10
  99 #define BZ_X_MAGIC_2     11
 100 #define BZ_X_MAGIC_3     12
 101 #define BZ_X_MAGIC_4     13
 102 #define BZ_X_BLKHDR_1    14
 103 #define BZ_X_BLKHDR_2    15
 104 #define BZ_X_BLKHDR_3    16
 105 #define BZ_X_BLKHDR_4    17
 106 #define BZ_X_BLKHDR_5    18
 107 #define BZ_X_BLKHDR_6    19
 108 #define BZ_X_BCRC_1      20
 109 #define BZ_X_BCRC_2      21
 110 #define BZ_X_BCRC_3      22
 111 #define BZ_X_BCRC_4      23
 112 #define BZ_X_RANDBIT     24
 113 #define BZ_X_ORIGPTR_1   25
 114 #define BZ_X_ORIGPTR_2   26
 115 #define BZ_X_ORIGPTR_3   27
 116 #define BZ_X_MAPPING_1   28
 117 #define BZ_X_MAPPING_2   29
 118 #define BZ_X_SELECTOR_1  30
 119 #define BZ_X_SELECTOR_2  31
 120 #define BZ_X_SELECTOR_3  32
 121 #define BZ_X_CODING_1    33
 122 #define BZ_X_CODING_2    34
 123 #define BZ_X_CODING_3    35
 124 #define BZ_X_MTF_1       36
 125 #define BZ_X_MTF_2       37
 126 #define BZ_X_MTF_3       38
 127 #define BZ_X_MTF_4       39
 128 #define BZ_X_MTF_5       40
 129 #define BZ_X_MTF_6       41
 130 #define BZ_X_ENDHDR_2    42
 131 #define BZ_X_ENDHDR_3    43
 132 #define BZ_X_ENDHDR_4    44
 133 #define BZ_X_ENDHDR_5    45
 134 #define BZ_X_ENDHDR_6    46
 135 #define BZ_X_CCRC_1      47
 136 #define BZ_X_CCRC_2      48
 137 #define BZ_X_CCRC_3      49
 138 #define BZ_X_CCRC_4      50
 139
 140 #define BZ_MAX_CODE_LEN    23
 141 #define BZ_VERSION  "1.0.1, 23-June-2000"
 142 #define OM_TEST          3
 143 #define SM_F2F 3
 144
 145 typedef struct {
 146         char *next_in;
 147         unsigned int avail_in;
 148         unsigned int total_in_lo32;
 149         unsigned int total_in_hi32;
 150
 151         char *next_out;
 152         unsigned int avail_out;
 153         unsigned int total_out_lo32;
 154         unsigned int total_out_hi32;
 155
 156         void *state;
 157
 158         void *(*bzalloc)(void *,int,int);
 159         void (*bzfree)(void *,void *);
 160         void *opaque;
 161 } bz_stream;
 162
 163 typedef struct {
 164         bz_stream       strm;
 165         FILE    *handle;
 166     unsigned char       initialisedOk;
 167         unsigned char   writing;
 168         char    buf[BZ_MAX_UNUSED];
 169         int             lastErr;
 170         int             bufN;
 171 } bzFile;
 172
 173 /*-- Structure holding all the decompression-side stuff. --*/
 174 typedef struct {
 175         /* pointer back to the struct bz_stream */
 176         bz_stream* strm;
 177
 178         /* state indicator for this stream */
 179         int     state;
 180
 181         /* for doing the final run-length decoding */
 182         unsigned char    state_out_ch;
 183         int    state_out_len;
 184         unsigned char     blockRandomised;
 185         int rNToGo;
 186         int rTPos;
 187
 188         /* the buffer for bit stream reading */
 189         unsigned int   bsBuff;
 190         int    bsLive;
 191
 192         /* misc administratium */
 193         int    blockSize100k;
 194         unsigned char     smallDecompress;
 195         int    currBlockNo;
 196         int    verbosity;
 197
 198         /* for undoing the Burrows-Wheeler transform */
 199         int    origPtr;
 200         unsigned int   tPos;
 201         int    k0;
 202         int    unzftab[256];
 203         int    nblock_used;
 204         int    cftab[257];
 205         int    cftabCopy[257];
 206
 207         /* for undoing the Burrows-Wheeler transform (FAST) */
 208         unsigned int *tt;
 209
 210         /* for undoing the Burrows-Wheeler transform (SMALL) */
 211         unsigned short *ll16;
 212         unsigned char *ll4;
 213
 214         /* stored and calculated CRCs */
 215         unsigned int   storedBlockCRC;
 216         unsigned int   storedCombinedCRC;
 217         unsigned int   calculatedBlockCRC;
 218         unsigned int   calculatedCombinedCRC;
 219
 220         /* map of bytes used in block */
 221         int    nInUse;
 222         unsigned char     inUse[256];
 223         unsigned char     inUse16[16];
 224         unsigned char    seqToUnseq[256];
 225
 226         /* for decoding the MTF values */
 227         unsigned char    mtfa   [MTFA_SIZE];
 228         unsigned char    selector   [2 + (900000 / BZ_G_SIZE)];
 229         unsigned char    selectorMtf[2 + (900000 / BZ_G_SIZE)];
 230         unsigned char    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 231         int    mtfbase[256 / MTFL_SIZE];
 232
 233         int    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 234         int    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 235         int    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 236         int    minLens[BZ_N_GROUPS];
 237
 238         /* save area for scalars in the main decompress code */
 239         int    save_i;
 240         int    save_j;
 241         int    save_t;
 242         int    save_alphaSize;
 243         int    save_nGroups;
 244         int    save_nSelectors;
 245         int    save_EOB;
 246         int    save_groupNo;
 247         int    save_groupPos;
 248         int    save_nextSym;
 249         int    save_nblockMAX;
 250         int    save_nblock;
 251         int    save_es;
 252         int    save_N;
 253         int    save_curr;
 254         int    save_zt;
 255         int    save_zn;
 256         int    save_zvec;
 257         int    save_zj;
 258         int    save_gSel;
 259         int    save_gMinlen;
 260         int     *save_gLimit;
 261         int     *save_gBase;
 262         int     *save_gPerm;
 263 } DState;
 264
 265 int BZ2_rNums[512];
 266 //int   verbosity_level;
 267 unsigned char smallMode;
 268 unsigned char noisy;
 269 char *progName;
 270 char inName[FILE_NAME_LEN];
 271 char outName[FILE_NAME_LEN];
 272 int srcMode;
 273 int opMode;
 274 unsigned char deleteOutputOnInterrupt;
 275 FILE *outputHandleJustInCase;
 276 int numFileNames;
 277 int numFilesProcessed;
 278 int exitValue;
 279
 280 const unsigned int BZ2_crc32Table[256] = {
 281
 282    /*-- Ugly, innit? --*/
 283
 284    0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
 285    0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
 286    0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
 287    0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
 288    0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
 289    0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
 290    0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
 291    0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
 292    0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
 293    0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
 294    0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
 295    0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
 296    0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
 297    0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
 298    0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
 299    0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
 300    0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
 301    0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
 302    0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
 303    0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
 304    0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
 305    0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
 306    0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
 307    0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
 308    0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
 309    0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
 310    0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
 311    0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
 312    0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
 313    0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
 314    0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
 315    0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
 316    0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
 317    0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
 318    0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
 319    0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
 320    0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
 321    0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
 322    0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
 323    0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
 324    0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
 325    0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
 326    0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
 327    0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
 328    0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
 329    0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
 330    0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
 331    0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
 332    0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
 333    0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
 334    0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
 335    0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
 336    0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
 337    0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
 338    0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
 339    0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
 340    0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
 341    0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
 342    0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
 343    0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
 344    0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
 345    0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
 346    0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
 347    0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
 348 };
 349
 350 void bz_rand_udp_mask(DState *s)
 351 {
 352         if (s->rNToGo == 0) {
 353                 s->rNToGo = BZ2_rNums[s->rTPos];
 354                 s->rTPos++;
 355                 if (s->rTPos == 512) {
 356                         s->rTPos = 0;
 357                 }
 358         }
 359         s->rNToGo--;
 360 }
 361
 362 static unsigned char myfeof(FILE *f)
 363 {
 364         int c = fgetc(f);
 365         if (c == EOF) {
 366                 return(TRUE);
 367         }
 368         ungetc(c, f);
 369         return(FALSE);
 370 }
 371
 372 static void cleanUpAndFail(int ec)
 373 {
 374         int retVal;
 375
 376         if ((srcMode == SM_F2F) && (opMode != OM_TEST) && deleteOutputOnInterrupt) {
 377                 if (noisy) {
 378                         error_msg("%s: Deleting output file %s, if it exists.\n", progName, outName);
 379                 }
 380                 if (outputHandleJustInCase != NULL) {
 381                         fclose(outputHandleJustInCase);
 382                 }
 383                 retVal = remove(outName);
 384                 if (retVal != 0) {
 385                         error_msg("%s: WARNING: deletion of output file (apparently) failed.\n", progName);
 386                 }
 387         }
 388         if (noisy && (numFileNames > 0) && (numFilesProcessed < numFileNames)) {
 389                 error_msg("%s: WARNING: some files have not been processed:\n"
 390                         "\t%d specified on command line, %d not processed yet.\n\n",
 391                         progName, numFileNames, numFileNames - numFilesProcessed );
 392         }
 393
 394         exit(ec);
 395 }
 396
 397
 398 void panic(char *s)
 399 {
 400         error_msg("\n%s: PANIC -- internal consistency error:\n"
 401              "\t%s\n"
 402              "\tThis is a BUG.  Please report it to me at:\n"
 403              "\tjseward@acm.org\n",
 404              progName, s);
 405         cleanUpAndFail( 3 );
 406 }
 407
 408 void BZ2_hbCreateDecodeTables(int *limit, int *base, int *perm, unsigned char *length, int minLen, int maxLen, int alphaSize )
 409 {
 410         int pp, i, j, vec;
 411
 412         pp = 0;
 413         for (i = minLen; i <= maxLen; i++) {
 414                 for (j = 0; j < alphaSize; j++) {
 415                         if (length[j] == i) {
 416                                 perm[pp] = j;
 417                                 pp++;
 418                         }
 419                 }
 420         }
 421
 422         for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
 423                 base[i] = 0;
 424         }
 425
 426         for (i = 0; i < alphaSize; i++) {
 427                 base[length[i]+1]++;
 428         }
 429
 430         for (i = 1; i < BZ_MAX_CODE_LEN; i++) {
 431                 base[i] += base[i-1];
 432         }
 433
 434         for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
 435                 limit[i] = 0;
 436         }
 437         vec = 0;
 438
 439         for (i = minLen; i <= maxLen; i++) {
 440                 vec += (base[i+1] - base[i]);
 441                 limit[i] = vec-1;
 442                 vec <<= 1;
 443         }
 444         for (i = minLen + 1; i <= maxLen; i++) {
 445                 base[i] = ((limit[i-1] + 1) << 1) - base[i];
 446         }
 447 }
 448
 449 int bz_get_small(DState *s)
 450 {
 451         int cccc;
 452         int nb, na, mid;
 453         nb = 0;
 454         na = 256;
 455         do {
 456                 mid = (nb + na) >> 1;
 457                 if (s->tPos >= s->cftab[mid]) {
 458                         nb = mid;
 459                 } else {
 460                         na = mid;
 461                 }
 462         }
 463         while (na - nb != 1);
 464         cccc = nb;
 465         s->tPos = (((unsigned int)s->ll16[s->tPos]) |
 466                 (((((unsigned int)(s->ll4[(s->tPos) >> 1])) >>
 467                 (((s->tPos) << 2) & 0x4)) & 0xF) << 16));
 468         return(cccc);
 469 }
 470
 471 void assert_h(int errcode)
 472 {
 473         error_msg_and_die("\n\nbzip2/libbzip2: internal error number %d.\n"
 474                 "This is a bug in bzip2/libbzip2, %s.\n"
 475                 "Please report it to me at: jseward@acm.org.  If this happened\n"
 476                 "when you were using some program which uses libbzip2 as a\n"
 477                 "component, you should also report this bug to the author(s)\n"
 478                 "of that program.  Please make an effort to report this bug;\n"
 479                 "timely and accurate bug reports eventually lead to higher\n"
 480                 "quality software.  Thanks.  Julian Seward, 21 March 2000.\n\n",
 481                 errcode, BZ_VERSION);
 482 }
 483
 484 static int get_bits(DState *s, int *vvv, char nnn)
 485 {
 486         while (1) {
 487                 if (s->bsLive >= nnn) {
 488                         *vvv = (s->bsBuff >> (s->bsLive-nnn)) & ((1 << nnn)-1);
 489                         s->bsLive -= nnn;
 490                         break;
 491                 }
 492                 if (s->strm->avail_in == 0) {
 493                         return(FALSE);
 494                 }
 495                 s->bsBuff = (s->bsBuff << 8) | ((unsigned int) (*((unsigned char*)(s->strm->next_in))));
 496                 s->bsLive += 8;
 497                 s->strm->next_in++;
 498                 s->strm->avail_in--;
 499                 s->strm->total_in_lo32++;
 500                 if (s->strm->total_in_lo32 == 0) {
 501                         s->strm->total_in_hi32++;
 502                 }
 503         }
 504         return(TRUE);
 505 }
 506
 507 int bz_get_fast(DState *s)
 508 {
 509         int cccc;
 510         s->tPos = s->tt[s->tPos];
 511         cccc = (unsigned char)(s->tPos & 0xff);
 512         s->tPos >>= 8;
 513         return(cccc);
 514 }
 515
 516 /*---------------------------------------------------*/
 517 int BZ2_decompress(DState *s)
 518 {
 519         int uc = 0;
 520         int     retVal;
 521         int     minLen, maxLen;
 522         bz_stream       *strm = s->strm;
 523
 524         /* stuff that needs to be saved/restored */
 525         int  i;
 526         int  j;
 527         int  t;
 528         int  alphaSize;
 529         int  nGroups;
 530         int  nSelectors;
 531         int  EOB;
 532         int  groupNo;
 533         int  groupPos;
 534         int  nextSym;
 535         int  nblockMAX;
 536         int  nblock;
 537         int  es;
 538         int  N;
 539         int  curr;
 540         int  zt;
 541         int  zn;
 542         int  zvec;
 543         int  zj;
 544         int  gSel;
 545         int  gMinlen;
 546         int *gLimit;
 547         int *gBase;
 548         int *gPerm;
 549         int switch_val;
 550
 551         int get_mtf_val_init(void)
 552         {
 553                 if (groupPos == 0) {
 554                         groupNo++;
 555                         if (groupNo >= nSelectors) {
 556                                 retVal = BZ_DATA_ERROR;
 557                                 return(FALSE);
 558                         }
 559                         groupPos = BZ_G_SIZE;
 560                         gSel = s->selector[groupNo];
 561                         gMinlen = s->minLens[gSel];
 562                         gLimit = &(s->limit[gSel][0]);
 563                         gPerm = &(s->perm[gSel][0]);
 564                         gBase = &(s->base[gSel][0]);
 565                 }
 566                 groupPos--;
 567                 zn = gMinlen;
 568                 return(TRUE);
 569         }
 570
 571         if (s->state == BZ_X_MAGIC_1) {
 572                 /*initialise the save area*/
 573                 s->save_i           = 0;
 574                 s->save_j           = 0;
 575                 s->save_t           = 0;
 576                 s->save_alphaSize   = 0;
 577                 s->save_nGroups     = 0;
 578                 s->save_nSelectors  = 0;
 579                 s->save_EOB         = 0;
 580                 s->save_groupNo     = 0;
 581                 s->save_groupPos    = 0;
 582                 s->save_nextSym     = 0;
 583                 s->save_nblockMAX   = 0;
 584                 s->save_nblock      = 0;
 585                 s->save_es          = 0;
 586                 s->save_N           = 0;
 587                 s->save_curr        = 0;
 588                 s->save_zt          = 0;
 589                 s->save_zn          = 0;
 590                 s->save_zvec        = 0;
 591                 s->save_zj          = 0;
 592                 s->save_gSel        = 0;
 593                 s->save_gMinlen     = 0;
 594                 s->save_gLimit      = NULL;
 595                 s->save_gBase       = NULL;
 596                 s->save_gPerm       = NULL;
 597         }
 598
 599         /*restore from the save area*/
 600         i           = s->save_i;
 601         j           = s->save_j;
 602         t           = s->save_t;
 603         alphaSize   = s->save_alphaSize;
 604         nGroups     = s->save_nGroups;
 605         nSelectors  = s->save_nSelectors;
 606         EOB         = s->save_EOB;
 607         groupNo     = s->save_groupNo;
 608         groupPos    = s->save_groupPos;
 609         nextSym     = s->save_nextSym;
 610         nblockMAX   = s->save_nblockMAX;
 611         nblock      = s->save_nblock;
 612         es          = s->save_es;
 613         N           = s->save_N;
 614         curr        = s->save_curr;
 615         zt          = s->save_zt;
 616         zn          = s->save_zn;
 617         zvec        = s->save_zvec;
 618         zj          = s->save_zj;
 619         gSel        = s->save_gSel;
 620         gMinlen     = s->save_gMinlen;
 621         gLimit      = s->save_gLimit;
 622         gBase       = s->save_gBase;
 623         gPerm       = s->save_gPerm;
 624
 625         retVal = BZ_OK;
 626         switch_val = s->state;
 627         switch (switch_val) {
 628                 case BZ_X_MAGIC_1:
 629                         s->state = BZ_X_MAGIC_1;
 630                         if (! get_bits(s, &uc, 8)) {
 631                                 retVal = BZ_OK;
 632                                 goto save_state_and_return;
 633                         }
 634                         if (uc != 'B') {
 635                                 retVal = BZ_DATA_ERROR_MAGIC;
 636                                 goto save_state_and_return;
 637                         }
 638
 639                 case BZ_X_MAGIC_2:
 640                         s->state = BZ_X_MAGIC_2;
 641                         if (! get_bits(s, &uc, 8)) {
 642                                 retVal = BZ_OK;
 643                                 goto save_state_and_return;
 644                         }
 645                         if (uc != 'Z') {
 646                                 retVal = BZ_DATA_ERROR_MAGIC;
 647                                 goto save_state_and_return;
 648                         }
 649
 650                 case BZ_X_MAGIC_3:
 651                         s->state = BZ_X_MAGIC_3;
 652                         if (! get_bits(s, &uc, 8)) {
 653                                 retVal = BZ_OK;
 654                                 goto save_state_and_return;
 655                         }
 656                         if (uc != 'h') {
 657                                 retVal = BZ_DATA_ERROR_MAGIC;
 658                                 goto save_state_and_return;
 659                         }
 660
 661                 case BZ_X_MAGIC_4:
 662                         s->state = BZ_X_MAGIC_4;
 663                         if (! get_bits(s, &s->blockSize100k, 8)) {
 664                                 retVal = BZ_OK;
 665                                 goto save_state_and_return;
 666                         }
 667                         if ((s->blockSize100k < '1') || (s->blockSize100k > '9')) {
 668                                 retVal = BZ_DATA_ERROR_MAGIC;
 669                                 goto save_state_and_return;
 670                         }
 671                         s->blockSize100k -= '0';
 672
 673                         if (s->smallDecompress) {
 674                                 s->ll16 = (strm->bzalloc)(strm->opaque, s->blockSize100k * 100000 * sizeof(unsigned short), 1);
 675                                 s->ll4 = (strm->bzalloc)(strm->opaque, ((1 + s->blockSize100k * 100000) >> 1) * sizeof(unsigned char), 1);
 676
 677                                 if (s->ll16 == NULL || s->ll4 == NULL) {
 678                                         retVal = BZ_MEM_ERROR;
 679                                         goto save_state_and_return;
 680                                 }
 681                         } else {
 682                                 s->tt = (strm->bzalloc)(strm->opaque, s->blockSize100k * 100000 * sizeof(int), 1);
 683                                 if (s->tt == NULL) {
 684                                         retVal = BZ_MEM_ERROR;
 685                                         goto save_state_and_return;
 686                                 }
 687                         }
 688
 689                 case BZ_X_BLKHDR_1:
 690                         s->state = BZ_X_BLKHDR_1;
 691                         if (! get_bits(s, &uc, 8)) {
 692                                 retVal = BZ_OK;
 693                                 goto save_state_and_return;
 694                         }
 695
 696                         if (uc == 0x17) {
 697                                 goto endhdr_2;
 698                         }
 699                         if (uc != 0x31) {
 700                                 retVal = BZ_DATA_ERROR;
 701                                 goto save_state_and_return;
 702                         }
 703
 704                 case BZ_X_BLKHDR_2:
 705                         s->state = BZ_X_BLKHDR_2;
 706                         if (! get_bits(s, &uc, 8)) {
 707                                 retVal = BZ_OK;
 708                                 goto save_state_and_return;
 709                         }
 710                         if (uc != 0x41) {
 711                                 retVal = BZ_DATA_ERROR;
 712                                 goto save_state_and_return;
 713                         }
 714
 715                 case BZ_X_BLKHDR_3:
 716                         s->state = BZ_X_BLKHDR_3;
 717                         if (! get_bits(s, &uc, 8)) {
 718                                 retVal = BZ_OK;
 719                                 goto save_state_and_return;
 720                         }
 721                         if (uc != 0x59) {
 722                                 retVal = BZ_DATA_ERROR;
 723                                 goto save_state_and_return;
 724                         }
 725
 726                 case BZ_X_BLKHDR_4:
 727                         s->state = BZ_X_BLKHDR_4;
 728                         if (! get_bits(s, &uc, 8)) {
 729                                 retVal = BZ_OK;
 730                                 goto save_state_and_return;
 731                         }
 732                         if (uc != 0x26) {
 733                                 retVal = BZ_DATA_ERROR;
 734                                 goto save_state_and_return;
 735                         }
 736
 737                 case BZ_X_BLKHDR_5:
 738                         s->state = BZ_X_BLKHDR_5;
 739                         if (! get_bits(s, &uc, 8)) {
 740                                 retVal = BZ_OK;
 741                                 goto save_state_and_return;
 742                         }
 743                         if (uc != 0x53) {
 744                                 retVal = BZ_DATA_ERROR;
 745                                 goto save_state_and_return;
 746                         }
 747
 748                 case BZ_X_BLKHDR_6:
 749                         s->state = BZ_X_BLKHDR_6;
 750                         if (! get_bits(s, &uc, 8)) {
 751                                 retVal = BZ_OK;
 752                                 goto save_state_and_return;
 753                         }
 754                         if (uc != 0x59) {
 755                                 retVal = BZ_DATA_ERROR;
 756                                 goto save_state_and_return;
 757                         }
 758
 759                 s->currBlockNo++;
 760                 if (s->verbosity >= 2) {
 761                         error_msg("\n    [%d: huff+mtf ", s->currBlockNo);
 762                 }
 763                 s->storedBlockCRC = 0;
 764
 765                 case BZ_X_BCRC_1:
 766                         s->state = BZ_X_BCRC_1;
 767                         if (! get_bits(s, &uc, 8)) {
 768                                 retVal = BZ_OK;
 769                                 goto save_state_and_return;
 770                         }
 771                         s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
 772
 773                 case BZ_X_BCRC_2:
 774                         s->state = BZ_X_BCRC_2;
 775                         if (! get_bits(s, &uc, 8)) {
 776                                 retVal = BZ_OK;
 777                                 goto save_state_and_return;
 778                         }
 779                         s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
 780
 781                 case BZ_X_BCRC_3:
 782                         s->state = BZ_X_BCRC_3;
 783                         if (! get_bits(s, &uc, 8)) {
 784                                 retVal = BZ_OK;
 785                                 goto save_state_and_return;
 786                         }
 787                         s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
 788
 789                 case BZ_X_BCRC_4:
 790                         s->state = BZ_X_BCRC_4;
 791                         if (! get_bits(s, &uc, 8)) {
 792                                 retVal = BZ_OK;
 793                                 goto save_state_and_return;
 794                         }
 795                         s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
 796
 797                 case BZ_X_RANDBIT:
 798                         s->state = BZ_X_RANDBIT;
 799                         {
 800                                 int tmp = s->blockRandomised;
 801                                 const int ret = get_bits(s, &tmp, 1);
 802                                 s->blockRandomised = tmp;
 803                                 if (! ret) {
 804                                         retVal = BZ_OK;
 805                                         goto save_state_and_return;
 806                                 }
 807                         }
 808
 809                         s->origPtr = 0;
 810
 811                 case BZ_X_ORIGPTR_1:
 812                         s->state = BZ_X_ORIGPTR_1;
 813                         if (! get_bits(s, &uc, 8)) {
 814                                 retVal = BZ_OK;
 815                                 goto save_state_and_return;
 816                         }
 817                         s->origPtr = (s->origPtr << 8) | ((int)uc);
 818
 819                 case BZ_X_ORIGPTR_2:
 820                         s->state = BZ_X_ORIGPTR_2;
 821                         if (! get_bits(s, &uc, 8)) {
 822                                 retVal = BZ_OK;
 823                                 goto save_state_and_return;
 824                         }
 825                         s->origPtr = (s->origPtr << 8) | ((int)uc);
 826
 827                 case BZ_X_ORIGPTR_3:
 828                         s->state = BZ_X_ORIGPTR_3;
 829                         if (! get_bits(s, &uc, 8)) {
 830                                 retVal = BZ_OK;
 831                                 goto save_state_and_return;
 832                         }
 833                         s->origPtr = (s->origPtr << 8) | ((int)uc);
 834
 835                         if (s->origPtr < 0) {
 836                                 retVal = BZ_DATA_ERROR;
 837                                 goto save_state_and_return;
 838                         }
 839                         if (s->origPtr > 10 + 100000*s->blockSize100k) {
 840                                 retVal = BZ_DATA_ERROR;
 841                                 goto save_state_and_return;
 842                         }
 843
 844                         /*--- Receive the mapping table ---*/
 845                 case BZ_X_MAPPING_1:
 846                         for (i = 0; i < 16; i++) {
 847                                 s->state = BZ_X_MAPPING_1;
 848                                 if (! get_bits(s, &uc, 1)) {
 849                                         retVal = BZ_OK;
 850                                         goto save_state_and_return;
 851                                 }
 852                                 if (uc == 1) {
 853                                         s->inUse16[i] = TRUE;
 854                                 } else {
 855                                         s->inUse16[i] = FALSE;
 856                                 }
 857                         }
 858
 859                         for (i = 0; i < 256; i++) {
 860                                 s->inUse[i] = FALSE;
 861                         }
 862
 863                         for (i = 0; i < 16; i++) {
 864                                 if (s->inUse16[i]) {
 865                                         for (j = 0; j < 16; j++) {
 866                                         case BZ_X_MAPPING_2:
 867                                                 s->state = BZ_X_MAPPING_2;
 868                                                 if (! get_bits(s, &uc, 1)) {
 869                                                         retVal = BZ_OK;
 870                                                         goto save_state_and_return;
 871                                                 }
 872                                                 if (uc == 1) {
 873                                                         s->inUse[i * 16 + j] = TRUE;
 874                                                 }
 875                                         }
 876                                 }
 877                         }
 878
 879                         s->nInUse = 0;
 880                         for (i = 0; i < 256; i++) {
 881                                 if (s->inUse[i]) {
 882                                         s->seqToUnseq[s->nInUse] = i;
 883                                         s->nInUse++;
 884                                 }
 885                         }
 886                         if (s->nInUse == 0) {
 887                                 retVal = BZ_DATA_ERROR;
 888                                 goto save_state_and_return;
 889                         }
 890                         alphaSize = s->nInUse+2;
 891
 892                 /*--- Now the selectors ---*/
 893                 case BZ_X_SELECTOR_1:
 894                         s->state = BZ_X_SELECTOR_1;
 895                         if (! get_bits(s, &nGroups, 3)) {
 896                                 retVal = BZ_OK;
 897                                 goto save_state_and_return;
 898                         }
 899                         if (nGroups < 2 || nGroups > 6) {
 900                                 retVal = BZ_DATA_ERROR;
 901                                 goto save_state_and_return;
 902                         }
 903
 904                 case BZ_X_SELECTOR_2:
 905                         s->state = BZ_X_SELECTOR_2;
 906                         if (! get_bits(s, &nSelectors, 15)) {
 907                                 retVal = BZ_OK;
 908                                 goto save_state_and_return;
 909                         }
 910                         if (nSelectors < 1) {
 911                                 retVal = BZ_DATA_ERROR;
 912                                 goto save_state_and_return;
 913                         }
 914
 915
 916
 917                         for (i = 0; i < nSelectors; i++) {
 918                                 j = 0;
 919                                 while (1) {
 920                                         case BZ_X_SELECTOR_3:
 921                                         s->state = BZ_X_SELECTOR_3;
 922                                         if (! get_bits(s, &uc, 1)) {
 923                                                 retVal = BZ_OK;
 924                                                 goto save_state_and_return;
 925                                         }
 926                                         if (uc == 0) {
 927                                                 break;
 928                                         }
 929                                         j++;
 930                                         if (j >= nGroups) {
 931                                                 retVal = BZ_DATA_ERROR;
 932                                                 goto save_state_and_return;
 933                                         }
 934                                 }
 935                                 s->selectorMtf[i] = j;
 936                         }
 937
 938                         /*--- Undo the MTF values for the selectors. ---*/
 939                         {
 940                                 unsigned char pos[BZ_N_GROUPS], tmp, v;
 941                                 for (v = 0; v < nGroups; v++) {
 942                                         pos[v] = v;
 943                                 }
 944                                 for (i = 0; i < nSelectors; i++) {
 945                                         v = s->selectorMtf[i];
 946                                         tmp = pos[v];
 947                                         while (v > 0) {
 948                                                 pos[v] = pos[v-1];
 949                                                 v--;
 950                                         }
 951                                         pos[0] = tmp;
 952                                         s->selector[i] = tmp;
 953                                 }
 954                         }
 955
 956                         /*--- Now the coding tables ---*/
 957                         for (t = 0; t < nGroups; t++) {
 958                         case BZ_X_CODING_1:
 959                                 s->state = BZ_X_CODING_1;
 960                                 if (! get_bits(s, &curr, 5)) {
 961                                         retVal = BZ_OK;
 962                                         goto save_state_and_return;
 963                                 }
 964                         for (i = 0; i < alphaSize; i++) {
 965                                 while (TRUE) {
 966                                         if (curr < 1 || curr > 20) {
 967                                                 retVal = BZ_DATA_ERROR;
 968                                                 goto save_state_and_return;
 969                                         }
 970
 971                                         case BZ_X_CODING_2:
 972                                                 s->state = BZ_X_CODING_2;
 973                                                 if (! get_bits(s, &uc, 1)) {
 974                                                         retVal = BZ_OK;
 975                                                         goto save_state_and_return;
 976                                                 }
 977                                                 if (uc == 0) {
 978                                                         break;
 979                                                 }
 980
 981                                         case BZ_X_CODING_3:
 982                                                 s->state = BZ_X_CODING_3;
 983                                                 if (! get_bits(s, &uc, 1)) {
 984                                                         retVal = BZ_OK;
 985                                                         goto save_state_and_return;
 986                                                 }
 987                                                 if (uc == 0) {
 988                                                         curr++;
 989                                                 } else {
 990                                                         curr--;
 991                                                 }
 992                                 }
 993                                 s->len[t][i] = curr;
 994                         }
 995                 }
 996
 997                 /*--- Create the Huffman decoding tables ---*/
 998                 for (t = 0; t < nGroups; t++) {
 999                         minLen = 32;
1000                         maxLen = 0;
1001                         for (i = 0; i < alphaSize; i++) {
1002                                 if (s->len[t][i] > maxLen) {
1003                                         maxLen = s->len[t][i];
1004                                 }
1005                                 if (s->len[t][i] < minLen) {
1006                                         minLen = s->len[t][i];
1007                                 }
1008                         }
1009
1010                         BZ2_hbCreateDecodeTables (
1011                                 &(s->limit[t][0]),
1012                                 &(s->base[t][0]),
1013                                 &(s->perm[t][0]),
1014                                 &(s->len[t][0]),
1015                                 minLen, maxLen, alphaSize
1016                                 );
1017
1018
1019                         s->minLens[t] = minLen;
1020                 }
1021
1022                 /*--- Now the MTF values ---*/
1023
1024                 EOB      = s->nInUse+1;
1025                 nblockMAX = 100000 * s->blockSize100k;
1026                 groupNo  = -1;
1027                 groupPos = 0;
1028
1029                 for (i = 0; i <= 255; i++) {
1030                         s->unzftab[i] = 0;
1031                 }
1032                 /*-- MTF init --*/
1033                 {
1034                         int ii, jj, kk;
1035                         kk = MTFA_SIZE-1;
1036                         for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
1037                                 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1038                                         s->mtfa[kk] = (unsigned char)(ii * MTFL_SIZE + jj);
1039                                         kk--;
1040                                 }
1041                                 s->mtfbase[ii] = kk + 1;
1042                         }
1043                 }
1044                 /*-- end MTF init --*/
1045
1046                 nblock = 0;
1047
1048                 if (! get_mtf_val_init()) {
1049                         goto save_state_and_return;
1050                 }
1051                 case BZ_X_MTF_1:
1052                         s->state = BZ_X_MTF_1;
1053                         if (! get_bits(s, &zvec, zn)) {
1054                                 retVal = BZ_OK;
1055                                 goto save_state_and_return;
1056                         }
1057                         while (1) {
1058                                 if (zn > 20 /* the longest code */) {
1059                                         retVal = BZ_DATA_ERROR;
1060                                         goto save_state_and_return;
1061                                 }
1062                                 if (zvec <= gLimit[zn]) {
1063                                         break;
1064                                 }
1065                                 zn++;
1066
1067                                 case BZ_X_MTF_2:
1068                                         s->state = BZ_X_MTF_2;
1069                                         if (! get_bits(s, &zj, 1)) {
1070                                                 retVal = BZ_OK;
1071                                                 goto save_state_and_return;
1072                                         }
1073                                         zvec = (zvec << 1) | zj;
1074                         }
1075                         if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1076                                 retVal = BZ_DATA_ERROR;
1077                                 goto save_state_and_return;
1078                         }
1079                         nextSym = gPerm[zvec - gBase[zn]];
1080
1081                 while (1) {
1082                         if (nextSym == EOB) {
1083                                 break;
1084                         }
1085
1086                 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
1087                         es = -1;
1088                         N = 1;
1089                         do {
1090                                 if (nextSym == BZ_RUNA) {
1091                                         es = es + (0+1) * N;
1092                                 } else {
1093                                         if (nextSym == BZ_RUNB) {
1094                                                 es = es + (1+1) * N;
1095                                         }
1096                                 }
1097                                 N = N * 2;
1098                                 if (! get_mtf_val_init()) {
1099                                         goto save_state_and_return;
1100                                 }
1101                                 case BZ_X_MTF_3:
1102                                         s->state = BZ_X_MTF_3;
1103                                         if (! get_bits(s, &zvec, zn)) {
1104                                                 retVal = BZ_OK;
1105                                                 goto save_state_and_return;
1106                                         }
1107                                         while (1) {
1108                                                 if (zn > 20 /* the longest code */) {
1109                                                         retVal = BZ_DATA_ERROR;
1110                                                         goto save_state_and_return;
1111                                                 }
1112                                                 if (zvec <= gLimit[zn]) {
1113                                                         break;
1114                                                 }
1115                                                 zn++;
1116
1117                                                 case BZ_X_MTF_4:
1118                                                         s->state = BZ_X_MTF_4;
1119                                                         if (! get_bits(s, &zj, 1)) {
1120                                                                 retVal = BZ_OK;
1121                                                                 goto save_state_and_return;
1122                                                         }
1123                                                         zvec = (zvec << 1) | zj;
1124                                         }
1125                                         if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1126                                                 retVal = BZ_DATA_ERROR;
1127                                                 goto save_state_and_return;
1128
1129                                         }
1130                                         nextSym = gPerm[zvec - gBase[zn]];
1131                         }
1132                         while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
1133
1134                         es++;
1135                         uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
1136                         s->unzftab[uc] += es;
1137
1138                         if (s->smallDecompress) {
1139                                 while (es > 0) {
1140                                         if (nblock >= nblockMAX) {
1141                                                 retVal = BZ_DATA_ERROR;
1142                                                 goto save_state_and_return;
1143                                         }
1144                                         s->ll16[nblock] = (unsigned short)uc;
1145                                         nblock++;
1146                                         es--;
1147                                 }
1148                         } else {
1149                                 while (es > 0) {
1150                                         if (nblock >= nblockMAX) {
1151                                                 retVal = BZ_DATA_ERROR;
1152                                                 goto save_state_and_return;
1153                                         }
1154                                         s->tt[nblock] = (unsigned int)uc;
1155                                         nblock++;
1156                                         es--;
1157                                 }
1158                         }
1159                         continue;
1160                 } else {
1161                         if (nblock >= nblockMAX) {
1162                                 retVal = BZ_DATA_ERROR;
1163                                 goto save_state_and_return;
1164                         }
1165                         /*-- uc = MTF ( nextSym-1 ) --*/
1166                         {
1167                                 int ii, jj, kk, pp, lno, off;
1168                                 unsigned int nn;
1169                                 nn = (unsigned int)(nextSym - 1);
1170
1171                                 if (nn < MTFL_SIZE) {
1172                                         /* avoid general-case expense */
1173                                         pp = s->mtfbase[0];
1174                                         uc = s->mtfa[pp+nn];
1175                                         while (nn > 3) {
1176                                                 int z = pp+nn;
1177                                                 s->mtfa[(z)  ] = s->mtfa[(z)-1];
1178                                                 s->mtfa[(z)-1] = s->mtfa[(z)-2];
1179                                                 s->mtfa[(z)-2] = s->mtfa[(z)-3];
1180                                                 s->mtfa[(z)-3] = s->mtfa[(z)-4];
1181                                                 nn -= 4;
1182                                         }
1183                                         while (nn > 0) {
1184                                                 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1185                                         }
1186                                         s->mtfa[pp] = uc;
1187                                 } else {
1188                                         /* general case */
1189                                         lno = nn / MTFL_SIZE;
1190                                         off = nn % MTFL_SIZE;
1191                                         pp = s->mtfbase[lno] + off;
1192                                         uc = s->mtfa[pp];
1193                                         while (pp > s->mtfbase[lno]) {
1194                                                 s->mtfa[pp] = s->mtfa[pp-1];
1195                                                 pp--;
1196                                         }
1197                                         s->mtfbase[lno]++;
1198                                         while (lno > 0) {
1199                                                 s->mtfbase[lno]--;
1200                                                 s->mtfa[s->mtfbase[lno]] = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1201                                                 lno--;
1202                                         }
1203                                         s->mtfbase[0]--;
1204                                         s->mtfa[s->mtfbase[0]] = uc;
1205                                         if (s->mtfbase[0] == 0) {
1206                                                 kk = MTFA_SIZE-1;
1207                                                 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1208                                                         for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1209                                                                 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1210                                                                 kk--;
1211                                                         }
1212                                                         s->mtfbase[ii] = kk + 1;
1213                                                 }
1214                                         }
1215                                 }
1216                         }
1217                         /*-- end uc = MTF ( nextSym-1 ) --*/
1218
1219                         s->unzftab[s->seqToUnseq[uc]]++;
1220             if (s->smallDecompress) {
1221                                 s->ll16[nblock] = (unsigned short)(s->seqToUnseq[uc]);
1222                         } else {
1223                                 s->tt[nblock]   = (unsigned int)(s->seqToUnseq[uc]);
1224                         }
1225                         nblock++;
1226
1227                         if (! get_mtf_val_init()) {
1228                                 goto save_state_and_return;
1229                         }
1230                         case BZ_X_MTF_5:
1231                                 s->state = BZ_X_MTF_5;
1232                                 if (! get_bits(s, &zvec, zn)) {
1233                                         retVal = BZ_OK;
1234                                         goto save_state_and_return;
1235                                 }
1236                                 while (1) {
1237                                         if (zn > 20 /* the longest code */) {
1238                                                 retVal = BZ_DATA_ERROR;
1239                                                 goto save_state_and_return;
1240                                         }
1241                                         if (zvec <= gLimit[zn]) {
1242                                                 break;
1243                                         }
1244                                         zn++;
1245
1246                                         case BZ_X_MTF_6:
1247                                                 s->state = BZ_X_MTF_6;
1248                                                 if (! get_bits(s, &zj, 1)) {
1249                                                         retVal = BZ_OK;
1250                                                         goto save_state_and_return;
1251                                                 }
1252                                                 zvec = (zvec << 1) | zj;
1253                                 }
1254                         if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1255                                 retVal = BZ_DATA_ERROR;
1256                                 goto save_state_and_return;
1257                         }
1258                         nextSym = gPerm[zvec - gBase[zn]];
1259                         continue;
1260                 }
1261         }
1262
1263         /* Now we know what nblock is, we can do a better sanity
1264                 check on s->origPtr.
1265         */
1266         if (s->origPtr < 0 || s->origPtr >= nblock) {
1267                 retVal = BZ_DATA_ERROR;
1268                 goto save_state_and_return;
1269         }
1270         s->state_out_len = 0;
1271         s->state_out_ch  = 0;
1272         s->calculatedBlockCRC = 0xffffffffL;
1273         s->state = BZ_X_OUTPUT;
1274         if (s->verbosity >= 2) {
1275                 error_msg("rt+rld");
1276         }
1277
1278         /*-- Set up cftab to facilitate generation of T^(-1) --*/
1279         s->cftab[0] = 0;
1280         for (i = 1; i <= 256; i++) {
1281                 s->cftab[i] = s->unzftab[i-1];
1282         }
1283         for (i = 1; i <= 256; i++) {
1284                 s->cftab[i] += s->cftab[i-1];
1285         }
1286
1287         if (s->smallDecompress) {
1288
1289                 /*-- Make a copy of cftab, used in generation of T --*/
1290                 for (i = 0; i <= 256; i++) {
1291                         s->cftabCopy[i] = s->cftab[i];
1292                 }
1293
1294                 /*-- compute the T vector --*/
1295                 for (i = 0; i < nblock; i++) {
1296                         uc = (unsigned char)(s->ll16[i]);
1297                         s->ll16[i] = (unsigned short)(s->cftabCopy[uc] & 0x0000ffff);
1298                         if (((i) & 0x1) == 0) {
1299                                 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (s->cftabCopy[uc] >> 16);
1300                         } else {
1301                                 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((s->cftabCopy[uc] >> 16) << 4);
1302                         }
1303                         s->cftabCopy[uc]++;
1304                 }
1305
1306                 /*-- Compute T^(-1) by pointer reversal on T --*/
1307                 i = s->origPtr;
1308                 j = (((unsigned int)s->ll16[i]) |
1309                         (((((unsigned int)(s->ll4[(i) >> 1])) >>
1310                         (((i) << 2) & 0x4)) & 0xF) << 16));
1311
1312                 do {
1313                         const int tmp = (((unsigned int)s->ll16[j]) |
1314                                 (((((unsigned int)(s->ll4[(j) >> 1])) >>
1315                                 (((j) << 2) & 0x4)) & 0xF) << 16));
1316
1317                         s->ll16[j] = (unsigned short)(i & 0x0000ffff);
1318                         if (((j) & 0x1) == 0) {
1319                                 s->ll4[(j) >> 1] = (s->ll4[(j) >> 1] & 0xf0) | (i >> 16);
1320                         } else {
1321                                 s->ll4[(j) >> 1] = (s->ll4[(j) >> 1] & 0x0f) | ((i >> 16) << 4);
1322                         }
1323                         i = j;
1324                         j = tmp;
1325                 }
1326                 while (i != s->origPtr);
1327                         s->tPos = s->origPtr;
1328                         s->nblock_used = 0;
1329                         if (s->blockRandomised) {
1330                                 s->rNToGo = 0;
1331                                 s->rTPos  = 0;
1332                                 s->k0 = bz_get_small(s);
1333                                 s->nblock_used++;
1334                                 bz_rand_udp_mask(s);
1335                                 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1336                         } else {
1337                                 s->k0 = bz_get_small(s);
1338                                 s->nblock_used++;
1339                         }
1340                 } else {
1341                         /*-- compute the T^(-1) vector --*/
1342                         for (i = 0; i < nblock; i++) {
1343                                 uc = (unsigned char)(s->tt[i] & 0xff);
1344                                 s->tt[s->cftab[uc]] |= (i << 8);
1345                                 s->cftab[uc]++;
1346                         }
1347
1348                         s->tPos = s->tt[s->origPtr] >> 8;
1349                         s->nblock_used = 0;
1350                         if (s->blockRandomised) {
1351                                 s->rNToGo = 0;
1352                                 s->rTPos  = 0;
1353                                 s->k0 = bz_get_fast(s);
1354
1355                                 s->nblock_used++;
1356                                 bz_rand_udp_mask(s);
1357                                 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1358                         } else {
1359                                 s->k0 = bz_get_fast(s);
1360                                 s->nblock_used++;
1361                         }
1362                 }
1363
1364                 retVal = BZ_OK;
1365                 goto save_state_and_return;
1366
1367 endhdr_2:
1368                 case BZ_X_ENDHDR_2:
1369                         s->state = BZ_X_ENDHDR_2;
1370                         if (! get_bits(s, &uc, 8)) {
1371                                 retVal = BZ_OK;
1372                                 goto save_state_and_return;
1373                         }
1374                         if (uc != 0x72) {
1375                                 retVal = BZ_DATA_ERROR;
1376                                 goto save_state_and_return;
1377                         }
1378
1379                 case BZ_X_ENDHDR_3:
1380                         s->state = BZ_X_ENDHDR_3;
1381                         if (! get_bits(s, &uc, 8)) {
1382                                 retVal = BZ_OK;
1383                                 goto save_state_and_return;
1384                         }
1385                         if (uc != 0x45) {
1386                                 retVal = BZ_DATA_ERROR;
1387                                 goto save_state_and_return;
1388                         }
1389
1390                 case BZ_X_ENDHDR_4:
1391                         s->state = BZ_X_ENDHDR_4;
1392                         if (! get_bits(s, &uc, 8)) {
1393                                 retVal = BZ_OK;
1394                                 goto save_state_and_return;
1395                         }
1396                         if (uc != 0x38) {
1397                                 retVal = BZ_DATA_ERROR;
1398                                 goto save_state_and_return;
1399                         }
1400
1401                 case BZ_X_ENDHDR_5:
1402                         s->state = BZ_X_ENDHDR_5;
1403                         if (! get_bits(s, &uc, 8)) {
1404                                 retVal = BZ_OK;
1405                                 goto save_state_and_return;
1406                         }
1407                         if (uc != 0x50) {
1408                                 retVal = BZ_DATA_ERROR;
1409                                 goto save_state_and_return;
1410                         }
1411
1412                 case BZ_X_ENDHDR_6:
1413                         s->state = BZ_X_ENDHDR_6;
1414                         if (! get_bits(s, &uc, 8)) {
1415                                 retVal = BZ_OK;
1416                                 goto save_state_and_return;
1417                         }
1418                         if (uc != 0x90) {
1419                                 retVal = BZ_DATA_ERROR;
1420                                 goto save_state_and_return;
1421                         }
1422                         s->storedCombinedCRC = 0;
1423
1424                 case BZ_X_CCRC_1:
1425                         s->state = BZ_X_CCRC_1;
1426                         if (! get_bits(s, &uc, 8)) {
1427                                 retVal = BZ_OK;
1428                                 goto save_state_and_return;
1429                         }
1430                         s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1431                 case BZ_X_CCRC_2:
1432                         s->state = BZ_X_CCRC_2;
1433                         if (! get_bits(s, &uc, 8)) {
1434                                 retVal = BZ_OK;
1435                                 goto save_state_and_return;
1436                         }
1437                         s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1438
1439                 case BZ_X_CCRC_3:
1440                         s->state = BZ_X_CCRC_3;
1441                         if (! get_bits(s, &uc, 8)) {
1442                                 retVal = BZ_OK;
1443                                 goto save_state_and_return;
1444                         }
1445                         s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1446
1447                 case BZ_X_CCRC_4:
1448                         s->state = BZ_X_CCRC_4;
1449                         if (! get_bits(s, &uc, 8)) {
1450                                 retVal = BZ_OK;
1451                                 goto save_state_and_return;
1452                         }
1453                         s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1454
1455                 s->state = BZ_X_IDLE;
1456                 retVal = BZ_STREAM_END;
1457                 goto save_state_and_return;
1458
1459 default:
1460                 printf("switch val is %d\n", switch_val);
1461                 assert_h(4001);
1462         }
1463
1464         assert_h(4002);
1465
1466 save_state_and_return:
1467         s->save_i           = i;
1468         s->save_j           = j;
1469         s->save_t           = t;
1470         s->save_alphaSize   = alphaSize;
1471         s->save_nGroups     = nGroups;
1472         s->save_nSelectors  = nSelectors;
1473         s->save_EOB         = EOB;
1474         s->save_groupNo     = groupNo;
1475         s->save_groupPos    = groupPos;
1476         s->save_nextSym     = nextSym;
1477         s->save_nblockMAX   = nblockMAX;
1478         s->save_nblock      = nblock;
1479         s->save_es          = es;
1480         s->save_N           = N;
1481         s->save_curr        = curr;
1482         s->save_zt          = zt;
1483         s->save_zn          = zn;
1484         s->save_zvec        = zvec;
1485         s->save_zj          = zj;
1486         s->save_gSel        = gSel;
1487         s->save_gMinlen     = gMinlen;
1488         s->save_gLimit      = gLimit;
1489         s->save_gBase       = gBase;
1490         s->save_gPerm       = gPerm;
1491
1492         return retVal;
1493 }
1494
1495 static void *default_bzalloc(void *opaque, int items, int size)
1496 {
1497         void *v = xmalloc(items *size);
1498         return v;
1499 }
1500
1501 static void default_bzfree(void *opaque, void *addr)
1502 {
1503         if (addr != NULL) {
1504                 free(addr);
1505         }
1506 }
1507
1508 //int BZ2_bzDecompressInit(bz_stream* strm, int verbosity_level, int small)
1509 int BZ2_bzDecompressInit(bz_stream* strm, int small)
1510 {
1511         DState* s;
1512
1513         if (sizeof(int) != 4) {
1514                 return BZ_CONFIG_ERROR;
1515         }
1516         if (sizeof(short) != 2) {
1517                 return BZ_CONFIG_ERROR;
1518         }
1519         if (sizeof(char) != 1) {
1520                 return BZ_CONFIG_ERROR;
1521         }
1522         if (strm == NULL) {
1523                 return BZ_PARAM_ERROR;
1524         }
1525         if (small != 0 && small != 1) {
1526                 return BZ_PARAM_ERROR;
1527         }
1528 //      if (verbosity_level < 0 || verbosity_level > 4) {
1529 //              return BZ_PARAM_ERROR;
1530 //      }
1531         if (strm->bzalloc == NULL) {
1532                 strm->bzalloc = default_bzalloc;
1533         }
1534         if (strm->bzfree == NULL) {
1535                 strm->bzfree = default_bzfree;
1536         }
1537         s = (strm->bzalloc)(strm->opaque, sizeof(DState), 1);
1538         if (s == NULL) {
1539                 return BZ_MEM_ERROR;
1540         }
1541         s->strm                  = strm;
1542         strm->state              = s;
1543         s->state                 = BZ_X_MAGIC_1;
1544         s->bsLive                = 0;
1545         s->bsBuff                = 0;
1546         s->calculatedCombinedCRC = 0;
1547         strm->total_in_lo32      = 0;
1548         strm->total_in_hi32      = 0;
1549         strm->total_out_lo32     = 0;
1550         strm->total_out_hi32     = 0;
1551         s->smallDecompress       = (unsigned char)small;
1552         s->ll4                   = NULL;
1553         s->ll16                  = NULL;
1554         s->tt                    = NULL;
1555         s->currBlockNo           = 0;
1556 //      s->verbosity             = verbosity_level;
1557
1558         return BZ_OK;
1559 }
1560
1561 void bz_seterr(int eee, int *bzerror, bzFile **bzf)
1562 {
1563         if (bzerror != NULL) {
1564                 *bzerror = eee;
1565         }
1566         if (*bzf != NULL) {
1567                 (*bzf)->lastErr = eee;
1568         }
1569 }
1570
1571 void BZ2_bzReadClose(int *bzerror, void *b)
1572 {
1573         bzFile* bzf = (bzFile*)b;
1574
1575         bz_seterr(BZ_OK, bzerror, &bzf);
1576         if (bzf == NULL) {
1577                 bz_seterr(BZ_OK, bzerror, &bzf);
1578                 return;
1579         }
1580
1581         if (bzf->writing) {
1582                 bz_seterr(BZ_SEQUENCE_ERROR, bzerror, &bzf);
1583                 return;
1584         }
1585
1586         if (bzf->initialisedOk) {
1587                 bz_stream *strm = &(bzf->strm);
1588                 DState *s;
1589                 if (strm == NULL) {
1590                         return;
1591                 }
1592                 s = strm->state;
1593                 if ((s == NULL) || (s->strm != strm)) {
1594                         return;
1595                 }
1596                 if (s->tt != NULL) {
1597                         (strm->bzfree)(strm->opaque,(s->tt));
1598                 }
1599                 if (s->ll16 != NULL) {
1600                         (strm->bzfree)(strm->opaque,(s->ll16));
1601                 }
1602                 if (s->ll4 != NULL) {
1603                         (strm->bzfree)(strm->opaque,(s->ll4));
1604                 }
1605                 (strm->bzfree)(strm->opaque,(strm->state));
1606                 strm->state = NULL;
1607                 return;
1608         }
1609         free(bzf);
1610 }
1611
1612 static void unRLE_obuf_to_output_FAST(DState *s)
1613 {
1614         unsigned char k1;
1615
1616         if (s->blockRandomised) {
1617                 while (1) {
1618                         /* try to finish existing run */
1619                         while (1) {
1620                                 if (s->strm->avail_out == 0) {
1621                                         return;
1622                                 }
1623                                 if (s->state_out_len == 0) {
1624                                         break;
1625                                 }
1626                                 *((unsigned char *)(s->strm->next_out)) = s->state_out_ch;
1627                                 s->calculatedBlockCRC = (s->calculatedBlockCRC << 8) ^
1628                                         BZ2_crc32Table[(s->calculatedBlockCRC >> 24) ^
1629                                         ((unsigned char)s->state_out_ch)];
1630                                 s->state_out_len--;
1631                                 s->strm->next_out++;
1632                                 s->strm->avail_out--;
1633                                 s->strm->total_out_lo32++;
1634                                 if (s->strm->total_out_lo32 == 0) {
1635                                         s->strm->total_out_hi32++;
1636                                 }
1637                         }
1638
1639                         /* can a new run be started? */
1640                         if (s->nblock_used == s->save_nblock+1) {
1641                                 return;
1642                         }
1643                         s->state_out_len = 1;
1644                         s->state_out_ch = s->k0;
1645                         k1 = bz_get_fast(s);
1646                         bz_rand_udp_mask(s);
1647                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1648                         s->nblock_used++;
1649                         if (s->nblock_used == s->save_nblock+1) {
1650                                 continue;
1651                         }
1652                         if (k1 != s->k0) {
1653                                 s->k0 = k1;
1654                                 continue;
1655                         }
1656
1657                         s->state_out_len = 2;
1658                         k1 = bz_get_fast(s);
1659                         bz_rand_udp_mask(s);
1660                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1661                         s->nblock_used++;
1662                         if (s->nblock_used == s->save_nblock+1) {
1663                                 continue;
1664                         }
1665                         if (k1 != s->k0) {
1666                                 s->k0 = k1;
1667                                 continue;
1668                         }
1669                         s->state_out_len = 3;
1670                         k1 = bz_get_fast(s);
1671                         bz_rand_udp_mask(s);
1672                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1673                         s->nblock_used++;
1674                         if (s->nblock_used == s->save_nblock+1) {
1675                                 continue;
1676                         }
1677                         if (k1 != s->k0) {
1678                                 s->k0 = k1;
1679                                 continue;
1680                         }
1681
1682                         k1 = bz_get_fast(s);
1683                         bz_rand_udp_mask(s);
1684                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1685                         s->nblock_used++;
1686                         s->state_out_len = ((int)k1) + 4;
1687                         s->k0 = bz_get_fast(s);
1688                         bz_rand_udp_mask(s);
1689                         s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1690                         s->nblock_used++;
1691                 }
1692         } else {
1693                 /* restore */
1694                 unsigned int c_calculatedBlockCRC = s->calculatedBlockCRC;
1695                 unsigned char c_state_out_ch       = s->state_out_ch;
1696                 int c_state_out_len      = s->state_out_len;
1697                 int c_nblock_used        = s->nblock_used;
1698                 int c_k0                 = s->k0;
1699                 unsigned int    *c_tt                 = s->tt;
1700                 unsigned int    c_tPos               = s->tPos;
1701                 char    *cs_next_out          = s->strm->next_out;
1702                 unsigned int  cs_avail_out         = s->strm->avail_out;
1703                 /* end restore */
1704
1705                 unsigned int avail_out_INIT = cs_avail_out;
1706                 int        s_save_nblockPP = s->save_nblock+1;
1707                 unsigned int total_out_lo32_old;
1708
1709                 while (1) {
1710                         /* try to finish existing run */
1711                         if (c_state_out_len > 0) {
1712                                 while (TRUE) {
1713                                         if (cs_avail_out == 0) {
1714                                                 goto return_notr;
1715                                         }
1716                                         if (c_state_out_len == 1) {
1717                                                 break;
1718                                         }
1719                                         *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1720                                         c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1721                                                 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1722                                                 ((unsigned char)c_state_out_ch)];
1723                                         c_state_out_len--;
1724                                         cs_next_out++;
1725                                         cs_avail_out--;
1726                                 }
1727 s_state_out_len_eq_one:
1728                                 {
1729                                         if (cs_avail_out == 0) {
1730                                                 c_state_out_len = 1;
1731                                                 goto return_notr;
1732                                         }
1733                                         *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1734                                         c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1735                                                 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1736                                                 ((unsigned char)c_state_out_ch)];
1737                                         cs_next_out++;
1738                                         cs_avail_out--;
1739                                 }
1740                         }
1741                         /* can a new run be started? */
1742                         if (c_nblock_used == s_save_nblockPP) {
1743                                 c_state_out_len = 0; goto return_notr;
1744                         }
1745                         c_state_out_ch = c_k0;
1746                         c_tPos = c_tt[c_tPos];
1747                         k1 = (unsigned char)(c_tPos & 0xff);
1748                         c_tPos >>= 8;
1749
1750                         c_nblock_used++;
1751
1752                         if (k1 != c_k0) {
1753                                 c_k0 = k1;
1754                                 goto s_state_out_len_eq_one;
1755                         }
1756
1757                         if (c_nblock_used == s_save_nblockPP) {
1758                                 goto s_state_out_len_eq_one;
1759                         }
1760
1761                         c_state_out_len = 2;
1762                         c_tPos = c_tt[c_tPos];
1763                         k1 = (unsigned char)(c_tPos & 0xff);
1764                         c_tPos >>= 8;
1765
1766                         c_nblock_used++;
1767                         if (c_nblock_used == s_save_nblockPP) {
1768                                 continue;
1769                         }
1770                         if (k1 != c_k0) {
1771                                 c_k0 = k1;
1772                                 continue;
1773                         }
1774
1775                         c_state_out_len = 3;
1776                         c_tPos = c_tt[c_tPos];
1777                         k1 = (unsigned char)(c_tPos & 0xff);
1778                         c_tPos >>= 8;
1779
1780                         c_nblock_used++;
1781                         if (c_nblock_used == s_save_nblockPP) {
1782                                 continue;
1783                         }
1784                         if (k1 != c_k0) {
1785                                 c_k0 = k1;
1786                                 continue;
1787                         }
1788
1789                         c_tPos = c_tt[c_tPos];
1790                         k1 = (unsigned char)(c_tPos & 0xff);
1791                         c_tPos >>= 8;
1792
1793                         c_nblock_used++;
1794                         c_state_out_len = ((int)k1) + 4;
1795
1796                         c_tPos = c_tt[c_tPos];
1797                         c_k0 = (unsigned char)(c_tPos & 0xff);
1798                         c_tPos >>= 8;
1799
1800                         c_nblock_used++;
1801                 }
1802
1803 return_notr:
1804                 total_out_lo32_old = s->strm->total_out_lo32;
1805                 s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
1806                 if (s->strm->total_out_lo32 < total_out_lo32_old) {
1807                         s->strm->total_out_hi32++;
1808                 }
1809
1810                 /* save */
1811                 s->calculatedBlockCRC = c_calculatedBlockCRC;
1812                 s->state_out_ch       = c_state_out_ch;
1813                 s->state_out_len      = c_state_out_len;
1814                 s->nblock_used        = c_nblock_used;
1815                 s->k0                 = c_k0;
1816                 s->tt                 = c_tt;
1817                 s->tPos               = c_tPos;
1818                 s->strm->next_out     = cs_next_out;
1819                 s->strm->avail_out    = cs_avail_out;
1820                 /* end save */
1821         }
1822 }
1823
1824 static void unRLE_obuf_to_output_SMALL(DState *s)
1825 {
1826         unsigned char k1;
1827
1828         if (s->blockRandomised) {
1829                 while (1) {
1830                         /* try to finish existing run */
1831                         while (1) {
1832                                 if (s->strm->avail_out == 0) {
1833                                         return;
1834                                 }
1835                                 if (s->state_out_len == 0) {
1836                                         break;
1837                                 }
1838                                 *((unsigned char *)(s->strm->next_out)) = s->state_out_ch;
1839                                 s->calculatedBlockCRC = (s->calculatedBlockCRC << 8) ^
1840                                         BZ2_crc32Table[(s->calculatedBlockCRC >> 24) ^
1841                                         ((unsigned char)s->state_out_ch)];
1842                                 s->state_out_len--;
1843                                 s->strm->next_out++;
1844                                 s->strm->avail_out--;
1845                                 s->strm->total_out_lo32++;
1846                                 if (s->strm->total_out_lo32 == 0) {
1847                                         s->strm->total_out_hi32++;
1848                                 }
1849                         }
1850
1851                         /* can a new run be started? */
1852                         if (s->nblock_used == s->save_nblock+1) {
1853                                 return;
1854                         }
1855
1856                         s->state_out_len = 1;
1857                         s->state_out_ch = s->k0;
1858                         k1 = bz_get_small(s);
1859                         bz_rand_udp_mask(s);
1860                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1861                         s->nblock_used++;
1862                         if (s->nblock_used == s->save_nblock+1) {
1863                                 continue;
1864                         }
1865                         if (k1 != s->k0) {
1866                                 s->k0 = k1;
1867                                 continue;
1868                         }
1869
1870                         s->state_out_len = 2;
1871                         k1 = bz_get_small(s);
1872                         bz_rand_udp_mask(s);
1873                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1874                         s->nblock_used++;
1875                         if (s->nblock_used == s->save_nblock+1) {
1876                                 continue;
1877                         }
1878                         if (k1 != s->k0) {
1879                                 s->k0 = k1;
1880                                 continue;
1881                         }
1882
1883                         s->state_out_len = 3;
1884                         k1 = bz_get_small(s);
1885                         bz_rand_udp_mask(s);
1886                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1887                         s->nblock_used++;
1888                         if (s->nblock_used == s->save_nblock+1) {
1889                                 continue;
1890                         }
1891                         if (k1 != s->k0) {
1892                                 s->k0 = k1;
1893                                 continue;
1894                         }
1895                         k1 = bz_get_small(s);
1896                         bz_rand_udp_mask(s);
1897                         k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1898                         s->nblock_used++;
1899                         s->state_out_len = ((int)k1) + 4;
1900                         s->k0 = bz_get_small(s);
1901                         bz_rand_udp_mask(s);
1902                         s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1903                         s->nblock_used++;
1904                 }
1905         } else {
1906                 while (1) {
1907                         /* try to finish existing run */
1908                         while (1) {
1909                                 if (s->strm->avail_out == 0) {
1910                                         return;
1911                                 }
1912                                 if (s->state_out_len == 0) {
1913                                         break;
1914                                 }
1915                                 *((unsigned char *)(s->strm->next_out)) = s->state_out_ch;
1916                                 s->calculatedBlockCRC = (s->calculatedBlockCRC << 8) ^
1917                                         BZ2_crc32Table[(s->calculatedBlockCRC >> 24) ^
1918                                         ((unsigned char)s->state_out_ch)];
1919                                 s->state_out_len--;
1920                                 s->strm->next_out++;
1921                                 s->strm->avail_out--;
1922                                 s->strm->total_out_lo32++;
1923                                 if (s->strm->total_out_lo32 == 0) {
1924                                         s->strm->total_out_hi32++;
1925                                 }
1926                         }
1927
1928                         /* can a new run be started? */
1929                         if (s->nblock_used == s->save_nblock+1) {
1930                                 return;
1931                         }
1932
1933                         s->state_out_len = 1;
1934                         s->state_out_ch = s->k0;
1935                         k1 = bz_get_small(s);
1936                         s->nblock_used++;
1937                         if (s->nblock_used == s->save_nblock+1) {
1938                                 continue;
1939                         }
1940                         if (k1 != s->k0) {
1941                                 s->k0 = k1;
1942                                 continue;
1943                         }
1944
1945                         s->state_out_len = 2;
1946                         k1 = bz_get_small(s);
1947                         s->nblock_used++;
1948                         if (s->nblock_used == s->save_nblock+1) {
1949                                 continue;
1950                         }
1951                         if (k1 != s->k0) {
1952                                 s->k0 = k1;
1953                                 continue;
1954                         }
1955
1956                         s->state_out_len = 3;
1957                         k1 = bz_get_small(s);
1958                         s->nblock_used++;
1959                         if (s->nblock_used == s->save_nblock+1) {
1960                                 continue;
1961                         }
1962                         if (k1 != s->k0) {
1963                                 s->k0 = k1;
1964                                 continue;
1965                         }
1966
1967                         k1 = bz_get_small(s);
1968                         s->nblock_used++;
1969                         s->state_out_len = ((int)k1) + 4;
1970                         s->k0 = bz_get_small(s);
1971                         s->nblock_used++;
1972                 }
1973         }
1974 }
1975
1976 int BZ2_bzDecompress(bz_stream *strm)
1977 {
1978         DState* s;
1979         if (strm == NULL) {
1980                 return BZ_PARAM_ERROR;
1981         }
1982         s = strm->state;
1983         if (s == NULL) {
1984                 return BZ_PARAM_ERROR;
1985         }
1986         if (s->strm != strm) {
1987                 return BZ_PARAM_ERROR;
1988         }
1989
1990         while (1) {
1991                 if (s->state == BZ_X_IDLE) {
1992                         return BZ_SEQUENCE_ERROR;
1993                 }
1994                 if (s->state == BZ_X_OUTPUT) {
1995                         if (s->smallDecompress) {
1996                                 unRLE_obuf_to_output_SMALL(s);
1997                         } else {
1998                                 unRLE_obuf_to_output_FAST(s);
1999                         }
2000                         if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
2001                                 s->calculatedBlockCRC = ~(s->calculatedBlockCRC);
2002                                 if (s->verbosity >= 3) {
2003                                         error_msg("{0x%x, 0x%x}", s->storedBlockCRC, s->calculatedBlockCRC);
2004                                 }
2005                                 if (s->verbosity >= 2) {
2006                                         error_msg("]");
2007                                 }
2008                                 if (s->calculatedBlockCRC != s->storedBlockCRC) {
2009                                         return BZ_DATA_ERROR;
2010                                 }
2011                                 s->calculatedCombinedCRC = (s->calculatedCombinedCRC << 1) | (s->calculatedCombinedCRC >> 31);
2012                                 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
2013                                 s->state = BZ_X_BLKHDR_1;
2014                         } else {
2015                                 return BZ_OK;
2016                         }
2017                 }
2018                 if (s->state >= BZ_X_MAGIC_1) {
2019                         int r = BZ2_decompress(s);
2020                         if (r == BZ_STREAM_END) {
2021                                 if (s->verbosity >= 3) {
2022                                         error_msg("\n    combined CRCs: stored = 0x%x, computed = 0x%x",
2023                           s->storedCombinedCRC, s->calculatedCombinedCRC );
2024                                 }
2025                                 if (s->calculatedCombinedCRC != s->storedCombinedCRC) {
2026                                         return BZ_DATA_ERROR;
2027                                 }
2028                                 return r;
2029                         }
2030                         if (s->state != BZ_X_OUTPUT) {
2031                                 return r;
2032                         }
2033                 }
2034         }
2035
2036         assert_h(6001);
2037
2038         return(0);  /*NOTREACHED*/
2039 }
2040
2041 int BZ2_bzRead(int *bzerror, void *b, void *buf, int len)
2042 {
2043         int n, ret;
2044         bzFile *bzf = (bzFile*)b;
2045
2046         bz_seterr(BZ_OK, bzerror, &bzf);
2047
2048         if (bzf == NULL || buf == NULL || len < 0) {
2049                 bz_seterr(BZ_PARAM_ERROR, bzerror, &bzf);
2050                 return 0;
2051         }
2052
2053         if (bzf->writing) {
2054                 bz_seterr(BZ_SEQUENCE_ERROR, bzerror, &bzf);
2055                 return 0;
2056         }
2057
2058         if (len == 0) {
2059                 bz_seterr(BZ_OK, bzerror, &bzf);
2060                 return 0;
2061         }
2062
2063         bzf->strm.avail_out = len;
2064         bzf->strm.next_out = buf;
2065
2066         while (1) {
2067                 if (ferror(bzf->handle)) {
2068                         bz_seterr(BZ_IO_ERROR, bzerror, &bzf);
2069                         return 0;
2070                 }
2071                 if ((bzf->strm.avail_in == 0) && !myfeof(bzf->handle)) {
2072                         n = fread(bzf->buf, sizeof(unsigned char), BZ_MAX_UNUSED, bzf->handle);
2073                         if (ferror(bzf->handle)) {
2074                                 bz_seterr(BZ_IO_ERROR, bzerror, &bzf);
2075                                 return 0;
2076                         }
2077                         bzf->bufN = n;
2078                         bzf->strm.avail_in = bzf->bufN;
2079                         bzf->strm.next_in = bzf->buf;
2080                 }
2081
2082                 ret = BZ2_bzDecompress(&(bzf->strm));
2083
2084                 if ((ret != BZ_OK) && (ret != BZ_STREAM_END)) {
2085                         bz_seterr(ret, bzerror, &bzf);
2086                         return 0;
2087                 }
2088
2089                 if ((ret == BZ_OK) && myfeof(bzf->handle) &&
2090                         (bzf->strm.avail_in == 0) && (bzf->strm.avail_out > 0)) {
2091                         bz_seterr(BZ_UNEXPECTED_EOF, bzerror, &bzf);
2092                         return(0);
2093                 }
2094
2095                 if (ret == BZ_STREAM_END) {
2096                         bz_seterr(BZ_STREAM_END, bzerror, &bzf);
2097                         return(len - bzf->strm.avail_out);
2098                 }
2099                 if (bzf->strm.avail_out == 0) {
2100                         bz_seterr(BZ_OK, bzerror, &bzf);
2101                         return(len);
2102                 }
2103         }
2104         return(0); /*not reached*/
2105 }
2106
2107 void BZ2_bzReadGetUnused(int *bzerror, void *b, void **unused, int *nUnused)
2108 {
2109         bzFile *bzf = (bzFile*)b;
2110         if (bzf == NULL) {
2111                 bz_seterr(BZ_PARAM_ERROR, bzerror, &bzf);
2112                 return;
2113         }
2114         if (bzf->lastErr != BZ_STREAM_END) {
2115                 bz_seterr(BZ_SEQUENCE_ERROR, bzerror, &bzf);
2116                 return;
2117         }
2118         if (unused == NULL || nUnused == NULL) {
2119                 bz_seterr(BZ_PARAM_ERROR, bzerror, &bzf);
2120                 return;
2121         }
2122
2123         bz_seterr(BZ_OK, bzerror, &bzf);
2124         *nUnused = bzf->strm.avail_in;
2125         *unused = bzf->strm.next_in;
2126 }
2127
2128 void *BZ2_bzReadOpen(int *bzerror, FILE *f, int small, void *unused, int nUnused)
2129 {
2130         bzFile *bzf = NULL;
2131         int ret;
2132
2133         bz_seterr(BZ_OK, bzerror, &bzf);
2134
2135         if (f == NULL || (small != 0 && small != 1) ||
2136                 (unused != NULL && (nUnused < 0 || nUnused > BZ_MAX_UNUSED)) ||
2137 //              (verbosity_level < 0 || verbosity_level > 4) ||
2138                 (unused == NULL && nUnused != 0)) {
2139                 bz_seterr(BZ_PARAM_ERROR, bzerror, &bzf);
2140                 return NULL;
2141         }
2142
2143         if (ferror(f)) {
2144                 bz_seterr(BZ_IO_ERROR, bzerror, &bzf);
2145                 return NULL;
2146         }
2147
2148         bzf = xmalloc(sizeof(bzFile));
2149         if (bzf == NULL) {
2150                 bz_seterr(BZ_MEM_ERROR, bzerror, &bzf);
2151                 return NULL;
2152         }
2153         bz_seterr(BZ_OK, bzerror, &bzf);
2154
2155         bzf->initialisedOk = FALSE;
2156         bzf->handle        = f;
2157         bzf->bufN          = 0;
2158         bzf->writing       = FALSE;
2159         bzf->strm.bzalloc  = NULL;
2160         bzf->strm.bzfree   = NULL;
2161         bzf->strm.opaque   = NULL;
2162
2163         while (nUnused > 0) {
2164                 bzf->buf[bzf->bufN] = *((unsigned char *)(unused)); bzf->bufN++;
2165                 unused = ((void *)( 1 + ((unsigned char *)(unused))  ));
2166                 nUnused--;
2167         }
2168
2169         ret = BZ2_bzDecompressInit(&(bzf->strm), small);
2170         if (ret != BZ_OK) {
2171                 bz_seterr(ret, bzerror, &bzf);
2172                 free(bzf);
2173                 return NULL;
2174         }
2175
2176         bzf->strm.avail_in = bzf->bufN;
2177         bzf->strm.next_in  = bzf->buf;
2178
2179         bzf->initialisedOk = TRUE;
2180         return bzf;
2181 }
2182
2183 static unsigned char uncompressStream(FILE *zStream, FILE *stream)
2184 {
2185         unsigned char unused[BZ_MAX_UNUSED];
2186         unsigned char *unusedTmp;
2187         unsigned char obuf[5000];
2188         void *bzf = NULL;
2189         int bzerr_dummy;
2190         int bzerr;
2191         int nread;
2192         int nUnused;
2193         int streamNo;
2194         int ret;
2195         int i;
2196
2197         nUnused = 0;
2198         streamNo = 0;
2199
2200         if (ferror(stream)) {
2201                 goto errhandler_io;
2202         }
2203         if (ferror(zStream)) {
2204                 goto errhandler_io;
2205         }
2206
2207         while(1) {
2208                 bzf = BZ2_bzReadOpen(&bzerr, zStream, (int)smallMode, unused, nUnused);
2209                 if (bzf == NULL || bzerr != BZ_OK) {
2210                         goto errhandler;
2211                 }
2212                 streamNo++;
2213
2214                 while (bzerr == BZ_OK) {
2215                         nread = BZ2_bzRead(&bzerr, bzf, obuf, 5000);
2216                         if (bzerr == BZ_DATA_ERROR_MAGIC) {
2217                                 goto errhandler;
2218                         }
2219                         if ((bzerr == BZ_OK || bzerr == BZ_STREAM_END) && nread > 0) {
2220                                 fwrite(obuf, sizeof(unsigned char), nread, stream);
2221                         }
2222                         if (ferror(stream)) {
2223                                 goto errhandler_io;
2224                         }
2225                 }
2226                 if (bzerr != BZ_STREAM_END) {
2227                         goto errhandler;
2228                 }
2229                 BZ2_bzReadGetUnused(&bzerr, bzf, (void **)(&unusedTmp), &nUnused);
2230                 if (bzerr != BZ_OK) {
2231                         panic("decompress:bzReadGetUnused");
2232                 }
2233                 for (i = 0; i < nUnused; i++) {
2234                         unused[i] = unusedTmp[i];
2235                 }
2236                 BZ2_bzReadClose(&bzerr, bzf);
2237                 if (bzerr != BZ_OK) {
2238                         panic("decompress:bzReadGetUnused");
2239                 }
2240                 if ((nUnused == 0) && myfeof(zStream)) {
2241                         break;
2242                 }
2243         }
2244
2245         if (ferror(zStream)) {
2246                 goto errhandler_io;
2247         }
2248         ret = fclose(zStream);
2249         if (ret == EOF) {
2250                 goto errhandler_io;
2251         }
2252         if (ferror(stream)) {
2253                 goto errhandler_io;
2254         }
2255         ret = fflush(stream);
2256         if (ret != 0) {
2257                 goto errhandler_io;
2258         }
2259         if (stream != stdout) {
2260                 ret = fclose(stream);
2261                 if (ret == EOF) {
2262                         goto errhandler_io;
2263                 }
2264         }
2265 //      if (verbosity_level >= 2) {
2266 //              fprintf(stderr,"\n    ");
2267 //      }
2268         return TRUE;
2269
2270 errhandler:
2271         BZ2_bzReadClose ( &bzerr_dummy, bzf );
2272         switch (bzerr) {
2273                 case BZ_CONFIG_ERROR:
2274                         error_msg("bzip2: I'm not configured correctly for this platform!\n"
2275                                 "\tI require Int32, Int16 and Char to have sizes\n"
2276                                 "\tof 4, 2 and 1 bytes to run properly, and they don't.\n"
2277                                 "\tProbably you can fix this by defining them correctly,\n"
2278                                 "\tand recompiling.  Bye!\n" );
2279                         exit(3);
2280                 case BZ_IO_ERROR:
2281 errhandler_io:
2282                         error_msg("\n%s: I/O or other error, bailing out.  "
2283                                 "Possible reason follows.\n", progName);
2284                         perror(progName);
2285                         cleanUpAndFail(1);
2286                 case BZ_DATA_ERROR:
2287                         error_msg("\n%s: Data integrity error when decompressing.\n", progName);
2288                         cleanUpAndFail(2);
2289                 case BZ_MEM_ERROR:
2290                         error_msg("\n%s: couldn't allocate enough memory\n", progName);
2291                         cleanUpAndFail(1);
2292                 case BZ_UNEXPECTED_EOF:
2293                         error_msg("\n%s: Compressed file ends unexpectedly;\n\t"
2294                                 "perhaps it is corrupted?  *Possible* reason follows.\n", progName);
2295                         perror(progName);
2296                         cleanUpAndFail(2);
2297                 case BZ_DATA_ERROR_MAGIC:
2298                         if (zStream != stdin) {
2299                                 fclose(zStream);
2300                         }
2301                         if (stream != stdout) {
2302                                 fclose(stream);
2303                         }
2304                         if (streamNo == 1) {
2305                                 return FALSE;
2306                         } else {
2307                                 if (noisy) {
2308                                         error_msg("\n%s: %s: trailing garbage after EOF ignored\n", progName, inName );
2309                                 }
2310                                 return TRUE;
2311                         }
2312                 default:
2313                         panic ( "decompress:unexpected error" );
2314         }
2315
2316         panic("decompress:end");
2317         return(TRUE); /*notreached*/
2318 }
2319
2320 int bunzip2_main(int argc, char **argv)
2321 {
2322         const int bunzip_to_stdout = 1;
2323         const int bunzip_force = 2;
2324         int flags = 0;
2325         int opt = 0;
2326         int status;
2327
2328         FILE *src_stream;
2329         FILE *dst_stream;
2330         char *save_name = NULL;
2331         char *delete_name = NULL;
2332
2333         /* if called as bzcat */
2334         if (strcmp(applet_name, "bzcat") == 0)
2335                 flags |= bunzip_to_stdout;
2336
2337         while ((opt = getopt(argc, argv, "cfh")) != -1) {
2338                 switch (opt) {
2339                 case 'c':
2340                         flags |= bunzip_to_stdout;
2341                         break;
2342                 case 'f':
2343                         flags |= bunzip_force;
2344                         break;
2345                 case 'h':
2346                 default:
2347                         show_usage(); /* exit's inside usage */
2348                 }
2349         }
2350
2351         /* Set input filename and number */
2352         if (argv[optind] == NULL || strcmp(argv[optind], "-") == 0) {
2353                 flags |= bunzip_to_stdout;
2354                 src_stream = stdin;
2355         } else {
2356                 /* Open input file */
2357                 src_stream = xfopen(argv[optind], "r");
2358
2359                 save_name = xstrdup(argv[optind]);
2360                 if (strcmp(save_name + strlen(save_name) - 4, ".bz2") != 0)
2361                         error_msg_and_die("Invalid extension");
2362                 save_name[strlen(save_name) - 4] = '\0';
2363         }
2364
2365         /* Check that the input is sane.  */
2366         if (isatty(fileno(src_stream)) && (flags & bunzip_force) == 0)
2367                 error_msg_and_die("compressed data not read from terminal.  Use -f to force it.");
2368
2369         if (flags & bunzip_to_stdout) {
2370                 dst_stream = stdout;
2371         } else {
2372                 dst_stream = xfopen(save_name, "w");
2373         }
2374
2375         if (uncompressStream(src_stream, dst_stream)) {
2376                 if (!(flags & bunzip_to_stdout))
2377                         delete_name = argv[optind];
2378                 status = EXIT_SUCCESS;
2379         } else {
2380                 if (!(flags & bunzip_to_stdout))
2381                         delete_name = save_name;
2382                 status = EXIT_FAILURE;
2383         }
2384
2385         if (delete_name) {
2386                 if (unlink(delete_name) < 0) {
2387                         error_msg_and_die("Couldn't remove %s", delete_name);
2388                 }
2389         }
2390
2391         return status;
2392 }