rand_points.c

生成直角Steiner树的程序包

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

	File:	rand_points.c
	Rev:	b-1
	Date:	02/28/2001

	Copyright (c) 1993, 2001 by David M. Warme

************************************************************************

	This program generates random point sets.

************************************************************************

	Modification Log:

	a-1:	02/21/93	warme
		: Created.
	a-2:	02/03/96	warme
		: Embedded the code that my own system uses for
		:  "rand/srand" so that this program produces
		:  the same (bad) mapping between seeds and
		:  sequences on all systems.
		: Added a much better random number generator
		:  using 64-bit shift register with XOR feedback.
		:  Perhaps now the point sets will start "looking"
		:  more random...
	b-1:	02/28/2001	warme
		: Process command line arguments in a more standard way.
		: Add usage() routine for when crud is given.

************************************************************************/

#include "steiner.h"
#include <time.h>


/*
 * Global Routines
 */

int			main (int, char **);


/*
 * External References
 */

	/* none */


/*
 * Local Equates
 */

#define	MAX_COORD	10000


/*
 * Local Routines
 */

static int16u		__rand (void);
static void		convert_seed (char *);
static int32u		cv_number (char *);
static void		decode_params (int, char **);
static void		generate_remainder_table (void);
static int32u		rand64 (int32u);
static int32u		random_coordinate (void);
static void		seed_to_string (char *, int32u, char *);
static void		usage (void);


/*
 * Local Variables
 */

static int		fflag;
static int32u		hi_seed;
static int32u		lo_seed;
static char *		me;
static int		npoints;
static int		oflag;
static bool		use_new_generator;

/*
 * This routine generates random point sets.
 */

	int
main (

int		argc,		/* IN - argument count. */
char **		argv		/* IN - argument vector. */
)
{
int			i;
int32u			x;
int32u			y;
char			sbuf [32];

	setbuf (stdout, NULL);

	decode_params (argc, argv);

	if (oflag NE 0) {
		if (use_new_generator) {
			/* Display seed in Hex. */
			seed_to_string (sbuf, 16, "0x");
		}
		else {
			/* Display seed in decimal. */
			seed_to_string (sbuf, 10, "");
		}
		fprintf ((oflag EQ 1) ? stdout : stderr,
			 "%% rand_points: seed = %s\n",
			 sbuf);
	}

	for (i = 0; i < npoints; i++) {
		x = random_coordinate ();
		if (NOT use_new_generator) {
			(void) __rand ();	/* Discard another number. */
		}
		y = random_coordinate ();
		(void) printf ("%5lu %5lu\n", x, y);
	}

	if (fflag NE 0) {
		if (use_new_generator) {
			/* Display seed in Hex. */
			seed_to_string (sbuf, 16, "0x");
		}
		else {
			/* Display seed in decimal. */
			seed_to_string (sbuf, 10, "");
		}
		fprintf ((oflag EQ 1) ? stdout : stderr,
			 "%% rand_points: final state = %s\n",
			 sbuf);
	}

	exit (0);
}

/*
 * This routine decodes the various command-line arguments.
 */

	static
	void
decode_params (

int		argc,
char **		argv
)
{
char *		ap;
char		c;

	--argc;
	me = *argv++;

	fflag = 0;
	oflag = 0;

	hi_seed = 1;
	lo_seed = 0;
	npoints = 10;

	while (argc > 0) {
		ap = *argv++;
		if (*ap NE '-') {
			npoints = cv_number (ap);
			break;
		}
		++ap;
		while ((c = *ap++) NE '\0') {
			switch (c) {
			case 'e':
				oflag = 2;
				break;

			case 'f':
				fflag = 1;
				break;

			case 'o':
				oflag = 1;
				break;

			case 'n':
				use_new_generator = TRUE;
				break;

			case 's':
				if (*ap EQ '\0') {
					if (argc <= 0) {
						usage ();
					}
					ap = *argv++;
					--argc;
				}
				convert_seed (ap);
				ap = "";
				break;

			case 'r':
				hi_seed = time (NULL);
				lo_seed = 0;
				break;

			default:
				usage ();
				break;
			}
		}
		--argc;
	}
}

/*
 * This routine prints out the proper usage and exits.
 */

static char *	arg_doc [] = {
	"",
	"\tGenerate N random points.  Default N is 10.",
	"",
	"\t-e\tWrite initial seed to stderr.",
	"\t-f\tWrite final seed to stderr (or stdout if -o given).",
	"\t-o\tWrite initial seed (and final seed if -f given) to stdout.",
	"\t-n\tUse newer (better) random generator.",
	"\t-s K\tSet random seed to K.",
	"\t-r\tRandomize: use current time as seed.",
	NULL
};

	static
	void
usage (void)

{
char **		pp;
char *		p;

	(void) fprintf (stderr,
			"\nUsage: %s [-efonr] [-s seed] [N]\n",
			me);

	pp = &arg_doc [0];
	while ((p = *pp++) NE NULL) {
		(void) fprintf (stderr, "%s\n", p);
	}
	exit (1);
}

/*
 * This routine converts the given string into a number.
 */

	static
	int32u
cv_number (

char *		num_string	/* IN - number to convert. */
)
{
char *		s;
int		c;
int32u		val;

	s = num_string;
	val = 0;
	while ((c = *s++) NE '\0') {
		if (NOT isdigit (c)) {
			(void) fprintf (stderr,
					"%s: `%s' is not a decimal number.\n",
					me, s);
			exit (1);
		}
		val = (val * 10) + (c - '0');
	}

	return (val);
}

/*
 * This routine converts the given ASCII string into a seed.  Either
 * decimal or Hex is accepted.
 */

	static
	void
convert_seed (

char *		string		/* IN - ASCII string to get seed from. */
)
{
char *		p;
int		i;
int		c;
int32u		carry;
int32u		base;
int16u		digs [4];

	p = string;

	base = 10;
	if ((p [0] EQ '0') AND (tolower (p [1]) EQ 'x')) {
		base = 16;
		p += 2;
	}

	for (i = 0; i < 4; i++) {
		digs [i] = 0;
	}

	for (;;) {
		c = *p++;
		if (c EQ '\0') {
			hi_seed = (((int32u) digs [2]) << 16) + digs [3];
			lo_seed = (((int32u) digs [0]) << 16) + digs [1];
			return;
		}

		/* Convert ASCII hex char to value */
		if (c < '0') c = -1;
		else if (c <= '9') c -= '0';
		else if (c < 'A') c = -1;
		else if (c <= 'F') c -= ('A' - 10);
		else if (c < 'a') c = -1;
		else if (c <= 'f') c -= ('a' - 10);
		else c = -1;

		if ((c < 0) OR (c >= base)) {
			fprintf (stderr,
				 "Warning: invalid seed: %s\n",
				 string);
			hi_seed = 1;
			lo_seed = 0;
			return;
		}

		carry = c;
		for (i = 3; i >= 0; i--) {
			carry += digs [i] * base;
			digs [i] = carry;
			carry >>= 16;
		}
	}
}

/*
 * This routine converts the current seed into a printable string
 * in the given base.