archival/bunzip2.c

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