content: /**
   * Copyright (c) 2014-2016 by Wen Yu.
   * All rights reserved. This program and the accompanying materials
   * are made available under the terms of the Eclipse Public License v1.0
   * which accompanies this distribution, and is available at
   * http://www.eclipse.org/legal/epl-v10.html
   * 
   * Any modifications to this file must keep this entire header intact.
   * 
   * Change History - most recent changes go on top of previous changes
   *
   * AnimatedGIFWriter.java
   *
   * Who   Date       Description
   * ====  =========  =================================================
   * WY    29Oct2015  Crop image if outside of logical screen
   * WY    28Oct2015  Initial creation
   */
  
  package com.actelion.research.util;
  
  import java.awt.Dimension;
  import java.awt.image.BufferedImage;
  import java.awt.image.DataBuffer;
  import java.awt.image.IndexColorModel;
  import java.awt.image.Raster;
  import java.io.IOException;
  import java.io.OutputStream;
  import java.util.Arrays;
  import java.util.List;
  
  public class AnimatedGIFWriter {	
  	// Fields
  	private int codeLen;
  	private int codeIndex;
  	private int clearCode;
  	private int endOfImage;
  	private int bufIndex;	
  	private int empty_bits = 0x08;
  	
  	private int bitsPerPixel = 0x08;
  
  	private byte bytes_buf[] = new byte[256];
  	private int[] colorPalette;
  	private boolean isApplyDither;
   	
  	/**
  	 * A child is made up of a parent(or prefix) code plus a suffix color
  	 * and siblings are strings with a common parent(or prefix) and different
  	 * suffix colors
  	 */
  	int child[] = new int[4097];
  	
  	int siblings[] = new int[4097];
  	int suffix[] = new int[4097];
  	
  	private int logicalScreenWidth;
  	private int logicalScreenHeight;
  	
  	private boolean animated;
  	private int loopCount;
  	private boolean firstFrame = true;
  	
  	// Define constants
  	public static final byte IMAGE_SEPARATOR = 0x2c; // ","
  	public static final byte IMAGE_TRAILER = 0x3b; // ";"
  	public static final byte EXTENSION_INTRODUCER = 0x21; // "!"
  	public static final byte GRAPHIC_CONTROL_LABEL = (byte)0xf9;
  	public static final byte APPLICATION_EXTENSION_LABEL = (byte)0xff;
  	public static final byte COMMENT_EXTENSION_LABEL = (byte)0xfe;
  	public static final byte TEXT_EXTENSION_LABEL = 0x01;	
  
  	private static final int MASK[] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  		
  	private static Dimension getLogicalScreenSize(BufferedImage[] images) {
  		// Determine the logical screen dimension assuming all the frames have the same
  		// left and top coordinates (0, 0)
  		int logicalScreenWidth = 0;
  		int logicalScreenHeight = 0;
  		
  		for(BufferedImage image : images) {
  			if(image.getWidth() > logicalScreenWidth)
  				logicalScreenWidth = image.getWidth();
  			if(image.getHeight() > logicalScreenHeight)
  				logicalScreenHeight = image.getHeight();
  		}
  		
  		return new Dimension(logicalScreenWidth, logicalScreenHeight);
  	}
  	
  	private static Dimension getLogicalScreenSize(GIFFrame[] frames) {
  		// Determine the logical screen dimension given all the frames with different
  		// left and top coordinates.
  		int logicalScreenWidth = 0;
  		int logicalScreenHeight = 0;
  		
  		for(GIFFrame frame : frames) {
  			int frameRightPosition = frame.getFrameWidth() + frame.getLeftPosition();
  			int frameBottomPosition = frame.getFrameHeight() + frame.getTopPosition();
  			if(frameRightPosition > logicalScreenWidth)
  				logicalScreenWidth = frameRightPosition;
  			if(frameBottomPosition > logicalScreenHeight)
  				logicalScreenHeight = frameBottomPosition;
  		}
  		
  		return new Dimension(logicalScreenWidth, logicalScreenHeight);
  	}
  	
  	public AnimatedGIFWriter() { this(false);}
  	
  	public AnimatedGIFWriter(boolean isApplyDither) {
  		this.isApplyDither = isApplyDither;
  	}
  	
  	// Write as a single frame GIF
  	public void write(BufferedImage img, OutputStream os) throws Exception {
  		if(img == null) throw new NullPointerException("Input image is null");
  		int imageWidth = img.getWidth();
  		int imageHeight = img.getHeight();
  		write(getRGB(img), imageWidth, imageHeight, os);
  	}	
  	
  	private void encode(byte[] pixels, OutputStream os) throws Exception {
  		// Define local variables
  		int parent = 0;
  		int son = 0;
  		int brother = 0;
  		int color = 0;
  		int index = 0;
  		int dimension = pixels.length;
  
  		// Write out the length of the root
  		os.write(bitsPerPixel = (bitsPerPixel == 1)?2:bitsPerPixel);
  		// Initialize the encoder
  		init_encoder(bitsPerPixel);
  		// Tell the decoder to initialize the string table
  		send_code_to_buffer(clearCode, os);
          // Get the first color and assign it to parent
  		parent = (pixels[index++]&0xff);
  
  		while (index < dimension)
  		{
  			color = (pixels[index++]&0xff);
  			son = child[parent];
  
  			if ( son > 0){
  				if (suffix[son] == color) {
  					parent = son;
  				} else {
  					brother = son;
  					while (true)
  					{
  						if (siblings[brother] > 0)
  						{
  							brother = siblings[brother];
  							if (suffix[brother] == color)
  						    {
  							   parent = brother;
  							   break;
  						    }
  						} else {
  							siblings[brother] = codeIndex;
  							suffix[codeIndex] = color;
  							send_code_to_buffer(parent,os);
  							parent = color;
  							codeIndex++;
                 				// Check code length
  				            if(codeIndex > ((1<<codeLen)))
  			                {
  								if (codeLen == 12) 
   			                    {
  				                    send_code_to_buffer(clearCode,os);
  				                    init_encoder(bitsPerPixel);
  			                    } else
  					                codeLen++;
  			                }
  							break;
  						}
  					}
  				}
  			} else {
  				child[parent] = codeIndex;
  				suffix[codeIndex] = color;
  				send_code_to_buffer(parent,os);
  				parent = color;
  				codeIndex++;
  				// Check code length
  				if(codeIndex > ((1<<codeLen)))
  			    {
                     if (codeLen == 12) 
  			       { 
  				       send_code_to_buffer(clearCode,os);
  				       init_encoder(bitsPerPixel);
  			       } else
  					   codeLen++;
  			    }
  			}
  		}
  		// Send the last color code to the buffer
  		send_code_to_buffer(parent,os);
  		// Send the endOfImage code to the buffer
  		send_code_to_buffer(endOfImage,os);
  		// Flush the last code buffer
  		flush_buf(os, bufIndex+1);
      }
  	
  	/**
  	 * This is intended to be called after writing all the frames if we write
  	 * an animated GIF frame by frame.
  	 * 
  	 * @param os OutputStream for the animated GIF
  	 * @throws Exception
  	 */
  	public void finishWrite(OutputStream os) throws Exception {	   	
      	os.write(IMAGE_TRAILER);
  		os.close();    	
  	}
      
      private void flush_buf(OutputStream os, int len) throws Exception {
  		os.write(len);
  		os.write(bytes_buf,0,len);
  		// Clear the bytes buffer
  		bufIndex = 0;
  		Arrays.fill(bytes_buf, 0, 0xff, (byte)0x00);
  	}
      
      /**
  	 * Retrieves RGB values from Raster. This seems to be the fastest way to get RGB values.
  	 *
  	 * TYPE_INT_RGB        = 1
  	 * TYPE_INT_ARGB       = 2
  	 * TYPE_INT_ARGB_PRE   = 3
  	 * TYPE_INT_BGR        = 4
  	 * TYPE_3BYTE_BGR      = 5
  	 * TYPE_4BYTE_ABGR     = 6
  	 * TYPE_4BYTE_ABGR_PRE = 7
  	 * TYPE_BYTE_GRAY      = 10
  	 * TYPE_BYTE_BINARY    = 12
  	 * TYPE_BYTE_INDEXED   = 13
  	 * TYPE_USHORT_GRAY    = 11
  	 * TYPE_USHORT_565_RGB = 8
  	 * TYPE_USHORT_555_RGB = 9
  	 * TYPE_CUSTOM         = 0.
  	 * 
  	 * @param image input BufferedImage 
  	 * @return integer array - default RGB color space representation
  	 */
  	private static int[] getRGB(BufferedImage image) {
  		// Get the BufferedImageType
  		int type = image.getType();
  		// Grab the internal data array
  		Raster raster = image.getRaster();
  		Object object = raster.getDataElements(0, 0, image.getWidth(), image.getHeight(), null);
  		// Determine the data transfer type
  		int transferType = raster.getTransferType();
  		// Get image dimension
  		int imageWidth = image.getWidth();
  		int imageHeight = image.getHeight();
  		int imageSize = imageWidth*imageHeight;
  		int[] rgbs = new int[imageSize];
  		// Branch by transfer type
  		switch(transferType) {
  			case DataBuffer.TYPE_INT:
  				rgbs = (int[])object;				
  				if(type == BufferedImage.TYPE_INT_ARGB_PRE) {										
  					for(int i = 0; i < imageSize; i++) {
  						float alpha = 255.0f/((rgbs[i]>>24)&0xff);
  						byte red = (byte)(((rgbs[i]>>16)&0xff)*alpha);
  						byte green = (byte)(((rgbs[i]>>8)&0xff)*alpha);
  						byte blue = (byte)((rgbs[i]&0xff)*alpha);
  						rgbs[i] = (rgbs[i]&0xff000000)|((red&0xff)<<16)|((green&0xff)<<8)|(blue&0xff);						 
  					}
  				} else if(type == BufferedImage.TYPE_INT_BGR) { // Convert BGR to RGB
  					for(int i = 0; i < rgbs.length; i++) {
  						int blue = (rgbs[i]>>16)&0xff;
  						int green = (rgbs[i]>>8) & 0xff;
  						int red = rgbs[i]&0xff;
  						rgbs[i] = 0xff000000|(red << 16)|(green << 8)|blue;
  					}
  				} else if(type == BufferedImage.TYPE_INT_RGB) {
  					for(int i = 0; i < rgbs.length; i++)
  						rgbs[i] = 0xff000000|rgbs[i];
  				} else if(type == BufferedImage.TYPE_INT_ARGB) {
  					;  // Do nothing
  				} else {
  					return image.getRGB(0, 0, imageWidth, imageHeight, rgbs, 0, imageWidth);
  				}
  				return rgbs;
  			case DataBuffer.TYPE_BYTE:
  				byte[] bpixels = (byte[])object;
  				// BufferedImage.getRGB() seems a bit faster in this case for small images.
  				if(type == BufferedImage.TYPE_BYTE_INDEXED || type == BufferedImage.TYPE_BYTE_BINARY) {
  					IndexColorModel indexModel = (IndexColorModel)image.getColorModel();
  					int mapSize = indexModel.getMapSize();
  					byte[] reds = new byte[mapSize];
  					byte[] greens = new byte[mapSize];
  					byte[] blues = new byte[mapSize];
  					byte[] alphas = new byte[mapSize];
  					int[] palette = new int[mapSize];
  					indexModel.getReds(reds); 
  					indexModel.getGreens(greens);
  					indexModel.getBlues(blues);
  					indexModel.getAlphas(alphas);
  					for(int i = 0; i < mapSize; i++)
  						palette[i] = (alphas[i]&0xff)<<24|(reds[i]&0xff)<<16|(greens[i]&0xff)<<8|blues[i]&0xff;
  					for(int i = 0; i < imageSize; i++)
  						rgbs[i] = palette[bpixels[i]&0xff];
  				} else if(type == BufferedImage.TYPE_4BYTE_ABGR) {
  					for(int i = 0, index = 0; i < imageSize; i++)
  						rgbs[i] = (((bpixels[index++]&0xff)<<16)|((bpixels[index++]&0xff)<<8)|(bpixels[index++]&0xff)|((bpixels[index++]&0xff)<<24));
  				} else if(type == BufferedImage.TYPE_3BYTE_BGR) {
  					for(int i = 0, index = 0; i < imageSize; i++)
  						rgbs[i] = ((0xff000000)|((bpixels[index++]&0xff)<<16)|((bpixels[index++]&0xff)<<8)|(bpixels[index++]&0xff));
  				} else if(type == BufferedImage.TYPE_4BYTE_ABGR_PRE) {				
  					for(int i = 0, index = 0; i < imageSize; i++, index += 4) {
  						float alpha = 255.0f*(bpixels[index+3]&0xff);
  						byte blue = (byte)((bpixels[index+2]&0xff)*alpha);
  						byte green = (byte)((bpixels[index+1]&0xff)*alpha);
  						byte red = (byte)((bpixels[index]&0xff)*alpha);
  						rgbs[i] =  (bpixels[index+3]&0xff000000)|((red&0xff)<<16)|((green&0xff)<<8)|(blue&0xff);						 
  					}
  				} else if(type == BufferedImage.TYPE_BYTE_GRAY) {
  					for(int i = 0; i < imageSize; i++)
  						rgbs[i] = (0xff000000)|((bpixels[i]&0xff)<<16)|((bpixels[i]&0xff)<<8)|(bpixels[i]&0xff);						 
  				} else {
  					return image.getRGB(0, 0, imageWidth, imageHeight, rgbs, 0, imageWidth);
  				}
  				return rgbs;
  			case DataBuffer.TYPE_USHORT:
  				short[] spixels = (short[])object;
  				if(type == BufferedImage.TYPE_USHORT_GRAY) {
  					for(int i = 0; i < imageSize; i++) {
  						int gray = ((spixels[i]>>8)&0xff);
  						rgbs[i] = (0xff000000)|(gray<<16)|(gray<<8)|gray;
  					}
  				} else if(type == BufferedImage.TYPE_USHORT_565_RGB) {
  					for(int i = 0; i < imageSize; i++) {
  						int red = ((spixels[i]>>11)&0x1f);
  						int green = ((spixels[i]>>5)&0x3f);
  						int blue = (spixels[i]&0x1f);
  						rgbs[i] = (0xff000000)|(red<<19)|(green<<10)|(blue<<3);
  					}
  				} else if(type == BufferedImage.TYPE_USHORT_555_RGB) {
  					for(int i = 0; i < imageSize; i++) {
  						int red = ((spixels[i]>>>10)&0x1f);
  						int green = ((spixels[i]>>>5)&0x1f);
  						int blue = (spixels[i]&0x1f);
  						rgbs[i] = (0xff000000)|(red<<19)|(green<<11)|(blue<<3);
  					}
  				} else {
  					return image.getRGB(0, 0, imageWidth, imageHeight, rgbs, 0, imageWidth);
  				}		
  				return rgbs;
  			default:
  				return image.getRGB(0, 0, imageWidth, imageHeight, rgbs, 0, imageWidth);
  		}
  	}
      
      private void init_encoder(int bitsPerPixel ) {
  		clearCode = 1 << bitsPerPixel;
  	    endOfImage = clearCode + 1;
    	    codeLen = bitsPerPixel + 1;
  	    codeIndex = endOfImage + 1;
  	    // Reset arrays
  	    Arrays.fill(child, 0);
  		Arrays.fill(siblings, 0);
  		Arrays.fill(suffix, 0);
      }
      
      /**
       * This is intended to be called first when writing an animated GIF
       * frame by frame.
       * 
       * @param os OutputStream for the animated GIF
       * @param logicalScreenWidth width of the logical screen. If it is less than
       *        or equal zero, it will be determined from the first frame
       * @param logicalScreenHeight height of the logical screen. If it is less than
       *        or equal zero, it will be determined from the first frame
       * @throws Exception
       */
      public void prepareForWrite(OutputStream os, int logicalScreenWidth, int logicalScreenHeight) throws Exception {
      	// Header first
      	writeHeader(os, true);
      	this.logicalScreenWidth = logicalScreenWidth;
      	this.logicalScreenHeight = logicalScreenHeight;
      	// We are going to write animated GIF, so enable animated flag
      	animated = true;
      }
      
      // Translate codes into bytes
      private void send_code_to_buffer(int code, OutputStream os)throws Exception	{
  		int temp = codeLen;
  		// Shift the code to the left of the last byte in bytes_buf
          bytes_buf[bufIndex] |= ((code&MASK[empty_bits])<<(8-empty_bits));
  		code >>= empty_bits;
          temp -= empty_bits;
          // If the code is longer than the empty_bits
  		while (temp > 0)
  		{
  			if ( ++bufIndex >= 0xff)
  			{
  				flush_buf(os,0xff);
  			}
  			bytes_buf[bufIndex] |= (code&0xff);
  			code >>= 8;
  			temp -= 8;
  		}
  		empty_bits = -temp;
  	}
      
      public void setLoopCount(int loopCount) {
      	this.loopCount = loopCount;
      }
  
      private void write(int[] pixels, int imageWidth, int imageHeight, OutputStream os) throws Exception {	
      	// Write GIF header
  		writeHeader(os, true);
  		// Set logical screen size
  		logicalScreenWidth = imageWidth;
  		logicalScreenHeight = imageHeight;
  		firstFrame = true;
  		// We only need to write one frame, so disable animated flag
      	animated = false;
  		// Write the image frame
  		writeFrame(pixels, imageWidth, imageHeight, 0, 0, 0, os);
  		// Make a clean end up of the image
  		os.write(IMAGE_TRAILER);
  		os.close();
      }
  
      /**
       * Writes an array of BufferedImage as an animated GIF
       * 
       * @param images an array of BufferedImage
       * @param delays delays in millisecond for each frame
       * @param os OutputStream for the animated GIF
       * @throws Exception
       */
      public void writeAnimatedGIF(BufferedImage[] images, int[] delays, OutputStream os) throws Exception {
      	// Header first
      	writeHeader(os, true);
      	
      	Dimension logicalScreenSize = getLogicalScreenSize(images);
      	
      	logicalScreenWidth = logicalScreenSize.width;
      	logicalScreenHeight = logicalScreenSize.height;
      	// We are going to write animated GIF, so enable animated flag
      	animated = true;
      	
      	for(int i = 0; i < images.length; i++) {
      		// Retrieve image dimension
  			int imageWidth = images[i].getWidth();
  			int imageHeight = images[i].getHeight();
  			writeFrame(getRGB(images[i]), imageWidth, imageHeight, 0, 0, delays[i], os);
      	}
      	
      	os.write(IMAGE_TRAILER);
  		os.close();    	
      }
      
      /**
       * Writes an array of GIFFrame as an animated GIF
       * 
       * @param frames an array of GIFFrame
       * @param os OutputStream for the animated GIF
       * @throws Exception
       */
      public void writeAnimatedGIF(GIFFrame[] frames, OutputStream os) throws Exception {
      	// Header first
      	writeHeader(os, true);
      	
      	Dimension logicalScreenSize = getLogicalScreenSize(frames);
      	
      	logicalScreenWidth = logicalScreenSize.width;
      	logicalScreenHeight = logicalScreenSize.height;
      	// We are going to write animated GIF, so enable animated flag
      	animated = true;
      	
      	for(int i = 0; i < frames.length; i++) {
      		// Retrieve image dimension
  			int imageWidth = frames[i].getFrameWidth();
  			int imageHeight = frames[i].getFrameHeight();
  			int[] pixels = getRGB(frames[i].getFrame());
  			if(frames[i].getTransparencyFlag() == GIFFrame.TRANSPARENCY_INDEX_SET && frames[i].getTransparentColor() != -1) {
  				int transColor = (frames[i].getTransparentColor() & 0x00ffffff);				
  				for(int j = pixels.length - 1; j > 0; j--) {
  					int pixel = (pixels[j] & 0x00ffffff);
  					if(pixel == transColor) pixels[j] = pixel; 
  				}
  			}
  			writeFrame(pixels, imageWidth, imageHeight, frames[i].getLeftPosition(), frames[i].getTopPosition(),
  					frames[i].getDelay(), frames[i].getDisposalMethod(), frames[i].getUserInputFlag(), os);
      	}
      	
      	os.write(IMAGE_TRAILER);
  		os.close();    	
      }
      
      /**
       * Writes a list of GIFFrame as an animated GIF
       * 
       * @param frames a list of GIFFrame
       * @param os OutputStream for the animated GIF
       * @throws Exception
       */
      public void writeAnimatedGIF(List<GIFFrame> frames, OutputStream os) throws Exception {
      	writeAnimatedGIF(frames.toArray(new GIFFrame[0]), os);
      }
      
      private void writeComment(OutputStream os, String comment) throws Exception {
      	os.write(EXTENSION_INTRODUCER);
  		os.write(COMMENT_EXTENSION_LABEL);
  		byte[] commentBytes = comment.getBytes();
  		int numBlocks = commentBytes.length/0xff;
  		int leftOver = commentBytes.length % 0xff;
  		int offset = 0;
  		if(numBlocks > 0) {
  			for(int i = 0; i < numBlocks; i++) {
  				os.write(0xff);
  				os.write(commentBytes, offset, 0xff);
  				offset += 0xff;
  			}
  		}
  		if(leftOver > 0) {
  			os.write(leftOver);
  			os.write(commentBytes, offset, leftOver);
  		}
  		os.write(0);
      }
      
      public void writeFrame(OutputStream os, GIFFrame frame) throws Exception {
      	// Retrieve image dimension
      	BufferedImage image = frame.getFrame();
      	int imageWidth = image.getWidth();
  		int imageHeight = image.getHeight();
  		int frameLeft = frame.getLeftPosition();
  		int frameTop = frame.getTopPosition();
  		// Determine the logical screen dimension
  		if(firstFrame) {
  			if(logicalScreenWidth <= 0)
  				logicalScreenWidth = imageWidth;
  			if(logicalScreenHeight <= 0)
  				logicalScreenHeight = imageHeight;
  		}
  		if(frameLeft >= logicalScreenWidth || frameTop >= logicalScreenHeight) return;
  		if((frameLeft + imageWidth) > logicalScreenWidth) imageWidth = logicalScreenWidth - frameLeft;
  		if((frameTop + imageHeight) > logicalScreenHeight) imageHeight = logicalScreenHeight - frameTop;
  		int[] pixels = getRGB(image.getSubimage(0, 0, imageWidth, imageHeight));
  		// Handle transparency color if explicitly set
      	if(frame.getTransparencyFlag() == GIFFrame.TRANSPARENCY_INDEX_SET && frame.getTransparentColor() != -1) {
  			int transColor = (frame.getTransparentColor() & 0x00ffffff);				
  			for(int j = pixels.length - 1; j > 0; j--) {
  				int pixel = (pixels[j] & 0x00ffffff);
  				if(pixel == transColor) pixels[j] = pixel; 
  			}
  		}    	
  		writeFrame(pixels, imageWidth, imageHeight, frame.getLeftPosition(), frame.getTopPosition(),
  				frame.getDelay(), frame.getDisposalMethod(), frame.getUserInputFlag(), os);
      }
      
      public void writeFrame(OutputStream os, BufferedImage frame) throws Exception {
      	writeFrame(os, frame, 100); // default delay is 100 milliseconds
      }
      
      public void writeFrame(OutputStream os, BufferedImage frame, int delay) throws Exception {
      	// Retrieve image dimension
  		int imageWidth = frame.getWidth();
  		int imageHeight = frame.getHeight();
  		// Determine the logical screen dimension
  		if(firstFrame) {
  			if(logicalScreenWidth <= 0)
  				logicalScreenWidth = imageWidth;
  			if(logicalScreenHeight <= 0)
  				logicalScreenHeight = imageHeight;
  		}
  		if(delay <= 0) delay = 100;
  		if(imageWidth > logicalScreenWidth) imageWidth = logicalScreenWidth;
  		if(imageHeight > logicalScreenHeight) imageHeight = logicalScreenHeight;
  		writeFrame(getRGB(frame.getSubimage(0, 0, imageWidth, imageHeight)), imageWidth, imageHeight, 0, 0, delay, os);
      }
  
  	private void writeFrame(int[] pixels, int imageWidth, int imageHeight, int imageLeftPosition, int imageTopPosition, int delay, int disposalMethod, int userInputFlag, OutputStream os) throws Exception {	
  		// Reset empty_bits
      	empty_bits = 0x08;
      	
      	int transparent_color = -1;
  		int[] colorInfo; 
  		
  		// Reduce colors, if the color depth is less than 8 bits, reduce colors
  		// to the actual bits needed, otherwise reduce to 8 bits.
  		byte[] newPixels = new byte[imageWidth*imageHeight];
  	    colorPalette = new int[256];
  	    
  	    colorInfo = checkColorDepth(pixels, newPixels, colorPalette);
  		
  	    if(colorInfo[0] > 0x08) {
  	    	bitsPerPixel = 8;
  	    	if(isApplyDither)
  	    		colorInfo = reduceColorsDiffusionDither(pixels, imageWidth, imageHeight, bitsPerPixel, newPixels, colorPalette);
  	    	else
  	    		colorInfo = reduceColors(pixels, bitsPerPixel, newPixels, colorPalette);
  	 	}
  	    
  	    bitsPerPixel = colorInfo[0];
  	    
  	    transparent_color = colorInfo[1];
  	    
  	    int num_of_color = 1<<bitsPerPixel;
  	    
  	    if(firstFrame) {
  	    	// Logical screen descriptor
  			byte  flags = (byte)0x88;//0b10001000 (having sorted global color map) - To be updated
  			byte  bgcolor = 0x00;// To be set
  			byte  aspectRatio = 0x00;			
  			int colorResolution = 0x07;
  			// Set GIF logical screen descriptor parameters
  			flags |= ((colorResolution<<4)|(bitsPerPixel - 1)); 			
  			if(transparent_color >= 0)
  				bgcolor = (byte)transparent_color;
  			// Write logical screen descriptor
  			writeLSD(os, (short)logicalScreenWidth, (short)logicalScreenHeight, flags, bgcolor, aspectRatio);
  			// Write the global colorPalette
  			writePalette(os, num_of_color);
  			writeComment(os, "Created by ICAFE - https://github.com/dragon66/icafe");
  			if(animated)// Write Netscape extension block
  				writeNetscapeApplicationBlock(os, loopCount);
  	    }		
  		
        	// Output the graphic control block
  	    writeGraphicControlBlock(os, delay, transparent_color, disposalMethod, userInputFlag);
          // Output image descriptor
          if(firstFrame) {
          	writeImageDescriptor(os, imageWidth, imageHeight, imageLeftPosition, imageTopPosition, -1);
  			firstFrame = false;
          } else {
          	writeImageDescriptor(os, imageWidth, imageHeight, imageLeftPosition, imageTopPosition, bitsPerPixel - 1);
          	// Write local colorPalette
          	writePalette(os, num_of_color);
          }
          // LZW encode the image
          encode(newPixels, os);
  		/** Write out a zero length data sub-block */
  		os.write(0x00);
  	}
  	
  	private void writeFrame(int[] pixels, int imageWidth, int imageHeight, int imageLeftPosition, int imageTopPosition, int delay, OutputStream os) throws Exception	{	
      	writeFrame(pixels, imageWidth, imageHeight, imageLeftPosition, imageTopPosition, delay, GIFFrame.DISPOSAL_RESTORE_TO_BACKGROUND, GIFFrame.USER_INPUT_NONE, os);
      }
  	
  	// Unit of delay is supposed to be in millisecond
      private void writeGraphicControlBlock(OutputStream os, int delay, int transparent_color, int disposalMethod, int userInputFlag) throws Exception {
      	// Scale delay
      	delay = Math.round(delay/10.0f);
      	
          byte[] buf = new byte[8];
  		buf[0] = EXTENSION_INTRODUCER; // Extension introducer
  		buf[1] = GRAPHIC_CONTROL_LABEL; // Graphic control label
  		buf[2] = 0x04; // Block size
  		// Add disposalMethod and userInputFlag
  		buf[3] |= (((disposalMethod&0x07) << 2)|((userInputFlag&0x01) << 1));
  		buf[4] = (byte)(delay&0xff);// Delay time
  		buf[5] = (byte)((delay>>8)&0xff);
  		buf[6] = (byte)transparent_color;
  		buf[7] = 0x00;
  		
  		if(transparent_color >= 0) // Add transparency indicator
  			buf[3] |= 0x01;
  		
  		os.write(buf, 0, 8);
  	}
  	
  	private void writeHeader(OutputStream os, boolean newFormat) throws IOException {
  		// 6 bytes: GIF signature (always "GIF") plus GIF version ("87a" or "89a")
  		if(newFormat)
  			os.write("GIF89a".getBytes());
  		else
  			os.write("GIF87a".getBytes());			
  	}
  	
      private void writeImageDescriptor(OutputStream os, int imageWidth, int imageHeight, int imageLeftPosition, int imageTopPosition, int colorTableSize) throws Exception {
  		byte imageDescriptor[] = new byte[10];
  		imageDescriptor[0] = IMAGE_SEPARATOR;// Image separator ","
  		imageDescriptor[1] = (byte)(imageLeftPosition&0xff);// Image left position
  		imageDescriptor[2] = (byte)((imageLeftPosition>>8)&0xff);
  		imageDescriptor[3] = (byte)(imageTopPosition&0xff);// Image top position
  		imageDescriptor[4] = (byte)((imageTopPosition>>8)&0xff);
          imageDescriptor[5] = (byte)(imageWidth&0xff);
  		imageDescriptor[6] = (byte)((imageWidth>>8)&0xff);
  		imageDescriptor[7] = (byte)(imageHeight&0xff);
  		imageDescriptor[8] = (byte)((imageHeight>>8)&0xff);
  		imageDescriptor[9] = (byte)0x20;//0b00100000 - Packed fields
  		
  		if(colorTableSize >= 0) // Local color table will follow
  			imageDescriptor[9] |= (1<<7|colorTableSize);
  		
  		os.write(imageDescriptor, 0, 10);
  	}
      
      // Write logical screen descriptor
  	private void writeLSD(OutputStream os, short screen_width, short screen_height, short flags, byte bgcolor, byte aspectRatio) throws IOException	{
  		byte[] descriptor = new byte[7]; 
  		// Screen_width
  	    descriptor[0] = (byte)(screen_width&0xff);
  	    descriptor[1] = (byte)((screen_width>>8)&0xff);
  	    // Screen_height
  	    descriptor[2] = (byte)(screen_height&0xff);
  	    descriptor[3] = (byte)((screen_height>>8)&0xff);
  		// Global flags
          descriptor[4] = (byte)(flags&0xff);
  		// Background color
          descriptor[5] = bgcolor;
  		// AspectRatio
  	    descriptor[6] = aspectRatio;
  	    
  	    os.write(descriptor);
  	}
  	
      private void writeNetscapeApplicationBlock(OutputStream os, int loopCounts) throws Exception {
      	byte[] buf = new byte[19];
   		buf[0] = EXTENSION_INTRODUCER; // Extension introducer
   		buf[1] = APPLICATION_EXTENSION_LABEL; // Application extension label
   		buf[2] = 0x0b; // Block size
   		buf[3] = 'N'; // Application Identifier (8 bytes)
   		buf[4] = 'E';
   		buf[5] = 'T';
   		buf[6] = 'S';
   		buf[7] = 'C';
   		buf[8] = 'A';
   		buf[9] = 'P';
   		buf[10]= 'E';
   		buf[11]= '2';// Application Authentication Code (3 bytes)
   		buf[12]= '.';
   		buf[13]= '0';
   		buf[14]= 0x03;
   		buf[15]= 0x01;
   		buf[16]= (byte)(loopCounts&0xff); // Loop counts
   		buf[17]= (byte)((loopCounts>>8)&0xff);
   		buf[18]= 0x00; // Block terminator 
   		
   		os.write(buf);
      }
      
      private void writePalette(OutputStream os, int num_of_color) throws Exception {
          int index = 0;
          byte colors[] = new byte[num_of_color*3];
          
          for (int i=0; i<num_of_color; i++)
  	    {
  		  colors[index++] = (byte)(((colorPalette[i]>>16)&0xff));
  		  colors[index++] = (byte)(((colorPalette[i]>>8)&0xff));
  		  colors[index++] = (byte)(colorPalette[i]&0xff);
  	    }
          
  	    os.write(colors, 0, num_of_color*3);
  	}
      
      private static int[] checkColorDepth(int[] rgbTriplets, byte[] newPixels, final int[] colorPalette) {
  		int index = 0;
  		int temp = 0;
  		int bitsPerPixel = 1;
  		int transparent_index = -1;// Transparent color index
  		int transparent_color = -1;// Transparent color
  		int[] colorInfo = new int[2];// Return value
  		
  		IntHashtable<Integer> rgbHash = new IntHashtable<Integer>(1023);
  				
  		for (int i = 0; i < rgbTriplets.length; i++) {
  			temp = (rgbTriplets[i]&0x00ffffff);
  
              if((rgbTriplets[i] >>> 24) < 0x80 ) { // Transparent
  				if (transparent_index < 0) {
  					transparent_index = index;
  				    transparent_color = temp;// Remember transparent color
  				}
  				temp = Integer.MAX_VALUE;
  			}	
  
              Integer entry = rgbHash.get(temp);
  			
  			if (entry!=null) {
  				newPixels[i] = entry.byteValue();
  			} else {
  				if(index > 0xff) {// More than 256 colors, have to reduce
  				 // Colors before saving as an indexed color image
  					colorInfo[0] = 24;
  					return colorInfo;
  				}
  				rgbHash.put(temp, index);
  				newPixels[i] = (byte)index;
  				colorPalette[index++] = ((0xff<<24)|temp);
  			}
  		}
  		if(transparent_index >= 0)// This line could be used to set a different background color
  			colorPalette[transparent_index] = transparent_color;
  		// Return the actual bits per pixel and the transparent color index if any
  		while ((1<<bitsPerPixel)<index)  bitsPerPixel++;
  		
  		colorInfo[0] = bitsPerPixel;
  		colorInfo[1] = transparent_index;
  
          return colorInfo;
  	}
      
      private static int[] reduceColorsDiffusionDither(int[] rgbTriplets, int width, int height, int colorDepth, byte[] newPixels, final int[] colorPalette)	{
  		if(colorDepth > 8 || colorDepth < 1) 
  			throw new IllegalArgumentException("Invalid color depth " + colorDepth);
  		int[] colorInfo = new int[2];
  		int colors = 0;
  		colors = new WuQuant(rgbTriplets, 1<<colorDepth).quantize(colorPalette, colorInfo);
  		// Call Floyd-Steinberg dither
  		dither_FloydSteinberg(rgbTriplets, width, height, newPixels, colors, colorPalette, colorInfo[1]);
  		// Return the actual bits per pixel and the transparent color index if any
  
  		return colorInfo;
  	}
      
   // Color quantization
   	private static int[] reduceColors(int[] rgbTriplets, int colorDepth, byte[] newPixels, final int[] colorPalette)	{
   		int[] colorInfo = new int[2];
   		new WuQuant(rgbTriplets, 1<<colorDepth).quantize(newPixels, colorPalette, colorInfo);
   		
   		return colorInfo;
   	}
      
      private static void dither_FloydSteinberg(int[] rgbTriplet, int width, int height, byte[] newPixels, int no_of_color, 
              int[] colorPalette, int transparent_index)
  	{
      	int index = 0, index1 = 0, err1, err2, err3, red, green, blue;
  	    // Define error arrays
  		// Errors for the current line
  		int[] tempErr;
  		int[] thisErrR = new int[width + 2];
  		int[] thisErrG = new int[width + 2];
  		int[] thisErrB = new int[width + 2];
          // Errors for the following line
  		int[] nextErrR = new int[width + 2];
  		int[] nextErrG = new int[width + 2];
  		int[] nextErrB = new int[width + 2];
  
  		InverseColorMap invMap;
  
  		invMap = new InverseColorMap();
  		invMap.createInverseMap(no_of_color, colorPalette);
  
  		for (int row = 0; row < height; row++) {
  			for (int col = 0; col < width; index1++, col++)	{
  				 // Transparent, no dither
  				if((rgbTriplet[index1] >>> 24) < 0x80 ) {
  					newPixels[index1] = (byte)transparent_index;
  					continue;
  		        }
  		
  				red = ((rgbTriplet[index1]&0xff0000)>>>16) + thisErrR[col + 1];
  				if (red > 255) red = 255;
  			    else if (red < 0) red = 0;
  	  		    
  				green = ((rgbTriplet[index1]&0x00ff00)>>>8) + thisErrG[col + 1];
  				if (green > 255) green = 255;
  			    else if (green < 0) green = 0;
  				
  				blue = (rgbTriplet[index1]&0x0000ff) + thisErrB[col + 1];
  				if (blue > 255) blue = 255;
  			    else if (blue < 0) blue = 0;
  
                  // Find the nearest color index
  			    index = invMap.getNearestColorIndex(red, green, blue);				
  				newPixels[index1] = (byte)index;// The colorPalette index for this pixel
  
  				// Find errors for different channels
  		        err1 = red   - ((colorPalette[index]>>16)&0xff);// Red channel
  				err2 = green - ((colorPalette[index]>>8)&0xff);// Green channel
  			    err3 = blue  -  (colorPalette[index]&0xff);// Blue channel
  			    // Diffuse error
  				// Red
                  thisErrR[col + 2] += ((err1*7)/16);
  				nextErrR[col    ] += ((err1*3)/16);
  				nextErrR[col + 1] += ((err1*5)/16);
  				nextErrR[col + 2] += ((err1)/16);
                  // Green
                  thisErrG[col + 2] += ((err2*7)/16);
  				nextErrG[col    ] += ((err2*3)/16);
  				nextErrG[col + 1] += ((err2*5)/16);
  				nextErrG[col + 2] += ((err2)/16);
  				// Blue
  				thisErrB[col + 2] += ((err3*7)/16);
  				nextErrB[col    ] += ((err3*3)/16);
  				nextErrB[col + 1] += ((err3*5)/16);
  				nextErrB[col + 2] += ((err3)/16);
  		    }
  			// We have finished one row, switch the error arrays
  			tempErr = thisErrR;
  			thisErrR = nextErrR;
              nextErrR = tempErr;
  
  			tempErr = thisErrG;
  			thisErrG = nextErrG;
  			nextErrG = tempErr;
  	
  	        tempErr = thisErrB;
  			thisErrB = nextErrB;
  			nextErrB = tempErr;
  			
              // Clear the error arrays
  			Arrays.fill(nextErrR, 0);
  			Arrays.fill(nextErrG, 0);
  			Arrays.fill(nextErrB, 0);
  		}
  	}
      
      public static class GIFFrame {
      	// Frame parameters
      	private BufferedImage frame;
      	private int leftPosition;
      	private int topPosition;
      	private int frameWidth;
      	private int frameHeight;
      	private int delay;
      	private int disposalMethod = DISPOSAL_UNSPECIFIED;
      	private int userInputFlag = USER_INPUT_NONE;
      	private int transparencyFlag = TRANSPARENCY_INDEX_NONE;
      	
      	// The transparent color value in RRGGBB format.
      	// The highest order byte has no effect.
      	private int transparentColor = TRANSPARENCY_COLOR_NONE; // Default no transparent color
      	
      	public static final int DISPOSAL_UNSPECIFIED = 0;
      	public static final int DISPOSAL_LEAVE_AS_IS = 1;
      	public static final int DISPOSAL_RESTORE_TO_BACKGROUND = 2;
      	public static final int DISPOSAL_RESTORE_TO_PREVIOUS = 3;
      	// Values between 4-7 inclusive
      	public static final int DISPOSAL_TO_BE_DEFINED = 7;
      	
      	public static final int USER_INPUT_NONE = 0;
      	public static final int USER_INPUT_EXPECTED = 1;
      	
      	public static final int TRANSPARENCY_INDEX_NONE = 0;
      	public static final int TRANSPARENCY_INDEX_SET = 1;
      	
      	public static final int TRANSPARENCY_COLOR_NONE = -1;
      	
      	public GIFFrame(BufferedImage frame) {
      		this(frame, 0, 0, 0, GIFFrame.DISPOSAL_UNSPECIFIED);
      	}
      	
      	public GIFFrame(BufferedImage frame, int delay) {
      		this(frame, 0, 0, delay, GIFFrame.DISPOSAL_UNSPECIFIED);
      	}
      	
      	public GIFFrame(BufferedImage frame, int delay, int disposalMethod) {
      		this(frame, 0, 0, delay, disposalMethod);
      	}
      	
      	public GIFFrame(BufferedImage frame, int leftPosition, int topPosition, int delay, int disposalMethod) {
      		this(frame, leftPosition, topPosition, delay, disposalMethod, USER_INPUT_NONE, TRANSPARENCY_INDEX_NONE, TRANSPARENCY_COLOR_NONE);
      	}
      	
      	public GIFFrame(BufferedImage frame, int leftPosition, int topPosition, int delay, int disposalMethod, int userInputFlag, int transparencyFlag, int transparentColor) {
      		if(frame == null) throw new IllegalArgumentException("Null input image");
      		if(disposalMethod < DISPOSAL_UNSPECIFIED || disposalMethod > DISPOSAL_TO_BE_DEFINED)
      			throw new IllegalArgumentException("Invalid disposal method: " + disposalMethod);
      		if(userInputFlag < USER_INPUT_NONE || userInputFlag > USER_INPUT_EXPECTED)
      			throw new IllegalArgumentException("Invalid user input flag: " + userInputFlag);
      		if(transparencyFlag < TRANSPARENCY_INDEX_NONE || transparencyFlag > TRANSPARENCY_INDEX_SET)
      			throw new IllegalArgumentException("Invalid transparency flag: " + transparencyFlag);
      		if(leftPosition < 0 || topPosition < 0)
      			throw new IllegalArgumentException("Negative coordinates for frame top-left position");
      		if(delay < 0) delay = 0;
      		this.frame = frame;
      		this.leftPosition = leftPosition;
      		this.topPosition = topPosition;	
      		this.delay = delay;
      		this.disposalMethod = disposalMethod;
      		this.userInputFlag = userInputFlag;
      		this.transparencyFlag = transparencyFlag;
      		this.frameWidth = frame.getWidth();
      		this.frameHeight = frame.getHeight();
      		this.transparentColor = transparentColor;
      	}
      	
      	public int getDelay() {
      		return delay;
      	}
      	
      	public int getDisposalMethod() {
      		return disposalMethod;
      	}
      	
      	public BufferedImage getFrame() {
      		return frame;
      	}
      	
      	public int getFrameHeight() {
      		return frameHeight;
      	}
      	
      	public int getFrameWidth() {
      		return frameWidth;
      	}
      	
      	public int getLeftPosition() {
      		return leftPosition;
      	}
      	
      	public int getTopPosition() {
      		return topPosition;
      	}
      	
      	public int getTransparentColor() {
      		return transparentColor;
      	}
      	
      	public int getTransparencyFlag() {
      		return transparencyFlag;
      	}
      	
      	public int getUserInputFlag() {
      		return userInputFlag;
      	}
       }
      
      /**
       * Java port of
       * C Implementation of Wu's Color Quantizer (v. 2)
       * (see Graphics Gems vol. II, pp. 126-133)
       * Author:	Xiaolin Wu
       * Dept. of Computer Science
       * Univ. of Western Ontario
       * London, Ontario N6A 5B7
       * wu@csd.uwo.ca
       * 
       * Algorithm: Greedy orthogonal bipartition of RGB space for variance
       * minimization aided by inclusion-exclusion tricks.
       * For speed no nearest neighbor search is done. Slightly
       * better performance can be expected by more sophisticated
       * but more expensive versions.
       * 
       * The author thanks Tom Lane at Tom_Lane@G.GP.CS.CMU.EDU for much of
       * additional documentation and a cure to a previous bug.
       * 
       * Free to distribute, comments and suggestions are appreciated.
       */
      private static class WuQuant {
      	private static final int MAXCOLOR =	256;
      	private static final int RED = 2;
      	private static final int GREEN = 1;
      	private static final int BLUE =	0;
      	
      	private static int QUANT_SIZE = 33;// quant size
  
      	private static final class Box {
      		int r0;	 /* min value, exclusive */
      		int r1;	 /* max value, inclusive */
      		int g0;  
      		int g1;  
      		int b0;  
      		int b1;
      		int vol;
      	};
      	
      	private int	size; /*image size*/
      	private int	lut_size; /*color look-up table size*/
      	private int qadd[];
      	private int pixels[];
      	private int transparent_color = -1;// Transparent color 
      	
          private float m2[][][] = new float[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE];
          private long wt[][][] = new long[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE];
          private long mr[][][] = new long[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE];
          private long mg[][][] = new long[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE];
          private long mb[][][] = new long[QUANT_SIZE][QUANT_SIZE][QUANT_SIZE];
             
          public WuQuant(int[] pixels, int lut_size) {
          	this.pixels = pixels;
          	this.size = pixels.length;
          	this.lut_size = lut_size;
          }
          
          public int quantize(final byte[] newPixels, final int[] lut, int[] colorInfo) {
              Box cube[] = new Box[MAXCOLOR];
              int lut_r, lut_g, lut_b;
              int tag[] = new int[QUANT_SIZE*QUANT_SIZE*QUANT_SIZE];
  
              int next, i, k;
              long weight;
              float vv[] = new float[MAXCOLOR], temp;
              
              Hist3d(wt, mr, mg, mb, m2);
              M3d(wt, mr, mg, mb, m2);
              
              for(i = 0; i < MAXCOLOR; i++)
           	   cube[i] = new Box();
              
              cube[0].r0 = cube[0].g0 = cube[0].b0 = 0;
              cube[0].r1 = cube[0].g1 = cube[0].b1 = QUANT_SIZE - 1;
              next = 0;
              
              if(transparent_color >= 0) lut_size--;
              
              for(i = 1; i < lut_size; ++i){
           	   if (Cut(cube[next], cube[i])) {
           		   /* volume test ensures we won't try to cut one-cell box */
           		   vv[next] = (cube[next].vol > 1) ? Var(cube[next]) : 0.0f;
           		   vv[i] = (cube[i].vol > 1) ? Var(cube[i]) : 0.0f;
           	   } else {
           		   vv[next] = 0.0f;   /* don't try to split this box again */
           		   i--;              /* didn't create box i */
           	   }
           	   next = 0; temp = vv[0];
           	   for(k = 1; k <= i; ++k)
           		   if (vv[k] > temp) {
           			   temp = vv[k]; next = k;
           		   }
           	   if (temp <= 0.0f) {
           		   k = i + 1;
           		   break;
           	   }
              }
          
              for(k = 0; k < lut_size; ++k){
           	   Mark(cube[k], k, tag);
           	   weight = Vol(cube[k], wt);
           	   if (weight > 0) {
           		   lut_r = (int)(Vol(cube[k], mr) / weight);
           		   lut_g = (int)(Vol(cube[k], mg) / weight);
           		   lut_b = (int)(Vol(cube[k], mb) / weight);
           		   lut[k] = (255 << 24) | (lut_r  << 16) | (lut_g << 8) | lut_b;
           	   }
           	   else	{
             		   lut[k] = 0;
           	   }
              }
  
              for(i = 0; i < size; ++i) {
           	   if((pixels[i] >>> 24) < 0x80)
           		   newPixels[i] = (byte)lut_size;
           	   else
           		   newPixels[i] = (byte)tag[qadd[i]];
              }
              
              int bitsPerPixel = 0;
              while ((1<<bitsPerPixel) < lut_size)  bitsPerPixel++;
              colorInfo[0] = bitsPerPixel;
              colorInfo[1] = -1;       
              
              if(transparent_color >= 0) {
            	  lut[lut_size] = transparent_color; // Set the transparent color
            	  colorInfo[1] = lut_size;
              }
              
              return lut_size;
          }
          
          public int quantize(final int[] lut, int[] colorInfo) {
             Box cube[] = new Box[MAXCOLOR];
             int lut_r, lut_g, lut_b;
           
             int next, i, k;
             long weight;
             float vv[] = new float[MAXCOLOR], temp;
             
             Hist3d(wt, mr, mg, mb, m2);
             M3d(wt, mr, mg, mb, m2);
             
             for(i = 0; i < MAXCOLOR; i++)
          	   cube[i] = new Box();
             
             cube[0].r0 = cube[0].g0 = cube[0].b0 = 0;
             cube[0].r1 = cube[0].g1 = cube[0].b1 = QUANT_SIZE - 1;
             next = 0;
             
             if(transparent_color >= 0) lut_size--;
             
             for(i = 1; i < lut_size; ++i){
          	   if (Cut(cube[next], cube[i])) {
          		   /* volume test ensures we won't try to cut one-cell box */
          		   vv[next] = (cube[next].vol > 1) ? Var(cube[next]) : 0.0f;
          		   vv[i] = (cube[i].vol > 1) ? Var(cube[i]) : 0.0f;
          	   } else {
          		   vv[next] = 0.0f;   /* don't try to split this box again */
          		   i--;              /* didn't create box i */
          	   }
          	   next = 0; temp = vv[0];
          	   for(k = 1; k <= i; ++k)
          		   if (vv[k] > temp) {
          			   temp = vv[k]; next = k;
          		   }
          	   if (temp <= 0.0f) {
          		   k = i + 1;
          		   break;
          	   }
             }
         
             for(k = 0; k < lut_size; ++k){
          	   weight = Vol(cube[k], wt);
          	   if (weight > 0) {
          		   lut_r = (int)(Vol(cube[k], mr) / weight);
          		   lut_g = (int)(Vol(cube[k], mg) / weight);
          		   lut_b = (int)(Vol(cube[k], mb) / weight);
          		   lut[k] = (255 << 24) | (lut_r  << 16) | (lut_g << 8) | lut_b;
          	   }
          	   else	{
            		   lut[k] = 0;		
          	   }
             }
             
             int bitsPerPixel = 0;
             while ((1<<bitsPerPixel) < lut_size)  bitsPerPixel++;
             colorInfo[0] = bitsPerPixel;
             colorInfo[1] = -1;
             
             if(transparent_color >= 0) {
            	  lut[lut_size] = transparent_color; // Set the transparent color
            	  colorInfo[1] = lut_size;
             }
             
             return lut_size;
          }
  
      	/* Histogram is in elements 1..HISTSIZE along each axis,
      	 * element 0 is for base or marginal value
      	 * NB: these must start out 0!
      	 */
      	private void Hist3d(long vwt[][][], long vmr[][][], long vmg[][][], long vmb[][][], float m2[][][]) {
      		/* build 3-D color histogram of counts, r/g/b, c^2 */
      		int r, g, b;
      		int	i, inr, ing, inb, table[] = new int[256];
      	
      		for(i = 0; i < 256; ++i) table[i]= i*i;
      		
      		qadd = new int[size];
      	
      		for(i = 0; i < size; ++i) {
      			int rgb = pixels[i];
      			if((rgb >>> 24) < 0x80) { // Transparent
      				if (transparent_color < 0)	// Find the transparent color	
      					transparent_color = rgb;
      			}
      			r = ((rgb >> 16)& 0xff);
      			g = ((rgb >> 8 )& 0xff);
      			b = ( rgb       & 0xff);
      			inr = (r >> 3) + 1; 
      			ing = (g >> 3) + 1; 
      			inb = (b >> 3) + 1; 
      			qadd[i] = (inr << 10) + (inr << 6) + inr + (ing << 5) + ing + inb;
      			/*[inr][ing][inb]*/
      			++vwt[inr][ing][inb];
      			vmr[inr][ing][inb] += r;
      			vmg[inr][ing][inb] += g;
      			vmb[inr][ing][inb] += b;
      		    m2[inr][ing][inb] += table[r] + table[g] + table[b];
      		}
      	}
      	
      	/* At conclusion of the histogram step, we can interpret
      	 *   wt[r][g][b] = sum over voxel of P(c)
      	 *   mr[r][g][b] = sum over voxel of r*P(c)  ,  similarly for mg, mb
      	 *   m2[r][g][b] = sum over voxel of c^2*P(c)
      	 * Actually each of these should be divided by 'size' to give the usual
      	 * interpretation of P() as ranging from 0 to 1, but we needn't do that here.
      	*/
  
      	/* We now convert histogram into moments so that we can rapidly calculate
      	 * the sums of the above quantities over any desired box.
      	 */
      	private void M3d(long vwt[][][], long vmr[][][], long vmg[][][], long vmb[][][], float m2[][][]) {
      		/* compute cumulative moments. */
      		int i, r, g, b;
      		int line, line_r, line_g, line_b;
      		int area[] = new int[QUANT_SIZE];
      		int area_r[] = new int[QUANT_SIZE];
      		int area_g[] = new int[QUANT_SIZE];
      		int area_b[] = new int[QUANT_SIZE];
      		float line2, area2[] = new float[QUANT_SIZE];
      	
      		for(r = 1; r < QUANT_SIZE; ++r) {
      			for(i = 0; i < QUANT_SIZE; ++i) 
      				area2[i] = area[i] = area_r[i] = area_g[i] = area_b[i] = 0;
      			for(g = 1; g < QUANT_SIZE; ++g) {
      				line2 = line = line_r = line_g = line_b = 0;
      				for(b = 1; b < QUANT_SIZE; ++b){
      					line   += vwt[r][g][b];
      					line_r += vmr[r][g][b]; 
      					line_g += vmg[r][g][b]; 
      					line_b += vmb[r][g][b];
      					line2  += m2[r][g][b];
      					
      					area[b] += line;
      					area_r[b] += line_r;
      					area_g[b] += line_g;
      					area_b[b] += line_b;
      					area2[b] += line2;
      					
      					vwt[r][g][b] = vwt[r-1][g][b] + area[b];
      					vmr[r][g][b] = vmr[r-1][g][b] + area_r[b];
      					vmg[r][g][b] = vmg[r-1][g][b] + area_g[b];
      					vmb[r][g][b] = vmb[r-1][g][b] + area_b[b];
      					m2[r][g][b]  = m2[r-1][g][b]  + area2[b];
      				}
      			}			
      		}
      	}
      	
      	private long Vol(Box cube, long mmt[][][]) {
      		/* Compute sum over a box of any given statistic */
      		return ( mmt[cube.r1][cube.g1][cube.b1] 
      				-mmt[cube.r1][cube.g1][cube.b0]
      				-mmt[cube.r1][cube.g0][cube.b1]
      				+mmt[cube.r1][cube.g0][cube.b0]
      				-mmt[cube.r0][cube.g1][cube.b1]
      				+mmt[cube.r0][cube.g1][cube.b0]
      				+mmt[cube.r0][cube.g0][cube.b1]
      				-mmt[cube.r0][cube.g0][cube.b0] );
      	}
      	
      	/* The next two routines allow a slightly more efficient calculation
      	* of Vol() for a proposed subbox of a given box.  The sum of Top()
      	* and Bottom() is the Vol() of a subbox split in the given direction
      	* and with the specified new upper bound.
      	*/
      	
      	private long Bottom(Box cube, int dir, long mmt[][][]) {
      		/* Compute part of Vol(cube, mmt) that doesn't depend on r1, g1, or b1 */
      		/* (depending on dir) */
      		switch(dir) {
      			case RED:
      				return( -mmt[cube.r0][cube.g1][cube.b1]
      						+mmt[cube.r0][cube.g1][cube.b0]
      						+mmt[cube.r0][cube.g0][cube.b1]
      						-mmt[cube.r0][cube.g0][cube.b0] );
      			case GREEN:
      				return( -mmt[cube.r1][cube.g0][cube.b1]
      						+mmt[cube.r1][cube.g0][cube.b0]
      						+mmt[cube.r0][cube.g0][cube.b1]
      						-mmt[cube.r0][cube.g0][cube.b0] );
      			case BLUE:
      				return( -mmt[cube.r1][cube.g1][cube.b0]
      						+mmt[cube.r1][cube.g0][cube.b0]
      						+mmt[cube.r0][cube.g1][cube.b0]
      						-mmt[cube.r0][cube.g0][cube.b0] );
      			default:
      				return 0;
      		}
      	}
  
      	private long Top(Box cube, int dir, int pos, long mmt[][][]) {
      		/* Compute remainder of Vol(cube, mmt), substituting pos for */
      		/* r1, g1, or b1 (depending on dir) */
      		switch(dir) {
      			case RED:
      				return( mmt[pos][cube.g1][cube.b1] 
      				   -mmt[pos][cube.g1][cube.b0]
      				   -mmt[pos][cube.g0][cube.b1]
      				   +mmt[pos][cube.g0][cube.b0] );
      			case GREEN:
      				return( mmt[cube.r1][pos][cube.b1] 
      				   -mmt[cube.r1][pos][cube.b0]
      				   -mmt[cube.r0][pos][cube.b1]
      				   +mmt[cube.r0][pos][cube.b0] );
      			case BLUE:
      				return( mmt[cube.r1][cube.g1][pos]
      				   -mmt[cube.r1][cube.g0][pos]
      				   -mmt[cube.r0][cube.g1][pos]
      				   +mmt[cube.r0][cube.g0][pos] );
      			default:
      				return 0;
      		}
      	}
      	
      	private float Var(Box cube) {
      		/* Compute the weighted variance of a box */
      		/* NB: as with the raw statistics, this is really the variance * size */
      		float dr, dg, db, xx;
      		dr = Vol(cube, mr); 
      		dg = Vol(cube, mg); 
      		db = Vol(cube, mb);
      		xx =  m2[cube.r1][cube.g1][cube.b1] 
      			  -m2[cube.r1][cube.g1][cube.b0]
      			  -m2[cube.r1][cube.g0][cube.b1]
      			  +m2[cube.r1][cube.g0][cube.b0]
      			  -m2[cube.r0][cube.g1][cube.b1]
      			  +m2[cube.r0][cube.g1][cube.b0]
      			  +m2[cube.r0][cube.g0][cube.b1]
      			  -m2[cube.r0][cube.g0][cube.b0];
      		return  xx - (dr*dr + dg*dg + db*db)/Vol(cube,wt);    
      	}
  
      	/* We want to minimize the sum of the variances of two subboxes.
      	* The sum(c^2) terms can be ignored since their sum over both subboxes
      	* is the same (the sum for the whole box) no matter where we split.
      	* The remaining terms have a minus sign in the variance formula,
      	* so we drop the minus sign and MAXIMIZE the sum of the two terms.
      	*/
      	private float Maximize(Box cube, int dir, int first, int last, int cut[],
      			long whole_r, long whole_g, long whole_b, long whole_w) {
      		long half_r, half_g, half_b, half_w;
      		long base_r, base_g, base_b, base_w;
      		int i;
      		float temp, max;
  
      		base_r = Bottom(cube, dir, mr);
      		base_g = Bottom(cube, dir, mg);
      		base_b = Bottom(cube, dir, mb);
      		base_w = Bottom(cube, dir, wt);
      		
      		max = 0.0f;
      		cut[0] = -1;
      	
      		for(i = first; i < last; ++i){
      			half_r = base_r + Top(cube, dir, i, mr);
      			half_g = base_g + Top(cube, dir, i, mg);
      			half_b = base_b + Top(cube, dir, i, mb);
      			half_w = base_w + Top(cube, dir, i, wt);
      			/* now half_x is sum over lower half of box, if split at i */
      			if (half_w == 0) /* subbox could be empty of pixels! */
      				continue;    /* never split into an empty box */
      			temp = (half_r*half_r + half_g*half_g +	half_b*half_b)/(float)half_w;
      			half_r = whole_r - half_r;
      			half_g = whole_g - half_g;
      			half_b = whole_b - half_b;
      			half_w = whole_w - half_w;
      			if (half_w == 0) /* subbox could be empty of pixels! */
      				continue; /* never split into an empty box */
      			temp += (half_r*half_r + half_g*half_g + half_b*half_b)/(float)half_w;
      			
      			if (temp > max) { max = temp; cut[0] = i;}
      		}
      		
      		return max;
      	}
      	
      	private boolean Cut(Box set1, Box set2) {
      		int dir;
      		int cutr[] = new int[1];
              int cutg[] = new int[1];
              int cutb[] = new int[1];
      		float maxr, maxg, maxb;
      		long whole_r, whole_g, whole_b, whole_w;
  
      		whole_r = Vol(set1, mr);
      		whole_g = Vol(set1, mg);
      		whole_b = Vol(set1, mb);
      		whole_w = Vol(set1, wt);
  
      		maxr = Maximize(set1, RED, set1.r0 + 1, set1.r1, cutr,
      				whole_r, whole_g, whole_b, whole_w);
      		maxg = Maximize(set1, GREEN, set1.g0 + 1, set1.g1, cutg,
      				whole_r, whole_g, whole_b, whole_w);
      		maxb = Maximize(set1, BLUE, set1.b0 + 1, set1.b1, cutb,
      				whole_r, whole_g, whole_b, whole_w);
  
      		if(maxr >= maxg && maxr >= maxb) {
      			dir = RED;
      			if (cutr[0] < 0) return false; /* can't split the box */
      		} else if(maxg >= maxr && maxg >= maxb) 
      			dir = GREEN;
      		else
      			dir = BLUE; 
  
      		set2.r1 = set1.r1;
      		set2.g1 = set1.g1;
      		set2.b1 = set1.b1;
  
      		switch (dir){
      			case RED:
      				set2.r0 = set1.r1 = cutr[0];
      				set2.g0 = set1.g0;
      				set2.b0 = set1.b0;
      				break;
      			case GREEN:
      				set2.g0 = set1.g1 = cutg[0];
      				set2.r0 = set1.r0;
      				set2.b0 = set1.b0;
      				break;
      			case BLUE:
      				set2.b0 = set1.b1 = cutb[0];
      				set2.r0 = set1.r0;
      				set2.g0 = set1.g0;
      				break;
      		}
      		set1.vol = (set1.r1 - set1.r0)*(set1.g1 - set1.g0)*(set1.b1 - set1.b0);
      		set2.vol = (set2.r1 - set2.r0)*(set2.g1 - set2.g0)*(set2.b1 - set2.b0);
      	
      		return true;  
      	}
      	
      	private void Mark(Box cube, int label, int tag[]) {
      		int r, g, b;
  
      		for(r = cube.r0 + 1; r <= cube.r1; ++r)
      			for(g = cube.g0 + 1; g <= cube.g1; ++g)
      				for(b = cube.b0 + 1; b <= cube.b1; ++b)
      					tag[(r<<10) + (r<<6) + r + (g<<5) + g + b] = label;
      	}
      }
      
      /**
       * A hash table using primitive integer keys. 
       *
       * Based on
       * QuadraticProbingHashTable.java
       * <p>
       * Probing table implementation of hash tables.
       * Note that all "matching" is based on the equals method.
       * 
       * @author Mark Allen Weiss
       */
      private static class IntHashtable<E> {
  
          /** The array of HashEntry. */
          private HashEntry<E> [ ] array;  // The array of HashEntry
          private int currentSize;  // The number of occupied cells
        
      	/**
           * Construct the hash table.
           * @param size the approximate initial size.
           */
          @SuppressWarnings("unchecked")
      	public IntHashtable(int size) {
              array = new HashEntry [size];
              makeEmpty( );
          }
  
          /**
           * Insert into the hash table. If the item is
           * already present, do nothing.
           * @param key the item to insert.
           */
          public void put(int key, E value) {
              // Insert key as active
              int currentPos = locate( key );
              if( isActive( currentPos ) )
                  return;
  
              array[ currentPos ] = new HashEntry<E> ( key, value, true );
  
              // Rehash
              if( ++currentSize > array.length / 2 )
                  rehash( );
          }
  
          /**
           * Expand the hash table.
           */
          @SuppressWarnings("unchecked")
      	private void rehash( ) {
              HashEntry<E> [ ] oldArray = array;
  
              // Create a new double-sized, empty table
              array = new HashEntry [nextPrime( 2 * oldArray.length )];
              currentSize = 0;
  
              // Copy table over
              for( int i = 0; i < oldArray.length; i++ )
                  if( oldArray[i] != null && oldArray[i].isActive )
                      put( oldArray[i].key, oldArray[i].value );
  
              return;
          }
  
          /**
           * Method that performs quadratic probing resolution.
           * @param key the item to search for.
           * @return the index of the item.
           */
          private int locate(int key) {
              int collisionNum = 0;
  
      		// And with the largest positive integer
      		int currentPos = (key & 0x7FFFFFFF) % array.length;
  
              while( array[ currentPos ] != null &&
                      array[ currentPos ].key != key )
              {
                  currentPos += 2 * ++collisionNum - 1;  // Compute ith probe
                  if( currentPos >= array.length )       // Implement the mod
                    currentPos -= array.length;
              }
              return currentPos;
          }
  
         	/**
           * Find an item in the hash table.
           * @param key the item to search for.
           * @return the value of the matching item.
           */
          public E get(int key) {
              int currentPos = locate( key );
              return isActive( currentPos ) ? array[ currentPos ].value : null;
          }
  
          /**
           * Return true if currentPos exists and is active.
           * @param currentPos the result of a call to findPos.
           * @return true if currentPos is active.
           */
          private boolean isActive( int currentPos ) {
              return array[ currentPos ] != null && array[ currentPos ].isActive;
          }
  
          /**
           * Make the hash table logically empty.
           */
          public void makeEmpty( ) {
              currentSize = 0;
              for( int i = 0; i < array.length; i++ )
                  array[ i ] = null;
          }
          
          /**
           * Internal method to find a prime number at least as large as n.
           * @param n the starting number (must be positive).
           * @return a prime number larger than or equal to n.
           */
          private static int nextPrime(int n) {
              if( n % 2 == 0 )
                  n++;
  
              for( ; !isPrime( n ); n += 2 )
                  ;
  
              return n;
          }
  
          /**
           * Internal method to test if a number is prime.
           * Not an efficient algorithm.
           * @param n the number to test.
           * @return the result of the test.
           */
          private static boolean isPrime(int n) {
              if( n == 2 || n == 3 )
                  return true;
  
              if( n == 1 || n % 2 == 0 )
                  return false;
  
              for( int i = 3; i * i <= n; i += 2 )
                  if( n % i == 0 )
                      return false;
  
              return true;
          }
          
          // The basic entry stored in ProbingHashTable
          private static class HashEntry<V> {
             int key;         // the key
             V value;       // the value
             boolean  isActive;  // false if deleted
        
        	       @SuppressWarnings("unused")
             HashEntry(int k, V val) {
                 this( k, val, true );
             }
  
             HashEntry(int k, V val, boolean i) {
                 key = k;
      	       value = val;
                 isActive  = i;
             }
          }        
      }
      
      private static class InverseColorMap {
      	private int bitsReserved;// Number of bits used in color quantization.
      	private int bitsDiscarded;// Number of discarded bits
      	private int maxColorVal;// Maximum value for each quantized color
      	private int invMapLen;// Length of the inverse color map
      	// The inverse color map itself
      	private byte[] invColorMap;
      	
      	// Default constructor using 5 for quantization bits
      	public InverseColorMap() {
      		this(5);
      	}
      	
          // Constructor using bitsReserved bits for quantization
      	public InverseColorMap(int rbits) {
      		bitsReserved = rbits;
      		bitsDiscarded  = 8 - bitsReserved;
      		maxColorVal = 1 << bitsReserved;
      		invMapLen = maxColorVal * maxColorVal * maxColorVal;
              invColorMap = new byte[invMapLen];
      	}
      	
         	// Fetch the forward color map index for this RGB 
      	public int getNearestColorIndex(int red, int green, int blue) {
      		return invColorMap[(((red >> bitsDiscarded) << (bitsReserved<<1))) | 
      					 ((green >> bitsDiscarded) << bitsReserved) |
      					 (blue >> bitsDiscarded)]&0xff;
      	}
      	
         	/**
      	 * Create an inverse color map using the input forward RGB map.
      	 */
      	public void createInverseMap(int no_of_colors, int[] colorPalette) {   
      		int red, green, blue, r, g, b;
              int rdist, gdist, bdist, dist;
              int rinc, ginc, binc;
  
      		int x = (1 << bitsDiscarded);// Step size for each color
      		int xsqr = (1 << (bitsDiscarded + bitsDiscarded));
              int txsqr = xsqr + xsqr;
      		int buf_index;
  
              int[] dist_buf = new int[invMapLen];
      		
      		// Initialize the distance buffer array with the largest integer value
      		for (int i = invMapLen; --i >= 0;)
      			dist_buf[i] = 0x7FFFFFFF;
              // Now loop through all the colors in the color map
      		for (int i = 0; i < no_of_colors; i++)
      		{
      			red   = ((colorPalette[i]>>16)&0xff);
      			green = ((colorPalette[i]>>8)&0xff);
      			blue  = (colorPalette[i]&0xff);
      			/**
      			 * We start from the origin (0,0,0) of the quantized colors, calculate
      			 * the distance between the cell center of the quantized colors and
      			 * the current color map entry as follows:
      			 * (rcenter * x + x/2) - red, where rcenter is the center of the 
      			 * Quantized red color map entry which is 0 since we start from 0.
      			 */
      	        rdist = (x>>1) - red;// Red distance
      	        gdist = (x>>1) - green;// Green distance
      	        bdist = (x>>1) - blue;// Blue distance
      	        dist = rdist*rdist + gdist*gdist + bdist*bdist;//The modular
                  // The distance increment with each step value x
      	        rinc = txsqr - (red   << (bitsDiscarded + 1));
      	        ginc = txsqr - (green << (bitsDiscarded + 1));
                  binc = txsqr - (blue  << (bitsDiscarded + 1));
  
      			buf_index = 0;
      			// Loop through quantized RGB space
      			for (r = 0, rdist = dist; r < maxColorVal; rdist += rinc, rinc += txsqr, r++ )
      			{
      				for (g = 0, gdist = rdist; g < maxColorVal; gdist += ginc, ginc += txsqr, g++)
      				{
      					for (b = 0, bdist = gdist; b < maxColorVal; bdist += binc, binc += txsqr, buf_index++, b++)
      					{
      						if (bdist < dist_buf[buf_index])
      						{
      							dist_buf[buf_index] = bdist;
      							invColorMap[buf_index] = (byte)i;
      						}
      					}
      				}
      			}
      		}
      	}    	
      }
  }
  