/**
 * Strictly speaking, it is against patent laws to produce unlicensed
 * GIF images.  See http://www.unisys.com for license agreements.
 * Without such a license, the use of a class similar to the following
 * would be prohibited.
 *
 * --
 * Greg Faron
 * Integre Technical Publishing Co.
 */

import java.awt.AWTException;
import java.awt.Image;
import java.awt.image.PixelGrabber;
import java.io.IOException;
import java.io.OutputStream;

/**
 * Class <CODE>GIFEncoder</CODE> takes an <CODE>Image</CODE> and
 * saves it to a file using the <CODE>GIF</CODE> file format
 * (<A HREF="http://www.dcs.ed.ac.uk/%7Emxr/gfx/">Graphics Interchange
 * Format</A>).
 * A <CODE>GIFEncoder</CODE> object is constructed with either an
 * <CODE>Image</CODE> object (which must be fully loaded), or a set of
 * three 2-dimensional <CODE>byte</CODE> arrays.  The image file can be
 * written out with a call to {@link #write(OutputStream) write()}.<p>
 * Three caveats:
 * <UL>
 * <LI>Class <CODE>GIFEncoder</CODE> will convert the image to
 * indexed color upon
 * construction.  This will take some time, depending on the size of
 * the image.
 * Also, the act of writing the image to disk will take some
 * time.</LI>
 * <LI>The image cannot have more than 256 colors, since GIF is an 8
 * bit format.  For a 24 bit to 8 bit quantization algorithm, see
 * Graphics Gems II III.2 by <A
 * HREF="http://www.csd.uwo.ca/faculty/wu/">Xialoin Wu</A>.
 * Or check out his <A HREF="http://www.csd.uwo.ca/faculty/wu/cq.c">C
 * source</A>.</LI>
 * <LI>Since the image must be completely loaded into memory,
 * <CODE>GIFEncoder</CODE>
 * may have problems with large images.  Attempting to encode an
 * image which will not
 * fit into memory will probably result in the following
 * exception:<BR>
 * <CODE>java.awt.AWTException: Grabber returned false:
 * 192</CODE></LI>
 * </UL>
 * <CODE>GIFEncoder</CODE> is based upon gifsave.c, which was written
 * and released by:<p>
 * <DIV ALIGN="CENTER">
 * Sverre H. Huseby<BR>
 * Bjoelsengt. 17<BR>
 * N-0468 Oslo<BR>
 * Norway<p>
 * Phone: +47 2 230539<BR>
 * <A HREF="mailto:sverrehu@ifi.uio.no">sverrehu@ifi.uio.no</A><BR>
 * </DIV>
 *
 * @author Adam Doppelt (dead link <A
 * @author Greg Faron - Integre Technical Publishing -
 * @version 0.90 21 Apr 1996
 */
public class GIFEncoder extends Object
   {
   /**
    * image height in pixels
    */
   short imageWidth, imageHeight;
   /**
    * number of different colours in image
    */
   int numberOfColors;
   /**
    * linear array of all pixels in row major order.
    */
   byte[] allPixels = null;
   /**
    * list of all colours used in the image.
    */
   byte[] allColors = null;

   /**
    * Convenience constructor for class <CODE>GIFEncoder</CODE>.  The
    * argument will
    * be converted to an indexed color array.
    * <B>This may take some time.</B>
    *
    * @param image  The image to encode. The image <B>must</B> be
    *               completely loaded.
    * @exception AWTException
    *                   Will be thrown if the pixel grab fails.
    *                   This can happen
    *                   if Java runs out of memory.  It may also
    *                   indicate that the
    *                   image contains more than 256 colors.
    */
   public GIFEncoder( Image image )
   throws AWTException
   {
      this.imageWidth = (short )image.getWidth( null );
      this.imageHeight = (short )image.getHeight( null );

      int values[] = new int[this.imageWidth * this.imageHeight];
      PixelGrabber grabber = new PixelGrabber( image,
                                               0, 0,
                                               this.imageWidth,
                                               this.imageHeight,
                                               values, 0, this.imageWidth );

      try
         {
         if ( grabber.grabPixels( ) != true )
            throw new AWTException( "Grabber returned false: " +
                                    grabber.status( ) );
         } // ends try

      catch ( InterruptedException ie )
         {
         }

      byte[][] r = new byte[this.imageWidth][this.imageHeight];
      byte[][] g = new byte[this.imageWidth][this.imageHeight];
      byte[][] b = new byte[this.imageWidth][this.imageHeight];
      int index = 0;

      for ( int y=0; y<this.imageHeight; y++ )
         {
         for ( int x=0; x<this.imageWidth; x++, index++ )
            {
            r[x][y] = (byte)( ( values[index] >> 16 ) & 0xFF );
            g[x][y] = (byte)( ( values[index] >> 8 ) & 0xFF );
            b[x][y] = (byte)( ( values[index] ) & 0xFF );
            } // ends for

         } // ends for

      this.toIndexColor( r, g, b );
   } // ends constructor GIFEncoder(Image )

   /** Standard constructor for class <CODE>GIFEncoder</CODE>.
     * Each array stores intensity
     * values for the image.  In other words,
     * <NOBR><CODE>r[x][y]</CODE></NOBR> refers to
     * the red intensity of the pixel at column <CODE>x</CODE>, row
     * <CODE>y</CODE>.
     * @param r A 2-dimensional array containing the red intensity values.
     * @param g A 2-dimensional array containing the green intensity
     * values.
     * @param b A 2-dimensional array containing the blue intensity values.
     * @exception AWTException Thrown if the image contains more than 256
     * colors.
     */
   public GIFEncoder( byte[][] r, byte[][] g, byte[][] b )
   throws AWTException
   {
      this.imageWidth = (short )( r.length );
      this.imageHeight = (short )( r[0].length );

      this.toIndexColor( r, g, b );
   } // ends constructor GIFEncoder(byte[][], byte[][], byte[][] )

   /** Writes the image out to a stream in the <CODE>GIF</CODE> file
     * format.
     * This will be a single GIF87a image, non-interlaced, with no
     * background color.
     * <B>This may take some time.</B>
     * @param output The stream to which to output. This should probably be
     * a buffered stream.
     * @exception IOException Thrown if a write operation fails.
     */
   public void write( OutputStream output )
   throws IOException
   {
      BitUtils.writeString( output, "GIF87a" );
      ScreenDescriptor sd = new ScreenDescriptor( this.imageWidth,
                                                  this.imageHeight, this.numberOfColors );
      sd.write( output );

      output.write( this.allColors, 0, this.allColors.length) ;

      ImageDescriptor id = new ImageDescriptor( this.imageWidth, this.imageHeight, ',' );
      id.write( output );

      byte codesize = BitUtils.BitsNeeded(this.numberOfColors);
      if ( codesize == 1 )
         {
         codesize ++;
         }
      output.write( codesize );

      LZWCompressor.LZWCompress( output, codesize, this.allPixels );
      output.write( 0 );

      id = new ImageDescriptor( (byte)0, (byte)0, ';' );
      id.write( output );
      output.flush();
   } // ends write( OutputStream )

   /**
    * Converts rgb desrcription of image to colour
    * number description used by GIF.
    *
    * @param r      red array of pixels
    * @param g      green array of pixels
    * @param b      blue array of pixels
    * @exception AWTException
    *                   Thrown if
    *                   too many different colours in image.
    */
   void toIndexColor( byte[][] r, byte[][] g, byte[][] b )
   throws AWTException
   {
      this.allPixels = new byte[this.imageWidth * this.imageHeight];
      this.allColors = new byte[256 * 3];
      int colornum = 0;
      for ( int x=0; x<this.imageWidth; x++ )
         {
         for ( int y=0; y<this.imageHeight; y++ )
            {
            int search;
            for ( search=0; search < colornum; search++ )
               {
               if ( this.allColors[search * 3] == r[x][y] &&
                    this.allColors[search * 3 + 1] == g[x][y] &&
                    this.allColors[search * 3 + 2] == b[x][y] )
                  {
                  break;
                  } // ends if

               } // ends for

            if ( search > 255 )
               throw new AWTException( "Too many colors." );
            // row major order y=row x=col
            this.allPixels[y * this.imageWidth + x] = (byte)search;

            if ( search == colornum )
               {
               this.allColors[search * 3] = r[x][y]; // [col][row]
               this.allColors[search * 3 + 1] = g[x][y];
               this.allColors[search * 3 + 2] = b[x][y];
               colornum++;
               } // ends if

            } // ends for

         } // ends for

      this.numberOfColors = 1 << BitUtils.BitsNeeded( colornum );
      byte copy[] = new byte[this.numberOfColors * 3];
      System.arraycopy( this.allColors, 0, copy, 0, this.numberOfColors * 3 );
      this.allColors = copy;
   } // ends toIndexColor(byte[][], byte[][], byte[][] )

   } // ends class GIFEncoder

/**
 * Used to write the bits composing the GIF image.
 */
class BitFile extends Object
   {
   /**
    * The outputstream where the data is written.
    */
   OutputStream output = null;
   /**
    * buffer for bits to write.
    */
   byte[] buffer;
   /**
    */
   int indexIntoOutputStream, bitsLeft;

   /**
    * constructor
    *
    * @param output Where image will be written
    */
   public BitFile( OutputStream output )
      {
      this.output = output;
      this.buffer = new byte[256];
      this.indexIntoOutputStream = 0;
      this.bitsLeft = 8;
      } // ends constructor BitFile(OutputStream )

   /**
    * Ensures image in ram gets to disk.
    *
    * @exception IOException
    */
   public void flush( )
   throws IOException
   {
      int numBytes = this.indexIntoOutputStream + ( (this.bitsLeft == 8 ) ? 0 : 1 );
      if ( numBytes > 0 )
         {
         this.output.write( numBytes );
         this.output.write( this.buffer, 0, numBytes );
         this.buffer[0] = 0;
         this.indexIntoOutputStream = 0;
         this.bitsLeft = 8;
         } // ends if

   } // ends flush( void )

   /**
    * Write bits to stream.
    *
    * @param bits    source of bits, low/high order?
    * @param numbits how many bits to write.
    *
    * @exception IOException
    */
   public void writeBits( int bits, int numbits )
   throws IOException
   {
      int bitsWritten = 0;
      int numBytes = 255;
      do
         {
         if ( (this.indexIntoOutputStream == 254 && this.bitsLeft == 0 ) ||
              this.indexIntoOutputStream > 254 )
            {
            this.output.write( numBytes );
            this.output.write( this.buffer, 0, numBytes );

            this.buffer[0] = 0;
            this.indexIntoOutputStream = 0;