CBZip2OutputStream


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