/*																									*/
/*	RDSGEN.C - Random-Dot Stereogram Generator										*/
/*																									*/
/*	Version 1.2																					*/
/*																									*/
/*	Written by: Fred Feucht																	*/
/*																									*/
/*																									*/
/*	This program will take a type 2 TARGA or GIF file as input and 			*/
/*	generate a type 2 TARGA or GIF output file as an RDS.							*/
/*																									*/
/*	The original concept comes from RDS.C by Alexander R. Enzmann, which I	*/
/* found	to be too inflexible.  RDS algorithm one is a modification of		*/
/*	the routine documented by Paul McMahon in "The Emporors New Clothes".	*/
/* Algorithms two and four are original.  Algorithm three is based on a		*/
/*	routine authored by Thimbleby, Inglis, and Witten at the University of	*/
/*	Waikato in New Zealand.  The program has been enhanced to support the	*/
/* GIF file format, for both input and output, with the additions of GIF   */
/* encoding and decoding routines from TGA2GIF and POVRay respectively     */
/* (authors are mentioned below).														*/
/*																									*/
/*	My thanks to all the previous authors whose code fragments appear 		*/
/*	herein.  I have given credit wherever possible to original authors.		*/
/* To those not specifically mentioned, I am grateful as well.					*/
/*																									*/
/* Permission is given by the author to freely redistribute and include		*/
/* this code in any program as long as this credit is given where due.		*/
/*																									*/
/* GIF and 'Graphics Interchange Format' are trademarks (tm) of				*/
/* Compuserve, Incorporated, an H&R Block Company.									*/
/*																									*/
/***************************************************************************/
/*																									*/
/*	Revisions for release 1.1B																*/
/*																									*/
/*																									*/
/*	Additional RDS algorithms 	/a switch												*/
/*																									*/
/*	Random color background		/c switch												*/
/*																									*/
/*	GIF background map			/m switch												*/
/*																									*/
/*	Depth of field control		/f switch												*/
/*																									*/
/*																									*/
/*																									*/
/*																									*/
/*	Revisions for release 1.2B																*/
/*																									*/
/*																									*/
/*	Additional RDS algorithms 	/a switch												*/
/*																									*/
/*	Type 2 TGA output				/t switch												*/
/*																									*/
/*	Width option					/w switch												*/
/*																									*/
/*	Background shift control	/x switch												*/
/*																									*/
/*	Depth map shift control		/y switch												*/
/*																									*/
/*	Background fill function	/e switch												*/
/*																									*/
/*																									*/


#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <math.h>
#include <ctype.h>
#include <graphics.h>

#include "rdsgen.h"

/*							*/
/* Global variables	*/
/*							*/

static int					stripc, density, direction, outfile, display, field;
static int					dshift, bshift, expand, origin;
static int					color_back, seed, algorithm, adapt, index_points;
static int					stripw, intype, point_max, map_file, scale;
static int					dispw, polyin;
static long					limit, zmax, zmin, newval, oldval, num, den;
static unsigned int		xres, yres;

static unsigned int *	depths;			/* one line of depth file data		*/ 
static unsigned int *	wdepths;			/* work array for depth map shift	*/
static unsigned char *	odata;			/* one line of GIF output data 		*/
static unsigned char *	rdata;			/* one line of red output data	   */
static unsigned char *	gdata;			/* one line of green output data		*/
static unsigned char *	bdata;			/* one line of blue output data		*/
static unsigned char *	wdata;			/* work array for background shift	*/

static int 					Width, Height;
static int 					curx, cury;
static long 				CountDown;
static int 					Pass = 0;
static int 					Interlace;

static FILE *				ofile;
static char *				oname;

static int *				same;

static int *				part_left;
static int *				part_right;

static int					sep;
static int					left, right, sl, sr;


/*								*/
/* input file stuff		*/
/*								*/

static FILE *				ifile;					/* input file handle					*/
static char *				iname;					/* input file name					*/

static unsigned char *	iemit_index;
static unsigned char * 	icmap;
static unsigned int		ftype, icmlen, icmsize, ipsize, idlen, iorient;
static int					icode_size,	iout_value, iold_code, ibad_code_count;

LOCAL WORD 					icurr_size;         	/* The current code size 			*/
LOCAL WORD 					iclear;             	/* Value for a clear code 			*/
LOCAL WORD 					iending;            	/* Value for a ending code 		*/
LOCAL WORD 					inew_codes;         	/* First available code 			*/
LOCAL WORD 					itop_slot;          	/* Highest code for current size */
LOCAL WORD 					islot;              	/* Last read code 					*/

LOCAL WORD 					ibyte_count = 0; 		/* # bytes left in block 			*/
LOCAL WORD 					ibit_count = 0;     	/* # bits left in current byte 	*/
LOCAL UTINY 				ibyte_buff[257];    	/* Current block 						*/
LOCAL UTINY *				ibyte_ptr;           /* Pointer to next byte in block */
LOCAL UTINY 				ibyte;  					/* current input byte		 		*/
LOCAL	UTINY					igifend;					/* end of object for gif input	*/

LOCAL UTINY *				idstack;					/* Stack for storing pixels 		*/
LOCAL UTINY *				isuffix;					/* Suffix table 						*/
LOCAL UWORD *				iprefix;					/* Prefix linked list 				*/

/*									*/
/* background file stuff	*/
/*									*/

static FILE *				bfile;					/* input file handle					*/
static char *				bname;					/* input file name					*/

static unsigned char *	bemit_index;
static int					bcode_size,	bout_value, bold_code, bbad_code_count;
static unsigned char * 	bcmap;
static unsigned int		bxres, byres, bcmlen, bcmsize;

LOCAL WORD 					bcurr_size;         	/* The current code size 			*/
LOCAL WORD 					bclear;             	/* Value for a clear code 			*/
LOCAL WORD 					bending;            	/* Value for a ending code 		*/
LOCAL WORD 					bnew_codes;         	/* First available code 			*/
LOCAL WORD 					btop_slot;          	/* Highest code for current size */
LOCAL WORD 					bslot;              	/* Last read code 					*/

LOCAL WORD 					bbyte_count = 0; 		/* # bytes left in block 			*/
LOCAL WORD 					bbit_count = 0;     	/* # bits left in current byte 	*/
LOCAL UTINY 				bbyte_buff[257];    	/* Current block 						*/
LOCAL UTINY *				bbyte_ptr;           /* Pointer to next byte in block */
LOCAL UTINY 				bbyte;  					/* current input byte		 		*/

LOCAL UTINY *				bdstack;					/* Stack for storing pixels 		*/
LOCAL UTINY *				bsuffix;					/* Suffix table 						*/
LOCAL UWORD *				bprefix;					/* Prefix linked list 				*/

/*								*/
/* output file stuff		*/
/*								*/

static unsigned char		idbuf[256];

static int n_bits;                        /* number of bits/code */
static int maxbits = BITS;                /* user settable max # bits/code */
static code_int maxcode;                  /* maximum code, given n_bits */
static code_int maxmaxcode = (code_int)1 << BITS; /* should NEVER generate this code */
static count_int htab [HSIZE];
static unsigned short codetab [HSIZE];

static code_int free_ent = 0;             /* first unused entry */
static int exit_stat = 0;

static int clear_flg = 0;

static int offset;
static long int in_count = 1;            	/* length of input */
static long int out_count = 0;           	/* # of codes output (for debugging) */

static int g_init_bits;
static FILE *g_outfile;

static int ClearCode;
static int EOFCode;

static code_int 			hsize = HSIZE; 	/* for dynamic table sizing */
static count_int 			fsize;

static unsigned long 	cur_accum = 0;
static int  				cur_bits = 0;

LOCAL ULONG code_mask[17] = {
  0,
  0x0001, 0x0003,
  0x0007, 0x000F,
  0x001F, 0x003F,
  0x007F, 0x00FF,
  0x01FF, 0x03FF,
  0x07FF, 0x0FFF,
  0x1FFF, 0x3FFF,
  0x7FFF, 0xFFFF
  };

static int red[256] = { 0x00, 0x00, 0x00, 0x00, 0x7F, 0x7F, 0x7F, 0x7F, 0x1F, 0x1F, 0x1F, 0x1F, 0xFF, 0xFF, 0xFF, 0xFF };

static int green[256] = { 0x00, 0x00, 0x7F, 0x7F, 0x00, 0x00, 0x1F, 0x7F, 0x1F, 0x1F, 0xFF, 0xFF, 0x1F, 0x1F, 0xFF, 0xFF };

static int blue[256] = { 0x00, 0x7F, 0x00, 0x7F, 0x00, 0x7F, 0x00, 0x7F, 0x1F, 0xFF, 0x1F, 0xFF, 0x1F, 0xFF, 0x1F, 0xFF };

const char GIFstr[] = "GIF87a";

const char POLYstr[] = "Polyray";	

/*                       						*/
/* Main processing routine 					*/
/*                       						*/

void main(argc, argv)

int argc;
char **argv;

{
	int	i, j;

	int	driver, mode, errcode;

	unsigned char * t;


	stripc = 8;					/* strip length = 1/8 of screen width */

   density = 50;				/* density 50 out of 100 pixels black	*/

	direction = 0;				/* normal picture orientation				*/ 

	outfile = 0;				/* output file is GIF format				*/

	display = 0;				/* do not display output while working */

	seed = 1;					/* random number seed						*/

	adapt = 0;					/* no background substitution				*/

	index_points = 0;			/* no indexing triangles in RDS output */
	
	point_max = 0;				/* size of index points						*/
	
	algorithm = 2;				/* use improved RDS algorithm				*/ 

	color_back = 0;			/* use black and white palette			*/
	
	map_file = 0;				/* no background map file 					*/
	
	field = 2;              /* field is 1/2 the distance to image	*/
	
	newval = 0xFFFF;			/* adaptive background replacement 		*/

	dispw = 10;             /* default display width 10 inches		*/

	polyin = 0;					/* input is not from polyray				*/

	origin = 0;					/* scan starts at column 0					*/

	bshift	= 0;			 	/* background shift value					*/

	dshift	= 0;			 	/* depth map shift value					*/

	expand = 0;					/* background expansion is off			*/

	if (argc < 3)
	{
		showparms();

		exit(0);
	}

	iname = argv[1];
   oname = argv[2];

	for(i=3; i<argc; i++)
	{
		if(argv[i][0] == '+' || argv[i][0] == '-' || argv[i][0] == '/')
		{
			switch (argv[i][1])
			{
				case	'?':	showparms();
								break;
				case	'a':
				case	'A':	if(argv[i][2] == '\0') error("Missing algorithm number\n");
								algorithm = atoi(argv[i]+2);
								if(algorithm < 1 || algorithm > 4) error("Algorithm number, %i, is out of range\n", algorithm);
								break;
				case	'b':
				case	'B':	if(argv[i][2] == '\0') error("Missing adaptive background substitution value\n");
								adapt = atoi(argv[i]+2);
								if(adapt < 1 || adapt > 64) error("Adaptive background offset, %i, is out of range\n", adapt);
								break;
				case	'c':
				case	'C':	color_back = 1;
								break;
				case	'd':
				case	'D':	if(argv[i][2] == '\0') error("Missing density value\n");
								density = atoi(argv[i]+2);
								if(density < 0 || density > 100) error("Density value, %i, is out of range\n", density);
								break;
				case	'e':
				case	'E':	expand = 1;
								break;
				case	'f':
				case	'F':	if(argv[i][2] == '\0') error("Missing depth of field value\n");
								field = atoi(argv[i]+2);
								if(field < 1 || field > 16) error("Depth of field value, %i, is out of range\n", field);
								break;
				case	'i':
				case	'I':	index_points = 1;
								break;
				case	'm':
				case	'M':	if(argv[i][2] == '\0') error("Missing map file name\n");
							   bname = &argv[i][2];
								map_file = 1;
								break;
				case	'n':
				case	'N':	direction = 1;
								break;
				case	'o':
				case	'O':	if(argv[i][2] == '\0') error("Missing origin value\n");
								origin = atoi(argv[i]+2);
								if(origin < 0) error("Origin value, %i, is out of range\n", origin);
								break;
			   case	'r':
				case	'R':	if(argv[i][2] == '\0') error("Missing random seed value\n");
								seed = atoi(argv[i]+2);
								break;
			   case	's':
				case	'S':	if(argv[i][2] == '\0') error("Missing strip count value\n");
								stripc = atoi(argv[i]+2);
								break;
				case	't':
				case	'T':	outfile = 1;
								break;
				case	'v':
				case	'V':	display = 1;
								break;
				case	'w':
				case	'W':	if(argv[i][2] == '\0') error("Missing display width value\n");
								dispw = atoi(argv[i]+2);
								if(dispw < 0 || dispw > 120) error("Display width value, %i, is out of range\n", dispw);
								break;
				case	'x':
				case	'X':	if(argv[i][2] == '\0') error("Missing background shift value\n");
								bshift = atoi(argv[i]+2);
								if(bshift < 0) error("Background shift value, %i, is out of range\n", bshift);
								break;
				case	'y':
				case	'Y':	if(argv[i][2] == '\0') error("Missing depth map shift value\n");
								dshift = atoi(argv[i]+2);
								if(dshift < 0) error("Depth map shift value, %i, is out of range\n", dshift);
								break;
				default:		error("Unknown option: %s\n", argv[i]);
			}
		}
		else error("Invalid switch\n");

	}

	if(map_file)
	{
		if(display) error("Video display is not available with bit-mapped background files\n");

		if(color_back) error("Random color and bit-mapped color are mutually exclusive\n");
	}

	if((origin > 0) & (algorithm == 3)) error("Origin option cannot be used with algorithm three\n");

	limit = (long) density * RAND_MAX / 100;

	if((seed < 1) || (seed > RAND_MAX)) error("Random number seed value, %i, is out of range\n", seed);

	srand(seed);
	
	ifile = fopen(iname, "rb");

	if (ifile == (FILE *)NULL)	error("Cannot open input file \"%s\".", iname);

	read_header_data(&xres, &yres);

	printf("xres: %d, yres: %d\n", xres, yres);
   
	printf("zmin: %u, zmax: %u\n", (unsigned) zmin, (unsigned) zmax);

	if((stripc < 1) || (stripc > xres)) error("Strip count value, %i, is out of range\n", stripc);

	stripw = xres / stripc;

	if(origin > xres-1) error("Origin value, %i, is out of range\n", origin);

	if(map_file)
	{
		bfile = fopen(bname, "rb");

		if (bfile == (FILE *)NULL)	error("Cannot open background map file \"%s\".", bname);

		read_background_header(&bxres, &byres);

		if(xres != bxres || yres != byres) error("Background map file resolution (%i x %i) does not match input resolution\n", bxres, byres);

		if(byres < stripw) error("Background map file resolution (%i x %i) is less than strip width, %i\n", bxres, byres, stripw);
	}

	point_max = yres >> 6;
	
	if(adapt) 
	{
		if(polyin)
		{
			oldval = (direction) ? 0 : 0xFFFF; 
		}
		else
		{
			oldval = (direction) ? 0xFFFF : 0;
		}

		newval = zmin - ((zmax - zmin) / adapt);

		zmin = newval;
	}
	
	if ((depths = (unsigned int *)malloc(xres * sizeof(unsigned int))) == NULL) error("Failed to allocate data row array\n");

	if ((odata = malloc(xres * sizeof(unsigned char))) == NULL) error("Failed to allocate the output image buffer\n");

	if(bshift)
	{
		if ((wdata = malloc(xres * sizeof(unsigned char))) == NULL) error("Failed to allocate the work array for background shift\n");
	}

	if(dshift)
	{
		if ((wdepths = malloc(xres * sizeof(unsigned int))) == NULL) error("Failed to allocate the work array for depth map shift\n");
	}

	if(outfile)
	{
   	if ((rdata = malloc(xres * sizeof(unsigned char))) == NULL) error("Failed to allocate the red image buffer\n");
   	if ((gdata = malloc(xres * sizeof(unsigned char))) == NULL) error("Failed to allocate the green image buffer\n");
   	if ((bdata = malloc(xres * sizeof(unsigned char))) == NULL) error("Failed to allocate the blue image buffer\n");
	}

	num = (zmax - zmin) * field + zmin;				/* numerator for depth calculation		*/

	den = 2 * (zmax - zmin) * field + zmin;		/* denumerator for depth calculation	*/

	scale = (xres * 5) / (dispw * 2);				/* scale for depth calculation			*/

	igifend = 0;											/* no gif end of object yet 				*/

	if(algorithm == 3)
	{
		if((same = malloc(xres * sizeof(int))) == NULL) error("Unable to allocate constraint array\n");

		stripw = scale >> 1;								/* strip width for index points			*/
	}

	if(map_file)
	{	
		for(i=0, j=0; i<256; i++)
		{
			red[i]	= bcmap[j++];
			green[i] = bcmap[j++];
			blue[i]	= bcmap[j++];
		}
	}
	else
	{
		if(!color_back)
		{	
			for(i=0; i<256; i++)
			{
				red[i]	= i;
			  	green[i] = i;
				blue[i]	= i;
			}
		}
	}

	if(outfile)
	{
		printf("Generating TGA output file\n");
	}
	else
	{
		printf("Generating GIF output file\n");
	}

   if(display)
	{
		switch(xres)
		{
			case 320:	if(yres != 200) error("Unable to display %i by %i image\n", xres, yres); 
							driver = CGA;
							mode = 1;	
							break;
			case 640:	if(yres == 480)
							{
								driver = VGA;
								mode = 2;
								break;
							}
							driver = EGA;
							if(yres == 350)
							{
								mode = 1;
								break;
							}
							if(yres == 200)
							{
								mode = 0;
								break;
							}
			default:		error("Unable to display %i by %i image\n", xres, yres); 
		}

		initgraph(&driver, &mode, 0);

		errcode = graphresult();

		if(errcode != grOk)
		{
			printf("%s\n", grapherrormsg(errcode));
			exit(0);
		}
	}

	if(outfile == 1)
	{
		TGAEncode(oname,						/* file name			*/
					 xres,yres);				/* image size			*/
	}
	else
	{
		GIFEncode(oname,				   	 /* file name 			*/
					 xres, yres,        	    /* image size 		*/
					 0,                      /* no interlace 		*/
					 0,                      /* bkg color 			*/
					 8,                      /* bits per pixel 	*/
					 red, green, blue,		 /* palette arrays 	*/
					 get_pix);					 /* pixel function 	*/
	
	}

	if(display == 0)
	{
		printf("\n");
	}
	else
	{
		beep();
	
		while(!kbhit());

		closegraph();
	}

	if(map_file) fclose(bfile);

	fclose(ifile);
}

/* 				                    														*/
/*  Generate a line of RDS from a line of depth data.								*/
/*       		  						  														*/	
/*  Four RDS algorithms are available.													*/	
/*       		  						  														*/	
/*  All algorithms: 						  													*/	
/*       		  						  														*/	
/*	 First just generate random dots of background map across the line		*/
/*																									*/
/*	 Next go through depth data, adjusting pixels according to the				*/
/*	 relative depth at each point.  Depth data is scanned first left			*/
/*  then right from the origin column.													*/	
/*																									*/



void gen_rds_line(int width)
{
	int				d, e, i, j, n, m, o, w;

	long				inc, dt;

	float				b, c;

	unsigned int	k;

	unsigned char	r1, g1, b1, r2, g2, b2;

	unsigned long  a, l, x, y, z;

	/*                      */
	/* initialize variables */
	/*                      */

	w = stripw / field;								/* limit useable strip by depth of field	*/

	z = zmax - zmin;									/* calculate useable portion of strip		*/

	/*                      */
	/* generate background	*/
	/*                      */

	if(map_file)
	{
		for(i=0; i<width; i++)						/* get dots from background map				*/
		{
			if((k = bget_map()) == bending) error("Premature EOF in map file, %s\n", bname);

			odata[i] = k;
		}
	}
	else
	{
		if(color_back)								/* if random color background		*/
		{
			for(i=0; i<width; i++) odata[i] = ((long) rand() << 4) / RAND_MAX;
		}
		else											/* if back and white background	*/
		{
			for(i=0; i<width; i++) odata[i] = (rand() < limit) ? 0 : 255;
		}
	}

	/*                      */
	/* rotate background		*/
	/*                      */

	if(bshift)
	{
		for(i=0; i<width; i++) wdata[i] = odata[i];

		for(i=width-bshift, j=0; i<width; i++, j++) odata[j] = wdata[i];

		for(i=0; i<width-bshift; i++, j++) odata[j] = wdata[i];
	}

	/*                      */
	/* rotate depth map		*/
	/*                      */

	if(dshift)
	{
		for(i=0; i<width; i++) wdepths[i] = depths[i];

		for(i=width-dshift, j=0; i<width; i++, j++) depths[j] = wdepths[i];

		for(i=0; i<width-dshift; i++, j++) depths[j] = wdepths[i];
	}

  	/*                      */
	/* generate RDS line		*/
	/*                      */
	
	if(algorithm == 1)
	{
		n = width;											/* rightmost pixel so far			*/

		e = 0;	 			 								/* leftmost pixel so far		*/

		for(i=origin-1; i>=0; i--)
		{
			l = depths[i];									/* extract depth value	 	 	*/
				
			o = (((l - zmin) * w) / z);				/* scale to strip width			*/

			d = (i - stripw + o);						/* calculate displacement to corresponding pixel */

			if(d >= 0)										/* if left pixel visible		*/
			{
				if(d < n)									/* if both pixels visible		*/
				{
					odata[d] = odata[i];					/* copy depth adjusted pixel from the right		 */

					n = d;									/* new rightmost pixel			*/

					if(expand)
					{
						for(j=d; j<e-1; j++)
						{
							odata[j+1] = odata[j];		/* fill-in missing pixels		*/
						}
						e = d;
					}
				}
			}
		}

		n = 0;												/* initialize rightmost pixel	*/

		e = width;											/* initialize leftmost pixel	*/
	
		for(i=origin; i<width; i++)
		{
			l = depths[i];									/* extract depth value			*/
				
			o = (((l - zmin) * w) / z);				/* scale to strip width			*/

			d = (i - stripw + o);						/* calculate displacement to corresponding pixel */

			if(d >= 0)										/* if left pixel visible		*/
			{
				if(d > n)			  						/* if from pixel left of last from pixel			 */ 
				{	
					odata[i] = odata[d];					/* copy depth adjusted pixel from the left		 */

					n = d;				  					/* new leftmost pixel			*/
				}
				else
				{
					if(expand)
					{
						odata[i] = odata[i-1];				/* fill-in missing pixels			*/
					}
				}
			}
		}
	}

	if(algorithm == 2)
	{
		n = width;												/* rightmost pixel so far			*/

		e = 0;	 												/* leftmost pixel so far			*/

		for(i=origin-1; i>=0; i--)
		{
			l = depths[i];										/* extract depth value 	 			*/
		  
			o = (num - l) * scale / (den - l);			/* calculate separation				*/

			d = i - (o >> 1);									/* left pixel is 1/2 offset back	*/

			if((d > -1) && ((d+o) < width))				/* if both pixels visible			*/								
			{
				if(d+o < n)										/* if visible by both eyes			*/
				{
					odata[d] = odata[d+o];					/* propagate pixel backward		*/

					n = d+o;										/* new rightmost pixel				*/

					if(expand)
					{
						for(j=d; j<e-1; j++)
						{
							odata[j+1] = odata[d+o];		/* fill-in missing pixels			*/
						}
						e = d;
					}
				}
			}
		}

		n = 0;													/* leftmost pixel	so far			*/

		e = width;												/* rightmost pixel so far			*/

		for(i=origin; i<width; i++)
		{
			l = depths[i];										/* extract depth value 	 			*/
		  
			o = (num - l) * scale / (den - l);			/* calculate separation				*/

			d = i - (o >> 1);									/* left pixel is 1/2 offset back	*/

			if((d > -1) && ((d+o) < width))				/* if both pixels visible			*/								
			{
				if(d > n)										/* if visible by both eyes			*/
				{
					odata[d+o] = odata[d];					/* propagate pixel forward			*/

					n = d;										/* new leftmost pixel				*/
				
					if(expand)
					{
						for(j=e+1; j<d+o; j++)
						{
							odata[j] = odata[d];				/* fill-in missing pixels			*/
						}
						e = d+o;
					}
				}
			}
		}
	}

	if(algorithm == 3)
	{
		/* initialize same array */
		
		for(i=0; i<width; i++) same[i] = i;

		/* scan line for pixel constraints */

		for(i=0; i<width; i++)
		{
			l = depths[i];											/* extract depth value						*/

			sep = (num - l) * scale / (den - l);			/* calculate separation length			*/

			left = i - sep / 2;									/* left is current - 1/2 separation		*/
			right = sep + left;									/* right is left plus separation			*/

			if(left >= 0 && right < width)					/* if both pixels on the screen			*/
			{
				w = 1;												/* assume point is visible					*/

				dt = depths[i] & 0xFFFF - zmin;				/* get relative depth value				*/

				inc = (16 * field * z - 8 * dt) / xres;	/* depth increase per unit of width		*/  

				for(j=1; dt<z; j++)								/* while relative depth within limits	*/
				{
					dt += inc;										/* increment relative depth value		*/

					l = dt + zmin;									/* convert to absolute depth value		*/

					if((i-j) >= 0 && depths[i-j] > l)		/* if on screen and occluded				*/
					{
						w = 0;										/* pixel is not visible (constrained)	*/
						break;
					}

					if((i+j) < width && depths[i+j] > l)	/* if on screen and occluded				*/
					{
						w = 0;										/* pixel is not visible (constrained)	*/ 
						break;
					}
				} 
				
				if(w)													/* if visible												*/
				{
					if(same[left] < right)						/* if previous constraint is left of new			*/ 
					{
						same[same[left]] = right;				/* previous node is constrained to new				*/

						same[left] = right;						/* new right-most constraint on this pixel		*/
					}
					else
					{
						same[right] = same[left];				/* right pixel is constrained to further right	*/
					}
				}
			}
		}
		
		for(i=width-1; i>=0; i--)				/* scan backwards					*/
		{
			if(same[i] != i)		 				/* if constrained					*/
			{
				odata[i] = odata[same[i]];		/* copy constrained pixel		*/
			}
		}
	}

	if(algorithm == 4)
	{
		b = z * field;											/* distance from screen to back plane	*/

		a = 2 * b + zmin;										/* adjusted depth value			  */

		m = xres >> 1; 										/* point of focus					  */

		n = width;												/* rightmost pixel so far		  */

		e = 0;													/* leftmost pixel so far		  */

		for(i=origin-1; i>=0; i--)
		{
			l = a - depths[i];							  	/* extract and adjust depth value		*/

			c = i - m;											/* calculate horizontal displacement	*/

			o = scale * (1.0 - sqrt(b*b + c*c) / l) + 0.5;	/* calculate separation	value		*/

			d = i - (o >> 1);									/* left pixel is 1/2 offset back	*/

			if((d > -1) && ((d+o) < width))				/* if both pixels visible			*/								
			{
				if(d+o < n)										/* if visible by both eyes			*/
				{
					odata[d] = odata[d+o];					/* propagate pixel backward		*/

					n = d+o;										/* new rightmost pixel				*/

					if(expand)
					{
						for(j=d; j<e-1; j++)
						{
							odata[j+1] = odata[d+o];		/* fill-in missing pixels			*/
						}
						e = d;
					}
				}
			}
		}

		n = 0;													/* leftmost pixel so far	*/

		e = width;												/* rightmost pixel so far	*/

		for(i=origin; i<width; i++)
		{
			l = a - depths[i];							  	/* extract and adjust depth value		*/

			c = i - m;											/* calculate horizontal displacement	*/

			o = scale * (1.0 - sqrt(b*b + c*c) / l) + 0.5;	/* calculate separation	value		*/

			d = i - (o >> 1);									/* left pixel is 1/2 offset back	*/

			if((d > -1) && ((d+o) < width))				/* if both pixels visible			*/								
			{
				if(d > n)										/* if visible by both eyes			*/
				{
					odata[d+o] = odata[d];					/* propagate pixel forward			*/

					n = d;										/* new leftmost pixel				*/
				
					if(expand)
					{
						for(j=e+1; j<d+o; j++)
						{
							odata[j] = odata[d];				/* fill-in missing pixels			*/
						}
						e = d+o;
					}
				}
			}
		}
	}
}


/*						                     	  	*/
/* Open a type 2 Targa for output.		 		*/
/*                					       		*/

void open_targa_file(char * oname, unsigned width, unsigned height)
{
	unsigned int	tcmlen;

   unsigned char 	tgaheader[18];

	memset(tgaheader, 0, 18);

	tcmlen = (color_back) ? 16 : 256;
   
	if ((ofile = fopen(oname, "wb")) == NULL)	error("Failed to open output file %s\n", oname);

	tgaheader[2] = 2;
	tgaheader[5] = (unsigned char) (tcmlen & 0xFF); 
	tgaheader[6] = (unsigned char) (tcmlen >> 8) & 0xFF; 
   tgaheader[12] = (unsigned char) (width & 0xFF);
   tgaheader[13] = (unsigned char) ((width >> 8) & 0xFF);
   tgaheader[14] = (unsigned char) (height & 0xFF);
   tgaheader[15] = (unsigned char) ((height >> 8) & 0xFF);
   tgaheader[16] = 24;
   tgaheader[17] = iorient;
   
	fwrite(tgaheader, 18, 1, ofile);
}

/*                       									  	*/
/* Write a line of points to a Targa file  				*/
/*										                       	*/

void write_targa_line(unsigned width)
{
   int i, j;

	for(i=0; i<width; i++)
	{
		j = odata[i];

		if(algorithm == 6)
		{
			fputc(bdata[i], ofile);
			fputc(gdata[i], ofile);
			fputc(rdata[i], ofile);
		}
		else
		{
			if(map_file)
			{
				j *= bcmsize;

				fputc(bcmap[j++], ofile);  	
				fputc(bcmap[j++], ofile);  	
				fputc(bcmap[j], ofile);  	
			}
			else
			{
				fputc(red[j], ofile);
				fputc(green[j], ofile);
				fputc(blue[j], ofile);
			}
		}
	}
}

/*							                       	*/
/* Read and evaluate one unit of input data	*/
/*                   							   */

unsigned int get_value()
{
	int 				i, j, k;

	register int	r, g, b;

	unsigned int 	val;

	unsigned char	bytes[4];


	if(intype)
	{
		/*												*/
		/* get input data from GIF decoder	*/
		/*												*/

		if((k = idecode_gif()) < 0) error("Error reading input file %s\n", iname);
	
		if(k == iending)
		{
			igifend = 1;
			
			return(iending);
		}

		k = k & 0xFF;

		j = icmsize * k;

		val = icmap[j++] << 8 | icmap[j];
	}
	else
	{
		/*												*/
		/* get input data from TGA file		*/
		/*												*/

		if (ftype == 2)
		{
			/*										  	*/
			/* input data is 8/16/24 bit rgb	*/
			/*										  	*/

			switch(ipsize)
			{
				case 1:	if((r = fgetc(ifile)) == EOF) error("Premature EOF reading input file: %s\n", iname);
							val = r << 8;
							break;

				case 2:	if((g = fgetc(ifile)) == EOF) error("Premature EOF reading input file: %s\n", iname);
							if((r = fgetc(ifile)) == EOF) error("Premature EOF reading input file: %s\n", iname);
               		val = r << 8 | g;
							break;

				case 3:	if((g = fgetc(ifile)) == EOF) error("Premature EOF reading input file: %s\n", iname);
							if((g = fgetc(ifile)) == EOF) error("Premature EOF reading input file: %s\n", iname);
							if((r = fgetc(ifile)) == EOF) error("Premature EOF reading input file: %s\n", iname);
               		val = r << 8 | g;
							break;

				default:	error("Invalid color map byte count, %i\n", ipsize);
			}
		}
		else
		{
			/*										  	*/
			/* input data is color map index	*/
			/*										  	*/

			if ((k = fgetc(ifile)) == EOF) error("Premature EOF reading input file: %s\n", iname);

			j = icmsize * k;

			if (ipsize == 2)
			{
				val = icmap[j++] | (icmap[j] << 8);
      	}
      	else
			{
				val = icmap[++j] | (icmap[++j] << 8);
      	}
   	}
	}

	if(direction) val = 65535 - val;

	return(val);
}


/*						                       			*/
/* Read next byte from background map file		*/
/*                						     			*/

unsigned int bget_map()
{
	int 				i, j;

	unsigned int 	k;


	if((k = bdecode_gif()) < 0) error("Error reading map file %s\n", bname);
	
	if(k == bending) return(bending);

	k = k & 0xFF;

	return(k);
}

		
/*						                       			*/
/* Add index points to top of image					*/
/*                						     			*/

void add_index(int line)
{
	int	i, c, d;

	c = point_max - line;

	d = ((xres - stripw) >> 1) - c;

	for(i=0; i<c<<1; i++) odata[d+i] = 0;

	d = ((xres + stripw) >> 1) - c;

	for(i=0; i<c<<1; i++) odata[d+i] = 0;
}

/*						                       			*/
/* Read a line's worth of the input file 			*/
/*                						     			*/

void	read_data_line(int width)
{
	int				i, j, k;

	unsigned int 	val;

	unsigned char	bytes[4];


	for (i=0;i<width;i++)
	{
		val = get_value();
	
		if(intype) if(igifend) error("Premature end of object reading input GIF file %s\n", iname);

		if(adapt) if(val == oldval) val = newval;

		depths[i] = val;
	}
}

/*          				           			*/
/* Read next entry for GIF output routine	*/
/*				                       			*/

int get_pix(int x, int y)
{
	int			i, val;

	static int	line = -1;	

	if(y != line)
	{
		line = y;
		
		if(display == 0) printf("Line: %d  \r", y);

		if(line > yres) error("Request for invalid input location [%i][%i]\n", x, y);

		read_data_line(xres);

		gen_rds_line(xres);

		if(index_points) if(y<point_max) add_index(y);

	   test_exit;

		if(display)
		{
			for(i=0; i<xres; i++)
			{
				putpixel(i, y, odata[i]);
			}
		}
	}

	val = odata[x];

	return(val);

}


/*          				           			*/
/* Read header portion of input file		*/
/*				                       			*/

void read_header_data(unsigned *xsize, unsigned *ysize)
{
	int				i, j, k, l;

	unsigned char 	header[18];

	unsigned char	bytes[4];

	int 				width, height;

	long				count, val, position;


	zmax = 0;
	zmin = 65536;

   if(fread(&header[0], 3, 1, ifile) != 1) error("Couldn't read header from input file: %s\n", iname);

	intype = strncmp((const char *) header, GIFstr, 3);

	intype = (intype) ? 0 : 1;

	if(intype)
	{
		if(fread(&header[3], 10, 1, ifile) != 1) error("Couldn't read GIF header from input file %s\n", iname);

		if(!(header[10] & 0x80)) error("Input file %s, has no color map\n", iname);

		icmlen 	= 1 << ((header[10] & 0x0F) + 1);
		icmsize	= 3; 

   	if (icmlen > 0)
		{
      	if ((icmap = malloc(sizeof(unsigned char)*icmsize*icmlen)) == NULL) error("Failed to allocate memory for color map\n");

			for (i=0;i<icmlen * icmsize;i++)
			{
         	if ((k = fgetc(ifile)) == EOF) error("Premature EOF in color map\n");
         
				icmap[i] = (unsigned char)k;
      	}
   	}

		k = 0;

		while(k != EOF)
		{
			switch(k = fgetc(ifile))
			{
			 	case ';':	k = EOF;
								break;

				case '!':	if((k = fgetc(ifile)) == EOF) error("Premature EOF in input file, %s\n", iname);
								if((k = fgetc(ifile)) == EOF) error("Premature EOF in input file, %s\n", iname);
								for(i=k; i>0; i--)  if((k = fgetc(ifile)) == EOF) error("Premature EOF in input file, %s\n", iname);
								break;

				case ',':	if (fread(header, 9, 1, ifile) != 1) error("Couldn't read object header from input file: %s\n", iname);

								width	 = header[4] | header[5] << 8;
								height =	header[6] | header[7] << 8;
								
								if ((header[8] & 0x80) == 0x80)
								{
									i = 1 << ((header[10] & 0x0F) + 1);
									for(; i<0; i++) if((k = fgetc(ifile)) == EOF) error("Premature EOF in input file, %s\n", iname);
								}
								
								position = ftell(ifile);
								
								if((k = ialloc_gif_stacks()) != 0) error("Unable to allocate stack space for GIF decoder\n");
	
								printf("scanning GIF input for depth ranges\n");
								
								if((val = iinit_gif_decoder()) != 0) error("Error %d, initializing GIF decoder\n", val);
								
								igifend = 0;

								val = get_value();

								while(!igifend)
								{
									if((!adapt) || (val != oldval))
									{
										if(zmax < val) zmax = val;
										if(zmin > val) zmin = val;
									}

									val = get_value();
								}

								if(ibad_code_count > 0) error("%d out of range codes encountered in GIF input file %s\n", ibad_code_count, iname);
								
								fseek(ifile, position, SEEK_SET);
								
								if((k = iinit_gif_decoder()) != 0) error("Error %d, reinitializing GIF decoder\n", k);
	
								k = EOF;
								
								break;

				default:		error("Unknown GIF format byte - %c\n", k);
			}
		}
	}
	else
	{
		if(fread(&header[3], 15, 1, ifile) != 1) error("Couldn't read TGA header from input file %s\n", iname);
	 
		idlen  	= header[0];
   	ftype  	= header[2];
   	icmlen	= header[5] | header[6] << 8;
   	icmsize	= header[7];
   	width  	= header[12] | header[13] << 8;
   	height 	= header[14] | header[15] << 8;
   	ipsize  	= header[16];	 
		iorient  = header[17] & 0x20;

   	if (!((ftype == 1 && ipsize <= 8) ||	(ftype == 2 && (ipsize == 16 || ipsize == 24)) ||	(ftype == 3 && ipsize == 8)))
		{
			error("Unsupported Targa type: %d\n", ftype);
		}

		if (icmlen > 256) error("Can't handle color maps of length %u\n", icmlen);

		if (icmlen > 0 && (icmsize != 16 && icmsize != 24)) error("Color maps entries must be 16 or 24 bits, not: %d\n", icmsize);
   	else icmsize /= 8;

   	if (ipsize != 8 && ipsize != 16 && ipsize != 24) error("%d bits/pixel not supported in height field, must be 8/16/24\n", ipsize);
   	else ipsize /= 8;

   	if (idlen > 0)
		{
			if (fread(idbuf, idlen, 1, ifile) != 1) error("Reading identification field of %s\n", iname);

			polyin = strncmp((const char *) idlen, POLYstr, 7);
		}

   	if (icmlen > 0)
		{
      	if ((icmap = malloc(sizeof(unsigned char)*icmsize*icmlen)) == NULL) error("Failed to allocate memory for color map\n");

			for (i=0;i<icmlen * icmsize;i++)
			{
         	if ((k = fgetc(ifile)) == EOF) error("Premature EOF in color map\n");
         
				icmap[i] = (unsigned char)k;
      	}
   	}

		if (ftype == 1 && icmap == NULL) error("Targa color map must have entries\n");

		position = ftell(ifile);

		printf("scanning TGA input for depth ranges\n");

		for(count= (long) width*height; count>0; count--)
		{
			val = get_value() & 0xFFFF;

			if((!adapt) || (val != oldval))
			{
				if(zmax < val) zmax = val;
				if(zmin > val) zmin = val;
			}
		}
	
		fseek(ifile, position, SEEK_SET);
	}

  	*xsize = width;
  	*ysize = height;
}


/*          				           			*/
/* Read header portion of background file	*/
/*				                       			*/

void read_background_header(unsigned *xsize, unsigned *ysize)
{
	int				i, j, k, l;

	unsigned char 	header[18];

	unsigned char	bytes[4];

	int 				width, height;

	long				count, val, position;


   if(fread(&header[0], 3, 1, bfile) != 1) error("Couldn't read header from map file: %s\n", bname);

	if((i = strncmp((const char *) header, GIFstr, 3)) != 0) error("Background map file, %s, is not in GIF format\n", bname);

	if(fread(&header[3], 10, 1, bfile) != 1) error("Couldn't read GIF header from map file %s\n", bname);

	if(!(header[10] & 0x80)) error("Background map file %s, has no color map\n", bname);

	bcmlen 	= 1 << ((header[10] & 0x0F) + 1);
	bcmsize		= 3; 

  	if (bcmlen > 0)
	{
     	if ((bcmap = malloc(sizeof(unsigned char)*bcmsize*bcmlen)) == NULL) error("Failed to allocate memory for color map\n");

		for (i=0;i<bcmlen * bcmsize;i++)
		{
        	if ((k = fgetc(bfile)) == EOF) error("Premature EOF in color map\n");
         
			bcmap[i] = (unsigned char)k;
     	}
  	}

	k = 0;

	while(k != EOF)
	{
		switch(k = fgetc(bfile))
		{
			case ';':	k = EOF;
							break;

			case '!':	if((k = fgetc(bfile)) == EOF) error("Premature EOF in map file, %s\n", bname);
							if((k = fgetc(bfile)) == EOF) error("Premature EOF in map file, %s\n", bname);
							for(i=k; i>0; i--)  if((k = fgetc(bfile)) == EOF) error("Premature EOF in map file, %s\n", bname);
							break;

			case ',':	if (fread(header, 9, 1, bfile) != 1) error("Couldn't read object header from map file: %s\n", bname);

							width	 = header[4] | header[5] << 8;
							height =	header[6] | header[7] << 8;
							
						  	*xsize = width;
						  	*ysize = height;

							if ((header[8] & 0x80) == 0x80)
							{
								i = 1 << ((header[10] & 0x0F) + 1);
								for(; i<0; i++) if((k = fgetc(bfile)) == EOF) error("Premature EOF in map file, %s\n", bname);
							}
							
							if((k = balloc_gif_stacks()) != 0) error("Unable to allocate stack space for GIF decoder\n");
	
							if((k = binit_gif_decoder()) != 0) error("Error %d, initializing GIF decoder\n", k);

							k = EOF;
							
							break;

			default:		error("Unknown GIF format byte - %c\n", k);
		}
	}
}


/* 				                    						*/
/*  Generate RDS from Targa depth data 				*/
/*       		  						  						*/	

void TGAEncode(char * oname, int width, int height)
{
   int 		i, j, k;

	open_targa_file(oname, width, height);

	for (i=0; i<height;i++)
	{
		if(display == 0) printf("Line: %d  \r", i);

		read_data_line(width);

		gen_rds_line(xres);

		if(index_points) if(i<point_max) add_index(i);

		if(display)
		{
			for(j=0; j<width; j++)
			{
				if(color_back)
				{
					putpixel(j, i, odata[j]);
				}
				else if(odata[j] == 255) putpixel(j, i, WHITE);
			}
		}

		test_exit;
		
		write_targa_line(width);
	}

	fclose(ofile);
}

/*                       						*/
/* Display command line parameters			*/
/*                       						*/

void	showparms()
{
	printf("\nUsage: rds input.ext output.ext options\n\n");
	printf("options: -a#       : Algorithm number, range 1 to 4 (default 2)\n");
	printf("         -b##      : Adaptive background value, range 1 to 64\n");
	printf("         -c        : Generate random 16-color background\n");
	printf("         -d###     : Density value, range 0 to 100 (default 50)\n");
	printf("         -e        : Extrapolate missing background pixels\n");
	printf("         -f##      : Depth of field value, range 1 to 16 (default 2)\n");
	printf("         -i        : Add indexing triangles to top of RDS\n");
	printf("         -mccc.ext : Background map file name\n");
	printf("         -n        : Produce a precedence reversed (negative) image\n");
	printf("         -o####    : Horizontal scan origin, range 0 to width (default 0)\n");
	printf("         -r#####   : Seed value for random generator, range 1-32767 (default 1)\n");
	printf("         -s###     : Strip count, range 1-width (default 8)\n");
	printf("         -t        : Generate type 2 TGA output file\n");
	printf("         -v        : Display image on video while processing\n");
	printf("         -w####    : Width of output image, range 0 to 120 inches (default 10)\n");
	printf("         -x####    : Background shift value, range 0 to width (default 0)\n");
	printf("         -y####    : Depth map shift value, range 0 to width (default 0)\n\n");
}


/*                       					*/
/* Beep, beep									*/
/*                       					*/

void beep()
{
	nosound();
	sound(1300);
	delay(80);
	sound(1600);
	delay(80);
	sound(1900);
	delay(80);
	nosound();
}

/*                       					*/
/* Display error message and exit		*/
/*                       					*/

void error(char *format, ...)
{
   va_list parms;
   
	/* fg_term(); */
   
	fprintf(stdout, "ERROR: ");

	va_start(parms, format);
   vfprintf(stdout, format, parms);
   va_end(parms);
   
	if(display) closegraph();

	exit(1);
}

/*																									*/
/*	GIF decoding routine																		*/
/*																									*/
/* This routine was borrowed from POVRAY which in turn borrowed the code 	*/
/* from FRACTINT.  It appears here in a somewhat modified format to 			*/
/*	conform to the requirements of my output driven logic.  Nevertheless,   */
/* I must give give appropriate credit to the orignal authors.					*/
/*																									*/
/* Based on :    	DECODER.C - An LZW decoder for GIF								*/
/*						Written by Steven A. Bennett										*/
/*						As inspired by Steve Wilhite										*/
/*						And modified by Bert Tyler and Timothy Wegner				*/
/* 																								*/

/*														*/
/* Get next byte of input for GIF decoder	*/
/* 													*/

int iget_byte()
{
	int	b;
	
	if((b = fgetc(ifile)) != EOF) return(b);

	printf("Premature EOF in GIF input file %s\n", iname);

	return(b);
}

/*														*/
/* get the next code from the GIF file		*/
/*														*/

WORD iget_next_code()
  {
  	WORD i, x;

  	ULONG ret;

	if (ibit_count == 0)
  	{
  		if (ibyte_count <= 0)
   	{
			/* Out of bytes in current block, so read next block */

	      ibyte_ptr = ibyte_buff;
      
			if ((ibyte_count = iget_byte()) < 0) return(ibyte_count);
      	else if (ibyte_count)
	      {		
   	   	for (i = 0; i < ibyte_count; ++i)
      	   {
         		if ((x = iget_byte()) < 0) return(x);
          	
					ibyte_buff[i] = (UTINY) x;
				}
   	   }
      }
    	ibyte = *ibyte_ptr++;
    
		ibit_count = 8;
    	--ibyte_count;
	}

  	ret = ibyte >> (8 - ibit_count);
  	
	while (icurr_size > ibit_count)
   {
   	if (ibyte_count <= 0)
      {
			/* Out of bytes in current block, so read next block */
      	
			ibyte_ptr = ibyte_buff;
      	
			if ((ibyte_count = iget_byte()) < 0) return(ibyte_count);
      	else if (ibyte_count)
        	{
        		for (i = 0; i < ibyte_count; ++i)
          	{
          		if ((x = iget_byte()) < 0) return(x);
          
					ibyte_buff[i] = (UTINY) x;
          	}
        	}
		}
    	
		ibyte = *ibyte_ptr++;
    	
		ret |= ibyte << ibit_count;
    	
		ibit_count += 8;
    	--ibyte_count;
	}
  	
	ibit_count -= icurr_size;
  	
	ret &= code_mask[icurr_size];
  	
	return((WORD)(ret));
}


/*									*/
/* Allocate stacks			*/
/*									*/

int ialloc_gif_stacks() 
{
	idstack = (UTINY *) malloc((MAX_CODES + 1)*sizeof(UTINY));
  	isuffix = (UTINY *) malloc((MAX_CODES + 1)*sizeof(UTINY));
  	iprefix = (UWORD *) malloc((MAX_CODES + 1)*sizeof(UWORD));

	return(0);
}


/*									*/
/* Release stacks				*/
/*									*/

void ifree_gif_stacks() 
{
	free(idstack);
  	free(isuffix);
  	free(iprefix);
}

/*														*/
/* Initialize for decoding a new image    */
/*														*/

int	iinit_gif_decoder()
{
  int		i, ret;


  ret = 0;
  
  if ((icode_size = iget_byte()) < 0) return(icode_size);

  if (icode_size < 2 || 9 < icode_size) return(BAD_CODE_SIZE);

  icurr_size = icode_size + 1;
  
  itop_slot = 1 << icurr_size;
  
  iclear = 1 << icode_size;
  
  iending = iclear + 1;
  
  islot = inew_codes = iending + 1;
  
  ibyte_count = ibit_count = 0;
  
  /* Initialize in case they forgot to put in a clear code.				*/
  /* (This shouldn't happen, but we'll try and decode it anyway...)	*/

  iold_code = iout_value = 0;

  ibad_code_count = 0;

  /* Set up the stack pointer and decode buffer pointer */

  iemit_index = idstack;

  for(i=0; i<MAX_CODES+1; i++) iprefix[i] = 0;
  for(i=0; i<MAX_CODES+1; i++) isuffix[i] = 0;

  return(ret);
}


/*													*/
/* Get next byte from GIF decoder		*/
/*													*/


int idecode_gif()

{
  	register int	c;
	register int	code;

  	/* This is the main loop.  For each code we get we pass through the
    * linked list of iprefix codes, pushing the corresponding "character" for
    * each code onto the stack.  When the list reaches a single "character"
    * we push that on the stack too, and then start unstacking each
    * character for output in the correct order.  Special handling is
    * included for the clear code, and the whole thing ends when we get
    * an ending code.
    */

   if(iemit_index > idstack) return(*(--iemit_index));

	while ((c = iget_next_code()) != iending)
   {
   	/* If we had a file error, return without completing the decode	*/

		if(c < 0) 
		return(0);

    	/* If the code is a clear code, reinitialize all necessary items	*/

		if(c == iclear)
      {
      	icurr_size = icode_size + 1;
      	islot = inew_codes;
      	itop_slot = 1 << icurr_size;

      	/* Continue reading codes until we get a non-clear code */
         /* (Another unlikely, but possible case...)				  */

			while ((c = iget_next_code()) == iclear);

	      /* If we get an ending code immediately after a clear code	*/
         /* (Yet another unlikely case), then break out of the loop.	*/

			if(c == iending) break;

			/* Finally, if the code is beyond the range of already set			*/
			/* codes, (This one had better NOT happen...  I have no idea 		*/
			/*	what will result from this, but I doubt it will look good... 	*/
			/* then set it	to color zero													*/

			if(c >= islot) c = 0;

      	iold_code = iout_value = c;

      	/* And let us not forget to put the character into the buffer		*/

			return(c);
		}
    	else
    	{
	 		/* In this case, it's not a clear code or an ending code, so			*/
      	/* it must be a code code...  So we can now decode the code into		*/
      	/* a stack of character codes. (Clear as mud, right?)						*/

			code = c;

      	/* Here we go again with one of those off chances...  If, on the		*/
	      /* off chance, the code we got is beyond the range of those already	*/
   	   /* set up (Another thing which had better NOT happen...) we trick		*/
      	/* the decoder into thinking it actually got the last code read.		*/
	      /* (Hmmn... I'm not sure why this works...  But it does...)				*/

			if(code >= islot)
			{
   	   	if(code > islot) ++ibad_code_count;
      	  	code = iold_code;
        		*iemit_index++ = (UTINY) iout_value;
	      }

   	   /* Here we scan back along the linked list of iprefixes, pushing		*/
     		/* helpless characters (ie. isuffixes) onto the stack as we do so.		*/
       
	      while (code >= inew_codes)
	      {
   	   	*iemit_index++ = isuffix[code];
      	  	code = iprefix[code];
	      }

	      /* Push the last character on the stack, and set up the new				*/
   	   /* iprefix and isuffix, and if the required slot number is greater		*/
      	/* than that allowed by the current bit size, increase the bit			*/
	      /* size.  (NOTE - If we are all full, we *don't* save the new			*/
   	   /* isuffix and iprefix...  I'm not certain if this is correct...			*/
      	/* it might be more proper to overwrite the last code...					*/

	      *iemit_index++ = (UTINY) code;

			if(islot < itop_slot)
      	{
	      	iout_value = code;
   	     	isuffix[islot] = (UTINY) iout_value;
      	  	iprefix[islot++] = iold_code;
	        	iold_code = c;
   	   }
	      
			if(islot >= itop_slot)
			{
				if(icurr_size < 12)
      	   {
         		itop_slot <<= 1;
          		++icurr_size;
	         }
			}

	      /* Now that we've pushed the decoded string (in reverse order)			*/
   	   /* onto the stack, lets pop it off and return it a byte at a 			*/
      	/* time to the caller																*/
       
   	   if(iemit_index > idstack) return(*(--iemit_index));
		}
	}
	return(c);
}


/*														*/
/* Get next byte of input for GIF decoder	*/
/* 													*/

int bget_byte()
{
	int	b;
	
	if((b = fgetc(bfile)) != EOF) return(b);

	printf("Premature EOF in GIF background file %s\n", bname);

	return(b);
}

/*																  	*/
/* get the next code from the background GIF file	*/
/*																	*/

WORD bget_next_code()
  {
  	WORD i, x;

  	ULONG ret;

	if (bbit_count == 0)
  	{
  		if (bbyte_count <= 0)
   	{
			/* Out of bytes in current block, so read next block */

	      bbyte_ptr = bbyte_buff;
      
			if ((bbyte_count = bget_byte()) < 0) return(bbyte_count);
      	else if (bbyte_count)
	      {		
   	   	for (i = 0; i < bbyte_count; ++i)
      	   {
         		if ((x = bget_byte()) < 0) return(x);
          	
					bbyte_buff[i] = (UTINY) x;
				}
   	   }
      }
    	bbyte = *bbyte_ptr++;
    
		bbit_count = 8;
    	--bbyte_count;
	}

  	ret = bbyte >> (8 - bbit_count);
  	
	while (bcurr_size > bbit_count)
   {
   	if (bbyte_count <= 0)
      {
			/* Out of bytes in current block, so read next block */
      	
			bbyte_ptr = bbyte_buff;
      	
			if ((bbyte_count = bget_byte()) < 0) return(bbyte_count);
      	else if (bbyte_count)
        	{
        		for (i = 0; i < bbyte_count; ++i)
          	{
          		if ((x = bget_byte()) < 0) return(x);
          
					bbyte_buff[i] = (UTINY) x;
          	}
        	}
		}
    	
		bbyte = *bbyte_ptr++;
    	
		ret |= bbyte << bbit_count;
    	
		bbit_count += 8;
    	--bbyte_count;
	}
  	
	bbit_count -= bcurr_size;
  	
	ret &= code_mask[bcurr_size];
  	
	return((WORD)(ret));
}


/*									*/
/* Allocate stacks			*/
/*									*/

int balloc_gif_stacks() 
{
	bdstack = (UTINY *) malloc((MAX_CODES + 1)*sizeof(UTINY));
  	bsuffix = (UTINY *) malloc((MAX_CODES + 1)*sizeof(UTINY));
  	bprefix = (UWORD *) malloc((MAX_CODES + 1)*sizeof(UWORD));

	return(0);
}


/*									*/
/* Release stacks				*/
/*									*/

void bfree_gif_stacks() 
{
	free(bdstack);
  	free(bsuffix);
  	free(bprefix);
}

/*														*/
/* Initialize for decoding a new image    */
/*														*/

int	binit_gif_decoder()
{
  int		i, ret;


  ret = 0;
  
  if ((bcode_size = bget_byte()) < 0) return(bcode_size);

  if (bcode_size < 2 || 9 < bcode_size) return(BAD_CODE_SIZE);

  bcurr_size = bcode_size + 1;
  
  btop_slot = 1 << bcurr_size;
  
  bclear = 1 << bcode_size;
  
  bending = bclear + 1;
  
  bslot = bnew_codes = bending + 1;
  
  bbyte_count = bbit_count = 0;
  
  /* Initialize in case they forgot to put in a clear code.				*/
  /* (This shouldn't happen, but we'll try and decode it anyway...)	*/

  bold_code = bout_value = 0;

  bbad_code_count = 0;

  /* Set up the stack pointer and decode buffer pointer */

  bemit_index = bdstack;

  for(i=0; i<MAX_CODES+1; i++) bprefix[i] = 0;
  for(i=0; i<MAX_CODES+1; i++) bsuffix[i] = 0;

  return(ret);
}


/*													*/
/* Get next byte from GIF decoder		*/
/*													*/


int bdecode_gif()

{
  	register int	c;
	register int	code;

  	/* This is the main loop.  For each code we get we pass through the
    * linked list of iprefix codes, pushing the corresponding "character" for
    * each code onto the stack.  When the list reaches a single "character"
    * we push that on the stack too, and then start unstacking each
    * character for output in the correct order.  Special handling is
    * included for the clear code, and the whole thing ends when we get
    * an ending code.
    */

   if(bemit_index > bdstack) return(*(--bemit_index));

	while ((c = bget_next_code()) != bending)
   {
   	/* If we had a file error, return without completing the decode	*/

		if(c < 0) 
		return(0);

    	/* If the code is a clear code, reinitialize all necessary items	*/

		if(c == bclear)
      {
      	bcurr_size = bcode_size + 1;
      	bslot = bnew_codes;
      	btop_slot = 1 << bcurr_size;

      	/* Continue reading codes until we get a non-clear code */
         /* (Another unlikely, but possible case...)				  */

			while ((c = bget_next_code()) == bclear);

	      /* If we get an ending code immediately after a clear code	*/
         /* (Yet another unlikely case), then break out of the loop.	*/

			if(c == bending) break;

			/* Finally, if the code is beyond the range of already set			*/
			/* codes, (This one had better NOT happen...  I have no idea 		*/
			/*	what will result from this, but I doubt it will look good... 	*/
			/* then set it	to color zero													*/

			if(c >= bslot) c = 0;

      	bold_code = bout_value = c;

      	/* And let us not forget to put the character into the buffer		*/

			return(c);
		}
    	else
    	{
	 		/* In this case, it's not a clear code or an ending code, so			*/
      	/* it must be a code code...  So we can now decode the code into		*/
      	/* a stack of character codes. (Clear as mud, right?)						*/

			code = c;

      	/* Here we go again with one of those off chances...  If, on the		*/
	      /* off chance, the code we got is beyond the range of those already	*/
   	   /* set up (Another thing which had better NOT happen...) we trick		*/
      	/* the decoder into thinking it actually got the last code read.		*/
	      /* (Hmmn... I'm not sure why this works...  But it does...)				*/

			if(code >= bslot)
			{
   	   	if(code > bslot) ++bbad_code_count;
      	  	code = bold_code;
        		*bemit_index++ = (UTINY) bout_value;
	      }

   	   /* Here we scan back along the linked list of iprefixes, pushing		*/
     		/* helpless characters (ie. isuffixes) onto the stack as we do so.		*/
       
	      while (code >= bnew_codes)
	      {
   	   	*bemit_index++ = bsuffix[code];
      	  	code = bprefix[code];
	      }

	      /* Push the last character on the stack, and set up the new				*/
   	   /* iprefix and isuffix, and if the required slot number is greater		*/
      	/* than that allowed by the current bit size, increase the bit			*/
	      /* size.  (NOTE - If we are all full, we *don't* save the new			*/
   	   /* isuffix and iprefix...  I'm not certain if this is correct...			*/
      	/* it might be more proper to overwrite the last code...					*/

	      *bemit_index++ = (UTINY) code;

			if(bslot < btop_slot)
      	{
	      	bout_value = code;
   	     	bsuffix[bslot] = (UTINY) bout_value;
      	  	bprefix[bslot++] = bold_code;
	        	bold_code = c;
   	   }
	      
			if(bslot >= btop_slot)
			{
				if(bcurr_size < 12)
      	   {
         		btop_slot <<= 1;
          		++bcurr_size;
	         }
			}

	      /* Now that we've pushed the decoded string (in reverse order)			*/
   	   /* onto the stack, lets pop it off and return it a byte at a 			*/
      	/* time to the caller																*/
       
   	   if(bemit_index > bdstack) return(*(--bemit_index));
		}
	}
	return(c);
}


/******************************************************************************
 *
 * GIF output routines
 *
 ******************************************************************************/

/*	Number of characters so far in this 'packet' */

static int a_count;


/*	Set up the 'byte output' routine */

void char_init()
{
	a_count = 0;
}

/*	Define the storage for the packet accumulator */

static char accum[ 256 ];

/*
 * Add a character to the end of the current packet, and if it is 254
 * characters, flush the packet to disk.
 */

void char_out( c )
int c;
{
	accum[ a_count++ ] = c;
	if( a_count >= 254 )
		flush_char();
}

/*
 * Flush the packet to disk, and reset the accumulator
 */

void	flush_char()
{
	if( a_count > 0 ) {
		fputc( a_count, g_outfile );
		fwrite( accum, 1, a_count, g_outfile );
		a_count = 0;
	}
}


/*													*/
/* Write out a word to the GIF file		*/
/*													*/

void Putword(int w, FILE *fp )
{
	fputc( w & 0xff, fp );
	fputc( (w / 256) & 0xff, fp );
}

/*
 * Bump the 'curx' and 'cury' to point to the next pixel
 */

static void BumpPixel()
{
	/*
	 * Bump the current X position
	 */
	curx++;

	/*
	 * If we are at the end of a scan line, set curx back to the beginning
	 * If we are interlaced, bump the cury to the appropriate spot,
	 * otherwise, just increment it.
	 */
	if( curx == Width ) {
		curx = 0;

	        if( !Interlace )
			cury++;
		else {
		     switch( Pass ) {

	               case 0:
        	          cury += 8;
                	  if( cury >= Height ) {
		  		Pass++;
				cury = 4;
		  	  }
                          break;

	               case 1:
        	          cury += 8;
                	  if( cury >= Height ) {
		  		Pass++;
				cury = 2;
		  	  }
			  break;

	               case 2:
	                  cury += 4;
	                  if( cury >= Height ) {
	                     Pass++;
	                     cury = 1;
	                  }
	                  break;

	               case 3:
	                  cury += 2;
	                  break;
			}
		}
	}
}

/*
 * Return the next pixel from the image
 */

int GIFNextPixel(getpixel)
ifunptr getpixel;
{
	int r;

	if( CountDown == 0 )
		return EOF;

	CountDown--;

	r = getpixel( curx, cury );

	BumpPixel();

	return r;
}

/* public */

void GIFEncode( FName, GWidth, GHeight, GInterlace, Background,
	   			 BitsPerPixel, Red, Green, Blue, GetPixel )

char *	FName;
int 		GWidth, GHeight;
int 		GInterlace;
int 		Background;
int 		BitsPerPixel;
int 		Red[], Green[], Blue[];
ifunptr 	GetPixel;

{
	FILE *fp;
	int B;
	int RWidth, RHeight;
	int LeftOfs, TopOfs;
	int Resolution;
	int ColorMapSize;
	int InitCodeSize;
	int i;

	Interlace = GInterlace;

	ColorMapSize = 1 << BitsPerPixel;

	RWidth = Width = GWidth;
	RHeight = Height = GHeight;
	LeftOfs = TopOfs = 0;

	Resolution = BitsPerPixel;

	/*
	 * Calculate number of bits we are expecting
	 */
	CountDown = (long)Width * (long)Height;

	/*
	 * Indicate which pass we are on (if interlace)
	 */
	Pass = 0;

	/*
	 * The initial code size
	 */
	if( BitsPerPixel <= 1 )
		InitCodeSize = 2;
	else
		InitCodeSize = BitsPerPixel;

	/*
	 * Set up the current x and y position
	 */
	curx = cury = 0;

	/*
	 * Open the GIF file for binary write
	 */
	fp = fopen( FName, "wb" );

	if( fp == (FILE *)0 ) {
		printf( "error: could not open output file\n" );
		exit(1);
	}

	/*
	 * Write the Magic header
	 */
	fwrite( "GIF87a", 1, 6, fp );

	/*
	 * Write out the screen width and height
	 */
	Putword( RWidth, fp );
	Putword( RHeight, fp );

	/*
	 * Indicate that there is a global colour map
	 */
	B = 0x80;	/* Yes, there is a color map */

	/*
	 * OR in the resolution
	 */
	B |= (Resolution - 1) << 5;

	/*
	 * OR in the Bits per Pixel
	 */
	B |= (BitsPerPixel - 1);

	/*
	 * Write it out
	 */
	fputc( B, fp );

	/*
	 * Write out the Background colour
	 */
	fputc( Background, fp );

	/*
	 * Byte of 0's (future expansion)
	 */
	fputc( 0, fp );

	/*
	 * Write out the Global Colour Map
	 */
     	for( i=0; i<ColorMapSize; i++ ) {
		fputc( Red[i], fp );
		fputc( Green[i], fp );
		fputc( Blue[i], fp );
	}

	/*
	 * Write an Image separator
	 */
	fputc( ',', fp );

	/*
	 * Write the Image header
	 */

	Putword( LeftOfs, fp );
	Putword( TopOfs, fp );
	Putword( Width, fp );
	Putword( Height, fp );

	/*
	 * Write out whether or not the image is interlaced
	 */
	if( Interlace )
		fputc( 0x40, fp );
	else
		fputc( 0x00, fp );

	/*
	 * Write out the initial code size
	 */
	fputc( InitCodeSize, fp );

	/*
	 * Go and actually compress the data
	 */
	compress( InitCodeSize+1, fp, GetPixel );

	/*
	 * Write out a Zero-length packet (to end the series)
	 */
	fputc( 0, fp );

	/*
	 * Write the GIF file terminator
	 */
	fputc( ';', fp );

	/*
	 * And close the file
	 */
	fclose(fp);

}

/*																									*/
/*	GIF encoding routine																		*/
/*																									*/
/* This routine was borrowed from TGA2GIF with very little modification 	*/
/*	I must give credit to the original authors for their highly useful code */
/*																									*/
/* Based on :    	GIFENCODE.C - An LZW encoder for GIF							*/
/*						Written by Steven B. Coy											*/
/*						From code by David Rowley											*/
/*						And modified by Drew Wells and Chris Cason					*/
/* 																								*/
/*
 * GIF Image compression - modified 'compress'
 *
 * Based on: compress.c - File compression ala IEEE Computer, June 1984.
 *
 * By Authors:  Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
 *              Jim McKie               (decvax!mcvax!jim)
 *              Steve Davies            (decvax!vax135!petsd!peora!srd)
 *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
 *              James A. Woods          (decvax!ihnp4!ames!jaw)
 *              Joe Orost               (decvax!vax135!petsd!joe)
 *
 */

/*
 * compress stdin to stdout
 *
 * Algorithm:  use open addressing double hashing (no chaining) on the
 * iprefix code / next character combination.  We do a variant of Knuth's
 * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
 * secondary probe.  Here, the modular division first probe is gives way
 * to a faster exclusive-or manipulation.  Also do block compression with
 * an adaptive reset, whereby the code table is cleared when the compression
 * ratio decreases, but after the table fills.  The variable-length output
 * codes are re-sized at this point, and a special CLEAR code is generated
 * for the decompressor.  Late addition:  construct the table according to
 * file size for noticeable speed improvement on small files.  Please direct
 * questions about this implementation to ames!jaw.
 */

compress( init_bits, outfile, ReadValue )
int init_bits;
FILE *outfile;
ifunptr ReadValue;
{
    register long fcode;
    register code_int i = 0;
    register int c;
    register code_int ent;
    register code_int disp;
    register code_int hsize_reg;
    register int hshift;

    /*
     * Set up the globals:  g_init_bits - initial number of bits
     *                      g_outfile   - pointer to output file
     */
    g_init_bits = init_bits;
    g_outfile = outfile;

    /*
     * Set up the necessary values
     */
    offset = 0;
    out_count = 0;
    clear_flg = 0;
    in_count = 1;
    maxcode = MAXCODE(n_bits = g_init_bits);

    ClearCode = (1 << (init_bits - 1));
    EOFCode = ClearCode + 1;
    free_ent = ClearCode + 2;

    char_init();

    ent = GIFNextPixel( ReadValue );

    hshift = 0;
    for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
	hshift++;
    hshift = 8 - hshift;                /* set hash code range bound */

    hsize_reg = hsize;
    cl_hash( (count_int) hsize_reg);            /* clear hash table */

    output( (code_int)ClearCode );

#ifdef SIGNED_COMPARE_SLOW
    while ( (c = GIFNextPixel( ReadValue )) != (unsigned) EOF ) {
#else
    while ( (c = GIFNextPixel( ReadValue )) != EOF ) {
#endif

	in_count++;

	fcode = (long) (((long) c << maxbits) + ent);
	i = (((code_int)c << hshift) ^ ent);    /* xor hashing */

	if ( HashTabOf (i) == fcode ) {
	    ent = CodeTabOf (i);
	    continue;
	} else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
	    goto nomatch;
	disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
	if ( i == 0 )
	    disp = 1;
probe:
	if ( (i -= disp) < 0 )
	    i += hsize_reg;

	if ( HashTabOf (i) == fcode ) {
	    ent = CodeTabOf (i);
	    continue;
	}
	if ( (long)HashTabOf (i) > 0 )
	    goto probe;
nomatch:
	output ( (code_int) ent );
	out_count++;
	ent = c;
#ifdef SIGNED_COMPARE_SLOW
	if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
#else
	if ( free_ent < maxmaxcode ) {
#endif
	    CodeTabOf (i) = free_ent++; /* code -> hashtable */
	    HashTabOf (i) = fcode;
	} else
		cl_block();
    }
    /*
     * Put out the final code.
     */
    output( (code_int)ent );
    out_count++;
    output( (code_int) EOFCode );

    return 0;
}

/*****************************************************************
 * TAG( output )
 *
 * Output the given code.
 * Inputs:
 *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
 *              that n_bits =< (long)wordsize - 1.
 * Outputs:
 *      Outputs code to the file.
 * Assumptions:
 *      Chars are 8 bits long.
 * Algorithm:
 *      Maintain a BITS character long buffer (so that 8 codes will
 * fit in it exactly).  Use the VAX insv instruction to insert each
 * code in turn.  When the buffer fills up empty it and start over.
 */

void	output( code )
code_int  code;
{
    cur_accum &= code_mask[ cur_bits ];

    if( cur_bits > 0 )
	cur_accum |= ((long)code << cur_bits);
    else
	cur_accum = code;

    cur_bits += n_bits;

    while( cur_bits >= 8 ) {
	char_out( (unsigned int)(cur_accum & 0xff) );
	cur_accum >>= 8;
	cur_bits -= 8;
    }

    /*
     * If the next entry is going to be too big for the code size,
     * then increase it, if possible.
     */
   if ( free_ent > maxcode || clear_flg ) {

	    if( clear_flg ) {

		maxcode = MAXCODE (n_bits = g_init_bits);
		clear_flg = 0;

	    } else {

		n_bits++;
		if ( n_bits == maxbits )
		    maxcode = maxmaxcode;
		else
		    maxcode = MAXCODE(n_bits);
	    }
	}

    if( code == EOFCode ) {
	/*
	 * At EOF, write the rest of the buffer.
	 */
	while( cur_bits > 0 ) {
		char_out( (unsigned int)(cur_accum & 0xff) );
		cur_accum >>= 8;
		cur_bits -= 8;
	}

	flush_char();

	fflush( g_outfile );

	if( ferror( g_outfile ) )
		writeerr();
    }
}

/*
 * Clear out the hash table
 */

void	cl_block ()             /* table clear for block compress */
{

	cl_hash ( (count_int) hsize );
	free_ent = ClearCode + 2;
	clear_flg = 1;

	output( (code_int)ClearCode );
}

void	cl_hash(hsize)          /* reset code table */
register count_int hsize;
{

	register count_int *htab_p = htab+hsize;

	register long i;
	register long m1 = -1;

	i = hsize - 16;
	do {                            /* might use Sys V memset(3) here */
		*(htab_p-16) = m1;
		*(htab_p-15) = m1;
		*(htab_p-14) = m1;
		*(htab_p-13) = m1;
		*(htab_p-12) = m1;
		*(htab_p-11) = m1;
		*(htab_p-10) = m1;
		*(htab_p-9) = m1;
		*(htab_p-8) = m1;
		*(htab_p-7) = m1;
		*(htab_p-6) = m1;
		*(htab_p-5) = m1;
		*(htab_p-4) = m1;
		*(htab_p-3) = m1;
		*(htab_p-2) = m1;
		*(htab_p-1) = m1;
		htab_p -= 16;
	} while ((i -= 16) >= 0);

	for ( i += 16; i > 0; i-- )
		*--htab_p = m1;
}

void	writeerr()
{
	printf( "error writing output file\n" );
	exit(1);
}