001/**
002 *
003 * Copyright (c) 2014, the Railo Company Ltd. All rights reserved.
004 *
005 * This library is free software; you can redistribute it and/or
006 * modify it under the terms of the GNU Lesser General Public
007 * License as published by the Free Software Foundation; either 
008 * version 2.1 of the License, or (at your option) any later version.
009 * 
010 * This library is distributed in the hope that it will be useful,
011 * but WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013 * Lesser General Public License for more details.
014 * 
015 * You should have received a copy of the GNU Lesser General Public 
016 * License along with this library.  If not, see <http://www.gnu.org/licenses/>.
017 * 
018 **/
019package lucee.runtime.img;
020
021import java.io.IOException;
022import java.io.OutputStream;
023
024//==============================================================================
025//  Adapted from Jef Poskanzer's Java port by way of J. M. G. Elliott.
026//  K Weiner 12/00
027
028public class LZWEncoder {
029
030        private static final int EOF = -1;
031
032        private int imgW, imgH;
033        private byte[] pixAry;
034        private int initCodeSize;
035        private int remaining;
036        private int curPixel;
037
038        // GIFCOMPR.C       - GIF Image compression routines
039        //
040        // Lempel-Ziv compression based on 'compress'.  GIF modifications by
041        // David Rowley (mgardi@watdcsu.waterloo.edu)
042
043        // General DEFINEs
044
045        static final int BITS = 12;
046
047        static final int HSIZE = 5003; // 80% occupancy
048
049        // GIF Image compression - modified 'compress'
050        //
051        // Based on: compress.c - File compression ala IEEE Computer, June 1984.
052        //
053        // By Authors:  Spencer W. Thomas      (decvax!harpo!utah-cs!utah-gr!thomas)
054        //              Jim McKie              (decvax!mcvax!jim)
055        //              Steve Davies           (decvax!vax135!petsd!peora!srd)
056        //              Ken Turkowski          (decvax!decwrl!turtlevax!ken)
057        //              James A. Woods         (decvax!ihnp4!ames!jaw)
058        //              Joe Orost              (decvax!vax135!petsd!joe)
059
060        int n_bits; // number of bits/code
061        int maxbits = BITS; // user settable max # bits/code
062        int maxcode; // maximum code, given n_bits
063        int maxmaxcode = 1 << BITS; // should NEVER generate this code
064
065        int[] htab = new int[HSIZE];
066        int[] codetab = new int[HSIZE];
067
068        int hsize = HSIZE; // for dynamic table sizing
069
070        int free_ent = 0; // first unused entry
071
072        // block compression parameters -- after all codes are used up,
073        // and compression rate changes, start over.
074        boolean clear_flg = false;
075
076        // Algorithm:  use open addressing double hashing (no chaining) on the
077        // prefix code / next character combination.  We do a variant of Knuth's
078        // algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
079        // secondary probe.  Here, the modular division first probe is gives way
080        // to a faster exclusive-or manipulation.  Also do block compression with
081        // an adaptive reset, whereby the code table is cleared when the compression
082        // ratio decreases, but after the table fills.  The variable-length output
083        // codes are re-sized at this point, and a special CLEAR code is generated
084        // for the decompressor.  Late addition:  construct the table according to
085        // file size for noticeable speed improvement on small files.  Please direct
086        // questions about this implementation to ames!jaw.
087
088        int g_init_bits;
089
090        int ClearCode;
091        int EOFCode;
092
093        // output
094        //
095        // Output the given code.
096        // Inputs:
097        //      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
098        //              that n_bits =< wordsize - 1.
099        // Outputs:
100        //      Outputs code to the file.
101        // Assumptions:
102        //      Chars are 8 bits long.
103        // Algorithm:
104        //      Maintain a BITS character long buffer (so that 8 codes will
105        // fit in it exactly).  Use the VAX insv instruction to insert each
106        // code in turn.  When the buffer fills up empty it and start over.
107
108        int cur_accum = 0;
109        int cur_bits = 0;
110
111        int masks[] =
112                {
113                        0x0000,
114                        0x0001,
115                        0x0003,
116                        0x0007,
117                        0x000F,
118                        0x001F,
119                        0x003F,
120                        0x007F,
121                        0x00FF,
122                        0x01FF,
123                        0x03FF,
124                        0x07FF,
125                        0x0FFF,
126                        0x1FFF,
127                        0x3FFF,
128                        0x7FFF,
129                        0xFFFF };
130
131        // Number of characters so far in this 'packet'
132        int a_count;
133
134        // Define the storage for the packet accumulator
135        byte[] accum = new byte[256];
136
137        //----------------------------------------------------------------------------
138        public LZWEncoder(int width, int height, byte[] pixels, int color_depth) {
139                imgW = width;
140                imgH = height;
141                pixAry = pixels;
142                initCodeSize = Math.max(2, color_depth);
143        }
144        
145        // Add a character to the end of the current packet, and if it is 254
146        // characters, flush the packet to disk.
147        void char_out(byte c, OutputStream outs) throws IOException {
148                accum[a_count++] = c;
149                if (a_count >= 254)
150                        flush_char(outs);
151        }
152        
153        // Clear out the hash table
154
155        // table clear for block compress
156        void cl_block(OutputStream outs) throws IOException {
157                cl_hash(hsize);
158                free_ent = ClearCode + 2;
159                clear_flg = true;
160
161                output(ClearCode, outs);
162        }
163        
164        // reset code table
165        void cl_hash(int hsize) {
166                for (int i = 0; i < hsize; ++i)
167                        htab[i] = -1;
168        }
169        
170        void compress(int init_bits, OutputStream outs) throws IOException {
171                int fcode;
172                int i /* = 0 */;
173                int c;
174                int ent;
175                int disp;
176                int hsize_reg;
177                int hshift;
178
179                // Set up the globals:  g_init_bits - initial number of bits
180                g_init_bits = init_bits;
181
182                // Set up the necessary values
183                clear_flg = false;
184                n_bits = g_init_bits;
185                maxcode = MAXCODE(n_bits);
186
187                ClearCode = 1 << (init_bits - 1);
188                EOFCode = ClearCode + 1;
189                free_ent = ClearCode + 2;
190
191                a_count = 0; // clear packet
192
193                ent = nextPixel();
194
195                hshift = 0;
196                for (fcode = hsize; fcode < 65536; fcode *= 2)
197                        ++hshift;
198                hshift = 8 - hshift; // set hash code range bound
199
200                hsize_reg = hsize;
201                cl_hash(hsize_reg); // clear hash table
202
203                output(ClearCode, outs);
204
205                outer_loop : while ((c = nextPixel()) != EOF) {
206                        fcode = (c << maxbits) + ent;
207                        i = (c << hshift) ^ ent; // xor hashing
208
209                        if (htab[i] == fcode) {
210                                ent = codetab[i];
211                                continue;
212                        } else if (htab[i] >= 0) // non-empty slot
213                                {
214                                disp = hsize_reg - i; // secondary hash (after G. Knott)
215                                if (i == 0)
216                                        disp = 1;
217                                do {
218                                        if ((i -= disp) < 0)
219                                                i += hsize_reg;
220
221                                        if (htab[i] == fcode) {
222                                                ent = codetab[i];
223                                                continue outer_loop;
224                                        }
225                                } while (htab[i] >= 0);
226                        }
227                        output(ent, outs);
228                        ent = c;
229                        if (free_ent < maxmaxcode) {
230                                codetab[i] = free_ent++; // code -> hashtable
231                                htab[i] = fcode;
232                        } else
233                                cl_block(outs);
234                }
235                // Put out the final code.
236                output(ent, outs);
237                output(EOFCode, outs);
238        }
239        
240        //----------------------------------------------------------------------------
241        public void encode(OutputStream os) throws IOException {
242                os.write(initCodeSize); // write "initial code size" byte
243
244                remaining = imgW * imgH; // reset navigation variables
245                curPixel = 0;
246
247                compress(initCodeSize + 1, os); // compress and write the pixel data
248
249                os.write(0); // write block terminator
250        }
251        
252        // Flush the packet to disk, and reset the accumulator
253        void flush_char(OutputStream outs) throws IOException {
254                if (a_count > 0) {
255                        outs.write(a_count);
256                        outs.write(accum, 0, a_count);
257                        a_count = 0;
258                }
259        }
260        
261        final int MAXCODE(int n_bits) {
262                return (1 << n_bits) - 1;
263        }
264        
265        //----------------------------------------------------------------------------
266        // Return the next pixel from the image
267        //----------------------------------------------------------------------------
268        private int nextPixel() {
269                if (remaining == 0)
270                        return EOF;
271
272                --remaining;
273
274                byte pix = pixAry[curPixel++];
275
276                return pix & 0xff;
277        }
278        
279        void output(int code, OutputStream outs) throws IOException {
280                cur_accum &= masks[cur_bits];
281
282                if (cur_bits > 0)
283                        cur_accum |= (code << cur_bits);
284                else
285                        cur_accum = code;
286
287                cur_bits += n_bits;
288
289                while (cur_bits >= 8) {
290                        char_out((byte) (cur_accum & 0xff), outs);
291                        cur_accum >>= 8;
292                        cur_bits -= 8;
293                }
294
295                // If the next entry is going to be too big for the code size,
296                // then increase it, if possible.
297                if (free_ent > maxcode || clear_flg) {
298                        if (clear_flg) {
299                                maxcode = MAXCODE(n_bits = g_init_bits);
300                                clear_flg = false;
301                        } else {
302                                ++n_bits;
303                                if (n_bits == maxbits)
304                                        maxcode = maxmaxcode;
305                                else
306                                        maxcode = MAXCODE(n_bits);
307                        }
308                }
309
310                if (code == EOFCode) {
311                        // At EOF, write the rest of the buffer.
312                        while (cur_bits > 0) {
313                                char_out((byte) (cur_accum & 0xff), outs);
314                                cur_accum >>= 8;
315                                cur_bits -= 8;
316                        }
317
318                        flush_char(outs);
319                }
320        }
321}