package com.one;

import java.io.IOException;
import java.io.OutputStream;

/**
 * Class for LZW compression of GIF data.
 * Extracted from GIFEncoder.
 *
 * GIFEncoder is based upon gifsave.c, which was written and released
 * by:<P>
 * <CENTER>
 *                                  Sverre H. Huseby<BR>
 *                                   Bjoelsengt. 17<BR>
 *                                     N-0468 Oslo<BR>
 *                                       Norway<P>
 *
 *                                 Phone: +47 2 230539<BR>
 *                                 sverrehu@ifi.uio.no<P>
 * </CENTER>
 * @version 0.90 21 Apr 1996
 * @author <A HREF="http://www.cs.brown.edu/people/amd/">Adam Doppelt</A>
 */

public class LZWCompressor
{
	protected static class BitFile
	{
		protected OutputStream output_;
		protected byte buffer_[];
		protected int index_, bitsLeft_;
	
		public BitFile(OutputStream output)
		{
			output_ = output;
			buffer_ = new byte[256];
			index_ = 0;
			bitsLeft_ = 8;
		}
	
		public void Flush() throws 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 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);
		}
	}
	
	protected static class LZWStringTable
	{
		protected final static int RES_CODES = 2;
		protected final static short HASH_FREE = (short)0xFFFF;
		protected final static short NEXT_FIRST = (short)0xFFFF;
		protected final static int MAXBITS = 12;
		protected final static int MAXSTR = (1 << MAXBITS);
		protected final static short HASHSIZE = 9973;
		protected final static short HASHSTEP = 2039;
	
		protected byte strChr_[];
		protected short strNxt_[];
		protected short strHsh_[];
		protected 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;
		}
	}
	
	protected OutputStream output;
	protected int codesize;
	protected int clearcode, endofinfo;
	protected int numbits, limit;
	protected BitFile bitFile;
	protected LZWStringTable strings;
	protected short prefix, index;
	
	public LZWCompressor(OutputStream output, int codesize) throws IOException
	{
		this.output = output;
		this.codesize = codesize;
		
		bitFile = new BitFile(output);
		strings = new LZWStringTable();

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

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

		strings.ClearTable(codesize);
		bitFile.WriteBits(clearcode, numbits);
		
		prefix = (short)0xFFFF;
	}
	
	public void write(byte c) throws IOException
	{
		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);
		}
	}
	
	public void finish() throws IOException
	{
		if(prefix != -1)
		{
			bitFile.WriteBits(prefix, numbits);
		}

		bitFile.WriteBits(endofinfo, numbits);
		bitFile.Flush();
	}
}