archival/bunzip2.c

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