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