OSDN Git Service

Add new source files
[armadillo/armadillo1.git] / src / jp / sfjp / armadillo / compression / lzhuf / LzhHuffmanEncoder.java
1 package jp.sfjp.armadillo.compression.lzhuf;
2
3 import java.io.*;
4 import java.util.*;
5 import jp.sfjp.armadillo.archive.lzh.*;
6 import jp.sfjp.armadillo.io.*;
7
8 /**
9  * Huffman encoder for LH4, LH5, LH6, LH7.
10  */
11 public final class LzhHuffmanEncoder implements LzssEncoderWritable {
12
13     private static final int BUFFER_SIZE = 4096;
14
15     private final BitOutputStream out;
16     private final int threshold;
17     private int index;
18     private final int[] symbolBuffer;
19     private final int[] offsetBuffer;
20     private final int[] frequencyTable;
21
22     /*
23      * C: code table
24      * L: code length table
25      * T1: code huffman table
26      * T2: length huffman table of T1
27      * T3: huffman table bit length of offset
28      */
29     private int[] ct1, lt1, ct2, lt2, ct3, lt3;
30     private int t1size;
31
32     public LzhHuffmanEncoder(OutputStream out, int threshold) {
33         this.out = new BitOutputStream(new FilterOutputStream(out) {
34             @Override
35             public void close() throws IOException {
36                 //
37             }
38         });
39         this.threshold = threshold;
40         this.index = 0;
41         this.symbolBuffer = new int[BUFFER_SIZE];
42         this.offsetBuffer = new int[BUFFER_SIZE];
43         this.frequencyTable = new int[512];
44     }
45
46     @Override
47     public void write(int symbol) throws IOException {
48         ++frequencyTable[symbol];
49         symbolBuffer[index++] = symbol;
50         if (index >= BUFFER_SIZE)
51             encode();
52     }
53
54     @Override
55     public void writeMatched(int offset, int length) throws IOException {
56         assert length >= threshold;
57         final int symbol = length - threshold + 0x100;
58         ++frequencyTable[symbol];
59         symbolBuffer[index] = symbol;
60         offsetBuffer[index++] = offset - 1;
61         if (index >= BUFFER_SIZE)
62             encode();
63     }
64
65     @Override
66     public void flush() throws IOException {
67         encode();
68     }
69
70     private void encode() throws IOException {
71         if (index == 0)
72             return;
73         try {
74             createTables();
75             outputCodes();
76         }
77         catch (final LzhQuit ex) {
78             throw ex;
79         }
80         catch (final RuntimeException ex) {
81             final IOException exception = new LzhufException("huffman encoding error");
82             exception.initCause(ex);
83             throw exception;
84         }
85         finally {
86             index = 0;
87             ct1 = null;
88             lt1 = null;
89             ct2 = null;
90             lt2 = null;
91             ct3 = null;
92             lt3 = null;
93             Arrays.fill(frequencyTable, 0);
94         }
95     }
96
97     private void createTables() {
98         // create T1
99         final LzhHuffmanTable table1 = LzhHuffmanTable.build(frequencyTable);
100         ct1 = table1.codeTable;
101         lt1 = table1.codeLengthTable;
102         t1size = getTrimmedSize(lt1);
103         final int size = getTrimmedSize(lt1);
104         final int[] ft = new int[512];
105         for (int i1 = 0; i1 < size;) {
106             final int length = lt1[i1++];
107             if (length == 0) {
108                 int count = 1;
109                 while (i1 < size && lt1[i1] == 0) {
110                     ++i1;
111                     ++count;
112                 }
113                 if (count <= 2)
114                     ft[0] += count;
115                 else if (count <= 18)
116                     ++ft[1];
117                 else if (count == 19) {
118                     ++ft[0];
119                     ++ft[1];
120                 }
121                 else
122                     ++ft[2];
123             }
124             else {
125                 final int p = length + 2;
126                 ++ft[p];
127             }
128         }
129         // create T2
130         final LzhHuffmanTable table2 = LzhHuffmanTable.build(ft);
131         ct2 = table2.codeTable;
132         lt2 = table2.codeLengthTable;
133         // create T3
134         final int[] ft3 = new int[17];
135         for (int i = 0; i < index; i++) {
136             if (symbolBuffer[i] < 0x100)
137                 continue;
138             final int offset = offsetBuffer[i];
139             int bitLength = 0;
140             while (true) {
141                 if (offset < 1 << bitLength)
142                     break;
143                 ++bitLength;
144             }
145             ++ft3[bitLength];
146         }
147         final LzhHuffmanTable table3 = LzhHuffmanTable.build(ft3);
148         ct3 = table3.codeTable;
149         lt3 = table3.codeLengthTable;
150     }
151
152     private void outputCodes() throws IOException {
153         // a size of LZSS elements
154         final int t2size = getTrimmedSize(lt2);
155         out.writeBits(index, 16);
156         // T2
157         out.writeBits(t2size, 5);
158         for (int i = 0; i < t2size;) {
159             final int length = lt2[i++];
160             if (length <= 6)
161                 out.writeBits(length, 3);
162             else {
163                 out.writeBits(0xFFFFFFFF, length - 4);
164                 out.writeBits(0, 1);
165             }
166             if (i == 3) {
167                 while (i < 6 && lt2[i] == 0)
168                     ++i;
169                 out.writeBits(i - 3, 2);
170             }
171         }
172         // T1 table size
173         out.writeBits(t1size, 9);
174         // T1
175         for (int i = 0; i < t1size;) {
176             final int length = lt1[i++];
177             if (length == 0) {
178                 int count = 1;
179                 while (i < t1size && lt1[i] == 0) {
180                     ++i;
181                     ++count;
182                 }
183                 if (count <= 2)
184                     for (int j = 0; j < count; j++)
185                         out.writeBits(ct2[0], lt2[0]);
186                 else if (count <= 18) {
187                     out.writeBits(ct2[1], lt2[1]);
188                     out.writeBits(count - 3, 4);
189                 }
190                 else if (count == 19) {
191                     out.writeBits(ct2[0], lt2[0]);
192                     out.writeBits(ct2[1], lt2[1]);
193                     out.writeBits(15, 4);
194                 }
195                 else {
196                     out.writeBits(ct2[2], lt2[2]);
197                     out.writeBits(count - 20, 9);
198                 }
199             }
200             else
201                 out.writeBits(ct2[length + 2], lt2[length + 2]);
202         }
203         // T3
204         final int t3size = getTrimmedSize(lt3);
205         out.writeBits(t3size, 4);
206         if (t3size == 0)
207             out.writeBits(0, 4);
208         else
209             for (int i = 0; i < t3size;) {
210                 final int length = lt3[i++];
211                 if (length <= 6)
212                     out.writeBits(length, 3);
213                 else {
214                     out.writeBits(0xFFFFFFFF, length - 4);
215                     out.writeBits(0, 1);
216                 }
217             }
218         // LZSS
219         for (int i = 0; i < index; i++) {
220             final int symbol = symbolBuffer[i];
221             out.writeBits(ct1[symbol], lt1[symbol]);
222             if (symbol >= 0x100) {
223                 final int offset = offsetBuffer[i];
224                 int offsetBitLength = 1;
225                 while (true) {
226                     if (offset < (1 << offsetBitLength))
227                         break;
228                     ++offsetBitLength;
229                 }
230                 if (offset == 0)
231                     offsetBitLength = 0;
232                 out.writeBits(ct3[offsetBitLength], lt3[offsetBitLength]);
233                 if (offsetBitLength > 1)
234                     out.writeBits(offset, offsetBitLength - 1);
235             }
236         }
237         out.flush();
238     }
239
240     private static int getTrimmedSize(int[] a) {
241         int i = a.length;
242         while (i > 0 && a[i - 1] == 0)
243             --i;
244         return i;
245     }
246
247     @Override
248     public void close() throws IOException {
249         try {
250             flush();
251         }
252         finally {
253             out.close();
254         }
255     }
256
257 }