OSDN Git Service

Add new source files
[armadillo/armadillo1.git] / src / jp / sfjp / armadillo / compression / lzhuf / LzhHuffmanDecoder.java
1 package jp.sfjp.armadillo.compression.lzhuf;
2
3 import java.io.*;
4 import jp.sfjp.armadillo.io.*;
5
6 /**
7  * Huffman decoder for LH4, LH5, LH6, LH7.
8  */
9 public final class LzhHuffmanDecoder implements LzssDecoderReadable {
10
11     /** Work table bit length (16 bits and a guard) */
12     private static final int WORK_TABLE_BITLENGTH = 16 + 1;
13
14     private BitInputStream bin;
15     private int blockSize;
16     private int symbolMaxBitLength;
17     private short[] symbolLengthTable;
18     private short[] symbolCodeTable;
19     private int offsetMaxBitLength;
20     private short[] offsetLengthTable;
21     private short[] offsetCodeTable;
22
23     public LzhHuffmanDecoder(InputStream in) {
24         this(in, -1);
25     }
26
27     /**
28      * @param in InputStream
29      * @param limit when positive value: bytes to decode
30      *              when negative value: infinite (until EOF)
31      */
32     public LzhHuffmanDecoder(final InputStream in, final long limit) {
33         this.bin = (limit < 0) ? new BitInputStream(in) : new BitInputStream(new InputStream() {
34             private long remaining = limit;
35
36             @Override
37             public int read() throws IOException {
38                 if (remaining <= 0)
39                     return -1;
40                 final int read = in.read();
41                 if (read != -1)
42                     --remaining;
43                 return read;
44             }
45
46         });
47         this.blockSize = 0;
48     }
49
50     @Override
51     public int read() throws IOException {
52         try {
53             assert blockSize >= 0;
54             if (blockSize == 0) {
55                 if (bin.prefetch() == -1)
56                     return -1;
57                 final int n = bin.readBits(16);
58                 if (n == -1)
59                     return -1;
60                 this.blockSize = n;
61                 assert blockSize > 0 : "block size = " + blockSize;
62                 createSymbolTables();
63                 createOffsetTables();
64             }
65             --blockSize;
66             final int b = bin.prefetchBits(symbolMaxBitLength);
67             assert b != -1;
68             final int code = symbolCodeTable[b];
69             bin.readBits(symbolLengthTable[code]);
70             assert code >= 0 && code < 511;
71             return code;
72         }
73         catch (final RuntimeException ex) {
74             throw new LzhufException("decode error", ex);
75         }
76     }
77
78     @Override
79     public int readOffset() throws IOException {
80         try {
81             final int b = bin.prefetchBits(offsetMaxBitLength);
82             assert b != -1;
83             final int code = offsetCodeTable[b];
84             final int codeLength = offsetLengthTable[code];
85             if (codeLength > 0)
86                 bin.readBits(codeLength);
87             assert code >= 0 && codeLength >= 0;
88             int offset;
89             if (code > 1)
90                 offset = (1 << (code - 1)) | bin.readBits(code - 1);
91             else
92                 offset = code;
93             assert offset >= 0;
94             return offset;
95         }
96         catch (final RuntimeException ex) {
97             throw new LzhufException("decode error", ex);
98         }
99     }
100
101     private void createSymbolTables() throws IOException {
102         // initialize symbolMaxBitLength, symbolLengthTable and symbolCodeTable
103         final short[] lengthList = readCodeLengthList(5, 3);
104         final int blength = getMaxBitSize(lengthList);
105         final short[] table = createCodeTable(lengthList, blength);
106         final int n = bin.readBits(9);
107         if (n < 1)
108             throw new LzhufException("invalid compressed data: number of code lengths=" + n);
109         final short[] codeLengthList = new short[n];
110         for (int i = 0; i < codeLengthList.length;) {
111             final int code = bin.prefetchBits(blength);
112             if (code == -1)
113                 throw new LzhufException("EOF appeared while reading symbol length list");
114             final int length = table[code];
115             final int bitLength = lengthList[length];
116             bin.readBits(bitLength);
117             switch (length) {
118                 case 0:
119                     ++i;
120                     break;
121                 case 1:
122                     i += bin.readBits(4) + 3;
123                     break;
124                 case 2:
125                     i += bin.readBits(9) + 20;
126                     break;
127                 default:
128                     codeLengthList[i++] = (short)(length - 2);
129             }
130         }
131         final int maxBitLength = getMaxBitSize(codeLengthList);
132         this.symbolMaxBitLength = maxBitLength;
133         this.symbolLengthTable = codeLengthList;
134         this.symbolCodeTable = createCodeTable(codeLengthList, maxBitLength);
135     }
136
137     private void createOffsetTables() throws IOException {
138         // initialize offsetMaxBitLength, offsetLengthTable and offsetCodeTable
139         short[] codeLengthList = readCodeLengthList(4, -1);
140         if (codeLengthList.length == 0) {
141             final int offset = bin.readBits(4);
142             codeLengthList = new short[offset + 1];
143             final short[] codeTable = new short[]{(short)offset, (short)offset};
144             this.offsetMaxBitLength = 1;
145             this.offsetLengthTable = codeLengthList;
146             this.offsetCodeTable = codeTable;
147         }
148         else {
149             final int maxBitLength = getMaxBitSize(codeLengthList);
150             this.offsetMaxBitLength = maxBitLength;
151             this.offsetLengthTable = codeLengthList;
152             this.offsetCodeTable = createCodeTable(codeLengthList, maxBitLength);
153         }
154     }
155
156     private short[] readCodeLengthList(int nBits, int special) throws IOException {
157         final int n = bin.readBits(nBits);
158         final short[] list = new short[n];
159         for (int i = 0; i < n; i++) {
160             if (i == special)
161                 i += bin.readBits(2);
162             int length = bin.readBits(3);
163             if (length == 7)
164                 while (bin.readBit() == 1)
165                     ++length;
166             list[i] = (short)length;
167         }
168         return list;
169     }
170
171     private static int getMaxBitSize(short[] bitLengthList) {
172         int max = 0;
173         for (int i = 0; i < bitLengthList.length; i++)
174             if (bitLengthList[i] > max)
175                 max = bitLengthList[i];
176         return max;
177     }
178
179     private static short[] createCodeTable(short[] lengthList, int maxBitLength) {
180         final int[] codeList = createCodeList(lengthList);
181         final int tableSize = (1 << maxBitLength);
182         final short[] table = new short[tableSize];
183         for (int i = 0; i < lengthList.length; i++)
184             if (lengthList[i] > 0) {
185                 final int rangeBits = maxBitLength - lengthList[i];
186                 final int start = codeList[i] << rangeBits;
187                 final int next = start + (1 << rangeBits);
188                 for (int index = start; index < next; index++)
189                     table[index] = (short)i;
190             }
191         return table;
192     }
193
194     private static int[] createCodeList(short[] codeLengthList) {
195         assert codeLengthList.length > 0;
196         if (codeLengthList.length == 1)
197             return new int[1];
198         final int[] counts = new int[WORK_TABLE_BITLENGTH];
199         for (int i = 0; i < codeLengthList.length; i++)
200             ++counts[codeLengthList[i]];
201         final int[] baseCodes = new int[WORK_TABLE_BITLENGTH];
202         // i = bit length - 1
203         for (int i = 0; i < WORK_TABLE_BITLENGTH - 1; i++)
204             baseCodes[i + 1] = baseCodes[i] + counts[i + 1] << 1;
205         final int[] codeList = new int[codeLengthList.length];
206         for (int i = 0; i < codeList.length; i++) {
207             final int codeLength = codeLengthList[i];
208             if (codeLength > 0)
209                 codeList[i] = baseCodes[codeLength - 1]++;
210         }
211         return codeList;
212     }
213
214     @Override
215     public void close() throws IOException {
216         try {
217             bin.close();
218         }
219         finally {
220             bin = null;
221             symbolLengthTable = null;
222             symbolCodeTable = null;
223             offsetLengthTable = null;
224             offsetCodeTable = null;
225         }
226     }
227
228 }