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