/*****************************************************************************/
/****  File sorgente giflzw.c                                 	          ****/
/****  di Alberto Geneletti	version 1.0	giugno 1993               ****/
/****                                                                     ****/
/****  Le seguenti routine di codifica e di decodifica sono in piccola    ****/
/****  parte basate su altri analoghi sorgenti pubblicamente disponibili. ****/
/****  In particolare ho tratto da ciascuno di essi la soluzione che mi   ****/
/****  e' sembrata migliore nell'implementazione delle varie routines.    ****/
/****  Ho inoltre migliorato tanto la gestione della memoria, quanto la   ****/
/****  semplicita' del codice, sperando di ottenere cosi' un'esecuzione   ****/
/****  piu' veloce. Il risultato e' un codice molto veloce, ma probabil-  ****/
/****  mente un po' troppo poco robusto.                                  ****/
/****  Non viene infatti quasi mai verificato il possibile salto al di    ****/
/****  fuori delle tabelle in situazioni di errore, causa di un molto     ****/
/****  probabile crash (core dump o guru meditation).                     ****/
/****  Il problema e' comunque piuttosto complesso, e sono confortato dal ****/
/****  gran numero di altri decodificatori GIF che si suicidano misera-   ****/
/****  mente di fronte ad un file troncato a meta'.                       ****/
/*****************************************************************************/

#include "gif.h"

#define	MAXBITS	12
#define MAXCODE	(1<<MAXBITS)

int16  *BaseCodeTable;
int8   *NewCodeTable;

char Buffer[260];

int ClearCode, EndOfInformationCode;
int CurrentBit, CurrentByte;
int CurrentMaxCode, NextFreeCode;
int CodeSize, MinCodeSize;

int Dy[4] = {8,8,4,2};
int Sy[4] = {0,4,2,1};
int Pass;

/************** Algoritmi di Codifica ****************************************/

#define HSIZE	5003

int BitsLeft;
int LastCode;

int16 *HashTable;
FILE *OutPutFile;

int InitEncoder()
{
	if(!(HashTable = (int16 *)
		malloc(HSIZE * sizeof(int16))))

			return(ALLOCATION_ERROR);

	if(!(BaseCodeTable = (int16 *)
		malloc(HSIZE * sizeof(int16)))) {

			free(HashTable);
			return(ALLOCATION_ERROR);
	}

	if(!(NewCodeTable = (int8 *)
		malloc(HSIZE * sizeof(int8)))) {

			free(HashTable);
			free(BaseCodeTable);
			return(ALLOCATION_ERROR);
	}

	ClearCode		= (1<<MinCodeSize);
	EndOfInformationCode	= ClearCode+1;
	ClearTable();
	return(OK);
}


void ClearTable()
{
	int i;

	CodeSize	= MinCodeSize+1;
	NextFreeCode	= ClearCode+2;
	CurrentMaxCode	= (1<<CodeSize);

	for(i=0;i<HSIZE;i++)
		HashTable[i]=0;

}


void SyncEncoder()
{
	PutCodeIntoBuffer(LastCode);
	PutCodeIntoBuffer(EndOfInformationCode);

	if(CurrentBit > 0)
		WriteBlockOfRasterData((CurrentBit+7)/8);

	WriteBlockOfRasterData(0);

	free(HashTable);
	free(BaseCodeTable);
	free(NewCodeTable);
}


void WriteBlockOfRasterData(int n)
{
	fputc(n,OutPutFile);
	fwrite(Buffer,1,n,OutPutFile);
}


void PutCodeIntoBuffer(int code)
{
	long temp;

	CurrentByte = CurrentBit >> 3;
	BitsLeft = CurrentBit & 7;

	if(CurrentByte >= 254) {
		WriteBlockOfRasterData(CurrentByte);
		Buffer[0] = Buffer[CurrentByte];
		CurrentBit = BitsLeft;
		CurrentByte = 0;
	}

	if(BitsLeft > 0) {
		temp = ((long) code << BitsLeft) | Buffer[CurrentByte];
		Buffer[CurrentByte]=temp;
		Buffer[CurrentByte+1]=(temp >> 8);
		Buffer[CurrentByte+2]=(temp >> 16);
	}
	else {
		Buffer[CurrentByte] = code;
		Buffer[CurrentByte+1]=(code >> 8);
	}
	CurrentBit += CodeSize;
}

void EncodeByte(int NewChar)
{
 	static int HashIndex,NextFreeHashEntry;

	HashIndex=(LastCode ^ (NewChar << 5)) & 0x0FFF;
	NextFreeHashEntry=1;

	while(1) {

		if(HashTable[HashIndex] == 0) {
			PutCodeIntoBuffer(LastCode);
			NextFreeHashEntry = NextFreeCode;
			if(NextFreeCode <= MAXCODE) {
				BaseCodeTable[HashIndex] = LastCode;
				NewCodeTable[HashIndex] = NewChar;
				HashTable[HashIndex] = NextFreeCode;
				NextFreeCode++;
			}

			if(NextFreeHashEntry == CurrentMaxCode) {
				if(CodeSize < 12) {
					CodeSize++;
					CurrentMaxCode <<= 1;
				}
				else {
					PutCodeIntoBuffer(ClearCode);
					ClearTable();
				}
			}
			LastCode = NewChar;
			break;
		}
		if(BaseCodeTable[HashIndex] == LastCode &&
		   NewCodeTable[HashIndex] == NewChar) {
			LastCode = HashTable[HashIndex];
			break;
		}
		HashIndex += NextFreeHashEntry;
		NextFreeHashEntry += 2;
		if(HashIndex >= HSIZE)
			HashIndex -= HSIZE;
	}
}


void PutLine(int NLine, GIFImage *GIFIm)
{
  	static char huge *BufPos;
  	static int col;
  	int Bug;

  	if(NLine == 0)
		Bug = 1;
  	else
		Bug = 0;

  	BufPos = GIFIm->BitMap + (long)GIFIm->Width * (long)NLine;

  	for (col = Bug; col < GIFIm->Width; col++)
    		EncodeByte(*BufPos++);
}


int PutBitMap(GIFImage *GIFIm)
{
	int Row, ReturnCode;

	OutPutFile 	= GIFIm->FD;
	MinCodeSize 	= GIFIm->InitialCodeSize;
	LastCode 	= *(GIFIm->BitMap);

	CurrentBit=0;

	if((ReturnCode = InitEncoder()) != OK)
		return(ReturnCode);

	PutCodeIntoBuffer(ClearCode);

	if(GIFIm->InterLace) {

		for(Pass = 0; Pass < 4; Pass ++) {
			Row = Sy[Pass];
			while(Row < GIFIm->Height) {
				(*GIFIm->ShowWorkInProgress)(0, GIFIm);
				PutLine(Row,GIFIm);
				Row += Dy[Pass];
			}
		}
	}
	else {
		for(Row = 0; Row < GIFIm->Height; Row++) {
			(*GIFIm->ShowWorkInProgress)(0, GIFIm);
			PutLine(Row,GIFIm);

		}
	}

	SyncEncoder();

	return(OK);
}


/**** Algoritmi di decodifica dello LZW **************************************/

int LastByte;
int LastBit;

int8   *Stack;
int8   *sp;

static int mask[] = {0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f,
		     0x003f, 0x007f, 0x00ff, 0x01ff, 0x03ff, 0x07ff,
		     0x0fff, 0x1fff, 0x3fff, 0x7fff};

int GetCode(GIFImage *GIFIm)
{
	register long int RowCode;
	int PacketLength;


	if ((CurrentBit+CodeSize) > LastBit) {

		Buffer[0] = Buffer[LastByte-2];
		Buffer[1] = Buffer[LastByte-1];

		if ((PacketLength = GetBlockOfData(&Buffer[2],GIFIm)) == 0) {
			return(EndOfInformationCode);
		}

		CurrentBit = (CurrentBit - LastBit) + 16;
		LastByte = 2 + PacketLength;
		LastBit = LastByte * 8;
	}


	CurrentByte = CurrentBit >> 3;

	RowCode = Buffer[CurrentByte+2];
	RowCode <<= 8;
	RowCode |= Buffer[CurrentByte+1];
	RowCode <<= 8;
	RowCode |= Buffer[CurrentByte];
	RowCode >>= (CurrentBit & 7);

	CurrentBit += CodeSize;

	return(((int) RowCode) & mask[CodeSize]);
}


int LZWReadByte(GIFImage *GIFIm)
{
	static int LastCode;
	static int ReturnCode;
	register int NewCode;
	int incode;


	if (sp > Stack)
		return((int) *(--sp));

	NewCode = GetCode(GIFIm);

	if (NewCode == ClearCode) {
		CodeSize = GIFIm->InitialCodeSize + 1;
		CurrentMaxCode = ClearCode << 1;
		NextFreeCode = ClearCode + 2;
		sp = Stack;

		do {
			NewCode = GetCode(GIFIm);
		} while (NewCode == ClearCode);

		ReturnCode = LastCode = NewCode;
		return(NewCode);
	}

	if (NewCode == EndOfInformationCode)
		return(-1);

	incode = NewCode;

	if (NewCode >= NextFreeCode) {
		*sp++ = (int8) ReturnCode;
		NewCode = LastCode;
	}

	while (NewCode >= ClearCode) {
		*sp++ = NewCodeTable[NewCode];
		NewCode = BaseCodeTable[NewCode];
	}

	ReturnCode = NewCode;

	if ((NewCode = NextFreeCode) < MAXCODE) {

		BaseCodeTable[NewCode] = LastCode;
		NewCodeTable[NewCode] = (int8) ReturnCode;
		NextFreeCode++;

		if ((NextFreeCode >= CurrentMaxCode) &&
			(CodeSize < MAXBITS)) {
				CodeSize++;
				CurrentMaxCode <<= 1;
		}
	}

	LastCode = incode;
	return(ReturnCode);
}


int InitDecoder(GIFImage *GIFIm)
{
	if(!(Stack = (int8 *)
		malloc(MAXCODE * sizeof(int8))))

			return(ALLOCATION_ERROR);

	if(!(BaseCodeTable = (int16 *)
		malloc(MAXCODE * sizeof(int16)))) {

			free(Stack);
			return(ALLOCATION_ERROR);
	}

	if(!(NewCodeTable = (int8 *)
		malloc(MAXCODE * sizeof(int8)))) {

			free(Stack);
			free(BaseCodeTable);
			return(ALLOCATION_ERROR);
	}

  	LastByte = 2;
  	LastBit = 0;
  	CurrentBit = 0;

  	ClearCode = 1 << (GIFIm->InitialCodeSize);
  	EndOfInformationCode = ClearCode + 1;

  	CodeSize = GIFIm->InitialCodeSize + 1;
  	CurrentMaxCode = ClearCode << 1;
  	NextFreeCode = ClearCode + 2;
  	sp = Stack;

  	return(OK);
}


void SyncDecoder()
{
	free(Stack);
	free(BaseCodeTable);
	free(NewCodeTable);
}


void GetLine(char huge *Buff, GIFImage *GIFIm)
{
  	char huge *BufPos;
  	long col;
  	int c;

  	BufPos = Buff;

  	for (col = GIFIm->Width; col > 0; col--) {
    		if((c = LZWReadByte(GIFIm)) < 0) {
			printf("\n");
			return;
		}

    		*BufPos++ = (unsigned char)c;
        }
}


int GetBitMap(GIFImage *GIFIm)
{
	int Row;
	char huge *BufPos;

	if(!(GIFIm->BitMap = (char huge *)
		farmalloc((long)GIFIm->Width*(long)GIFIm->Height)))
			return(ALLOCATION_ERROR);
	else
		GIFIm->AllocationFlags |= AUTOALLOCATED_BITMAP;

	InitDecoder(GIFIm);

	if(GIFIm->InterLace) {

		for(Pass = 0; Pass < 4; Pass ++) {
			Row = Sy[Pass];
			while(Row < GIFIm->Height) {
				BufPos = GIFIm->BitMap +
				(long)((long)GIFIm->Width * (long)Row);
				(*GIFIm->ShowWorkInProgress)(0, GIFIm);
				GetLine(BufPos,GIFIm);
				Row += Dy[Pass];
			}
		}
	}
	else {

		for(Row = 0, BufPos = GIFIm->BitMap;
			Row < GIFIm->Height; Row++,
			BufPos += GIFIm->Width) {
				(*GIFIm->ShowWorkInProgress)(0, GIFIm);
				GetLine(BufPos,GIFIm);
		}
	}
   	IgnoreCurrentChunk(GIFIm);
	SyncDecoder();

	return(OK);
}