/*********************************************************************/
/**        Bill Menees' Summer Semester 1992 Math 491 Project       **/
/**  Dithers a grey-scale graphics image (in a proprietary format)  **/
/** to use only black or white pixels.  It can dither square images **/
/**    with side lengths in powers of 2 of up to MAXSIZE pixels.    **/
/**      The dithering algorithm is based on the Hilbert curve.     **/
/*********************************************************************/
/**  Note: The graphics routines used are specific to Turbo C/C++.  **/
/**  Also, this program is coded to use only a 640x480x16 VGA mode. **/
/*********************************************************************/

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <graphics.h>
#define MAXLEN 10000
#define NUM 2
#define MAXSIZE 64

FILE *ginput, *goutput;

/**************************************************************/
/** This does the spinning "clock" during string generation. **/
/**************************************************************/
void update_clock(int *angle)
{
	int x, y;

	x=wherex();
	y=wherey();

	switch((*angle)%=4) {
		case 0: gotoxy(--x,y);
			putchar('/');
			(*angle)++;
			break;
		case 1: gotoxy(--x,y);
			putchar('-');
			(*angle)++;
			break;
		case 2: gotoxy(--x,y);
			putchar('\\');
			(*angle)++;
			break;
		case 3: gotoxy(--x,y);
			putchar('|');
			(*angle)++;
			break;
	}

}

/*****************************************************/
/**  This function generates the string which the   **/
/**  turtle will follow to make the Hilbert curve.  **/
/*****************************************************/
char *genstr(char *str0, int maxlevel)
{
	char str[MAXLEN];
	char axiom[]="X", command;
	char Kar[]="XY";
	char Rule[][12]= {"-YF+XFX+FY-","+XF-YFY-FX+"};
	char shortRule[][8]= {"-F+F+F-","+F-F-F+"};
	int level, i, k, length, angle;

	strcpy(str0,axiom);
	strcpy(str,"");
	clrscr();
	_setcursortype(_NOCURSOR);
	printf("\n\n\n\n\n\n\n\n                      Higher orders take longer...  ");
	angle=0;
	for(level=1;level<=maxlevel;level++) {
		for(k=0;k<strlen(str0);k++) {
			if(k%20==0)
				update_clock(&angle);
			command=str0[k];
			i=0;
			while(i<NUM && !(command==Kar[i]))
				i++;
			if(command==Kar[i])
			/* On the last level the short rules are used */
			/* to keep the final string length shorter as */
			/* the Xs and Ys aren't needed any more then. */ 
				if(level==maxlevel)
					strcat(str,shortRule[i]);
				else
					strcat(str,Rule[i]);
			else {
				length=strlen(str);
				str[length]=command;
				length++;
				str[length]='\0';
			}
		}
		strcpy(str0,str);
		strcpy(str,"");
	}
	return(str0);
}

/***********************************************************/
/** This sets the VGA 16 color palette to 16 grey scales. **/
/***********************************************************/
void pal_to_grey(struct palettetype pal)
{
	int i;

	getpalette(&pal);
	for(i=0;i<pal.size;i++)
		setrgbpalette(pal.colors[i],i*4,i*4,i*4);
}

/**********************************************************/
/** Read in the pixel intensities of the grey-scale pic. **/
/**********************************************************/
void get_intensity(int ttm, float inmat[][MAXSIZE])
{
	float temp;
	int i, j;

	for(i=0;i<ttm;i++)
		for(j=0;j<ttm;j++) {
		/* How do I get &(inmat[i][j]) to work here */
		/* instead of having to use the temp assn?  */
			fscanf(ginput," %f", &temp);
			inmat[i][j]=temp;
		}
}

/*****************************************/
/** Draws the square around the images. **/
/*****************************************/
void show_box(int xcoor, int ycoor, int ttm, int sidelen)
{
	setlinestyle(SOLID_LINE,0,THICK_WIDTH);
	rectangle(xcoor-5,ycoor-5,(ttm*sidelen)+xcoor+5,(ttm*sidelen)+ycoor+5);
	setlinestyle(SOLID_LINE,0,NORM_WIDTH);
}

/*******************************************/
/** Shows the input (grey-scale) picture. **/
/*******************************************/
void show_input(int ttm, float inmat[][MAXSIZE],
	int xcoor, int ycoor, int sidelen, int xside)
{
	int i, j;

	for(i=0;i<ttm;i++) {
		for(j=0;j<ttm;j++) {
			setfillstyle(SOLID_FILL, (int)(15*inmat[i][j]));
			bar(xcoor,ycoor,xcoor+sidelen,ycoor+sidelen);
			xcoor+=sidelen;
		}
		xcoor=xside;
		ycoor+=sidelen;
	}
     /* getch(); */
}

/*****************************************/
/** Stores output pixel info in a file. **/
/*****************************************/
void store_output(int ttm, int outmat[][MAXSIZE], float errestimate)
{
	int i, j;

	for(i=0;i<ttm;i++) {
		for(j=0;j<ttm;j++)
			fprintf(goutput,"%d ",outmat[i][j]);
		fprintf(goutput,"\n");
	}
	fprintf(goutput, "\n%f", errestimate);
}

/*****************************************/
/** Outputs dithered picture to screen. **/
/*****************************************/
void show_output(int ttm, int outmat[][MAXSIZE],
	int xcoor, int ycoor, int sidelen, int xside)
{
	int i, j;

	xcoor=xside;
	ycoor=10;
	moveto(xcoor,ycoor);
	for(i=0;i<ttm;i++) {
		for(j=0;j<ttm;j++) {
			setfillstyle(SOLID_FILL, 15*outmat[i][j]);
			bar(xcoor,ycoor,xcoor+sidelen,ycoor+sidelen);
			xcoor+=sidelen;
		}
		xcoor=xside;
		ycoor+=sidelen;
	}
	getch(); 
}

/*************************************/
/** This function dithers the input **/
/** using the Hilbert curve method. **/
/*************************************/
void dither(char *str, int maxlevel)
{
	/** NOTE: THIS REQUIRES 640x480x16 VGA!!! **/
	int gdriver = VGA, gmode = VGAHI, errorcode;
	struct palettetype pal;
	int i, j, ttm, outmat[MAXSIZE][MAXSIZE];
	int xcoor, ycoor, sidelen, direction, xside, x, y;
	float inmat[MAXSIZE][MAXSIZE], errestimate;
	char command;

	if(registerbgidriver(EGAVGA_driver) < 0) {
		printf("Couldn't find EGAVGA driver!");
		exit(1);
	}

	initgraph(&gdriver, &gmode, "");
	errorcode=graphresult();

	if(errorcode!= grOk) {
		printf("Graphics error: %s\n", grapherrormsg(errorcode));
		printf("Press any key to continue...");
		getch();
	}
	else {
		pal_to_grey(pal);
		ttm=1; /* abbreviation for two to maxlevel */
		for(i=1;i<=maxlevel;i++) ttm*=2;

		get_intensity(ttm, inmat);

		sidelen=((getmaxy()+1-20)/ttm);
		xcoor=xside=((getmaxx()-getmaxy())/2)+1;
		ycoor=10;  /* this 10 is half the 20 used for
				centering up in sidelen */
		moveto(xcoor,ycoor);
		show_box(xcoor, ycoor, ttm, sidelen);

		show_input(ttm, inmat, xcoor, ycoor, sidelen, xside);

		/* this overlays the hilbert curve on the input pic  */
		/* and does the dithering in memory as it goes along */
		/*    (in other words, this is the turtle part...)   */
		xcoor=xside+sidelen/2;
		ycoor=10+sidelen/2;
		moveto(xcoor,ycoor);
		if(inmat[0][0]<=0.5)
			outmat[0][0]=0;
		else
			outmat[0][0]=1;
		errestimate=inmat[0][0]-(float)outmat[0][0];
		x=y=direction=0;
		/********************************/
		/**     Direction Compass:     **/
		/**             3              **/
		/**             |              **/
		/**          2--*--0           **/
		/**             |              **/
		/**             1              **/
		/**   (It's inverted because   **/
		/**     the graphics screen    **/
		/**      coordinates are.)     **/
		/********************************/
		for(i=0;i<strlen(str);i++) {
			command=str[i];
			if(command=='-') direction=(direction+1)%4;
			else if(command=='+') {
				/* the modulo operator (%)
				   in Turbo C++ doesn't work
				   "correctly". -1%4 returns -1
				   instead of 3.  Thus the ==0 clause. */
				if(direction==0) direction=3;
				else direction=(direction-1)%4;
			}
			else if(command=='F') {
				switch(direction) {
					case 0: lineto(xcoor+=sidelen,ycoor);
						x++;
						break;
					case 1: lineto(xcoor,ycoor+=sidelen);
						y++;
						break;
					case 2: lineto(xcoor-=sidelen,ycoor);
						x--;
						break;
					case 3: lineto(xcoor,ycoor-=sidelen);
						y--;
						break;
				}
				errestimate+=inmat[y][x];
				if(errestimate > 1) {
					outmat[y][x]=1;
					errestimate--;
				}
				else
					outmat[y][x]=0;
			}
		}
	     /* getch(); */

		store_output(ttm, outmat, errestimate);

		show_output(ttm, outmat, xcoor, ycoor, sidelen, xside);
	}
	closegraph();
	printf("Error estimate is: %f",errestimate);
}

void main()
{
	char string[MAXLEN];
	int maxlevel;
	char inname[20], outname[20];

	printf("\n\nEnter name of file to dither: ");
	scanf(" %s",inname);
	printf("Enter name of file to output to: ");
	scanf(" %s",outname);

	if((ginput=fopen(inname,"rt"))==NULL) {
		printf("Error opening %s!\n", inname);
		exit(1);
	}
	else if((goutput=fopen(outname,"wt"))==NULL) {
		printf("Error opening %s!\n", outname);
		exit(2);
	}
	else {
		fscanf(ginput," %d",&maxlevel);
		fprintf(goutput,"%d\n",maxlevel);
		strcpy(string,"");
		strcpy(string,genstr(string, maxlevel));
	     /* printf("\n%s",string);
		getch(); */
		dither(string, maxlevel);
	}
	fclose(ginput);
	fclose(goutput);
}