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        public void write(final int b) throws IOException {
435            if (this.out != null) {
436                write0(b);
437            } else {
438                throw new IOException("closed");
439            }
440        }
441    
442        private void writeRun() throws IOException {
443            final int lastShadow = this.last;
444    
445            if (lastShadow < this.allowableBlockSize) {
446                final int currentCharShadow = this.currentChar;
447                final Data dataShadow = this.data;
448                dataShadow.inUse[currentCharShadow] = true;
449                final byte ch = (byte) currentCharShadow;
450    
451                int runLengthShadow = this.runLength;
452                this.crc.updateCRC(currentCharShadow, runLengthShadow);
453    
454                switch (runLengthShadow) {
455                case 1:
456                    dataShadow.block[lastShadow + 2] = ch;
457                    this.last = lastShadow + 1;
458                    break;
459    
460                case 2:
461                    dataShadow.block[lastShadow + 2] = ch;
462                    dataShadow.block[lastShadow + 3] = ch;
463                    this.last = lastShadow + 2;
464                    break;
465    
466                case 3: {
467                    final byte[] block = dataShadow.block;
468                    block[lastShadow + 2] = ch;
469                    block[lastShadow + 3] = ch;
470                    block[lastShadow + 4] = ch;
471                    this.last = lastShadow + 3;
472                }
473                    break;
474    
475                default: {
476                    runLengthShadow -= 4;
477                    dataShadow.inUse[runLengthShadow] = true;
478                    final byte[] block = dataShadow.block;
479                    block[lastShadow + 2] = ch;
480                    block[lastShadow + 3] = ch;
481                    block[lastShadow + 4] = ch;
482                    block[lastShadow + 5] = ch;
483                    block[lastShadow + 6] = (byte) runLengthShadow;
484                    this.last = lastShadow + 5;
485                }
486                    break;
487    
488                }
489            } else {
490                endBlock();
491                initBlock();
492                writeRun();
493            }
494        }
495    
496        /**
497         * Overriden to close the stream.
498         */
499        protected void finalize() throws Throwable {
500            finish();
501            super.finalize();
502        }
503    
504    
505        public void finish() throws IOException {
506            if (out != null) {
507                try {
508                    if (this.runLength > 0) {
509                        writeRun();
510                    }
511                    this.currentChar = -1;
512                    endBlock();
513                    endCompression();
514                } finally {
515                    this.out = null;
516                    this.data = null;
517                }
518            }
519        }
520    
521        public void close() throws IOException {
522            if (out != null) {
523                OutputStream outShadow = this.out;
524                finish();
525                outShadow.close();
526            }
527        }
528    
529        public void flush() throws IOException {
530            OutputStream outShadow = this.out;
531            if (outShadow != null) {
532                outShadow.flush();
533            }
534        }
535    
536        /**
537         * Writes magic bytes like BZ on the first position of the stream
538         * and bytes indiciating the file-format, which is 
539         * huffmanised, followed by a digit indicating blockSize100k.
540         * @throws IOException if the magic bytes could not been written
541         */
542        private void init() throws IOException {
543            bsPutUByte('B');
544            bsPutUByte('Z');
545    
546            this.data = new Data(this.blockSize100k);
547    
548            // huffmanised magic bytes
549            bsPutUByte('h');
550            bsPutUByte('0' + this.blockSize100k);
551    
552            this.combinedCRC = 0;
553            initBlock();
554        }
555    
556        private void initBlock() {
557            // blockNo++;
558            this.crc.initialiseCRC();
559            this.last = -1;
560            // ch = 0;
561    
562            boolean[] inUse = this.data.inUse;
563            for (int i = 256; --i >= 0;) {
564                inUse[i] = false;
565            }
566    
567            /* 20 is just a paranoia constant */
568            this.allowableBlockSize = (this.blockSize100k * BZip2Constants.BASEBLOCKSIZE) - 20;
569        }
570    
571        private void endBlock() throws IOException {
572            this.blockCRC = this.crc.getFinalCRC();
573            this.combinedCRC = (this.combinedCRC << 1) | (this.combinedCRC >>> 31);
574            this.combinedCRC ^= this.blockCRC;
575    
576            // empty block at end of file
577            if (this.last == -1) {
578                return;
579            }
580    
581            /* sort the block and establish posn of original string */
582            blockSort();
583    
584            /*
585             * A 6-byte block header, the value chosen arbitrarily as 0x314159265359
586             * :-). A 32 bit value does not really give a strong enough guarantee
587             * that the value will not appear by chance in the compressed
588             * datastream. Worst-case probability of this event, for a 900k block,
589             * is about 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48
590             * bits. For a compressed file of size 100Gb -- about 100000 blocks --
591             * only a 48-bit marker will do. NB: normal compression/ decompression
592             * donot rely on these statistical properties. They are only important
593             * when trying to recover blocks from damaged files.
594             */
595            bsPutUByte(0x31);
596            bsPutUByte(0x41);
597            bsPutUByte(0x59);
598            bsPutUByte(0x26);
599            bsPutUByte(0x53);
600            bsPutUByte(0x59);
601    
602            /* Now the block's CRC, so it is in a known place. */
603            bsPutInt(this.blockCRC);
604    
605            /* Now a single bit indicating randomisation. */
606            if (this.blockRandomised) {
607                bsW(1, 1);
608            } else {
609                bsW(1, 0);
610            }
611    
612            /* Finally, block's contents proper. */
613            moveToFrontCodeAndSend();
614        }
615    
616        private void endCompression() throws IOException {
617            /*
618             * Now another magic 48-bit number, 0x177245385090, to indicate the end
619             * of the last block. (sqrt(pi), if you want to know. I did want to use
620             * e, but it contains too much repetition -- 27 18 28 18 28 46 -- for me
621             * to feel statistically comfortable. Call me paranoid.)
622             */
623            bsPutUByte(0x17);
624            bsPutUByte(0x72);
625            bsPutUByte(0x45);
626            bsPutUByte(0x38);
627            bsPutUByte(0x50);
628            bsPutUByte(0x90);
629    
630            bsPutInt(this.combinedCRC);
631            bsFinishedWithStream();
632        }
633    
634        /**
635         * Returns the blocksize parameter specified at construction time.
636         */
637        public final int getBlockSize() {
638            return this.blockSize100k;
639        }
640    
641        public void write(final byte[] buf, int offs, final int len)
642            throws IOException {
643            if (offs < 0) {
644                throw new IndexOutOfBoundsException("offs(" + offs + ") < 0.");
645            }
646            if (len < 0) {
647                throw new IndexOutOfBoundsException("len(" + len + ") < 0.");
648            }
649            if (offs + len > buf.length) {
650                throw new IndexOutOfBoundsException("offs(" + offs + ") + len("
651                                                    + len + ") > buf.length("
652                                                    + buf.length + ").");
653            }
654            if (this.out == null) {
655                throw new IOException("stream closed");
656            }
657    
658            for (int hi = offs + len; offs < hi;) {
659                write0(buf[offs++]);
660            }
661        }
662    
663        private void write0(int b) throws IOException {
664            if (this.currentChar != -1) {
665                b &= 0xff;
666                if (this.currentChar == b) {
667                    if (++this.runLength > 254) {
668                        writeRun();
669                        this.currentChar = -1;
670                        this.runLength = 0;
671                    }
672                    // else nothing to do
673                } else {
674                    writeRun();
675                    this.runLength = 1;
676                    this.currentChar = b;
677                }
678            } else {
679                this.currentChar = b & 0xff;
680                this.runLength++;
681            }
682        }
683    
684        private static void hbAssignCodes(final int[] code, final byte[] length,
685                                          final int minLen, final int maxLen,
686                                          final int alphaSize) {
687            int vec = 0;
688            for (int n = minLen; n <= maxLen; n++) {
689                for (int i = 0; i < alphaSize; i++) {
690                    if ((length[i] & 0xff) == n) {
691                        code[i] = vec;
692                        vec++;
693                    }
694                }
695                vec <<= 1;
696            }
697        }
698    
699        private void bsFinishedWithStream() throws IOException {
700            while (this.bsLive > 0) {
701                int ch = this.bsBuff >> 24;
702                this.out.write(ch); // write 8-bit
703                this.bsBuff <<= 8;
704                this.bsLive -= 8;
705            }
706        }
707    
708        private void bsW(final int n, final int v) throws IOException {
709            final OutputStream outShadow = this.out;
710            int bsLiveShadow = this.bsLive;
711            int bsBuffShadow = this.bsBuff;
712    
713            while (bsLiveShadow >= 8) {
714                outShadow.write(bsBuffShadow >> 24); // write 8-bit
715                bsBuffShadow <<= 8;
716                bsLiveShadow -= 8;
717            }
718    
719            this.bsBuff = bsBuffShadow | (v << (32 - bsLiveShadow - n));
720            this.bsLive = bsLiveShadow + n;
721        }
722    
723        private void bsPutUByte(final int c) throws IOException {
724            bsW(8, c);
725        }
726    
727        private void bsPutInt(final int u) throws IOException {
728            bsW(8, (u >> 24) & 0xff);
729            bsW(8, (u >> 16) & 0xff);
730            bsW(8, (u >> 8) & 0xff);
731            bsW(8, u & 0xff);
732        }
733    
734        private void sendMTFValues() throws IOException {
735            final byte[][] len = this.data.sendMTFValues_len;
736            final int alphaSize = this.nInUse + 2;
737    
738            for (int t = N_GROUPS; --t >= 0;) {
739                byte[] len_t = len[t];
740                for (int v = alphaSize; --v >= 0;) {
741                    len_t[v] = GREATER_ICOST;
742                }
743            }
744    
745            /* Decide how many coding tables to use */
746            // assert (this.nMTF > 0) : this.nMTF;
747            final int nGroups = (this.nMTF < 200) ? 2 : (this.nMTF < 600) ? 3
748                : (this.nMTF < 1200) ? 4 : (this.nMTF < 2400) ? 5 : 6;
749    
750            /* Generate an initial set of coding tables */
751            sendMTFValues0(nGroups, alphaSize);
752    
753            /*
754             * Iterate up to N_ITERS times to improve the tables.
755             */
756            final int nSelectors = sendMTFValues1(nGroups, alphaSize);
757    
758            /* Compute MTF values for the selectors. */
759            sendMTFValues2(nGroups, nSelectors);
760    
761            /* Assign actual codes for the tables. */
762            sendMTFValues3(nGroups, alphaSize);
763    
764            /* Transmit the mapping table. */
765            sendMTFValues4();
766    
767            /* Now the selectors. */
768            sendMTFValues5(nGroups, nSelectors);
769    
770            /* Now the coding tables. */
771            sendMTFValues6(nGroups, alphaSize);
772    
773            /* And finally, the block data proper */
774            sendMTFValues7(nSelectors);
775        }
776    
777        private void sendMTFValues0(final int nGroups, final int alphaSize) {
778            final byte[][] len = this.data.sendMTFValues_len;
779            final int[] mtfFreq = this.data.mtfFreq;
780    
781            int remF = this.nMTF;
782            int gs = 0;
783    
784            for (int nPart = nGroups; nPart > 0; nPart--) {
785                final int tFreq = remF / nPart;
786                int ge = gs - 1;
787                int aFreq = 0;
788    
789                for (final int a = alphaSize - 1; (aFreq < tFreq) && (ge < a);) {
790                    aFreq += mtfFreq[++ge];
791                }
792    
793                if ((ge > gs) && (nPart != nGroups) && (nPart != 1)
794                    && (((nGroups - nPart) & 1) != 0)) {
795                    aFreq -= mtfFreq[ge--];
796                }
797    
798                final byte[] len_np = len[nPart - 1];
799                for (int v = alphaSize; --v >= 0;) {
800                    if ((v >= gs) && (v <= ge)) {
801                        len_np[v] = LESSER_ICOST;
802                    } else {
803                        len_np[v] = GREATER_ICOST;
804                    }
805                }
806    
807                gs = ge + 1;
808                remF -= aFreq;
809            }
810        }
811    
812        private int sendMTFValues1(final int nGroups, final int alphaSize) {
813            final Data dataShadow = this.data;
814            final int[][] rfreq = dataShadow.sendMTFValues_rfreq;
815            final int[] fave = dataShadow.sendMTFValues_fave;
816            final short[] cost = dataShadow.sendMTFValues_cost;
817            final char[] sfmap = dataShadow.sfmap;
818            final byte[] selector = dataShadow.selector;
819            final byte[][] len = dataShadow.sendMTFValues_len;
820            final byte[] len_0 = len[0];
821            final byte[] len_1 = len[1];
822            final byte[] len_2 = len[2];
823            final byte[] len_3 = len[3];
824            final byte[] len_4 = len[4];
825            final byte[] len_5 = len[5];
826            final int nMTFShadow = this.nMTF;
827    
828            int nSelectors = 0;
829    
830            for (int iter = 0; iter < N_ITERS; iter++) {
831                for (int t = nGroups; --t >= 0;) {
832                    fave[t] = 0;
833                    int[] rfreqt = rfreq[t];
834                    for (int i = alphaSize; --i >= 0;) {
835                        rfreqt[i] = 0;
836                    }
837                }
838    
839                nSelectors = 0;
840    
841                for (int gs = 0; gs < this.nMTF;) {
842                    /* Set group start & end marks. */
843    
844                    /*
845                     * Calculate the cost of this group as coded by each of the
846                     * coding tables.
847                     */
848    
849                    final int ge = Math.min(gs + G_SIZE - 1, nMTFShadow - 1);
850    
851                    if (nGroups == N_GROUPS) {
852                        // unrolled version of the else-block
853    
854                        short cost0 = 0;
855                        short cost1 = 0;
856                        short cost2 = 0;
857                        short cost3 = 0;
858                        short cost4 = 0;
859                        short cost5 = 0;
860    
861                        for (int i = gs; i <= ge; i++) {
862                            final int icv = sfmap[i];
863                            cost0 += len_0[icv] & 0xff;
864                            cost1 += len_1[icv] & 0xff;
865                            cost2 += len_2[icv] & 0xff;
866                            cost3 += len_3[icv] & 0xff;
867                            cost4 += len_4[icv] & 0xff;
868                            cost5 += len_5[icv] & 0xff;
869                        }
870    
871                        cost[0] = cost0;
872                        cost[1] = cost1;
873                        cost[2] = cost2;
874                        cost[3] = cost3;
875                        cost[4] = cost4;
876                        cost[5] = cost5;
877    
878                    } else {
879                        for (int t = nGroups; --t >= 0;) {
880                            cost[t] = 0;
881                        }
882    
883                        for (int i = gs; i <= ge; i++) {
884                            final int icv = sfmap[i];
885                            for (int t = nGroups; --t >= 0;) {
886                                cost[t] += len[t][icv] & 0xff;
887                            }
888                        }
889                    }
890    
891                    /*
892                     * Find the coding table which is best for this group, and
893                     * record its identity in the selector table.
894                     */
895                    int bt = -1;
896                    for (int t = nGroups, bc = 999999999; --t >= 0;) {
897                        final int cost_t = cost[t];
898                        if (cost_t < bc) {
899                            bc = cost_t;
900                            bt = t;
901                        }
902                    }
903    
904                    fave[bt]++;
905                    selector[nSelectors] = (byte) bt;
906                    nSelectors++;
907    
908                    /*
909                     * Increment the symbol frequencies for the selected table.
910                     */
911                    final int[] rfreq_bt = rfreq[bt];
912                    for (int i = gs; i <= ge; i++) {
913                        rfreq_bt[sfmap[i]]++;
914                    }
915    
916                    gs = ge + 1;
917                }
918    
919                /*
920                 * Recompute the tables based on the accumulated frequencies.
921                 */
922                for (int t = 0; t < nGroups; t++) {
923                    hbMakeCodeLengths(len[t], rfreq[t], this.data, alphaSize, 20);
924                }
925            }
926    
927            return nSelectors;
928        }
929    
930        private void sendMTFValues2(final int nGroups, final int nSelectors) {
931            // assert (nGroups < 8) : nGroups;
932    
933            final Data dataShadow = this.data;
934            byte[] pos = dataShadow.sendMTFValues2_pos;
935    
936            for (int i = nGroups; --i >= 0;) {
937                pos[i] = (byte) i;
938            }
939    
940            for (int i = 0; i < nSelectors; i++) {
941                final byte ll_i = dataShadow.selector[i];
942                byte tmp = pos[0];
943                int j = 0;
944    
945                while (ll_i != tmp) {
946                    j++;
947                    byte tmp2 = tmp;
948                    tmp = pos[j];
949                    pos[j] = tmp2;
950                }
951    
952                pos[0] = tmp;
953                dataShadow.selectorMtf[i] = (byte) j;
954            }
955        }
956    
957        private void sendMTFValues3(final int nGroups, final int alphaSize) {
958            int[][] code = this.data.sendMTFValues_code;
959            byte[][] len = this.data.sendMTFValues_len;
960    
961            for (int t = 0; t < nGroups; t++) {
962                int minLen = 32;
963                int maxLen = 0;
964                final byte[] len_t = len[t];
965                for (int i = alphaSize; --i >= 0;) {
966                    final int l = len_t[i] & 0xff;
967                    if (l > maxLen) {
968                        maxLen = l;
969                    }
970                    if (l < minLen) {
971                        minLen = l;
972                    }
973                }
974    
975                // assert (maxLen <= 20) : maxLen;
976                // assert (minLen >= 1) : minLen;
977    
978                hbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
979            }
980        }
981    
982        private void sendMTFValues4() throws IOException {
983            final boolean[] inUse = this.data.inUse;
984            final boolean[] inUse16 = this.data.sentMTFValues4_inUse16;
985    
986            for (int i = 16; --i >= 0;) {
987                inUse16[i] = false;
988                final int i16 = i * 16;
989                for (int j = 16; --j >= 0;) {
990                    if (inUse[i16 + j]) {
991                        inUse16[i] = true;
992                    }
993                }
994            }
995    
996            for (int i = 0; i < 16; i++) {
997                bsW(1, inUse16[i] ? 1 : 0);
998            }
999    
1000            final OutputStream outShadow = this.out;
1001            int bsLiveShadow = this.bsLive;
1002            int bsBuffShadow = this.bsBuff;
1003    
1004            for (int i = 0; i < 16; i++) {
1005                if (inUse16[i]) {
1006                    final int i16 = i * 16;
1007                    for (int j = 0; j < 16; j++) {
1008                        // inlined: bsW(1, inUse[i16 + j] ? 1 : 0);
1009                        while (bsLiveShadow >= 8) {
1010                            outShadow.write(bsBuffShadow >> 24); // write 8-bit
1011                            bsBuffShadow <<= 8;
1012                            bsLiveShadow -= 8;
1013                        }
1014                        if (inUse[i16 + j]) {
1015                            bsBuffShadow |= 1 << (32 - bsLiveShadow - 1);
1016                        }
1017                        bsLiveShadow++;
1018                    }
1019                }
1020            }
1021    
1022            this.bsBuff = bsBuffShadow;
1023            this.bsLive = bsLiveShadow;
1024        }
1025    
1026        private void sendMTFValues5(final int nGroups, final int nSelectors)
1027            throws IOException {
1028            bsW(3, nGroups);
1029            bsW(15, nSelectors);
1030    
1031            final OutputStream outShadow = this.out;
1032            final byte[] selectorMtf = this.data.selectorMtf;
1033    
1034            int bsLiveShadow = this.bsLive;
1035            int bsBuffShadow = this.bsBuff;
1036    
1037            for (int i = 0; i < nSelectors; i++) {
1038                for (int j = 0, hj = selectorMtf[i] & 0xff; j < hj; j++) {
1039                    // inlined: bsW(1, 1);
1040                    while (bsLiveShadow >= 8) {
1041                        outShadow.write(bsBuffShadow >> 24);
1042                        bsBuffShadow <<= 8;
1043                        bsLiveShadow -= 8;
1044                    }
1045                    bsBuffShadow |= 1 << (32 - bsLiveShadow - 1);
1046                    bsLiveShadow++;
1047                }
1048    
1049                // inlined: bsW(1, 0);
1050                while (bsLiveShadow >= 8) {
1051                    outShadow.write(bsBuffShadow >> 24);
1052                    bsBuffShadow <<= 8;
1053                    bsLiveShadow -= 8;
1054                }
1055                // bsBuffShadow |= 0 << (32 - bsLiveShadow - 1);
1056                bsLiveShadow++;
1057            }
1058    
1059            this.bsBuff = bsBuffShadow;
1060            this.bsLive = bsLiveShadow;
1061        }
1062    
1063        private void sendMTFValues6(final int nGroups, final int alphaSize)
1064            throws IOException {
1065            final byte[][] len = this.data.sendMTFValues_len;
1066            final OutputStream outShadow = this.out;
1067    
1068            int bsLiveShadow = this.bsLive;
1069            int bsBuffShadow = this.bsBuff;
1070    
1071            for (int t = 0; t < nGroups; t++) {
1072                byte[] len_t = len[t];
1073                int curr = len_t[0] & 0xff;
1074    
1075                // inlined: bsW(5, curr);
1076                while (bsLiveShadow >= 8) {
1077                    outShadow.write(bsBuffShadow >> 24); // write 8-bit
1078                    bsBuffShadow <<= 8;
1079                    bsLiveShadow -= 8;
1080                }
1081                bsBuffShadow |= curr << (32 - bsLiveShadow - 5);
1082                bsLiveShadow += 5;
1083    
1084                for (int i = 0; i < alphaSize; i++) {
1085                    int lti = len_t[i] & 0xff;
1086                    while (curr < lti) {
1087                        // inlined: bsW(2, 2);
1088                        while (bsLiveShadow >= 8) {
1089                            outShadow.write(bsBuffShadow >> 24); // write 8-bit
1090                            bsBuffShadow <<= 8;
1091                            bsLiveShadow -= 8;
1092                        }
1093                        bsBuffShadow |= 2 << (32 - bsLiveShadow - 2);
1094                        bsLiveShadow += 2;
1095    
1096                        curr++; /* 10 */
1097                    }
1098    
1099                    while (curr > lti) {
1100                        // inlined: bsW(2, 3);
1101                        while (bsLiveShadow >= 8) {
1102                            outShadow.write(bsBuffShadow >> 24); // write 8-bit
1103                            bsBuffShadow <<= 8;
1104                            bsLiveShadow -= 8;
1105                        }
1106                        bsBuffShadow |= 3 << (32 - bsLiveShadow - 2);
1107                        bsLiveShadow += 2;
1108    
1109                        curr--; /* 11 */
1110                    }
1111    
1112                    // inlined: bsW(1, 0);
1113                    while (bsLiveShadow >= 8) {
1114                        outShadow.write(bsBuffShadow >> 24); // write 8-bit
1115                        bsBuffShadow <<= 8;
1116                        bsLiveShadow -= 8;
1117                    }
1118                    // bsBuffShadow |= 0 << (32 - bsLiveShadow - 1);
1119                    bsLiveShadow++;
1120                }
1121            }
1122    
1123            this.bsBuff = bsBuffShadow;
1124            this.bsLive = bsLiveShadow;
1125        }
1126    
1127        private void sendMTFValues7(final int nSelectors) throws IOException {
1128            final Data dataShadow = this.data;
1129            final byte[][] len = dataShadow.sendMTFValues_len;
1130            final int[][] code = dataShadow.sendMTFValues_code;
1131            final OutputStream outShadow = this.out;
1132            final byte[] selector = dataShadow.selector;
1133            final char[] sfmap = dataShadow.sfmap;
1134            final int nMTFShadow = this.nMTF;
1135    
1136            int selCtr = 0;
1137    
1138            int bsLiveShadow = this.bsLive;
1139            int bsBuffShadow = this.bsBuff;
1140    
1141            for (int gs = 0; gs < nMTFShadow;) {
1142                final int ge = Math.min(gs + G_SIZE - 1, nMTFShadow - 1);
1143                final int selector_selCtr = selector[selCtr] & 0xff;
1144                final int[] code_selCtr = code[selector_selCtr];
1145                final byte[] len_selCtr = len[selector_selCtr];
1146    
1147                while (gs <= ge) {
1148                    final int sfmap_i = sfmap[gs];
1149    
1150                    //
1151                    // inlined: bsW(len_selCtr[sfmap_i] & 0xff,
1152                    // code_selCtr[sfmap_i]);
1153                    //
1154                    while (bsLiveShadow >= 8) {
1155                        outShadow.write(bsBuffShadow >> 24);
1156                        bsBuffShadow <<= 8;
1157                        bsLiveShadow -= 8;
1158                    }
1159                    final int n = len_selCtr[sfmap_i] & 0xFF;
1160                    bsBuffShadow |= code_selCtr[sfmap_i] << (32 - bsLiveShadow - n);
1161                    bsLiveShadow += n;
1162    
1163                    gs++;
1164                }
1165    
1166                gs = ge + 1;
1167                selCtr++;
1168            }
1169    
1170            this.bsBuff = bsBuffShadow;
1171            this.bsLive = bsLiveShadow;
1172        }
1173    
1174        private void moveToFrontCodeAndSend() throws IOException {
1175            bsW(24, this.origPtr);
1176            generateMTFValues();
1177            sendMTFValues();
1178        }
1179    
1180        /**
1181         * This is the most hammered method of this class.
1182         *
1183         * <p>
1184         * This is the version using unrolled loops. Normally I never use such ones
1185         * in Java code. The unrolling has shown a noticable performance improvement
1186         * on JRE 1.4.2 (Linux i586 / HotSpot Client). Of course it depends on the
1187         * JIT compiler of the vm.
1188         * </p>
1189         */
1190        private boolean mainSimpleSort(final Data dataShadow, final int lo,
1191                                       final int hi, final int d) {
1192            final int bigN = hi - lo + 1;
1193            if (bigN < 2) {
1194                return this.firstAttempt && (this.workDone > this.workLimit);
1195            }
1196    
1197            int hp = 0;
1198            while (INCS[hp] < bigN) {
1199                hp++;
1200            }
1201    
1202            final int[] fmap = dataShadow.fmap;
1203            final char[] quadrant = dataShadow.quadrant;
1204            final byte[] block = dataShadow.block;
1205            final int lastShadow = this.last;
1206            final int lastPlus1 = lastShadow + 1;
1207            final boolean firstAttemptShadow = this.firstAttempt;
1208            final int workLimitShadow = this.workLimit;
1209            int workDoneShadow = this.workDone;
1210    
1211            // Following block contains unrolled code which could be shortened by
1212            // coding it in additional loops.
1213    
1214            HP: while (--hp >= 0) {
1215                final int h = INCS[hp];
1216                final int mj = lo + h - 1;
1217    
1218                for (int i = lo + h; i <= hi;) {
1219                    // copy
1220                    for (int k = 3; (i <= hi) && (--k >= 0); i++) {
1221                        final int v = fmap[i];
1222                        final int vd = v + d;
1223                        int j = i;
1224    
1225                        // for (int a;
1226                        // (j > mj) && mainGtU((a = fmap[j - h]) + d, vd,
1227                        // block, quadrant, lastShadow);
1228                        // j -= h) {
1229                        // fmap[j] = a;
1230                        // }
1231                        //
1232                        // unrolled version:
1233    
1234                        // start inline mainGTU
1235                        boolean onceRunned = false;
1236                        int a = 0;
1237    
1238                        HAMMER: while (true) {
1239                            if (onceRunned) {
1240                                fmap[j] = a;
1241                                if ((j -= h) <= mj) {
1242                                    break HAMMER;
1243                                }
1244                            } else {
1245                                onceRunned = true;
1246                            }
1247    
1248                            a = fmap[j - h];
1249                            int i1 = a + d;
1250                            int i2 = vd;
1251    
1252                            // following could be done in a loop, but
1253                            // unrolled it for performance:
1254                            if (block[i1 + 1] == block[i2 + 1]) {
1255                                if (block[i1 + 2] == block[i2 + 2]) {
1256                                    if (block[i1 + 3] == block[i2 + 3]) {
1257                                        if (block[i1 + 4] == block[i2 + 4]) {
1258                                            if (block[i1 + 5] == block[i2 + 5]) {
1259                                                if (block[(i1 += 6)] == block[(i2 += 6)]) {
1260                                                    int x = lastShadow;
1261                                                    X: while (x > 0) {
1262                                                        x -= 4;
1263    
1264                                                        if (block[i1 + 1] == block[i2 + 1]) {
1265                                                            if (quadrant[i1] == quadrant[i2]) {
1266                                                                if (block[i1 + 2] == block[i2 + 2]) {
1267                                                                    if (quadrant[i1 + 1] == quadrant[i2 + 1]) {
1268                                                                        if (block[i1 + 3] == block[i2 + 3]) {
1269                                                                            if (quadrant[i1 + 2] == quadrant[i2 + 2]) {
1270                                                                                if (block[i1 + 4] == block[i2 + 4]) {
1271                                                                                    if (quadrant[i1 + 3] == quadrant[i2 + 3]) {
1272                                                                                        if ((i1 += 4) >= lastPlus1) {
1273                                                                                            i1 -= lastPlus1;
1274                                                                                        }
1275                                                                                        if ((i2 += 4) >= lastPlus1) {
1276                                                                                            i2 -= lastPlus1;
1277                                                                                        }
1278                                                                                        workDoneShadow++;
1279                                                                                        continue X;
1280                                                                                    } else if ((quadrant[i1 + 3] > quadrant[i2 + 3])) {
1281                                                                                        continue HAMMER;
1282                                                                                    } else {
1283                                                                                        break HAMMER;
1284                                                                                    }
1285                                                                                } else if ((block[i1 + 4] & 0xff) > (block[i2 + 4] & 0xff)) {
1286                                                                                    continue HAMMER;
1287                                                                                } else {
1288                                                                                    break HAMMER;
1289                                                                                }
1290                                                                            } else if ((quadrant[i1 + 2] > quadrant[i2 + 2])) {
1291                                                                                continue HAMMER;
1292                                                                            } else {
1293                                                                                break HAMMER;
1294                                                                            }
1295                                                                        } else if ((block[i1 + 3] & 0xff) > (block[i2 + 3] & 0xff)) {
1296                                                                            continue HAMMER;
1297                                                                        } else {
1298                                                                            break HAMMER;
1299                                                                        }
1300                                                                    } else if ((quadrant[i1 + 1] > quadrant[i2 + 1])) {
1301                                                                        continue HAMMER;
1302                                                                    } else {
1303                                                                        break HAMMER;
1304                                                                    }
1305                                                                } else if ((block[i1 + 2] & 0xff) > (block[i2 + 2] & 0xff)) {
1306                                                                    continue HAMMER;
1307                                                                } else {
1308                                                                    break HAMMER;
1309                                                                }
1310                                                            } else if ((quadrant[i1] > quadrant[i2])) {
1311                                                                continue HAMMER;
1312                                                            } else {
1313                                                                break HAMMER;
1314                                                            }
1315                                                        } else if ((block[i1 + 1] & 0xff) > (block[i2 + 1] & 0xff)) {
1316                                                            continue HAMMER;
1317                                                        } else {
1318                                                            break HAMMER;
1319                                                        }
1320    
1321                                                    }
1322                                                    break HAMMER;
1323                                                } // while x > 0
1324                                                else {
1325                                                    if ((block[i1] & 0xff) > (block[i2] & 0xff)) {
1326                                                        continue HAMMER;
1327                                                    } else {
1328                                                        break HAMMER;
1329                                                    }
1330                                                }
1331                                            } else if ((block[i1 + 5] & 0xff) > (block[i2 + 5] & 0xff)) {
1332                                                continue HAMMER;
1333                                            } else {
1334                                                break HAMMER;
1335                                            }
1336                                        } else if ((block[i1 + 4] & 0xff) > (block[i2 + 4] & 0xff)) {
1337                                            continue HAMMER;
1338                                        } else {
1339                                            break HAMMER;
1340                                        }
1341                                    } else if ((block[i1 + 3] & 0xff) > (block[i2 + 3] & 0xff)) {
1342                                        continue HAMMER;
1343                                    } else {
1344                                        break HAMMER;
1345                                    }
1346                                } else if ((block[i1 + 2] & 0xff) > (block[i2 + 2] & 0xff)) {
1347                                    continue HAMMER;
1348                                } else {
1349                                    break HAMMER;
1350                                }
1351                            } else if ((block[i1 + 1] & 0xff) > (block[i2 + 1] & 0xff)) {
1352                                continue HAMMER;
1353                            } else {
1354                                break HAMMER;
1355                            }
1356    
1357                        } // HAMMER
1358                        // end inline mainGTU
1359    
1360                        fmap[j] = v;
1361                    }
1362    
1363                    if (firstAttemptShadow && (i <= hi)
1364                        && (workDoneShadow > workLimitShadow)) {
1365                        break HP;
1366                    }
1367                }
1368            }
1369    
1370            this.workDone = workDoneShadow;
1371            return firstAttemptShadow && (workDoneShadow > workLimitShadow);
1372        }
1373    
1374        private static void vswap(int[] fmap, int p1, int p2, int n) {
1375            n += p1;
1376            while (p1 < n) {
1377                int t = fmap[p1];
1378                fmap[p1++] = fmap[p2];
1379                fmap[p2++] = t;
1380            }
1381        }
1382    
1383        private static byte med3(byte a, byte b, byte c) {
1384            return (a < b) ? (b < c ? b : a < c ? c : a) : (b > c ? b : a > c ? c
1385                                                            : a);
1386        }
1387    
1388        private void blockSort() {
1389            this.workLimit = WORK_FACTOR * this.last;
1390            this.workDone = 0;
1391            this.blockRandomised = false;
1392            this.firstAttempt = true;
1393            mainSort();
1394    
1395            if (this.firstAttempt && (this.workDone > this.workLimit)) {
1396                randomiseBlock();
1397                this.workLimit = this.workDone = 0;
1398                this.firstAttempt = false;
1399                mainSort();
1400            }
1401    
1402            int[] fmap = this.data.fmap;
1403            this.origPtr = -1;
1404            for (int i = 0, lastShadow = this.last; i <= lastShadow; i++) {
1405                if (fmap[i] == 0) {
1406                    this.origPtr = i;
1407                    break;
1408                }
1409            }
1410    
1411            // assert (this.origPtr != -1) : this.origPtr;
1412        }
1413    
1414        /**
1415         * Method "mainQSort3", file "blocksort.c", BZip2 1.0.2
1416         */
1417        private void mainQSort3(final Data dataShadow, final int loSt,
1418                                final int hiSt, final int dSt) {
1419            final int[] stack_ll = dataShadow.stack_ll;
1420            final int[] stack_hh = dataShadow.stack_hh;
1421            final int[] stack_dd = dataShadow.stack_dd;
1422            final int[] fmap = dataShadow.fmap;
1423            final byte[] block = dataShadow.block;
1424    
1425            stack_ll[0] = loSt;
1426            stack_hh[0] = hiSt;
1427            stack_dd[0] = dSt;
1428    
1429            for (int sp = 1; --sp >= 0;) {
1430                final int lo = stack_ll[sp];
1431                final int hi = stack_hh[sp];
1432                final int d = stack_dd[sp];
1433    
1434                if ((hi - lo < SMALL_THRESH) || (d > DEPTH_THRESH)) {
1435                    if (mainSimpleSort(dataShadow, lo, hi, d)) {
1436                        return;
1437                    }
1438                } else {
1439                    final int d1 = d + 1;
1440                    final int med = med3(block[fmap[lo] + d1],
1441                                         block[fmap[hi] + d1], block[fmap[(lo + hi) >>> 1] + d1]) & 0xff;
1442    
1443                    int unLo = lo;
1444                    int unHi = hi;
1445                    int ltLo = lo;
1446                    int gtHi = hi;
1447    
1448                    while (true) {
1449                        while (unLo <= unHi) {
1450                            final int n = (block[fmap[unLo] + d1] & 0xff)
1451                                - med;
1452                            if (n == 0) {
1453                                final int temp = fmap[unLo];
1454                                fmap[unLo++] = fmap[ltLo];
1455                                fmap[ltLo++] = temp;
1456                            } else if (n < 0) {
1457                                unLo++;
1458                            } else {
1459                                break;
1460                            }
1461                        }
1462    
1463                        while (unLo <= unHi) {
1464                            final int n = (block[fmap[unHi] + d1] & 0xff)
1465                                - med;
1466                            if (n == 0) {
1467                                final int temp = fmap[unHi];
1468                                fmap[unHi--] = fmap[gtHi];
1469                                fmap[gtHi--] = temp;
1470                            } else if (n > 0) {
1471                                unHi--;
1472                            } else {
1473                                break;
1474                            }
1475                        }
1476    
1477                        if (unLo <= unHi) {
1478                            final int temp = fmap[unLo];
1479                            fmap[unLo++] = fmap[unHi];
1480                            fmap[unHi--] = temp;
1481                        } else {
1482                            break;
1483                        }
1484                    }
1485    
1486                    if (gtHi < ltLo) {
1487                        stack_ll[sp] = lo;
1488                        stack_hh[sp] = hi;
1489                        stack_dd[sp] = d1;
1490                        sp++;
1491                    } else {
1492                        int n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo)
1493                            : (unLo - ltLo);
1494                        vswap(fmap, lo, unLo - n, n);
1495                        int m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi)
1496                            : (gtHi - unHi);
1497                        vswap(fmap, unLo, hi - m + 1, m);
1498    
1499                        n = lo + unLo - ltLo - 1;
1500                        m = hi - (gtHi - unHi) + 1;
1501    
1502                        stack_ll[sp] = lo;
1503                        stack_hh[sp] = n;
1504                        stack_dd[sp] = d;
1505                        sp++;
1506    
1507                        stack_ll[sp] = n + 1;
1508                        stack_hh[sp] = m - 1;
1509                        stack_dd[sp] = d1;
1510                        sp++;
1511    
1512                        stack_ll[sp] = m;
1513                        stack_hh[sp] = hi;
1514                        stack_dd[sp] = d;
1515                        sp++;
1516                    }
1517                }
1518            }
1519        }
1520    
1521        private void mainSort() {
1522            final Data dataShadow = this.data;
1523            final int[] runningOrder = dataShadow.mainSort_runningOrder;
1524            final int[] copy = dataShadow.mainSort_copy;
1525            final boolean[] bigDone = dataShadow.mainSort_bigDone;
1526            final int[] ftab = dataShadow.ftab;
1527            final byte[] block = dataShadow.block;
1528            final int[] fmap = dataShadow.fmap;
1529            final char[] quadrant = dataShadow.quadrant;
1530            final int lastShadow = this.last;
1531            final int workLimitShadow = this.workLimit;
1532            final boolean firstAttemptShadow = this.firstAttempt;
1533    
1534            // Set up the 2-byte frequency table
1535            for (int i = 65537; --i >= 0;) {
1536                ftab[i] = 0;
1537            }
1538    
1539            /*
1540             * In the various block-sized structures, live data runs from 0 to
1541             * last+NUM_OVERSHOOT_BYTES inclusive. First, set up the overshoot area
1542             * for block.
1543             */
1544            for (int i = 0; i < NUM_OVERSHOOT_BYTES; i++) {
1545                block[lastShadow + i + 2] = block[(i % (lastShadow + 1)) + 1];
1546            }
1547            for (int i = lastShadow + NUM_OVERSHOOT_BYTES +1; --i >= 0;) {
1548                quadrant[i] = 0;
1549            }
1550            block[0] = block[lastShadow + 1];
1551    
1552            // Complete the initial radix sort:
1553    
1554            int c1 = block[0] & 0xff;
1555            for (int i = 0; i <= lastShadow; i++) {
1556                final int c2 = block[i + 1] & 0xff;
1557                ftab[(c1 << 8) + c2]++;
1558                c1 = c2;
1559            }
1560    
1561            for (int i = 1; i <= 65536; i++)
1562                ftab[i] += ftab[i - 1];
1563    
1564            c1 = block[1] & 0xff;
1565            for (int i = 0; i < lastShadow; i++) {
1566                final int c2 = block[i + 2] & 0xff;
1567                fmap[--ftab[(c1 << 8) + c2]] = i;
1568                c1 = c2;
1569            }
1570    
1571            fmap[--ftab[((block[lastShadow + 1] & 0xff) << 8) + (block[1] & 0xff)]] = lastShadow;
1572    
1573            /*
1574             * Now ftab contains the first loc of every small bucket. Calculate the
1575             * running order, from smallest to largest big bucket.
1576             */
1577            for (int i = 256; --i >= 0;) {
1578                bigDone[i] = false;
1579                runningOrder[i] = i;
1580            }
1581    
1582            for (int h = 364; h != 1;) {
1583                h /= 3;
1584                for (int i = h; i <= 255; i++) {
1585                    final int vv = runningOrder[i];
1586                    final int a = ftab[(vv + 1) << 8] - ftab[vv << 8];
1587                    final int b = h - 1;
1588                    int j = i;
1589                    for (int ro = runningOrder[j - h]; (ftab[(ro + 1) << 8] - ftab[ro << 8]) > a; ro = runningOrder[j
1590                                                                                                                    - h]) {
1591                        runningOrder[j] = ro;
1592                        j -= h;
1593                        if (j <= b) {
1594                            break;
1595                        }
1596                    }
1597                    runningOrder[j] = vv;
1598                }
1599            }
1600    
1601            /*
1602             * The main sorting loop.
1603             */
1604            for (int i = 0; i <= 255; i++) {
1605                /*
1606                 * Process big buckets, starting with the least full.
1607                 */
1608                final int ss = runningOrder[i];
1609    
1610                // Step 1:
1611                /*
1612                 * Complete the big bucket [ss] by quicksorting any unsorted small
1613                 * buckets [ss, j]. Hopefully previous pointer-scanning phases have
1614                 * already completed many of the small buckets [ss, j], so we don't
1615                 * have to sort them at all.
1616                 */
1617                for (int j = 0; j <= 255; j++) {
1618                    final int sb = (ss << 8) + j;
1619                    final int ftab_sb = ftab[sb];
1620                    if ((ftab_sb & SETMASK) != SETMASK) {
1621                        final int lo = ftab_sb & CLEARMASK;
1622                        final int hi = (ftab[sb + 1] & CLEARMASK) - 1;
1623                        if (hi > lo) {
1624                            mainQSort3(dataShadow, lo, hi, 2);
1625                            if (firstAttemptShadow
1626                                && (this.workDone > workLimitShadow)) {
1627                                return;
1628                            }
1629                        }
1630                        ftab[sb] = ftab_sb | SETMASK;
1631                    }
1632                }
1633    
1634                // Step 2:
1635                // Now scan this big bucket so as to synthesise the
1636                // sorted order for small buckets [t, ss] for all t != ss.
1637    
1638                for (int j = 0; j <= 255; j++) {
1639                    copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
1640                }
1641    
1642                for (int j = ftab[ss << 8] & CLEARMASK, hj = (ftab[(ss + 1) << 8] & CLEARMASK); j < hj; j++) {
1643                    final int fmap_j = fmap[j];
1644                    c1 = block[fmap_j] & 0xff;
1645                    if (!bigDone[c1]) {
1646                        fmap[copy[c1]] = (fmap_j == 0) ? lastShadow : (fmap_j - 1);
1647                        copy[c1]++;
1648                    }
1649                }
1650    
1651                for (int j = 256; --j >= 0;)
1652                    ftab[(j << 8) + ss] |= SETMASK;
1653    
1654                // Step 3:
1655                /*
1656                 * The ss big bucket is now done. Record this fact, and update the
1657                 * quadrant descriptors. Remember to update quadrants in the
1658                 * overshoot area too, if necessary. The "if (i < 255)" test merely
1659                 * skips this updating for the last bucket processed, since updating
1660                 * for the last bucket is pointless.
1661                 */
1662                bigDone[ss] = true;
1663    
1664                if (i < 255) {
1665                    final int bbStart = ftab[ss << 8] & CLEARMASK;
1666                    final int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart;
1667                    int shifts = 0;
1668    
1669                    while ((bbSize >> shifts) > 65534) {
1670                        shifts++;
1671                    }
1672    
1673                    for (int j = 0; j < bbSize; j++) {
1674                        final int a2update = fmap[bbStart + j];
1675                        final char qVal = (char) (j >> shifts);
1676                        quadrant[a2update] = qVal;
1677                        if (a2update < NUM_OVERSHOOT_BYTES) {
1678                            quadrant[a2update + lastShadow + 1] = qVal;
1679                        }
1680                    }
1681                }
1682    
1683            }
1684        }
1685    
1686        private void randomiseBlock() {
1687            final boolean[] inUse = this.data.inUse;
1688            final byte[] block = this.data.block;
1689            final int lastShadow = this.last;
1690    
1691            for (int i = 256; --i >= 0;)
1692                inUse[i] = false;
1693    
1694            int rNToGo = 0;
1695            int rTPos = 0;
1696            for (int i = 0, j = 1; i <= lastShadow; i = j, j++) {
1697                if (rNToGo == 0) {
1698                    rNToGo = (char) Rand.rNums(rTPos);
1699                    if (++rTPos == 512) {
1700                        rTPos = 0;
1701                    }
1702                }
1703    
1704                rNToGo--;
1705                block[j] ^= ((rNToGo == 1) ? 1 : 0);
1706    
1707                // handle 16 bit signed numbers
1708                inUse[block[j] & 0xff] = true;
1709            }
1710    
1711            this.blockRandomised = true;
1712        }
1713    
1714        private void generateMTFValues() {
1715            final int lastShadow = this.last;
1716            final Data dataShadow = this.data;
1717            final boolean[] inUse = dataShadow.inUse;
1718            final byte[] block = dataShadow.block;
1719            final int[] fmap = dataShadow.fmap;
1720            final char[] sfmap = dataShadow.sfmap;
1721            final int[] mtfFreq = dataShadow.mtfFreq;
1722            final byte[] unseqToSeq = dataShadow.unseqToSeq;
1723            final byte[] yy = dataShadow.generateMTFValues_yy;
1724    
1725            // make maps
1726            int nInUseShadow = 0;
1727            for (int i = 0; i < 256; i++) {
1728                if (inUse[i]) {
1729                    unseqToSeq[i] = (byte) nInUseShadow;
1730                    nInUseShadow++;
1731                }
1732            }
1733            this.nInUse = nInUseShadow;
1734    
1735            final int eob = nInUseShadow + 1;
1736    
1737            for (int i = eob; i >= 0; i--) {
1738                mtfFreq[i] = 0;
1739            }
1740    
1741            for (int i = nInUseShadow; --i >= 0;) {
1742                yy[i] = (byte) i;
1743            }
1744    
1745            int wr = 0;
1746            int zPend = 0;
1747    
1748            for (int i = 0; i <= lastShadow; i++) {
1749                final byte ll_i = unseqToSeq[block[fmap[i]] & 0xff];
1750                byte tmp = yy[0];
1751                int j = 0;
1752    
1753                while (ll_i != tmp) {
1754                    j++;
1755                    byte tmp2 = tmp;
1756                    tmp = yy[j];
1757                    yy[j] = tmp2;
1758                }
1759                yy[0] = tmp;
1760    
1761                if (j == 0) {
1762                    zPend++;
1763                } else {
1764                    if (zPend > 0) {
1765                        zPend--;
1766                        while (true) {
1767                            if ((zPend & 1) == 0) {
1768                                sfmap[wr] = RUNA;
1769                                wr++;
1770                                mtfFreq[RUNA]++;
1771                            } else {
1772                                sfmap[wr] = RUNB;
1773                                wr++;
1774                                mtfFreq[RUNB]++;
1775                            }
1776    
1777                            if (zPend >= 2) {
1778                                zPend = (zPend - 2) >> 1;
1779                            } else {
1780                                break;
1781                            }
1782                        }
1783                        zPend = 0;
1784                    }
1785                    sfmap[wr] = (char) (j + 1);
1786                    wr++;
1787                    mtfFreq[j + 1]++;
1788                }
1789            }
1790    
1791            if (zPend > 0) {
1792                zPend--;
1793                while (true) {
1794                    if ((zPend & 1) == 0) {
1795                        sfmap[wr] = RUNA;
1796                        wr++;
1797                        mtfFreq[RUNA]++;
1798                    } else {
1799                        sfmap[wr] = RUNB;
1800                        wr++;
1801                        mtfFreq[RUNB]++;
1802                    }
1803    
1804                    if (zPend >= 2) {
1805                        zPend = (zPend - 2) >> 1;
1806                    } else {
1807                        break;
1808                    }
1809                }
1810            }
1811    
1812            sfmap[wr] = (char) eob;
1813            mtfFreq[eob]++;
1814            this.nMTF = wr + 1;
1815        }
1816    
1817        private static final class Data extends Object {
1818    
1819            // with blockSize 900k
1820            final boolean[] inUse = new boolean[256]; // 256 byte
1821            final byte[] unseqToSeq = new byte[256]; // 256 byte
1822            final int[] mtfFreq = new int[MAX_ALPHA_SIZE]; // 1032 byte
1823            final byte[] selector = new byte[MAX_SELECTORS]; // 18002 byte
1824            final byte[] selectorMtf = new byte[MAX_SELECTORS]; // 18002 byte
1825    
1826            final byte[] generateMTFValues_yy = new byte[256]; // 256 byte
1827            final byte[][] sendMTFValues_len = new byte[N_GROUPS][MAX_ALPHA_SIZE]; // 1548
1828            // byte
1829            final int[][] sendMTFValues_rfreq = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192
1830            // byte
1831            final int[] sendMTFValues_fave = new int[N_GROUPS]; // 24 byte
1832            final short[] sendMTFValues_cost = new short[N_GROUPS]; // 12 byte
1833            final int[][] sendMTFValues_code = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192
1834            // byte
1835            final byte[] sendMTFValues2_pos = new byte[N_GROUPS]; // 6 byte
1836            final boolean[] sentMTFValues4_inUse16 = new boolean[16]; // 16 byte
1837    
1838            final int[] stack_ll = new int[QSORT_STACK_SIZE]; // 4000 byte
1839            final int[] stack_hh = new int[QSORT_STACK_SIZE]; // 4000 byte
1840            final int[] stack_dd = new int[QSORT_STACK_SIZE]; // 4000 byte
1841    
1842            final int[] mainSort_runningOrder = new int[256]; // 1024 byte
1843            final int[] mainSort_copy = new int[256]; // 1024 byte
1844            final boolean[] mainSort_bigDone = new boolean[256]; // 256 byte
1845    
1846            final int[] heap = new int[MAX_ALPHA_SIZE + 2]; // 1040 byte
1847            final int[] weight = new int[MAX_ALPHA_SIZE * 2]; // 2064 byte
1848            final int[] parent = new int[MAX_ALPHA_SIZE * 2]; // 2064 byte
1849    
1850            final int[] ftab = new int[65537]; // 262148 byte
1851            // ------------
1852            // 333408 byte
1853    
1854            final byte[] block; // 900021 byte
1855            final int[] fmap; // 3600000 byte
1856            final char[] sfmap; // 3600000 byte
1857            // ------------
1858            // 8433529 byte
1859            // ============
1860    
1861            /**
1862             * Array instance identical to sfmap, both are used only
1863             * temporarily and indepently, so we do not need to allocate
1864             * additional memory.
1865             */
1866            final char[] quadrant;
1867    
1868            Data(int blockSize100k) {
1869                super();
1870    
1871                final int n = blockSize100k * BZip2Constants.BASEBLOCKSIZE;
1872                this.block = new byte[(n + 1 + NUM_OVERSHOOT_BYTES)];
1873                this.fmap = new int[n];
1874                this.sfmap = new char[2 * n];
1875                this.quadrant = this.sfmap;
1876            }
1877    
1878        }
1879    
1880    }