/**
 * GIFFile.cpp
 */

#include "GIFFile.h"
#include <assert.h>

const unsigned char GIFFile::nsBlock[] = {0x4e, 0x45, 0x54, 0x53, 0x43, 0x41, 0x50, 0x45, 0x32, 0x2e, 0x30 };

struct DecoderInfo {
	/**
	 * Indices used during decompression
	 */
	int dataBlockIndex;

	/**
	 * Fields used by getBits()
	 */
	int remainingBits;
	int currentBits;
	DataBlock* compressedData;
};

/**
 * 指定されたファイルからGIFFileインスタンスを構築する
 */
GIFFile::GIFFile(_TCHAR* filename) : valid(false),
									 parent(NULL),
									 globalPalette(NULL),
									 localPalette(NULL),
									 animationFrameCount(0),
									 animationFrames(NULL),
									 raster(NULL) {
	FILE* file = _tfopen(filename, _T("rb"));
	if (! file) {
		return;
	}
    // Validate the signature
	if(! readSignature(file)) {
		fclose(file);
		return;
	}
	char data[7];
	if (fread(data, 1, 7, file) != 7) {
		fclose(file);
		return;
	}

	this->globalWidth  = ((data[1] & 0xFF) << 8) | (data[0] & 0xFF);
	this->globalHeight = ((data[3] & 0xFF) << 8) | (data[2] & 0xFF);

	char flags = data[4];
	this->nColors = (1 << (( flags & 0x07) + 1));
	this->hasGlobalColorMap = ((flags & 0x80) != 0);

	this->bgIndex = data[5];

	if( this->hasGlobalColorMap ) {
		this->globalPalette = (unsigned char*) malloc(this->nColors * 3);
		if (! this->globalPalette) {
			fclose(file);
			return;
		}
		if (fread(globalPalette, 1, this->nColors * 3, file) != this->nColors * 3 ) {
			fclose(file);
			return;
		}
	} else {
		this->globalPalette = NULL;
	}
    
	int c = fgetc(file);
    while( c == EXTENSION ) {
		readExtension(file);
		c = fgetc(file);
	}
      
	if(c != LOCAL) {
		fclose(file);
		return;
	}

	if (! loadImage(file)) {
		fclose(file);
		return;
	}
    c = fgetc(file); 

	this->animationFrameCount = 0;
	if(c != TERMINATOR && c != EOF) {
		while(c != TERMINATOR && c != EOF) {
			GIFFile* gif = new GIFFile(this, file, c);
			if (! gif) {
				fclose(file);
				return;
			}
			if (gif->isValid()) {
				this->animationFrameCount++;
				GIFFile** tmp = (GIFFile**) realloc(this->animationFrames,
												sizeof(GIFFile) * this->animationFrameCount);
				if (! tmp) {
					fclose(file);
					return;
				}
				this->animationFrames = tmp;
				this->animationFrames[this->animationFrameCount - 1] = gif;
			}
			c = fgetc(file); 
		}
	}
	fclose(file);
	this->valid = true;
}

/**
 * アニメーションフレームを構築する
 */
GIFFile::GIFFile(GIFFile* parent, FILE* file, int c) : valid(false),
													   localPalette(NULL),
													   raster(NULL) {
    // Copy global properties.
	this->parent = parent;
    this->globalWidth = parent->globalWidth;
    this->globalHeight = parent->globalHeight;
    this->nColors = parent->nColors;
    this->globalPalette = parent->globalPalette;
    this->hasGlobalColorMap = parent->hasGlobalColorMap;
    this->interlaced = parent->interlaced;
	this->isLooped = parent->isLooped;
    this->loopCount = parent->loopCount;
	this->animationFrameCount = 0;
	this->animationFrames = NULL;

    while( c == EXTENSION ) {
		if (! readExtension(file)) {
			return;
		}
		c = fgetc(file);
    }
      
	if( c != LOCAL ) {
		return;
	}
	if (!loadImage(file)) {
		return;
	}

	this->valid = true;
}

/**
 * デストラクタ
 */
GIFFile::~GIFFile() {
	if (! this->parent) {
		for (int i = 0; i < this->animationFrameCount; ++i) {
			delete this->animationFrames[i];
		}
		free(this->globalPalette);
		free(this->animationFrames);
	}

	free(this->localPalette);
	free(this->raster);
}

bool GIFFile::readSignature(FILE* file) {
    char data[6];
	if (fread(data, 1, 6, file) != 6) {
		return false;
	}

    if( data[0] != 0x47 || data[1] != 0x49 || data[2] != 0x46 || data[3] != 0x38 ) // GIF8
		return false;

    if( (data[4] != 0x39 && data[4] != 0x37) || // 7 | 9
		(data[5] != 0x61 && data[5] != 0x62) ) // 'a' or 'b'
		return false;
    return true;
}

bool GIFFile::readExtension(FILE* file) {
	int functionCode = fgetc(file);
	DataBlock* dataBlock = readData(file);
	char* data = dataBlock->data;

	switch( functionCode ) {
		case EXTENSION_GCONTROL: // Graphics control extension
			this->disposalMethod = (data[0] & 0x1C) >> 2;
			// allegedly there can be bad values of this.
			if( this->disposalMethod < 1 && this->disposalMethod > 3 )
				disposalMethod = 1; 
			this->hasTransparency = ((data[0] & 0x01) == 1);
			this->transparentIndex = (data[3] & 0xFF);
			this->duration = ((data[2] & 0xFF) << 8) | (data[1] & 0xFF);

			break;

		case EXTENSION_APPLICATION:
			if (0 == memcmp(data, nsBlock, sizeof(nsBlock))) {
				this->isLooped = true;
				this->loopCount = ((data[12] & 0xFF) << 8) | (data[13] & 0xFF);
			}
			break;

		default:
			break;
	}
	delete dataBlock;

	return true;
}

/**
 * データブロックを読み込む
 */
DataBlock* GIFFile::readData(FILE* file) {
	int totalBytes = 0;
	char* data = NULL;

	int n = fgetc(file);
	while (n > 0) {
		char* tmp = (char*) realloc(data, totalBytes + n);
		if (! tmp) {
			free(data);
			return false;
		}
		data = tmp;
		fread(tmp + totalBytes, 1, n, file);
		totalBytes += n;
		n = fgetc(file);
	}
	DataBlock* dataBlock = new DataBlock();
	dataBlock->size = totalBytes;
	dataBlock->data = data;

	return dataBlock;
}

/**
 * ローカルブロックを読み込む
 */
bool GIFFile::readLocal(FILE* file) {
    char data[9];
	if (fread(data, 1, 9, file) != 9) {
		return false;
	}

	this->x = ((data[1] & 0xFF) << 8) | (data[0] & 0xFF);
    this->y = ((data[3] & 0xFF) << 8) | (data[2] & 0xFF);
    this->width = ((data[5] & 0xFF) << 8) | (data[4] & 0xFF);
    this->height = ((data[7] & 0xFF) << 8) | (data[6] & 0xFF);
    char flags = data[8];
    
	this->interlaced = (( flags & 0x40 ) != 0);
    if( (flags & 0x80) != 0 ) {
		// has a local color map
		int nLocalColors = (1 << (( flags & 0x07) + 1));
		if(! this->hasGlobalColorMap )
			nColors = nLocalColors;
		this->localPalette = (unsigned char*) malloc(nLocalColors * 3);
		if (! this->localPalette) {
			return false;
		}
		if(fread(localPalette, 1, nLocalColors * 3, file) != nLocalColors * 3) {
			return false;
		}
	}
	return true;
}

int GIFFile::getBits(int nbits, DecoderInfo& info) {
	while( nbits > info.remainingBits) {
		int c = (info.compressedData->data[info.dataBlockIndex++] & 0xFF) << info.remainingBits;
		info.currentBits |= c;
		info.remainingBits += 8;
	}
    int rval = (info.currentBits & ((1 << nbits) - 1));
    info.currentBits = (info.currentBits >> nbits);
    info.remainingBits -= nbits;
    return rval;
}

#define DICTIONARY_SIZE	4096
/**
 * 画像をデコードする
 *
 * @param	pBits	デコード後の画像を格納するバッファ。
 *					width * height 分のDWORD配列である必要がある
 */
bool GIFFile::decodeRaster(int initialCodeSize, DataBlock* compressedData, BYTE* pBits) {
	DecoderInfo info;
	info.remainingBits = 0;
	info.currentBits = 0;
    info.dataBlockIndex = 0;
	info.compressedData = compressedData;

    int rasterIndex = 0; // Index into the raster
	const int maxRasterIndex = width * height;
    int clearCode = (1 << initialCodeSize); // 256 usually
    int endCode = clearCode + 1; // The stop code.

    BYTE* raster = pBits;

    int codeSize = initialCodeSize + 1;
    int code = getBits(codeSize, info); // = clear
    int nextCode = endCode + 1;

    /*
     * Initialize LZW dictionary
     *
     * First index - code #
     * Second index:
     * 0 = color index
     * 1 = parent (-1 - no parent)
     * 2 = first value
     * 3 - depth
     * The latter two aren't strictly necessary but make things faster, since
     * copying the values forward is faster than going back and looking.
     */
	struct dictionary_item {
		short color_index;
		short parent;
		short first;
		short depth;
	};

	dictionary_item* dictionary = (dictionary_item*) calloc(1, sizeof(dictionary_item) * DICTIONARY_SIZE);
	if (! dictionary) {
		return false;
	}
    for(short i = 0; i < this->nColors; i ++ ) {
		dictionary[i].color_index = i;  // color index	
		dictionary[i].parent      = -1; // parent
		dictionary[i].first       = i;  // first	
		dictionary[i].depth       = 1;  // depth
	}

    code = getBits( codeSize, info ); // get second code
	assert(rasterIndex < maxRasterIndex);
	if (rasterIndex < maxRasterIndex) {
		raster[rasterIndex++] = (byte)dictionary[code].color_index;
	}
    int old = code;    
    code = getBits( codeSize, info ); // start at the third code
    int c;

    do {
		if(code == clearCode) {
			codeSize = initialCodeSize + 1;
			nextCode = endCode + 1; 
			// get and output second code
			code = getBits( codeSize, info ); 
			assert(rasterIndex < width * height);
			if (rasterIndex < maxRasterIndex) {
				raster[rasterIndex++] = (char) dictionary[code].color_index;
			}
			old = code;
		} else {
			dictionary[nextCode].parent = (short)old; // parent = old
			dictionary[nextCode].first  = dictionary[old].first; // first pixel
			dictionary[nextCode].depth  = (short)(dictionary[old].depth + 1); // depth
	
			// appended pixel  = first pixel of c
			if( code < nextCode ) {
				dictionary[nextCode].color_index = dictionary[code].first; 
				old = code;
			} else { // first of old
				dictionary[nextCode].color_index = dictionary[old].first; 
				old = nextCode;
			}
			c = old;
			// output the code c
			int depth = dictionary[c].depth;
			for( int i = depth - 1; i >= 0; i-- ) {
				assert((rasterIndex + i) < width * height);	// 1 x 1 ピクセルの場合、このassert()は失敗する(が、書き込みはスキップされるので問題はないはず）
				if (rasterIndex + i < maxRasterIndex) {
					raster[ rasterIndex + i ] = (char)dictionary[c].color_index;
				}
				c = dictionary[c].parent; // go to parent.
			}
			rasterIndex += depth;
			nextCode++;

			if( codeSize < 12 && nextCode >= (1 << codeSize) )
				codeSize++;
		}
		code = getBits( codeSize, info );
	
	} while( code != endCode && info.dataBlockIndex < compressedData->size );
   
	free(dictionary);

	return true;
}

/**
 * 指定されたバッファにARGBフォーマットでイメージを転送する
 * 転送先バッファは getGlobalWidth() * getGlobalHeight() * sizeof(DWORD) 分のサイズを
 * 確保しておく必要がある
 */
void GIFFile::draw(DWORD* dest) {
	// カラーインデックス値をRGBに変換する
	unsigned char* palette = this->localPalette;
	if (! palette) {
		palette = this->globalPalette;
	}
	if (! palette) {
		// どうするべき？
		return;
	}
	
	// Disposal methodを処理する
	switch (getDisposalMethod()) {
		case this->DISPOSAL_MODE_RESTORE_TO_BACKGROUND_COLOR:
			// 背景色で塗りつぶす
			DWORD bg = indexToARGB(palette, this->bgIndex);
			const DWORD* endOfDest = dest + getGlobalWidth() * getGlobalHeight();
			DWORD* work = dest;
			while (work < endOfDest) {
				*work++ = bg;
			}
			break;
		// ToDo: その他のモードもサポートする
	}

	// イメージの転送を開始する
	BYTE* src = this->raster;
	if (getGlobalWidth() == getWidth() && getGlobalHeight() == getHeight()
			&& (getX() == 0 && getY() == 0)) {
		// サイズが一致した場合は、先頭から順にARGBに変換してコピーしていく
		int raster_size = width * height;
		for (int i = 0; i < raster_size; ++i) {
			int index = *src++;
			DWORD pixel = indexToARGB(palette, index);
			if (! this->parent || pixel & 0xff000000) {
				// 先頭フレーム、または2フレーム目以降の不透明色
				*dest = pixel;
			}
			dest++;
		}
	} else {
		// サイズが違う場合、1行ずつ転送する
		int startX = getX() > 0 ? getX() : 0;
		int startY = getY() > 0 ? getY() : 0;
		int endX = (startX + getWidth()) < getGlobalWidth()
					? startX + getWidth()
					: getGlobalWidth();
		int endY = (startY + getHeight()) < getGlobalHeight()
					? startY + getHeight()
					: getGlobalHeight();
		for (int j = startY; j < endY; ++j) {
			BYTE* srcLine = src + (j - startY) * getWidth();
			DWORD* destLine = dest + j * getGlobalWidth() + startX;
			for (int i = startX; i < endX; ++i) {
				DWORD pixel = indexToARGB(palette, *srcLine);
				if (! this->parent || pixel & 0xff000000) {
					*destLine = pixel;
				}
				srcLine++;
				destLine++;
			}
		}
	}
}

/**
 * 指定されたバッファにRGB565フォーマットでイメージを転送する
 * 転送先バッファは getGlobalWidth() * getGlobalHeight() * sizeof(WORD) 分のサイズを
 * 確保しておく必要がある
 */
void GIFFile::drawRGB565(WORD* dest) {
	// カラーインデックス値をRGBに変換する
	unsigned char* palette = this->localPalette;
	if (! palette) {
		palette = this->globalPalette;
	}
	if (! palette) {
		// どうするべき？
		return;
	}
	
	// Disposal methodを処理する
	switch (getDisposalMethod()) {
		case this->DISPOSAL_MODE_RESTORE_TO_BACKGROUND_COLOR:
			// 背景色で塗りつぶす
			WORD bg = indexToRGB565(palette, this->bgIndex);
			const WORD* endOfDest = dest + getGlobalWidth() * getGlobalHeight();
			WORD* work = dest;
			while (work < endOfDest) {
				*work++ = bg;
			}
			break;
		// ToDo: その他のモードもサポートする
	}

	// イメージの転送を開始する
	BYTE* src = this->raster;
	if (getGlobalWidth() == getWidth() && getGlobalHeight() == getHeight()
			&& (getX() == 0 && getY() == 0)) {
		// サイズが一致した場合は、先頭から順にARGBに変換してコピーしていく
		int raster_size = width * height;
		for (int i = 0; i < raster_size; ++i) {
			int index = *src++;
			WORD pixel = indexToRGB565(palette, index);
			*dest++ = pixel;
		}
	} else {
		// サイズが違う場合、1行ずつ転送する
		int startX = getX() > 0 ? getX() : 0;
		int startY = getY() > 0 ? getY() : 0;
		int endX = (startX + getWidth()) < getGlobalWidth()
					? startX + getWidth()
					: getGlobalWidth();
		int endY = (startY + getHeight()) < getGlobalHeight()
					? startY + getHeight()
					: getGlobalHeight();
		for (int j = startY; j < endY; ++j) {
			BYTE* srcLine = src + (j - startY) * getWidth();
			WORD* destLine = dest + j * getGlobalWidth() + startX;
			for (int i = startX; i < endX; ++i) {
				WORD pixel = indexToRGB565(palette, *srcLine);
				*destLine++ = pixel;
				srcLine++;
			}
		}
	}
}

/**
 * イメージデータをファイルからロードする
 */
bool GIFFile::loadImage(FILE* file) {
	if (! readLocal(file)) {
		return false;
	}

	int initialCodeSize = fgetc(file);
	DataBlock* compressedData = readData(file);
	if (! compressedData) {
		return false;
	}

	this->raster = (BYTE*) malloc(sizeof(BYTE) * getWidth() * getHeight());
	if (! this->raster) {
		return false;
	}
	if (! decodeRaster(initialCodeSize, compressedData, this->raster)) {
		delete compressedData;
		free(this->raster);
		this->raster = NULL;
		return false;
	}
	delete compressedData;

	if (this->interlaced) {
		if (! deinterlace(this->raster)) {
			free(this->raster);
			this->raster = NULL;
			return false;
		}
	}
	return true;
}

bool GIFFile::deinterlace(BYTE* pBits) {
	BYTE* nr = (BYTE*) malloc(this->width * this->height * sizeof(BYTE));
	if (! nr) {
		return NULL;
	}
	BYTE* data = pBits;

    int n = 0;
    for(int i = 0; i < ((height + 7) >> 3); i++) {
		memcpy(nr + width * i * 8, data, width * sizeof(BYTE));
		data += width;
    }
    for(int i = 0; i < ((height + 3) >> 3); i++) {
		memmove(nr + width * (8 * i + 4), data, width * sizeof(BYTE));
		data += width;
	}
    for(int i = 0; i < (height >> 2); i++) {
		memmove(nr + width * (4 * i + 2), data, width * sizeof(BYTE));
		data += width;
	}
    
	for(int i = 0; i < (height >> 1); i++) {
		memmove(nr + width * (2 * i + 1), data, width * sizeof(BYTE));
		data += width;
	}
	memcpy(pBits, nr, sizeof(BYTE) * width * height);
	free(nr);

	return true;
}

/**
 * 透明色を返す
 */
COLORREF GIFFile::getTransparentColor() {
	COLORREF result;
	if (hasTransparentColor()) {
		unsigned char index = this->transparentIndex;
		unsigned char* palette;
		if (this->localPalette) {
			palette = this->localPalette;
		} else {
			palette = this->globalPalette;
		}
		if (palette) {
			unsigned char* color = &palette[index * 3];
			result = RGB(color[0], color[1], color[2]);
		} else {
			result = RGB(0, 0, 0);
		}
	}
	return result;
}