/*
 * This file was adapted from D J Hagberg's GifDecoder.java
 *
 * This software is copyrighted by D. J. Hagberg, Jr., and other parties.
 * The following terms apply to all files associated with the software
 * unless explicitly disclaimed in individual files.
 * 
 * The authors hereby grant permission to use, copy, modify, distribute,
 * and license this software and its documentation for any purpose, provided
 * that existing copyright notices are retained in all copies and that this
 * notice is included verbatim in any distributions. No written agreement,
 * license, or royalty fee is required for any of the authorized uses.
 * Modifications to this software may be copyrighted by their authors
 * and need not follow the licensing terms described here, provided that
 * the new terms are clearly indicated on the first page of each file where
 * they apply.
 * 
 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY
 * FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
 * DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
 * IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
 * NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
 * MODIFICATIONS.
 * 
 * GOVERNMENT USE: If you are acquiring this software on behalf of the
 * U.S. government, the Government shall have only "Restricted Rights"
 * in the software and related documentation as defined in the Federal 
 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
 * are acquiring the software on behalf of the Department of Defense, the
 * software shall be classified as "Commercial Computer Software" and the
 * Government shall have only "Restricted Rights" as defined in Clause
 * 252.227-7013 (c) (1) of DFARs.  Notwithstanding the foregoing, the
 * authors grant the U.S. Government and others acting in its behalf
 * permission to use and distribute the software in accordance with the
 * terms specified in this license.
 *
 */
package org.ibex.graphics;

import org.ibex.util.*;
import java.io.BufferedInputStream;
import java.io.InputStream;
import java.io.IOException;
import java.io.PrintWriter;

/** Converts an InputStream carrying a GIF image into an ARGB int[] */
public class GIF {

    // Public Methods /////////////////////////////////////////////////////////

    private GIF() { }

    private static Queue instances = new Queue(10);

    public static void load(InputStream is, Picture p) {
        GIF g = (GIF)instances.remove(false);
        if (g == null) g = new GIF();
        try {
            g._load(is, p);
        } catch (Exception e) {
            if (Log.on) Log.info(GIF.class, e);
            return;
        }
        // FIXME: must reset fields
        // if (instances.size() < 10) instances.append(g);
    }

    private void _load(InputStream is, Picture p) throws IOException {
        this.p = p;
        if (is instanceof BufferedInputStream) _in = (BufferedInputStream)is;
        else _in = new BufferedInputStream(is);
        decodeAsBufferedImage(0);
        p.isLoaded = true;
        p = null;
        _in = null;
    }


    /** Decode a particular frame from the GIF file. Frames must be decoded in order, starting with 0. */
    private void decodeAsBufferedImage(int page) throws IOException, IOException {

        // If the user requested a page already decoded, we cannot go back.
        if (page <= index ) return;

        // If we just started reading this stream, initialize the global info.
        if (index < 0 ) {
            if (!readIntoBuf(6) || _buf[0] != 'G' || _buf[1] != 'I' || _buf[2] != 'F' ||
                _buf[3] != '8' || !(_buf[4] == '7' || _buf[4] == '9') || _buf[5] != 'a')
                throw new IOException("Not a GIF8Xa file.");
            if (!readGlobalImageDescriptor()) throw new IOException("Unable to read GIF header.");
        }
        
        // Loop through the blocks in the image.
        int block_identifier;
        while (true) {
            if(!readIntoBuf(1)) throw new IOException("Unexpected EOF(1)");
            block_identifier = _buf[0];
            if (block_identifier == ';') throw new IOException("No image data");
            if (block_identifier == '!') {
                if (!readExtensionBlock()) throw new IOException("Unexpected EOF(2)");
                continue;
            }

            // not a valid start character -- ignore it.
            if (block_identifier != ',') continue;

            if (!readLocalImageDescriptor()) throw new IOException("Unexpected EOF(3)");
            p.data = new int[p.width * p.height];
            readImage();

            // If we did not decode the requested index, need to go on
            // to the next one (future implementations should consider
            // caching already-decoded images here to allow for random
            // access to animated GIF pages).
            index++;
            if (index < page) continue;
            
            // If we did decode the requested index, we can return.
            break;
        }
        
        // Return the image thus-far decoded
        return;
    }

    /** Actually read the image data */
    private void readImage() 
        throws IOException, IOException {
        int len = p.width;
        int rows = p.height;
        int initialCodeSize;
        int v;
        int xpos = 0, ypos = 0, pass = 0, i;
        int prefix[] = new int[(1 << MAX_LWZ_BITS)];
        int append[] = new int[(1 << MAX_LWZ_BITS)];
        int stack[] = new int[(1 << MAX_LWZ_BITS)*2];
        int top_idx;
        int codeSize, clearCode, inCode, endCode, oldCode, maxCode, code, firstCode;
        
        // Initialize the decoder
        if (!readIntoBuf(1)) throw new IOException("Unexpected EOF decoding image");
        initialCodeSize = _buf[0];

        // Look at the right color map, setting up transparency if called for.
        int[] cmap = global_color_map;
        if (hascmap) cmap = color_map;
        if (trans_idx >= 0) cmap[trans_idx] = 0x00000000;

        /* Initialize the decoder */
        /* Set values for "special" numbers:
         * clear code   reset the decoder
         * end code     stop decoding
         * code size    size of the next code to retrieve
         * max code     next available table position
         */
        clearCode   = 1 << initialCodeSize;
        endCode     = clearCode + 1;
        codeSize    = initialCodeSize + 1;
        maxCode     = clearCode + 2;
        oldCode     = -1;
        firstCode   = -1;
        
        for (i = 0; i < clearCode; i++) append[i] = i;
        top_idx = 0; // top of stack.
        
        bitsInWindow = 0;
        bytes = 0;
        window = 0L;
        done = false;
        c = -1;
        
        /* Read until we finish the image */
        ypos = 0;
        for (i = 0; i < rows; i++) {
            for (xpos = 0; xpos < len;) {
                
                if (top_idx == 0) {
                    /* Bummer -- our stack is empty.  Now we have to work! */
                    code = getCode(codeSize);
                    if (code < 0) return;
                    
                    if (code > maxCode || code == endCode) return;
                    if (code == clearCode) {
                        codeSize    = initialCodeSize + 1;
                        maxCode     = clearCode + 2;
                        oldCode     = -1;
                        continue;
                    }
                    
                    // Last pass reset the decoder, so the first code we
                    // see must be a singleton.  Seed the stack with it,
                    // and set up the old/first code pointers for
                    // insertion into the string table.  We can't just
                    // roll this into the clearCode test above, because
                    // at that point we have not yet read the next code.
                    if (oldCode == -1) {
                        stack[top_idx++] = append[code];
                        oldCode = code;
                        firstCode = code;
                        continue;
                    }
                    
                    inCode = code;

                    // maxCode is always one bigger than our
                    // highest assigned code.  If the code we see
                    // is equal to maxCode, then we are about to
                    // add a new string to the table. ???  
                    if (code == maxCode) {
                        stack[top_idx++] = firstCode;
                        code = oldCode;
                    }
                    
                    // Populate the stack by tracing the string in the
                    // string table from its tail to its head
                    while (code > clearCode) {
                        stack[top_idx++] = append[code];
                        code = prefix[code];
                    }
                    firstCode = append[code];
                    
                    // If there's no more room in our string table, quit.
                    // Otherwise, add a new string to the table
                    if (maxCode >= (1 << MAX_LWZ_BITS)) return;
                    
                    // Push the head of the string onto the stack
                    stack[top_idx++] = firstCode;
                    
                    // Add a new string to the string table
                    prefix[maxCode] = oldCode;
                    append[maxCode] = firstCode;
                    maxCode++;
                    
                    // maxCode tells us the maximum code value we can accept.
                    // If we see that we need more bits to represent it than
                    // we are requesting from the unpacker, we need to increase
                    // the number we ask for.
                    if ((maxCode >= (1 << codeSize)) && (maxCode < (1<<MAX_LWZ_BITS))) codeSize++;
                    oldCode = inCode;
                }
                
                // Pop the next color index off the stack
                v = stack[--top_idx];
                if (v < 0) return;
                
                // Finally, we can set a pixel!  Joy!
                p.data[xpos + ypos * p.width] = cmap[v];
                xpos++;
            }
            
            // If interlacing, the next ypos is not just +1
            if (interlaced) {
                ypos += _interlaceStep[pass];
                while (ypos >= rows) {
                    pass++;
                    if (pass > 3) return;
                    ypos = _interlaceStart[pass];
                }
            } else ypos++;
        }
        return;
    }

    /** Extract the next compression code from the file. */
    private int getCode(int code_size) throws IOException {
        int ret;
        
        while (bitsInWindow < code_size) {
            // Not enough bits in our window to cover the request
            if (done) return -1;
            
            if (bytes == 0) {
                // Not enough bytes in our buffer to add to the window
                bytes = getDataBlock();
                c = 0;
                if (bytes <= 0) {
                    done = true;
                    break;
                }
            }
            // Tack another byte onto the window, see if that's enough
            window += (_buf[c]) << bitsInWindow;
            ++c;
            bitsInWindow += 8;
            bytes--;
        }
        
        
        // The next code will always be the last code_size bits of the window
        ret = ((int)window) & ((1 << code_size) - 1);
        
        // Shift data in the window to put the next code at the end
        window >>= code_size;
        bitsInWindow -= code_size;
        return ret;
    }
    
    /** Read the global image descriptor and optional global color map. Sets global_* variables. */
    private boolean readGlobalImageDescriptor() throws IOException {
        int packed;
        int aspect; // we ignore this.
        int ofs;
        
        if (!readIntoBuf(7) ) return false;
        global_width     = _buf[0] | (_buf[1] << 8);
        global_height    = _buf[2] | (_buf[3] << 8);
        packed       = _buf[4];
        global_bgcolor   = _buf[5];
        aspect       = _buf[6];
        global_cmapsize  = 2 << (packed & 0x07);
        global_hascmap   = (packed & GLOBALCOLORMAP) == GLOBALCOLORMAP;
        global_color_map = null;
        
        // Read the color map, if we have one.
        if (global_hascmap) {
            if (!readColorMap(global_cmapsize,true)) {
                return false;
            }
        }
        
        return true;
    }
    
    /** Read a local image descriptor and optional local color map. */
    private boolean readLocalImageDescriptor() throws IOException {
        int packed;
        
        if (!readIntoBuf(9) ) return false;
        
        left       = _buf[0] | (_buf[1] << 8);
        top        = _buf[2] | (_buf[3] << 8);
        p.width      = _buf[4] | (_buf[5] << 8);
        p.height     = _buf[6] | (_buf[7] << 8);
        packed        = _buf[8];
        hascmap    = (packed & LOCALCOLORMAP) == LOCALCOLORMAP;
        cmapsize   = 2 << (packed & 0x07);
        interlaced = (packed & INTERLACE) == INTERLACE;
        color_map  = null;
        
        // Read the local color table, if there is one.
        return !(hascmap && !readColorMap(cmapsize,false));
    }

    /** Read a color map (global or local). */
    private boolean readColorMap(int nColors, boolean isGlobal)
        throws IOException {
        int[] map = new int[nColors];
        for( int i=0; i < nColors; ++i) {
            if (!readIntoBuf(3) ) return false;
            map[i] = (_buf[0] << 16) | (_buf[1] << 8) | _buf[2] | 0xFF000000;
        }
        if (isGlobal) global_color_map = map;
        else color_map = map;
        return true;
    }

    /** Read the contents of a GIF89a Graphical Extension Block. */
    private boolean readExtensionBlock() throws IOException {
        if (!readIntoBuf(1) ) return false;
        int label = _buf[0];
        int count = -1;
        switch (label) {
        case 0x01:      // Plain Text Extension
        case 0xff:      // Application Extension
        case 0xfe:      // Comment Extension
            break;
        case 0xf9:      // Graphic Control Extension
            count = getDataBlock();
            if (count < 0) return true;
            // Check for transparency setting.
            if ((_buf[0] & HASTRANSPARENCY) != 0) trans_idx = _buf[3];
            else trans_idx = -1;
        }
        do { count = getDataBlock(); } while (count > 0);
        return true;
    }

    /** Read a block of data from the GIF file. */
    private int getDataBlock() throws IOException {
        if (!readIntoBuf(1) ) return -1;
        int count = _buf[0];
        if (count != 0) if (!readIntoBuf(count) ) return -1;
        return count;
    }
    
    /** Read the indicated number of bytes into _buf, our instance-wide buffer. */
    private boolean readIntoBuf(int count) throws IOException {
        for(int i = 0; i < count; i++) if ((_buf[i] = _in.read()) == -1) return false;
        return true;
    }

    // Private Data //////////////////////////////////////////////////////////

    private Picture p;

    // State management stuff
    private int index = -1;
    private BufferedInputStream _in = null;
    private int[] _buf = new int[BUFSIZE];

    // Transparency settings
    private int trans_idx = -1;

    // Global image descriptor contents
    private int global_width = 0;
    private int global_height = 0;
    private int global_bgcolor = 0;
    private int global_cmapsize = 0;
    private boolean global_hascmap = false;
    private int[] global_color_map = null;

    // Local image descriptor contents
    private int left = 0;
    private int top = 0;
    private int cmapsize = 0;
    private boolean hascmap = false;
    private boolean interlaced = false;
    private int[] color_map = null;

    // Variables used in getCode(...) to track sliding bit-window.
    private int     bytes = 0;
    private boolean done;
    private int     c;
    private long    window;
    private int     bitsInWindow = 0;

    // Class-wide constants.
    private static final int INTERLACE      = 0x40;
    private static final int GLOBALCOLORMAP = 0x80;
    private static final int LOCALCOLORMAP  = 0x80;
    private static final int HASTRANSPARENCY    = 0x01;
    private static final int MAX_LWZ_BITS   = 12;
    private static final int BUFSIZE        = 280;
    private static final int[] _interlaceStep   = { 8, 8, 4, 2 };
    private static final int[] _interlaceStart  = { 0, 4, 2, 1 };
}