001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one
003     * or more contributor license agreements.  See the NOTICE file
004     * distributed with this work for additional information
005     * regarding copyright ownership.  The ASF licenses this file
006     * to you under the Apache License, Version 2.0 (the
007     * "License"); you may not use this file except in compliance
008     * with the License.  You may obtain a copy of the License at
009     *
010     * http://www.apache.org/licenses/LICENSE-2.0
011     *
012     * Unless required by applicable law or agreed to in writing,
013     * software distributed under the License is distributed on an
014     * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015     * KIND, either express or implied.  See the License for the
016     * specific language governing permissions and limitations
017     * under the License.
018     */
019    
020    /*
021     * This package is based on the work done by Keiron Liddle, Aftex Software
022     * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
023     * great code.
024     */
025    package org.apache.commons.compress.compressors.bzip2;
026    
027    import java.io.IOException;
028    import java.io.InputStream;
029    
030    import org.apache.commons.compress.compressors.CompressorInputStream;
031    
032    /**
033     * An input stream that decompresses from the BZip2 format to be read as any other stream.
034     * 
035     * @NotThreadSafe
036     */
037    public class BZip2CompressorInputStream extends CompressorInputStream implements
038                                                                              BZip2Constants {
039    
040        /**
041         * Index of the last char in the block, so the block size == last + 1.
042         */
043        private int last;
044    
045        /**
046         * Index in zptr[] of original string after sorting.
047         */
048        private int origPtr;
049    
050        /**
051         * always: in the range 0 .. 9. The current block size is 100000 * this
052         * number.
053         */
054        private int blockSize100k;
055    
056        private boolean blockRandomised;
057    
058        private int bsBuff;
059        private int bsLive;
060        private final CRC crc = new CRC();
061    
062        private int nInUse;
063    
064        private InputStream in;
065    
066        private int currentChar = -1;
067    
068        private static final int EOF = 0;
069        private static final int START_BLOCK_STATE = 1;
070        private static final int RAND_PART_A_STATE = 2;
071        private static final int RAND_PART_B_STATE = 3;
072        private static final int RAND_PART_C_STATE = 4;
073        private static final int NO_RAND_PART_A_STATE = 5;
074        private static final int NO_RAND_PART_B_STATE = 6;
075        private static final int NO_RAND_PART_C_STATE = 7;
076    
077        private int currentState = START_BLOCK_STATE;
078    
079        private int storedBlockCRC, storedCombinedCRC;
080        private int computedBlockCRC, computedCombinedCRC;
081    
082        // Variables used by setup* methods exclusively
083    
084        private int su_count;
085        private int su_ch2;
086        private int su_chPrev;
087        private int su_i2;
088        private int su_j2;
089        private int su_rNToGo;
090        private int su_rTPos;
091        private int su_tPos;
092        private char su_z;
093    
094        /**
095         * All memory intensive stuff. This field is initialized by initBlock().
096         */
097        private BZip2CompressorInputStream.Data data;
098    
099        /**
100         * Constructs a new BZip2CompressorInputStream which decompresses bytes read from the
101         * specified stream.
102         * 
103         * @throws IOException
104         *             if the stream content is malformed or an I/O error occurs.
105         * @throws NullPointerException
106         *             if <tt>in == null</tt>
107         */
108        public BZip2CompressorInputStream(final InputStream in) throws IOException {
109            super();
110    
111            this.in = in;
112            init();
113        }
114    
115        /** {@inheritDoc} */
116        public int read() throws IOException {
117            if (this.in != null) {
118                return read0();
119            } else {
120                throw new IOException("stream closed");
121            }
122        }
123    
124        /*
125         * (non-Javadoc)
126         * 
127         * @see java.io.InputStream#read(byte[], int, int)
128         */
129        public int read(final byte[] dest, final int offs, final int len)
130            throws IOException {
131            if (offs < 0) {
132                throw new IndexOutOfBoundsException("offs(" + offs + ") < 0.");
133            }
134            if (len < 0) {
135                throw new IndexOutOfBoundsException("len(" + len + ") < 0.");
136            }
137            if (offs + len > dest.length) {
138                throw new IndexOutOfBoundsException("offs(" + offs + ") + len("
139                                                    + len + ") > dest.length(" + dest.length + ").");
140            }
141            if (this.in == null) {
142                throw new IOException("stream closed");
143            }
144    
145            final int hi = offs + len;
146            int destOffs = offs;
147            for (int b; (destOffs < hi) && ((b = read0()) >= 0);) {
148                dest[destOffs++] = (byte) b;
149            }
150    
151            return (destOffs == offs) ? -1 : (destOffs - offs);
152        }
153    
154        private void makeMaps() {
155            final boolean[] inUse = this.data.inUse;
156            final byte[] seqToUnseq = this.data.seqToUnseq;
157    
158            int nInUseShadow = 0;
159    
160            for (int i = 0; i < 256; i++) {
161                if (inUse[i])
162                    seqToUnseq[nInUseShadow++] = (byte) i;
163            }
164    
165            this.nInUse = nInUseShadow;
166        }
167    
168        private int read0() throws IOException {
169            final int retChar = this.currentChar;
170    
171            switch (this.currentState) {
172            case EOF:
173                return -1;
174    
175            case START_BLOCK_STATE:
176                throw new IllegalStateException();
177    
178            case RAND_PART_A_STATE:
179                throw new IllegalStateException();
180    
181            case RAND_PART_B_STATE:
182                setupRandPartB();
183                break;
184    
185            case RAND_PART_C_STATE:
186                setupRandPartC();
187                break;
188    
189            case NO_RAND_PART_A_STATE:
190                throw new IllegalStateException();
191    
192            case NO_RAND_PART_B_STATE:
193                setupNoRandPartB();
194                break;
195    
196            case NO_RAND_PART_C_STATE:
197                setupNoRandPartC();
198                break;
199    
200            default:
201                throw new IllegalStateException();
202            }
203    
204            return retChar;
205        }
206    
207        private void init() throws IOException {
208            if (null == in) {
209                throw new IOException("No InputStream");
210            }
211            if (in.available() == 0) {
212                throw new IOException("Empty InputStream");
213            }
214            checkMagicChar('B', "first");
215            checkMagicChar('Z', "second");
216            checkMagicChar('h', "third");
217    
218            int blockSize = this.in.read();
219            if ((blockSize < '1') || (blockSize > '9')) {
220                throw new IOException("Stream is not BZip2 formatted: illegal "
221                                      + "blocksize " + (char) blockSize);
222            }
223    
224            this.blockSize100k = blockSize - '0';
225    
226            initBlock();
227            setupBlock();
228        }
229    
230        private void checkMagicChar(char expected, String position)
231            throws IOException {
232            int magic = this.in.read();
233            if (magic != expected) {
234                throw new IOException("Stream is not BZip2 formatted: expected '"
235                                      + expected + "' as " + position + " byte but got '"
236                                      + (char) magic + "'");
237            }
238        }
239    
240        private void initBlock() throws IOException {
241            char magic0 = bsGetUByte();
242            char magic1 = bsGetUByte();
243            char magic2 = bsGetUByte();
244            char magic3 = bsGetUByte();
245            char magic4 = bsGetUByte();
246            char magic5 = bsGetUByte();
247    
248            if (magic0 == 0x17 && magic1 == 0x72 && magic2 == 0x45
249                && magic3 == 0x38 && magic4 == 0x50 && magic5 == 0x90) {
250                complete(); // end of file
251            } else if (magic0 != 0x31 || // '1'
252                       magic1 != 0x41 || // ')'
253                       magic2 != 0x59 || // 'Y'
254                       magic3 != 0x26 || // '&'
255                       magic4 != 0x53 || // 'S'
256                       magic5 != 0x59 // 'Y'
257                       ) {
258                this.currentState = EOF;
259                throw new IOException("bad block header");
260            } else {
261                this.storedBlockCRC = bsGetInt();
262                this.blockRandomised = bsR(1) == 1;
263    
264                /**
265                 * Allocate data here instead in constructor, so we do not allocate
266                 * it if the input file is empty.
267                 */
268                if (this.data == null) {
269                    this.data = new Data(this.blockSize100k);
270                }
271    
272                // currBlockNo++;
273                getAndMoveToFrontDecode();
274    
275                this.crc.initialiseCRC();
276                this.currentState = START_BLOCK_STATE;
277            }
278        }
279    
280        private void endBlock() throws IOException {
281            this.computedBlockCRC = this.crc.getFinalCRC();
282    
283            // A bad CRC is considered a fatal error.
284            if (this.storedBlockCRC != this.computedBlockCRC) {
285                // make next blocks readable without error
286                // (repair feature, not yet documented, not tested)
287                this.computedCombinedCRC = (this.storedCombinedCRC << 1)
288                    | (this.storedCombinedCRC >>> 31);
289                this.computedCombinedCRC ^= this.storedBlockCRC;
290    
291                throw new IOException("BZip2 CRC error");
292            }
293    
294            this.computedCombinedCRC = (this.computedCombinedCRC << 1)
295                | (this.computedCombinedCRC >>> 31);
296            this.computedCombinedCRC ^= this.computedBlockCRC;
297        }
298    
299        private void complete() throws IOException {
300            this.storedCombinedCRC = bsGetInt();
301            this.currentState = EOF;
302            this.data = null;
303    
304            if (this.storedCombinedCRC != this.computedCombinedCRC) {
305                throw new IOException("BZip2 CRC error");
306            }
307        }
308    
309        public void close() throws IOException {
310            InputStream inShadow = this.in;
311            if (inShadow != null) {
312                try {
313                    if (inShadow != System.in) {
314                        inShadow.close();
315                    }
316                } finally {
317                    this.data = null;
318                    this.in = null;
319                }
320            }
321        }
322    
323        private int bsR(final int n) throws IOException {
324            int bsLiveShadow = this.bsLive;
325            int bsBuffShadow = this.bsBuff;
326    
327            if (bsLiveShadow < n) {
328                final InputStream inShadow = this.in;
329                do {
330                    int thech = inShadow.read();
331    
332                    if (thech < 0) {
333                        throw new IOException("unexpected end of stream");
334                    }
335    
336                    bsBuffShadow = (bsBuffShadow << 8) | thech;
337                    bsLiveShadow += 8;
338                } while (bsLiveShadow < n);
339    
340                this.bsBuff = bsBuffShadow;
341            }
342    
343            this.bsLive = bsLiveShadow - n;
344            return (bsBuffShadow >> (bsLiveShadow - n)) & ((1 << n) - 1);
345        }
346    
347        private boolean bsGetBit() throws IOException {
348            int bsLiveShadow = this.bsLive;
349            int bsBuffShadow = this.bsBuff;
350    
351            if (bsLiveShadow < 1) {
352                int thech = this.in.read();
353    
354                if (thech < 0) {
355                    throw new IOException("unexpected end of stream");
356                }
357    
358                bsBuffShadow = (bsBuffShadow << 8) | thech;
359                bsLiveShadow += 8;
360                this.bsBuff = bsBuffShadow;
361            }
362    
363            this.bsLive = bsLiveShadow - 1;
364            return ((bsBuffShadow >> (bsLiveShadow - 1)) & 1) != 0;
365        }
366    
367        private char bsGetUByte() throws IOException {
368            return (char) bsR(8);
369        }
370    
371        private int bsGetInt() throws IOException {
372            return (((((bsR(8) << 8) | bsR(8)) << 8) | bsR(8)) << 8) | bsR(8);
373        }
374    
375        /**
376         * Called by createHuffmanDecodingTables() exclusively.
377         */
378        private static void hbCreateDecodeTables(final int[] limit,
379                                                 final int[] base, final int[] perm, final char[] length,
380                                                 final int minLen, final int maxLen, final int alphaSize) {
381            for (int i = minLen, pp = 0; i <= maxLen; i++) {
382                for (int j = 0; j < alphaSize; j++) {
383                    if (length[j] == i) {
384                        perm[pp++] = j;
385                    }
386                }
387            }
388    
389            for (int i = MAX_CODE_LEN; --i > 0;) {
390                base[i] = 0;
391                limit[i] = 0;
392            }
393    
394            for (int i = 0; i < alphaSize; i++) {
395                base[length[i] + 1]++;
396            }
397    
398            for (int i = 1, b = base[0]; i < MAX_CODE_LEN; i++) {
399                b += base[i];
400                base[i] = b;
401            }
402    
403            for (int i = minLen, vec = 0, b = base[i]; i <= maxLen; i++) {
404                final int nb = base[i + 1];
405                vec += nb - b;
406                b = nb;
407                limit[i] = vec - 1;
408                vec <<= 1;
409            }
410    
411            for (int i = minLen + 1; i <= maxLen; i++) {
412                base[i] = ((limit[i - 1] + 1) << 1) - base[i];
413            }
414        }
415    
416        private void recvDecodingTables() throws IOException {
417            final Data dataShadow = this.data;
418            final boolean[] inUse = dataShadow.inUse;
419            final byte[] pos = dataShadow.recvDecodingTables_pos;
420            final byte[] selector = dataShadow.selector;
421            final byte[] selectorMtf = dataShadow.selectorMtf;
422    
423            int inUse16 = 0;
424    
425            /* Receive the mapping table */
426            for (int i = 0; i < 16; i++) {
427                if (bsGetBit()) {
428                    inUse16 |= 1 << i;
429                }
430            }
431    
432            for (int i = 256; --i >= 0;) {
433                inUse[i] = false;
434            }
435    
436            for (int i = 0; i < 16; i++) {
437                if ((inUse16 & (1 << i)) != 0) {
438                    final int i16 = i << 4;
439                    for (int j = 0; j < 16; j++) {
440                        if (bsGetBit()) {
441                            inUse[i16 + j] = true;
442                        }
443                    }
444                }
445            }
446    
447            makeMaps();
448            final int alphaSize = this.nInUse + 2;
449    
450            /* Now the selectors */
451            final int nGroups = bsR(3);
452            final int nSelectors = bsR(15);
453    
454            for (int i = 0; i < nSelectors; i++) {
455                int j = 0;
456                while (bsGetBit()) {
457                    j++;
458                }
459                selectorMtf[i] = (byte) j;
460            }
461    
462            /* Undo the MTF values for the selectors. */
463            for (int v = nGroups; --v >= 0;) {
464                pos[v] = (byte) v;
465            }
466    
467            for (int i = 0; i < nSelectors; i++) {
468                int v = selectorMtf[i] & 0xff;
469                final byte tmp = pos[v];
470                while (v > 0) {
471                    // nearly all times v is zero, 4 in most other cases
472                    pos[v] = pos[v - 1];
473                    v--;
474                }
475                pos[0] = tmp;
476                selector[i] = tmp;
477            }
478    
479            final char[][] len = dataShadow.temp_charArray2d;
480    
481            /* Now the coding tables */
482            for (int t = 0; t < nGroups; t++) {
483                int curr = bsR(5);
484                final char[] len_t = len[t];
485                for (int i = 0; i < alphaSize; i++) {
486                    while (bsGetBit()) {
487                        curr += bsGetBit() ? -1 : 1;
488                    }
489                    len_t[i] = (char) curr;
490                }
491            }
492    
493            // finally create the Huffman tables
494            createHuffmanDecodingTables(alphaSize, nGroups);
495        }
496    
497        /**
498         * Called by recvDecodingTables() exclusively.
499         */
500        private void createHuffmanDecodingTables(final int alphaSize,
501                                                 final int nGroups) {
502            final Data dataShadow = this.data;
503            final char[][] len = dataShadow.temp_charArray2d;
504            final int[] minLens = dataShadow.minLens;
505            final int[][] limit = dataShadow.limit;
506            final int[][] base = dataShadow.base;
507            final int[][] perm = dataShadow.perm;
508    
509            for (int t = 0; t < nGroups; t++) {
510                int minLen = 32;
511                int maxLen = 0;
512                final char[] len_t = len[t];
513                for (int i = alphaSize; --i >= 0;) {
514                    final char lent = len_t[i];
515                    if (lent > maxLen) {
516                        maxLen = lent;
517                    }
518                    if (lent < minLen) {
519                        minLen = lent;
520                    }
521                }
522                hbCreateDecodeTables(limit[t], base[t], perm[t], len[t], minLen,
523                                     maxLen, alphaSize);
524                minLens[t] = minLen;
525            }
526        }
527    
528        private void getAndMoveToFrontDecode() throws IOException {
529            this.origPtr = bsR(24);
530            recvDecodingTables();
531    
532            final InputStream inShadow = this.in;
533            final Data dataShadow = this.data;
534            final byte[] ll8 = dataShadow.ll8;
535            final int[] unzftab = dataShadow.unzftab;
536            final byte[] selector = dataShadow.selector;
537            final byte[] seqToUnseq = dataShadow.seqToUnseq;
538            final char[] yy = dataShadow.getAndMoveToFrontDecode_yy;
539            final int[] minLens = dataShadow.minLens;
540            final int[][] limit = dataShadow.limit;
541            final int[][] base = dataShadow.base;
542            final int[][] perm = dataShadow.perm;
543            final int limitLast = this.blockSize100k * 100000;
544    
545            /*
546             * Setting up the unzftab entries here is not strictly necessary, but it
547             * does save having to do it later in a separate pass, and so saves a
548             * block's worth of cache misses.
549             */
550            for (int i = 256; --i >= 0;) {
551                yy[i] = (char) i;
552                unzftab[i] = 0;
553            }
554    
555            int groupNo = 0;
556            int groupPos = G_SIZE - 1;
557            final int eob = this.nInUse + 1;
558            int nextSym = getAndMoveToFrontDecode0(0);
559            int bsBuffShadow = this.bsBuff;
560            int bsLiveShadow = this.bsLive;
561            int lastShadow = -1;
562            int zt = selector[groupNo] & 0xff;
563            int[] base_zt = base[zt];
564            int[] limit_zt = limit[zt];
565            int[] perm_zt = perm[zt];
566            int minLens_zt = minLens[zt];
567    
568            while (nextSym != eob) {
569                if ((nextSym == RUNA) || (nextSym == RUNB)) {
570                    int s = -1;
571    
572                    for (int n = 1; true; n <<= 1) {
573                        if (nextSym == RUNA) {
574                            s += n;
575                        } else if (nextSym == RUNB) {
576                            s += n << 1;
577                        } else {
578                            break;
579                        }
580    
581                        if (groupPos == 0) {
582                            groupPos = G_SIZE - 1;
583                            zt = selector[++groupNo] & 0xff;
584                            base_zt = base[zt];
585                            limit_zt = limit[zt];
586                            perm_zt = perm[zt];
587                            minLens_zt = minLens[zt];
588                        } else {
589                            groupPos--;
590                        }
591    
592                        int zn = minLens_zt;
593    
594                        // Inlined:
595                        // int zvec = bsR(zn);
596                        while (bsLiveShadow < zn) {
597                            final int thech = inShadow.read();
598                            if (thech >= 0) {
599                                bsBuffShadow = (bsBuffShadow << 8) | thech;
600                                bsLiveShadow += 8;
601                                continue;
602                            } else {
603                                throw new IOException("unexpected end of stream");
604                            }
605                        }
606                        int zvec = (bsBuffShadow >> (bsLiveShadow - zn))
607                            & ((1 << zn) - 1);
608                        bsLiveShadow -= zn;
609    
610                        while (zvec > limit_zt[zn]) {
611                            zn++;
612                            while (bsLiveShadow < 1) {
613                                final int thech = inShadow.read();
614                                if (thech >= 0) {
615                                    bsBuffShadow = (bsBuffShadow << 8) | thech;
616                                    bsLiveShadow += 8;
617                                    continue;
618                                } else {
619                                    throw new IOException(
620                                                          "unexpected end of stream");
621                                }
622                            }
623                            bsLiveShadow--;
624                            zvec = (zvec << 1)
625                                | ((bsBuffShadow >> bsLiveShadow) & 1);
626                        }
627                        nextSym = perm_zt[zvec - base_zt[zn]];
628                    }
629    
630                    final byte ch = seqToUnseq[yy[0]];
631                    unzftab[ch & 0xff] += s + 1;
632    
633                    while (s-- >= 0) {
634                        ll8[++lastShadow] = ch;
635                    }
636    
637                    if (lastShadow >= limitLast) {
638                        throw new IOException("block overrun");
639                    }
640                } else {
641                    if (++lastShadow >= limitLast) {
642                        throw new IOException("block overrun");
643                    }
644    
645                    final char tmp = yy[nextSym - 1];
646                    unzftab[seqToUnseq[tmp] & 0xff]++;
647                    ll8[lastShadow] = seqToUnseq[tmp];
648    
649                    /*
650                     * This loop is hammered during decompression, hence avoid
651                     * native method call overhead of System.arraycopy for very
652                     * small ranges to copy.
653                     */
654                    if (nextSym <= 16) {
655                        for (int j = nextSym - 1; j > 0;) {
656                            yy[j] = yy[--j];
657                        }
658                    } else {
659                        System.arraycopy(yy, 0, yy, 1, nextSym - 1);
660                    }
661    
662                    yy[0] = tmp;
663    
664                    if (groupPos == 0) {
665                        groupPos = G_SIZE - 1;
666                        zt = selector[++groupNo] & 0xff;
667                        base_zt = base[zt];
668                        limit_zt = limit[zt];
669                        perm_zt = perm[zt];
670                        minLens_zt = minLens[zt];
671                    } else {
672                        groupPos--;
673                    }
674    
675                    int zn = minLens_zt;
676    
677                    // Inlined:
678                    // int zvec = bsR(zn);
679                    while (bsLiveShadow < zn) {
680                        final int thech = inShadow.read();
681                        if (thech >= 0) {
682                            bsBuffShadow = (bsBuffShadow << 8) | thech;
683                            bsLiveShadow += 8;
684                            continue;
685                        } else {
686                            throw new IOException("unexpected end of stream");
687                        }
688                    }
689                    int zvec = (bsBuffShadow >> (bsLiveShadow - zn))
690                        & ((1 << zn) - 1);
691                    bsLiveShadow -= zn;
692    
693                    while (zvec > limit_zt[zn]) {
694                        zn++;
695                        while (bsLiveShadow < 1) {
696                            final int thech = inShadow.read();
697                            if (thech >= 0) {
698                                bsBuffShadow = (bsBuffShadow << 8) | thech;
699                                bsLiveShadow += 8;
700                                continue;
701                            } else {
702                                throw new IOException("unexpected end of stream");
703                            }
704                        }
705                        bsLiveShadow--;
706                        zvec = (zvec << 1) | ((bsBuffShadow >> bsLiveShadow) & 1);
707                    }
708                    nextSym = perm_zt[zvec - base_zt[zn]];
709                }
710            }
711    
712            this.last = lastShadow;
713            this.bsLive = bsLiveShadow;
714            this.bsBuff = bsBuffShadow;
715        }
716    
717        private int getAndMoveToFrontDecode0(final int groupNo) throws IOException {
718            final InputStream inShadow = this.in;
719            final Data dataShadow = this.data;
720            final int zt = dataShadow.selector[groupNo] & 0xff;
721            final int[] limit_zt = dataShadow.limit[zt];
722            int zn = dataShadow.minLens[zt];
723            int zvec = bsR(zn);
724            int bsLiveShadow = this.bsLive;
725            int bsBuffShadow = this.bsBuff;
726    
727            while (zvec > limit_zt[zn]) {
728                zn++;
729                while (bsLiveShadow < 1) {
730                    final int thech = inShadow.read();
731    
732                    if (thech >= 0) {
733                        bsBuffShadow = (bsBuffShadow << 8) | thech;
734                        bsLiveShadow += 8;
735                        continue;
736                    } else {
737                        throw new IOException("unexpected end of stream");
738                    }
739                }
740                bsLiveShadow--;
741                zvec = (zvec << 1) | ((bsBuffShadow >> bsLiveShadow) & 1);
742            }
743    
744            this.bsLive = bsLiveShadow;
745            this.bsBuff = bsBuffShadow;
746    
747            return dataShadow.perm[zt][zvec - dataShadow.base[zt][zn]];
748        }
749    
750        private void setupBlock() throws IOException {
751            if (this.data == null) {
752                return;
753            }
754    
755            final int[] cftab = this.data.cftab;
756            final int[] tt = this.data.initTT(this.last + 1);
757            final byte[] ll8 = this.data.ll8;
758            cftab[0] = 0;
759            System.arraycopy(this.data.unzftab, 0, cftab, 1, 256);
760    
761            for (int i = 1, c = cftab[0]; i <= 256; i++) {
762                c += cftab[i];
763                cftab[i] = c;
764            }
765    
766            for (int i = 0, lastShadow = this.last; i <= lastShadow; i++) {
767                tt[cftab[ll8[i] & 0xff]++] = i;
768            }
769    
770            if ((this.origPtr < 0) || (this.origPtr >= tt.length)) {
771                throw new IOException("stream corrupted");
772            }
773    
774            this.su_tPos = tt[this.origPtr];
775            this.su_count = 0;
776            this.su_i2 = 0;
777            this.su_ch2 = 256; /* not a char and not EOF */
778    
779            if (this.blockRandomised) {
780                this.su_rNToGo = 0;
781                this.su_rTPos = 0;
782                setupRandPartA();
783            } else {
784                setupNoRandPartA();
785            }
786        }
787    
788        private void setupRandPartA() throws IOException {
789            if (this.su_i2 <= this.last) {
790                this.su_chPrev = this.su_ch2;
791                int su_ch2Shadow = this.data.ll8[this.su_tPos] & 0xff;
792                this.su_tPos = this.data.tt[this.su_tPos];
793                if (this.su_rNToGo == 0) {
794                    this.su_rNToGo = Rand.rNums(this.su_rTPos) - 1;
795                    if (++this.su_rTPos == 512) {
796                        this.su_rTPos = 0;
797                    }
798                } else {
799                    this.su_rNToGo--;
800                }
801                this.su_ch2 = su_ch2Shadow ^= (this.su_rNToGo == 1) ? 1 : 0;
802                this.su_i2++;
803                this.currentChar = su_ch2Shadow;
804                this.currentState = RAND_PART_B_STATE;
805                this.crc.updateCRC(su_ch2Shadow);
806            } else {
807                endBlock();
808                initBlock();
809                setupBlock();
810            }
811        }
812    
813        private void setupNoRandPartA() throws IOException {
814            if (this.su_i2 <= this.last) {
815                this.su_chPrev = this.su_ch2;
816                int su_ch2Shadow = this.data.ll8[this.su_tPos] & 0xff;
817                this.su_ch2 = su_ch2Shadow;
818                this.su_tPos = this.data.tt[this.su_tPos];
819                this.su_i2++;
820                this.currentChar = su_ch2Shadow;
821                this.currentState = NO_RAND_PART_B_STATE;
822                this.crc.updateCRC(su_ch2Shadow);
823            } else {
824                this.currentState = NO_RAND_PART_A_STATE;
825                endBlock();
826                initBlock();
827                setupBlock();
828            }
829        }
830    
831        private void setupRandPartB() throws IOException {
832            if (this.su_ch2 != this.su_chPrev) {
833                this.currentState = RAND_PART_A_STATE;
834                this.su_count = 1;
835                setupRandPartA();
836            } else if (++this.su_count >= 4) {
837                this.su_z = (char) (this.data.ll8[this.su_tPos] & 0xff);
838                this.su_tPos = this.data.tt[this.su_tPos];
839                if (this.su_rNToGo == 0) {
840                    this.su_rNToGo = Rand.rNums(this.su_rTPos) - 1;
841                    if (++this.su_rTPos == 512) {
842                        this.su_rTPos = 0;
843                    }
844                } else {
845                    this.su_rNToGo--;
846                }
847                this.su_j2 = 0;
848                this.currentState = RAND_PART_C_STATE;
849                if (this.su_rNToGo == 1) {
850                    this.su_z ^= 1;
851                }
852                setupRandPartC();
853            } else {
854                this.currentState = RAND_PART_A_STATE;
855                setupRandPartA();
856            }
857        }
858    
859        private void setupRandPartC() throws IOException {
860            if (this.su_j2 < this.su_z) {
861                this.currentChar = this.su_ch2;
862                this.crc.updateCRC(this.su_ch2);
863                this.su_j2++;
864            } else {
865                this.currentState = RAND_PART_A_STATE;
866                this.su_i2++;
867                this.su_count = 0;
868                setupRandPartA();
869            }
870        }
871    
872        private void setupNoRandPartB() throws IOException {
873            if (this.su_ch2 != this.su_chPrev) {
874                this.su_count = 1;
875                setupNoRandPartA();
876            } else if (++this.su_count >= 4) {
877                this.su_z = (char) (this.data.ll8[this.su_tPos] & 0xff);
878                this.su_tPos = this.data.tt[this.su_tPos];
879                this.su_j2 = 0;
880                setupNoRandPartC();
881            } else {
882                setupNoRandPartA();
883            }
884        }
885    
886        private void setupNoRandPartC() throws IOException {
887            if (this.su_j2 < this.su_z) {
888                int su_ch2Shadow = this.su_ch2;
889                this.currentChar = su_ch2Shadow;
890                this.crc.updateCRC(su_ch2Shadow);
891                this.su_j2++;
892                this.currentState = NO_RAND_PART_C_STATE;
893            } else {
894                this.su_i2++;
895                this.su_count = 0;
896                setupNoRandPartA();
897            }
898        }
899    
900        private static final class Data extends Object {
901    
902            // (with blockSize 900k)
903            final boolean[] inUse = new boolean[256]; // 256 byte
904    
905            final byte[] seqToUnseq = new byte[256]; // 256 byte
906            final byte[] selector = new byte[MAX_SELECTORS]; // 18002 byte
907            final byte[] selectorMtf = new byte[MAX_SELECTORS]; // 18002 byte
908    
909            /**
910             * Freq table collected to save a pass over the data during
911             * decompression.
912             */
913            final int[] unzftab = new int[256]; // 1024 byte
914    
915            final int[][] limit = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192 byte
916            final int[][] base = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192 byte
917            final int[][] perm = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192 byte
918            final int[] minLens = new int[N_GROUPS]; // 24 byte
919    
920            final int[] cftab = new int[257]; // 1028 byte
921            final char[] getAndMoveToFrontDecode_yy = new char[256]; // 512 byte
922            final char[][] temp_charArray2d = new char[N_GROUPS][MAX_ALPHA_SIZE]; // 3096
923            // byte
924            final byte[] recvDecodingTables_pos = new byte[N_GROUPS]; // 6 byte
925            // ---------------
926            // 60798 byte
927    
928            int[] tt; // 3600000 byte
929            byte[] ll8; // 900000 byte
930    
931            // ---------------
932            // 4560782 byte
933            // ===============
934    
935            Data(int blockSize100k) {
936                super();
937    
938                this.ll8 = new byte[blockSize100k * BZip2Constants.BASEBLOCKSIZE];
939            }
940    
941            /**
942             * Initializes the {@link #tt} array.
943             * 
944             * This method is called when the required length of the array is known.
945             * I don't initialize it at construction time to avoid unneccessary
946             * memory allocation when compressing small files.
947             */
948            final int[] initTT(int length) {
949                int[] ttShadow = this.tt;
950    
951                // tt.length should always be >= length, but theoretically
952                // it can happen, if the compressor mixed small and large
953                // blocks. Normally only the last block will be smaller
954                // than others.
955                if ((ttShadow == null) || (ttShadow.length < length)) {
956                    this.tt = ttShadow = new int[length];
957                }
958    
959                return ttShadow;
960            }
961    
962        }
963    
964        /**
965         * Checks if the signature matches what is expected for a bzip2 file.
966         * 
967         * @param signature
968         *            the bytes to check
969         * @param length
970         *            the number of bytes to check
971         * @return true, if this stream is a bzip2 compressed stream, false otherwise
972         * 
973         * @since Apache Commons Compress 1.1
974         */
975        public static boolean matches(byte[] signature, int length) {
976    
977            if (length < 3) {
978                return false;
979            }
980            
981            if (signature[0] != 'B') {
982                return false;
983            }
984    
985            if (signature[1] != 'Z') {
986                return false;
987            }
988    
989            if (signature[2] != 'h') {
990                return false;
991            }
992            
993            return true;
994        }
995    }