/*
 * @(#)GIFImageReader.java	1.44 03/12/19
 *
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package com.sun.imageio.plugins.gif;

import java.awt.Point;
import java.awt.Rectangle;
import java.awt.image.BufferedImage;
import java.awt.image.DataBuffer;
import java.awt.image.WritableRaster;
import java.io.BufferedInputStream;
import java.io.DataInputStream;
import java.io.EOFException;
import java.io.InputStream;
import java.io.IOException;
import java.nio.ByteOrder;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import javax.imageio.IIOException;
import javax.imageio.ImageReader;
import javax.imageio.ImageReadParam;
import javax.imageio.ImageTypeSpecifier;
import javax.imageio.metadata.IIOMetadata;
import javax.imageio.spi.ImageReaderSpi;
import javax.imageio.stream.ImageInputStream;

/**
 * @version 0.5
 */
public class GIFImageReader extends ImageReader {

    // The current ImageInputStream source.
    ImageInputStream stream = null;

    // Per-stream settings

    // True if the file header including stream metadata has been read.
    boolean gotHeader = false;
    
    // Global metadata, read once per input setting.
    GIFStreamMetadata streamMetadata = null;

    // The current image index
    int currIndex = -1;

    // Metadata for image at 'currIndex', or null.
    GIFImageMetadata imageMetadata = null;

    // A List of Longs indicating the stream positions of the
    // start of the metadata for each image.  Entries are added
    // as needed.
    List imageStartPosition = new ArrayList();

    // Length of metadata for image at 'currIndex', valid only if
    // imageMetadata != null.
    int imageMetadataLength;

    // The number of images in the stream, if known, otherwise -1.
    int numImages = -1;

    // Variables used by the LZW decoding process
    byte[] block = new byte[255];
    int blockLength = 0;
    int bitPos = 0;
    int nextByte = 0;
    int initCodeSize;
    int clearCode;
    int eofCode;

    // 32-bit lookahead buffer
    int next32Bits = 0;

    // Try if the end of the data blocks has been found,
    // and we are simply draining the 32-bit buffer
    boolean lastBlockFound = false;

    // The image to be written.
    BufferedImage theImage = null;

    // The image's tile.
    WritableRaster theTile = null;
    
    // The image dimensions (from the stream).
    int width = -1, height = -1;

    // The pixel currently being decoded (in the stream's coordinates).
    int streamX = -1, streamY = -1;

    // The number of rows decoded
    int rowsDone = 0;

    // The current interlace pass, starting with 0.
    int interlacePass = 0;

    // End per-stream settings

    // Constants used to control interlacing.
    static final int[] interlaceIncrement = { 8, 8, 4, 2, -1 };
    static final int[] interlaceOffset = { 0, 4, 2, 1, -1 };

    public GIFImageReader(ImageReaderSpi originatingProvider) {
        super(originatingProvider);
    }

    // Take input from an ImageInputStream
    public void setInput(Object input,
                         boolean seekForwardOnly,
                         boolean ignoreMetadata) {
        super.setInput(input, seekForwardOnly, ignoreMetadata);
        if (input != null) {
            if (!(input instanceof ImageInputStream)) {
                throw new IllegalArgumentException
                    ("input not an ImageInputStream!"); 
            }
            this.stream = (ImageInputStream)input;
        } else {
            this.stream = null;
        }
        
        // Clear all values based on the previous stream contents
        resetStreamSettings();
    }

    public int getNumImages(boolean allowSearch) throws IIOException {
        if (stream == null) {
            throw new IllegalStateException("Input not set!");
        }
        if (seekForwardOnly && allowSearch) {
            throw new IllegalStateException
                ("seekForwardOnly and allowSearch can't both be true!");
        }

        if (numImages > 0) {
            return numImages;
        }
        if (allowSearch) {
            this.numImages = locateImage(Integer.MAX_VALUE) + 1;
        }
        return numImages;
    }

    // Throw an IndexOutOfBoundsException if index < minIndex,
    // and bump minIndex if required.
    private void checkIndex(int imageIndex) {
        if (imageIndex < minIndex) {
            throw new IndexOutOfBoundsException("imageIndex < minIndex!");
        }
        if (seekForwardOnly) {
            minIndex = imageIndex;
        }
    }

    public int getWidth(int imageIndex) throws IIOException {
        checkIndex(imageIndex);

        int index = locateImage(imageIndex);
        if (index != imageIndex) {
            throw new IndexOutOfBoundsException();
        }
        readMetadata();
        return imageMetadata.imageWidth;
    }

    public int getHeight(int imageIndex) throws IIOException {
        checkIndex(imageIndex);

        int index = locateImage(imageIndex);
        if (index != imageIndex) {
            throw new IndexOutOfBoundsException();
        }
        readMetadata();
        return imageMetadata.imageHeight;
    }

    public Iterator getImageTypes(int imageIndex) throws IIOException {
        checkIndex(imageIndex);

        int index = locateImage(imageIndex);
        if (index != imageIndex) {
            throw new IndexOutOfBoundsException();
        }
        readMetadata();

        List l = new ArrayList(1);

        byte[] colorTable;
        if (imageMetadata.localColorTable != null) {
            colorTable = imageMetadata.localColorTable;
        } else {
            colorTable = streamMetadata.globalColorTable;
        }

        // Normalize color table length to 2^1, 2^2, 2^4, or 2^8
        int length = colorTable.length3;
        int bits;
        if (length == 2) {
            bits = 1;
        } else if (length == 4) {
            bits = 2;
        } else if (length == 8 || length == 16) {
            // Bump from 3 to 4 bits
            bits = 4;
        } else {
            // Bump to 8 bits
            bits = 8;
        }
        int lutLength = 1 << bits;
        byte[] r = new byte[lutLength];
        byte[] g = new byte[lutLength];
        byte[] b = new byte[lutLength];

        // Entries from length + 1 to lutLength - 1 will be 0
        int rgbIndex = 0;
        for (int i = 0; i < length; i++) {
            r[i] = colorTable[rgbIndex++];
            g[i] = colorTable[rgbIndex++];
            b[i] = colorTable[rgbIndex++];
        }

        byte[] a = null;
        if (imageMetadata.transparentColorFlag) {
            a = new byte[lutLength];
            Arrays.fill(a, (byte)255);
            
            // Some files erroneously have a transparent color index
            // of 255 even though there are fewer than 256 colors.
            int idx = Math.min(imageMetadata.transparentColorIndex,
                               lutLength - 1);
            a[idx] = (byte)0;
        }

        int[] bitsPerSample = new int[1];
        bitsPerSample[0] = bits;
        l.add(ImageTypeSpecifier.createIndexed(r, g, b, a, bits,
                                               DataBuffer.TYPE_BYTE));
        return l.iterator();
    }

    public ImageReadParam getDefaultReadParam() {
        return new ImageReadParam();
    }

    public IIOMetadata getStreamMetadata() throws IIOException {
        readHeader();
        return streamMetadata;
    }

    public IIOMetadata getImageMetadata(int imageIndex) throws IIOException {
        checkIndex(imageIndex);

        int index = locateImage(imageIndex);
        if (index != imageIndex) {
            throw new IndexOutOfBoundsException("Bad image index!");
        }
        readMetadata();
        return imageMetadata;
    }

    // BEGIN LZW STUFF

    private void initNext32Bits() {
        next32Bits = block[0] & 0xff;
        next32Bits |= (block[1] & 0xff) << 8;
        next32Bits |= (block[2] & 0xff) << 16;
        next32Bits |= block[3] << 24;
        nextByte = 4;
    }

    // Load a block (1-255 bytes) at a time, and maintain
    // a 32-bit lookahead buffer that is filled from the left
    // and extracted from the right.
    //
    // When the last block is found, we continue to 
    //
    private int getCode(int codeSize, int codeMask) throws IOException {
        if (bitPos + codeSize > 32) {
            return eofCode; // No more data available
        }

        int code = (next32Bits >> bitPos) & codeMask;
        bitPos += codeSize;

        // Shift in a byte of new data at a time
        while (bitPos >= 8 && !lastBlockFound) {
            next32Bits >>>= 8;
            bitPos -= 8;
            
            // Check if current block is out of bytes
            if (nextByte >= blockLength) {
                // Get next block size
                blockLength = stream.readUnsignedByte();
                if (blockLength == 0) {
                    lastBlockFound = true;
                    return code;
                } else {
                    int left = blockLength;
                    int off = 0;
                    while (left > 0) {
                        int nbytes = stream.read(block, off, left);
                        off += nbytes;
                        left -= nbytes;
                    }
                    nextByte = 0;
                }
            }

            next32Bits |= block[nextByte++] << 24;
        }

        return code;
    }

    public void initializeStringTable(int[] prefix,
                                      byte[] suffix,
                                      byte[] initial,
                                      int[] length) {
        int numEntries = 1 << initCodeSize;
  	for (int i = 0; i < numEntries; i++) {
            prefix[i] = -1;
            suffix[i] = (byte)i;
            initial[i] = (byte)i;
            length[i] = 1;
        }
        
        // Fill in the entire table for robustness against
        // out-of-sequence codes.
  	for (int i = numEntries; i < 4096; i++) {
            prefix[i] = -1;
            length[i] = 1;
        }
        
	// tableIndex = numEntries + 2;
        // codeSize = initCodeSize + 1;
        // codeMask = (1 << codeSize) - 1;
    }

    Rectangle sourceRegion;
    int sourceXSubsampling;
    int sourceYSubsampling;
    int sourceMinProgressivePass;
    int sourceMaxProgressivePass;

    Point destinationOffset;
    Rectangle destinationRegion;

    // Used only if IIOReadUpdateListeners are present
    int updateMinY;
    int updateYStep;

    boolean decodeThisRow = true;
    int destY = 0;

    byte[] rowBuf;

    private void outputRow() {
        // Clip against ImageReadParam
        int width = Math.min(sourceRegion.width,
                             destinationRegion.width*sourceXSubsampling);
        int destX = destinationRegion.x;

        if (sourceXSubsampling == 1) {
            theTile.setDataElements(destX, destY, width, 1, rowBuf);
        } else {
            for (int x = 0; x < width; x += sourceXSubsampling, destX++) {
                theTile.setSample(destX, destY, 0, rowBuf[x] & 0xff);
            }
        }

        // Update IIOReadUpdateListeners, if any
        if (updateListeners != null) {
            int[] bands = { 0 };
            // updateYStep will have been initialized if
            // updateListeners is non-null
            processImageUpdate(theImage,
                               destX, destY,
                               width, 1, 1, updateYStep,
                               bands);
        }
    }

    private void computeDecodeThisRow() {
        this.decodeThisRow =
            (destY < destinationRegion.y + destinationRegion.height) &&
            (streamY >= sourceRegion.y) &&
            (streamY < sourceRegion.y + sourceRegion.height) &&
            (((streamY - sourceRegion.y) % sourceYSubsampling) == 0);
    }

    private void outputPixels(byte[] string, int len) {
        if (interlacePass < sourceMinProgressivePass ||
            interlacePass > sourceMaxProgressivePass) {
            return;
        }

        for (int i = 0; i < len; i++) {
            if (streamX >= sourceRegion.x) {
                rowBuf[streamX - sourceRegion.x] = string[i];
            }

            // Process end-of-row
            ++streamX;
            if (streamX == width) {
                // Update IIOReadProgressListeners
                ++rowsDone;
                processImageProgress(100.0F*rowsDoneheight);

                if (decodeThisRow) {
                    outputRow();
                }
                
                streamX = 0;
                if (imageMetadata.interlaceFlag) {
                    streamY += interlaceIncrement[interlacePass];
                    if (streamY >= height) {
                        // Inform IIOReadUpdateListeners of end of pass
                        if (updateListeners != null) {
                            processPassComplete(theImage);
                        }

                        ++interlacePass;
                        if (interlacePass > sourceMaxProgressivePass) {
                            return;
                        }
                        streamY = interlaceOffset[interlacePass];
                        startPass(interlacePass);
                    }
                } else {
                    ++streamY;
                }
                
                // Determine whether pixels from this row will 
                // be written to the destination
                this.destY = destinationRegion.y +
                    (streamY - sourceRegion.y)/sourceYSubsampling;
                computeDecodeThisRow();
            }
        }
    }

    // END LZW STUFF
    
    private void readHeader() throws IIOException {
        if (gotHeader) {
            return;
        }
        if (stream == null) {
            throw new IllegalStateException("Input not set!");
        }

        // Create an object to store the stream metadata
        this.streamMetadata = new GIFStreamMetadata();

        try {
            stream.setByteOrder(ByteOrder.LITTLE_ENDIAN);
            
            byte[] signature = new byte[6];
            stream.readFully(signature);

            StringBuffer version = new StringBuffer(3);
            version.append((char)signature[3]);
            version.append((char)signature[4]);
            version.append((char)signature[5]);
            streamMetadata.version = version.toString();

            streamMetadata.logicalScreenWidth = stream.readUnsignedShort();
            streamMetadata.logicalScreenHeight = stream.readUnsignedShort();

            int packedFields = stream.readUnsignedByte();
            boolean globalColorTableFlag = (packedFields & 0x80) != 0;
            streamMetadata.colorResolution = ((packedFields >> 4) & 0x7) + 1;
            streamMetadata.sortFlag = (packedFields & 0x8) != 0;
            int numGCTEntries = 1 << ((packedFields & 0x7) + 1);

            streamMetadata.backgroundColorIndex = stream.readUnsignedByte();
            streamMetadata.pixelAspectRatio = stream.readUnsignedByte();

            if (globalColorTableFlag) {
                streamMetadata.globalColorTable = new byte[3*numGCTEntries];
                stream.readFully(streamMetadata.globalColorTable);
            } else {
                streamMetadata.globalColorTable = null;
            }

            // Found position of metadata for image 0
            imageStartPosition.add(new Long(stream.getStreamPosition()));
        } catch (IOException e) {
            throw new IIOException("I/O error reading header!", e);
        }

        gotHeader = true;
    }

    private boolean skipImage() throws IIOException {
        // Stream must be at the beginning of an image descriptor
        // upon exit 

        try {
            while (true) {
                int blockType = stream.readUnsignedByte();

                if (blockType == 0x2c) {
                    stream.skipBytes(8);

                    int packedFields = stream.readUnsignedByte();
                    if ((packedFields & 0x80) != 0) {
                        // Skip color table if any
                        int bits = (packedFields & 0x7) + 1;
                        stream.skipBytes(3*(1 << bits));
                    }

                    stream.skipBytes(1);
                    
                    int length = 0;
                    do {
                        length = stream.readUnsignedByte();
                        stream.skipBytes(length);
                    } while (length > 0);

                    return true;
                } else if (blockType == 0x3b) {
                    return false;
                } else if (blockType == 0x21) {
                    int label = stream.readUnsignedByte();

                    int length = 0;
                    do {
                        length = stream.readUnsignedByte();
                        stream.skipBytes(length);
                    } while (length > 0);
                } else if (blockType == 0x0) {
                    // EOF
                    return false;
                } else {
                    int length = 0;
                    do {
                        length = stream.readUnsignedByte();
                        stream.skipBytes(length);
                    } while (length > 0);
                }
            }
        } catch (EOFException e) {
            return false;
        } catch (IOException e) {
            throw new IIOException("I/O error locating image!", e);
        }
    }

    private int locateImage(int imageIndex) throws IIOException {
        readHeader();

        try {
            // Find closest known index
            int index = Math.min(imageIndex, imageStartPosition.size() - 1);
            
            // Seek to that position
            Long l = (Long)imageStartPosition.get(index);
            stream.seek(l.longValue());

            // Skip images until at desired index or last image found
            while (index < imageIndex) {
                if (!skipImage()) {
                    --index;
                    return index;
                }
                
                Long l1 = new Long(stream.getStreamPosition());                
                imageStartPosition.add(l1);
                ++index;
            }
        } catch (IOException e) {
            throw new IIOException("Couldn't seek!", e);
        }

        if (currIndex != imageIndex) {
            imageMetadata = null;
        }
        currIndex = imageIndex;
        return imageIndex;
    }

    // Read blocks of 1-255 bytes, stop at a 0-length block
    private byte[] concatenateBlocks() throws IOException {
        byte[] data = new byte[0];
        while (true) {
            int length = stream.readUnsignedByte();
            if (length == 0) {
                break;
            }
            byte[] newData = new byte[data.length + length];
            System.arraycopy(data, 0, newData, 0, data.length);
            stream.readFully(newData, data.length, length);
            data = newData;
        }

        return data;
    }

    // Stream must be positioned at start of metadata for 'currIndex'
    private void readMetadata() throws IIOException {
        if (stream == null) {
            throw new IllegalStateException("Input not set!");
        }

        try {
            // Create an object to store the image metadata
            this.imageMetadata = new GIFImageMetadata();
            
            long startPosition = stream.getStreamPosition();
            while (true) {
                int blockType = stream.readUnsignedByte();
                if (blockType == 0x2c) { // Image Descriptor
                    imageMetadata.imageLeftPosition =
                        stream.readUnsignedShort();
                    imageMetadata.imageTopPosition =
                        stream.readUnsignedShort();
                    imageMetadata.imageWidth = stream.readUnsignedShort();
                    imageMetadata.imageHeight = stream.readUnsignedShort();

                    int idPackedFields = stream.readUnsignedByte();
                    boolean localColorTableFlag =
                        (idPackedFields & 0x80) != 0;
                    imageMetadata.interlaceFlag = (idPackedFields & 0x40) != 0;
                    imageMetadata.sortFlag = (idPackedFields & 0x20) != 0;
                    int numLCTEntries = 1 << ((idPackedFields & 0x7) + 1);

                    if (localColorTableFlag) {
                        // Read color table if any
                        imageMetadata.localColorTable =
                            new byte[3*numLCTEntries];
                        stream.readFully(imageMetadata.localColorTable);
                    } else {
                        imageMetadata.localColorTable = null;
                    }

                    // Record length of this metadata block
                    this.imageMetadataLength =
                        (int)(stream.getStreamPosition() - startPosition);

                    // Now positioned at start of LZW-compressed pixels
                    return;
                } else if (blockType == 0x21) { // Extension block
                    int label = stream.readUnsignedByte();

                    if (label == 0xf9) { // Graphics Control Extension
                        int gceLength = stream.readUnsignedByte(); // 4
                        int gcePackedFields = stream.readUnsignedByte();
                        imageMetadata.disposalMethod =
                            (gcePackedFields >> 2) & 0x3;
                        imageMetadata.userInputFlag = 
                            (gcePackedFields & 0x2) != 0;
                        imageMetadata.transparentColorFlag = 
                            (gcePackedFields & 0x1) != 0;

                        imageMetadata.delayTime = stream.readUnsignedShort();
                        imageMetadata.transparentColorIndex 
                            = stream.readUnsignedByte();
                        
                        int terminator = stream.readUnsignedByte();
                    } else if (label == 0x1) { // Plain text extension 
                        int length = stream.readUnsignedByte();
                        imageMetadata.hasPlainTextExtension = true;
                        imageMetadata.textGridLeft =
                            stream.readUnsignedShort();
                        imageMetadata.textGridTop =
                            stream.readUnsignedShort();
                        imageMetadata.textGridWidth =
                            stream.readUnsignedShort();
                        imageMetadata.textGridHeight =
                            stream.readUnsignedShort();
                        imageMetadata.characterCellWidth =
                            stream.readUnsignedByte();
                        imageMetadata.characterCellHeight =
                            stream.readUnsignedByte();
                        imageMetadata.textForegroundColor =
                            stream.readUnsignedByte();
                        imageMetadata.textBackgroundColor =
                            stream.readUnsignedByte();
                        imageMetadata.text = concatenateBlocks();
                    } else if (label == 0xfe) { // Comment extension
                        byte[] comment = concatenateBlocks();
                        if (imageMetadata.comments == null) {
                            imageMetadata.comments = new ArrayList();
                        }
                        imageMetadata.comments.add(comment);
                    } else if (label == 0xff) { // Application extension
                        int blockSize = stream.readUnsignedByte();
                        byte[] applicationID = new byte[8];
                        stream.readFully(applicationID);
                        byte[] authCode = new byte[3];
                        stream.readFully(authCode);
                        byte[] applicationData = concatenateBlocks();

                        // Init lists if necessary
                        if (imageMetadata.applicationIDs == null) {
                            imageMetadata.applicationIDs = new ArrayList();
                            imageMetadata.authenticationCodes =
                                new ArrayList();
                            imageMetadata.applicationData = new ArrayList();
                        }
                        imageMetadata.applicationIDs.add(applicationID);
                        imageMetadata.authenticationCodes.add(authCode);
                        imageMetadata.applicationData.add(applicationData);
                    } else {
                        // Skip over unknown extension blocks
                        int length = 0;
                        do {
                            length = stream.readUnsignedByte();
                            stream.skipBytes(length);
                        } while (length > 0);
                    }
                } else if (blockType == 0x3b) { // Trailer
                    throw new IndexOutOfBoundsException
                        ("Attempt to read past end of image sequence!");
                } else {
                    throw new IIOException("Unexpected block type " +
                                           blockType + "!");
                }
            }
        } catch (IIOException iioe) {
            throw iioe;
        } catch (IOException ioe) {
            throw new IIOException("I/O error reading image metadata!", ioe);
        }
    }

    // Helper for protected computeUpdatedPixels method
    private static void computeUpdatedPixels(int sourceOffset,
                                             int sourceExtent,
                                             int destinationOffset,
                                             int dstMin,
                                             int dstMax,
                                             int sourceSubsampling,
                                             int passStart,
                                             int passExtent,
                                             int passPeriod,
                                             int[] vals,
                                             int offset) {

        // We need to satisfy the congruences:
        // dst = destinationOffset + (src - sourceOffset)/sourceSubsampling
        //
        // src - passStart == 0 (mod passPeriod)
        // src - sourceOffset == 0 (mod sourceSubsampling)
        //
        // subject to the inequalities:
        //
        // src >= passStart
        // src < passStart + passExtent
        // src >= sourceOffset
        // src < sourceOffset + sourceExtent
        // dst >= dstMin
        // dst <= dstmax
        //
        // where
        //
        // dst = destinationOffset + (src - sourceOffset)/sourceSubsampling
        //
        // For now we use a brute-force approach although we could
        // attempt to analyze the congruences.  If passPeriod and
        // sourceSubsamling are relatively prime, the period will be
        // their product.  If they share a common factor, either the
        // period will be equal to the larger value, or the sequences
        // will be completely disjoint, depending on the relationship
        // between passStart and sourceOffset.  Since we only have to do this
        // twice per image (once each for X and Y), it seems cheap enough
        // to do it the straightforward way.

        boolean gotPixel = false;
        int firstDst = -1;
        int secondDst = -1;
        int lastDst = -1;

        for (int i = 0; i < passExtent; i++) {
            int src = passStart + i*passPeriod;
            if (src < sourceOffset) {
                continue;
            }
            if ((src - sourceOffset) % sourceSubsampling != 0) {
                continue;
            }
            if (src >= sourceOffset + sourceExtent) {
                break;
            }

            int dst = destinationOffset +
                (src - sourceOffset)/sourceSubsampling;
            if (dst < dstMin) {
                continue;
            }
            if (dst > dstMax) {
                break;
            }

            if (!gotPixel) {
                firstDst = dst; // Record smallest valid pixel
                gotPixel = true;
            } else if (secondDst == -1) {
                secondDst = dst; // Record second smallest valid pixel
            }
            lastDst = dst; // Record largest valid pixel
        }

        vals[offset] = firstDst;

        // If we never saw a valid pixel, set width to 0
        if (!gotPixel) {
            vals[offset + 2] = 0;
        } else {
            vals[offset + 2] = lastDst - firstDst + 1;
        }

        // The period is given by the difference of any two adjacent pixels
        vals[offset + 4] = Math.max(secondDst - firstDst, 1);
    }

    /**
     * A utility method that computes the exact set of destination
     * pixels that will be written during a particular decoding pass.
     * The intent is to simplify the work done by readers in combining
     * the source region, source subsampling, and destination offset
     * information obtained from the <code>ImageReadParam</code> with
     * the offsets and periods of a progressive or interlaced decoding
     * pass.
     *
     * @param sourceRegion a <code>Rectangle</code> containing the
     * source region being read, offset by the source subsampling
     * offsets, and clipped against the source bounds, as returned by
     * the <code>getSourceRegion</code> method.
     * @param destinationOffset a <code>Point</code> containing the
     * coordinates of the upper-left pixel to be written in the
     * destination.
     * @param dstMinX the smallest X coordinate (inclusive) of the
     * destination <code>Raster</code>.
     * @param dstMinY the smallest Y coordinate (inclusive) of the
     * destination <code>Raster</code>.
     * @param dstMaxX the largest X coordinate (inclusive) of the destination
     * <code>Raster</code>.
     * @param dstMaxY the largest Y coordinate (inclusive) of the destination
     * <code>Raster</code>.
     * @param sourceXSubsampling the X subsampling factor.
     * @param sourceYSubsampling the Y subsampling factor.
     * @param passXStart the smallest source X coordinate (inclusive)
     * of the current progressive pass.
     * @param passYStart the smallest source Y coordinate (inclusive)
     * of the current progressive pass.
     * @param passWidth the width in pixels of the current progressive
     * pass.
     * @param passHeight the height in pixels of the current progressive
     * pass.
     * @param passPeriodX the X period (horizontal spacing between
     * pixels) of the current progressive pass.
     * @param passPeriodY the Y period (vertical spacing between
     * pixels) of the current progressive pass.
     *
     * @return an array of 6 <code>int</code>s containing the
     * destination min X, min Y, width, height, X period and Y period
     * of the region that will be updated.
     */
    private static int[] computeUpdatedPixels(Rectangle sourceRegion,
                                              Point destinationOffset,
                                              int dstMinX,
                                              int dstMinY,
                                              int dstMaxX,
                                              int dstMaxY,
                                              int sourceXSubsampling,
                                              int sourceYSubsampling,
                                              int passXStart,
                                              int passYStart,
                                              int passWidth,
                                              int passHeight,
                                              int passPeriodX,
                                              int passPeriodY) {
        int[] vals = new int[6];
        computeUpdatedPixels(sourceRegion.x, sourceRegion.width,
                             destinationOffset.x,
                             dstMinX, dstMaxX, sourceXSubsampling,
                             passXStart, passWidth, passPeriodX,
                             vals, 0);
        computeUpdatedPixels(sourceRegion.y, sourceRegion.height,
                             destinationOffset.y,
                             dstMinY, dstMaxY, sourceYSubsampling,
                             passYStart, passHeight, passPeriodY,
                             vals, 1);
        return vals;
    }

    private void startPass(int pass) {
        if (updateListeners == null) {
            return;
        }

        int y = 0;
        int yStep = 1;
        if (imageMetadata.interlaceFlag) {
            y = interlaceOffset[interlacePass];
            yStep = interlaceIncrement[interlacePass];
        }

        int[] vals =
            computeUpdatedPixels(sourceRegion,
                                 destinationOffset,
                                 destinationRegion.x, 
                                 destinationRegion.y,
                                 destinationRegion.x +
                                 destinationRegion.width - 1,
                                 destinationRegion.y +
                                 destinationRegion.height - 1,
                                 sourceXSubsampling,
                                 sourceYSubsampling,
                                 0,
                                 y,
                                 destinationRegion.width,
                                 (destinationRegion.height + yStep - 1)/yStep,
                                 1,
                                 yStep);

        // Initialized updateMinY and updateYStep
        this.updateMinY = vals[1];
        this.updateYStep = vals[5];

        // Inform IIOReadUpdateListeners of new pass
        int[] bands = { 0 };

        processPassStarted(theImage,
                           interlacePass,
                           sourceMinProgressivePass,
                           sourceMaxProgressivePass,
                           0,
                           updateMinY,
                           1,
                           updateYStep,
                           bands);
    }

    public BufferedImage read(int imageIndex, ImageReadParam param)
        throws IIOException {
        if (stream == null) {
            throw new IllegalStateException("Input not set!");
        }
        checkIndex(imageIndex);

        int index = locateImage(imageIndex);
        if (index != imageIndex) {
            throw new IndexOutOfBoundsException("imageIndex out of bounds!");
        }

        clearAbortRequest();
        readMetadata();

        // A null ImageReadParam means we use the default
        if (param == null) {
            param = getDefaultReadParam();
        }

        // Initialize the destination image
        Iterator imageTypes = getImageTypes(imageIndex);
        this.theImage = getDestination(param,
                                       imageTypes,
                                       imageMetadata.imageWidth,
                                       imageMetadata.imageHeight);
        this.theTile = theImage.getWritableTile(0, 0);
        this.width = imageMetadata.imageWidth;
        this.height = imageMetadata.imageHeight;
        this.streamX = 0;
        this.streamY = 0;
        this.rowsDone = 0;
        this.interlacePass = 0;

        // Get source region, taking subsampling offsets into account,
        // and clipping against the true source bounds
        
        this.sourceRegion = new Rectangle(0, 0, 0, 0);
        this.destinationRegion = new Rectangle(0, 0, 0, 0);
        computeRegions(param, width, height, theImage,
                       sourceRegion, destinationRegion);
        this.destinationOffset = new Point(destinationRegion.x,
                                           destinationRegion.y);

        this.sourceXSubsampling = param.getSourceXSubsampling();
        this.sourceYSubsampling = param.getSourceYSubsampling();
        this.sourceMinProgressivePass =
            Math.max(param.getSourceMinProgressivePass(), 0);
        this.sourceMaxProgressivePass =
            Math.min(param.getSourceMaxProgressivePass(), 3);

        this.destY = destinationRegion.y +
            (streamY - sourceRegion.y)/sourceYSubsampling;
        computeDecodeThisRow();

        // Inform IIOReadProgressListeners of start of image
        processImageStarted(imageIndex);
        startPass(0);

        this.rowBuf = new byte[width];

        try {
            // Read and decode the image data, fill in theImage
            this.initCodeSize = stream.readUnsignedByte();

            // Read first data block
            this.blockLength = stream.readUnsignedByte();
            int left = blockLength;
            int off = 0;
            while (left > 0) {
                int nbytes = stream.read(block, off, left);
                left -= nbytes;
                off += nbytes;
            }

            this.bitPos = 0;
            this.nextByte = 0;
            this.lastBlockFound = false;
            this.interlacePass = 0;

            // Init 32-bit buffer
            initNext32Bits();

            this.clearCode = 1 << initCodeSize;
            this.eofCode = clearCode + 1;

            int code, oldCode = 0;

            int[] prefix = new int[4096];
            byte[] suffix = new byte[4096];
            byte[] initial = new byte[4096];
            int[] length = new int[4096];
            byte[] string = new byte[4096];

            initializeStringTable(prefix, suffix, initial, length);
            int tableIndex = (1 << initCodeSize) + 2;
            int codeSize = initCodeSize + 1;
            int codeMask = (1 << codeSize) - 1;

            while (!abortRequested()) {
                code = getCode(codeSize, codeMask);

                if (code == clearCode) {
                    initializeStringTable(prefix, suffix, initial, length);
                    tableIndex = (1 << initCodeSize) + 2;
                    codeSize = initCodeSize + 1;
                    codeMask = (1 << codeSize) - 1;

                    code = getCode(codeSize, codeMask);
                    if (code == eofCode) {
                        // Inform IIOReadProgressListeners of end of image
                        processImageComplete();
                        return theImage;
                    }
                } else if (code == eofCode) {
                    // Inform IIOReadProgressListeners of end of image
                    processImageComplete();
                    return theImage;
                } else {
                    int newSuffixIndex;
                    if (code < tableIndex) {
                        newSuffixIndex = code;
                    } else { // code == tableIndex
                        newSuffixIndex = oldCode;
                        if (code != tableIndex) {
                            // warning - code out of sequence
                            // possibly data corruption
                            processWarningOccurred("Out-of-sequence code!");
                        }
                    }

                    int ti = tableIndex;
                    int oc = oldCode;

                    prefix[ti] = oc;
                    suffix[ti] = initial[newSuffixIndex];
                    initial[ti] = initial[oc];
                    length[ti] = length[oc] + 1;
                    
                    ++tableIndex;
                    if ((tableIndex == (1 << codeSize)) &&
                        (tableIndex < 4096)) {
                        ++codeSize;
                        codeMask = (1 << codeSize) - 1;
                    }
                }

                // Reverse code
                int c = code;
                int len = length[c];
                for (int i = len - 1; i >= 0; i--) {
                    string[i] = suffix[c];
                    c = prefix[c];
                }
                
                outputPixels(string, len);
                oldCode = code;
            }

            processReadAborted();
            return theImage;
        } catch (IOException e) {
            e.printStackTrace();
            throw new IIOException("I/O error reading image!", e);
        }
    }    
    
    /**
     * Remove all settings including global settings such as
     * <code>Locale</code>s and listeners, as well as stream settings.
     */
    public void reset() {
        super.reset();
        resetStreamSettings();
    }

    /**
     * Remove local settings based on parsing of a stream.
     */
    private void resetStreamSettings() {
        gotHeader = false;
        streamMetadata = null;
        currIndex = -1;
        imageMetadata = null;
        imageStartPosition = new ArrayList();
        numImages = -1;

        // No need to reinitialize 'block'
        blockLength = 0;
        bitPos = 0;
        nextByte = 0;

        next32Bits = 0;
        lastBlockFound = false;

        theImage = null;
        theTile = null;
        width = -1;
        height = -1;
        streamX = -1;
        streamY = -1;
        rowsDone = 0;
        interlacePass = 0;
    }
}