/* fractile.c */
#define VERSION "fractile 1.1, placed in public domain by Steve Kirkendall, 8 April 1996"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include "tile.h"
extern char *optarg;
extern int optind;
extern char **readopt(FILE *fp);


/* These variables are set from command-line flags */
int	byheight = 0;	/* color by height (else by slope) */
int	illumdx = -1;	/* X offset to neighbor pixel when figuring slope */
int	illumdy = -1;	/* Y offset to neighbor pixel when figuring slope */
int	roundoff = 0;	/* rount to nearest color?  (else use random dither) */
int	size = 4;	/* size of image (2^size points on each side) */
int	first = 1;	/* first level to subject to random noise */
int	last = 7;	/* last level to subject to random noise */
int	maxpalette = 2;	/* number of colors in spectrum */
int	bounce = 4;	/* number of distinct colors in palette */
int	cw, ccw;	/* travel direction when interpolating colors */
double	flood = 0.0;	/* flood height */
double	crush = 1.0;	/* crush height (above and below average) */
double	emph = 0.1;	/* emphasis factor */
char	*light = "lightbrown";/* northwest exposure color, or high altitude */
char	*dark = "darkbrown";/* southeast exposure color, or low altitude */
char	*water = "darkblue";/* color of the flooded areas */
char	outfile[255];	/* name of the output file */

/* These are computed */
int	dim;		/* number of points along each edge */
int	mask;		/* position mask */
int	wet;		/* count of points below flood level */

/* These store the texture colors, as 8-bit RGB values */
rgb_t	lightrgb;
rgb_t	darkrgb;
rgb_t	waterrgb;

/* This is the two-dimensional array of point heights */
float		**altitude;
unsigned char    *imagedata;
#define image(x,y)	(imagedata[(y) * dim + x])

/* function declarations */
void usage(char *hint);
void allocalt(void);
void genimage(void);
void fractal(void);
void docrush(void);
void main(int argc, char **argv);


void usage(char *hint)
{
#ifdef SUPPORT_X11
	fprintf(stderr, "usage: fractile [options] [outfile[.gif]]\n");
#else
	fprintf(stderr, "usage: fractile [options] outfile[.gif]\n");
#endif
	fprintf(stderr, "   -v           Display the version number; don't generate an image\n");
	fprintf(stderr, "   -r           Round to nearest color (else use random dithering)\n");
	fprintf(stderr, "   -s [s,][f,]l Output will be square, 2^s pixels on each side\n");
	fprintf(stderr, "                 f & l determine the first & last levels subjected to noise\n");
	fprintf(stderr, "   -i illum     Compass heading to illumination source, or 'h'; default is NW\n");
	fprintf(stderr, "   -p [c,]s     Size of color palette, and optional number of colors in it\n");
	fprintf(stderr, "   -t inter     Interpolation path from dark to light color. cw/ccw/chord\n");
	fprintf(stderr, "   -f flood     Flood level.  0.0 <= flood <= 1.0\n");
	fprintf(stderr, "   -c crush     Crush factor.  0.0 <= crush <= 1.0\n");
	fprintf(stderr, "   -e emphasis  Steepness emphasis factor.  1.0 <= emphasis; default is 10.0\n");
	fprintf(stderr, "   -l light     Name of light color; default is lightbrown\n");
	fprintf(stderr, "   -d dark      Name of dark color; default is darkbrown\n");
	fprintf(stderr, "   -w water     Name of water color (for -f#); default is darkblue\n");
	fprintf(stderr, "   -m macro     Use options from a line in fractile.mac or ~/.fractile\n");
	fprintf(stderr, "   -M macro     Display options from a line in fractile.mac or ~/.fractile\n");
	if (hint)
	{
		fprintf(stderr, "%s\n", hint);
	}
	else
	{
		fprintf(stderr, "This program uses a random number generator to produce background image tiles\n");
		fprintf(stderr, "for use with Netscape or other graphical utilities.  It generates a factal\n");
		fprintf(stderr, "altitude map and then derives an image from that map.  The output file can use\n");
#ifdef SUPPORT_X11
		fprintf(stderr, "either CompuServe's GIF image file format, or Microsoft's BMP format.  If no\n");
		fprintf(stderr, "output file name is specified, this program will attempt to set the background\n");
		fprintf(stderr, "image of your X terminal.\n");
#else
		fprintf(stderr, "either CompuServe's GIF image file format, or Microsoft's BMP format.\n");
#endif
	}
	exit(1);
}



/* allocate the altitude array */
void allocalt(void)
{
	int	i;

	/* compute the number of points along each edge */
	dim = (1 << size);
	mask = dim - 1; /* <-- nifty binary hack */

	/* if we would need to allocate too much RAM for a size_t, complain */
	if ((long)dim * (long)dim >= 65536 && sizeof(size_t) == 2)
	{
		fprintf(stderr, "This computer can only generate 128x128 images\n");
		exit(2);
	}

	/* allocate the altitude array */
	altitude = (float **)malloc(dim * sizeof(float *));
	for (i = 0; i < dim; i++)
	{
		altitude[i] = (float *)malloc(dim * sizeof(float));
	}
	
	/* allocate the imagedata array */
	imagedata = (unsigned char *)malloc(dim * dim * sizeof(unsigned char));
}



/* This function does the fractal height stuff */
void fractal()
{
	int	this;		/* current level of refinement */
	int	neighbor;	/* offset to neighbor positions */
	double	noise;		/* random noise scaling factor */
	int	i, j;

	/* make the first point */
	altitude[0][0] = 0.5;

	/* for each level of detail... */
	for (this = 1, neighbor = dim / 2, noise = 0.5;
	     neighbor > 0;
	     this++, neighbor /= 2, noise /= 2.0)
	{
		/* first fill in the diagonals */
		for (i = neighbor; i < dim; i += neighbor * 2)
		{
			for (j = neighbor; j < dim; j += neighbor * 2)
			{
				/* Find the average of 4 nearest points from
				 * the previous generation.
				 */
				altitude[i][j] =
					(altitude[i - neighbor][j - neighbor] +
					altitude[i - neighbor][(j + neighbor) & mask] +
					altitude[(i + neighbor) & mask][j - neighbor] +
					altitude[(i + neighbor) & mask][(j + neighbor) & mask]) / 4.0;

				if (first <= this && this <= last)
					altitude[i][j] += drand48() * 2.0 * noise - noise;
			}
		}

		/* then fill in the horizontals */
		for (i = neighbor; i < dim; i += neighbor * 2)
		{
			for (j = 0; j < dim; j += neighbor * 2)
			{
				/* Find the average of 4 nearest points from
				 * the previous generation.
				 */
				altitude[i][j] =
					(altitude[i][(j - neighbor) & mask] +
					altitude[i][j + neighbor] +
					altitude[i - neighbor][j] +
					altitude[(i + neighbor) & mask][j]) / 4.0;

				if (first <= this && this <= last)
					altitude[i][j] += drand48() * 2.0 * noise - noise;
			}
		}

		/* then fill in the verticals */
		for (i = 0; i < dim; i += neighbor * 2)
		{
			for (j = neighbor; j < dim; j += neighbor * 2)
			{
				/* Find the average of 4 nearest points from
				 * the previous generation.
				 */
				altitude[i][j] =
					(altitude[i][j - neighbor] +
					altitude[i][(j + neighbor) & mask] +
					altitude[(i - neighbor) & mask][j] +
					altitude[i + neighbor][j]) / 4.0;

				if (first <= this && this <= last)
					altitude[i][j] += drand48() * 2.0 * noise - noise;
			}
		}
	}
}


/* This function performs the crush operation.  It also counts the number of
 * pixels that are below the flood level
 */
void docrush()
{
	int	i, j;
	double	low, high, avg;
	double	top, bottom, diff;

	/* compute the average height */
	high = avg = 0.0;
	low = 1.0;
	for (i = 0; i < dim; i++)
	{
		for (j = 0; j < dim; j++)
		{
			avg += altitude[i][j];
			if (low > altitude[i][j])
				low = altitude[i][j];
			if (high < altitude[i][j])
				high = altitude[i][j];
		}
	}

	/* compute the limits */
	flood = low + (high - low) * flood;
	avg /= (double)dim * (double)dim;
	top = (high - avg) * crush + avg;
	bottom = (low - avg) * crush + avg;
	diff = high - low;

	/* crush the non-flooded altitudes that are far from average */
	wet = 0;
	for (i = 0; i < dim; i++)
	{
		for (j = 0; j < dim; j++)
		{
			if (altitude[i][j] < flood)
				wet++;
			else if (altitude[i][j] > top)
				altitude[i][j] = top;
			else if (altitude[i][j] < bottom)
				altitude[i][j] = bottom;
		}
	}

	/* If coloring by height instead of by slope, then normalize
	 * the heights to be in the range from 0 to 1.  Also normalize
	 * the flood value the same way, so the normalized heights can
	 * be compared to it.
	 */
	if (byheight)
	{
		for (i = 0; i < dim; i++)
		{
			for (j = 0; j < dim; j++)
			{
				altitude[i][j] = (altitude[i][j] - low) / diff;
			}
		}
		flood = (flood - low) / diff;
	}
}


/* This function outputs the texture as an X-windows pixmap.  This is also
 * where altitudes are converted into pixel values.
 */
void genimage()
{
	int	i, x, y;
	double	diff;
	double	lightest, darkest, mult;

	/* compute the slope emphasis values */
	if (emph > 1.0)
	{
		lightest = darkest = 0.0;
		for (y = 0; y < dim; y++)
		{
			for (x = 0; x < dim; x++)
			{
				diff = altitude[(x + illumdx) & mask][(y + illumdy) & mask] - altitude[x][y];
				if (diff < lightest) lightest = diff;
				if (diff > darkest) darkest = diff;
			}
		}
		mult = darkest - lightest;
		if (mult > 0.00001) mult = (double)(maxpalette - 1) / mult;
	}

	/* for each pixel... */
	for (y = 0; y < dim; y++)
	{
		for (x = 0; x < dim; x++)
		{
			/* water? */
			if (altitude[x][y] < flood)
			{
				image(x,y) = maxpalette;
				continue;
			}

			/* produce a floating-point color number */
			if (byheight)
			{
				/* convert the altitude into a floating point
				 * color value.
				 */
				diff = altitude[x][y] * (double)(maxpalette - 1);
			}
			else
			{
				/* Find the height difference.  Since the
				 * original heights range from 0.0 to 1.0, their
				 * difference will range from -1.0 to 1.0, but
				 * will probably be much closer to 0 because of
				 * the successive refinement algorithm.
				 */
				diff = altitude[(x + illumdx) & mask][(y + illumdy) & mask] - altitude[x][y];

				if (emph <= 1.0)
				{
					/* Expand or compress the difference.
					 * This results in numbers which are
					 * still between -1.0 and 1.0, but
					 * should be closer to 0 if emph > 1,
					 * and farther from 0 if emph < 1.
					 */
					if (diff < 0)
						diff = -pow(-diff, emph);
					else 
						diff = pow(diff, emph);

					/* Convert the difference directly into
					 * a color number.  At this point, the
					 * color number is a floating point
					 * value so we can find the color error.
					 */
					diff = (diff + 1.0) / 2.0 * (double)(maxpalette - 1);
				}
				else
				{
					diff = (diff - lightest) * mult;
				}
			}

			/* convert the floating point color to an integer */
			if (roundoff)
			{
				/* round to nearest integer */
				i = (diff + 0.5);
			}
			else
			{
				/* randomly choose one of the two nearest
				 * integer colors.
				 */
				i = floor(diff);
				if (i < maxpalette - 1)
				{
					/* Use the color error to make the
					 * nearer color be more likely to be
					 * chosen.
					 */
					if (drand48() < diff - i)
						i++;
				}
			}

			/* output the color code for this pixel */
			image(x,y) = i;
		}
	}
}



void main(int argc, char **argv)
{
	int	opt;
	int	i, j;
	int	didm;
	char	macrofile[200];
	char	**macroargv;
	FILE	*fp;

	/* seed the random number generator */
	srand48(time(NULL) + getpid());

	/* convert the default color names to rgb_t values */
	waterrgb = name_to_RGB(water);
	lightrgb = name_to_RGB(light);
	darkrgb = name_to_RGB(dark);

	didm = 0;
	while ((opt = getopt(argc, argv, "vrs:i:o:p:t:f:c:e:l:d:w:m:M:?")) != EOF)
	{
		switch (opt)
		{
		  case 'v':
			puts(VERSION);
			exit(0);

		  case 'r':
			roundoff = 1;
			break;

		  case 's':
			if (sscanf(optarg, "%d,%d,%d", &size, &i, &last) == 3)
			{
				if (size < last)
					usage("size can't be smaller than last");
				first = i;
			}
			else if (sscanf(optarg, "%d,%d", &size, &last) == 2)
			{
				if (size <= last)
				{
					first = size;
					size = 4;
				}
			}
			else
			{
				last = atoi(optarg);
			}
			if (last < 0)
				usage(NULL);
			if (size < 4 || size > 12)
				usage("size must be between 4 and 12 (or maybe less, depending on available RAM)");
			if (last > 12)
				usage("last can't exceed size, which shouldn't be larger than 12");
			if (first >last)
				usage("first can't exceed last");
			if (first < 1 || last < 1)
				usage("first & last must be at least 1");
			break;

		  case 'i':
			if (*optarg == 'h')
			{
				byheight = 1;

			}
			else if (!strcmp(optarg, "random"))
			{
				illumdy = -1;
				switch ((int)(drand48() * 7))
				{
				  case 0:
				  case 1:   illumdx = -1;	break;
				  case 2:
				  case 3:   illumdx = 0;	break;
				  case 4:
				  case 5:   illumdx = 1;	break;
				  default:  illumdx = 10;	break;
				}
			}
			else
			{
				illumdx = illumdy = 0;
				for (i = 0; optarg[i]; i++)
				{
					switch (optarg[i])
					{
					  case 'n':
					  case 'N':
						illumdy--;
						break;

					  case 's':
					  case 'S':
						illumdy++;
						break;

					  case 'e':
					  case 'E':
						illumdx++;
						break;

					  case 'w':
					  case 'W':
						illumdx--;
						break;

					  case '0':
					  case '1':
					  case '2':
					  case '3':
					  case '4':
					  case '5':
					  case '6':
					  case '7':
					  case '8':
					  case '9':
						j = atoi(&optarg[i]);
						illumdx *= j;
						illumdy *= j;
						while (isdigit(optarg[i]))
						{
							i++;
						}
						i--; /* stay on last digit */
						break;

					  default:
						usage("illumination must be a compass heading such as \"nw\" or \"e\"");
					}
				}
				if (illumdx == 0 && illumdy == 0)
				{
					usage("invalid compass heading for -i");
				}
			}
			break;

		  case 'p':
			if (sscanf(optarg, "%d,%d", &bounce, &maxpalette) != 2)
			{
				bounce = atoi(optarg);
				maxpalette = 0;
			}
			if (bounce < 2)
				usage("must use at least two colors");
			break;

		  case 't':
			if (!strcmp(optarg, "cw"))
				cw = 1, ccw = 0;
			else if (!strcmp(optarg, "ccw"))
				cw = 0, ccw = 1;
			else if (!strcmp(optarg, "chord"))
				cw = ccw = 0;
			else if (!strcmp(optarg, "random"))
				switch ((int)(drand48() * 3))
				{
				  case 0:	cw = 1, ccw = 0;	break;
				  case 1:	cw = 0, ccw = 1;	break;
				  default:	cw = 0, ccw = 0;	break;
				}
			else
				usage("invalid -t value; should be cw, ccw, or chord");
			break;

		  case 'f':
			flood = atof(optarg);
			if (flood < 0.0 || flood > 1.0)
				usage("flood level must be between 0.0 and 1.0");
			break;

		  case 'c':
		  	crush = atof(optarg);
		  	if (crush < 0.0 || crush > 1.0)
		  		usage("crush level must be between 0.0 and 1.0");
			break;

		  case 'e':
		  	emph = atof(optarg);
			if (emph > 1.0)
				emph = 1.0 / emph;
			else
				emph = 2.0; /* to denote automatic emphasis */
			break;

		  case 'w':
		  	water = optarg;
			waterrgb = name_to_RGB(water);
			break;

		  case 'l':
			light = optarg;
			lightrgb = name_to_RGB(light);
			break;

		  case 'd':
			dark = optarg;
			darkrgb = name_to_RGB(dark);
			break;

		  case 'm':
		  case 'M':
			/* use of static variables prohibits nested macros */
			if (didm)
				usage("-mmacro can only occur once");
			didm = 1;

			/* open the macro file.  It may be "fractile.mac" in
			 * the current directory, ".fractile" in the HOME
			 * directory, or "fractile.mac" in the directory
			 * where the executable resides.
			 */
			fp = fopen("fractile.mac", "r");
			if (!fp)
			{
				if (getenv("HOME"))
				{
					sprintf(macrofile, "%s/.fractile", getenv("HOME"));
				}
				else if (strrchr(argv[0], '\\'))
				{
					strcpy(macrofile, argv[0]);
					strcpy(strrchr(argv[0], '\\') + 1, "fractile.mac");
				}
				else
				{
					perror("fractile.mac");
					exit(2);
				}
				fp = fopen(macrofile, "r");
				if (!fp)
				{
					perror(macrofile);
					exit(2);
				}
			}

			/* search for the macro */
			if (!strcmp(optarg, "random"))
			{
				/* count the number of macros */
				for (i = 0; readopt(fp) != NULL; i++)
				{
				}
				rewind(fp);

				/* if empty file, then complain */
				if (i == 0)
				{
					fprintf(stderr, "%s: no macros defined\n", argv[0]);
					exit(2);
				}

				/* choose macro randomly */
				i *= drand48();

				/* read that macro */
				do
				{
					macroargv = readopt(fp);
				} while (--i >= 0);
				fclose(fp);
			}
			else
			{
				/* look for a specific name */
				while ((macroargv = readopt(fp)) != NULL &&
					(!macroargv[0] || strcmp(macroargv[0], optarg)))
				{
				}
				fclose(fp);
				if (macroargv == NULL)
				{
					fprintf(stderr, "%s: macro \"%s\" not found\n", argv[0], optarg);
					exit(2);
				}
			}

			if (opt == 'M')
			{
				/* display the macro name and its options */
				for (i = 0; macroargv[i]; i++)
				{
					printf("%s%s", i>0?" ":"", macroargv[i]);
				}
				printf("\n");
				exit(0);
			}
			else if (macroargv[1] != NULL)
			{
				/* skip the macro name; use its options */
				putopt(1, macroargv);
			}
			break;

		  default:
			usage(NULL);
		}
	}

	/* find the filename.  If no filename, then give usage message */
	if (optind + 1 == argc)
	{
		strcpy(outfile, argv[optind]);
		if (strchr(outfile, '.') == NULL)
			strcat(outfile, ".gif");
	}
#ifdef SUPPORT_X11
	else if (optind != argc)
	{
		usage("you can only specify one output name, or none");
	}
#else
	else
	{
		usage("you must specify one output file name");
	}
#endif

	/* some sanity checks */
	if (size < last)
		size = last;
	if (maxpalette < bounce)
		maxpalette = bounce;
	if (maxpalette > 255)
		usage("palette size shouldn't exceed 255 colors");

	/* allocate the altitude array */
	allocalt();

	/* generate the altitude map */
	fractal();

	/* clip the heights, and find the flooded areas */
	docrush();

	/* generate a color palette */
	genpalette(lightrgb, darkrgb, waterrgb, maxpalette, cw, ccw, bounce);

	/* generate an image from the altitude map */
	genimage();
	
	/* reduce the color palette by eliminating duplicate/unused colors */
	reduce(imagedata, dim, dim);
	
	/* output a GIF image */
#ifdef SUPPORT_X11
	if (*outfile == '\0')
		WriteX11(outfile, imagedata, dim, dim, palette, palettesize);
	else
#endif
	if ((outfile[strlen(outfile) - 1] & 0x5f) == 'P')
		WriteBmp(outfile, imagedata, dim, dim, palette, palettesize);
	else
		WriteGif(outfile, imagedata, dim, dim, palette, palettesize);

	exit(0);
}