#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>

namespace GIF
{
#define EXTENSION_INTRODUCER 0x21
#define IMAGE_DESCRIPTOR 0x2C
#define TRAILER 0x3B

#define GRAPHIC_CONTROL 0xF9
#define APPLICATION_EXTENSION 0xFF
#define COMMENT_EXTENSION 0xFE
#define PLAINTEXT_EXTENSION 0x01

#define READ(dst, size)        \
    memcpy(dst, buffer, size); \
    buffer += size

        typedef struct
    {
        unsigned short width;
        unsigned short height;
        unsigned char fields;
        unsigned char background_color_index;
        unsigned char pixel_aspect_ratio;
    } screen_descriptor_t;

    typedef struct
    {
        unsigned char r;
        unsigned char g;
        unsigned char b;
    } rgb;

    typedef struct
    {
        unsigned short image_left_position;
        unsigned short image_top_position;
        unsigned short image_width;
        unsigned short image_height;
        unsigned char fields;
    } image_descriptor_t;

    typedef struct
    {
        unsigned char byte;
        int prev;
        int len;
    } dictionary_entry_t;

    typedef struct
    {
        unsigned char extension_code;
        unsigned char block_size;
    } extension_t;

    typedef struct
    {
        unsigned char fields;
        unsigned short delay_time;
        unsigned char transparent_color_index;
    } graphic_control_extension_t;

    typedef struct
    {
        unsigned char application_id[8];
        unsigned char version[3];
    } application_extension_t;

    typedef struct
    {
        unsigned short left;
        unsigned short top;
        unsigned short width;
        unsigned short height;
        unsigned char cell_width;
        unsigned char cell_height;
        unsigned char foreground_color;
        unsigned char background_color;
    } plaintext_extension_t;

    // static unsigned short width = 0;
    // static unsigned short height = 0;
    // static unsigned char* uncompressed_data = NULL;

    void uncompress(int code_length,
                    const unsigned char *input,
                    int input_length,
                    unsigned char *out)
    {
        // int maxbits;
        int i, bit;
        int code, prev = -1;
        dictionary_entry_t *dictionary;
        int dictionary_ind;
        unsigned int mask = 0x01;
        int reset_code_length;
        int clear_code; // This varies depending on code_length
        int stop_code;  // one more than clear code
        int match_len;

        clear_code = 1 << (code_length);
        stop_code = clear_code + 1;
        // To handle clear codes
        reset_code_length = code_length;

        // Create a dictionary large enough to hold "code_length" entries.
        // Once the dictionary overflows, code_length increases
        dictionary = (dictionary_entry_t *)
            malloc(sizeof(dictionary_entry_t) * (1 << (code_length + 1)));

        // Initialize the first 2^code_len entries of the dictionary with their
        // indices.  The rest of the entries will be built up dynamically.

        // Technically, it shouldn't be necessary to initialize the
        // dictionary.  The spec says that the encoder "should output a
        // clear code as the first code in the image data stream".  It doesn't
        // say must, though...
        for (dictionary_ind = 0;
             dictionary_ind < (1 << code_length);
             dictionary_ind++)
        {
            dictionary[dictionary_ind].byte = dictionary_ind;
            // XXX this only works because prev is a 32-bit int (> 12 bits)
            dictionary[dictionary_ind].prev = -1;
            dictionary[dictionary_ind].len = 1;
        }

        // 2^code_len + 1 is the special "end" code; don't give it an entry here
        dictionary_ind++;
        dictionary_ind++;

        // TODO verify that the very last byte is clear_code + 1
        while (input_length)
        {
            code = 0x0;
            // Always read one more bit than the code length
            for (i = 0; i < (code_length + 1); i++)
            {
                // This is different than in the file read example; that
                // was a call to "next_bit"
                bit = (*input & mask) ? 1 : 0;
                mask <<= 1;

                if (mask == 0x100)
                {
                    mask = 0x01;
                    input++;
                    input_length--;
                }

                code = code | (bit << i);
            }

            if (code == clear_code)
            {
                code_length = reset_code_length;
                dictionary = (dictionary_entry_t *)realloc(dictionary,
                                                           sizeof(dictionary_entry_t) * (1 << (code_length + 1)));

                for (dictionary_ind = 0;
                     dictionary_ind < (1 << code_length);
                     dictionary_ind++)
                {
                    dictionary[dictionary_ind].byte = dictionary_ind;
                    // XXX this only works because prev is a 32-bit int (> 12 bits)
                    dictionary[dictionary_ind].prev = -1;
                    dictionary[dictionary_ind].len = 1;
                }
                dictionary_ind++;
                dictionary_ind++;
                prev = -1;
                continue;
            }
            else if (code == stop_code)
            {
                /*if ( input_length > 1 )
                {
                    fprintf( stderr, "Malformed GIF (early stop code)\n" );
                    exit( 0 );
                }*/
                break;
            }

            // Update the dictionary with this character plus the _entry_
            // (character or string) that came before it
            if ((prev > -1) && (code_length < 12))
            {
                if (code > dictionary_ind)
                {
                    fprintf(stderr, "code = %.02x, but dictionary_ind = %.02x\n",
                            code, dictionary_ind);
                    exit(0);
                }

                // Special handling for KwKwK
                if (code == dictionary_ind)
                {
                    int ptr = prev;

                    while (dictionary[ptr].prev != -1)
                    {
                        ptr = dictionary[ptr].prev;
                    }
                    dictionary[dictionary_ind].byte = dictionary[ptr].byte;
                }
                else
                {
                    int ptr = code;
                    while (dictionary[ptr].prev != -1)
                    {
                        ptr = dictionary[ptr].prev;
                    }
                    dictionary[dictionary_ind].byte = dictionary[ptr].byte;
                }

                dictionary[dictionary_ind].prev = prev;

                dictionary[dictionary_ind].len = dictionary[prev].len + 1;

                dictionary_ind++;

                // GIF89a mandates that this stops at 12 bits
                if ((dictionary_ind == (1 << (code_length + 1))) &&
                    (code_length < 11))
                {
                    code_length++;

                    dictionary = (dictionary_entry_t *)realloc(dictionary,
                                                               sizeof(dictionary_entry_t) * (1 << (code_length + 1)));
                }
            }

            prev = code;

            // Now copy the dictionary entry backwards into "out"
            match_len = dictionary[code].len;
            while (code != -1)
            {
                out[dictionary[code].len - 1] = dictionary[code].byte;
                if (dictionary[code].prev == code)
                {
                    fprintf(stderr, "Internal error; self-reference.");
                    exit(0);
                }
                code = dictionary[code].prev;
            }

            out += match_len;
        }
    }

    static int read_sub_blocks(unsigned char *buffer, unsigned char **data)
    {
        int data_length;
        int index;
        unsigned char block_size;

        // Everything following are data sub-blocks, until a 0-sized block is
        // encountered.
        data_length = 0;
        *data = NULL;
        index = 0;

        while (1)
        {
            READ(&block_size, 1);

            if (block_size == 0) // end of sub-blocks
            {
                break;
            }

            data_length += block_size;
            *data = (unsigned char *)realloc(*data, data_length);

            // TODO this could be split across block size boundaries
            READ(*data + index, block_size);

            index += block_size;
        }

        return data_length;
    }

    unsigned char *process_image_descriptor(unsigned char *buffer,
                                            rgb *gct,
                                            int gct_size,
                                            int resolution_bits)
    {
        image_descriptor_t image_descriptor;
        int compressed_data_length;
        unsigned char *compressed_data = NULL;
        unsigned char lzw_code_size;
        int uncompressed_data_length = 0;
        unsigned char *uncompressed_data = NULL;

        // TODO there could actually be lots of these
        READ(&image_descriptor, 9);

        // TODO if LCT = true, read the LCT

        READ(&lzw_code_size, 1);

        compressed_data_length = read_sub_blocks(buffer, &compressed_data);

        //    width = image_descriptor.image_width;
        //    height = image_descriptor.image_height;
        uncompressed_data_length = image_descriptor.image_width *
                                   image_descriptor.image_height;
        uncompressed_data = (unsigned char *)malloc(uncompressed_data_length);

        uncompress(lzw_code_size, compressed_data, compressed_data_length,
                   uncompressed_data);

        if (compressed_data)
            free(compressed_data);

        // if ( uncompressed_data )
        //     free( uncompressed_data );

        return uncompressed_data;
    }

/**
 * @param gif_file the file descriptor of a file containing a
 *  GIF-encoded file.  This should point to the first byte in
 *  the file when invoked.
 */
#define rb (*(buffer++))

    uint32_t *LoadPalette(unsigned char *buffer)
    {
        unsigned char header[7];
        screen_descriptor_t screen_descriptor;
        // int color_resolution_bits;

        int global_color_table_size = 0; // number of entries in global_color_table
        uint32_t *global_color_table = NULL;

        READ(header, 6);
        READ(&screen_descriptor, 7);

        // color_resolution_bits = ((screen_descriptor.fields & 0x70) >> 4) + 1;
        global_color_table = (uint32_t *)calloc(1, 1024);

        if (screen_descriptor.fields & 0x80)
        {
            global_color_table_size = 1 << (((screen_descriptor.fields & 0x07) + 1));

            // global_color_table = (rgb *)malloc(3 * global_color_table_size);
            // READ(global_color_table, 3 * global_color_table_size);
            for (int i = 0; i < global_color_table_size; ++i)
            {
                global_color_table[i] = (0xFF << 24) + (buffer[0] << 16) + (buffer[1] << 8) + buffer[2];
                buffer += 3;
            }
        }
        return global_color_table;
    }

    static unsigned char *process_gif_stream(unsigned char *buffer, unsigned short *w, unsigned short *h)
    {
        unsigned char header[7];
        screen_descriptor_t screen_descriptor;
        int color_resolution_bits;

        int global_color_table_size = 0; // number of entries in global_color_table
        rgb *global_color_table = NULL;

        unsigned char block_type = 0x0;

        // A GIF file starts with a Header (section 17)
        READ(header, 6);
        header[6] = 0x0;

        // XXX there's another format, GIF87a, that you may still find
        // floating around.
        /*if ( strcmp( "GIF89a", (char*)header ) )
        {
            fprintf( stderr,
                    "Invalid GIF file (header is '%s', should be 'GIF89a')\n",
                    header );
            return NULL;
        }*/

        // Followed by a logical screen descriptor
        // Note that this works because GIFs specify little-endian order; on a
        // big-endian machine, the height & width would need to be reversed.

        // Can't use sizeof here since GCC does byte alignment;
        // sizeof( screen_descriptor_t ) = 8!
        READ(&screen_descriptor, 7);
        *w = screen_descriptor.width;
        *h = screen_descriptor.height;

        color_resolution_bits = ((screen_descriptor.fields & 0x70) >> 4) + 1;

        if (screen_descriptor.fields & 0x80)
        {
            // int i;
            //  If bit 7 is set, the next block is a global color table; read it
            global_color_table_size = 1 << (((screen_descriptor.fields & 0x07) + 1));

            global_color_table = (rgb *)malloc(3 * global_color_table_size);

            // XXX this could conceivably return a short count...
            READ(global_color_table, 3 * global_color_table_size);
        }

        while (block_type != TRAILER)
        {
            READ(&block_type, 1);

            unsigned char size;
            switch (block_type)
            {
            case IMAGE_DESCRIPTOR:
                return process_image_descriptor(buffer,
                                                global_color_table,
                                                global_color_table_size,
                                                color_resolution_bits);
                break;
            case EXTENSION_INTRODUCER:
                buffer++;
                size = *(buffer++);
                buffer += size;
                do
                {
                    size = *(buffer++);
                    buffer += size;
                } while (size != 0);

                /*if ( !process_extension( buffer ) )
                {
                    return NULL;
                }*/
                break;
            case TRAILER:
                break;
            default:
                fprintf(stderr, "Bailing on unrecognized block type %.02x\n",
                        block_type);
                return NULL;
            }
        }
        return NULL;
    }

    unsigned char *LoadGif(unsigned char *buffer, unsigned short *w, unsigned short *h)
    {
        return process_gif_stream(buffer, w, h);
    }

/*int main( int argc, char *argv[] )
{
    FILE* gif_file;
    
    if ( argc < 2 )
    {
        fprintf( stderr, "Usage: %s <path-to-gif-file>\n", argv[ 0 ] );
        exit( 0 );
    }
    
    gif_file = fopen( argv[ 1 ], "rb" );
    
    if ( gif_file == NULL )
    {
        fprintf( stderr, "Unable to open file '%s'", argv[ 1 ] );
        perror( ": " );
    }
    
    process_gif_stream( gif_file );
    
    fclose( gif_file );
}*/}