|
/Users/lyon/j4p/src/ip/gif/neuquantAnimation/LZWEncoder.java
|
1 package ip.gif.neuquantAnimation;
2
3 import java.io.OutputStream;
4 import java.io.IOException;
5
6 //==============================================================================
7 // Adapted from Jef Poskanzer's Java port by way of J. M. G. Elliott.
8 // K Weiner 12/00
9
10 class LZWEncoder {
11
12 private static final int EOF = -1;
13
14 private int imgW, imgH;
15 private byte[] pixAry;
16 private int initCodeSize;
17 private int remaining;
18 private int curPixel;
19
20 // GIFCOMPR.C - GIF Image compression routines
21 //
22 // Lempel-Ziv compression based on 'compress'. GIF modifications by
23 // David Rowley (mgardi@watdcsu.waterloo.edu)
24
25 // General DEFINEs
26
27 static final int BITS = 12;
28
29 static final int HSIZE = 5003; // 80% occupancy
30
31 // GIF Image compression - modified 'compress'
32 //
33 // Based on: compress.c - File compression ala IEEE Computer, June 1984.
34 //
35 // By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
36 // Jim McKie (decvax!mcvax!jim)
37 // Steve Davies (decvax!vax135!petsd!peora!srd)
38 // Ken Turkowski (decvax!decwrl!turtlevax!ken)
39 // James A. Woods (decvax!ihnp4!ames!jaw)
40 // Joe Orost (decvax!vax135!petsd!joe)
41
42 int n_bits; // number of bits/code
43 int maxbits = BITS; // user settable max # bits/code
44 int maxcode; // maximum code, given n_bits
45 int maxmaxcode = 1 << BITS; // should NEVER generate this code
46
47 int[] htab = new int[HSIZE];
48 int[] codetab = new int[HSIZE];
49
50 int hsize = HSIZE; // for dynamic table sizing
51
52 int free_ent = 0; // first unused entry
53
54 // block compression parameters -- after all codes are used up,
55 // and compression rate changes, start over.
56 boolean clear_flg = false;
57
58 // Algorithm: use open addressing double hashing (no chaining) on the
59 // prefix code / next character combination. We do a variant of Knuth's
60 // algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
61 // secondary probe. Here, the modular division first probe is gives way
62 // to a faster exclusive-or manipulation. Also do block compression with
63 // an adaptive reset, whereby the code table is cleared when the compression
64 // ratio decreases, but after the table fills. The variable-length output
65 // codes are re-sized at this point, and a special CLEAR code is generated
66 // for the decompressor. Late addition: construct the table according to
67 // file size for noticeable speed improvement on small files. Please direct
68 // questions about this implementation to ames!jaw.
69
70 int g_init_bits;
71
72 int ClearCode;
73 int EOFCode;
74
75 // output
76 //
77 // Output the given code.
78 // Inputs:
79 // code: A n_bits-bit integer. If == -1, then EOF. This assumes
80 // that n_bits =< wordsize - 1.
81 // Outputs:
82 // Outputs code to the file.
83 // Assumptions:
84 // Chars are 8 bits long.
85 // Algorithm:
86 // Maintain a BITS character long buffer (so that 8 codes will
87 // fit in it exactly). Use the VAX insv instruction to insert each
88 // code in turn. When the buffer fills up empty it and start over.
89
90 int cur_accum = 0;
91 int cur_bits = 0;
92
93 int masks[] =
94 {
95 0x0000,
96 0x0001,
97 0x0003,
98 0x0007,
99 0x000F,
100 0x001F,
101 0x003F,
102 0x007F,
103 0x00FF,
104 0x01FF,
105 0x03FF,
106 0x07FF,
107 0x0FFF,
108 0x1FFF,
109 0x3FFF,
110 0x7FFF,
111 0xFFFF };
112
113 // Number of characters so far in this 'packet'
114 int a_count;
115
116 // Define the storage for the packet accumulator
117 byte[] accum = new byte[256];
118
119 //----------------------------------------------------------------------------
120 LZWEncoder(int width, int height, byte[] pixels, int color_depth) {
121 imgW = width;
122 imgH = height;
123 pixAry = pixels;
124 initCodeSize = Math.max(2, color_depth);
125 }
126
127 // Add a character to the end of the current packet, and if it is 254
128 // characters, flush the packet to disk.
129 void char_out(byte c, OutputStream outs) throws IOException {
130 accum[a_count++] = c;
131 if (a_count >= 254)
132 flush_char(outs);
133 }
134
135 // Clear out the hash table
136
137 // table clear for block compress
138 void cl_block(OutputStream outs) throws IOException {
139 cl_hash(hsize);
140 free_ent = ClearCode + 2;
141 clear_flg = true;
142
143 output(ClearCode, outs);
144 }
145
146 // reset code table
147 void cl_hash(int hsize) {
148 for (int i = 0; i < hsize; ++i)
149 htab[i] = -1;
150 }
151
152 void compress(int init_bits, OutputStream outs) throws IOException {
153 int fcode;
154 int i /* = 0 */;
155 int c;
156 int ent;
157 int disp;
158 int hsize_reg;
159 int hshift;
160
161 // Set up the globals: g_init_bits - initial number of bits
162 g_init_bits = init_bits;
163
164 // Set up the necessary values
165 clear_flg = false;
166 n_bits = g_init_bits;
167 maxcode = MAXCODE(n_bits);
168
169 ClearCode = 1 << (init_bits - 1);
170 EOFCode = ClearCode + 1;
171 free_ent = ClearCode + 2;
172
173 a_count = 0; // clear packet
174
175 ent = nextPixel();
176
177 hshift = 0;
178 for (fcode = hsize; fcode < 65536; fcode *= 2)
179 ++hshift;
180 hshift = 8 - hshift; // set hash code range bound
181
182 hsize_reg = hsize;
183 cl_hash(hsize_reg); // clear hash table
184
185 output(ClearCode, outs);
186
187 outer_loop : while ((c = nextPixel()) != EOF) {
188 fcode = (c << maxbits) + ent;
189 i = (c << hshift) ^ ent; // xor hashing
190
191 if (htab[i] == fcode) {
192 ent = codetab[i];
193 continue;
194 } else if (htab[i] >= 0) // non-empty slot
195 {
196 disp = hsize_reg - i; // secondary hash (after G. Knott)
197 if (i == 0)
198 disp = 1;
199 do {
200 if ((i -= disp) < 0)
201 i += hsize_reg;
202
203 if (htab[i] == fcode) {
204 ent = codetab[i];
205 continue outer_loop;
206 }
207 } while (htab[i] >= 0);
208 }
209 output(ent, outs);
210 ent = c;
211 if (free_ent < maxmaxcode) {
212 codetab[i] = free_ent++; // code -> hashtable
213 htab[i] = fcode;
214 } else
215 cl_block(outs);
216 }
217 // Put out the final code.
218 output(ent, outs);
219 output(EOFCode, outs);
220 }
221
222 //----------------------------------------------------------------------------
223 void encode(OutputStream os) throws IOException {
224 os.write(initCodeSize); // write "initial code size" byte
225
226 remaining = imgW * imgH; // reset navigation variables
227 curPixel = 0;
228
229 compress(initCodeSize + 1, os); // compress and write the pixel data
230
231 os.write(0); // write block terminator
232 }
233
234 // Flush the packet to disk, and reset the accumulator
235 void flush_char(OutputStream outs) throws IOException {
236 if (a_count > 0) {
237 outs.write(a_count);
238 outs.write(accum, 0, a_count);
239 a_count = 0;
240 }
241 }
242
243 final int MAXCODE(int n_bits) {
244 return (1 << n_bits) - 1;
245 }
246
247 //----------------------------------------------------------------------------
248 // Return the next pixel from the image
249 //----------------------------------------------------------------------------
250 private int nextPixel() {
251 if (remaining == 0)
252 return EOF;
253
254 --remaining;
255
256 byte pix = pixAry[curPixel++];
257
258 return pix & 0xff;
259 }
260
261 void output(int code, OutputStream outs) throws IOException {
262 cur_accum &= masks[cur_bits];
263
264 if (cur_bits > 0)
265 cur_accum |= (code << cur_bits);
266 else
267 cur_accum = code;
268
269 cur_bits += n_bits;
270
271 while (cur_bits >= 8) {
272 char_out((byte) (cur_accum & 0xff), outs);
273 cur_accum >>= 8;
274 cur_bits -= 8;
275 }
276
277 // If the next entry is going to be too big for the code size,
278 // then increase it, if possible.
279 if (free_ent > maxcode || clear_flg) {
280 if (clear_flg) {
281 maxcode = MAXCODE(n_bits = g_init_bits);
282 clear_flg = false;
283 } else {
284 ++n_bits;
285 if (n_bits == maxbits)
286 maxcode = maxmaxcode;
287 else
288 maxcode = MAXCODE(n_bits);
289 }
290 }
291
292 if (code == EOFCode) {
293 // At EOF, write the rest of the buffer.
294 while (cur_bits > 0) {
295 char_out((byte) (cur_accum & 0xff), outs);
296 cur_accum >>= 8;
297 cur_bits -= 8;
298 }
299
300 flush_char(outs);
301 }
302 }
303 }
304