← Back to branch summary

~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

« back to all changes in this revision

Viewing changes to external/ikvm/openjdk/java/util/zip/InflaterHuffmanTree.java

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2013-05-12 09:46:03 UTC
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130512094603-mad323bzcxvmcam0
Tags: upstream-4.0.5+dfsg
Import upstream version 4.0.5+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
external/ikvm/openjdk/java/util/zip/InflaterHuffmanTree.java
 
1
/* InflaterHuffmanTree.java --
 
2
   Copyright (C) 2001, 2004  Free Software Foundation, Inc.
 
3
 
 
4
This file is part of GNU Classpath.
 
5
 
 
6
GNU Classpath is free software; you can redistribute it and/or modify
 
7
it under the terms of the GNU General Public License as published by
 
8
the Free Software Foundation; either version 2, or (at your option)
 
9
any later version.
 
10
 
 
11
GNU Classpath is distributed in the hope that it will be useful, but
 
12
WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
14
General Public License for more details.
 
15
 
 
16
You should have received a copy of the GNU General Public License
 
17
along with GNU Classpath; see the file COPYING.  If not, write to the
 
18
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 
19
02110-1301 USA.
 
20
 
 
21
Linking this library statically or dynamically with other modules is
 
22
making a combined work based on this library.  Thus, the terms and
 
23
conditions of the GNU General Public License cover the whole
 
24
combination.
 
25
 
 
26
As a special exception, the copyright holders of this library give you
 
27
permission to link this library with independent modules to produce an
 
28
executable, regardless of the license terms of these independent
 
29
modules, and to copy and distribute the resulting executable under
 
30
terms of your choice, provided that you also meet, for each linked
 
31
independent module, the terms and conditions of the license of that
 
32
module.  An independent module is a module which is not derived from
 
33
or based on this library.  If you modify this library, you may extend
 
34
this exception to your version of the library, but you are not
 
35
obligated to do so.  If you do not wish to do so, delete this
 
36
exception statement from your version. */
 
37
 
 
38
package java.util.zip;
 
39
 
 
40
class InflaterHuffmanTree
 
41
{
 
42
  private static final int MAX_BITLEN = 15;
 
43
 
 
44
  private short[] tree;
 
45
 
 
46
  static InflaterHuffmanTree defLitLenTree, defDistTree;
 
47
 
 
48
  static
 
49
  {
 
50
    try
 
51
      {
 
52
        byte[] codeLengths = new byte[288];
 
53
        int i = 0;
 
54
        while (i < 144)
 
55
          codeLengths[i++] = 8;
 
56
        while (i < 256)
 
57
          codeLengths[i++] = 9;
 
58
        while (i < 280)
 
59
          codeLengths[i++] = 7;
 
60
        while (i < 288)
 
61
          codeLengths[i++] = 8;
 
62
        defLitLenTree = new InflaterHuffmanTree(codeLengths);
 
63
 
 
64
        codeLengths = new byte[32];
 
65
        i = 0;
 
66
        while (i < 32)
 
67
          codeLengths[i++] = 5;
 
68
        defDistTree = new InflaterHuffmanTree(codeLengths);
 
69
      }
 
70
    catch (DataFormatException ex)
 
71
      {
 
72
        throw new InternalError
 
73
          ("InflaterHuffmanTree: static tree length illegal");
 
74
      }
 
75
  }
 
76
 
 
77
  /**
 
78
   * Constructs a Huffman tree from the array of code lengths.
 
79
   *
 
80
   * @param codeLengths the array of code lengths
 
81
   */
 
82
  InflaterHuffmanTree(byte[] codeLengths) throws DataFormatException
 
83
  {
 
84
    buildTree(codeLengths);
 
85
  }
 
86
 
 
87
  private void buildTree(byte[] codeLengths) throws DataFormatException
 
88
  {
 
89
    int[] blCount = new int[MAX_BITLEN+1];
 
90
    int[] nextCode = new int[MAX_BITLEN+1];
 
91
    for (int i = 0; i < codeLengths.length; i++)
 
92
      {
 
93
        int bits = codeLengths[i];
 
94
        if (bits > 0)
 
95
          blCount[bits]++;
 
96
      }
 
97
 
 
98
    int max = 0;
 
99
    int code = 0;
 
100
    int treeSize = 512;
 
101
    for (int bits = 1; bits <= MAX_BITLEN; bits++)
 
102
      {
 
103
        nextCode[bits] = code;
 
104
        if (blCount[bits] > 0)
 
105
          max = bits;
 
106
        code += blCount[bits] << (16 - bits);
 
107
        if (bits >= 10)
 
108
          {
 
109
            /* We need an extra table for bit lengths >= 10. */
 
110
            int start = nextCode[bits] & 0x1ff80;
 
111
            int end   = code & 0x1ff80;
 
112
            treeSize += (end - start) >> (16 - bits);
 
113
          }
 
114
      }
 
115
    if (code != 65536 && max > 1)
 
116
      throw new DataFormatException("incomplete dynamic bit lengths tree");
 
117
 
 
118
    /* Now create and fill the extra tables from longest to shortest
 
119
     * bit len.  This way the sub trees will be aligned.
 
120
     */
 
121
    tree = new short[treeSize];
 
122
    int treePtr = 512;
 
123
    for (int bits = MAX_BITLEN; bits >= 10; bits--)
 
124
      {
 
125
        int end   = code & 0x1ff80;
 
126
        code -= blCount[bits] << (16 - bits);
 
127
        int start = code & 0x1ff80;
 
128
        for (int i = start; i < end; i += 1 << 7)
 
129
          {
 
130
            tree[DeflaterHuffman.bitReverse(i)]
 
131
              = (short) ((-treePtr << 4) | bits);
 
132
            treePtr += 1 << (bits-9);
 
133
          }
 
134
      }
 
135
 
 
136
    for (int i = 0; i < codeLengths.length; i++)
 
137
      {
 
138
        int bits = codeLengths[i];
 
139
        if (bits == 0)
 
140
          continue;
 
141
        code = nextCode[bits];
 
142
        int revcode = DeflaterHuffman.bitReverse(code);
 
143
        if (bits <= 9)
 
144
          {
 
145
            do
 
146
              {
 
147
                tree[revcode] = (short) ((i << 4) | bits);
 
148
                revcode += 1 << bits;
 
149
              }
 
150
            while (revcode < 512);
 
151
          }
 
152
        else
 
153
          {
 
154
            int subTree = tree[revcode & 511];
 
155
            int treeLen = 1 << (subTree & 15);
 
156
            subTree = -(subTree >> 4);
 
157
            do
 
158
              {
 
159
                tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
 
160
                revcode += 1 << bits;
 
161
              }
 
162
            while (revcode < treeLen);
 
163
          }
 
164
        nextCode[bits] = code + (1 << (16 - bits));
 
165
      }
 
166
  }
 
167
 
 
168
  /**
 
169
   * Reads the next symbol from input.  The symbol is encoded using the
 
170
   * huffman tree.
 
171
   * @param input the input source.
 
172
   * @return the next symbol, or -1 if not enough input is available.
 
173
   */
 
174
  int getSymbol(StreamManipulator input) throws DataFormatException
 
175
  {
 
176
    int lookahead, symbol;
 
177
    if ((lookahead = input.peekBits(9)) >= 0)
 
178
      {
 
179
        if ((symbol = tree[lookahead]) >= 0)
 
180
          {
 
181
            input.dropBits(symbol & 15);
 
182
            return symbol >> 4;
 
183
          }
 
184
        int subtree = -(symbol >> 4);
 
185
        int bitlen = symbol & 15;
 
186
        if ((lookahead = input.peekBits(bitlen)) >= 0)
 
187
          {
 
188
            symbol = tree[subtree | (lookahead >> 9)];
 
189
            input.dropBits(symbol & 15);
 
190
            return symbol >> 4;
 
191
          }
 
192
        else
 
193
          {
 
194
            int bits = input.getAvailableBits();
 
195
            lookahead = input.peekBits(bits);
 
196
            symbol = tree[subtree | (lookahead >> 9)];
 
197
            if ((symbol & 15) <= bits)
 
198
              {
 
199
                input.dropBits(symbol & 15);
 
200
                return symbol >> 4;
 
201
              }
 
202
            else
 
203
              return -1;
 
204
          }
 
205
      }
 
206
    else
 
207
      {
 
208
        int bits = input.getAvailableBits();
 
209
        lookahead = input.peekBits(bits);
 
210
        symbol = tree[lookahead];
 
211
        if (symbol >= 0 && (symbol & 15) <= bits)
 
212
          {
 
213
            input.dropBits(symbol & 15);
 
214
            return symbol >> 4;
 
215
          }
 
216
        else
 
217
          return -1;
 
218
      }
 
219
  }
 
220
}