////////////////////////////////////////////////////////////////////////////////
//
//	File: GIFLoad.cpp
//
//	Date: December 1999
//
//	Author: Daniel Switkin
//
//	Copyright 2003 (c) by Daniel Switkin. This file is made publically available
//	under the BSD license, with the stipulations that this complete header must
//	remain at the top of the file indefinitely, and credit must be given to the
//	original author in any about box using this software.
//
////////////////////////////////////////////////////////////////////////////////

// Additional authors:	John Scipione, <jscipione@gmail.com>


#include "GIFLoad.h"

#include <stdio.h>
#include <stdlib.h>
#include <syslog.h>

#include <new>

#include <ByteOrder.h>
#include <InterfaceDefs.h>
#include <TranslatorFormats.h>

#include "GIFPrivate.h"


extern bool debug;


GIFLoad::GIFLoad(BPositionIO* input, BPositionIO* output)
	:
	fatalerror(false),
	fInput(input),
	fOutput(output),
	fPalette(NULL),
 	fHeadMemblock(NULL),
	fScanLine(NULL)
{
	fInput->Seek(0, SEEK_SET);

	if (!ReadGIFHeader()) {
		fatalerror = true;
		return;
	}

	if (debug) {
		syslog(LOG_INFO, "GIFLoad::GIFLoad() - Image dimensions are %d x %d\n",
			fWidth, fHeight);
	}

	unsigned char c;
	if (fInput->Read(&c, 1) < 1) {
		fatalerror = true;
		return;
	}

	while (c != TERMINATOR_INTRODUCER) {
		if (c == DESCRIPTOR_INTRODUCER) {
			if ((!ReadGIFImageHeader()) || (!ReadGIFImageData())) {
				if (debug) {
					syslog(LOG_ERR, "GIFLoad::GIFLoad() - "
						"A fatal error occurred\n");
				}

				fatalerror = true;
			} else {
				if (debug) {
					syslog(LOG_INFO, "GIFLoad::GIFLoad() - "
						"Found a single image and leaving\n");
				}
			}
			free(fScanLine);
			fScanLine = NULL;
			return;
		} else if (c == EXTENSION_INTRODUCER) {
			unsigned char d;
			if (fInput->Read(&d, 1) < 1) {
				fatalerror = true;
				return;
			}
			if (d == LOOP_BLOCK_LABEL) {
				if (!ReadGIFLoopBlock()) {
					fatalerror = true;
					return;
				}
			} else if (d == GRAPHIC_CONTROL_LABEL) {
				if (!ReadGIFControlBlock()) {
					fatalerror = true;
					return;
				}
			} else if (d == COMMENT_EXTENSION_LABEL) {
				if (!ReadGIFCommentBlock()) {
					fatalerror = true;
					return;
				}
			} else {
				if (!ReadGIFUnknownBlock(d)) {
					fatalerror = true;
					return;
				}
			}
		} else if (c != BLOCK_TERMINATOR) {
			if (!ReadGIFUnknownBlock(c)) {
				fatalerror = true;
				return;
			}
		}

		if (fInput->Read(&c, 1) < 1) {
			fatalerror = true;
			return;
		}
	}

	if (debug)
		syslog(LOG_INFO, "GIFLoad::GIFLoad() - Done\n");
}


GIFLoad::~GIFLoad()
{
	delete fPalette;
}


bool
GIFLoad::ReadGIFHeader()
{
	// standard header
	unsigned char header[13];
	if (fInput->Read(header, 13) < 13)
		return false;

	fWidth = header[6] + (header[7] << 8);
	fHeight = header[8] + (header[9] << 8);

	fPalette = new(std::nothrow) LoadPalette();
	if (fPalette == NULL)
		return false;

	// Global palette
	if (header[10] & GIF_LOCALCOLORMAP) {
		fPalette->size_in_bits = (header[10] & 0x07) + 1;
		if (debug) {
			syslog(LOG_INFO, "GIFLoad::ReadGIFHeader() - "
				"Found %d bit global palette\n",
				fPalette->size_in_bits);
		}
		int s = 1 << fPalette->size_in_bits;
		fPalette->size = s;

		unsigned char gp[256 * 3];
		if (fInput->Read(gp, s * 3) < s * 3)
			return false;

		for (int x = 0; x < s; x++)
			fPalette->SetColor(x, gp[x * 3], gp[x * 3 + 1], gp[x * 3 + 2]);

		fPalette->backgroundindex = header[11];
	} else {
		// install BeOS system palette in case local palette isn't present
		color_map* map = (color_map*)system_colors();
		for (int x = 0; x < 256; x++) {
			fPalette->SetColor(x, map->color_list[x].red,
				map->color_list[x].green, map->color_list[x].blue);
		}
		fPalette->size = 256;
		fPalette->size_in_bits = 8;
	}

	return true;
}


bool
GIFLoad::ReadGIFLoopBlock()
{
	unsigned char length;
	if (fInput->Read(&length, 1) < 1)
		return false;

	fInput->Seek(length, SEEK_CUR);
	do {
		if (fInput->Read(&length, 1) < 1)
			return false;

		fInput->Seek(length, SEEK_CUR);
	} while (length != 0);

	return true;
}


bool
GIFLoad::ReadGIFControlBlock()
{
	unsigned char data[6];
	if (fInput->Read(data, 6) < 6)
		return false;

	if ((data[1] & 0x01) != 0) {
		fPalette->usetransparent = true;
		fPalette->transparentindex = data[4];
		if (debug) {
			syslog(LOG_INFO, "GIFLoad::ReadGIFControlBlock() - "
				"Transparency active, using palette index %d\n", data[4]);
		}
	}

	return true;
}


bool
GIFLoad::ReadGIFCommentBlock()
{
	if (debug)
		syslog(LOG_INFO, "GIFLoad::ReadGIFCommentBlock() - Found:\n");

	unsigned char length;
	char comment_data[256];
	do {
		if (fInput->Read(&length, 1) < 1)
			return false;

		if (fInput->Read(comment_data, length) < length)
			return false;

		comment_data[length] = BLOCK_TERMINATOR;
		if (debug)
			syslog(LOG_INFO, "%s", comment_data);
	} while (length != BLOCK_TERMINATOR);

	if (debug)
		syslog(LOG_INFO, "\n");

	return true;
}


bool
GIFLoad::ReadGIFUnknownBlock(unsigned char c)
{
	if (debug)
		syslog(LOG_INFO, "GIFLoad::ReadGIFUnknownBlock() - Found: %d\n", c);

	unsigned char length;
	do {
		if (fInput->Read(&length, 1) < 1)
			return false;

		fInput->Seek(length, SEEK_CUR);
	} while (length != BLOCK_TERMINATOR);

	return true;
}


bool
GIFLoad::ReadGIFImageHeader()
{
	unsigned char data[9];
	if (fInput->Read(data, 9) < 9)
		return false;

	int left = data[0] + (data[1] << 8);
	int top = data[2] + (data[3] << 8);
	int localWidth = data[4] + (data[5] << 8);
	int localHeight = data[6] + (data[7] << 8);
	if (fWidth != localWidth || fHeight != localHeight) {
		if (debug) {
			syslog(LOG_ERR, "GIFLoad::ReadGIFImageHeader() - "
				"Local dimensions do not match global, setting to %d x %d\n",
				localWidth, localHeight);
		}
		fWidth = localWidth;
		fHeight = localHeight;
	}

	fScanLine = (uint32*)malloc(fWidth * 4);
	if (fScanLine == NULL) {
		if (debug) {
			syslog(LOG_ERR, "GIFLoad::ReadGIFImageHeader() - "
				"Could not allocate scanline\n");
		}
		return false;
	}

	BRect rect(left, top, left + fWidth - 1, top + fHeight - 1);
	TranslatorBitmap header;
	header.magic = B_HOST_TO_BENDIAN_INT32(B_TRANSLATOR_BITMAP);
	header.bounds.left = B_HOST_TO_BENDIAN_FLOAT(rect.left);
	header.bounds.top = B_HOST_TO_BENDIAN_FLOAT(rect.top);
	header.bounds.right = B_HOST_TO_BENDIAN_FLOAT(rect.right);
	header.bounds.bottom = B_HOST_TO_BENDIAN_FLOAT(rect.bottom);
	header.rowBytes = B_HOST_TO_BENDIAN_INT32(fWidth * 4);
	header.colors = (color_space)B_HOST_TO_BENDIAN_INT32(B_RGBA32);
	header.dataSize = B_HOST_TO_BENDIAN_INT32(fWidth * 4 * fHeight);
	if (fOutput->Write(&header, 32) < 32)
		return false;

	if (data[8] & GIF_LOCALCOLORMAP) {
		// has local palette
		fPalette->size_in_bits = (data[8] & 0x07) + 1;
		int s = 1 << fPalette->size_in_bits;
		fPalette->size = s;
		if (debug) {
			syslog(LOG_INFO, "GIFLoad::ReadGIFImageHeader() - "
				"Found %d bit local palette\n", fPalette->size_in_bits);
		}

		unsigned char lp[256 * 3];
		if (fInput->Read(lp, s * 3) < s * 3)
			return false;

		for (int x = 0; x < s; x++)
			fPalette->SetColor(x, lp[x * 3], lp[x * 3 + 1], lp[x * 3 + 2]);
	}

	fInterlaced = data[8] & GIF_INTERLACED;
	if (debug) {
		if (fInterlaced) {
			syslog(LOG_INFO, "GIFLoad::ReadGIFImageHeader() - "
				"Image is interlaced\n");
		} else {
			syslog(LOG_INFO, "GIFLoad::ReadGIFImageHeader() - "
				"Image is not interlaced\n");
		}
	}

	return true;
}


bool
GIFLoad::ReadGIFImageData()
{
	unsigned char newEntry[ENTRY_COUNT];
	unsigned char codeSize;
	if (fInput->Read(&codeSize, 1) < 1)
		return false;

	if (codeSize > fPalette->size_in_bits) {
		if (debug) {
			syslog(LOG_ERR, "GIFLoad::ReadGIFImageData() - "
				"Code_size should be %d, not %d, allowing it\n",
				fCodeSize, codeSize);
		}
		if (!InitFrame(codeSize))
			return false;
	} else if (codeSize < fPalette->size_in_bits) {
		if (debug) {
			syslog(LOG_ERR, "GIFLoad::ReadGIFImageData() - "
				"Code_size should be %d, not %d\n", fCodeSize, codeSize);
		}
		return false;
	} else if (!InitFrame(fPalette->size_in_bits))
		return false;

	if (debug)
		syslog(LOG_INFO, "GIFLoad::ReadGIFImageData() - Starting LZW\n");

	while ((fNewCode = NextCode()) != -1 && fNewCode != fEndCode) {
		if (fNewCode == fClearCode) {
			ResetTable();
			fNewCode = NextCode();
			fOldCode[0] = fNewCode;
			fOldCodeLength = 1;
			if (!OutputColor(fOldCode, 1))
				goto bad_end;

			if (fNewCode == -1 || fNewCode == fEndCode) {
				if (debug) {
					syslog(LOG_ERR, "GIFLoad::ReadGIFImageData() - "
						"Premature fEndCode or error reading fNewCode\n");
				}
				goto bad_end;
			}
			continue;
		}

		// explicitly check for lack of clear code at start of file
		if (fOldCodeLength == 0) {
			fOldCode[0] = fNewCode;
			fOldCodeLength = 1;
			if (!OutputColor(fOldCode, 1))
				goto bad_end;

			continue;
		}

		// error out if we're trying to access an out-of-bounds index
		if (fNextCode >= ENTRY_COUNT)
			goto bad_end;

		if (fTable[fNewCode] != NULL) {
			// exists in table

			if (!OutputColor(fTable[fNewCode], fEntrySize[fNewCode]))
				goto bad_end;

			//memcpy(newEntry, fOldCode, fOldCodeLength);
			for (unsigned int x = 0; x < fOldCodeLength; x++)
				newEntry[x] = fOldCode[x];

			//memcpy(newEntry + fOldCodeLength, fTable[fNewCode], 1);
			newEntry[fOldCodeLength] = fTable[fNewCode][0];
		} else {
			// does not exist in table

			//memcpy(newEntry, fOldCode, fOldCodeLength);
			for (unsigned int x = 0; x < fOldCodeLength; x++)
				newEntry[x] = fOldCode[x];

			//memcpy(newEntry + fOldCodeLength, fOldCode, 1);
			newEntry[fOldCodeLength] = fOldCode[0];

			if (!OutputColor(newEntry, fOldCodeLength + 1))
				goto bad_end;
		}
		fTable[fNextCode] = MemblockAllocate(fOldCodeLength + 1);
		if (fTable[fNextCode] == NULL)
			goto bad_end;

		//memcpy(fTable[fNextCode], newEntry, fOldCodeLength + 1);
		for (unsigned int x = 0; x < fOldCodeLength + 1; x++)
			fTable[fNextCode][x] = newEntry[x];

		fEntrySize[fNextCode] = fOldCodeLength + 1;

		//memcpy(fOldCode, fTable[fNewCode], fEntrySize[fNewCode]);
		for (int x = 0; x < fEntrySize[fNewCode]; x++)
			fOldCode[x] = fTable[fNewCode][x];

		fOldCodeLength = fEntrySize[fNewCode];
		fNextCode++;

		if (fNextCode > fMaxCode && fBits < LZ_MAX_BITS) {
			fBits++;
			fMaxCode = (1 << fBits) - 1;
		}
	}

	MemblockDeleteAll();
	if (fNewCode == -1)
		return false;

	if (debug)
		syslog(LOG_INFO, "GIFLoad::ReadGIFImageData() - Done\n");

	return true;

bad_end:
	if (debug)
		syslog(LOG_ERR, "GIFLoad::ReadGIFImageData() - Reached a bad end\n");

	MemblockDeleteAll();
	return false;
}


short
GIFLoad::NextCode()
{
	while (fBitCount < fBits) {
		if (fByteCount == 0) {
			if (fInput->Read(&fByteCount, 1) < 1)
				return -1;

			if (fByteCount == 0)
				return fEndCode;

			if (fInput->Read(fByteBuffer + (255 - fByteCount), fByteCount)
					< fByteCount) {
				return -1;
			}
		}
		fBitBuffer |= (unsigned int)fByteBuffer[255 - fByteCount] << fBitCount;
		fByteCount--;
		fBitCount += 8;
	}

	short s = fBitBuffer & ((1 << fBits) - 1);
	fBitBuffer >>= fBits;
	fBitCount -= fBits;

	return s;
}


void
GIFLoad::ResetTable()
{
	fBits = fCodeSize + 1;
	fNextCode = fClearCode + 2;
	fMaxCode = (1 << fBits) - 1;

	MemblockDeleteAll();
	for (int x = 0; x < ENTRY_COUNT; x++) {
		fTable[x] = NULL;
		if (x < (1 << fCodeSize)) {
			fTable[x] = MemblockAllocate(1);
			if (fTable[x] != NULL) {
				fTable[x][0] = x;
				fEntrySize[x] = 1;
			}
		}
	}
}


bool
GIFLoad::InitFrame(int codeSize)
{
	fCodeSize = codeSize;
	if (fCodeSize == 1)
		fCodeSize++;

	fBits = fCodeSize + 1;
	fClearCode = 1 << fCodeSize;
	fEndCode = fClearCode + 1;
	fNextCode = fClearCode + 2;
	fMaxCode = (1 << fBits) - 1;

	fPass = 0;

	if (fInterlaced)
		fRow = gl_pass_starts_at[0];
	else
		fRow = 0;

	fBitCount = 0;
	fBitBuffer = 0;
	fByteCount = 0;
	fOldCodeLength = 0;
	fNewCode = 0;
	fScanlinePosition = 0;

	ResetTable();
	return true;
}


unsigned char*
GIFLoad::MemblockAllocate(int size)
{
	// Do 4k mallocs, keep them in a linked list, do a first fit across
	// them when a new request comes along.

	if (fHeadMemblock == NULL) {
		fHeadMemblock = (Memblock*)malloc(sizeof(Memblock));
		if (fHeadMemblock == NULL)
			return NULL;

		unsigned char* value = fHeadMemblock->data;
		fHeadMemblock->offset = size;
		fHeadMemblock->next = NULL;

		return value;
	} else {
		Memblock* block = fHeadMemblock;
		Memblock* last = NULL;
		while (block != NULL) {
			if (ENTRY_COUNT - block->offset > size) {
				unsigned char* value = block->data + block->offset;
				block->offset += size;

				return value;
			}
			last = block;
			block = block->next;
		}

		block = (Memblock*)malloc(sizeof(Memblock));
		if (block == NULL)
			return NULL;

		unsigned char* value = block->data;
		block->offset = size;
		block->next = NULL;
		if (last != NULL)
			last->next = block;

		return value;
	}
}


void
GIFLoad::MemblockDeleteAll()
{
	Memblock* block = NULL;

	while (fHeadMemblock != NULL) {
		// delete the linked list
		block = fHeadMemblock->next;
		free(fHeadMemblock);
		fHeadMemblock = block;
	}
}


bool
GIFLoad::OutputColor(unsigned char* string, int size)
{
	int bpr = fWidth << 2;

	for (int x = 0; x < size; x++) {
		fScanLine[fScanlinePosition] = fPalette->ColorForIndex(string[x]);
		fScanlinePosition++;

		if (fScanlinePosition >= fWidth) {
			if (fOutput->WriteAt(32 + (fRow * bpr), fScanLine, bpr) < bpr)
				return false;

			fScanlinePosition = 0;
			if (fInterlaced) {
				fRow += gl_increment_pass_by[fPass];
				while (fRow >= fHeight) {
					fPass++;
					if (fPass > 3)
						return true;

					fRow = gl_pass_starts_at[fPass];
				}
			} else
				fRow++;
		}
	}

	return true;
}