// GifEncoder - write out an image as a GIF
//
// Transparency handling and variable bit size courtesy of Jack Palevich.
//
// Copyright (C)1996,1998 by Jef Poskanzer <jef@acme.com>. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
// Visit the ACME Labs Java page for up-to-date versions of this and other
// fine Java utilities: http://www.acme.com/java/

package Acme.JPM.Encoders;

import java.util.*;
import java.io.*;
import java.awt.Image;
import java.awt.image.*;

/// Write out an image as a GIF.
// <P>
// <A HREF="/resources/classes/Acme/JPM/Encoders/GifEncoder.java">Fetch the software.</A><BR>
// <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
// <P>
// @see ToGif

public class GifEncoder extends ImageEncoder
    {

    private boolean interlace = false;

    /// Constructor from Image.
    // @param img The image to encode.
    // @param out The stream to write the GIF to.
    public GifEncoder( Image img, OutputStream out ) throws IOException
	{
	super( img, out );
	}

    /// Constructor from Image with interlace setting.
    // @param img The image to encode.
    // @param out The stream to write the GIF to.
    // @param interlace Whether to interlace.
    public GifEncoder( Image img, OutputStream out, boolean interlace ) throws IOException
	{
	super( img, out );
	this.interlace = interlace;
	}

    /// Constructor from ImageProducer.
    // @param prod The ImageProducer to encode.
    // @param out The stream to write the GIF to.
    public GifEncoder( ImageProducer prod, OutputStream out ) throws IOException
	{
	super( prod, out );
	}

    /// Constructor from ImageProducer with interlace setting.
    // @param prod The ImageProducer to encode.
    // @param out The stream to write the GIF to.
    public GifEncoder( ImageProducer prod, OutputStream out, boolean interlace ) throws IOException
	{
	super( prod, out );
	this.interlace = interlace;
	}


    int width, height;
    int[][] rgbPixels;

    void encodeStart( int width, int height ) throws IOException
	{
	this.width = width;
	this.height = height;
	rgbPixels = new int[height][width];
	}

    void encodePixels(
	int x, int y, int w, int h, int[] rgbPixels, int off, int scansize )
	throws IOException
	{
	// Save the pixels.
	for ( int row = 0; row < h; ++row )
	    System.arraycopy(
		rgbPixels, row * scansize + off,
		this.rgbPixels[y + row], x, w );

	}

    Acme.IntHashtable colorHash;

    void encodeDone() throws IOException
	{
	int transparentIndex = -1;
	int transparentRgb = -1;
        // Put all the pixels into a hash table.
        colorHash = new Acme.IntHashtable();
	int index = 0;
        for ( int row = 0; row < height; ++row )
            {
            int rowOffset = row * width;
            for ( int col = 0; col < width; ++col )
                {
                int rgb = rgbPixels[row][col];
		boolean isTransparent = ( ( rgb >>> 24 ) < 0x80 );
		if ( isTransparent )
		    {
		    if ( transparentIndex < 0 )
			{
			// First transparent color; remember it.
			transparentIndex = index;
			transparentRgb = rgb;
			}
		    else if ( rgb != transparentRgb )
			{
			// A second transparent color; replace it with
			// the first one.
			rgbPixels[row][col] = rgb = transparentRgb;
			}
		    }
                GifEncoderHashitem item =
		    (GifEncoderHashitem) colorHash.get( rgb );
                if ( item == null )
		    {
		    if ( index >= 256 )
			throw new IOException( "too many colors for a GIF" );
                    item = new GifEncoderHashitem(
			rgb, 1, index, isTransparent );
		    ++index;
		    colorHash.put( rgb, item );
		    }
                else
                    ++item.count;
                }
            }

	// Figure out how many bits to use.
	int logColors;
	if ( index <= 2 )
	    logColors = 1;
	else if ( index <= 4 )
	    logColors = 2;
	else if ( index <= 16 )
	    logColors = 4;
	else
	    logColors = 8;

	// Turn colors into colormap entries.
	int mapSize = 1 << logColors;
	byte[] reds = new byte[mapSize];
	byte[] grns = new byte[mapSize];
	byte[] blus = new byte[mapSize];
	for ( Enumeration e = colorHash.elements(); e.hasMoreElements(); )
	    {
	    GifEncoderHashitem item = (GifEncoderHashitem) e.nextElement();
	    reds[item.index] = (byte) ( ( item.rgb >> 16 ) & 0xff );
	    grns[item.index] = (byte) ( ( item.rgb >>  8 ) & 0xff );
	    blus[item.index] = (byte) (   item.rgb         & 0xff );
	    }

	GIFEncode(
	    out, width, height, interlace, (byte) 0, transparentIndex,
	    logColors, reds, grns, blus );
	}

    byte GetPixel( int x, int y ) throws IOException
	{
	GifEncoderHashitem item =
	    (GifEncoderHashitem) colorHash.get( rgbPixels[y][x] );
	if ( item == null )
	    throw new IOException( "color not found" );
	return (byte) item.index;
	}

    static void writeString( OutputStream out, String str ) throws IOException
        {
        byte[] buf = str.getBytes();
        out.write( buf );
        }

    // Adapted from ppmtogif, which is based on GIFENCOD by David
    // Rowley <mgardi@watdscu.waterloo.edu>.  Lempel-Zim compression
    // based on "compress".

    int Width, Height;
    boolean Interlace;
    int curx, cury;
    int CountDown;
    int Pass = 0;

    void GIFEncode(
	OutputStream outs, int Width, int Height, boolean Interlace, byte Background, int Transparent, int BitsPerPixel, byte[] Red, byte[] Green, byte[] Blue )
	throws IOException
	{
	byte B;
	int LeftOfs, TopOfs;
	int ColorMapSize;
	int InitCodeSize;
	int i;

	this.Width = Width;
	this.Height = Height;
	this.Interlace = Interlace;
	ColorMapSize = 1 << BitsPerPixel;
	LeftOfs = TopOfs = 0;

	// Calculate number of bits we are expecting
	CountDown = Width * Height;

	// Indicate which pass we are on (if interlace)
	Pass = 0;

	// The initial code size
	if ( BitsPerPixel <= 1 )
	    InitCodeSize = 2;
	else
	    InitCodeSize = BitsPerPixel;

	// Set up the current x and y position
	curx = 0;
	cury = 0;

	// Write the Magic header
	writeString( outs, "GIF89a" );

	// Write out the screen width and height
	Putword( Width, outs );
	Putword( Height, outs );

	// Indicate that there is a global colour map
	B = (byte) 0x80;		// Yes, there is a color map
	// OR in the resolution
	B |= (byte) ( ( 8 - 1 ) << 4 );
	// Not sorted
	// OR in the Bits per Pixel
	B |= (byte) ( ( BitsPerPixel - 1 ) );

	// Write it out
	Putbyte( B, outs );

	// Write out the Background colour
	Putbyte( Background, outs );

	// Pixel aspect ratio - 1:1.
	//Putbyte( (byte) 49, outs );
	// Java's GIF reader currently has a bug, if the aspect ratio byte is
	// not zero it throws an ImageFormatException.  It doesn't know that
	// 49 means a 1:1 aspect ratio.  Well, whatever, zero works with all
	// the other decoders I've tried so it probably doesn't hurt.
	Putbyte( (byte) 0, outs );

	// Write out the Global Colour Map
	for ( i = 0; i < ColorMapSize; ++i )
	    {
	    Putbyte( Red[i], outs );
	    Putbyte( Green[i], outs );
	    Putbyte( Blue[i], outs );
	    }

	// Write out extension for transparent colour index, if necessary.
	if ( Transparent != -1 )
	    {
	    Putbyte( (byte) '!', outs );
	    Putbyte( (byte) 0xf9, outs );
	    Putbyte( (byte) 4, outs );
	    Putbyte( (byte) 1, outs );
	    Putbyte( (byte) 0, outs );
	    Putbyte( (byte) 0, outs );
	    Putbyte( (byte) Transparent, outs );
	    Putbyte( (byte) 0, outs );
	    }

	// Write an Image separator
	Putbyte( (byte) ',', outs );

	// Write the Image header
	Putword( LeftOfs, outs );
	Putword( TopOfs, outs );
	Putword( Width, outs );
	Putword( Height, outs );

	// Write out whether or not the image is interlaced
	if ( Interlace )
	    Putbyte( (byte) 0x40, outs );
	else
	    Putbyte( (byte) 0x00, outs );

	// Write out the initial code size
	Putbyte( (byte) InitCodeSize, outs );

	// Go and actually compress the data
	compress( InitCodeSize+1, outs );

	// Write out a Zero-length packet (to end the series)
	Putbyte( (byte) 0, outs );

	// Write the GIF file terminator
	Putbyte( (byte) ';', outs );
	}

    // Bump the 'curx' and 'cury' to point to the next pixel
    void BumpPixel()
	{
	// Bump the current X position
	++curx;

	// If we are at the end of a scan line, set curx back to the beginning
	// If we are interlaced, bump the cury to the appropriate spot,
	// otherwise, just increment it.
	if ( curx == Width )
	    {
	    curx = 0;

	    if ( ! Interlace )
		++cury;
	    else
		{
		switch( Pass )
		    {
		    case 0:
		    cury += 8;
		    if ( cury >= Height )
			{
			++Pass;
			cury = 4;
			}
		    break;