/*	
 *	clipgif.c
 *
 *	GIF Decoder
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2009 Naoyuki Sawa
 *
 *	* Thu Apr 09 22:39:06 JST 2009 Naoyuki Sawa
 *	- 1st リリース。
 */
#include "clip.h"

/****************************************************************************
 *	
 ****************************************************************************/

void
gif_decode(const void* _p,
	void (*size_proc)(int w, int h, void* user_data),
	void (*draw_proc)(int i, int x, int y, int c, const unsigned char (*p)[3], void* user_data),
	void* user_data)
{
	const unsigned char* p = _p;
	int number_of_images = 0;
	int i;
	int len;
	int old_code;
	int new_code;
	int character;
	int Block_Size;
	int Packed_Fields;
	/* Logical Screen Descriptor */
	int Logical_Screen_Width;
	int Logical_Screen_Height;
	int Size_of_Global_Color_Table;
	//int Sort_Flag;
	//int Color_Resolution;
	int Global_Color_Table_Flag;
	//int Background_Color_Index;
	//int Pixel_Aspect_Ratio;
	const unsigned char (*Global_Color_Table)[3/*Red,Green,Blue*/];
	/* Graphic Control Extension */
	int Transparent_Color_Flag = 0; /* Graphic Control Extensionが無い場合は透過色無しとするために必要 */
	//int User_Input_Flag;
	//int Disposal_Method;
	//int Reserved;
	//int Delay_Time;
	int Transparent_Color_Index = 0; /* 警告抑制 */
	/* Image Descriptor */
	int Image_Left_Position;
	int Image_Top_Position;
	int Image_Width;
	int Image_Height;
	int Size_of_Local_Color_Table;
	//int Reserved;
	//int Sort_Flag;
	int Interlace_Flag;
	int Local_Color_Table_Flag;
	const unsigned char (*Local_Color_Table)[3/*Red,Green,Blue*/];
	/* Table Based Image Data */
	int LZW_Minimum_Code_Size;
	int Clear_code;
	int End_of_Information_code;
	/* Raster Data stream */
	int bit_pos;
	int bits_per_code;
	int next_available_compression_code;
	struct {
		unsigned short old_code[1 << 12]; /* +    0,8192 */
		unsigned char character[1 << 12]; /* + 8192,4096 */
	} *dictionary;                            /* =12288      */
	/* Interlaced Images */
	static const unsigned char interlace_pattern[/*Interlace_Pass*/][2] = {
		{ 1, 0 }, /* Image is not interlaced. */
		{ 8, 0 }, /* Group 1 : Every 8th. row, starting with row 0. (Pass 1) */
		{ 8, 4 }, /* Group 2 : Every 8th. row, starting with row 4. (Pass 2) */
		{ 4, 2 }, /* Group 3 : Every 4th. row, starting with row 2. (Pass 3) */
		{ 2, 1 }, /* Group 4 : Every 2nd. row, starting with row 1. (Pass 4) */
	};
	int Column_number;
	int Row_number;
	int Interlace_Pass;

	/* Header */
	if(memcmp(p + 0, "GIF", 3/*Signature*/)) {
		DIE();
	}
	//if(memcmp(p + 3, "87a", 3/*Version*/) && memcmp(p + 3, "89a", 3/*Version*/)) {
	//	DIE();
	//}
	p += 6/*Signature,Version*/;
	/* Logical Screen Descriptor */
	Logical_Screen_Width       = LEHALF(p + 0);
	Logical_Screen_Height      = LEHALF(p + 2);
	Packed_Fields              = LEBYTE(p + 4);
	Size_of_Global_Color_Table = (Packed_Fields >> 0) & 7;
	//Sort_Flag                = (Packed_Fields >> 3) & 1;
	//Color_Resolution         = (Packed_Fields >> 4) & 3;
	Global_Color_Table_Flag    = (Packed_Fields >> 7) & 1;
	//Background_Color_Index   = LEBYTE(p + 5);
	//Pixel_Aspect_Ratio       = LEBYTE(p + 6);
	p += 7/*Logical Screen Width,Logical Screen Height,Packed Fields,Background Color Index,Pixel Aspect Ratio*/;
	/* Global Color Table */
	if(Global_Color_Table_Flag) {
		Global_Color_Table = (const unsigned char (*)[3/*Red,Green,Blue*/])p;
		p += (1 << (Size_of_Global_Color_Table + 1)) * 3/*Red,Green,Blue*/;
	} else {
		Global_Color_Table = NULL; /* 警告抑制 */
	}
	if(size_proc) {
		size_proc(Logical_Screen_Width, Logical_Screen_Height, user_data);
	}
	if(draw_proc) {
		dictionary = malloc(sizeof dictionary[0]);
		if(!dictionary) {
			DIE();
		}
		do {
			switch(LEBYTE(p + 0)) {
			case 0x21/*Extension Introducer*/:
				switch(LEBYTE(p + 1)) {
				case 0xF9/*Graphic Control Label*/:
					/* Graphic Control Extension */
					p += 2/*Extension Introducer,Graphic Control Label*/;
					for(;;) {
						Block_Size = LEBYTE(p + 0);
						if(!Block_Size/*Block Terminator*/) {
							p += 1/*Block Size*/;
							break;
						}
						Packed_Fields           = LEBYTE(p + 1);
						Transparent_Color_Flag  = (Packed_Fields >> 0) & 1;
						//User_Input_Flag       = (Packed_Fields >> 1) & 1;
						//Disposal_Method       = (Packed_Fields >> 2) & 7;
						//Reserved              = (Packed_Fields >> 5) & 7;
						//Delay_Time            = LEHALF(p + 2);
						Transparent_Color_Index = LEBYTE(p + 4);
						p += Block_Size + 1/*Block Size*/;
					}
					break;
				default:
					/* Comment Extension */
					/* Plain Text Extension */
					/* Application Extension */
					p += 2/*Extension Introducer,Label*/;
					for(;;) {
						Block_Size = LEBYTE(p + 0);
						if(!Block_Size/*Block Terminator*/) {
							p += 1/*Block Size*/;
							break;
						}
						p += Block_Size + 1/*Block Size*/;
					}
					break;
				}
				break;
			case 0x2C/*Image Separator*/:
				/* Image Descriptor */
				Image_Left_Position       = LEHALF(p + 1);
				Image_Top_Position        = LEHALF(p + 3);
				Image_Width               = LEHALF(p + 5);
				Image_Height              = LEHALF(p + 7);
				Packed_Fields             = LEBYTE(p + 9);
				Size_of_Local_Color_Table = (Packed_Fields >> 0) & 7;
				//Reserved                = (Packed_Fields >> 3) & 3;
				//Sort_Flag               = (Packed_Fields >> 5) & 1;
				Interlace_Flag            = (Packed_Fields >> 6) & 1;
				Local_Color_Table_Flag    = (Packed_Fields >> 7) & 1;
				p += 10/*Image Separator,Image Left Position,Image Top Position,Image Width,Image Height,Packed Fields*/;
				/* Local Color Table */
				if(Local_Color_Table_Flag) {
					Local_Color_Table = (const unsigned char (*)[3/*Red,Green,Blue*/])p;
					p += (1 << (Size_of_Local_Color_Table + 1)) * 3/*Red,Green,Blue*/;
				} else {
					Local_Color_Table = NULL; /* 警告抑制 */
				}
				/* Table Based Image Data */
				LZW_Minimum_Code_Size = *p++;
				Clear_code = 1 << LZW_Minimum_Code_Size;
				End_of_Information_code = Clear_code + 1;
				for(character = 0; character < Clear_code; character++) {
					dictionary->character[character] = character;
				}
				/* Raster Data stream */
				bit_pos = 0;
				bits_per_code = LZW_Minimum_Code_Size + 1;
				next_available_compression_code = Clear_code + 2;
				old_code = -1;
				/* Interlaced Images */
				Column_number = 0;
				Row_number = 0;
				Interlace_Pass = Interlace_Flag;
				do {
					/* Variable-Length-Code LZW Compression */
					new_code = 0;
					for(i = 0; i < bits_per_code; i++) {
						if(!bit_pos) {
							Block_Size = LEBYTE(p + 0);
							if(!Block_Size/*Block Terminator*/) {
								DIE();
							}
							p += Block_Size + 1/*Block Size*/;
							bit_pos = -(Block_Size << 3);
						}
						new_code |= ((p[bit_pos >> 3] >> (bit_pos & 7)) & 1) << i;
						bit_pos++;
					}
					if(new_code == Clear_code) {
						bits_per_code = LZW_Minimum_Code_Size + 1;
						next_available_compression_code = Clear_code + 2;
						old_code = -1;
						continue;
					}
					if(new_code == End_of_Information_code) {
						break;
					}
					if(new_code < next_available_compression_code) {
						if(next_available_compression_code < 1 << 12 && old_code != -1) {
							for(character = new_code; character >= Clear_code; character = dictionary->old_code[character]) { /** no job **/ }
							dictionary->old_code[next_available_compression_code] = old_code;
							dictionary->character[next_available_compression_code] = character;
							next_available_compression_code++;
						} else {
							/** no job **/
						}
					} else if(new_code == next_available_compression_code) {
						if(next_available_compression_code < 1 << 12 && old_code != -1) {
							for(character = old_code; character >= Clear_code; character = dictionary->old_code[character]) { /** no job **/ }
							dictionary->old_code[next_available_compression_code] = old_code;
							dictionary->character[next_available_compression_code] = character;
							next_available_compression_code++;
						} else {
							DIE();
						}
					} else /*if(new_code > next_available_compression_code)*/ {
						DIE();
					}
					if(next_available_compression_code == 1 << bits_per_code && bits_per_code < 12) {
						bits_per_code++;
					}
					for(character = new_code, len = 1; character >= Clear_code; character = dictionary->old_code[character], len++) { /** no job **/ }
					do {
						for(character = new_code, i = 1; i < len; character = dictionary->old_code[character], i++) { /** no job **/ }
						if(Transparent_Color_Flag == 0 || Transparent_Color_Index != dictionary->character[character]) {
							int x = Image_Left_Position + Column_number;
							int y = Image_Top_Position + Row_number;
							if(x >= 0 && x <= Logical_Screen_Width - 1 && y >= 0 && y <= Logical_Screen_Height - 1) {
								draw_proc(number_of_images, x, y, dictionary->character[character],
									Local_Color_Table_Flag ? Local_Color_Table : Global_Color_Table_Flag ? Global_Color_Table : NULL,
									user_data);
							}
						}
						if(++Column_number == Image_Width) {
							Column_number = 0;
							Row_number += interlace_pattern[Interlace_Pass][0/*Every row*/];
							while(Row_number >= Image_Height && Interlace_Pass >= 1/*Group 1*/ && Interlace_Pass <= 3/*Group 3*/) {
								Interlace_Pass++;
								Row_number = interlace_pattern[Interlace_Pass][1/*starting with row*/];
							}
						}
					} while(--len);
					old_code = new_code;
				} while(Row_number < Image_Height);
				for(;;) {
					Block_Size = LEBYTE(p + 0);
					if(!Block_Size/*Block Terminator*/) {
						p += 1/*Block Size*/;
						break;
					}
					p += Block_Size + 1/*Block Size*/;
				}
				number_of_images++;
				break;
			default:
				DIE();
			}
		} while(LEBYTE(p + 0) != 0x3B/*GIF Trailer*/);
		free(dictionary);
	}
}