    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    package org.apache.commons.compress.compressors.bzip2;
    020
    021    import java.io.IOException;
    022    import java.io.OutputStream;
    023
    024    import org.apache.commons.compress.compressors.CompressorOutputStream;
    025
    026    /**
    027     * An output stream that compresses into the BZip2 format into another stream.
    028     *
    029     * <p>
    030     * The compression requires large amounts of memory. Thus you should call the
    031     * {@link #close() close()} method as soon as possible, to force
    032     * <tt>BZip2CompressorOutputStream</tt> to release the allocated memory.
    033     * </p>
    034     *
    035     * <p> You can shrink the amount of allocated memory and maybe raise
    036     * the compression speed by choosing a lower blocksize, which in turn
    037     * may cause a lower compression ratio. You can avoid unnecessary
    038     * memory allocation by avoiding using a blocksize which is bigger
    039     * than the size of the input.  </p>
    040     *
    041     * <p> You can compute the memory usage for compressing by the
    042     * following formula: </p>
    043     *
    044     * <pre>
    045     * &lt;code&gt;400k + (9 * blocksize)&lt;/code&gt;.
    046     * </pre>
    047     *
    048     * <p> To get the memory required for decompression by {@link
    049     * BZip2CompressorInputStream} use </p>
    050     *
    051     * <pre>
    052     * &lt;code&gt;65k + (5 * blocksize)&lt;/code&gt;.
    053     * </pre>
    054     *
    055     * <table width="100%" border="1">
    056     * <colgroup> <col width="33%" /> <col width="33%" /> <col width="33%" />
    057     * </colgroup>
    058     * <tr>
    059     * <th colspan="3">Memory usage by blocksize</th>
    060     * </tr>
    061     * <tr>
    062     * <th align="right">Blocksize</th> <th align="right">Compression<br>
    063     * memory usage</th> <th align="right">Decompression<br>
    064     * memory usage</th>
    065     * </tr>
    066     * <tr>
    067     * <td align="right">100k</td>
    068     * <td align="right">1300k</td>
    069     * <td align="right">565k</td>
    070     * </tr>
    071     * <tr>
    072     * <td align="right">200k</td>
    073     * <td align="right">2200k</td>
    074     * <td align="right">1065k</td>
    075     * </tr>
    076     * <tr>
    077     * <td align="right">300k</td>
    078     * <td align="right">3100k</td>
    079     * <td align="right">1565k</td>
    080     * </tr>
    081     * <tr>
    082     * <td align="right">400k</td>
    083     * <td align="right">4000k</td>
    084     * <td align="right">2065k</td>
    085     * </tr>
    086     * <tr>
    087     * <td align="right">500k</td>
    088     * <td align="right">4900k</td>
    089     * <td align="right">2565k</td>
    090     * </tr>
    091     * <tr>
    092     * <td align="right">600k</td>
    093     * <td align="right">5800k</td>
    094     * <td align="right">3065k</td>
    095     * </tr>
    096     * <tr>
    097     * <td align="right">700k</td>
    098     * <td align="right">6700k</td>
    099     * <td align="right">3565k</td>
    100     * </tr>
    101     * <tr>
    102     * <td align="right">800k</td>
    103     * <td align="right">7600k</td>
    104     * <td align="right">4065k</td>
    105     * </tr>
    106     * <tr>
    107     * <td align="right">900k</td>
    108     * <td align="right">8500k</td>
    109     * <td align="right">4565k</td>
    110     * </tr>
    111     * </table>
    112     *
    113     * <p>
    114     * For decompression <tt>BZip2CompressorInputStream</tt> allocates less memory if the
    115     * bzipped input is smaller than one block.
    116     * </p>
    117     *
    118     * <p>
    119     * Instances of this class are not threadsafe.
    120     * </p>
    121     *
    122     * <p>
    123     * TODO: Update to BZip2 1.0.1
    124     * </p>
    125     * @NotThreadSafe
    126     */
    127    public class BZip2CompressorOutputStream extends CompressorOutputStream
    128        implements BZip2Constants {
    129
    130        /**
    131         * The minimum supported blocksize <tt> == 1</tt>.
    132         */
    133        public static final int MIN_BLOCKSIZE = 1;
    134
    135        /**
    136         * The maximum supported blocksize <tt> == 9</tt>.
    137         */
    138        public static final int MAX_BLOCKSIZE = 9;
    139
    140        private static final int SETMASK = (1 << 21);
    141        private static final int CLEARMASK = (~SETMASK);
    142        private static final int GREATER_ICOST = 15;
    143        private static final int LESSER_ICOST = 0;
    144        private static final int SMALL_THRESH = 20;
    145        private static final int DEPTH_THRESH = 10;
    146        private static final int WORK_FACTOR = 30;
    147
    148        /*
    149         * <p> If you are ever unlucky/improbable enough to get a stack
    150         * overflow whilst sorting, increase the following constant and
    151         * try again. In practice I have never seen the stack go above 27
    152         * elems, so the following limit seems very generous.  </p>
    153         */
    154        private static final int QSORT_STACK_SIZE = 1000;
    155
    156        /**
    157         * Knuth's increments seem to work better than Incerpi-Sedgewick here.
    158         * Possibly because the number of elems to sort is usually small, typically
    159         * &lt;= 20.
    160         */
    161        private static final int[] INCS = { 1, 4, 13, 40, 121, 364, 1093, 3280,
    162                                            9841, 29524, 88573, 265720, 797161,
    163                                            2391484 };
    164
    165        private static void hbMakeCodeLengths(final byte[] len, final int[] freq,
    166                                              final Data dat, final int alphaSize,
    167                                              final int maxLen) {
    168            /*
    169             * Nodes and heap entries run from 1. Entry 0 for both the heap and
    170             * nodes is a sentinel.
    171             */
    172            final int[] heap = dat.heap;
    173            final int[] weight = dat.weight;
    174            final int[] parent = dat.parent;
    175
    176            for (int i = alphaSize; --i >= 0;) {
    177                weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
    178            }
    179
    180            for (boolean tooLong = true; tooLong;) {
    181                tooLong = false;
    182
    183                int nNodes = alphaSize;
    184                int nHeap = 0;
    185                heap[0] = 0;
    186                weight[0] = 0;
    187                parent[0] = -2;
    188
    189                for (int i = 1; i <= alphaSize; i++) {
    190                    parent[i] = -1;
    191                    nHeap++;
    192                    heap[nHeap] = i;
    193
    194                    int zz = nHeap;
    195                    int tmp = heap[zz];
    196                    while (weight[tmp] < weight[heap[zz >> 1]]) {
    197                        heap[zz] = heap[zz >> 1];
    198                        zz >>= 1;
    199                    }
    200                    heap[zz] = tmp;
    201                }
    202
    203                while (nHeap > 1) {
    204                    int n1 = heap[1];
    205                    heap[1] = heap[nHeap];
    206                    nHeap--;
    207
    208                    int yy = 0;
    209                    int zz = 1;
    210                    int tmp = heap[1];
    211
    212                    while (true) {
    213                        yy = zz << 1;
    214
    215                        if (yy > nHeap) {
    216                            break;
    217                        }
    218
    219                        if ((yy < nHeap)
    220                            && (weight[heap[yy + 1]] < weight[heap[yy]])) {
    221                            yy++;
    222                        }
    223
    224                        if (weight[tmp] < weight[heap[yy]]) {
    225                            break;
    226                        }
    227
    228                        heap[zz] = heap[yy];
    229                        zz = yy;
    230                    }
    231
    232                    heap[zz] = tmp;
    233
    234                    int n2 = heap[1];
    235                    heap[1] = heap[nHeap];
    236                    nHeap--;
    237
    238                    yy = 0;
    239                    zz = 1;
    240                    tmp = heap[1];
    241
    242                    while (true) {
    243                        yy = zz << 1;
    244
    245                        if (yy > nHeap) {
    246                            break;
    247                        }
    248
    249                        if ((yy < nHeap)
    250                            && (weight[heap[yy + 1]] < weight[heap[yy]])) {
    251                            yy++;
    252                        }
    253
    254                        if (weight[tmp] < weight[heap[yy]]) {
    255                            break;
    256                        }
    257
    258                        heap[zz] = heap[yy];
    259                        zz = yy;
    260                    }
    261
    262                    heap[zz] = tmp;
    263                    nNodes++;
    264                    parent[n1] = parent[n2] = nNodes;
    265
    266                    final int weight_n1 = weight[n1];
    267                    final int weight_n2 = weight[n2];
    268                    weight[nNodes] = ((weight_n1 & 0xffffff00)
    269                                      + (weight_n2 & 0xffffff00))
    270                        | (1 + (((weight_n1 & 0x000000ff)
    271                                 > (weight_n2 & 0x000000ff))
    272                                ? (weight_n1 & 0x000000ff)
    273                                : (weight_n2 & 0x000000ff)));
    274
    275                    parent[nNodes] = -1;
    276                    nHeap++;
    277                    heap[nHeap] = nNodes;
    278
    279                    tmp = 0;
    280                    zz = nHeap;
    281                    tmp = heap[zz];
    282                    final int weight_tmp = weight[tmp];
    283                    while (weight_tmp < weight[heap[zz >> 1]]) {
    284                        heap[zz] = heap[zz >> 1];
    285                        zz >>= 1;
    286                    }
    287                    heap[zz] = tmp;
    288
    289                }
    290
    291                for (int i = 1; i <= alphaSize; i++) {
    292                    int j = 0;
    293                    int k = i;
    294
    295                    for (int parent_k; (parent_k = parent[k]) >= 0;) {
    296                        k = parent_k;
    297                        j++;
    298                    }
    299
    300                    len[i - 1] = (byte) j;
    301                    if (j > maxLen) {
    302                        tooLong = true;
    303                    }
    304                }
    305
    306                if (tooLong) {
    307                    for (int i = 1; i < alphaSize; i++) {
    308                        int j = weight[i] >> 8;
    309                        j = 1 + (j >> 1);
    310                        weight[i] = j << 8;
    311                    }
    312                }
    313            }
    314        }
    315
    316        /**
    317         * Index of the last char in the block, so the block size == last + 1.
    318         */
    319        private int last;
    320
    321        /**
    322         * Index in fmap[] of original string after sorting.
    323         */
    324        private int origPtr;
    325
    326        /**
    327         * Always: in the range 0 .. 9. The current block size is 100000 * this
    328         * number.
    329         */
    330        private final int blockSize100k;
    331
    332        private boolean blockRandomised;
    333
    334        private int bsBuff;
    335        private int bsLive;
    336        private final CRC crc = new CRC();
    337
    338        private int nInUse;
    339
    340        private int nMTF;
    341
    342        /*
    343         * Used when sorting. If too many long comparisons happen, we stop sorting,
    344         * randomise the block slightly, and try again.
    345         */
    346        private int workDone;
    347        private int workLimit;
    348        private boolean firstAttempt;
    349
    350        private int currentChar = -1;
    351        private int runLength = 0;
    352
    353        private int blockCRC;
    354        private int combinedCRC;
    355        private int allowableBlockSize;
    356
    357        /**
    358         * All memory intensive stuff.
    359         */
    360        private Data data;
    361
    362        private OutputStream out;
    363
    364        /**
    365         * Chooses a blocksize based on the given length of the data to compress.
    366         *
    367         * @return The blocksize, between {@link #MIN_BLOCKSIZE} and
    368         *         {@link #MAX_BLOCKSIZE} both inclusive. For a negative
    369         *         <tt>inputLength</tt> this method returns <tt>MAX_BLOCKSIZE</tt>
    370         *         always.
    371         *
    372         * @param inputLength
    373         *            The length of the data which will be compressed by
    374         *            <tt>CBZip2OutputStream</tt>.
    375         */
    376        public static int chooseBlockSize(long inputLength) {
    377            return (inputLength > 0) ? (int) Math
    378                .min((inputLength / 132000) + 1, 9) : MAX_BLOCKSIZE;
    379        }
    380
    381        /**
    382         * Constructs a new <tt>CBZip2OutputStream</tt> with a blocksize of 900k.
    383         *
    384         * @param out
    385         *            the destination stream.
    386         *
    387         * @throws IOException
    388         *             if an I/O error occurs in the specified stream.
    389         * @throws NullPointerException
    390         *             if <code>out == null</code>.
    391         */
    392        public BZip2CompressorOutputStream(final OutputStream out)
    393            throws IOException {
    394            this(out, MAX_BLOCKSIZE);
    395        }
    396
    397        /**
    398         * Constructs a new <tt>CBZip2OutputStream</tt> with specified blocksize.
    399         *
    400         * @param out
    401         *            the destination stream.
    402         * @param blockSize
    403         *            the blockSize as 100k units.
    404         *
    405         * @throws IOException
    406         *             if an I/O error occurs in the specified stream.
    407         * @throws IllegalArgumentException
    408         *             if <code>(blockSize < 1) || (blockSize > 9)</code>.
    409         * @throws NullPointerException
    410         *             if <code>out == null</code>.
    411         *
    412         * @see #MIN_BLOCKSIZE
    413         * @see #MAX_BLOCKSIZE
    414         */
    415        public BZip2CompressorOutputStream(final OutputStream out,
    416                                           final int blockSize)
    417            throws IOException {
    418            super();
    419
    420            if (blockSize < 1) {
    421                throw new IllegalArgumentException("blockSize(" + blockSize
    422                                                   + ") < 1");
    423            }
    424            if (blockSize > 9) {
    425                throw new IllegalArgumentException("blockSize(" + blockSize
    426                                                   + ") > 9");
    427            }
    428
    429            this.blockSize100k = blockSize;
    430            this.out = out;
    431            init();
    432        }
    433
    434        /** {@inheritDoc} */
    435        @Override
    436        public void write(final int b) throws IOException {
    437            if (this.out != null) {
    438                write0(b);
    439            } else {
    440                throw new IOException("closed");
    441            }
    442        }
    443
    444        private void writeRun() throws IOException {
    445            final int lastShadow = this.last;
    446
    447            if (lastShadow < this.allowableBlockSize) {
    448                final int currentCharShadow = this.currentChar;
    449                final Data dataShadow = this.data;
    450                dataShadow.inUse[currentCharShadow] = true;
    451                final byte ch = (byte) currentCharShadow;
    452
    453                int runLengthShadow = this.runLength;
    454                this.crc.updateCRC(currentCharShadow, runLengthShadow);
    455
    456                switch (runLengthShadow) {
    457                case 1:
    458                    dataShadow.block[lastShadow + 2] = ch;
    459                    this.last = lastShadow + 1;
    460                    break;
    461
    462                case 2:
    463                    dataShadow.block[lastShadow + 2] = ch;
    464                    dataShadow.block[lastShadow + 3] = ch;
    465                    this.last = lastShadow + 2;
    466                    break;
    467
    468                case 3: {
    469                    final byte[] block = dataShadow.block;
    470                    block[lastShadow + 2] = ch;
    471                    block[lastShadow + 3] = ch;
    472                    block[lastShadow + 4] = ch;
    473                    this.last = lastShadow + 3;
    474                }
    475                    break;
    476
    477                default: {
    478                    runLengthShadow -= 4;
    479                    dataShadow.inUse[runLengthShadow] = true;
    480                    final byte[] block = dataShadow.block;
    481                    block[lastShadow + 2] = ch;
    482                    block[lastShadow + 3] = ch;
    483                    block[lastShadow + 4] = ch;
    484                    block[lastShadow + 5] = ch;
    485                    block[lastShadow + 6] = (byte) runLengthShadow;
    486                    this.last = lastShadow + 5;
    487                }
    488                    break;
    489
    490                }
    491            } else {
    492                endBlock();
    493                initBlock();
    494                writeRun();
    495            }
    496        }
    497
    498        /**
    499         * Overriden to close the stream.
    500         */
    501        @Override
    502        protected void finalize() throws Throwable {
    503            finish();
    504            super.finalize();
    505        }
    506
    507
    508        public void finish() throws IOException {
    509            if (out != null) {
    510                try {
    511                    if (this.runLength > 0) {
    512                        writeRun();
    513                    }
    514                    this.currentChar = -1;
    515                    endBlock();
    516                    endCompression();
    517                } finally {
    518                    this.out = null;
    519                    this.data = null;
    520                }
    521            }
    522        }
    523
    524        @Override
    525        public void close() throws IOException {
    526            if (out != null) {
    527                OutputStream outShadow = this.out;
    528                finish();
    529                outShadow.close();
    530            }
    531        }
    532
    533        @Override
    534        public void flush() throws IOException {
    535            OutputStream outShadow = this.out;
    536            if (outShadow != null) {
    537                outShadow.flush();
    538            }
    539        }
    540
    541        /**
    542         * Writes magic bytes like BZ on the first position of the stream
    543         * and bytes indiciating the file-format, which is
    544         * huffmanised, followed by a digit indicating blockSize100k.
    545         * @throws IOException if the magic bytes could not been written
    546         */
    547        private void init() throws IOException {
    548            bsPutUByte('B');
    549            bsPutUByte('Z');
    550
    551            this.data = new Data(this.blockSize100k);
    552
    553            // huffmanised magic bytes
    554            bsPutUByte('h');
    555            bsPutUByte('0' + this.blockSize100k);
    556
    557            this.combinedCRC = 0;
    558            initBlock();
    559        }
    560
    561        private void initBlock() {
    562            // blockNo++;
    563            this.crc.initialiseCRC();
    564            this.last = -1;
    565            // ch = 0;
    566
    567            boolean[] inUse = this.data.inUse;
    568            for (int i = 256; --i >= 0;) {
    569                inUse[i] = false;
    570            }
    571
    572            /* 20 is just a paranoia constant */
    573            this.allowableBlockSize = (this.blockSize100k * BZip2Constants.BASEBLOCKSIZE) - 20;
    574        }
    575
    576        private void endBlock() throws IOException {
    577            this.blockCRC = this.crc.getFinalCRC();
    578            this.combinedCRC = (this.combinedCRC << 1) | (this.combinedCRC >>> 31);
    579            this.combinedCRC ^= this.blockCRC;
    580
    581            // empty block at end of file
    582            if (this.last == -1) {
    583                return;
    584            }
    585
    586            /* sort the block and establish posn of original string */
    587            blockSort();
    588
    589            /*
    590             * A 6-byte block header, the value chosen arbitrarily as 0x314159265359
    591             * :-). A 32 bit value does not really give a strong enough guarantee
    592             * that the value will not appear by chance in the compressed
    593             * datastream. Worst-case probability of this event, for a 900k block,
    594             * is about 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48
    595             * bits. For a compressed file of size 100Gb -- about 100000 blocks --
    596             * only a 48-bit marker will do. NB: normal compression/ decompression
    597             * donot rely on these statistical properties. They are only important
    598             * when trying to recover blocks from damaged files.
    599             */
    600            bsPutUByte(0x31);
    601            bsPutUByte(0x41);
    602            bsPutUByte(0x59);
    603            bsPutUByte(0x26);
    604            bsPutUByte(0x53);
    605            bsPutUByte(0x59);
    606
    607            /* Now the block's CRC, so it is in a known place. */
    608            bsPutInt(this.blockCRC);
    609
    610            /* Now a single bit indicating randomisation. */
    611            if (this.blockRandomised) {
    612                bsW(1, 1);
    613            } else {
    614                bsW(1, 0);
    615            }
    616
    617            /* Finally, block's contents proper. */
    618            moveToFrontCodeAndSend();
    619        }
    620
    621        private void endCompression() throws IOException {
    622            /*
    623             * Now another magic 48-bit number, 0x177245385090, to indicate the end
    624             * of the last block. (sqrt(pi), if you want to know. I did want to use
    625             * e, but it contains too much repetition -- 27 18 28 18 28 46 -- for me
    626             * to feel statistically comfortable. Call me paranoid.)
    627             */
    628            bsPutUByte(0x17);
    629            bsPutUByte(0x72);
    630            bsPutUByte(0x45);
    631            bsPutUByte(0x38);
    632            bsPutUByte(0x50);
    633            bsPutUByte(0x90);
    634
    635            bsPutInt(this.combinedCRC);
    636            bsFinishedWithStream();
    637        }
    638
    639        /**
    640         * Returns the blocksize parameter specified at construction time.
    641         */
    642        public final int getBlockSize() {
    643            return this.blockSize100k;
    644        }
    645
    646        @Override
    647        public void write(final byte[] buf, int offs, final int len)
    648            throws IOException {
    649            if (offs < 0) {
    650                throw new IndexOutOfBoundsException("offs(" + offs + ") < 0.");
    651            }
    652            if (len < 0) {
    653                throw new IndexOutOfBoundsException("len(" + len + ") < 0.");
    654            }
    655            if (offs + len > buf.length) {
    656                throw new IndexOutOfBoundsException("offs(" + offs + ") + len("
    657                                                    + len + ") > buf.length("
    658                                                    + buf.length + ").");
    659            }
    660            if (this.out == null) {
    661                throw new IOException("stream closed");
    662            }
    663
    664            for (int hi = offs + len; offs < hi;) {
    665                write0(buf[offs++]);
    666            }
    667        }
    668
    669        private void write0(int b) throws IOException {
    670            if (this.currentChar != -1) {
    671                b &= 0xff;
    672                if (this.currentChar == b) {
    673                    if (++this.runLength > 254) {
    674                        writeRun();
    675                        this.currentChar = -1;
    676                        this.runLength = 0;
    677                    }
    678                    // else nothing to do
    679                } else {
    680                    writeRun();
    681                    this.runLength = 1;
    682                    this.currentChar = b;
    683                }
    684            } else {
    685                this.currentChar = b & 0xff;
    686                this.runLength++;
    687            }
    688        }
    689
    690        private static void hbAssignCodes(final int[] code, final byte[] length,
    691                                          final int minLen, final int maxLen,
    692                                          final int alphaSize) {
    693            int vec = 0;
    694            for (int n = minLen; n <= maxLen; n++) {
    695                for (int i = 0; i < alphaSize; i++) {
    696                    if ((length[i] & 0xff) == n) {
    697                        code[i] = vec;
    698                        vec++;
    699                    }
    700                }
    701                vec <<= 1;
    702            }
    703        }
    704
    705        private void bsFinishedWithStream() throws IOException {
    706            while (this.bsLive > 0) {
    707                int ch = this.bsBuff >> 24;
    708                this.out.write(ch); // write 8-bit
    709                this.bsBuff <<= 8;
    710                this.bsLive -= 8;
    711            }
    712        }
    713
    714        private void bsW(final int n, final int v) throws IOException {
    715            final OutputStream outShadow = this.out;
    716            int bsLiveShadow = this.bsLive;
    717            int bsBuffShadow = this.bsBuff;
    718
    719            while (bsLiveShadow >= 8) {
    720                outShadow.write(bsBuffShadow >> 24); // write 8-bit
    721                bsBuffShadow <<= 8;
    722                bsLiveShadow -= 8;
    723            }
    724
    725            this.bsBuff = bsBuffShadow | (v << (32 - bsLiveShadow - n));
    726            this.bsLive = bsLiveShadow + n;
    727        }
    728
    729        private void bsPutUByte(final int c) throws IOException {
    730            bsW(8, c);
    731        }
    732
    733        private void bsPutInt(final int u) throws IOException {
    734            bsW(8, (u >> 24) & 0xff);
    735            bsW(8, (u >> 16) & 0xff);
    736            bsW(8, (u >> 8) & 0xff);
    737            bsW(8, u & 0xff);
    738        }
    739
    740        private void sendMTFValues() throws IOException {
    741            final byte[][] len = this.data.sendMTFValues_len;
    742            final int alphaSize = this.nInUse + 2;
    743
    744            for (int t = N_GROUPS; --t >= 0;) {
    745                byte[] len_t = len[t];
    746                for (int v = alphaSize; --v >= 0;) {
    747                    len_t[v] = GREATER_ICOST;
    748                }
    749            }
    750
    751            /* Decide how many coding tables to use */
    752            // assert (this.nMTF > 0) : this.nMTF;
    753            final int nGroups = (this.nMTF < 200) ? 2 : (this.nMTF < 600) ? 3
    754                : (this.nMTF < 1200) ? 4 : (this.nMTF < 2400) ? 5 : 6;
    755
    756            /* Generate an initial set of coding tables */
    757            sendMTFValues0(nGroups, alphaSize);
    758
    759            /*
    760             * Iterate up to N_ITERS times to improve the tables.
    761             */
    762            final int nSelectors = sendMTFValues1(nGroups, alphaSize);
    763
    764            /* Compute MTF values for the selectors. */
    765            sendMTFValues2(nGroups, nSelectors);
    766
    767            /* Assign actual codes for the tables. */
    768            sendMTFValues3(nGroups, alphaSize);
    769
    770            /* Transmit the mapping table. */
    771            sendMTFValues4();
    772
    773            /* Now the selectors. */
    774            sendMTFValues5(nGroups, nSelectors);
    775
    776            /* Now the coding tables. */
    777            sendMTFValues6(nGroups, alphaSize);
    778
    779            /* And finally, the block data proper */
    780            sendMTFValues7();
    781        }
    782
    783        private void sendMTFValues0(final int nGroups, final int alphaSize) {
    784            final byte[][] len = this.data.sendMTFValues_len;
    785            final int[] mtfFreq = this.data.mtfFreq;
    786
    787            int remF = this.nMTF;
    788            int gs = 0;
    789
    790            for (int nPart = nGroups; nPart > 0; nPart--) {
    791                final int tFreq = remF / nPart;
    792                int ge = gs - 1;
    793                int aFreq = 0;
    794
    795                for (final int a = alphaSize - 1; (aFreq < tFreq) && (ge < a);) {
    796                    aFreq += mtfFreq[++ge];
    797                }
    798
    799                if ((ge > gs) && (nPart != nGroups) && (nPart != 1)
    800                    && (((nGroups - nPart) & 1) != 0)) {
    801                    aFreq -= mtfFreq[ge--];
    802                }
    803
    804                final byte[] len_np = len[nPart - 1];
    805                for (int v = alphaSize; --v >= 0;) {
    806                    if ((v >= gs) && (v <= ge)) {
    807                        len_np[v] = LESSER_ICOST;
    808                    } else {
    809                        len_np[v] = GREATER_ICOST;
    810                    }
    811                }
    812
    813                gs = ge + 1;
    814                remF -= aFreq;
    815            }
    816        }
    817
    818        private int sendMTFValues1(final int nGroups, final int alphaSize) {
    819            final Data dataShadow = this.data;
    820            final int[][] rfreq = dataShadow.sendMTFValues_rfreq;
    821            final int[] fave = dataShadow.sendMTFValues_fave;
    822            final short[] cost = dataShadow.sendMTFValues_cost;
    823            final char[] sfmap = dataShadow.sfmap;
    824            final byte[] selector = dataShadow.selector;
    825            final byte[][] len = dataShadow.sendMTFValues_len;
    826            final byte[] len_0 = len[0];
    827            final byte[] len_1 = len[1];
    828            final byte[] len_2 = len[2];
    829            final byte[] len_3 = len[3];
    830            final byte[] len_4 = len[4];
    831            final byte[] len_5 = len[5];
    832            final int nMTFShadow = this.nMTF;
    833
    834            int nSelectors = 0;
    835
    836            for (int iter = 0; iter < N_ITERS; iter++) {
    837                for (int t = nGroups; --t >= 0;) {
    838                    fave[t] = 0;
    839                    int[] rfreqt = rfreq[t];
    840                    for (int i = alphaSize; --i >= 0;) {
    841                        rfreqt[i] = 0;
    842                    }
    843                }
    844
    845                nSelectors = 0;
    846
    847                for (int gs = 0; gs < this.nMTF;) {
    848                    /* Set group start & end marks. */
    849
    850                    /*
    851                     * Calculate the cost of this group as coded by each of the
    852                     * coding tables.
    853                     */
    854
    855                    final int ge = Math.min(gs + G_SIZE - 1, nMTFShadow - 1);
    856
    857                    if (nGroups == N_GROUPS) {
    858                        // unrolled version of the else-block
    859
    860                        short cost0 = 0;
    861                        short cost1 = 0;
    862                        short cost2 = 0;
    863                        short cost3 = 0;
    864                        short cost4 = 0;
    865                        short cost5 = 0;
    866
    867                        for (int i = gs; i <= ge; i++) {
    868                            final int icv = sfmap[i];
    869                            cost0 += len_0[icv] & 0xff;
    870                            cost1 += len_1[icv] & 0xff;
    871                            cost2 += len_2[icv] & 0xff;
    872                            cost3 += len_3[icv] & 0xff;
    873                            cost4 += len_4[icv] & 0xff;
    874                            cost5 += len_5[icv] & 0xff;
    875                        }
    876
    877                        cost[0] = cost0;
    878                        cost[1] = cost1;
    879                        cost[2] = cost2;
    880                        cost[3] = cost3;
    881                        cost[4] = cost4;
    882                        cost[5] = cost5;
    883
    884                    } else {
    885                        for (int t = nGroups; --t >= 0;) {
    886                            cost[t] = 0;
    887                        }
    888
    889                        for (int i = gs; i <= ge; i++) {
    890                            final int icv = sfmap[i];
    891                            for (int t = nGroups; --t >= 0;) {
    892                                cost[t] += len[t][icv] & 0xff;
    893                            }
    894                        }
    895                    }
    896
    897                    /*
    898                     * Find the coding table which is best for this group, and
    899                     * record its identity in the selector table.
    900                     */
    901                    int bt = -1;
    902                    for (int t = nGroups, bc = 999999999; --t >= 0;) {
    903                        final int cost_t = cost[t];
    904                        if (cost_t < bc) {
    905                            bc = cost_t;
    906                            bt = t;
    907                        }
    908                    }
    909
    910                    fave[bt]++;
    911                    selector[nSelectors] = (byte) bt;
    912                    nSelectors++;
    913
    914                    /*
    915                     * Increment the symbol frequencies for the selected table.
    916                     */
    917                    final int[] rfreq_bt = rfreq[bt];
    918                    for (int i = gs; i <= ge; i++) {
    919                        rfreq_bt[sfmap[i]]++;
    920                    }
    921
    922                    gs = ge + 1;
    923                }
    924
    925                /*
    926                 * Recompute the tables based on the accumulated frequencies.
    927                 */
    928                for (int t = 0; t < nGroups; t++) {
    929                    hbMakeCodeLengths(len[t], rfreq[t], this.data, alphaSize, 20);
    930                }
    931            }
    932
    933            return nSelectors;
    934        }
    935
    936        private void sendMTFValues2(final int nGroups, final int nSelectors) {
    937            // assert (nGroups < 8) : nGroups;
    938
    939            final Data dataShadow = this.data;
    940            byte[] pos = dataShadow.sendMTFValues2_pos;
    941
    942            for (int i = nGroups; --i >= 0;) {
    943                pos[i] = (byte) i;
    944            }
    945
    946            for (int i = 0; i < nSelectors; i++) {
    947                final byte ll_i = dataShadow.selector[i];
    948                byte tmp = pos[0];
    949                int j = 0;
    950
    951                while (ll_i != tmp) {
    952                    j++;
    953                    byte tmp2 = tmp;
    954                    tmp = pos[j];
    955                    pos[j] = tmp2;
    956                }
    957
    958                pos[0] = tmp;
    959                dataShadow.selectorMtf[i] = (byte) j;
    960            }
    961        }
    962
    963        private void sendMTFValues3(final int nGroups, final int alphaSize) {
    964            int[][] code = this.data.sendMTFValues_code;
    965            byte[][] len = this.data.sendMTFValues_len;
    966
    967            for (int t = 0; t < nGroups; t++) {
    968                int minLen = 32;
    969                int maxLen = 0;
    970                final byte[] len_t = len[t];
    971                for (int i = alphaSize; --i >= 0;) {
    972                    final int l = len_t[i] & 0xff;
    973                    if (l > maxLen) {
    974                        maxLen = l;
    975                    }
    976                    if (l < minLen) {
    977                        minLen = l;
    978                    }
    979                }
    980
    981                // assert (maxLen <= 20) : maxLen;
    982                // assert (minLen >= 1) : minLen;
    983
    984                hbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
    985            }
    986        }
    987
    988        private void sendMTFValues4() throws IOException {
    989            final boolean[] inUse = this.data.inUse;
    990            final boolean[] inUse16 = this.data.sentMTFValues4_inUse16;
    991
    992            for (int i = 16; --i >= 0;) {
    993                inUse16[i] = false;
    994                final int i16 = i * 16;
    995                for (int j = 16; --j >= 0;) {
    996                    if (inUse[i16 + j]) {
    997                        inUse16[i] = true;
    998                    }
    999                }
    1000            }
    1001
    1002            for (int i = 0; i < 16; i++) {
    1003                bsW(1, inUse16[i] ? 1 : 0);
    1004            }
    1005
    1006            final OutputStream outShadow = this.out;
    1007            int bsLiveShadow = this.bsLive;
    1008            int bsBuffShadow = this.bsBuff;
    1009
    1010            for (int i = 0; i < 16; i++) {
    1011                if (inUse16[i]) {
    1012                    final int i16 = i * 16;
    1013                    for (int j = 0; j < 16; j++) {
    1014                        // inlined: bsW(1, inUse[i16 + j] ? 1 : 0);
    1015                        while (bsLiveShadow >= 8) {
    1016                            outShadow.write(bsBuffShadow >> 24); // write 8-bit
    1017                            bsBuffShadow <<= 8;
    1018                            bsLiveShadow -= 8;
    1019                        }
    1020                        if (inUse[i16 + j]) {
    1021                            bsBuffShadow |= 1 << (32 - bsLiveShadow - 1);
    1022                        }
    1023                        bsLiveShadow++;
    1024                    }
    1025                }
    1026            }
    1027
    1028            this.bsBuff = bsBuffShadow;
    1029            this.bsLive = bsLiveShadow;
    1030        }
    1031
    1032        private void sendMTFValues5(final int nGroups, final int nSelectors)
    1033            throws IOException {
    1034            bsW(3, nGroups);
    1035            bsW(15, nSelectors);
    1036
    1037            final OutputStream outShadow = this.out;
    1038            final byte[] selectorMtf = this.data.selectorMtf;
    1039
    1040            int bsLiveShadow = this.bsLive;
    1041            int bsBuffShadow = this.bsBuff;
    1042
    1043            for (int i = 0; i < nSelectors; i++) {
    1044                for (int j = 0, hj = selectorMtf[i] & 0xff; j < hj; j++) {
    1045                    // inlined: bsW(1, 1);
    1046                    while (bsLiveShadow >= 8) {
    1047                        outShadow.write(bsBuffShadow >> 24);
    1048                        bsBuffShadow <<= 8;
    1049                        bsLiveShadow -= 8;
    1050                    }
    1051                    bsBuffShadow |= 1 << (32 - bsLiveShadow - 1);
    1052                    bsLiveShadow++;
    1053                }
    1054
    1055                // inlined: bsW(1, 0);
    1056                while (bsLiveShadow >= 8) {
    1057                    outShadow.write(bsBuffShadow >> 24);
    1058                    bsBuffShadow <<= 8;
    1059                    bsLiveShadow -= 8;
    1060                }
    1061                // bsBuffShadow |= 0 << (32 - bsLiveShadow - 1);
    1062                bsLiveShadow++;
    1063            }
    1064
    1065            this.bsBuff = bsBuffShadow;
    1066            this.bsLive = bsLiveShadow;
    1067        }
    1068
    1069        private void sendMTFValues6(final int nGroups, final int alphaSize)
    1070            throws IOException {
    1071            final byte[][] len = this.data.sendMTFValues_len;
    1072            final OutputStream outShadow = this.out;
    1073
    1074            int bsLiveShadow = this.bsLive;
    1075            int bsBuffShadow = this.bsBuff;
    1076
    1077            for (int t = 0; t < nGroups; t++) {
    1078                byte[] len_t = len[t];
    1079                int curr = len_t[0] & 0xff;
    1080
    1081                // inlined: bsW(5, curr);
    1082                while (bsLiveShadow >= 8) {
    1083                    outShadow.write(bsBuffShadow >> 24); // write 8-bit
    1084                    bsBuffShadow <<= 8;
    1085                    bsLiveShadow -= 8;
    1086                }
    1087                bsBuffShadow |= curr << (32 - bsLiveShadow - 5);
    1088                bsLiveShadow += 5;
    1089
    1090                for (int i = 0; i < alphaSize; i++) {
    1091                    int lti = len_t[i] & 0xff;
    1092                    while (curr < lti) {
    1093                        // inlined: bsW(2, 2);
    1094                        while (bsLiveShadow >= 8) {
    1095                            outShadow.write(bsBuffShadow >> 24); // write 8-bit
    1096                            bsBuffShadow <<= 8;
    1097                            bsLiveShadow -= 8;
    1098                        }
    1099                        bsBuffShadow |= 2 << (32 - bsLiveShadow - 2);
    1100                        bsLiveShadow += 2;
    1101
    1102                        curr++; /* 10 */
    1103                    }
    1104
    1105                    while (curr > lti) {
    1106                        // inlined: bsW(2, 3);
    1107                        while (bsLiveShadow >= 8) {
    1108                            outShadow.write(bsBuffShadow >> 24); // write 8-bit
    1109                            bsBuffShadow <<= 8;
    1110                            bsLiveShadow -= 8;
    1111                        }
    1112                        bsBuffShadow |= 3 << (32 - bsLiveShadow - 2);
    1113                        bsLiveShadow += 2;
    1114
    1115                        curr--; /* 11 */
    1116                    }
    1117
    1118                    // inlined: bsW(1, 0);
    1119                    while (bsLiveShadow >= 8) {
    1120                        outShadow.write(bsBuffShadow >> 24); // write 8-bit
    1121                        bsBuffShadow <<= 8;
    1122                        bsLiveShadow -= 8;
    1123                    }
    1124                    // bsBuffShadow |= 0 << (32 - bsLiveShadow - 1);
    1125                    bsLiveShadow++;
    1126                }
    1127            }
    1128
    1129            this.bsBuff = bsBuffShadow;
    1130            this.bsLive = bsLiveShadow;
    1131        }
    1132
    1133        private void sendMTFValues7() throws IOException {
    1134            final Data dataShadow = this.data;
    1135            final byte[][] len = dataShadow.sendMTFValues_len;
    1136            final int[][] code = dataShadow.sendMTFValues_code;
    1137            final OutputStream outShadow = this.out;
    1138            final byte[] selector = dataShadow.selector;
    1139            final char[] sfmap = dataShadow.sfmap;
    1140            final int nMTFShadow = this.nMTF;
    1141
    1142            int selCtr = 0;
    1143
    1144            int bsLiveShadow = this.bsLive;
    1145            int bsBuffShadow = this.bsBuff;
    1146
    1147            for (int gs = 0; gs < nMTFShadow;) {
    1148                final int ge = Math.min(gs + G_SIZE - 1, nMTFShadow - 1);
    1149                final int selector_selCtr = selector[selCtr] & 0xff;
    1150                final int[] code_selCtr = code[selector_selCtr];
    1151                final byte[] len_selCtr = len[selector_selCtr];
    1152
    1153                while (gs <= ge) {
    1154                    final int sfmap_i = sfmap[gs];
    1155
    1156                    //
    1157                    // inlined: bsW(len_selCtr[sfmap_i] & 0xff,
    1158                    // code_selCtr[sfmap_i]);
    1159                    //
    1160                    while (bsLiveShadow >= 8) {
    1161                        outShadow.write(bsBuffShadow >> 24);
    1162                        bsBuffShadow <<= 8;
    1163                        bsLiveShadow -= 8;
    1164                    }
    1165                    final int n = len_selCtr[sfmap_i] & 0xFF;
    1166                    bsBuffShadow |= code_selCtr[sfmap_i] << (32 - bsLiveShadow - n);
    1167                    bsLiveShadow += n;
    1168
    1169                    gs++;
    1170                }
    1171
    1172                gs = ge + 1;
    1173                selCtr++;
    1174            }
    1175
    1176            this.bsBuff = bsBuffShadow;
    1177            this.bsLive = bsLiveShadow;
    1178        }
    1179
    1180        private void moveToFrontCodeAndSend() throws IOException {
    1181            bsW(24, this.origPtr);
    1182            generateMTFValues();
    1183            sendMTFValues();
    1184        }
    1185
    1186        /**
    1187         * This is the most hammered method of this class.
    1188         *
    1189         * <p>
    1190         * This is the version using unrolled loops. Normally I never use such ones
    1191         * in Java code. The unrolling has shown a noticable performance improvement
    1192         * on JRE 1.4.2 (Linux i586 / HotSpot Client). Of course it depends on the
    1193         * JIT compiler of the vm.
    1194         * </p>
    1195         */
    1196        private boolean mainSimpleSort(final Data dataShadow, final int lo,
    1197                                       final int hi, final int d) {
    1198            final int bigN = hi - lo + 1;
    1199            if (bigN < 2) {
    1200                return this.firstAttempt && (this.workDone > this.workLimit);
    1201            }
    1202
    1203            int hp = 0;
    1204            while (INCS[hp] < bigN) {
    1205                hp++;
    1206            }
    1207
    1208            final int[] fmap = dataShadow.fmap;
    1209            final char[] quadrant = dataShadow.quadrant;
    1210            final byte[] block = dataShadow.block;
    1211            final int lastShadow = this.last;
    1212            final int lastPlus1 = lastShadow + 1;
    1213            final boolean firstAttemptShadow = this.firstAttempt;
    1214            final int workLimitShadow = this.workLimit;
    1215            int workDoneShadow = this.workDone;
    1216
    1217            // Following block contains unrolled code which could be shortened by
    1218            // coding it in additional loops.
    1219
    1220            HP: while (--hp >= 0) {
    1221                final int h = INCS[hp];
    1222                final int mj = lo + h - 1;
    1223
    1224                for (int i = lo + h; i <= hi;) {
    1225                    // copy
    1226                    for (int k = 3; (i <= hi) && (--k >= 0); i++) {
    1227                        final int v = fmap[i];
    1228                        final int vd = v + d;
    1229                        int j = i;
    1230
    1231                        // for (int a;
    1232                        // (j > mj) && mainGtU((a = fmap[j - h]) + d, vd,
    1233                        // block, quadrant, lastShadow);
    1234                        // j -= h) {
    1235                        // fmap[j] = a;
    1236                        // }
    1237                        //
    1238                        // unrolled version:
    1239
    1240                        // start inline mainGTU
    1241                        boolean onceRunned = false;
    1242                        int a = 0;
    1243
    1244                        HAMMER: while (true) {
    1245                            if (onceRunned) {
    1246                                fmap[j] = a;
    1247                                if ((j -= h) <= mj) {
    1248                                    break HAMMER;
    1249                                }
    1250                            } else {
    1251                                onceRunned = true;
    1252                            }
    1253
    1254                            a = fmap[j - h];
    1255                            int i1 = a + d;
    1256                            int i2 = vd;
    1257
    1258                            // following could be done in a loop, but
    1259                            // unrolled it for performance:
    1260                            if (block[i1 + 1] == block[i2 + 1]) {
    1261                                if (block[i1 + 2] == block[i2 + 2]) {
    1262                                    if (block[i1 + 3] == block[i2 + 3]) {
    1263                                        if (block[i1 + 4] == block[i2 + 4]) {
    1264                                            if (block[i1 + 5] == block[i2 + 5]) {
    1265                                                if (block[(i1 += 6)] == block[(i2 += 6)]) {
    1266                                                    int x = lastShadow;
    1267                                                    X: while (x > 0) {
    1268                                                        x -= 4;
    1269
    1270                                                        if (block[i1 + 1] == block[i2 + 1]) {
    1271                                                            if (quadrant[i1] == quadrant[i2]) {
    1272                                                                if (block[i1 + 2] == block[i2 + 2]) {
    1273                                                                    if (quadrant[i1 + 1] == quadrant[i2 + 1]) {
    1274                                                                        if (block[i1 + 3] == block[i2 + 3]) {
    1275                                                                            if (quadrant[i1 + 2] == quadrant[i2 + 2]) {
    1276                                                                                if (block[i1 + 4] == block[i2 + 4]) {
    1277                                                                                    if (quadrant[i1 + 3] == quadrant[i2 + 3]) {
    1278                                                                                        if ((i1 += 4) >= lastPlus1) {
    1279                                                                                            i1 -= lastPlus1;
    1280                                                                                        }
    1281                                                                                        if ((i2 += 4) >= lastPlus1) {
    1282                                                                                            i2 -= lastPlus1;
    1283                                                                                        }
    1284                                                                                        workDoneShadow++;
    1285                                                                                        continue X;
    1286                                                                                    } else if ((quadrant[i1 + 3] > quadrant[i2 + 3])) {
    1287                                                                                        continue HAMMER;
    1288                                                                                    } else {
    1289                                                                                        break HAMMER;
    1290                                                                                    }
    1291                                                                                } else if ((block[i1 + 4] & 0xff) > (block[i2 + 4] & 0xff)) {
    1292                                                                                    continue HAMMER;
    1293                                                                                } else {
    1294                                                                                    break HAMMER;
    1295                                                                                }
    1296                                                                            } else if ((quadrant[i1 + 2] > quadrant[i2 + 2])) {
    1297                                                                                continue HAMMER;
    1298                                                                            } else {
    1299                                                                                break HAMMER;
    1300                                                                            }
    1301                                                                        } else if ((block[i1 + 3] & 0xff) > (block[i2 + 3] & 0xff)) {
    1302                                                                            continue HAMMER;
    1303                                                                        } else {
    1304                                                                            break HAMMER;
    1305                                                                        }
    1306                                                                    } else if ((quadrant[i1 + 1] > quadrant[i2 + 1])) {
    1307                                                                        continue HAMMER;
    1308                                                                    } else {
    1309                                                                        break HAMMER;
    1310                                                                    }
    1311                                                                } else if ((block[i1 + 2] & 0xff) > (block[i2 + 2] & 0xff)) {
    1312                                                                    continue HAMMER;
    1313                                                                } else {
    1314                                                                    break HAMMER;
    1315                                                                }
    1316                                                            } else if ((quadrant[i1] > quadrant[i2])) {
    1317                                                                continue HAMMER;
    1318                                                            } else {
    1319                                                                break HAMMER;
    1320                                                            }
    1321                                                        } else if ((block[i1 + 1] & 0xff) > (block[i2 + 1] & 0xff)) {
    1322                                                            continue HAMMER;
    1323                                                        } else {
    1324                                                            break HAMMER;
    1325                                                        }
    1326
    1327                                                    }
    1328                                                    break HAMMER;
    1329                                                } // while x > 0
    1330                                                else {
    1331                                                    if ((block[i1] & 0xff) > (block[i2] & 0xff)) {
    1332                                                        continue HAMMER;
    1333                                                    } else {
    1334                                                        break HAMMER;
    1335                                                    }
    1336                                                }
    1337                                            } else if ((block[i1 + 5] & 0xff) > (block[i2 + 5] & 0xff)) {
    1338                                                continue HAMMER;
    1339                                            } else {
    1340                                                break HAMMER;
    1341                                            }
    1342                                        } else if ((block[i1 + 4] & 0xff) > (block[i2 + 4] & 0xff)) {
    1343                                            continue HAMMER;
    1344                                        } else {
    1345                                            break HAMMER;
    1346                                        }
    1347                                    } else if ((block[i1 + 3] & 0xff) > (block[i2 + 3] & 0xff)) {
    1348                                        continue HAMMER;
    1349                                    } else {
    1350                                        break HAMMER;
    1351                                    }
    1352                                } else if ((block[i1 + 2] & 0xff) > (block[i2 + 2] & 0xff)) {
    1353                                    continue HAMMER;
    1354                                } else {
    1355                                    break HAMMER;
    1356                                }
    1357                            } else if ((block[i1 + 1] & 0xff) > (block[i2 + 1] & 0xff)) {
    1358                                continue HAMMER;
    1359                            } else {
    1360                                break HAMMER;
    1361                            }
    1362
    1363                        } // HAMMER
    1364                        // end inline mainGTU
    1365
    1366                        fmap[j] = v;
    1367                    }
    1368
    1369                    if (firstAttemptShadow && (i <= hi)
    1370                        && (workDoneShadow > workLimitShadow)) {
    1371                        break HP;
    1372                    }
    1373                }
    1374            }
    1375
    1376            this.workDone = workDoneShadow;
    1377            return firstAttemptShadow && (workDoneShadow > workLimitShadow);
    1378        }
    1379
    1380        private static void vswap(int[] fmap, int p1, int p2, int n) {
    1381            n += p1;
    1382            while (p1 < n) {
    1383                int t = fmap[p1];
    1384                fmap[p1++] = fmap[p2];
    1385                fmap[p2++] = t;
    1386            }
    1387        }
    1388
    1389        private static byte med3(byte a, byte b, byte c) {
    1390            return (a < b) ? (b < c ? b : a < c ? c : a) : (b > c ? b : a > c ? c
    1391                                                            : a);
    1392        }
    1393
    1394        private void blockSort() {
    1395            this.workLimit = WORK_FACTOR * this.last;
    1396            this.workDone = 0;
    1397            this.blockRandomised = false;
    1398            this.firstAttempt = true;
    1399            mainSort();
    1400
    1401            if (this.firstAttempt && (this.workDone > this.workLimit)) {
    1402                randomiseBlock();
    1403                this.workLimit = this.workDone = 0;
    1404                this.firstAttempt = false;
    1405                mainSort();
    1406            }
    1407
    1408            int[] fmap = this.data.fmap;
    1409            this.origPtr = -1;
    1410            for (int i = 0, lastShadow = this.last; i <= lastShadow; i++) {
    1411                if (fmap[i] == 0) {
    1412                    this.origPtr = i;
    1413                    break;
    1414                }
    1415            }
    1416
    1417            // assert (this.origPtr != -1) : this.origPtr;
    1418        }
    1419
    1420        /**
    1421         * Method "mainQSort3", file "blocksort.c", BZip2 1.0.2
    1422         */
    1423        private void mainQSort3(final Data dataShadow, final int loSt,
    1424                                final int hiSt, final int dSt) {
    1425            final int[] stack_ll = dataShadow.stack_ll;
    1426            final int[] stack_hh = dataShadow.stack_hh;
    1427            final int[] stack_dd = dataShadow.stack_dd;
    1428            final int[] fmap = dataShadow.fmap;
    1429            final byte[] block = dataShadow.block;
    1430
    1431            stack_ll[0] = loSt;
    1432            stack_hh[0] = hiSt;
    1433            stack_dd[0] = dSt;
    1434
    1435            for (int sp = 1; --sp >= 0;) {
    1436                final int lo = stack_ll[sp];
    1437                final int hi = stack_hh[sp];
    1438                final int d = stack_dd[sp];
    1439
    1440                if ((hi - lo < SMALL_THRESH) || (d > DEPTH_THRESH)) {
    1441                    if (mainSimpleSort(dataShadow, lo, hi, d)) {
    1442                        return;
    1443                    }
    1444                } else {
    1445                    final int d1 = d + 1;
    1446                    final int med = med3(block[fmap[lo] + d1],
    1447                                         block[fmap[hi] + d1], block[fmap[(lo + hi) >>> 1] + d1]) & 0xff;
    1448
    1449                    int unLo = lo;
    1450                    int unHi = hi;
    1451                    int ltLo = lo;
    1452                    int gtHi = hi;
    1453
    1454                    while (true) {
    1455                        while (unLo <= unHi) {
    1456                            final int n = (block[fmap[unLo] + d1] & 0xff)
    1457                                - med;
    1458                            if (n == 0) {
    1459                                final int temp = fmap[unLo];
    1460                                fmap[unLo++] = fmap[ltLo];
    1461                                fmap[ltLo++] = temp;
    1462                            } else if (n < 0) {
    1463                                unLo++;
    1464                            } else {
    1465                                break;
    1466                            }
    1467                        }
    1468
    1469                        while (unLo <= unHi) {
    1470                            final int n = (block[fmap[unHi] + d1] & 0xff)
    1471                                - med;
    1472                            if (n == 0) {
    1473                                final int temp = fmap[unHi];
    1474                                fmap[unHi--] = fmap[gtHi];
    1475                                fmap[gtHi--] = temp;
    1476                            } else if (n > 0) {
    1477                                unHi--;
    1478                            } else {
    1479                                break;
    1480                            }
    1481                        }
    1482
    1483                        if (unLo <= unHi) {
    1484                            final int temp = fmap[unLo];
    1485                            fmap[unLo++] = fmap[unHi];
    1486                            fmap[unHi--] = temp;
    1487                        } else {
    1488                            break;
    1489                        }
    1490                    }
    1491
    1492                    if (gtHi < ltLo) {
    1493                        stack_ll[sp] = lo;
    1494                        stack_hh[sp] = hi;
    1495                        stack_dd[sp] = d1;
    1496                        sp++;
    1497                    } else {
    1498                        int n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo)
    1499                            : (unLo - ltLo);
    1500                        vswap(fmap, lo, unLo - n, n);
    1501                        int m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi)
    1502                            : (gtHi - unHi);
    1503                        vswap(fmap, unLo, hi - m + 1, m);
    1504
    1505                        n = lo + unLo - ltLo - 1;
    1506                        m = hi - (gtHi - unHi) + 1;
    1507
    1508                        stack_ll[sp] = lo;
    1509                        stack_hh[sp] = n;
    1510                        stack_dd[sp] = d;
    1511                        sp++;
    1512
    1513                        stack_ll[sp] = n + 1;
    1514                        stack_hh[sp] = m - 1;
    1515                        stack_dd[sp] = d1;
    1516                        sp++;
    1517
    1518                        stack_ll[sp] = m;
    1519                        stack_hh[sp] = hi;
    1520                        stack_dd[sp] = d;
    1521                        sp++;
    1522                    }
    1523                }
    1524            }
    1525        }
    1526
    1527        private void mainSort() {
    1528            final Data dataShadow = this.data;
    1529            final int[] runningOrder = dataShadow.mainSort_runningOrder;
    1530            final int[] copy = dataShadow.mainSort_copy;
    1531            final boolean[] bigDone = dataShadow.mainSort_bigDone;
    1532            final int[] ftab = dataShadow.ftab;
    1533            final byte[] block = dataShadow.block;
    1534            final int[] fmap = dataShadow.fmap;
    1535            final char[] quadrant = dataShadow.quadrant;
    1536            final int lastShadow = this.last;
    1537            final int workLimitShadow = this.workLimit;
    1538            final boolean firstAttemptShadow = this.firstAttempt;
    1539
    1540            // Set up the 2-byte frequency table
    1541            for (int i = 65537; --i >= 0;) {
    1542                ftab[i] = 0;
    1543            }
    1544
    1545            /*
    1546             * In the various block-sized structures, live data runs from 0 to
    1547             * last+NUM_OVERSHOOT_BYTES inclusive. First, set up the overshoot area
    1548             * for block.
    1549             */
    1550            for (int i = 0; i < NUM_OVERSHOOT_BYTES; i++) {
    1551                block[lastShadow + i + 2] = block[(i % (lastShadow + 1)) + 1];
    1552            }
    1553            for (int i = lastShadow + NUM_OVERSHOOT_BYTES +1; --i >= 0;) {
    1554                quadrant[i] = 0;
    1555            }
    1556            block[0] = block[lastShadow + 1];
    1557
    1558            // Complete the initial radix sort:
    1559
    1560            int c1 = block[0] & 0xff;
    1561            for (int i = 0; i <= lastShadow; i++) {
    1562                final int c2 = block[i + 1] & 0xff;
    1563                ftab[(c1 << 8) + c2]++;
    1564                c1 = c2;
    1565            }
    1566
    1567            for (int i = 1; i <= 65536; i++)
    1568                ftab[i] += ftab[i - 1];
    1569
    1570            c1 = block[1] & 0xff;
    1571            for (int i = 0; i < lastShadow; i++) {
    1572                final int c2 = block[i + 2] & 0xff;
    1573                fmap[--ftab[(c1 << 8) + c2]] = i;
    1574                c1 = c2;
    1575            }
    1576
    1577            fmap[--ftab[((block[lastShadow + 1] & 0xff) << 8) + (block[1] & 0xff)]] = lastShadow;
    1578
    1579            /*
    1580             * Now ftab contains the first loc of every small bucket. Calculate the
    1581             * running order, from smallest to largest big bucket.
    1582             */
    1583            for (int i = 256; --i >= 0;) {
    1584                bigDone[i] = false;
    1585                runningOrder[i] = i;
    1586            }
    1587
    1588            for (int h = 364; h != 1;) {
    1589                h /= 3;
    1590                for (int i = h; i <= 255; i++) {
    1591                    final int vv = runningOrder[i];
    1592                    final int a = ftab[(vv + 1) << 8] - ftab[vv << 8];
    1593                    final int b = h - 1;
    1594                    int j = i;
    1595                    for (int ro = runningOrder[j - h]; (ftab[(ro + 1) << 8] - ftab[ro << 8]) > a; ro = runningOrder[j
    1596                                                                                                                    - h]) {
    1597                        runningOrder[j] = ro;
    1598                        j -= h;
    1599                        if (j <= b) {
    1600                            break;
    1601                        }
    1602                    }
    1603                    runningOrder[j] = vv;
    1604                }
    1605            }
    1606
    1607            /*
    1608             * The main sorting loop.
    1609             */
    1610            for (int i = 0; i <= 255; i++) {
    1611                /*
    1612                 * Process big buckets, starting with the least full.
    1613                 */
    1614                final int ss = runningOrder[i];
    1615
    1616                // Step 1:
    1617                /*
    1618                 * Complete the big bucket [ss] by quicksorting any unsorted small
    1619                 * buckets [ss, j]. Hopefully previous pointer-scanning phases have
    1620                 * already completed many of the small buckets [ss, j], so we don't
    1621                 * have to sort them at all.
    1622                 */
    1623                for (int j = 0; j <= 255; j++) {
    1624                    final int sb = (ss << 8) + j;
    1625                    final int ftab_sb = ftab[sb];
    1626                    if ((ftab_sb & SETMASK) != SETMASK) {
    1627                        final int lo = ftab_sb & CLEARMASK;
    1628                        final int hi = (ftab[sb + 1] & CLEARMASK) - 1;
    1629                        if (hi > lo) {
    1630                            mainQSort3(dataShadow, lo, hi, 2);
    1631                            if (firstAttemptShadow
    1632                                && (this.workDone > workLimitShadow)) {
    1633                                return;
    1634                            }
    1635                        }
    1636                        ftab[sb] = ftab_sb | SETMASK;
    1637                    }
    1638                }
    1639
    1640                // Step 2:
    1641                // Now scan this big bucket so as to synthesise the
    1642                // sorted order for small buckets [t, ss] for all t != ss.
    1643
    1644                for (int j = 0; j <= 255; j++) {
    1645                    copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
    1646                }
    1647
    1648                for (int j = ftab[ss << 8] & CLEARMASK, hj = (ftab[(ss + 1) << 8] & CLEARMASK); j < hj; j++) {
    1649                    final int fmap_j = fmap[j];
    1650                    c1 = block[fmap_j] & 0xff;
    1651                    if (!bigDone[c1]) {
    1652                        fmap[copy[c1]] = (fmap_j == 0) ? lastShadow : (fmap_j - 1);
    1653                        copy[c1]++;
    1654                    }
    1655                }
    1656
    1657                for (int j = 256; --j >= 0;)
    1658                    ftab[(j << 8) + ss] |= SETMASK;
    1659
    1660                // Step 3:
    1661                /*
    1662                 * The ss big bucket is now done. Record this fact, and update the
    1663                 * quadrant descriptors. Remember to update quadrants in the
    1664                 * overshoot area too, if necessary. The "if (i < 255)" test merely
    1665                 * skips this updating for the last bucket processed, since updating
    1666                 * for the last bucket is pointless.
    1667                 */
    1668                bigDone[ss] = true;
    1669
    1670                if (i < 255) {
    1671                    final int bbStart = ftab[ss << 8] & CLEARMASK;
    1672                    final int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart;
    1673                    int shifts = 0;
    1674
    1675                    while ((bbSize >> shifts) > 65534) {
    1676                        shifts++;
    1677                    }
    1678
    1679                    for (int j = 0; j < bbSize; j++) {
    1680                        final int a2update = fmap[bbStart + j];
    1681                        final char qVal = (char) (j >> shifts);
    1682                        quadrant[a2update] = qVal;
    1683                        if (a2update < NUM_OVERSHOOT_BYTES) {
    1684                            quadrant[a2update + lastShadow + 1] = qVal;
    1685                        }
    1686                    }
    1687                }
    1688
    1689            }
    1690        }
    1691
    1692        private void randomiseBlock() {
    1693            final boolean[] inUse = this.data.inUse;
    1694            final byte[] block = this.data.block;
    1695            final int lastShadow = this.last;
    1696
    1697            for (int i = 256; --i >= 0;)
    1698                inUse[i] = false;
    1699
    1700            int rNToGo = 0;
    1701            int rTPos = 0;
    1702            for (int i = 0, j = 1; i <= lastShadow; i = j, j++) {
    1703                if (rNToGo == 0) {
    1704                    rNToGo = (char) Rand.rNums(rTPos);
    1705                    if (++rTPos == 512) {
    1706                        rTPos = 0;
    1707                    }
    1708                }
    1709
    1710                rNToGo--;
    1711                block[j] ^= ((rNToGo == 1) ? 1 : 0);
    1712
    1713                // handle 16 bit signed numbers
    1714                inUse[block[j] & 0xff] = true;
    1715            }
    1716
    1717            this.blockRandomised = true;
    1718        }
    1719
    1720        private void generateMTFValues() {
    1721            final int lastShadow = this.last;
    1722            final Data dataShadow = this.data;
    1723            final boolean[] inUse = dataShadow.inUse;
    1724            final byte[] block = dataShadow.block;
    1725            final int[] fmap = dataShadow.fmap;
    1726            final char[] sfmap = dataShadow.sfmap;
    1727            final int[] mtfFreq = dataShadow.mtfFreq;
    1728            final byte[] unseqToSeq = dataShadow.unseqToSeq;
    1729            final byte[] yy = dataShadow.generateMTFValues_yy;
    1730
    1731            // make maps
    1732            int nInUseShadow = 0;
    1733            for (int i = 0; i < 256; i++) {
    1734                if (inUse[i]) {
    1735                    unseqToSeq[i] = (byte) nInUseShadow;
    1736                    nInUseShadow++;
    1737                }
    1738            }
    1739            this.nInUse = nInUseShadow;
    1740
    1741            final int eob = nInUseShadow + 1;
    1742
    1743            for (int i = eob; i >= 0; i--) {
    1744                mtfFreq[i] = 0;
    1745            }
    1746
    1747            for (int i = nInUseShadow; --i >= 0;) {
    1748                yy[i] = (byte) i;
    1749            }
    1750
    1751            int wr = 0;
    1752            int zPend = 0;
    1753
    1754            for (int i = 0; i <= lastShadow; i++) {
    1755                final byte ll_i = unseqToSeq[block[fmap[i]] & 0xff];
    1756                byte tmp = yy[0];
    1757                int j = 0;
    1758
    1759                while (ll_i != tmp) {
    1760                    j++;
    1761                    byte tmp2 = tmp;
    1762                    tmp = yy[j];
    1763                    yy[j] = tmp2;
    1764                }
    1765                yy[0] = tmp;
    1766
    1767                if (j == 0) {
    1768                    zPend++;
    1769                } else {
    1770                    if (zPend > 0) {
    1771                        zPend--;
    1772                        while (true) {
    1773                            if ((zPend & 1) == 0) {
    1774                                sfmap[wr] = RUNA;
    1775                                wr++;
    1776                                mtfFreq[RUNA]++;
    1777                            } else {
    1778                                sfmap[wr] = RUNB;
    1779                                wr++;
    1780                                mtfFreq[RUNB]++;
    1781                            }
    1782
    1783                            if (zPend >= 2) {
    1784                                zPend = (zPend - 2) >> 1;
    1785                            } else {
    1786                                break;
    1787                            }
    1788                        }
    1789                        zPend = 0;
    1790                    }
    1791                    sfmap[wr] = (char) (j + 1);
    1792                    wr++;
    1793                    mtfFreq[j + 1]++;
    1794                }
    1795            }
    1796
    1797            if (zPend > 0) {
    1798                zPend--;
    1799                while (true) {
    1800                    if ((zPend & 1) == 0) {
    1801                        sfmap[wr] = RUNA;
    1802                        wr++;
    1803                        mtfFreq[RUNA]++;
    1804                    } else {
    1805                        sfmap[wr] = RUNB;
    1806                        wr++;
    1807                        mtfFreq[RUNB]++;
    1808                    }
    1809
    1810                    if (zPend >= 2) {
    1811                        zPend = (zPend - 2) >> 1;
    1812                    } else {
    1813                        break;
    1814                    }
    1815                }
    1816            }
    1817
    1818            sfmap[wr] = (char) eob;
    1819            mtfFreq[eob]++;
    1820            this.nMTF = wr + 1;
    1821        }
    1822
    1823        private static final class Data extends Object {
    1824
    1825            // with blockSize 900k
    1826            final boolean[] inUse = new boolean[256]; // 256 byte
    1827            final byte[] unseqToSeq = new byte[256]; // 256 byte
    1828            final int[] mtfFreq = new int[MAX_ALPHA_SIZE]; // 1032 byte
    1829            final byte[] selector = new byte[MAX_SELECTORS]; // 18002 byte
    1830            final byte[] selectorMtf = new byte[MAX_SELECTORS]; // 18002 byte
    1831
    1832            final byte[] generateMTFValues_yy = new byte[256]; // 256 byte
    1833            final byte[][] sendMTFValues_len = new byte[N_GROUPS][MAX_ALPHA_SIZE]; // 1548
    1834            // byte
    1835            final int[][] sendMTFValues_rfreq = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192
    1836            // byte
    1837            final int[] sendMTFValues_fave = new int[N_GROUPS]; // 24 byte
    1838            final short[] sendMTFValues_cost = new short[N_GROUPS]; // 12 byte
    1839            final int[][] sendMTFValues_code = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192
    1840            // byte
    1841            final byte[] sendMTFValues2_pos = new byte[N_GROUPS]; // 6 byte
    1842            final boolean[] sentMTFValues4_inUse16 = new boolean[16]; // 16 byte
    1843
    1844            final int[] stack_ll = new int[QSORT_STACK_SIZE]; // 4000 byte
    1845            final int[] stack_hh = new int[QSORT_STACK_SIZE]; // 4000 byte
    1846            final int[] stack_dd = new int[QSORT_STACK_SIZE]; // 4000 byte
    1847
    1848            final int[] mainSort_runningOrder = new int[256]; // 1024 byte
    1849            final int[] mainSort_copy = new int[256]; // 1024 byte
    1850            final boolean[] mainSort_bigDone = new boolean[256]; // 256 byte
    1851
    1852            final int[] heap = new int[MAX_ALPHA_SIZE + 2]; // 1040 byte
    1853            final int[] weight = new int[MAX_ALPHA_SIZE * 2]; // 2064 byte
    1854            final int[] parent = new int[MAX_ALPHA_SIZE * 2]; // 2064 byte
    1855
    1856            final int[] ftab = new int[65537]; // 262148 byte
    1857            // ------------
    1858            // 333408 byte
    1859
    1860            final byte[] block; // 900021 byte
    1861            final int[] fmap; // 3600000 byte
    1862            final char[] sfmap; // 3600000 byte
    1863            // ------------
    1864            // 8433529 byte
    1865            // ============
    1866
    1867            /**
    1868             * Array instance identical to sfmap, both are used only
    1869             * temporarily and indepently, so we do not need to allocate
    1870             * additional memory.
    1871             */
    1872            final char[] quadrant;
    1873
    1874            Data(int blockSize100k) {
    1875                super();
    1876
    1877                final int n = blockSize100k * BZip2Constants.BASEBLOCKSIZE;
    1878                this.block = new byte[(n + 1 + NUM_OVERSHOOT_BYTES)];
    1879                this.fmap = new int[n];
    1880                this.sfmap = new char[2 * n];
    1881                this.quadrant = this.sfmap;
    1882            }
    1883
    1884        }
    1885
    1886    }