开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Internet/网络编程 > 网格计算 > 查看源码
CBZip2OutputStream.java
资源名称：hadoop-0.20.0.tar.gz　[点击查看]
上传用户：quxuerui
上传日期：2018-01-08
资源大小：41811k
文件大小：56k
源码类别：

网格计算

开发平台：

Java

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