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.gif;
020
021/*
022 * @(#)GIFEncoder.java    0.90 4/21/96 Adam Doppelt
023 */
024import java.awt.AWTException;
025import java.awt.Image;
026import java.awt.image.PixelGrabber;
027import java.io.IOException;
028import java.io.OutputStream;
029
030/**
031 * GIFEncoder is a class which takes an image and saves it to a stream
032 * using the GIF file format (<A
033 * HREF="http://www.dcs.ed.ac.uk/%7Emxr/gfx/">Graphics Interchange
034 * Format</A>). A GIFEncoder
035 * is constructed with either an AWT Image (which must be fully
036 * loaded) or a set of RGB arrays. The image can be written out with a
037 * call to <CODE>Write</CODE>.<P>
038 *
039 * Three caveats:
040 * <UL>
041 *   <LI>GIFEncoder will convert the image to indexed color upon
042 *   construction. This will take some time, depending on the size of
043 *   the image. Also, actually writing the image out (Write) will take
044 *   time.<P>
045 *
046 *   <LI>The image cannot have more than 256 colors, since GIF is an 8
047 *   bit format. For a 24 bit to 8 bit quantization algorithm, see
048 *   Graphics Gems II III.2 by Xialoin Wu. Or check out his <A
049 *   HREF="http://www.csd.uwo.ca/faculty/wu/cq.c">C source</A>.<P>
050 *
051 *   <LI>Since the image must be completely loaded into memory,
052 *   GIFEncoder may have problems with large images. Attempting to
053 *   encode an image which will not fit into memory will probably
054 *   result in the following exception:<P>
055 *   <CODE>java.awt.AWTException: Grabber returned false: 192</CODE><P>
056 * </UL><P>
057 *
058 * GIFEncoder is based upon gifsave.c, which was written and released
059 * by:<P>
060 * <CENTER>
061 *                                  Sverre H. Huseby<BR>
062 *                                   Bjoelsengt. 17<BR>
063 *                                     N-0468 Oslo<BR>
064 *                                       Norway<P>
065 *
066 *                                 Phone: +47 2 230539<BR>
067 *                                 sverrehu@ifi.uio.no<P>
068 * </CENTER>
069 */
070public class GifEncoder {
071    short width_, height_;
072    int numColors_;
073    byte pixels_[], colors_[];
074    
075    ScreenDescriptor sd_;
076    ImageDescriptor id_;
077    
078/**
079 * Construct a GIFEncoder. The constructor will convert the image to
080 * an indexed color array. <B>This may take some time.</B><P>
081 * 
082 * @param image The image to encode. The image <B>must</B> be
083 * completely loaded.
084 * @exception AWTException Will be thrown if the pixel grab fails. This
085 * can happen if Java runs out of memory. It may also indicate that the image
086 * contains more than 256 colors.
087 * */
088    public GifEncoder(Image image) throws AWTException {
089        width_ = (short)image.getWidth(null);
090        height_ = (short)image.getHeight(null);
091
092        int values[] = new int[width_ * height_];
093        PixelGrabber grabber = new PixelGrabber(
094            image, 0, 0, width_, height_, values, 0, width_);
095        
096        try {
097            if(grabber.grabPixels() != true)
098                throw new AWTException("Grabber returned false: " +
099                                       grabber.status());
100        }
101        catch (InterruptedException e) { ; }
102        
103        byte r[][] = new byte[width_][height_];
104        byte g[][] = new byte[width_][height_];
105        byte b[][] = new byte[width_][height_];
106        int index = 0;
107        for (int y = 0; y < height_; ++y)
108            for (int x = 0; x < width_; ++x) {
109                r[x][y] = (byte)((values[index] >> 16) & 0xFF);
110                g[x][y] = (byte)((values[index] >> 8) & 0xFF);
111                b[x][y] = (byte)((values[index]) & 0xFF);  
112                ++index;
113            }
114        ToIndexedColor(r, g, b);
115    }
116
117/**
118 * Construct a GIFEncoder. The constructor will convert the image to
119 * an indexed color array. <B>This may take some time.</B><P>
120 *
121 * Each array stores intensity values for the image. In other words,
122 * r[x][y] refers to the red intensity of the pixel at column x, row
123 * y.<P>
124 *
125 * @param r An array containing the red intensity values.
126 * @param g An array containing the green intensity values.
127 * @param b An array containing the blue intensity values.
128 *
129 * @exception AWTException Will be thrown if the image contains more than
130 * 256 colors.
131 * */
132    public GifEncoder(byte r[][], byte g[][], byte b[][]) throws AWTException {
133        width_ = (short)(r.length);
134        height_ = (short)(r[0].length);
135
136        ToIndexedColor(r, g, b);
137    }
138
139/**
140 * Writes the image out to a stream in the GIF file format. This will
141 * be a single GIF87a image, non-interlaced, with no background color.
142 * <B>This may take some time.</B><P>
143 *
144 * @param output The stream to output to. This should probably be a
145 * buffered stream.
146 *
147 * @exception IOException Will be thrown if a write operation fails.
148 * */
149    public void Write(OutputStream output) throws IOException {
150        BitUtils.WriteString(output, "GIF87a");
151        
152        ScreenDescriptor sd = new ScreenDescriptor(width_, height_,
153                                                   numColors_);
154        sd.Write(output);
155
156        output.write(colors_, 0, colors_.length);
157
158        ImageDescriptor id = new ImageDescriptor(width_, height_, ',');
159        id.Write(output);
160
161        byte codesize = BitUtils.BitsNeeded(numColors_);
162        if (codesize == 1)
163            ++codesize;
164        output.write(codesize);
165
166        LZWCompressor.LZWCompress(output, codesize, pixels_);
167        output.write(0);
168
169        id = new ImageDescriptor((byte)0, (byte)0, ';');
170        id.Write(output);
171        output.flush();
172    }
173
174    void ToIndexedColor(byte r[][], byte g[][],
175                        byte b[][]) throws AWTException {
176        pixels_ = new byte[width_ * height_];
177        colors_ = new byte[256 * 3];
178        int colornum = 0;
179        for (int x = 0; x < width_; ++x) {
180            for (int y = 0; y < height_; ++y) {
181                int search;
182                for (search = 0; search < colornum; ++search)
183                    if (colors_[search * 3]     == r[x][y] &&
184                        colors_[search * 3 + 1] == g[x][y] &&
185                        colors_[search * 3 + 2] == b[x][y])
186                        break;
187                
188                if (search > 255)
189                    throw new AWTException("Too many colors.");
190
191                pixels_[y * width_ + x] = (byte)search;
192                
193                if (search == colornum) {
194                    colors_[search * 3]     = r[x][y];
195                    colors_[search * 3 + 1] = g[x][y];
196                    colors_[search * 3 + 2] = b[x][y];
197                    ++colornum;
198                }
199            }
200        }
201        numColors_ = 1 << BitUtils.BitsNeeded(colornum);
202        byte copy[] = new byte[numColors_ * 3];
203        System.arraycopy(colors_, 0, copy, 0, numColors_ * 3);
204        colors_ = copy;
205    }
206    
207}
208
209class BitFile {
210    OutputStream output_;
211    byte buffer_[];
212    int index_, bitsLeft_;
213
214    public BitFile(OutputStream output) {
215        output_ = output;
216        buffer_ = new byte[256];
217        index_ = 0;
218        bitsLeft_ = 8;
219    }
220
221    public void Flush() throws IOException {
222        int numBytes = index_ + (bitsLeft_ == 8 ? 0 : 1);
223        if (numBytes > 0) {
224            output_.write(numBytes);
225            output_.write(buffer_, 0, numBytes);
226            buffer_[0] = 0;
227            index_ = 0;
228            bitsLeft_ = 8;
229        }
230    }
231
232    public void WriteBits(int bits, int numbits) throws IOException {
233        //int bitsWritten = 0;
234        int numBytes = 255;
235        do {
236            if ((index_ == 254 && bitsLeft_ == 0) || index_ > 254) {
237                output_.write(numBytes);
238                output_.write(buffer_, 0, numBytes);
239
240                buffer_[0] = 0;
241                index_ = 0;
242                bitsLeft_ = 8;
243            }
244
245            if (numbits <= bitsLeft_) {
246                buffer_[index_] |= (bits & ((1 << numbits) - 1)) <<
247                    (8 - bitsLeft_);
248                //bitsWritten += numbits;
249                bitsLeft_ -= numbits;
250                numbits = 0;
251            }
252            else {
253                buffer_[index_] |= (bits & ((1 << bitsLeft_) - 1)) <<
254                    (8 - bitsLeft_);
255                //bitsWritten += bitsLeft_;
256                bits >>= bitsLeft_;
257                numbits -= bitsLeft_;
258                buffer_[++index_] = 0;
259                bitsLeft_ = 8;
260            }
261        } while (numbits != 0);
262    }
263}
264
265class LZWStringTable {
266    private final static int RES_CODES = 2;
267    private final static short HASH_FREE = (short)0xFFFF;
268    private final static short NEXT_FIRST = (short)0xFFFF;
269    private final static int MAXBITS = 12;
270    private final static int MAXSTR = (1 << MAXBITS);
271    private final static short HASHSIZE = 9973;
272    private final static short HASHSTEP = 2039;
273
274    byte strChr_[];
275    short strNxt_[];
276    short strHsh_[];
277    short numStrings_;
278
279    public LZWStringTable() {
280        strChr_ = new byte[MAXSTR];
281        strNxt_ = new short[MAXSTR];
282        strHsh_ = new short[HASHSIZE];    
283    }
284
285    public int AddCharString(short index, byte b) {
286        int hshidx;
287
288        if (numStrings_ >= MAXSTR)
289            return 0xFFFF;
290        
291        hshidx = Hash(index, b);
292        while (strHsh_[hshidx] != HASH_FREE)
293            hshidx = (hshidx + HASHSTEP) % HASHSIZE;
294        
295        strHsh_[hshidx] = numStrings_;
296        strChr_[numStrings_] = b;
297        strNxt_[numStrings_] = (index != HASH_FREE) ? index : NEXT_FIRST;
298
299        return numStrings_++;
300    }
301    
302    public short FindCharString(short index, byte b) {
303        int hshidx, nxtidx;
304
305        if (index == HASH_FREE)
306            return b;
307
308        hshidx = Hash(index, b);
309        while ((nxtidx = strHsh_[hshidx]) != HASH_FREE) {
310            if (strNxt_[nxtidx] == index && strChr_[nxtidx] == b)
311                return (short)nxtidx;
312            hshidx = (hshidx + HASHSTEP) % HASHSIZE;
313        }
314
315        return (short)0xFFFF;
316    }
317
318    public void ClearTable(int codesize) {
319        numStrings_ = 0;
320        
321        for (int q = 0; q < HASHSIZE; q++) {
322            strHsh_[q] = HASH_FREE;
323        }
324
325        int w = (1 << codesize) + RES_CODES;
326        for (int q = 0; q < w; q++)
327            AddCharString((short)0xFFFF, (byte)q);
328    }
329    
330    static public int Hash(short index, byte lastbyte) {
331        return (((short)(lastbyte << 8) ^ index) & 0xFFFF) % HASHSIZE;
332    }
333}
334
335class LZWCompressor {
336
337    public static void LZWCompress(OutputStream output, int codesize,
338                                   byte toCompress[]) throws IOException {
339        byte c;
340        short index;
341        int clearcode, endofinfo, numbits, limit;//, errcode;
342        short prefix = (short)0xFFFF;
343
344        BitFile bitFile = new BitFile(output);
345        LZWStringTable strings = new LZWStringTable();
346
347        clearcode = 1 << codesize;
348        endofinfo = clearcode + 1;
349    
350        numbits = codesize + 1;
351        limit = (1 << numbits) - 1;
352        
353        strings.ClearTable(codesize);
354        bitFile.WriteBits(clearcode, numbits);
355
356        for (int loop = 0; loop < toCompress.length; ++loop) {
357            c = toCompress[loop];
358            if ((index = strings.FindCharString(prefix, c)) != -1)
359                prefix = index;
360            else {
361                bitFile.WriteBits(prefix, numbits);
362                if (strings.AddCharString(prefix, c) > limit) {
363                    if (++numbits > 12) {
364                        bitFile.WriteBits(clearcode, numbits - 1);
365                        strings.ClearTable(codesize);
366                        numbits = codesize + 1;
367                    }
368                    limit = (1 << numbits) - 1;
369                }
370                
371                prefix = (short)(c & 0xFF);
372            }
373        }
374        
375        if (prefix != -1)
376            bitFile.WriteBits(prefix, numbits);
377        
378        bitFile.WriteBits(endofinfo, numbits);
379        bitFile.Flush();
380    }
381}
382
383class ScreenDescriptor {
384    public short localScreenWidth_, localScreenHeight_;
385    private byte byte_;
386    public byte backgroundColorIndex_, pixelAspectRatio_;
387
388    public ScreenDescriptor(short width, short height, int numColors) {
389        localScreenWidth_ = width;
390        localScreenHeight_ = height;
391        SetGlobalColorTableSize((byte)(BitUtils.BitsNeeded(numColors) - 1));
392        SetGlobalColorTableFlag((byte)1);
393        SetSortFlag((byte)0);
394        SetColorResolution((byte)7);
395        backgroundColorIndex_ = 0;
396        pixelAspectRatio_ = 0;
397    }
398
399    public void Write(OutputStream output) throws IOException {
400        BitUtils.WriteWord(output, localScreenWidth_);
401        BitUtils.WriteWord(output, localScreenHeight_);
402        output.write(byte_);
403        output.write(backgroundColorIndex_);
404        output.write(pixelAspectRatio_);
405    }
406
407    public void SetGlobalColorTableSize(byte num) {
408        byte_ |= (num & 7);
409    }
410
411    public void SetSortFlag(byte num) {
412        byte_ |= (num & 1) << 3;
413    }
414
415    public void SetColorResolution(byte num) {
416        byte_ |= (num & 7) << 4;
417    }
418    
419    public void SetGlobalColorTableFlag(byte num) {
420        byte_ |= (num & 1) << 7;
421    }
422}
423
424class ImageDescriptor {
425    public byte separator_;
426    public short leftPosition_, topPosition_, width_, height_;
427    private byte byte_;
428
429    public ImageDescriptor(short width, short height, char separator) {
430        separator_ = (byte)separator;
431        leftPosition_ = 0;
432        topPosition_ = 0;
433        width_ = width;
434        height_ = height;
435        SetLocalColorTableSize((byte)0);
436        SetReserved((byte)0);
437        SetSortFlag((byte)0);
438        SetInterlaceFlag((byte)0);
439        SetLocalColorTableFlag((byte)0);
440    }
441    
442    public void Write(OutputStream output) throws IOException {
443        output.write(separator_);
444        BitUtils.WriteWord(output, leftPosition_);
445        BitUtils.WriteWord(output, topPosition_);
446        BitUtils.WriteWord(output, width_);
447        BitUtils.WriteWord(output, height_);            
448        output.write(byte_);
449    }
450
451    public void SetLocalColorTableSize(byte num) {
452        byte_ |= (num & 7);
453    }
454
455    public void SetReserved(byte num) {
456        byte_ |= (num & 3) << 3;
457    }
458
459    public void SetSortFlag(byte num) {
460        byte_ |= (num & 1) << 5;
461    }
462    
463    public void SetInterlaceFlag(byte num) {
464        byte_ |= (num & 1) << 6;
465    }
466
467    public void SetLocalColorTableFlag(byte num) {
468        byte_ |= (num & 1) << 7;
469    }
470}
471
472class BitUtils {
473    public static byte BitsNeeded(int n) {
474        byte ret = 1;
475
476        if (n-- == 0)
477            return 0;
478
479        while ((n >>= 1) != 0)
480            ++ret;
481        
482        return ret;
483    }    
484
485    public static void WriteWord(OutputStream output,
486                                 short w) throws IOException {
487        output.write(w & 0xFF);
488        output.write((w >> 8) & 0xFF);
489    }
490    
491    static void WriteString(OutputStream output,
492                            String string) throws IOException {
493        for (int loop = 0; loop < string.length(); ++loop)
494            output.write((byte)(string.charAt(loop)));
495    }
496}