/************************************************************************************
	GLOVER PSX	(c) 1998-9 ISL

	utils.c:		General purpose utility functions

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

#include "glover.h"
//#include <strings.h>	// to get rid of a warning about "strtok"

#define POLYNOMIAL 0x04c11db7L

static int				randomSeed;
static unsigned long	CRCtable[256];


/**************************************************************************
	FUNCTION:	upperStr()
	PURPOSE:	Convert string to upper case
	PARAMETERS:	String ptr
	RETURNS:	
**************************************************************************/

void upperStr(char *str)
{
	while(*str)
	{
		if ((*str>='a')&&(*str<='z'))
			*str -= 'a'-'A';
		str++;
	}
}


/**************************************************************************
	FUNCTION:	seedRandomInt()
	PURPOSE:	Set random integer seed value
	PARAMETERS:	Seed value
	RETURNS:	
**************************************************************************/

void seedRandomInt(int seed)
{
	randomSeed = seed;
}


/**************************************************************************
	FUNCTION:	randomInt()
	PURPOSE:	Generate pseudo random integer
	PARAMETERS:	Maximum value
	RETURNS:	Random value (0-limit)
**************************************************************************/

int randomInt(int limit)
{
	randomSeed = randomSeed ^ (randomSeed<<1);
	if ((randomSeed & 0x80000000)==0)
		randomSeed++;
	else
		if (randomSeed == 0x80000000)
			randomSeed = 0;
	return (randomSeed % (limit+1));
}


/**************************************************************************
	FUNCTION:	getNextToken()
	PURPOSE:	Get next word from string
	PARAMETERS:	First time: string, subsequent calls: NULL
	RETURNS:	(Temporary) ptr to word
**************************************************************************/

char *getNextToken(char *str)
{
	char 	seps[]=" ,\t\n\x0d";
	char	*tkn;

	tkn = strtok(str, seps);
	while((tkn!=NULL)&&(strchr(seps,tkn[0])))
		tkn = strtok(NULL, seps);
	return tkn;
}


/**************************************************************************
	FUNCTION:	initCRC()
	PURPOSE:	Initialise internal table for CRC calculations
	PARAMETERS:	
	RETURNS:	
**************************************************************************/

void initCRC()
{
	register int i, j;
	register unsigned long CRCaccum;

	for (i=0; i<256; i++)
		{
		CRCaccum = ((unsigned long)i<<24);
		for (j=0; j<8; j++)
			{
			if (CRCaccum & 0x80000000L)
				CRCaccum = (CRCaccum<<1)^POLYNOMIAL;
			else
				CRCaccum = (CRCaccum<<1);
			}
		CRCtable[i] = CRCaccum;
		}
}


/**************************************************************************
	FUNCTION:	str2CRC()
	PURPOSE:	Calculate 32-bit CRC for given string
	PARAMETERS:	Ptr to string
	RETURNS:	32-bit CRC
**************************************************************************/

unsigned long str2CRC(char *ptr)
{
	register int i, j;
	int size = strlen(ptr);
	unsigned long CRCaccum = 0;

	for (j=0; j<size; j++)
		{
		i = ((int)(CRCaccum>>24)^(*ptr++))&0xff;
		CRCaccum = (CRCaccum<<8)^CRCtable[i];
		}
	return CRCaccum;
}

unsigned long mem2CRC(char *ptr, int size)
{
	register int i, j;
	unsigned long CRCaccum = 0;

	for (j=0; j<size; j++)
		{
		i = ((int)(CRCaccum>>24)^(*ptr++))&0xff;
		CRCaccum = (CRCaccum<<8)^CRCtable[i];
		}
	return CRCaccum;
}

/**************************************************************************
	FUNCTION:	getFileFromStack()
	PURPOSE:	Get ptr to (sub)file from inside flatstack file
	PARAMETERS:	Ptr to flatstack file, name of (sub)file
	RETURNS:	Ptr to base of required file
**************************************************************************/

char *getFileFromStack(char *stackFile, char *name)
{
	unsigned long 	crc;
	int				loop, numFiles, *iPtr;

	crc = str2CRC(name);
	iPtr = (int *)stackFile;
	numFiles = iPtr[1];
	for(loop=0; loop<numFiles; loop++)
	{
		if (iPtr[2+loop*3]==crc)
		{
//			debugPrintf("STACK FILE: %s\n", name);
			return stackFile+iPtr[2+loop*3+1];
		}
	}
	debugPrintf("Couldn't find '%s' in stack file\n", name);
	return NULL;
}
/**************************************************************************
	FUNCTION:	pointInPoly()
	PURPOSE:	Find if a point is in a poly
	PARAMETERS:	x,y of point, number of points, and a list of points
	RETURNS:	yes or no
**************************************************************************/
UBYTE pointInTri(long x, long y,Point2DType *edge)
{
LONG x0,x1,y0,y1,xx,yy;
ULONG inside=0,i;
	//DB("Hit=(%d,%d) ", x, y);
//	numOfPoints=3;

	// Move point in by one stops falling through cracks
	xx=(edge[0].x+edge[1].x+edge[2].x)/3;
	yy=(edge[0].y+edge[1].y+edge[2].y)/3;
	if (x>xx) x--;
	else x++;
	if (y>yy) y--;
	else y++;
 	i=4-1;
	while(i>0)
	{
		i--;
		x0=edge[i].x;
		y0=edge[i].y;
		x1=edge[(i+1)MOD 3].x;
		y1=edge[(i+1)MOD 3].y;

		//DB("[%d]=(%d,%d) ", i, x0,y0);
		if((y0>=y) != (y1>=y)) //so both y's are either > or < than y
		{
			if((x0>=x) == (x1>=x)) //so both x's are either > or < than x
			{
				if((x0>=x))inside++;
			}
			else //x's straddle y axis, need to check which side point is on
			{
				if( (x1 - (y1-y) * ( x0 - x1 ) / (y0 - y1)) >= x)inside++;
			}
		}
	}
	return inside&1;		
}
/**************************************************************************/
UBYTE pointInPoly(long x, long y, long numOfPoints, Point2DType *edge)
{
LONG x0,x1,y0,y1;
ULONG inside=0,i;
	//DB("Hit=(%d,%d) ", x, y);
	i=numOfPoints-1;
	while(i>0)
	{
		i--;
		x0=edge[i].x;
		y0=edge[i].y;
		x1=edge[(i+1)].x;
		y1=edge[(i+1)].y;

		//DB("[%d]=(%d,%d) ", i, x0,y0);
		if((y0>=y) != (y1>=y)) //so both y's are either > or < than y
		{
			if((x0>=x) == (x1>=x)) //so both x's are either > or < than x
			{
				if((x0>=x))inside++;
			}
			else //x's straddle y axis, need to check which side point is on
			{
				if( (x1 - (y1-y) * ( x0 - x1 ) / (y0 - y1)) >= x)inside++;
			}
		}
	}
	return inside&1;		
}
/**************************************************************************
	FUNCTION:	pointInPoly3D()
	PURPOSE:	Find if a point is in a poly
	PARAMETERS:	x,y of point, number of points, and a list of points
	RETURNS:	yes or no
**************************************************************************/

UBYTE pointInPoly3D(long x, long y, long numOfPoints, Point3DType *edge)
{
	LONG x0,x1,y0,y1;
	ULONG inside=0,i;
	
	i=numOfPoints-1;
	while(i>0)
	{
		i--;

		x0=edge[i].x;
		y0=edge[i].z;
		x1=edge[(i+1)].x;
		y1=edge[(i+1)].z;

		if((y0>=y) != (y1>=y)) //so both y's are either > or < than y
		{
			if((x0>=x) == (x1>=x)) //so both x's are either > or < than x
			{
				if((x0>=x))inside++;
			}
			else //x's straddle y axis, need to check which side point is on
			{
				if( (x1 - (y1-y) * ( x0 - x1 ) / (y0 - y1)) >= x)inside++;
			}
		}
	}
	return inside&1;		
}


/**************************************************************************
	FUNCTION:	intersectLines()
	PURPOSE:	Find intersection of two lines
	PARAMETERS:	Line end points, actual point return ptrs
	RETURNS:	0/1
**************************************************************************/

UBYTE intersectLines(long x1,long y1,long x2,long y2,long x3,long y3,long x4,long y4, long *x,long *y)
{
	long	Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;

	Ax = x2-x1;
	Bx = x3-x4;
	Ay = y2-y1;
	By = y3-y4;
	Cx = x1-x3;
	Cy = y1-y3;
	d = By*Cx-Bx*Cy;
	f = Ay*Bx-Ax*By;
	if (f>0)
	{
		if ((d<0)||(d>f))
			return 0;
	}
	else
	{
		if ((d>0)||(d<f))
			return 0;
	}
	e = Ax*Cy-Ay*Cx;
	if (f>0)
	{
		if ((e<0)||(e>f))
			return 0;
	}
	else
	{
		if ((e>0)||(e<f))
			return 0;
	}
	if (f==0)
		return 0;
	num = d*Ax;
	offset = SAMESIGN(num,f)?f/2:-f/2;
	*x = x1+(num+offset)/f;
	num = d*Ay;
	offset = SAMESIGN(num,f)?f/2:-f/2;
	*y = y1+(num+offset)/f;
	return 1;
}


/**************************************************************************
	FUNCTION:	intersectVectPoly()
	PURPOSE:	Find intersection of vector and poly
	PARAMETERS:	Line end points, poly, point return ptrs
	RETURNS:	0/1
**************************************************************************/

UBYTE intersectVectPoly(long x0,long y0, long x1,long y1, long numOfPoints, Point2DType *edge, long *x, long *y)
{
	long		loop;

	for(loop=0; loop<numOfPoints-1; loop++)
	{
		if (intersectLines(x0,y0,x1,y1, edge[loop].x,edge[loop].y,edge[loop+1].x,edge[loop+1].y, x,y))
			return 1;
	}
	return 0;
}

/**************************************************************************
	FUNCTION:	intersectVectPoly3D()
	PURPOSE:	Find intersection of vector and poly
	PARAMETERS:	Line end points, poly, edge return ptrs
	RETURNS:	0/1
**************************************************************************/

int intersectVectPoly3D(int x0,int z0, int x1,int z1, long numOfPoints, Point3DType *edge)
{
	int loop;
	long x,z;

	for(loop=0; loop<numOfPoints-1; loop++)
	{
		if (intersectLines(x0,z0,x1,z1, edge[loop].x,edge[loop].z,edge[loop+1].x,edge[loop+1].z, &x,&z))
		{
			return loop;
		}
	}
	return -1;
}


/**************************************************************************
	FUNCTION:	interpolateVectPoly()
	PURPOSE:	Find intersection of vector and poly
	PARAMETERS:	Line end points, poly, point return ptrs
	RETURNS:	0/1
**************************************************************************/

void findScrapeVector(Point2DType* moveVec, Point2DType* edgeVec)
{
	long	dot, lenEdge, scrape,calc;

	dot = moveVec->x*edgeVec->x + moveVec->y*edgeVec->y;
	
	//lenEdge = fast_sqrt(edgeVec->x*edgeVec->x + edgeVec->y*edgeVec->y)>>16;
	calc=edgeVec->x*edgeVec->x + edgeVec->y*edgeVec->y;
	FASTSQRT(lenEdge,calc);
	lenEdge>>=16;
	scrape = dot/lenEdge;
	moveVec->x = (edgeVec->x*scrape)/lenEdge;
	moveVec->y = (edgeVec->y*scrape)/lenEdge;
}


/**************************************************************************
	FUNCTION:	interpolateVectPoly()
	PURPOSE:	Find intersection of vector and poly
	PARAMETERS:	Line end points, poly, point return ptrs
	RETURNS:	0/1
**************************************************************************/

UBYTE interpolateVectPoly(long x0,long y0, long x1,long y1, long numOfPoints, Point2DType *edge, long *x, long *y)
{
	long		loop;

	Point2DType m,l;

	for(loop=0; loop<numOfPoints-1; loop++)
	{
		if (intersectLines(x0,y0,x1,y1, edge[loop].x,edge[loop].y,edge[loop+1].x,edge[loop+1].y, x,y))
		{
			m.x = x1-x0;
			m.y = y1-y0;
			l.x = edge[loop+1].x-edge[loop].x;
			l.y = edge[loop+1].y-edge[loop].y;
			findScrapeVector(&m,&l);
			*x = m.x;
			*y = m.y;
			return 1;
		}
	}
	return 0;
}


/**************************************************************************
	FUNCTION:	interpolateVectPoly3D()
	PURPOSE:	Find intersection of vector and poly
	PARAMETERS:	Line end points, poly, point return ptrs
	RETURNS:	0/1
**************************************************************************/

UBYTE interpolateVectPoly3D(long x0,long y0, long x1,long y1, long numOfPoints, Point3DType *edge, long *x, long *y)
{
	long		loop;

	Point2DType m,l;

	for(loop=0; loop<numOfPoints-1; loop++)
	{
//		ang = calc_angle(x0-x1,y0-y1);//just for checks

		if (intersectLines(x0,y0,x1,y1, edge[loop].x,edge[loop].z,edge[loop+1].x,edge[loop+1].z, x,y))
		{
//			ang2=calc_angle(x0-*x,y0-*y);
			
//			if(ang!=ang2)
 //			{
 //				debugPrintf("1\n");
 //			  	return 0;//ignor the bugger!
 //			}
 //			else
 //				debugPrintf("2\n");
		
			m.x = x1-x0;
			m.y = y1-y0;
			l.x = edge[loop+1].x-edge[loop].x;
			l.y = edge[loop+1].z-edge[loop].z;
			findScrapeVector(&m,&l);
			*x = m.x;
			*y = m.y;
			return 1;
		}
	}
	return 0;
}



/**************************************************************************
	FUNCTION:	interpolateTriangle()
	PURPOSE:	for finding the height at a x,z in a poly3
	PARAMETERS:	list of 3d points, and x,z co-ord of point
	RETURNS:	
**************************************************************************/

int interpolateTriangle(Point3DType *pList, LONG x, LONG z)
{
	UBYTE count;
	ULONG loop;

	LONG  xdist,ydist,zdist,divide,edgey[2],edgex[2];

	count=0;

	//z interpolation

	for(loop=0; loop < 3; loop++)
	{
		if(count==2)continue;

		if((pList[loop].z<=z) != (pList[(loop+1) MOD 3].z<=z)) //edge covers z
		{
			xdist = (pList[(loop+1) MOD 3].x-pList[loop].x);
			ydist = (pList[(loop+1) MOD 3].y-pList[loop].y);
			zdist = (pList[(loop+1) MOD 3].z-pList[loop].z);
	
			zdist*=4096;
			divide=z-pList[loop].z;
			if(divide==0)
				return -1;
			zdist/=divide;

			edgex[count]=((xdist*4096)/zdist)+pList[loop].x;
			edgey[count++]=((ydist*4096)/zdist)+pList[loop].y;
		}
	}
	if(count<2)return -1;

	//x interpolation
	
	xdist = (edgex[1] - edgex[0]);
	ydist = (edgey[1] - edgey[0]);	
	
	xdist*=4096;
	divide=x-edgex[0];
	if(divide==0)
		return -1;
	xdist/=divide;

	return ((ydist*4096)/xdist)+edgey[0];
}




int findShortestAngle(int ang1, int ang2)
{
	int temp = ang1 - ang2;

	if ((temp > -2048) && (temp <= 2048))
		return temp;
	else if (temp > 2048)
		return ang1 - ang2 - 4096;
	else
		return ang1 + 4096 - ang2;
}

char sFloat[32];
char sTemp[16];

long pFraction[12]={
500000000,
250000000,
125000000,
62500000,
31250000,
15625000,
7812500,
3906250,
1953125,
976563,
488281,
244141};

char *printFixed(long l)
{
	int bit,nc;
	int dRem=1000000000;// needs to be 1 billion
	int rem=l&4095;
	int div=ABS(l/4096);

	if(l<0)
	{
		nc=sprintf(sFloat, "-%d.", div);
		rem=-rem;
	}
	else
		nc=sprintf(sFloat, "%d.", div);


	for(bit=0; bit<12; bit++)
	{
		if(rem&2048)
			dRem+=pFraction[bit];
		rem=rem<<1;
	}
	sprintf(sTemp, "%d", dRem);
	strncpy(sFloat+nc, sTemp+1, 5);// change this for more decimal places

	return(sFloat);
}

void *align4(void *pn)
{
	long n=(long)pn;
	long m=n&3;
	if(m)
		return(void*)(n+(4-m));
	else
		return(void*)(n);
}

int isObjectInBox(VECTOR *pPos, VECTOR *pSize, VECTOR *pObjPos)
{
	VECTOR objZ;

	//DB("BOX POS=%d,%d,%d\n", pPos->vx, pPos->vy, pPos->vz);
	//DB("OBJ POS=%d,%d,%d\n", pObjPos->vx, pObjPos->vy, pObjPos->vz);

	SUBVECTOR(&objZ, pObjPos, pPos);
	
	if((objZ.vx<0) || (objZ.vx>pSize->vx)) return FALSE;
	if((objZ.vy<0) || (objZ.vy>pSize->vy)) return FALSE;
	if((objZ.vz<0) || (objZ.vz>pSize->vz)) return FALSE;

	return TRUE;
}

/*
#define AIMATHS_SQRT(N) (fast_sqrt(N)>>16)

extern int CheckForLineCollision(const VERT * const start, const VERT * const end, VERT * const object_pos, int radius)
{
	int i;

	VECTOR ul;		// unit vector of line
	long scalar_se;	// scalar length of line start to end

	// create the unit vector from start to end
	ul.vx = end->vx - start->vx;
	ul.vy = end->vy - start->vy;
	ul.vz = end->vz - start->vz;
	scalar_se = (ul.vx*ul.vx) + (ul.vy*ul.vy) + (ul.vz*ul.vz);
	scalar_se = AIMATHS_SQRT(scalar_se);

	if (!scalar_se)
	{
		DB("Start to End has a length of 0!\n\n");
		return 0;
	}

	ul.vx <<= 12;
	ul.vy <<= 12;
	ul.vz <<= 12;
	ul.vx /= scalar_se;
	ul.vy /= scalar_se;
	ul.vz /= scalar_se;
	

	{
			VECTOR sp;		// vector for start to point p
			long scalar_p;	// scalar length along line to perpendicular point p
			long scalar_sp;	// scalar length of line start to test point p
			long dist;

			// So far we have ul, a fixed point unit vector.
			// Fill in sp
			sp.vx = formation[0].object_list[i].pos.vx - start->vx;
			sp.vy = formation[0].object_list[i].pos.vy - start->vy;
			sp.vz = formation[0].object_list[i].pos.vz - start->vz;
			// and dot with the unit vector to get the scalar distance along start to end
			// to the point on the line perpendicular to the test point
			scalar_p = (sp.vx*ul.vx) + (sp.vy*ul.vy) + (sp.vz*ul.vz);
			// this scalar length is still in fixed point so scale it back down
			scalar_p >>= 12;
			// Do a couple of checks to see if we're before the start,
			if (scalar_p < 0)
				continue;
			// Or after the end.
			if (scalar_p > scalar_se)
				continue;
			scalar_sp = (sp.vx*sp.vx) + (sp.vy*sp.vy) + (sp.vz*sp.vz);
			scalar_sp = AIMATHS_SQRT(scalar_sp);
			// using pythag to solve a right angled triangle
			dist = AIMATHS_SQRT((scalar_sp*scalar_sp) - (scalar_p*scalar_p));
			if (dist <= formation[0].radius)
			{
//				PRINTF("start to point = %d\n", scalar_sp);
//				PRINTF("start to perp = %d\n", scalar_p);
//				PRINTF("dist = %d, radius = %d\n", dist, formation[0].radius);
				formation[0].object_list[i].on = 0;
				object_pos->vx = formation[0].object_list[i].pos.vx;
				object_pos->vy = formation[0].object_list[i].pos.vy;
				object_pos->vz = formation[0].object_list[i].pos.vz;
				// only one collision allowed so return here
				return 1;
			}
	
	}
	return 0;
}
*/