/**
 * WriteGIF is a class that takes an Image and saves it to
 * a GIF format file.
 *
 * Based upon gifsave.c, which was written and released by
 * Sverre H. Huseby. Ported to Java by Adam Doppelt of Brown
 * University.
 * Modified and integrated with the ImageProc program for
 * CS411X, advanced Java Programming at the University of
 * Bridgeport by Victor Silva
 * Modified again by D. Lyon 7/8/01
 *
 */
package ip.gif;

import java.io.FileOutputStream;

public class WriteGIF {
  short width_, height_;
  int numColors_;
  byte pixels_[], colors_[];

  ScreenDescriptor sd_;
  ImageDescriptor id_;

  public static void toFile(java.awt.Image img, String fname) {
    // encode the image as a GIF
    try {
      WriteGIF wg = new WriteGIF(img);
      wg.toOutputStream(
          new java.io.BufferedOutputStream(
              new FileOutputStream(fname))
      );
    } catch (Exception e) {
      System.out.println("Save GIF Exception!");
    }
  }

  public WriteGIF(java.awt.Image image) throws java.awt.AWTException {
    width_ = (short) image.getWidth(null);
    height_ = (short) image.getHeight(null);

    int values[] = new int[width_ * height_];
    java.awt.image.PixelGrabber grabber = new java.awt.image.PixelGrabber(
        image, 0, 0, width_, height_, values, 0, width_);

    try {
      if (grabber.grabPixels() != true)
        throw new java.awt.AWTException("Grabber returned false: " +
                                        grabber.status());
    } catch (InterruptedException e) {
    }
    ;

    //--------------------------------------------------------------
    // TODO -> Possible Speed up - do it a row at a time, a la ACME
    //--------------------------------------------------------------
    byte r[][] = new byte[width_][height_];
    byte g[][] = new byte[width_][height_];
    byte b[][] = new byte[width_][height_];
    int index = 0;

    for (int y = 0; y < height_; ++y) {
      for (int x = 0; x < width_; ++x) {
        r[x][y] = (byte) ((values[index] >> 16) & 0xFF);
        g[x][y] = (byte) ((values[index] >> 8) & 0xFF);
        b[x][y] = (byte) ((values[index]) & 0xFF);
        ++index;
      }
    }
    toIndexedColor(r, g, b);
  }


  public void toOutputStream(java.io.OutputStream os)
      throws java.io.IOException {
    BitUtils.writeString(os, "GIF87a");
    ScreenDescriptor sd =
        new ScreenDescriptor(
            width_, height_, numColors_);
    sd.write(os);
    os.write(colors_, 0, colors_.length);
    ImageDescriptor id =
        new ImageDescriptor(width_, height_, ',');
    id.toOutputStream(os);

    byte codesize = BitUtils.bitsNeeded(numColors_);
    if (codesize == 1) ++codesize;

    os.write(codesize);

    LZWCompressor.compress(os, codesize, pixels_);
    os.write(0);

    id = new ImageDescriptor((byte) 0, (byte) 0, ';');
    id.toOutputStream(os);
    os.flush();
  }

  void toIndexedColor(byte r[][], byte g[][], byte b[][])
      throws java.awt.AWTException {
    pixels_ = new byte[width_ * height_];
    colors_ = new byte[256 * 3];
    int colornum = 0;
    for (int x = 0; x < width_; ++x) {
      for (int y = 0; y < height_; ++y) {
        int search;
        for (search = 0; search < colornum; ++search) {
          if (colors_[search * 3] == r[x][y] &&
              colors_[search * 3 + 1] == g[x][y] &&
              colors_[search * 3 + 2] == b[x][y]) {
            break;
          }
        }

        // If there are more than 256 colors invoke
        // the color quantization procedure.
        //quantization();
        if (search > 255) {
          throw new java.awt.AWTException("Too many colors.");
        }

        pixels_[y * width_ + x] = (byte) search;

        if (search == colornum) {
          colors_[search * 3] = r[x][y];
          colors_[search * 3 + 1] = g[x][y];
          colors_[search * 3 + 2] = b[x][y];
          ++colornum;
        }
      }
    }
    numColors_ = 1 << BitUtils.bitsNeeded(colornum);
    byte copy[] = new byte[numColors_ * 3];
    System.arraycopy(colors_, 0, copy, 0, numColors_ * 3);
    colors_ = copy;
  }
}

class BitFile {
  java.io.OutputStream output_;
  byte buffer_[];
  int index_, bitsLeft_;

  public BitFile(java.io.OutputStream output) {
    output_ = output;
    buffer_ = new byte[256];
    index_ = 0;
    bitsLeft_ = 8;
  }

  public void flush() throws java.io.IOException {
    int numBytes = index_ + (bitsLeft_ == 8 ? 0 : 1);
    if (numBytes > 0) {
      output_.write(numBytes);
      output_.write(buffer_, 0, numBytes);
      buffer_[0] = 0;
      index_ = 0;
      bitsLeft_ = 8;
    }
  }

  public void writeBits(int bits, int numbits)
      throws java.io.IOException {
    int bitsWritten = 0;
    int numBytes = 255;
    do {
      if ((index_ == 254 && bitsLeft_ == 0)
          || index_ > 254) {
        output_.write(numBytes);
        output_.write(buffer_, 0, numBytes);

        buffer_[0] = 0;
        index_ = 0;
        bitsLeft_ = 8;
      }

      if (numbits <= bitsLeft_) {
        buffer_[index_] |= (bits & ((1 << numbits) - 1)) <<
            (8 - bitsLeft_);
        bitsWritten += numbits;
        bitsLeft_ -= numbits;
        numbits = 0;
      } else {
        buffer_[index_] |= (bits & ((1 << bitsLeft_) - 1)) <<
            (8 - bitsLeft_);
        bitsWritten += bitsLeft_;
        bits >>= bitsLeft_;
        numbits -= bitsLeft_;
        buffer_[++index_] = 0;
        bitsLeft_ = 8;
      }
    } while (numbits != 0);
  }
}

class LZWStringTable {
  private final static int RES_CODES = 2;
  private final static short HASH_FREE = (short) 0xFFFF;
  private final static short NEXT_FIRST = (short) 0xFFFF;
  private final static int MAXBITS = 12;
  private final static int MAXSTR = (1 << MAXBITS);
  private final static short HASHSIZE = 9973;
  private final static short HASHSTEP = 2039;

  byte strChr_[];
  short strNxt_[];
  short strHsh_[];
  short numStrings_;

  public LZWStringTable() {
    strChr_ = new byte[MAXSTR];
    strNxt_ = new short[MAXSTR];
    strHsh_ = new short[HASHSIZE];
  }

  public int addCharString(short index, byte b) {
    int hshidx;

    if (numStrings_ >= MAXSTR)
      return 0xFFFF;

    hshidx = hash(index, b);
    while (strHsh_[hshidx] != HASH_FREE)
      hshidx = (hshidx + HASHSTEP) % HASHSIZE;

    strHsh_[hshidx] = numStrings_;
    strChr_[numStrings_] = b;
    strNxt_[numStrings_] = (index != HASH_FREE) ? index : NEXT_FIRST;

    return numStrings_++;
  }

  public short findCharString(short index, byte b) {
    int hshidx, nxtidx;

    if (index == HASH_FREE)
      return b;

    hshidx = hash(index, b);
    while ((nxtidx = strHsh_[hshidx]) != HASH_FREE) {
      if (strNxt_[nxtidx] == index
          && strChr_[nxtidx] == b)
        return (short) nxtidx;
      hshidx = (hshidx + HASHSTEP) % HASHSIZE;
    }

    return (short) 0xFFFF;
  }

  public void clearTable(int codesize) {
    numStrings_ = 0;

    for (int q = 0; q < HASHSIZE; q++)
      strHsh_[q] = HASH_FREE;

    int w = (1 << codesize) + RES_CODES;
    for (int q = 0; q < w; q++)
      addCharString((short) 0xFFFF, (byte) q);
  }

  static public int hash(short index, byte lastbyte) {
    return (
        (int) (
        (short) (lastbyte << 8) ^ index
        ) & 0xFFFF
        ) % HASHSIZE;
  }
}

class LZWCompressor {
  public static void compress(
      java.io.OutputStream os, int codesize,
      byte toCompress[]) throws java.io.IOException {
    byte c;
    short index;
    int clearcode, endofinfo, numbits, limit, errcode;
    short prefix = (short) 0xFFFF;

    BitFile bitFile = new BitFile(os);
    LZWStringTable strings = new LZWStringTable();

    clearcode = 1 << codesize;
    endofinfo = clearcode + 1;

    numbits = codesize + 1;
    limit = (1 << numbits) - 1;

    strings.clearTable(codesize);
    bitFile.writeBits(clearcode, numbits);

    for (int loop = 0; loop < toCompress.length; ++loop) {
      c = toCompress[loop];
      if ((index =
          strings.findCharString(prefix, c)) != -1)
        prefix = index;
      else {
        bitFile.writeBits(prefix, numbits);
        if (strings.addCharString(prefix, c) > limit) {
          if (++numbits > 12) {
            bitFile.writeBits(clearcode, numbits - 1);
            strings.clearTable(codesize);
            numbits = codesize + 1;
          }
          limit = (1 << numbits) - 1;
        }

        prefix = (short) ((short) c & 0xFF);
      }
    }

    if (prefix != -1) {
      bitFile.writeBits(prefix, numbits);
    }

    bitFile.writeBits(endofinfo, numbits);
    bitFile.flush();
  }
}

class ScreenDescriptor {
  public short localScreenWidth_, localScreenHeight_;
  private byte byte_;
  public byte backgroundColorIndex_, pixelAspectRatio_;

  public ScreenDescriptor(
      short width, short height, int numColors) {
    localScreenWidth_ = width;
    localScreenHeight_ = height;
    SetGlobalColorTableSize(
        (byte) (BitUtils.bitsNeeded(numColors) - 1));
    SetGlobalColorTableFlag((byte) 1);
    SetSortFlag((byte) 0);
    SetColorResolution((byte) 7);
    backgroundColorIndex_ = 0;
    pixelAspectRatio_ = 0;
  }

  public void write(java.io.OutputStream os)
      throws java.io.IOException {
    BitUtils.writeWord(os, localScreenWidth_);
    BitUtils.writeWord(os, localScreenHeight_);
    os.write(byte_);
    os.write(backgroundColorIndex_);
    os.write(pixelAspectRatio_);
  }

  public void SetGlobalColorTableSize(byte num) {
    byte_ |= (num & 7);
  }

  public void SetSortFlag(byte num) {
    byte_ |= (num & 1) << 3;
  }

  public void SetColorResolution(byte num) {
    byte_ |= (num & 7) << 4;
  }

  public void SetGlobalColorTableFlag(byte num) {
    byte_ |= (num & 1) << 7;
  }
}

class ImageDescriptor {
  public byte separator_;
  public short leftPosition_, topPosition_, width_, height_;
  private byte byte_;

  public ImageDescriptor(
      short width, short height, char separator) {
    separator_ = (byte) separator;
    leftPosition_ = 0;
    topPosition_ = 0;
    width_ = width;
    height_ = height;
    setLocalColorTableSize((byte) 0);
    setReserved((byte) 0);
    setSortFlag((byte) 0);
    setInterlaceFlag((byte) 0);
    setLocalColorTableFlag((byte) 0);
  }

  public void toOutputStream(java.io.OutputStream os)
      throws java.io.IOException {
    os.write(separator_);
    BitUtils.writeWord(os, leftPosition_);
    BitUtils.writeWord(os, topPosition_);
    BitUtils.writeWord(os, width_);
    BitUtils.writeWord(os, height_);
    os.write(byte_);
  }

  public void setLocalColorTableSize(byte num) {
    byte_ |= (num & 7);
  }

  public void setReserved(byte num) {
    byte_ |= (num & 3) << 3;
  }

  public void setSortFlag(byte num) {
    byte_ |= (num & 1) << 5;
  }

  public void setInterlaceFlag(byte num) {
    byte_ |= (num & 1) << 6;
  }

  public void setLocalColorTableFlag(byte num) {
    byte_ |= (num & 1) << 7;
  }
}

class BitUtils {
  public static byte bitsNeeded(int n) {
    byte ret = 1;

    if (n-- == 0) return 0;

    while ((n >>= 1) != 0)
      ++ret;

    return ret;
  }

  public static void writeWord(
      java.io.OutputStream os, short w)
      throws java.io.IOException {
    os.write(w & 0xFF);
    os.write((w >> 8) & 0xFF);
  }

  static void writeString(
      java.io.OutputStream os, String string)
      throws java.io.IOException {
    for (int i = 0; i < string.length(); ++i)
      os.write((byte) (string.charAt(i)));
  }
}