unused/apache/tools/bzip2/CBZip2InputStream.java

   1 /*
   2  *  Licensed to the Apache Software Foundation (ASF) under one or more
   3  *  contributor license agreements.  See the NOTICE file distributed with
   4  *  this work for additional information regarding copyright ownership.
   5  *  The ASF licenses this file to You under the Apache License, Version 2.0
   6  *  (the "License"); you may not use this file except in compliance with
   7  *  the License.  You may obtain a copy of the License at
   8  *
   9  *      http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  *  Unless required by applicable law or agreed to in writing, software
  12  *  distributed under the License is distributed on an "AS IS" BASIS,
  13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  *  See the License for the specific language governing permissions and
  15  *  limitations under the License.
  16  *
  17  */
  18
  19 /*
  20  * This package is based on the work done by Keiron Liddle, Aftex Software
  21  * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
  22  * great code.
  23  */
  24 package org.apache.tools.bzip2;
  25
  26 import java.io.IOException;
  27 import java.io.InputStream;
  28
  29 /**
  30  * An input stream that decompresses from the BZip2 format (without the file
  31  * header chars) to be read as any other stream.
  32  *
  33  * <p>The decompression requires large amounts of memory. Thus you
  34  * should call the {@link #close() close()} method as soon as
  35  * possible, to force <tt>CBZip2InputStream</tt> to release the
  36  * allocated memory.  See {@link CBZip2OutputStream
  37  * CBZip2OutputStream} for information about memory usage.</p>
  38  *
  39  * <p><tt>CBZip2InputStream</tt> reads bytes from the compressed
  40  * source stream via the single byte {@link java.io.InputStream#read()
  41  * read()} method exclusively. Thus you should consider to use a
  42  * buffered source stream.</p>
  43  *
  44  * <p>Instances of this class are not threadsafe.</p>
  45  */
  46 public class CBZip2InputStream extends InputStream implements BZip2Constants {
  47
  48     /**
  49      * Index of the last char in the block, so the block size == last + 1.
  50      */
  51     private int  last;
  52
  53     /**
  54      * Index in zptr[] of original string after sorting.
  55      */
  56     private int  origPtr;
  57
  58     /**
  59      * always: in the range 0 .. 9.
  60      * The current block size is 100000 * this number.
  61      */
  62     private int blockSize100k;
  63
  64     private boolean blockRandomised;
  65
  66     private int bsBuff;
  67     private int bsLive;
  68     private final CRC crc = new CRC();
  69
  70     private int nInUse;
  71
  72     private InputStream in;
  73     private final boolean decompressConcatenated;
  74
  75     private int currentChar = -1;
  76
  77     private static final int EOF                  = 0;
  78     private static final int START_BLOCK_STATE = 1;
  79     private static final int RAND_PART_A_STATE = 2;
  80     private static final int RAND_PART_B_STATE = 3;
  81     private static final int RAND_PART_C_STATE = 4;
  82     private static final int NO_RAND_PART_A_STATE = 5;
  83     private static final int NO_RAND_PART_B_STATE = 6;
  84     private static final int NO_RAND_PART_C_STATE = 7;
  85
  86     private int currentState = START_BLOCK_STATE;
  87
  88     private int storedBlockCRC, storedCombinedCRC;
  89     private int computedBlockCRC, computedCombinedCRC;
  90
  91     // Variables used by setup* methods exclusively
  92
  93     private int su_count;
  94     private int su_ch2;
  95     private int su_chPrev;
  96     private int su_i2;
  97     private int su_j2;
  98     private int su_rNToGo;
  99     private int su_rTPos;
 100     private int su_tPos;
 101     private char su_z;
 102
 103     /**
 104      * All memory intensive stuff.
 105      * This field is initialized by initBlock().
 106      */
 107     private CBZip2InputStream.Data data;
 108
 109     /**
 110      * Constructs a new CBZip2InputStream which decompresses bytes read from
 111      * the specified stream. This doesn't suppprt decompressing
 112      * concatenated .bz2 files.
 113      *
 114      * <p>Although BZip2 headers are marked with the magic
 115      * <tt>"Bz"</tt> this constructor expects the next byte in the
 116      * stream to be the first one after the magic.  Thus callers have
 117      * to skip the first two bytes. Otherwise this constructor will
 118      * throw an exception. </p>
 119      * @param in
 120      *
 121      * @throws IOException
 122      *  if the stream content is malformed or an I/O error occurs.
 123      * @throws NullPointerException
 124      *  if <tt>in == null</tt>
 125      */
 126     public CBZip2InputStream(final InputStream in) throws IOException {
 127         this(in, false);
 128     }
 129
 130     /**
 131      * Constructs a new CBZip2InputStream which decompresses bytes
 132      * read from the specified stream.
 133      *
 134      * <p>Although BZip2 headers are marked with the magic
 135      * <tt>"Bz"</tt> this constructor expects the next byte in the
 136      * stream to be the first one after the magic.  Thus callers have
 137      * to skip the first two bytes. Otherwise this constructor will
 138      * throw an exception. </p>
 139      *
 140      * @param in the InputStream from which this object should be created
 141      * @param decompressConcatenated
 142      *                     if true, decompress until the end of the input;
 143      *                     if false, stop after the first .bz2 stream and
 144      *                     leave the input position to point to the next
 145      *                     byte after the .bz2 stream
 146      *
 147      * @throws IOException
 148      *             if the stream content is malformed or an I/O error occurs.
 149      * @throws NullPointerException
 150      *             if <tt>in == null</tt>
 151      */
 152     public CBZip2InputStream(final InputStream in,
 153                              final boolean decompressConcatenated)
 154             throws IOException {
 155         super();
 156
 157         this.in = in;
 158         this.decompressConcatenated = decompressConcatenated;
 159
 160         init(true);
 161         initBlock();
 162         setupBlock();
 163     }
 164
 165   /** {@inheritDoc} */
 166   @Override
 167   public int read() throws IOException {
 168     if (this.in == null)
 169       throw new IOException("stream closed");
 170     return read0();
 171   }
 172
 173     /*
 174      * (non-Javadoc)
 175      *
 176      * @see java.io.InputStream#read(byte[], int, int)
 177      */
 178     @Override
 179     public int read(final byte[] dest, final int offs, final int len)
 180         throws IOException {
 181         if (offs < 0) {
 182             throw new IndexOutOfBoundsException("offs(" + offs + ") < 0.");
 183         }
 184         if (len < 0) {
 185             throw new IndexOutOfBoundsException("len(" + len + ") < 0.");
 186         }
 187         if (offs + len > dest.length) {
 188             throw new IndexOutOfBoundsException("offs(" + offs + ") + len("
 189                                                 + len + ") > dest.length("
 190                                                 + dest.length + ").");
 191         }
 192         if (this.in == null) {
 193             throw new IOException("stream closed");
 194         }
 195
 196         final int hi = offs + len;
 197         int destOffs = offs;
 198         for (int b; (destOffs < hi) && ((b = read0()) >= 0);) {
 199             dest[destOffs++] = (byte) b;
 200         }
 201
 202         return (destOffs == offs) ? -1 : (destOffs - offs);
 203     }
 204
 205     private void makeMaps() {
 206         final boolean[] inUse   = this.data.inUse;
 207         final byte[] seqToUnseq = this.data.seqToUnseq;
 208
 209         int nInUseShadow = 0;
 210
 211         for (int i = 0; i < 256; i++) {
 212             if (inUse[i]) {
 213                 seqToUnseq[nInUseShadow++] = (byte) i;
 214             }
 215         }
 216
 217         this.nInUse = nInUseShadow;
 218     }
 219
 220     private int read0() throws IOException {
 221         final int retChar = this.currentChar;
 222
 223         switch (this.currentState) {
 224         case EOF:
 225             return -1;
 226
 227         case START_BLOCK_STATE:
 228             throw new IllegalStateException();
 229
 230         case RAND_PART_A_STATE:
 231             throw new IllegalStateException();
 232
 233         case RAND_PART_B_STATE:
 234             setupRandPartB();
 235             break;
 236
 237         case RAND_PART_C_STATE:
 238             setupRandPartC();
 239             break;
 240
 241         case NO_RAND_PART_A_STATE:
 242             throw new IllegalStateException();
 243
 244         case NO_RAND_PART_B_STATE:
 245             setupNoRandPartB();
 246             break;
 247
 248         case NO_RAND_PART_C_STATE:
 249             setupNoRandPartC();
 250             break;
 251
 252         default:
 253             throw new IllegalStateException();
 254         }
 255
 256         return retChar;
 257     }
 258
 259     private boolean init(boolean isFirstStream) throws IOException {
 260         if (null == in) {
 261             throw new IOException("No InputStream");
 262         }
 263
 264         if (isFirstStream) {
 265             if (in.available() == 0) {
 266                 throw new IOException("Empty InputStream");
 267             }
 268         } else {
 269             int magic0 = read();
 270             if (magic0 == -1) {
 271                 return false;
 272             }
 273             int magic1 = read();
 274             if (magic0 != 'B' || magic1 != 'Z') {
 275                 throw new IOException("Garbage after a valid BZip2 stream");
 276             }
 277         }
 278
 279         int magic2 = read();
 280         if (magic2 != 'h') {
 281             throw new IOException(isFirstStream
 282                     ? "Stream is not in the BZip2 format"
 283                     : "Garbage after a valid BZip2 stream");
 284         }
 285
 286         int blockSize = read();
 287         if ((blockSize < '1') || (blockSize > '9')) {
 288             throw new IOException("Stream is not BZip2 formatted: illegal "
 289                                   + "blocksize " + (char) blockSize);
 290         }
 291
 292         this.blockSize100k = blockSize - '0';
 293
 294         this.bsLive = 0;
 295         this.computedCombinedCRC = 0;
 296
 297         return true;
 298     }
 299
 300   private void initBlock() throws IOException {
 301     char magic0;
 302     char magic1;
 303     char magic2;
 304     char magic3;
 305     char magic4;
 306     char magic5;
 307
 308     while (true) {
 309       // Get the block magic bytes.
 310       magic0 = bsGetUByte();
 311       magic1 = bsGetUByte();
 312       magic2 = bsGetUByte();
 313       magic3 = bsGetUByte();
 314       magic4 = bsGetUByte();
 315       magic5 = bsGetUByte();
 316
 317       // If isn't end of stream magic, break out of the loop.
 318       if (magic0 != 0x17 || magic1 != 0x72 || magic2 != 0x45 || magic3 != 0x38
 319           || magic4 != 0x50 || magic5 != 0x90) {
 320         break;
 321       }
 322
 323       // End of stream was reached. Check the combined CRC and
 324       // advance to the next .bz2 stream if decoding concatenated
 325       // streams.
 326       if (complete()) {
 327         return;
 328       }
 329     }
 330
 331     if (magic0 != 0x31 || // '1'
 332         magic1 != 0x41 || // ')'
 333         magic2 != 0x59 || // 'Y'
 334         magic3 != 0x26 || // '&'
 335         magic4 != 0x53 || // 'S'
 336         magic5 != 0x59 // 'Y'
 337     ) {
 338       this.currentState = EOF;
 339       throw new IOException("bad block header");
 340     }
 341     this.storedBlockCRC = bsGetInt();
 342     this.blockRandomised = bsR(1) == 1;
 343
 344     /**
 345      * Allocate data here instead in constructor, so we do not allocate it if
 346      * the input file is empty.
 347      */
 348     if (this.data == null) {
 349       this.data = new Data(this.blockSize100k);
 350     }
 351
 352     // currBlockNo++;
 353     getAndMoveToFrontDecode();
 354
 355     this.crc.initialiseCRC();
 356     this.currentState = START_BLOCK_STATE;
 357   }
 358
 359     private void endBlock() throws IOException {
 360         this.computedBlockCRC = this.crc.getFinalCRC();
 361
 362         // A bad CRC is considered a fatal error.
 363         if (this.storedBlockCRC != this.computedBlockCRC) {
 364             // make next blocks readable without error
 365             // (repair feature, not yet documented, not tested)
 366             this.computedCombinedCRC
 367                 = (this.storedCombinedCRC << 1)
 368                 | (this.storedCombinedCRC >>> 31);
 369             this.computedCombinedCRC ^= this.storedBlockCRC;
 370
 371             reportCRCError();
 372         }
 373
 374         this.computedCombinedCRC
 375             = (this.computedCombinedCRC << 1)
 376             | (this.computedCombinedCRC >>> 31);
 377         this.computedCombinedCRC ^= this.computedBlockCRC;
 378     }
 379
 380     private boolean complete() throws IOException {
 381         this.storedCombinedCRC = bsGetInt();
 382         this.currentState = EOF;
 383         this.data = null;
 384
 385         if (this.storedCombinedCRC != this.computedCombinedCRC) {
 386             reportCRCError();
 387         }
 388
 389         // Look for the next .bz2 stream if decompressing
 390         // concatenated files.
 391         return !decompressConcatenated || !init(false);
 392     }
 393
 394     @Override
 395     public void close() throws IOException {
 396         InputStream inShadow = this.in;
 397         if (inShadow != null) {
 398             try {
 399                 if (inShadow != System.in) {
 400                     inShadow.close();
 401                 }
 402             } finally {
 403                 this.data = null;
 404                 this.in = null;
 405             }
 406         }
 407     }
 408
 409     private int bsR(final int n) throws IOException {
 410         int bsLiveShadow = this.bsLive;
 411         int bsBuffShadow = this.bsBuff;
 412
 413         if (bsLiveShadow < n) {
 414             final InputStream inShadow = this.in;
 415             do {
 416                 int thech = read();//inShadow.read();
 417
 418                 if (thech < 0) {
 419                     throw new IOException("unexpected end of stream");
 420                 }
 421
 422                 bsBuffShadow = (bsBuffShadow << 8) | thech;
 423                 bsLiveShadow += 8;
 424             } while (bsLiveShadow < n);
 425
 426             this.bsBuff = bsBuffShadow;
 427         }
 428
 429         this.bsLive = bsLiveShadow - n;
 430         return (bsBuffShadow >> (bsLiveShadow - n)) & ((1 << n) - 1);
 431     }
 432
 433     private boolean bsGetBit() throws IOException {
 434         int bsLiveShadow = this.bsLive;
 435         int bsBuffShadow = this.bsBuff;
 436
 437         if (bsLiveShadow < 1) {
 438             int thech = read();
 439
 440             if (thech < 0) {
 441                 throw new IOException("unexpected end of stream");
 442             }
 443
 444             bsBuffShadow = (bsBuffShadow << 8) | thech;
 445             bsLiveShadow += 8;
 446             this.bsBuff = bsBuffShadow;
 447         }
 448
 449         this.bsLive = bsLiveShadow - 1;
 450         return ((bsBuffShadow >> (bsLiveShadow - 1)) & 1) != 0;
 451     }
 452
 453     private char bsGetUByte() throws IOException {
 454         return (char) bsR(8);
 455     }
 456
 457     private int bsGetInt() throws IOException {
 458         return (((((bsR(8) << 8) | bsR(8)) << 8) | bsR(8)) << 8) | bsR(8);
 459     }
 460
 461     /**
 462      * Called by createHuffmanDecodingTables() exclusively.
 463      * @param limit
 464      * @param base
 465      * @param perm
 466      * @param length
 467      * @param minLen
 468      * @param maxLen
 469      * @param alphaSize
 470      */
 471     private static void hbCreateDecodeTables(final int[] limit,
 472                                              final int[] base,
 473                                              final int[] perm,
 474                                              final char[] length,
 475                                              final int minLen,
 476                                              final int maxLen,
 477                                              final int alphaSize) {
 478         for (int i = minLen, pp = 0; i <= maxLen; i++) {
 479             for (int j = 0; j < alphaSize; j++) {
 480                 if (length[j] == i) {
 481                     perm[pp++] = j;
 482                 }
 483             }
 484         }
 485
 486         for (int i = MAX_CODE_LEN; --i > 0;) {
 487             base[i] = 0;
 488             limit[i] = 0;
 489         }
 490
 491         for (int i = 0; i < alphaSize; i++) {
 492             base[length[i] + 1]++;
 493         }
 494
 495         for (int i = 1, b = base[0]; i < MAX_CODE_LEN; i++) {
 496             b += base[i];
 497             base[i] = b;
 498         }
 499
 500         for (int i = minLen, vec = 0, b = base[i]; i <= maxLen; i++) {
 501             final int nb = base[i + 1];
 502             vec += nb - b;
 503             b = nb;
 504             limit[i] = vec - 1;
 505             vec <<= 1;
 506         }
 507
 508         for (int i = minLen + 1; i <= maxLen; i++) {
 509             base[i] = ((limit[i - 1] + 1) << 1) - base[i];
 510         }
 511     }
 512
 513     private void recvDecodingTables() throws IOException {
 514         final Data dataShadow     = this.data;
 515         final boolean[] inUse     = dataShadow.inUse;
 516         final byte[] pos          = dataShadow.recvDecodingTables_pos;
 517         final byte[] selector     = dataShadow.selector;
 518         final byte[] selectorMtf  = dataShadow.selectorMtf;
 519
 520         int inUse16 = 0;
 521
 522         /* Receive the mapping table */
 523         for (int i = 0; i < 16; i++) {
 524             if (bsGetBit()) {
 525                 inUse16 |= 1 << i;
 526             }
 527         }
 528
 529         for (int i = 256; --i >= 0;) {
 530             inUse[i] = false;
 531         }
 532
 533         for (int i = 0; i < 16; i++) {
 534             if ((inUse16 & (1 << i)) != 0) {
 535                 final int i16 = i << 4;
 536                 for (int j = 0; j < 16; j++) {
 537                     if (bsGetBit()) {
 538                         inUse[i16 + j] = true;
 539                     }
 540                 }
 541             }
 542         }
 543
 544         makeMaps();
 545         final int alphaSize = this.nInUse + 2;
 546
 547         /* Now the selectors */
 548         final int nGroups = bsR(3);
 549         final int nSelectors = bsR(15);
 550
 551         for (int i = 0; i < nSelectors; i++) {
 552             int j = 0;
 553             while (bsGetBit()) {
 554                 j++;
 555             }
 556             selectorMtf[i] = (byte) j;
 557         }
 558
 559         /* Undo the MTF values for the selectors. */
 560         for (int v = nGroups; --v >= 0;) {
 561             pos[v] = (byte) v;
 562         }
 563
 564         for (int i = 0; i < nSelectors; i++) {
 565             int v = selectorMtf[i] & 0xff;
 566             final byte tmp = pos[v];
 567             while (v > 0) {
 568                 // nearly all times v is zero, 4 in most other cases
 569                 pos[v] = pos[v - 1];
 570                 v--;
 571             }
 572             pos[0] = tmp;
 573             selector[i] = tmp;
 574         }
 575
 576         final char[][] len  = dataShadow.temp_charArray2d;
 577
 578         /* Now the coding tables */
 579         for (int t = 0; t < nGroups; t++) {
 580             int curr = bsR(5);
 581             final char[] len_t = len[t];
 582             for (int i = 0; i < alphaSize; i++) {
 583                 while (bsGetBit()) {
 584                     curr += bsGetBit() ? -1 : 1;
 585                 }
 586                 len_t[i] = (char) curr;
 587             }
 588         }
 589
 590         // finally create the Huffman tables
 591         createHuffmanDecodingTables(alphaSize, nGroups);
 592     }
 593
 594     /**
 595      * Called by recvDecodingTables() exclusively.
 596      * @param alphaSize
 597      * @param nGroups
 598      */
 599     private void createHuffmanDecodingTables(final int alphaSize,
 600                                              final int nGroups) {
 601         final Data dataShadow = this.data;
 602         final char[][] len  = dataShadow.temp_charArray2d;
 603         final int[] minLens = dataShadow.minLens;
 604         final int[][] limit = dataShadow.limit;
 605         final int[][] base  = dataShadow.base;
 606         final int[][] perm  = dataShadow.perm;
 607
 608         for (int t = 0; t < nGroups; t++) {
 609             int minLen = 32;
 610             int maxLen = 0;
 611             final char[] len_t = len[t];
 612             for (int i = alphaSize; --i >= 0;) {
 613                 final char lent = len_t[i];
 614                 if (lent > maxLen) {
 615                     maxLen = lent;
 616                 }
 617                 if (lent < minLen) {
 618                     minLen = lent;
 619                 }
 620             }
 621             hbCreateDecodeTables(limit[t], base[t], perm[t], len[t], minLen,
 622                                  maxLen, alphaSize);
 623             minLens[t] = minLen;
 624         }
 625     }
 626
 627   private void getAndMoveToFrontDecode() throws IOException {
 628     this.origPtr = bsR(24);
 629     recvDecodingTables();
 630
 631     final InputStream inShadow = this.in;
 632     final Data dataShadow = this.data;
 633     final byte[] ll8 = dataShadow.ll8;
 634     final int[] unzftab = dataShadow.unzftab;
 635     final byte[] selector = dataShadow.selector;
 636     final byte[] seqToUnseq = dataShadow.seqToUnseq;
 637     final char[] yy = dataShadow.getAndMoveToFrontDecode_yy;
 638     final int[] minLens = dataShadow.minLens;
 639     final int[][] limit = dataShadow.limit;
 640     final int[][] base = dataShadow.base;
 641     final int[][] perm = dataShadow.perm;
 642     final int limitLast = this.blockSize100k * 100000;
 643
 644     /*
 645       Setting up the unzftab entries here is not strictly
 646       necessary, but it does save having to do it later
 647       in a separate pass, and so saves a block's worth of
 648       cache misses.
 649     */
 650     for (int i = 256; --i >= 0;) {
 651       yy[i] = (char) i;
 652       unzftab[i] = 0;
 653     }
 654
 655     int groupNo = 0;
 656     int groupPos = G_SIZE - 1;
 657     final int eob = this.nInUse + 1;
 658     int nextSym = getAndMoveToFrontDecode0(0);
 659     int bsBuffShadow = this.bsBuff;
 660     int bsLiveShadow = this.bsLive;
 661     int lastShadow = -1;
 662     int zt = selector[groupNo] & 0xff;
 663     int[] base_zt = base[zt];
 664     int[] limit_zt = limit[zt];
 665     int[] perm_zt = perm[zt];
 666     int minLens_zt = minLens[zt];
 667
 668     while (nextSym != eob) {
 669       if ((nextSym == RUNA) || (nextSym == RUNB)) {
 670         int s = -1;
 671
 672         for (int n = 1; true; n <<= 1) {
 673           if (nextSym == RUNA) {
 674             s += n;
 675           } else if (nextSym == RUNB) {
 676             s += n << 1;
 677           } else {
 678             break;
 679           }
 680
 681           if (groupPos == 0) {
 682             groupPos = G_SIZE - 1;
 683             zt = selector[++groupNo] & 0xff;
 684             base_zt = base[zt];
 685             limit_zt = limit[zt];
 686             perm_zt = perm[zt];
 687             minLens_zt = minLens[zt];
 688           } else {
 689             groupPos--;
 690           }
 691
 692           int zn = minLens_zt;
 693
 694           // Inlined:
 695           // int zvec = bsR(zn);
 696           while (bsLiveShadow < zn) {
 697             final int thech = read();//inShadow.read();
 698             if (thech < 0)
 699               throw new IOException("unexpected end of stream");
 700
 701             bsBuffShadow = (bsBuffShadow << 8) | thech;
 702             bsLiveShadow += 8;
 703             continue;
 704           }
 705           int zvec = (bsBuffShadow >> (bsLiveShadow - zn)) & ((1 << zn) - 1);
 706           bsLiveShadow -= zn;
 707
 708           while (zvec > limit_zt[zn]) {
 709             zn++;
 710             while (bsLiveShadow < 1) {
 711               final int thech = read();//inShadow.read();
 712               if (thech < 0)
 713                 throw new IOException("unexpected end of stream");
 714               bsBuffShadow = (bsBuffShadow << 8) | thech;
 715               bsLiveShadow += 8;
 716               continue;
 717             }
 718             bsLiveShadow--;
 719             zvec = (zvec << 1) | ((bsBuffShadow >> bsLiveShadow) & 1);
 720           }
 721           nextSym = perm_zt[zvec - base_zt[zn]];
 722         }
 723
 724         final byte ch = seqToUnseq[yy[0]];
 725         unzftab[ch & 0xff] += s + 1;
 726
 727         while (s-- >= 0) {
 728           ll8[++lastShadow] = ch;
 729         }
 730
 731         if (lastShadow >= limitLast) {
 732           throw new IOException("block overrun");
 733         }
 734       } else {
 735         if (++lastShadow >= limitLast) {
 736           throw new IOException("block overrun");
 737         }
 738
 739         final char tmp = yy[nextSym - 1];
 740         unzftab[seqToUnseq[tmp] & 0xff]++;
 741         ll8[lastShadow] = seqToUnseq[tmp];
 742
 743         /*
 744           This loop is hammered during decompression,
 745           hence avoid native method call overhead of
 746           System.arraycopy for very small ranges to copy.
 747         */
 748         if (nextSym <= 16) {
 749           for (int j = nextSym - 1; j > 0;) {
 750             yy[j] = yy[--j];
 751           }
 752         } else {
 753           System.arraycopy(yy, 0, yy, 1, nextSym - 1);
 754         }
 755
 756         yy[0] = tmp;
 757
 758         if (groupPos == 0) {
 759           groupPos = G_SIZE - 1;
 760           zt = selector[++groupNo] & 0xff;
 761           base_zt = base[zt];
 762           limit_zt = limit[zt];
 763           perm_zt = perm[zt];
 764           minLens_zt = minLens[zt];
 765         } else {
 766           groupPos--;
 767         }
 768
 769         int zn = minLens_zt;
 770
 771         // Inlined:
 772         // int zvec = bsR(zn);
 773         while (bsLiveShadow < zn) {
 774           final int thech = read();//inShadow.read();
 775           if (thech < 0)
 776             throw new IOException("unexpected end of stream");
 777           bsBuffShadow = (bsBuffShadow << 8) | thech;
 778           bsLiveShadow += 8;
 779           continue;
 780         }
 781         int zvec = (bsBuffShadow >> (bsLiveShadow - zn)) & ((1 << zn) - 1);
 782         bsLiveShadow -= zn;
 783
 784         while (zvec > limit_zt[zn]) {
 785           zn++;
 786           while (bsLiveShadow < 1) {
 787             final int thech = read();//inShadow.read();
 788             if (thech <0)
 789               throw new IOException("unexpected end of stream");
 790               bsBuffShadow = (bsBuffShadow << 8) | thech;
 791               bsLiveShadow += 8;
 792               continue;
 793           }
 794           bsLiveShadow--;
 795           zvec = (zvec << 1) | ((bsBuffShadow >> bsLiveShadow) & 1);
 796         }
 797         nextSym = perm_zt[zvec - base_zt[zn]];
 798       }
 799     }
 800
 801     this.last = lastShadow;
 802     this.bsLive = bsLiveShadow;
 803     this.bsBuff = bsBuffShadow;
 804   }
 805
 806   private int getAndMoveToFrontDecode0(final int groupNo) throws IOException {
 807     final InputStream inShadow = this.in;
 808     final Data dataShadow = this.data;
 809     final int zt = dataShadow.selector[groupNo] & 0xff;
 810     final int[] limit_zt = dataShadow.limit[zt];
 811     int zn = dataShadow.minLens[zt];
 812     int zvec = bsR(zn);
 813     int bsLiveShadow = this.bsLive;
 814     int bsBuffShadow = this.bsBuff;
 815
 816     while (zvec > limit_zt[zn]) {
 817       zn++;
 818       while (bsLiveShadow < 1) {
 819         final int thech = read();//inShadow.read();
 820
 821         if (thech < 0)
 822           throw new IOException("unexpected end of stream");
 823
 824         bsBuffShadow = (bsBuffShadow << 8) | thech;
 825         bsLiveShadow += 8;
 826         continue;
 827       }
 828       bsLiveShadow--;
 829       zvec = (zvec << 1) | ((bsBuffShadow >> bsLiveShadow) & 1);
 830     }
 831
 832     this.bsLive = bsLiveShadow;
 833     this.bsBuff = bsBuffShadow;
 834
 835     return dataShadow.perm[zt][zvec - dataShadow.base[zt][zn]];
 836   }
 837
 838     private void setupBlock() throws IOException {
 839         if (this.data == null) {
 840             return;
 841         }
 842
 843         final int[] cftab = this.data.cftab;
 844         final int[] tt    = this.data.initTT(this.last + 1);
 845         final byte[] ll8  = this.data.ll8;
 846         cftab[0] = 0;
 847         System.arraycopy(this.data.unzftab, 0, cftab, 1, 256);
 848
 849         for (int i = 1, c = cftab[0]; i <= 256; i++) {
 850             c += cftab[i];
 851             cftab[i] = c;
 852         }
 853
 854         for (int i = 0, lastShadow = this.last; i <= lastShadow; i++) {
 855             tt[cftab[ll8[i] & 0xff]++] = i;
 856         }
 857
 858         if ((this.origPtr < 0) || (this.origPtr >= tt.length)) {
 859             throw new IOException("stream corrupted");
 860         }
 861
 862         this.su_tPos = tt[this.origPtr];
 863         this.su_count = 0;
 864         this.su_i2 = 0;
 865         this.su_ch2 = 256;   /* not a char and not EOF */
 866
 867         if (this.blockRandomised) {
 868             this.su_rNToGo = 0;
 869             this.su_rTPos = 0;
 870             setupRandPartA();
 871         } else {
 872             setupNoRandPartA();
 873         }
 874     }
 875
 876     private void setupRandPartA() throws IOException {
 877         if (this.su_i2 <= this.last) {
 878             this.su_chPrev = this.su_ch2;
 879             int su_ch2Shadow = this.data.ll8[this.su_tPos] & 0xff;
 880             this.su_tPos = this.data.tt[this.su_tPos];
 881             if (this.su_rNToGo == 0) {
 882                 this.su_rNToGo = BZip2Constants.rNums[this.su_rTPos] - 1;
 883                 if (++this.su_rTPos == 512) {
 884                     this.su_rTPos = 0;
 885                 }
 886             } else {
 887                 this.su_rNToGo--;
 888             }
 889             this.su_ch2 = su_ch2Shadow ^= (this.su_rNToGo == 1) ? 1 : 0;
 890             this.su_i2++;
 891             this.currentChar = su_ch2Shadow;
 892             this.currentState = RAND_PART_B_STATE;
 893             this.crc.updateCRC(su_ch2Shadow);
 894         } else {
 895             endBlock();
 896             initBlock();
 897             setupBlock();
 898         }
 899     }
 900
 901     private void setupNoRandPartA() throws IOException {
 902         if (this.su_i2 <= this.last) {
 903             this.su_chPrev = this.su_ch2;
 904             int su_ch2Shadow = this.data.ll8[this.su_tPos] & 0xff;
 905             this.su_ch2 = su_ch2Shadow;
 906             this.su_tPos = this.data.tt[this.su_tPos];
 907             this.su_i2++;
 908             this.currentChar = su_ch2Shadow;
 909             this.currentState = NO_RAND_PART_B_STATE;
 910             this.crc.updateCRC(su_ch2Shadow);
 911         } else {
 912             this.currentState = NO_RAND_PART_A_STATE;
 913             endBlock();
 914             initBlock();
 915             setupBlock();
 916         }
 917     }
 918
 919     private void setupRandPartB() throws IOException {
 920         if (this.su_ch2 != this.su_chPrev) {
 921             this.currentState = RAND_PART_A_STATE;
 922             this.su_count = 1;
 923             setupRandPartA();
 924         } else if (++this.su_count >= 4) {
 925             this.su_z = (char) (this.data.ll8[this.su_tPos] & 0xff);
 926             this.su_tPos = this.data.tt[this.su_tPos];
 927             if (this.su_rNToGo == 0) {
 928                 this.su_rNToGo = BZip2Constants.rNums[this.su_rTPos] - 1;
 929                 if (++this.su_rTPos == 512) {
 930                     this.su_rTPos = 0;
 931                 }
 932             } else {
 933                 this.su_rNToGo--;
 934             }
 935             this.su_j2 = 0;
 936             this.currentState = RAND_PART_C_STATE;
 937             if (this.su_rNToGo == 1) {
 938                 this.su_z ^= 1;
 939             }
 940             setupRandPartC();
 941         } else {
 942             this.currentState = RAND_PART_A_STATE;
 943             setupRandPartA();
 944         }
 945     }
 946
 947     private void setupRandPartC() throws IOException {
 948         if (this.su_j2 < this.su_z) {
 949             this.currentChar = this.su_ch2;
 950             this.crc.updateCRC(this.su_ch2);
 951             this.su_j2++;
 952         } else {
 953             this.currentState = RAND_PART_A_STATE;
 954             this.su_i2++;
 955             this.su_count = 0;
 956             setupRandPartA();
 957         }
 958     }
 959
 960     private void setupNoRandPartB() throws IOException {
 961         if (this.su_ch2 != this.su_chPrev) {
 962             this.su_count = 1;
 963             setupNoRandPartA();
 964         } else if (++this.su_count >= 4) {
 965             this.su_z = (char) (this.data.ll8[this.su_tPos] & 0xff);
 966             this.su_tPos = this.data.tt[this.su_tPos];
 967             this.su_j2 = 0;
 968             setupNoRandPartC();
 969         } else {
 970             setupNoRandPartA();
 971         }
 972     }
 973
 974     private void setupNoRandPartC() throws IOException {
 975         if (this.su_j2 < this.su_z) {
 976             int su_ch2Shadow = this.su_ch2;
 977             this.currentChar = su_ch2Shadow;
 978             this.crc.updateCRC(su_ch2Shadow);
 979             this.su_j2++;
 980             this.currentState = NO_RAND_PART_C_STATE;
 981         } else {
 982             this.su_i2++;
 983             this.su_count = 0;
 984             setupNoRandPartA();
 985         }
 986     }
 987
 988     private static final class Data extends Object {
 989
 990         // (with blockSize 900k)
 991         final boolean[] inUse   = new boolean[256];                                   //      256 byte
 992
 993         final byte[] seqToUnseq   = new byte[256];                                    //      256 byte
 994         final byte[] selector     = new byte[MAX_SELECTORS];                          //    18002 byte
 995         final byte[] selectorMtf  = new byte[MAX_SELECTORS];                          //    18002 byte
 996
 997         /**
 998          * Freq table collected to save a pass over the data during
 999          * decompression.
1000          */
1001         final int[] unzftab = new int[256];                                           //     1024 byte
1002
1003         final int[][] limit = new int[N_GROUPS][MAX_ALPHA_SIZE];                      //     6192 byte
1004         final int[][] base  = new int[N_GROUPS][MAX_ALPHA_SIZE];                      //     6192 byte
1005         final int[][] perm  = new int[N_GROUPS][MAX_ALPHA_SIZE];                      //     6192 byte
1006         final int[] minLens = new int[N_GROUPS];                                      //       24 byte
1007
1008         final int[]     cftab     = new int[257];                                     //     1028 byte
1009         final char[]    getAndMoveToFrontDecode_yy = new char[256];                   //      512 byte
1010         final char[][]  temp_charArray2d  = new char[N_GROUPS][MAX_ALPHA_SIZE];       //     3096 byte
1011         final byte[] recvDecodingTables_pos = new byte[N_GROUPS];                     //        6 byte
1012         //---------------
1013         //    60798 byte
1014
1015         int[] tt;                                                                     //  3600000 byte
1016         byte[] ll8;                                                                   //   900000 byte
1017         //---------------
1018         //  4560782 byte
1019         //===============
1020
1021         Data(int blockSize100k) {
1022             super();
1023
1024             this.ll8 = new byte[blockSize100k * BZip2Constants.baseBlockSize];
1025         }
1026
1027         /**
1028          * Initializes the {@link #tt} array.
1029          *
1030          * This method is called when the required length of the array
1031          * is known.  I don't initialize it at construction time to
1032          * avoid unnecessary memory allocation when compressing small
1033          * files.
1034          * @param length
1035          * @return int array
1036          */
1037         final int[] initTT(int length) {
1038             int[] ttShadow = this.tt;
1039
1040             // tt.length should always be >= length, but theoretically
1041             // it can happen, if the compressor mixed small and large
1042             // blocks.  Normally only the last block will be smaller
1043             // than others.
1044             if ((ttShadow == null) || (ttShadow.length < length)) {
1045                 this.tt = ttShadow = new int[length];
1046             }
1047
1048             return ttShadow;
1049         }
1050
1051     }
1052
1053     @SuppressWarnings("unused")
1054     private static void reportCRCError() throws IOException {
1055         // The clean way would be to throw an exception.
1056         //throw new IOException("crc error");
1057
1058         // Just print a message, like the previous versions of this class did
1059         System.err.println("BZip2 CRC error");
1060     }
1061
1062 }
1063