001    package railo.runtime.img;
002    
003    import java.io.IOException;
004    import java.io.OutputStream;
005    
006    //==============================================================================
007    //  Adapted from Jef Poskanzer's Java port by way of J. M. G. Elliott.
008    //  K Weiner 12/00
009    
010    public class LZWEncoder {
011    
012            private static final int EOF = -1;
013    
014            private int imgW, imgH;
015            private byte[] pixAry;
016            private int initCodeSize;
017            private int remaining;
018            private int curPixel;
019    
020            // GIFCOMPR.C       - GIF Image compression routines
021            //
022            // Lempel-Ziv compression based on 'compress'.  GIF modifications by
023            // David Rowley (mgardi@watdcsu.waterloo.edu)
024    
025            // General DEFINEs
026    
027            static final int BITS = 12;
028    
029            static final int HSIZE = 5003; // 80% occupancy
030    
031            // GIF Image compression - modified 'compress'
032            //
033            // Based on: compress.c - File compression ala IEEE Computer, June 1984.
034            //
035            // By Authors:  Spencer W. Thomas      (decvax!harpo!utah-cs!utah-gr!thomas)
036            //              Jim McKie              (decvax!mcvax!jim)
037            //              Steve Davies           (decvax!vax135!petsd!peora!srd)
038            //              Ken Turkowski          (decvax!decwrl!turtlevax!ken)
039            //              James A. Woods         (decvax!ihnp4!ames!jaw)
040            //              Joe Orost              (decvax!vax135!petsd!joe)
041    
042            int n_bits; // number of bits/code
043            int maxbits = BITS; // user settable max # bits/code
044            int maxcode; // maximum code, given n_bits
045            int maxmaxcode = 1 << BITS; // should NEVER generate this code
046    
047            int[] htab = new int[HSIZE];
048            int[] codetab = new int[HSIZE];
049    
050            int hsize = HSIZE; // for dynamic table sizing
051    
052            int free_ent = 0; // first unused entry
053    
054            // block compression parameters -- after all codes are used up,
055            // and compression rate changes, start over.
056            boolean clear_flg = false;
057    
058            // Algorithm:  use open addressing double hashing (no chaining) on the
059            // prefix code / next character combination.  We do a variant of Knuth's
060            // algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
061            // secondary probe.  Here, the modular division first probe is gives way
062            // to a faster exclusive-or manipulation.  Also do block compression with
063            // an adaptive reset, whereby the code table is cleared when the compression
064            // ratio decreases, but after the table fills.  The variable-length output
065            // codes are re-sized at this point, and a special CLEAR code is generated
066            // for the decompressor.  Late addition:  construct the table according to
067            // file size for noticeable speed improvement on small files.  Please direct
068            // questions about this implementation to ames!jaw.
069    
070            int g_init_bits;
071    
072            int ClearCode;
073            int EOFCode;
074    
075            // output
076            //
077            // Output the given code.
078            // Inputs:
079            //      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
080            //              that n_bits =< wordsize - 1.
081            // Outputs:
082            //      Outputs code to the file.
083            // Assumptions:
084            //      Chars are 8 bits long.
085            // Algorithm:
086            //      Maintain a BITS character long buffer (so that 8 codes will
087            // fit in it exactly).  Use the VAX insv instruction to insert each
088            // code in turn.  When the buffer fills up empty it and start over.
089    
090            int cur_accum = 0;
091            int cur_bits = 0;
092    
093            int masks[] =
094                    {
095                            0x0000,
096                            0x0001,
097                            0x0003,
098                            0x0007,
099                            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            public 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            public 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    }