/* corestep.c

Author: Jay Han (jayhan@cs.washington.edu)

The non-simulating optima number calculator.
After an idea by Michael Constant.

Run this program without parameters for help.

Usage
-----

There are three possible uses:
1. Test a single step: -s #
2. Test all mod-N: -m #
3. Test all steps: (default)

For each type, you may specify or not a selection criterion:
-cc   classic formula
-ca   alternate formula
-cf   find-X (with up to FINDS numbers)

If a criterion is specified, you may choose how many will be shown:
-b #  shows the # best steps

In any case, you may ask to display the scores and find number for
the chosen numbers by using
-dc   show classic score
-da   show alternate score
-df   with up to FINDS numbers

Other options:
-l #  limit to steps <= #
-v    verbose
-q    quiet
-o    alternate output (don't know how to use this yet...)

Notes
-----

1. Find-X numbers are displayed in percent.  100% is perfect, 200% means it
takes twice as long as perfect (e.g. 1600 iterations to find 10 in small core).

2. If you specify two or more find-numbers as the criterion, the compound score
is the average of the specified find-numbers.  However, if you
specify -df parameters, each find number will be dispayed separately.

3. All sorted scores (best scores) are displayed best-to-worst.
For the classic formula, higher score is better.
For the alternate formula and the find numbers, lower score is better.

4. In general, the display has been programmed to be tight, so as to give as
much information as possible in the smallest space.  However, the results are
tabulated to allow easy browsing and character-based sorting.

Examples
--------

Find all mod-4 numbers: corestep -m 4 -c
Find 5 best mod-4 numbers using classic formula: corestep -m 4 -cc
Same, display their find-20 and find-100 numbers: corestep -m 4 -cc -df 20 100
Find 10 best mod-1 numbers for 10-sized opponents: corestep -m 1 -cf 10 -b 10
Same, display their find-50 and find-200: corestep -m 1 -cf 10 -b 10 -df 50 200
Find 20 best numbers for 10- and 20-sized opponents:
(this takes some time, so we'll have the verbose mode on)
corestep -cf 10 20 -b 20 -v
Same, display their classic score: corestep -cf 10 20 -b 20 -dc

Compiling
---------

The program uses log(), which should be included in libm.a, the math library.
Usually, it can be linked in with the compiler option -lm, as in:
     gcc -O2 -o corestep corestep.c -lm
(Don't forget to turn on all optimization options!)

This program should compile without problems on any OS with an ANSI C compiler,
provided that uint is 16 bit wide.

Feedback
--------

I'd be happy to hear from you.  Tell me if you find this program useful,
interesting, or totally unsuited to your needs.  Bug-reports are always
welcome, even if they prove false! :-) If you have new ideas you'd like to see
incorporated into the program, let me know also.  I'm particularly looking for
other alternate scoring formulas that give meaningful/useful results.

*************************************************************************/
#define DATE	"5/13/1994"
#define VERSION	"3"
/************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

typedef unsigned int uint;

#define DISP_CLASSIC	0x1
#define DISP_ALTERNATE	0x2
#define DISP_FIND		0x4

#define BANNER \
"corestep v%s: Non-simulating optimal step finder by Jay Han, %s.\n"

char banner[100];

#define FINDS		10
#define NBEST		5
#define CORESIZE	8000   /* 55440 */

uint coresize = (uint)CORESIZE;
int verbose=1, printer=0, display=0;
char tformat[10], rformat[5], lformat[5];
uint critfind[FINDS], dispfind[FINDS];
int size, nbest=NBEST, ncrit=0, ndisp=0;
uint maxstep=0, mod=0;
char criterion='c';

uint modsize (s)
uint s;
{
	uint r, b=s, a=coresize;

	if (s == 0 || s == 1) return s;

	while (r=a%b)
	{
		a = b;
		b = r;
	}
	return b;
}

double classic ( m, s)
uint m, s;
{
	uint t, u;

	if (s == 0) return 0;
	t = m % s;
	u = m / s;
	if (t == 0) return (double) s * (u - 1);

	if (t < s - t)
		return classic (s, t) * u + classic (t, s % t)
			+ (double) (u - 1) * s + (double) t;
	else
		return classic (s, s - t) * u + classic (t, s - t)
			+ (double) (u - 1) * s + (double) t;
}

double alternate ( m,  s)
uint m, s;
{
	uint t, u;

	if (s == 0) return (double) 0;
	t = m % s;
	u = m / s;
	if (t == 0)
		return (double) (u - 2) * 0.5 * m + (double) s
			- (double) (u - 1) * 0.25 * u * s;

	if (t < s - t)
		return alternate (s, t) * u + alternate (t, s % t)
			+ (double) (u - 2) * 0.5 * m + (double) s
				- (double) (u - 1) * 0.25 * u * s;
	else
		return alternate (s, s - t) * u + alternate (t, s - t)
			+ (double) (u - 2) * 0.5 * m + (double) s
				- (double) (u - 1) * 0.25 * u * s;
}

double compute ( s, fn)
uint s; 
double (*fn)();
{
	double score;
	score = fn (coresize, s) / ((double) coresize / modsize (s) - 1);
	if (score > 999.9) return 999.9;
	return score;
}

uint rec ( m,  s,  x)
uint m, s, x;
{
	uint t, u;

	if (m <= x) return 0;
	if (s == 0) return 0;
	if (s <= x) return (m - x - 1) / s + 1;
	u = m / s;
	t = m % s;
	if (t == 0) return coresize / modsize (s);

	if (t < s - t)
		return rec (s, t, x) * u + rec (t, s % t, x) + u;
	else
		return rec (s, s - t, x) * u + rec (t, s - t, x) + u;
}

double find ( s,  x)
uint s, x;
{
	double score;
	if (modsize (s) > x) return 999.9;
	else 
	{
		score = 100.0 * (rec (coresize, s, x) + 1) * x / coresize;
		if (score > 999.9) score = 999.9;
	}
	return score;
}

double findmany ( s,  nfind,  findl)
uint s;
int  nfind;
uint findl[];
{
	double score=0.0;
	int i;

	for (i=0; i < nfind; i++)
		score += find (s, findl[i]);
	return score / nfind;
}

double makescore (step)
uint step;
{
	switch (criterion)
	{
	  case 'c': return compute (step, classic);
	  case 'a': return compute (step, alternate);
	  case 'f': return findmany (step, ncrit, critfind);
	}
}

#define printtext(t,x)	printf (tformat, t, x)
#define printright(x)	printf (rformat, x)
#define printleft(x)	printf (lformat, x)

void printscore ( step, score, dodisplay)
uint step;
double score;
int dodisplay;
{
	int i;

	if (score < 0.0 && !dodisplay) return;
	if (printer) printtext (";", step);
	else printtext ("Step", step);

	if (!mod)
	{
		printf ("  Mod");
		printleft (modsize (step));
	}

	if (score >= 0.0) 
	{
		if (score < 1000.0) printf ("  Score: %6.2lf", score);
		else printf ("  Score: 999.99");
	}

	if (dodisplay)
	{
		if (display & DISP_CLASSIC)
			printf ("  Classic: %6.2lf", compute (step, classic));
		if (display & DISP_ALTERNATE)
			printf ("  Alternate: %6.2lf", compute (step, alternate));
		for (i=0; i < ndisp; i++)
		{
			printf ("  Finds");
			printleft (dispfind[i]);
			printf (" %5.1f%%", find (step, dispfind[i]));
		}
	}
	printf ("\n");
}

void printsettings ()
{
	int i;

	if (verbose)
	{
		if (printer) printf ("; ");
		printf ("Coresize %u.", coresize);
		if (mod) printf ("  Mod-%u.", mod);
		if (maxstep) printf ("  Maximum %u.", maxstep);
		if (nbest) printf ("  Best %d.", nbest);
		if (criterion)
		{
			printf ("  Scoring: ");
			switch (criterion)
			{
			  case 'c': printf ("classic"); break;
			  case 'a': printf ("alternate"); break;
			  case 'f': printf ("find");
				for (i=0; i<ncrit; i++) printf (" %u", critfind[i]);
				break;
			}
			printf (".");
		}
		printf ("\n");
	}
}

char *progname;

void usage ()
{
	fprintf (stderr, banner);
	fprintf (stderr, "Syntax: %s [coresize] [-options]\n", progname);
	fprintf (stderr, "coresize defaults to %u.  Must be first argument.\n", CORESIZE);
	fprintf (stderr, "-s #   test one step size\n");
	fprintf (stderr, "-m #   test numbers with this mod-factor\n");
	fprintf (stderr, "-l #   maximum step size [default coresize/2]\n");
	fprintf (stderr, "-b #   show # best (0 means don't sort) [default %d]\n", NBEST);
	fprintf (stderr, "-c...  criterion (-c means no scoring) [default -cc]\n");
	fprintf (stderr, "       -cc     classic formula    -ca alternate formula\n");
	fprintf (stderr, "       -cf #   find # [max. %d specs]\n", FINDS);
	fprintf (stderr, "-d...  same as -c but display only\n");
	fprintf (stderr, "-vqo   verbose / quiet / alternate output\n");
	exit (-1);
}

int main (argc, argv)
int argc;
char *argv[];
{
	int i, j;
	uint step=0, *beststep, stepstep=1;
	double score, *best, sign;

	sprintf (banner, BANNER, VERSION, DATE);
	progname = argv[0];
	if (argc == 1) usage();

	for (i=1; i<argc; i++)
	{
		if (argv[i][0] == '-')
		{
			switch (argv[i][1])
			{
			  case 'l':
				if (argv[++i]) sscanf (argv[i], "%u", &maxstep);
				else usage(); break;
			  case 's':
				if (argv[++i]) sscanf (argv[i], "%u", &step);
				else usage(); break;
			  case 'm':
				if (argv[++i]) sscanf (argv[i], "%u", &mod);
				else usage(); break;
			  case 'b':
				if (argv[++i]) sscanf (argv[i], "%d", &nbest);
				else usage(); break;

			  case 'd':
				switch (argv[i][2])
				{
				  case 'c': display |= DISP_CLASSIC; break;
				  case 'a': display |= DISP_ALTERNATE; break;
				  case 'f': display |= DISP_FIND;
					if (argv[++i])
					{
						for (; argv[i] && argv[i][0] != '-' && ndisp < FINDS; i++)
							sscanf (argv[i], "%d", &dispfind[ndisp++]);
						if (argv[i] && argv[i][0] == '-') i--;
					}
					else usage();
					break;
				  default: usage();
				}
				break;

			  case 'c':
				switch (criterion = argv[i][2])
				{
				  case 'c': sign = 1.0; break;
				  case 'a': sign = -1.0; break;
				  case 'f':
					if (argv[++i])
					{
						sign = -1.0;
						for (; argv[i] && argv[i][0] != '-' && ncrit < FINDS; i++)
							sscanf (argv[i], "%d", &critfind[ncrit++]);
						if (argv[i] && argv[i][0] == '-') i--;
					}
					else usage();
				  case 0: break;
				  default: usage();
				}
				break;

			  case 'v': verbose = 2; break;
			  case 'q': verbose = 0; break;
			  case 'o': printer = 1; verbose = 0; break;
			  case 'p': printer = 1; break;
			  default: usage();
			}
		}
		else
			sscanf (argv[i], "%u", &coresize);
	}

	size = (log (coresize) / log (10.0)) + 1.0;
	sprintf (tformat, "%%s %%%du", size);
	sprintf (rformat, " %%%du", size);
	sprintf (lformat, " %%-%du", size);

	if (step)
	{
		if (verbose)
		{
			if (printer) printf ("; ");
			printf (banner);
			nbest = mod = maxstep = 0;
			printsettings ();
		}

		score = makescore (step);
		printscore (step, score, 1);
		return 0;
	}

	if (mod && coresize % mod)
	{
		fprintf (stderr, "***** %u is not a divisor of %u !!!\n", mod, coresize);
		usage();
	}

	if (!maxstep) maxstep = coresize/2;
	if (verbose)
	{
		if (printer) printf ("; ");
		printf (banner);
		printsettings();
	}

	if (nbest)
	{
		best = (double*) calloc (nbest, sizeof(double));
		beststep = (uint*) calloc (nbest, sizeof(uint));
	}

	if (mod) stepstep = mod;
	else stepstep = 1;
	for (step = stepstep; step <= maxstep; step += stepstep)
	{
		if (mod && mod != modsize (step)) continue;

		if (criterion)
		{
			score = makescore (step);
			if (nbest)
			{
				for (i=0; i<nbest; i++)
				{
					if (score * sign > best[i] * sign || beststep[i] == 0)
					{
						if (verbose == 2) printscore (step, score, 0);
						for (j=nbest-1; j>i; j--)
						{
							best[j] = best[j-1];
							beststep[j] = beststep[j-1];
						}
						best[i] = score;
						beststep[i] = step;
						break;
					}
				}
			}
		}
		else printscore (step, -1.0, 1);
	}

	if (criterion)
	{
		if (verbose == 2)
		{
			if (printer) printf ("; ");
			printf ("Best:\n");
		}
		
		for (i=0; i<nbest; i++)
			printscore (beststep[i], best[i], 1);
	}
}