InflaterHuffmanTree.java 6.62 KB
Newer Older
Tom Tromey committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
/* InflaterHuffmanTree.java --
   Copyright (C) 2001, 2004  Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */

package java.util.zip;

class InflaterHuffmanTree
{
  private static final int MAX_BITLEN = 15;
43

Tom Tromey committed
44 45 46 47 48 49
  private short[] tree;

  static InflaterHuffmanTree defLitLenTree, defDistTree;

  static
  {
50
    try
Tom Tromey committed
51
      {
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
        byte[] codeLengths = new byte[288];
        int i = 0;
        while (i < 144)
          codeLengths[i++] = 8;
        while (i < 256)
          codeLengths[i++] = 9;
        while (i < 280)
          codeLengths[i++] = 7;
        while (i < 288)
          codeLengths[i++] = 8;
        defLitLenTree = new InflaterHuffmanTree(codeLengths);

        codeLengths = new byte[32];
        i = 0;
        while (i < 32)
          codeLengths[i++] = 5;
        defDistTree = new InflaterHuffmanTree(codeLengths);
      }
Tom Tromey committed
70 71
    catch (DataFormatException ex)
      {
72 73
        throw new InternalError
          ("InflaterHuffmanTree: static tree length illegal");
Tom Tromey committed
74 75 76 77 78 79 80 81 82 83 84 85
      }
  }

  /**
   * Constructs a Huffman tree from the array of code lengths.
   *
   * @param codeLengths the array of code lengths
   */
  InflaterHuffmanTree(byte[] codeLengths) throws DataFormatException
  {
    buildTree(codeLengths);
  }
86

Tom Tromey committed
87 88 89 90 91 92
  private void buildTree(byte[] codeLengths) throws DataFormatException
  {
    int[] blCount = new int[MAX_BITLEN+1];
    int[] nextCode = new int[MAX_BITLEN+1];
    for (int i = 0; i < codeLengths.length; i++)
      {
93 94 95
        int bits = codeLengths[i];
        if (bits > 0)
          blCount[bits]++;
Tom Tromey committed
96 97
      }

98
    int max = 0;
Tom Tromey committed
99 100 101 102
    int code = 0;
    int treeSize = 512;
    for (int bits = 1; bits <= MAX_BITLEN; bits++)
      {
103
        nextCode[bits] = code;
104 105
        if (blCount[bits] > 0)
          max = bits;
106 107 108 109 110 111 112 113
        code += blCount[bits] << (16 - bits);
        if (bits >= 10)
          {
            /* We need an extra table for bit lengths >= 10. */
            int start = nextCode[bits] & 0x1ff80;
            int end   = code & 0x1ff80;
            treeSize += (end - start) >> (16 - bits);
          }
Tom Tromey committed
114
      }
115 116
    if (code != 65536 && max > 1)
      throw new DataFormatException("incomplete dynamic bit lengths tree");
Tom Tromey committed
117 118 119 120 121 122 123 124

    /* Now create and fill the extra tables from longest to shortest
     * bit len.  This way the sub trees will be aligned.
     */
    tree = new short[treeSize];
    int treePtr = 512;
    for (int bits = MAX_BITLEN; bits >= 10; bits--)
      {
125 126 127 128 129 130 131 132 133
        int end   = code & 0x1ff80;
        code -= blCount[bits] << (16 - bits);
        int start = code & 0x1ff80;
        for (int i = start; i < end; i += 1 << 7)
          {
            tree[DeflaterHuffman.bitReverse(i)]
              = (short) ((-treePtr << 4) | bits);
            treePtr += 1 << (bits-9);
          }
Tom Tromey committed
134
      }
135

Tom Tromey committed
136 137
    for (int i = 0; i < codeLengths.length; i++)
      {
138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
        int bits = codeLengths[i];
        if (bits == 0)
          continue;
        code = nextCode[bits];
        int revcode = DeflaterHuffman.bitReverse(code);
        if (bits <= 9)
          {
            do
              {
                tree[revcode] = (short) ((i << 4) | bits);
                revcode += 1 << bits;
              }
            while (revcode < 512);
          }
        else
          {
            int subTree = tree[revcode & 511];
            int treeLen = 1 << (subTree & 15);
            subTree = -(subTree >> 4);
            do
              {
                tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
                revcode += 1 << bits;
              }
            while (revcode < treeLen);
          }
        nextCode[bits] = code + (1 << (16 - bits));
Tom Tromey committed
165 166 167 168 169 170 171 172 173 174 175 176 177 178
      }
  }

  /**
   * Reads the next symbol from input.  The symbol is encoded using the
   * huffman tree.
   * @param input the input source.
   * @return the next symbol, or -1 if not enough input is available.
   */
  int getSymbol(StreamManipulator input) throws DataFormatException
  {
    int lookahead, symbol;
    if ((lookahead = input.peekBits(9)) >= 0)
      {
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
        if ((symbol = tree[lookahead]) >= 0)
          {
            input.dropBits(symbol & 15);
            return symbol >> 4;
          }
        int subtree = -(symbol >> 4);
        int bitlen = symbol & 15;
        if ((lookahead = input.peekBits(bitlen)) >= 0)
          {
            symbol = tree[subtree | (lookahead >> 9)];
            input.dropBits(symbol & 15);
            return symbol >> 4;
          }
        else
          {
            int bits = input.getAvailableBits();
            lookahead = input.peekBits(bits);
            symbol = tree[subtree | (lookahead >> 9)];
            if ((symbol & 15) <= bits)
              {
                input.dropBits(symbol & 15);
                return symbol >> 4;
              }
            else
              return -1;
          }
Tom Tromey committed
205 206 207
      }
    else
      {
208 209 210 211 212 213 214 215 216 217
        int bits = input.getAvailableBits();
        lookahead = input.peekBits(bits);
        symbol = tree[lookahead];
        if (symbol >= 0 && (symbol & 15) <= bits)
          {
            input.dropBits(symbol & 15);
            return symbol >> 4;
          }
        else
          return -1;
Tom Tromey committed
218 219 220
      }
  }
}