Clover coverage report - Ant Coverage
Coverage timestamp: Tue Apr 8 2003 20:43:55 EST
file stats: LOC: 1,673   Methods: 33
NCLOC: 1,255   Classes: 2
 
 Source file Conditionals Statements Methods TOTAL
CBZip2OutputStream.java 89.8% 94.2% 93.9% 92.9%
 1   
 /*
 2   
  * The Apache Software License, Version 1.1
 3   
  *
 4   
  * Copyright (c) 2001-2002 The Apache Software Foundation.  All rights
 5   
  * reserved.
 6   
  *
 7   
  * Redistribution and use in source and binary forms, with or without
 8   
  * modification, are permitted provided that the following conditions
 9   
  * are met:
 10   
  *
 11   
  * 1. Redistributions of source code must retain the above copyright
 12   
  *    notice, this list of conditions and the following disclaimer.
 13   
  *
 14   
  * 2. Redistributions in binary form must reproduce the above copyright
 15   
  *    notice, this list of conditions and the following disclaimer in
 16   
  *    the documentation and/or other materials provided with the
 17   
  *    distribution.
 18   
  *
 19   
  * 3. The end-user documentation included with the redistribution, if
 20   
  *    any, must include the following acknowlegement:
 21   
  *       "This product includes software developed by the
 22   
  *        Apache Software Foundation (http://www.apache.org/)."
 23   
  *    Alternately, this acknowlegement may appear in the software itself,
 24   
  *    if and wherever such third-party acknowlegements normally appear.
 25   
  *
 26   
  * 4. The names "Ant" and "Apache Software
 27   
  *    Foundation" must not be used to endorse or promote products derived
 28   
  *    from this software without prior written permission. For written
 29   
  *    permission, please contact apache@apache.org.
 30   
  *
 31   
  * 5. Products derived from this software may not be called "Apache"
 32   
  *    nor may "Apache" appear in their names without prior written
 33   
  *    permission of the Apache Group.
 34   
  *
 35   
  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 36   
  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 37   
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 38   
  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 39   
  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 40   
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 41   
  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 42   
  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 43   
  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 44   
  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 45   
  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 46   
  * SUCH DAMAGE.
 47   
  * ====================================================================
 48   
  *
 49   
  * This software consists of voluntary contributions made by many
 50   
  * individuals on behalf of the Apache Software Foundation.  For more
 51   
  * information on the Apache Software Foundation, please see
 52   
  * <http://www.apache.org/>.
 53   
  */
 54   
 
 55   
 /*
 56   
  * This package is based on the work done by Keiron Liddle, Aftex Software
 57   
  * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
 58   
  * great code.
 59   
  */
 60   
 
 61   
 package org.apache.tools.bzip2;
 62   
 
 63   
 import java.io.OutputStream;
 64   
 import java.io.IOException;
 65   
 
 66   
 /**
 67   
  * An output stream that compresses into the BZip2 format (without the file
 68   
  * header chars) into another stream.
 69   
  *
 70   
  * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a>
 71   
  *
 72   
  * TODO:    Update to BZip2 1.0.1
 73   
  */
 74   
 public class CBZip2OutputStream extends OutputStream implements BZip2Constants {
 75   
     protected static final int SETMASK = (1 << 21);
 76   
     protected static final int CLEARMASK = (~SETMASK);
 77   
     protected static final int GREATER_ICOST = 15;
 78   
     protected static final int LESSER_ICOST = 0;
 79   
     protected static final int SMALL_THRESH = 20;
 80   
     protected static final int DEPTH_THRESH = 10;
 81   
 
 82   
     /*
 83   
       If you are ever unlucky/improbable enough
 84   
       to get a stack overflow whilst sorting,
 85   
       increase the following constant and try
 86   
       again.  In practice I have never seen the
 87   
       stack go above 27 elems, so the following
 88   
       limit seems very generous.
 89   
     */
 90   
     protected static final int QSORT_STACK_SIZE = 1000;
 91   
 
 92  0
     private static void panic() {
 93  0
         System.out.println("panic");
 94   
         //throw new CError();
 95   
     }
 96   
 
 97  8
     private void makeMaps() {
 98  8
         int i;
 99  8
         nInUse = 0;
 100  8
         for (i = 0; i < 256; i++) {
 101  2048
             if (inUse[i]) {
 102  1847
                 seqToUnseq[nInUse] = (char) i;
 103  1847
                 unseqToSeq[i] = (char) nInUse;
 104  1847
                 nInUse++;
 105   
             }
 106   
         }
 107   
     }
 108   
 
 109  184
     protected static void hbMakeCodeLengths(char[] len, int[] freq,
 110   
                                             int alphaSize, int maxLen) {
 111   
         /*
 112   
           Nodes and heap entries run from 1.  Entry 0
 113   
           for both the heap and nodes is a sentinel.
 114   
         */
 115  184
         int nNodes, nHeap, n1, n2, i, j, k;
 116  184
         boolean  tooLong;
 117   
 
 118  184
         int[] heap = new int[MAX_ALPHA_SIZE + 2];
 119  184
         int[] weight = new int[MAX_ALPHA_SIZE * 2];
 120  184
         int[] parent = new int[MAX_ALPHA_SIZE * 2];
 121   
 
 122  184
         for (i = 0; i < alphaSize; i++) {
 123  44256
             weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
 124   
         }
 125   
 
 126  184
         while (true) {
 127  184
             nNodes = alphaSize;
 128  184
             nHeap = 0;
 129   
 
 130  184
             heap[0] = 0;
 131  184
             weight[0] = 0;
 132  184
             parent[0] = -2;
 133   
 
 134  184
             for (i = 1; i <= alphaSize; i++) {
 135  44256
                 parent[i] = -1;
 136  44256
                 nHeap++;
 137  44256
                 heap[nHeap] = i;
 138   
                 {
 139  44256
                     int zz, tmp;
 140  44256
                     zz = nHeap;
 141  44256
                     tmp = heap[zz];
 142  44256
                     while (weight[tmp] < weight[heap[zz >> 1]]) {
 143  29805
                         heap[zz] = heap[zz >> 1];
 144  29805
                         zz >>= 1;
 145   
                     }
 146  44256
                     heap[zz] = tmp;
 147   
                 }
 148   
             }
 149  184
             if (!(nHeap < (MAX_ALPHA_SIZE + 2))) {
 150  0
                 panic();
 151   
             }
 152   
 
 153  184
             while (nHeap > 1) {
 154  44072
                 n1 = heap[1];
 155  44072
                 heap[1] = heap[nHeap];
 156  44072
                 nHeap--;
 157   
                 {
 158  44072
                     int zz = 0, yy = 0, tmp = 0;
 159  44072
                     zz = 1;
 160  44072
                     tmp = heap[zz];
 161  44072
                     while (true) {
 162  290553
                         yy = zz << 1;
 163  290553
                         if (yy > nHeap) {
 164  42342
                             break;
 165   
                         }
 166  248211
                         if (yy < nHeap &&
 167   
                             weight[heap[yy + 1]] < weight[heap[yy]]) {
 168  100827
                             yy++;
 169   
                         }
 170  248211
                         if (weight[tmp] < weight[heap[yy]]) {
 171  1730
                             break;
 172   
                         }
 173  246481
                         heap[zz] = heap[yy];
 174  246481
                         zz = yy;
 175   
                     }
 176  44072
                     heap[zz] = tmp;
 177   
                 }
 178  44072
                 n2 = heap[1];
 179  44072
                 heap[1] = heap[nHeap];
 180  44072
                 nHeap--;
 181   
                 {
 182  44072
                     int zz = 0, yy = 0, tmp = 0;
 183  44072
                     zz = 1;
 184  44072
                     tmp = heap[zz];
 185  44072
                     while (true) {
 186  274950
                         yy = zz << 1;
 187  274950
                         if (yy > nHeap) {
 188  33025
                             break;
 189   
                         }
 190  241925
                         if (yy < nHeap &&
 191   
                             weight[heap[yy + 1]] < weight[heap[yy]]) {
 192  100887
                             yy++;
 193   
                         }
 194  241925
                         if (weight[tmp] < weight[heap[yy]]) {
 195  11047
                             break;
 196   
                         }
 197  230878
                         heap[zz] = heap[yy];
 198  230878
                         zz = yy;
 199   
                     }
 200  44072
                     heap[zz] = tmp;
 201   
                 }
 202  44072
                 nNodes++;
 203  44072
                 parent[n1] = parent[n2] = nNodes;
 204   
 
 205  44072
                 weight[nNodes] = ((weight[n1] & 0xffffff00)
 206   
                                   + (weight[n2] & 0xffffff00))
 207   
                     | (1 + (((weight[n1] & 0x000000ff) >
 208   
                              (weight[n2] & 0x000000ff)) ?
 209   
                             (weight[n1] & 0x000000ff) :
 210   
                             (weight[n2] & 0x000000ff)));
 211   
 
 212  44072
                 parent[nNodes] = -1;
 213  44072
                 nHeap++;
 214  44072
                 heap[nHeap] = nNodes;
 215   
                 {
 216  44072
                     int zz = 0, tmp = 0;
 217  44072
                     zz = nHeap;
 218  44072
                     tmp = heap[zz];
 219  44072
                     while (weight[tmp] < weight[heap[zz >> 1]]) {
 220  1523
                         heap[zz] = heap[zz >> 1];
 221  1523
                         zz >>= 1;
 222   
                     }
 223  44072
                     heap[zz] = tmp;
 224   
                 }
 225   
             }
 226  184
             if (!(nNodes < (MAX_ALPHA_SIZE * 2))) {
 227  0
                 panic();
 228   
             }
 229   
 
 230  184
             tooLong = false;
 231  184
             for (i = 1; i <= alphaSize; i++) {
 232  44256
                 j = 0;
 233  44256
                 k = i;
 234  44256
                 while (parent[k] >= 0) {
 235  370730
                     k = parent[k];
 236  370730
                     j++;
 237   
                 }
 238  44256
                 len[i - 1] = (char) j;
 239  44256
                 if (j > maxLen) {
 240  0
                     tooLong = true;
 241   
                 }
 242   
             }
 243   
 
 244  184
             if (!tooLong) {
 245  184
                 break;
 246   
             }
 247   
 
 248  0
             for (i = 1; i < alphaSize; i++) {
 249  0
                 j = weight[i] >> 8;
 250  0
                 j = 1 + (j / 2);
 251  0
                 weight[i] = j << 8;
 252   
             }
 253   
         }
 254   
     }
 255   
 
 256   
     /*
 257   
       index of the last char in the block, so
 258   
       the block size == last + 1.
 259   
     */
 260   
     int last;
 261   
 
 262   
     /*
 263   
       index in zptr[] of original string after sorting.
 264   
     */
 265   
     int origPtr;
 266   
 
 267   
     /*
 268   
       always: in the range 0 .. 9.
 269   
       The current block size is 100000 * this number.
 270   
     */
 271   
     int blockSize100k;
 272   
 
 273   
     boolean blockRandomised;
 274   
 
 275   
     int bytesIn;
 276   
     int bytesOut;
 277   
     int bsBuff;
 278   
     int bsLive;
 279   
     CRC mCrc = new CRC();
 280   
 
 281   
     private boolean[] inUse = new boolean[256];
 282   
     private int nInUse;
 283   
 
 284   
     private char[] seqToUnseq = new char[256];
 285   
     private char[] unseqToSeq = new char[256];
 286   
 
 287   
     private char[] selector = new char[MAX_SELECTORS];
 288   
     private char[] selectorMtf = new char[MAX_SELECTORS];
 289   
 
 290   
     private char[] block;
 291   
     private int[] quadrant;
 292   
     private int[] zptr;
 293   
     private short[] szptr;
 294   
     private int[] ftab;
 295   
 
 296   
     private int nMTF;
 297   
 
 298   
     private int[] mtfFreq = new int[MAX_ALPHA_SIZE];
 299   
 
 300   
     /*
 301   
      * Used when sorting.  If too many long comparisons
 302   
      * happen, we stop sorting, randomise the block
 303   
      * slightly, and try again.
 304   
      */
 305   
     private int workFactor;
 306   
     private int workDone;
 307   
     private int workLimit;
 308   
     private boolean firstAttempt;
 309   
     private int nBlocksRandomised;
 310   
 
 311   
     private int currentChar = -1;
 312   
     private int runLength = 0;
 313   
 
 314  5
     public CBZip2OutputStream(OutputStream inStream) throws IOException {
 315  5
         this(inStream, 9);
 316   
     }
 317   
 
 318  5
     public CBZip2OutputStream(OutputStream inStream, int inBlockSize)
 319   
         throws IOException {
 320  5
         block = null;
 321  5
         quadrant = null;
 322  5
         zptr = null;
 323  5
         ftab = null;
 324   
 
 325  5
         bsSetStream(inStream);
 326   
 
 327  5
         workFactor = 50;
 328  5
         if (inBlockSize > 9) {
 329  0
             inBlockSize = 9;
 330   
         }
 331  5
         if (inBlockSize < 1) {
 332  0
             inBlockSize = 1;
 333   
         }
 334  5
         blockSize100k = inBlockSize;
 335  5
         allocateCompressStructures();
 336  5
         initialize();
 337  5
         initBlock();
 338   
     }
 339   
 
 340   
     /**
 341   
      *
 342   
      * modified by Oliver Merkel, 010128
 343   
      *
 344   
      */
 345  3256320
     public void write(int bv) throws IOException {
 346  3256320
         int b = (256 + bv) % 256;
 347  3256320
         if (currentChar != -1) {
 348  3255458
             if (currentChar == b) {
 349  510734
                 runLength++;
 350  510734
                 if (runLength > 254) {
 351  857
                     writeRun();
 352  857
                     currentChar = -1;
 353  857
                     runLength = 0;
 354   
                 }
 355   
             } else {
 356  2744724
                 writeRun();
 357  2744724
                 runLength = 1;
 358  2744724
                 currentChar = b;
 359   
             }
 360   
         } else {
 361  862
             currentChar = b;
 362  862
             runLength++;
 363   
         }
 364   
     }
 365   
 
 366  2745589
     private void writeRun() throws IOException {
 367  2745589
         if (last < allowableBlockSize) {
 368  2745586
             inUse[currentChar] = true;
 369  2745586
             for (int i = 0; i < runLength; i++) {
 370  3256320
                 mCrc.updateCRC((char) currentChar);
 371   
             }
 372  2745586
             switch (runLength) {
 373   
             case 1:
 374  2718205
                 last++;
 375  2718205
                 block[last + 1] = (char) currentChar;
 376  2718205
                 break;
 377   
             case 2:
 378  17183
                 last++;
 379  17183
                 block[last + 1] = (char) currentChar;
 380  17183
                 last++;
 381  17183
                 block[last + 1] = (char) currentChar;
 382  17183
                 break;
 383   
             case 3:
 384  5566
                 last++;
 385  5566
                 block[last + 1] = (char) currentChar;
 386  5566
                 last++;
 387  5566
                 block[last + 1] = (char) currentChar;
 388  5566
                 last++;
 389  5566
                 block[last + 1] = (char) currentChar;
 390  5566
                 break;
 391   
             default:
 392  4632
                 inUse[runLength - 4] = true;
 393  4632
                 last++;
 394  4632
                 block[last + 1] = (char) currentChar;
 395  4632
                 last++;
 396  4632
                 block[last + 1] = (char) currentChar;
 397  4632
                 last++;
 398  4632
                 block[last + 1] = (char) currentChar;
 399  4632
                 last++;
 400  4632
                 block[last + 1] = (char) currentChar;
 401  4632
                 last++;
 402  4632
                 block[last + 1] = (char) (runLength - 4);
 403  4632
                 break;
 404   
             }
 405   
         } else {
 406  3
             endBlock();
 407  3
             initBlock();
 408  3
             writeRun();
 409   
         }
 410   
     }
 411   
 
 412   
     boolean closed = false;
 413   
 
 414  5
     public void finalize() throws Throwable {
 415  5
         close();
 416   
     }
 417   
 
 418  10
     public void close() throws IOException {
 419  10
         if (closed) {
 420  5
             return;
 421   
         }
 422   
 
 423  5
         if (runLength > 0) {
 424  5
             writeRun();
 425   
         }
 426  5
         currentChar = -1;
 427  5
         endBlock();
 428  5
         endCompression();
 429  5
         closed = true;
 430  5
         super.close();
 431  5
         bsStream.close();
 432   
     }
 433   
 
 434  4
     public void flush() throws IOException {
 435  4
         super.flush();
 436  4
         bsStream.flush();
 437   
     }
 438   
 
 439   
     private int blockCRC, combinedCRC;
 440   
 
 441  5
     private void initialize() throws IOException {
 442  5
         bytesIn = 0;
 443  5
         bytesOut = 0;
 444  5
         nBlocksRandomised = 0;
 445   
 
 446   
         /* Write `magic' bytes h indicating file-format == huffmanised,
 447   
            followed by a digit indicating blockSize100k.
 448   
         */
 449  5
         bsPutUChar('h');
 450  5
         bsPutUChar('0' + blockSize100k);
 451   
 
 452  5
         combinedCRC = 0;
 453   
     }
 454   
 
 455   
     private int allowableBlockSize;
 456   
 
 457  8
     private void initBlock() {
 458   
         //        blockNo++;
 459  8
         mCrc.initialiseCRC();
 460  8
         last = -1;
 461   
         //        ch = 0;
 462   
 
 463  8
         for (int i = 0; i < 256; i++) {
 464  2048
             inUse[i] = false;
 465   
         }
 466   
 
 467   
         /* 20 is just a paranoia constant */
 468  8
         allowableBlockSize = baseBlockSize * blockSize100k - 20;
 469   
     }
 470   
 
 471  8
     private void endBlock() throws IOException {
 472  8
         blockCRC = mCrc.getFinalCRC();
 473  8
         combinedCRC = (combinedCRC << 1) | (combinedCRC >>> 31);
 474  8
         combinedCRC ^= blockCRC;
 475   
 
 476   
         /* sort the block and establish posn of original string */
 477  8
         doReversibleTransformation();
 478   
 
 479   
         /*
 480   
           A 6-byte block header, the value chosen arbitrarily
 481   
           as 0x314159265359 :-).  A 32 bit value does not really
 482   
           give a strong enough guarantee that the value will not
 483   
           appear by chance in the compressed datastream.  Worst-case
 484   
           probability of this event, for a 900k block, is about
 485   
           2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
 486   
           For a compressed file of size 100Gb -- about 100000 blocks --
 487   
           only a 48-bit marker will do.  NB: normal compression/
 488   
           decompression do *not* rely on these statistical properties.
 489   
           They are only important when trying to recover blocks from
 490   
           damaged files.
 491   
         */
 492  8
         bsPutUChar(0x31);
 493  8
         bsPutUChar(0x41);
 494  8
         bsPutUChar(0x59);
 495  8
         bsPutUChar(0x26);
 496  8
         bsPutUChar(0x53);
 497  8
         bsPutUChar(0x59);
 498   
 
 499   
         /* Now the block's CRC, so it is in a known place. */
 500  8
         bsPutint(blockCRC);
 501   
 
 502   
         /* Now a single bit indicating randomisation. */
 503  8
         if (blockRandomised) {
 504  0
             bsW(1, 1);
 505  0
             nBlocksRandomised++;
 506   
         } else {
 507  8
             bsW(1, 0);
 508   
         }
 509   
 
 510   
         /* Finally, block's contents proper. */
 511  8
         moveToFrontCodeAndSend();
 512   
     }
 513   
 
 514  5
     private void endCompression() throws IOException {
 515   
         /*
 516   
           Now another magic 48-bit number, 0x177245385090, to
 517   
           indicate the end of the last block.  (sqrt(pi), if
 518   
           you want to know.  I did want to use e, but it contains
 519   
           too much repetition -- 27 18 28 18 28 46 -- for me
 520   
           to feel statistically comfortable.  Call me paranoid.)
 521   
         */
 522  5
         bsPutUChar(0x17);
 523  5
         bsPutUChar(0x72);
 524  5
         bsPutUChar(0x45);
 525  5
         bsPutUChar(0x38);
 526  5
         bsPutUChar(0x50);
 527  5
         bsPutUChar(0x90);
 528   
 
 529  5
         bsPutint(combinedCRC);
 530   
 
 531  5
         bsFinishedWithStream();
 532   
     }
 533   
 
 534  46
     private void hbAssignCodes (int[] code, char[] length, int minLen,
 535   
                                 int maxLen, int alphaSize) {
 536  46
         int n, vec, i;
 537   
 
 538  46
         vec = 0;
 539  46
         for (n = minLen; n <= maxLen; n++) {
 540  221
             for (i = 0; i < alphaSize; i++) {
 541  51189
                 if (length[i] == n) {
 542  11064
                     code[i] = vec;
 543  11064
                     vec++;
 544   
                 }
 545   
             };
 546  221
             vec <<= 1;
 547   
         }
 548   
     }
 549   
 
 550  5
     private void bsSetStream(OutputStream f) {
 551  5
         bsStream = f;
 552  5
         bsLive = 0;
 553  5
         bsBuff = 0;
 554  5
         bytesOut = 0;
 555  5
         bytesIn = 0;
 556   
     }
 557   
 
 558  5
     private void bsFinishedWithStream() throws IOException {
 559  5
         while (bsLive > 0) {
 560  10
             int ch = (bsBuff >> 24);
 561  10
             try {
 562  10
                 bsStream.write(ch); // write 8-bit
 563   
             } catch (IOException e) {
 564  0
                 throw  e;
 565   
             }
 566  10
             bsBuff <<= 8;
 567  10
             bsLive -= 8;
 568  10
             bytesOut++;
 569   
         }
 570   
     }
 571   
 
 572  225176
     private void bsW(int n, int v) throws IOException {
 573  225176
         while (bsLive >= 8) {
 574  81365
             int ch = (bsBuff >> 24);
 575  81365
             try {
 576  81365
                 bsStream.write(ch); // write 8-bit
 577   
             } catch (IOException e) {
 578  0
                 throw e;
 579   
             }
 580  81365
             bsBuff <<= 8;
 581  81365
             bsLive -= 8;
 582  81365
             bytesOut++;
 583   
         }
 584  225176
         bsBuff |= (v << (32 - bsLive - n));
 585  225176
         bsLive += n;
 586   
     }
 587   
 
 588  88
     private void bsPutUChar(int c) throws IOException {
 589  88
         bsW(8, c);
 590   
     }
 591   
 
 592  13
     private void bsPutint(int u) throws IOException {
 593  13
         bsW(8, (u >> 24) & 0xff);
 594  13
         bsW(8, (u >> 16) & 0xff);
 595  13
         bsW(8, (u >>  8) & 0xff);
 596  13
         bsW(8,  u        & 0xff);
 597   
     }
 598   
 
 599  8
     private void bsPutIntVS(int numBits, int c) throws IOException {
 600  8
         bsW(numBits, c);
 601   
     }
 602   
 
 603  8
     private void sendMTFValues() throws IOException {
 604  8
         char len[][] = new char[N_GROUPS][MAX_ALPHA_SIZE];
 605   
 
 606  8
         int v, t, i, j, gs, ge, totc, bt, bc, iter;
 607  8
         int nSelectors = 0, alphaSize, minLen, maxLen, selCtr;
 608  8
         int nGroups, nBytes;
 609   
 
 610  8
         alphaSize = nInUse + 2;
 611  8
         for (t = 0; t < N_GROUPS; t++) {
 612  48
             for (v = 0; v < alphaSize; v++) {
 613  11178
                 len[t][v] = (char) GREATER_ICOST;
 614   
             }
 615   
         }
 616   
 
 617   
         /* Decide how many coding tables to use */
 618  8
         if (nMTF <= 0) {
 619  0
             panic();
 620   
         }
 621   
 
 622  8
         if (nMTF < 200) {
 623  0
             nGroups = 2;
 624  8
         } else if (nMTF < 600) {
 625  0
             nGroups = 3;
 626  8
         } else if (nMTF < 1200) {
 627  1
             nGroups = 4;
 628  7
         } else if (nMTF < 2400) {
 629  0
             nGroups = 5;
 630   
         } else {
 631  7
             nGroups = 6;
 632   
         }
 633   
 
 634   
         /* Generate an initial set of coding tables */ {
 635  8
             int nPart, remF, tFreq, aFreq;
 636   
 
 637  8
             nPart = nGroups;
 638  8
             remF  = nMTF;
 639  8
             gs = 0;
 640  8
             while (nPart > 0) {
 641  46
                 tFreq = remF / nPart;
 642  46
                 ge = gs - 1;
 643  46
                 aFreq = 0;
 644  46
                 while (aFreq < tFreq && ge < alphaSize - 1) {
 645  1876
                     ge++;
 646  1876
                     aFreq += mtfFreq[ge];
 647   
                 }
 648   
 
 649  46
                 if (ge > gs && nPart != nGroups && nPart != 1
 650   
                     && ((nGroups - nPart) % 2 == 1)) {
 651  13
                     aFreq -= mtfFreq[ge];
 652  13
                     ge--;
 653   
                 }
 654   
 
 655  46
                 for (v = 0; v < alphaSize; v++) {
 656  11064
                     if (v >= gs && v <= ge) {
 657  1863
                         len[nPart - 1][v] = (char) LESSER_ICOST;
 658   
                     } else {
 659  9201
                         len[nPart - 1][v] = (char) GREATER_ICOST;
 660   
                     }
 661   
                 }
 662   
 
 663  46
                 nPart--;
 664  46
                 gs = ge + 1;
 665  46
                 remF -= aFreq;
 666   
             }
 667   
         }
 668   
 
 669  8
         int[][] rfreq = new int[N_GROUPS][MAX_ALPHA_SIZE];
 670  8
         int[] fave = new int[N_GROUPS];
 671  8
         short[] cost = new short[N_GROUPS];
 672   
         /*
 673   
           Iterate up to N_ITERS times to improve the tables.
 674   
         */
 675  8
         for (iter = 0; iter < N_ITERS; iter++) {
 676  32
             for (t = 0; t < nGroups; t++) {
 677  184
                 fave[t] = 0;
 678   
             }
 679   
 
 680  32
             for (t = 0; t < nGroups; t++) {
 681  184
                 for (v = 0; v < alphaSize; v++) {
 682  44256
                     rfreq[t][v] = 0;
 683   
                 }
 684   
             }
 685   
 
 686  32
             nSelectors = 0;
 687  32
             totc = 0;
 688  32
             gs = 0;
 689  32
             while (true) {
 690   
 
 691   
                 /* Set group start & end marks. */
 692  16212
                 if (gs >= nMTF) {
 693  32
                     break;
 694   
                 }
 695  16180
                 ge = gs + G_SIZE - 1;
 696  16180
                 if (ge >= nMTF) {
 697  32
                     ge = nMTF - 1;
 698   
                 }
 699   
 
 700   
                 /*
 701   
                   Calculate the cost of this group as coded
 702   
                   by each of the coding tables.
 703   
                 */
 704  16180
                 for (t = 0; t < nGroups; t++) {
 705  96888
                     cost[t] = 0;
 706   
                 }
 707   
 
 708  16180
                 if (nGroups == 6) {
 709  16084
                     short cost0, cost1, cost2, cost3, cost4, cost5;
 710  16084
                     cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
 711  16084
                     for (i = gs; i <= ge; i++) {
 712  803560
                         short icv = szptr[i];
 713  803560
                         cost0 += len[0][icv];
 714  803560
                         cost1 += len[1][icv];
 715  803560
                         cost2 += len[2][icv];
 716  803560
                         cost3 += len[3][icv];
 717  803560
                         cost4 += len[4][icv];
 718  803560
                         cost5 += len[5][icv];
 719   
                     }
 720  16084
                     cost[0] = cost0;
 721  16084
                     cost[1] = cost1;
 722  16084
                     cost[2] = cost2;
 723  16084
                     cost[3] = cost3;
 724  16084
                     cost[4] = cost4;
 725  16084
                     cost[5] = cost5;
 726   
                 } else {
 727  96
                     for (i = gs; i <= ge; i++) {
 728  4648
                         short icv = szptr[i];
 729  4648
                         for (t = 0; t < nGroups; t++) {
 730  18592
                             cost[t] += len[t][icv];
 731   
                         }
 732   
                     }
 733   
                 }
 734   
 
 735   
                 /*
 736   
                   Find the coding table which is best for this group,
 737   
                   and record its identity in the selector table.
 738   
                 */
 739  16180
                 bc = 999999999;
 740  16180
                 bt = -1;
 741  16180
                 for (t = 0; t < nGroups; t++) {
 742  96888
                     if (cost[t] < bc) {
 743  45457
                         bc = cost[t];
 744  45457
                         bt = t;
 745   
                     }
 746   
                 };
 747  16180
                 totc += bc;
 748  16180
                 fave[bt]++;
 749  16180
                 selector[nSelectors] = (char) bt;
 750  16180
                 nSelectors++;
 751   
 
 752   
                 /*
 753   
                   Increment the symbol frequencies for the selected table.
 754   
                 */
 755  16180
                 for (i = gs; i <= ge; i++) {
 756  808208
                     rfreq[bt][szptr[i]]++;
 757   
                 }
 758   
 
 759  16180
                 gs = ge + 1;
 760   
             }
 761   
 
 762   
             /*
 763   
               Recompute the tables based on the accumulated frequencies.
 764   
             */
 765  32
             for (t = 0; t < nGroups; t++) {
 766  184
                 hbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20);
 767   
             }
 768   
         }
 769   
 
 770  8
         rfreq = null;
 771  8
         fave = null;
 772  8
         cost = null;
 773   
 
 774  8
         if (!(nGroups < 8)) {
 775  0
             panic();
 776   
         }
 777  8
         if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / G_SIZE)))) {
 778  0
             panic();
 779   
         }
 780   
 
 781   
 
 782   
         /* Compute MTF values for the selectors. */
 783   
         {
 784  8
             char[] pos = new char[N_GROUPS];
 785  8
             char ll_i, tmp2, tmp;
 786  8
             for (i = 0; i < nGroups; i++) {
 787  46
                 pos[i] = (char) i;
 788   
             }
 789  8
             for (i = 0; i < nSelectors; i++) {
 790  4045
                 ll_i = selector[i];
 791  4045
                 j = 0;
 792  4045
                 tmp = pos[j];
 793  4045
                 while (ll_i != tmp) {
 794  1118
                     j++;
 795  1118
                     tmp2 = tmp;
 796  1118
                     tmp = pos[j];
 797  1118
                     pos[j] = tmp2;
 798   
                 }
 799  4045
                 pos[0] = tmp;
 800  4045
                 selectorMtf[i] = (char) j;
 801   
             }
 802   
         }
 803   
 
 804  8
         int[][] code = new int[N_GROUPS][MAX_ALPHA_SIZE];
 805   
 
 806   
         /* Assign actual codes for the tables. */
 807  8
         for (t = 0; t < nGroups; t++) {
 808  46
             minLen = 32;
 809  46
             maxLen = 0;
 810  46
             for (i = 0; i < alphaSize; i++) {
 811  11064
                 if (len[t][i] > maxLen) {
 812  124
                     maxLen = len[t][i];
 813   
                 }
 814  11064
                 if (len[t][i] < minLen) {
 815  86
                     minLen = len[t][i];
 816   
                 }
 817   
             }
 818  46
             if (maxLen > 20) {
 819  0
                 panic();
 820   
             }
 821  46
             if (minLen < 1) {
 822  0
                 panic();
 823   
             }
 824  46
             hbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
 825   
         }
 826   
 
 827   
         /* Transmit the mapping table. */
 828   
         {
 829  8
             boolean[] inUse16 = new boolean[16];
 830  8
             for (i = 0; i < 16; i++) {
 831  128
                 inUse16[i] = false;
 832  128
                 for (j = 0; j < 16; j++) {
 833  2048
                     if (inUse[i * 16 + j]) {
 834  1847
                         inUse16[i] = true;
 835   
                     }
 836   
                 }
 837   
             }
 838   
 
 839  8
             nBytes = bytesOut;
 840  8
             for (i = 0; i < 16; i++) {
 841  128
                 if (inUse16[i]) {
 842  121
                     bsW(1, 1);
 843   
                 } else {
 844  7
                     bsW(1, 0);
 845   
                 }
 846   
             }
 847   
 
 848  8
             for (i = 0; i < 16; i++) {
 849  128
                 if (inUse16[i]) {
 850  121
                     for (j = 0; j < 16; j++) {
 851  1936
                         if (inUse[i * 16 + j]) {
 852  1847
                             bsW(1, 1);
 853   
                         } else {
 854  89
                             bsW(1, 0);
 855   
                         }
 856   
                     }
 857   
                 }
 858   
             }
 859   
 
 860   
         }
 861   
 
 862   
         /* Now the selectors. */
 863  8
         nBytes = bytesOut;
 864  8
         bsW (3, nGroups);
 865  8
         bsW (15, nSelectors);
 866  8
         for (i = 0; i < nSelectors; i++) {
 867  4045
             for (j = 0; j < selectorMtf[i]; j++) {
 868  1118
                 bsW(1, 1);
 869   
             }
 870  4045
             bsW(1, 0);
 871   
         }
 872   
 
 873   
         /* Now the coding tables. */
 874  8
         nBytes = bytesOut;
 875   
 
 876  8
         for (t = 0; t < nGroups; t++) {
 877  46
             int curr = len[t][0];
 878  46
             bsW(5, curr);
 879  46
             for (i = 0; i < alphaSize; i++) {
 880  11064
                 while (curr < len[t][i]) {
 881  2362
                     bsW(2, 2);
 882  2362
                     curr++; /* 10 */
 883   
                 }
 884  11064
                 while (curr > len[t][i]) {
 885  2253
                     bsW(2, 3);
 886  2253
                     curr--; /* 11 */
 887   
                 }
 888  11064
                 bsW (1, 0);
 889   
             }
 890   
         }
 891   
 
 892   
         /* And finally, the block data proper */
 893  8
         nBytes = bytesOut;
 894  8
         selCtr = 0;
 895  8
         gs = 0;
 896  8
         while (true) {
 897  4053
             if (gs >= nMTF) {
 898  8
                 break;
 899   
             }
 900  4045
             ge = gs + G_SIZE - 1;
 901  4045
             if (ge >= nMTF) {
 902  8
                 ge = nMTF - 1;
 903   
             }
 904  4045
             for (i = gs; i <= ge; i++) {
 905  202052
                 bsW(len[selector[selCtr]][szptr[i]],
 906   
                     code[selector[selCtr]][szptr[i]]);
 907   
             }
 908   
 
 909  4045
             gs = ge + 1;
 910  4045
             selCtr++;
 911   
         }
 912  8
         if (!(selCtr == nSelectors)) {
 913  0
             panic();
 914   
         }
 915   
     }
 916   
 
 917  8
     private void moveToFrontCodeAndSend () throws IOException {
 918  8
         bsPutIntVS(24, origPtr);
 919  8
         generateMTFValues();
 920  8
         sendMTFValues();
 921   
     }
 922   
 
 923   
     private OutputStream bsStream;
 924   
 
 925  16885
     private void simpleSort(int lo, int hi, int d) {
 926  16885
         int i, j, h, bigN, hp;
 927  16885
         int v;
 928   
 
 929  16885
         bigN = hi - lo + 1;
 930  16885
         if (bigN < 2) {
 931  1225
             return;
 932   
         }
 933   
 
 934  15660
         hp = 0;
 935  15660
         while (incs[hp] < bigN) {
 936  63192
             hp++;
 937   
         }
 938  15660
         hp--;
 939   
 
 940  15660
         for (; hp >= 0; hp--) {
 941  63192
             h = incs[hp];
 942   
 
 943  63192
             i = lo + h;
 944  63192
             while (true) {
 945   
                 /* copy 1 */
 946  1705763
                 if (i > hi) {
 947  47193
                     break;
 948   
                 }
 949  1658570
                 v = zptr[i];
 950  1658570
                 j = i;
 951  1658570
                 while (fullGtU(zptr[j - h] + d, v + d)) {
 952  1485939
                     zptr[j] = zptr[j - h];
 953  1485939
                     j = j - h;
 954  1485939
                     if (j <= (lo + h - 1)) {
 955  338942
                         break;
 956   
                     }
 957   
                 }
 958  1658570
                 zptr[j] = v;
 959  1658570
                 i++;
 960   
 
 961   
                 /* copy 2 */
 962  1658570
                 if (i > hi) {
 963  2106
                     break;
 964   
                 }
 965  1656464
                 v = zptr[i];
 966  1656464
                 j = i;
 967  1656464
                 while (fullGtU(zptr[j - h] + d, v + d)) {
 968  1503409
                     zptr[j] = zptr[j - h];
 969  1503409
                     j = j - h;
 970  1503409
                     if (j <= (lo + h - 1)) {
 971  330168
                         break;
 972   
                     }
 973   
                 }
 974  1656464
                 zptr[j] = v;
 975  1656464
                 i++;
 976   
 
 977   
                 /* copy 3 */
 978  1656464
                 if (i > hi) {
 979  13893
                     break;
 980   
                 }
 981  1642571
                 v = zptr[i];
 982  1642571
                 j = i;
 983  1642571
                 while (fullGtU(zptr[j - h] + d, v + d)) {
 984  1510857
                     zptr[j] = zptr[j - h];
 985  1510857
                     j = j - h;
 986  1510857
                     if (j <= (lo + h - 1)) {
 987  308188
                         break;
 988   
                     }
 989   
                 }
 990  1642571
                 zptr[j] = v;
 991  1642571
                 i++;
 992   
 
 993  1642571
                 if (workDone > workLimit && firstAttempt) {
 994  0
                     return;
 995   
                 }
 996   
             }
 997   
         }
 998   
     }
 999   
 
 1000  3088
     private void vswap(int p1, int p2, int n) {
 1001  3088
         int temp = 0;
 1002  3088
         while (n > 0) {
 1003  133912
             temp = zptr[p1];
 1004  133912
             zptr[p1] = zptr[p2];
 1005  133912
             zptr[p2] = temp;
 1006  133912
             p1++;
 1007  133912
             p2++;
 1008  133912
             n--;
 1009   
         }
 1010   
     }
 1011   
 
 1012  96761
     private char med3(char a, char b, char c) {
 1013  96761
         char t;
 1014  96761
         if (a > b) {
 1015  476
             t = a;
 1016  476
             a = b;
 1017  476
             b = t;
 1018   
         }
 1019  96761
         if (b > c) {
 1020  621
             t = b;
 1021  621
             b = c;
 1022  621
             c = t;
 1023   
         }
 1024  96761
         if (a > b) {
 1025  156
             b = a;
 1026   
         }
 1027  96761
         return b;
 1028   
     }
 1029   
 
 1030   
     private class StackElem {
 1031   
         int ll;
 1032   
         int hh;
 1033   
         int dd;
 1034   
     }
 1035   
 
 1036  13796
     private void qSort3(int loSt, int hiSt, int dSt) {
 1037  13796
         int unLo, unHi, ltLo, gtHi, med, n, m;
 1038  13796
         int sp, lo, hi, d;
 1039  13796
         StackElem[] stack = new StackElem[QSORT_STACK_SIZE];
 1040  13796
         for (int count = 0; count < QSORT_STACK_SIZE; count++) {
 1041  13796000
             stack[count] = new StackElem();
 1042   
         }
 1043   
 
 1044  13796
         sp = 0;
 1045   
 
 1046  13796
         stack[sp].ll = loSt;
 1047  13796
         stack[sp].hh = hiSt;
 1048  13796
         stack[sp].dd = dSt;
 1049  13796
         sp++;
 1050   
 
 1051  13796
         while (sp > 0) {
 1052  113645
             if (sp >= QSORT_STACK_SIZE) {
 1053  0
                 panic();
 1054   
             }
 1055   
 
 1056  113645
             sp--;
 1057  113645
             lo = stack[sp].ll;
 1058  113645
             hi = stack[sp].hh;
 1059  113645
             d = stack[sp].dd;
 1060   
 
 1061  113645
             if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH) {
 1062  16884
                 simpleSort(lo, hi, d);
 1063  16884
                 if (workDone > workLimit && firstAttempt) {
 1064  0
                     return;
 1065   
                 }
 1066  16884
                 continue;
 1067   
             }
 1068   
 
 1069  96761
             med = med3(block[zptr[lo] + d + 1],
 1070   
                        block[zptr[hi            ] + d  + 1],
 1071   
                        block[zptr[(lo + hi) >> 1] + d + 1]);
 1072   
 
 1073  96761
             unLo = ltLo = lo;
 1074  96761
             unHi = gtHi = hi;
 1075   
 
 1076  96761
             while (true) {
 1077  113092
                 while (true) {
 1078  12361999
                     if (unLo > unHi) {
 1079  95989
                         break;
 1080   
                     }
 1081  12266010
                     n = ((int) block[zptr[unLo] + d + 1]) - med;
 1082  12266010
                     if (n == 0) {
 1083  12159609
                         int temp = 0;
 1084  12159609
                         temp = zptr[unLo];
 1085  12159609
                         zptr[unLo] = zptr[ltLo];
 1086  12159609
                         zptr[ltLo] = temp;
 1087  12159609
                         ltLo++;
 1088  12159609
                         unLo++;
 1089  12159609
                         continue;
 1090   
                     };
 1091  106401
                     if (n >  0) {
 1092  17103
                         break;
 1093   
                     }
 1094  89298
                     unLo++;
 1095   
                 }
 1096  113092
                 while (true) {
 1097  276807
                     if (unLo > unHi) {
 1098  96761
                         break;
 1099   
                     }
 1100  180046
                     n = ((int) block[zptr[unHi] + d + 1]) - med;
 1101  180046
                     if (n == 0) {
 1102  83786
                         int temp = 0;
 1103  83786
                         temp = zptr[unHi];
 1104  83786
                         zptr[unHi] = zptr[gtHi];
 1105  83786
                         zptr[gtHi] = temp;
 1106  83786
                         gtHi--;
 1107  83786
                         unHi--;
 1108  83786
                         continue;
 1109   
                     };
 1110  96260
                     if (n <  0) {
 1111  16331
                         break;
 1112   
                     }
 1113  79929
                     unHi--;
 1114   
                 }
 1115  113092
                 if (unLo > unHi) {
 1116  96761
                     break;
 1117   
                 }
 1118  16331
                 int temp = 0;
 1119  16331
                 temp = zptr[unLo];
 1120  16331
                 zptr[unLo] = zptr[unHi];
 1121  16331
                 zptr[unHi] = temp;
 1122  16331
                 unLo++;
 1123  16331
                 unHi--;
 1124   
             }
 1125   
 
 1126  96761
             if (gtHi < ltLo) {
 1127  95217
                 stack[sp].ll = lo;
 1128  95217
                 stack[sp].hh = hi;
 1129  95217
                 stack[sp].dd = d + 1;
 1130  95217
                 sp++;
 1131  95217
                 continue;
 1132   
             }
 1133   
 
 1134  1544
             n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo) : (unLo - ltLo);
 1135  1544
             vswap(lo, unLo - n, n);
 1136  1544
             m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi) : (gtHi - unHi);
 1137  1544
             vswap(unLo, hi - m + 1, m);
 1138   
 
 1139  1544
             n = lo + unLo - ltLo - 1;
 1140  1544
             m = hi - (gtHi - unHi) + 1;
 1141   
 
 1142  1544
             stack[sp].ll = lo;
 1143  1544
             stack[sp].hh = n;
 1144  1544
             stack[sp].dd = d;
 1145  1544
             sp++;
 1146   
 
 1147  1544
             stack[sp].ll = n + 1;
 1148  1544
             stack[sp].hh = m - 1;
 1149  1544
             stack[sp].dd = d + 1;
 1150  1544
             sp++;
 1151   
 
 1152  1544
             stack[sp].ll = m;
 1153  1544
             stack[sp].hh = hi;
 1154  1544
             stack[sp].dd = d;
 1155  1544
             sp++;
 1156   
         }
 1157   
     }
 1158   
 
 1159  8
     private void mainSort() {
 1160  8
         int i, j, ss, sb;
 1161  8
         int[] runningOrder = new int[256];
 1162  8
         int[] copy = new int[256];
 1163  8
         boolean[] bigDone = new boolean[256];
 1164  8
         int c1, c2;
 1165  8
         int numQSorted;
 1166   
 
 1167   
         /*
 1168   
           In the various block-sized structures, live data runs
 1169   
           from 0 to last+NUM_OVERSHOOT_BYTES inclusive.  First,
 1170   
           set up the overshoot area for block.
 1171   
         */
 1172   
 
 1173   
         //   if (verbosity >= 4) fprintf ( stderr, "   sort initialise ...\n" );
 1174  8
         for (i = 0; i < NUM_OVERSHOOT_BYTES; i++) {
 1175  160
             block[last + i + 2] = block[(i % (last + 1)) + 1];
 1176   
         }
 1177  8
         for (i = 0; i <= last + NUM_OVERSHOOT_BYTES; i++) {
 1178  2792589
             quadrant[i] = 0;
 1179   
         }
 1180   
 
 1181  8
         block[0] = (char) (block[last + 1]);
 1182   
 
 1183  8
         if (last < 4000) {
 1184   
             /*
 1185   
               Use simpleSort(), since the full sorting mechanism
 1186   
               has quite a large constant overhead.
 1187   
             */
 1188  1
             for (i = 0; i <= last; i++) {
 1189  2932
                 zptr[i] = i;
 1190   
             }
 1191  1
             firstAttempt = false;
 1192  1
             workDone = workLimit = 0;
 1193  1
             simpleSort(0, last, 0);
 1194   
         } else {
 1195  7
             numQSorted = 0;
 1196  7
             for (i = 0; i <= 255; i++) {
 1197  1792
                 bigDone[i] = false;
 1198   
             }
 1199   
 
 1200  7
             for (i = 0; i <= 65536; i++) {
 1201  458759
                 ftab[i] = 0;
 1202   
             }
 1203   
 
 1204  7
             c1 = block[0];
 1205  7
             for (i = 0; i <= last; i++) {
 1206  2789497
                 c2 = block[i + 1];
 1207  2789497
                 ftab[(c1 << 8) + c2]++;
 1208  2789497
                 c1 = c2;
 1209   
             }
 1210   
 
 1211  7
             for (i = 1; i <= 65536; i++) {
 1212  458752
                 ftab[i] += ftab[i - 1];
 1213   
             }
 1214   
 
 1215  7
             c1 = block[1];
 1216  7
             for (i = 0; i < last; i++) {
 1217  2789490
                 c2 = block[i + 2];
 1218  2789490
                 j = (c1 << 8) + c2;
 1219  2789490
                 c1 = c2;
 1220  2789490
                 ftab[j]--;
 1221  2789490
                 zptr[ftab[j]] = i;
 1222   
             }
 1223   
 
 1224  7
             j = ((block[last + 1]) << 8) + (block[1]);
 1225  7
             ftab[j]--;
 1226  7
             zptr[ftab[j]] = last;
 1227   
 
 1228   
             /*
 1229   
               Now ftab contains the first loc of every small bucket.
 1230   
               Calculate the running order, from smallest to largest
 1231   
               big bucket.
 1232   
             */
 1233   
 
 1234  7
             for (i = 0; i <= 255; i++) {
 1235  1792
                 runningOrder[i] = i;
 1236   
             }
 1237   
 
 1238   
             {
 1239  7
                 int vv;
 1240  7
                 int h = 1;
 1241  7
                 do {
 1242  35
                     h = 3 * h + 1;
 1243   
                 }
 1244  35
                 while (h <= 256);
 1245  7
                 do {
 1246  35
                     h = h / 3;
 1247  35
                     for (i = h; i <= 255; i++) {
 1248  7707
                         vv = runningOrder[i];
 1249  7707
                         j = i;
 1250  7707
                         while ((ftab[((runningOrder[j - h]) + 1) << 8]
 1251   
                                 - ftab[(runningOrder[j - h]) << 8]) >
 1252   
                                (ftab[((vv) + 1) << 8] - ftab[(vv) << 8])) {
 1253  10114
                             runningOrder[j] = runningOrder[j - h];
 1254  10114
                             j = j - h;
 1255  10114
                             if (j <= (h - 1)) {
 1256  1043
                                 break;
 1257   
                             }
 1258   
                         }
 1259  7707
                         runningOrder[j] = vv;
 1260   
                     }
 1261  35
                 } while (h != 1);
 1262   
             }
 1263   
 
 1264   
             /*
 1265   
               The main sorting loop.
 1266   
             */
 1267  7
             for (i = 0; i <= 255; i++) {
 1268   
 
 1269   
                 /*
 1270   
                   Process big buckets, starting with the least full.
 1271   
                 */
 1272  1792
                 ss = runningOrder[i];
 1273   
 
 1274   
                 /*
 1275   
                   Complete the big bucket [ss] by quicksorting
 1276   
                   any unsorted small buckets [ss, j].  Hopefully
 1277   
                   previous pointer-scanning phases have already
 1278   
                   completed many of the small buckets [ss, j], so
 1279   
                   we don't have to sort them at all.
 1280   
                 */
 1281  1792
                 for (j = 0; j <= 255; j++) {
 1282  458752
                     sb = (ss << 8) + j;
 1283  458752
                     if (!((ftab[sb] & SETMASK) == SETMASK)) {
 1284  230272
                         int lo = ftab[sb] & CLEARMASK;
 1285  230272
                         int hi = (ftab[sb + 1] & CLEARMASK) - 1;
 1286  230272
                         if (hi > lo) {
 1287  13796
                             qSort3(lo, hi, 2);
 1288  13796
                             numQSorted += (hi - lo + 1);
 1289  13796
                             if (workDone > workLimit && firstAttempt) {
 1290  0
                                 return;
 1291   
                             }
 1292   
                         }
 1293  230272
                         ftab[sb] |= SETMASK;
 1294   
                     }
 1295   
                 }
 1296   
 
 1297   
                 /*
 1298   
                   The ss big bucket is now done.  Record this fact,
 1299   
                   and update the quadrant descriptors.  Remember to
 1300   
                   update quadrants in the overshoot area too, if
 1301   
                   necessary.  The "if (i < 255)" test merely skips
 1302   
                   this updating for the last bucket processed, since
 1303   
                   updating for the last bucket is pointless.
 1304   
                 */
 1305  1792
                 bigDone[ss] = true;
 1306   
 
 1307  1792
                 if (i < 255) {
 1308  1785
                     int bbStart  = ftab[ss << 8] & CLEARMASK;
 1309  1785
                     int bbSize   = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart;
 1310  1785
                     int shifts   = 0;
 1311   
 
 1312  1785
                     while ((bbSize >> shifts) > 65534) {
 1313  0
                         shifts++;
 1314   
                     }
 1315   
 
 1316  1785
                     for (j = 0; j < bbSize; j++) {
 1317  2726990
                         int a2update = zptr[bbStart + j];
 1318  2726990
                         int qVal = (j >> shifts);
 1319  2726990
                         quadrant[a2update] = qVal;
 1320  2726990
                         if (a2update < NUM_OVERSHOOT_BYTES) {
 1321  121
                             quadrant[a2update + last + 1] = qVal;
 1322   
                         }
 1323   
                     }
 1324   
 
 1325  1785
                     if (!(((bbSize - 1) >> shifts) <= 65535)) {
 1326  0
                         panic();
 1327   
                     }
 1328   
                 }
 1329   
 
 1330   
                 /*
 1331   
                   Now scan this big bucket so as to synthesise the
 1332   
                   sorted order for small buckets [t, ss] for all t != ss.
 1333   
                 */
 1334  1792
                 for (j = 0; j <= 255; j++) {
 1335  458752
                     copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
 1336   
                 }
 1337   
 
 1338  1792
                 for (j = ftab[ss << 8] & CLEARMASK;
 1339  2791289
                      j < (ftab[(ss + 1) << 8] & CLEARMASK); j++) {
 1340  2789497
                     c1 = block[zptr[j]];
 1341  2789497
                     if (!bigDone[c1]) {
 1342  1377832
                         zptr[copy[c1]] = zptr[j] == 0 ? last : zptr[j] - 1;
 1343  1377832
                         copy[c1]++;
 1344   
                     }
 1345   
                 }
 1346   
 
 1347  1792
                 for (j = 0; j <= 255; j++) {
 1348  458752
                     ftab[(j << 8) + ss] |= SETMASK;
 1349   
                 }
 1350   
             }
 1351   
         }
 1352   
     }
 1353   
 
 1354  0
     private void randomiseBlock() {
 1355  0
         int i;
 1356  0
         int rNToGo = 0;
 1357  0
         int rTPos  = 0;
 1358  0
         for (i = 0; i < 256; i++) {
 1359  0
             inUse[i] = false;
 1360   
         }
 1361   
 
 1362  0
         for (i = 0; i <= last; i++) {
 1363  0
             if (rNToGo == 0) {
 1364  0
                 rNToGo = (char) rNums[rTPos];
 1365  0
                 rTPos++;
 1366  0
                 if (rTPos == 512) {
 1367  0
                     rTPos = 0;
 1368   
                 }
 1369   
             }
 1370  0
             rNToGo--;
 1371  0
             block[i + 1] ^= ((rNToGo == 1) ? 1 : 0);
 1372   
             // handle 16 bit signed numbers
 1373  0
             block[i + 1] &= 0xFF;
 1374   
 
 1375  0
             inUse[block[i + 1]] = true;
 1376   
         }
 1377   
     }
 1378   
 
 1379  8
     private void doReversibleTransformation() {
 1380  8
         int i;
 1381   
 
 1382  8
         workLimit = workFactor * last;
 1383  8
         workDone = 0;
 1384  8
         blockRandomised = false;
 1385  8
         firstAttempt = true;
 1386   
 
 1387  8
         mainSort();
 1388   
 
 1389  8
         if (workDone > workLimit && firstAttempt) {
 1390  0
             randomiseBlock();
 1391  0
             workLimit = workDone = 0;
 1392  0
             blockRandomised = true;
 1393  0
             firstAttempt = false;
 1394  0
             mainSort();
 1395   
         }
 1396   
 
 1397  8
         origPtr = -1;
 1398  1134685
         for (i = 0; i <= last; i++) {
 1399  1134685
             if (zptr[i] == 0) {
 1400  8
                 origPtr = i;
 1401  8
                 break;
 1402   
             }
 1403   
         };
 1404   
 
 1405  8
         if (origPtr == -1) {
 1406  0
             panic();
 1407   
         }
 1408   
     }
 1409   
 
 1410  8480512
     private boolean fullGtU(int i1, int i2) {
 1411  8480512
         int k;
 1412  8480512
         char c1, c2;
 1413  8480512
         int s1, s2;
 1414   
 
 1415  8480512
         c1 = block[i1 + 1];
 1416  8480512
         c2 = block[i2 + 1];
 1417  8480512
         if (c1 != c2) {
 1418  35714
             return (c1 > c2);
 1419   
         }
 1420  8444798
         i1++;
 1421  8444798
         i2++;
 1422   
 
 1423  8444798
         c1 = block[i1 + 1];
 1424  8444798
         c2 = block[i2 + 1];
 1425  8444798
         if (c1 != c2) {
 1426  17023
             return (c1 > c2);
 1427   
         }
 1428  8427775
         i1++;
 1429  8427775
         i2++;
 1430   
 
 1431  8427775
         c1 = block[i1 + 1];
 1432  8427775
         c2 = block[i2 + 1];
 1433  8427775
         if (c1 != c2) {
 1434  7789
             return (c1 > c2);
 1435   
         }
 1436  8419986
         i1++;
 1437  8419986
         i2++;
 1438   
 
 1439  8419986
         c1 = block[i1 + 1];
 1440  8419986
         c2 = block[i2 + 1];
 1441  8419986
         if (c1 != c2) {
 1442  5841
             return (c1 > c2);
 1443   
         }
 1444  8414145
         i1++;
 1445  8414145
         i2++;
 1446   
 
 1447  8414145
         c1 = block[i1 + 1];
 1448  8414145
         c2 = block[i2 + 1];
 1449  8414145
         if (c1 != c2) {
 1450  4857
             return (c1 > c2);
 1451   
         }
 1452  8409288
         i1++;
 1453  8409288
         i2++;
 1454   
 
 1455  8409288
         c1 = block[i1 + 1];
 1456  8409288
         c2 = block[i2 + 1];
 1457  8409288
         if (c1 != c2) {
 1458  4332
             return (c1 > c2);
 1459   
         }
 1460  8404956
         i1++;
 1461  8404956
         i2++;
 1462   
 
 1463  8404956
         k = last + 1;
 1464   
 
 1465  8404956
         do {
 1466  44433992
             c1 = block[i1 + 1];
 1467  44433992
             c2 = block[i2 + 1];
 1468  44433992
             if (c1 != c2) {
 1469  23233
                 return (c1 > c2);
 1470   
             }
 1471  44410759
             s1 = quadrant[i1];
 1472  44410759
             s2 = quadrant[i2];
 1473  44410759
             if (s1 != s2) {
 1474  3794385
                 return (s1 > s2);
 1475   
             }
 1476  40616374
             i1++;
 1477  40616374
             i2++;
 1478   
 
 1479  40616374
             c1 = block[i1 + 1];
 1480  40616374
             c2 = block[i2 + 1];
 1481  40616374
             if (c1 != c2) {
 1482  16161
                 return (c1 > c2);
 1483   
             }
 1484  40600213
             s1 = quadrant[i1];
 1485  40600213
             s2 = quadrant[i2];
 1486  40600213
             if (s1 != s2) {
 1487  2082074
                 return (s1 > s2);
 1488   
             }
 1489  38518139
             i1++;
 1490  38518139
             i2++;
 1491   
 
 1492  38518139
             c1 = block[i1 + 1];
 1493  38518139
             c2 = block[i2 + 1];
 1494  38518139
             if (c1 != c2) {
 1495  13973
                 return (c1 > c2);
 1496   
             }
 1497  38504166
             s1 = quadrant[i1];
 1498  38504166
             s2 = quadrant[i2];
 1499  38504166
             if (s1 != s2) {
 1500  1380264
                 return (s1 > s2);
 1501   
             }
 1502  37123902
             i1++;
 1503  37123902
             i2++;
 1504   
 
 1505  37123902
             c1 = block[i1 + 1];
 1506  37123902
             c2 = block[i2 + 1];
 1507  37123902
             if (c1 != c2) {
 1508  16308
                 return (c1 > c2);
 1509   
             }
 1510  37107594
             s1 = quadrant[i1];
 1511  37107594
             s2 = quadrant[i2];
 1512  37107594
             if (s1 != s2) {
 1513  1078558
                 return (s1 > s2);
 1514   
             }
 1515  36029036
             i1++;
 1516  36029036
             i2++;
 1517   
 
 1518  36029036
             if (i1 > last) {
 1519  22
                 i1 -= last;
 1520  22
                 i1--;
 1521   
             };
 1522  36029036
             if (i2 > last) {
 1523  32
                 i2 -= last;
 1524  32
                 i2--;
 1525   
             };
 1526   
 
 1527  36029036
             k -= 4;
 1528  36029036
             workDone++;
 1529  36029036
         } while (k >= 0);
 1530   
 
 1531  0
         return false;
 1532   
     }
 1533   
 
 1534   
     /*
 1535   
       Knuth's increments seem to work better
 1536   
       than Incerpi-Sedgewick here.  Possibly
 1537   
       because the number of elems to sort is
 1538   
       usually small, typically <= 20.
 1539   
     */
 1540   
     private int[] incs = { 1, 4, 13, 40, 121, 364, 1093, 3280,
 1541   
                            9841, 29524, 88573, 265720,
 1542   
                            797161, 2391484 };
 1543   
 
 1544  5
     private void allocateCompressStructures () {
 1545  5
         int n = baseBlockSize * blockSize100k;
 1546  5
         block = new char[(n + 1 + NUM_OVERSHOOT_BYTES)];
 1547  5
         quadrant = new int[(n + NUM_OVERSHOOT_BYTES)];
 1548  5
         zptr = new int[n];
 1549  5
         ftab = new int[65537];
 1550   
 
 1551  5
         if (block == null || quadrant == null || zptr == null
 1552   
             || ftab == null) {
 1553   
             //int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
 1554   
             //compressOutOfMemory ( totalDraw, n );
 1555   
         }
 1556   
 
 1557   
         /*
 1558   
           The back end needs a place to store the MTF values
 1559   
           whilst it calculates the coding tables.  We could
 1560   
           put them in the zptr array.  However, these values
 1561   
           will fit in a short, so we overlay szptr at the
 1562   
           start of zptr, in the hope of reducing the number
 1563   
           of cache misses induced by the multiple traversals
 1564   
           of the MTF values when calculating coding tables.
 1565   
           Seems to improve compression speed by about 1%.
 1566   
         */
 1567   
         //    szptr = zptr;
 1568   
 
 1569   
 
 1570  5
         szptr = new short[2 * n];
 1571   
     }
 1572   
 
 1573  8
     private void generateMTFValues() {
 1574  8
         char[] yy = new char[256];
 1575  8
         int  i, j;
 1576  8
         char tmp;
 1577  8
         char tmp2;
 1578  8
         int zPend;
 1579  8
         int wr;
 1580  8
         int EOB;
 1581   
 
 1582  8
         makeMaps();
 1583  8
         EOB = nInUse + 1;
 1584   
 
 1585  8
         for (i = 0; i <= EOB; i++) {
 1586  1863
             mtfFreq[i] = 0;
 1587   
         }
 1588   
 
 1589  8
         wr = 0;
 1590  8
         zPend = 0;
 1591  8
         for (i = 0; i < nInUse; i++) {
 1592  1847
             yy[i] = (char) i;
 1593   
         }
 1594   
 
 1595   
 
 1596  8
         for (i = 0; i <= last; i++) {
 1597  2792429
             char ll_i;
 1598   
 
 1599  2792429
             ll_i = unseqToSeq[block[zptr[i]]];
 1600   
 
 1601  2792429
             j = 0;
 1602  2792429
             tmp = yy[j];
 1603  2792429
             while (ll_i != tmp) {
 1604  5841073
                 j++;
 1605  5841073
                 tmp2 = tmp;
 1606  5841073
                 tmp = yy[j];
 1607  5841073
                 yy[j] = tmp2;
 1608   
             };
 1609  2792429
             yy[0] = tmp;
 1610   
 
 1611  2792429
             if (j == 0) {
 1612  2740072
                 zPend++;
 1613   
             } else {
 1614  52357
                 if (zPend > 0) {
 1615  29096
                     zPend--;
 1616  29096
                     while (true) {
 1617  149662
                         switch (zPend % 2) {
 1618   
                         case 0:
 1619  20461
                             szptr[wr] = (short) RUNA;
 1620  20461
                             wr++;
 1621  20461
                             mtfFreq[RUNA]++;
 1622  20461
                             break;
 1623   
                         case 1:
 1624  129201
                             szptr[wr] = (short) RUNB;
 1625  129201
                             wr++;
 1626  129201
                             mtfFreq[RUNB]++;
 1627  129201
                             break;
 1628   
                         };
 1629  149662
                         if (zPend < 2) {
 1630  29096
                             break;
 1631   
                         }
 1632  120566
                         zPend = (zPend - 2) / 2;
 1633   
                     };
 1634  29096
                     zPend = 0;
 1635   
                 }
 1636  52357
                 szptr[wr] = (short) (j + 1);
 1637  52357
                 wr++;
 1638  52357
                 mtfFreq[j + 1]++;
 1639   
             }
 1640   
         }
 1641   
 
 1642  8
         if (zPend > 0) {
 1643  5
             zPend--;
 1644  5
             while (true) {
 1645  25
                 switch (zPend % 2) {
 1646   
                 case 0:
 1647  3
                     szptr[wr] = (short) RUNA;
 1648  3
                     wr++;
 1649  3
                     mtfFreq[RUNA]++;
 1650  3
                     break;
 1651   
                 case 1:
 1652  22
                     szptr[wr] = (short) RUNB;
 1653  22
                     wr++;
 1654  22
                     mtfFreq[RUNB]++;
 1655  22
                     break;
 1656   
                 }
 1657  25
                 if (zPend < 2) {
 1658  5
                     break;
 1659   
                 }
 1660  20
                 zPend = (zPend - 2) / 2;
 1661   
             }
 1662   
         }
 1663   
 
 1664  8
         szptr[wr] = (short) EOB;
 1665  8
         wr++;
 1666  8
         mtfFreq[EOB]++;
 1667   
 
 1668  8
         nMTF = wr;
 1669   
     }
 1670   
 }
 1671   
 
 1672   
 
 1673