home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.ee.pdx.edu
/
2014.02.ftp.ee.pdx.edu.tar
/
ftp.ee.pdx.edu
/
pub
/
frp
/
util
/
name2
/
names2.c
Wrap
C/C++ Source or Header
|
1991-03-09
|
19KB
|
838 lines
/* names2.c */
/* Random name generator */
/* Richard Kennaway */
/* INTERNET: jrk@uk.ac.uea.sys */
/* UUCP: ...mcvax!uea-sys!jrk */
/* Public domain! */
/* August 1989: First version. */
/* January 1990: Ported to MPW3.
Removed some untidiness (lint warnings).
Print randseed to stderr and take randseed as option
to allow reproducibility.
Better representation of tetragraph table.
Ability to specify character set. */
/* March 1990: Additional patches by Martin J. Laubach
for Amiga compatibility, ANSI standard prototypes,
and elimination of some more lint warnings */
/* March 1990: Fixed the bug preventing it working on many cpus, due to
assumptions about byte-ordering. Thanks to Carl Lowenstein
for finding this. */
#define FALSE 0
#define TRUE 1
/* Choose one... */
#define UNIX TRUE /* Version for Unix */
/* #define MPW FALSE /* Version for Apple Macintosh (MPW C) */
/* #define AMIGA TRUE /* Version for Commodore Amiga (Lattice C) -- automatically defined */
/* If MPW is TRUE, define one of MPW2 or MPW3 as TRUE, the other as FALSE. */
#define MPW2 FALSE /* MPW version 2 */
#define MPW3 FALSE /* MPW version 3 */
/* System declarations */
#include <stdio.h>
#if MPW
#include <Memory.h> /* For BlockMove(). */
#include <QuickDraw.h> /* For random numbers. */
#include <OSUtils.h> /* For GetDateTime(). */
#endif
#define EOFCHAR (-1)
#ifdef __STDC__
#include <stdlib.h> /* for malloc(), free(), rand(), srand() */
#include <string.h> /* for memcoy() */
#include <time.h> /* for time() */
#else
extern char *malloc();
#endif
/* Compatibility */
typedef char int8;
typedef unsigned char uint8;
typedef short int16;
typedef unsigned short uint16;
typedef unsigned long uint32;
typedef long int32;
#define MAXUINT8 ((uint8) ((int8) (-1)))
#define MAXUINT16 ((uint16) ((int16) (-1)))
#define MAXUINT32 ((int32) ((int32) (-1)))
#define NUMCHARS 256
#define CHARMASK 255
#define CHARBITS 8
#define FIRSTCHAR(x) ((uint8) (((x) >> CHARBITS) & CHARMASK))
#define SECONDCHAR(x) ((uint8) ((x) & CHARMASK))
#define chartoint(c) ((int16)(uint8)(c))
#define A_CHAR chartoint('A')
#define Z_CHAR chartoint('Z')
#define a_CHAR chartoint('a')
#define z_CHAR chartoint('z')
#define SPACE_CHAR chartoint(' ')
#define A_TO_a (a_CHAR-A_CHAR)
#if MPW2
#define NEWLINECHAR chartoint('\r')
#endif
#if UNIX || MPW3 || AMIGA
#define NEWLINECHAR chartoint('\n')
/* Note: the actual value of '\n' is different in UNIX and MPW3,
and '\n' in MPW3 is the same as '\r' in MPW2. */
#endif
/* Where is the random number generator? */
#if UNIX
typedef char *Ptr;
#define Boolean int
#define BlockMove bcopy
int32 random();
#define Random() ((int16) (random()))
#endif
#if AMIGA
typedef char *Ptr;
#define Boolean uint16
#define BlockMove(from,to,size) memcpy(to,from,size)
#define random() rand()
#define srandom(x) srand(x)
int32 random();
#define Random() ((int16) (random()))
int rand(void); /* bug in include files */
void srand(unsigned int);
#endif
uint32 RandSeed;
/* Globals. */
int Argc;
unsigned char **Argv;
int ExitStatus = 0;
Boolean FileArgs = FALSE, Big = TRUE, SeparateWords = TRUE;
Boolean CaseSignificant = FALSE, Letters[NUMCHARS];
int16 CurFile;
/* Layout. */
#define BREAK1 60
#define BREAK2 75
int16 Column = 0;
int32 Lines = 0;
#define DEFAULTMAXLINES 20
int32 MaxLines = DEFAULTMAXLINES;
/* Tables */
int16 NumChars = 0;
#define SPACEINDEX 0
int32 t2size, t3size, t4size;
#define NOTCHOICE MAXUINT16
int16 CharToIndex[NUMCHARS], IndexToChar[NUMCHARS];
int32 table0 = 0,
*table1 = NULL,
*table2 = NULL;
#define BLOCKSIZE(n) (sizeof(int32) + sizeof(int32) + (n)*sizeof(uint16))
#define INITSIZE 10
#define GROWNUM 5
#define GROWDEN 4
typedef struct DigraphBlock {
int32 size, maxsize;
uint16 data[1];
} DigraphBlockRec, *DigraphBlockPtr;
DigraphBlockPtr *quadtable = NULL;
/*-------------------------------------------------------------------------*/
#ifdef __STDC__
# define P(s) s
#else
# define P(s) ()
#endif
void SortArray P((uint16 *, int32 ));
char *trymemory P((int32 bytesNeeded , Boolean mustGet ));
void zero P((char *start , int32 numBytes ));
void getmemory P((void ));
void setchar P((uint8 c , Boolean accept ));
void setchars P((uint8 *s , Boolean accept ));
void maketranstable P((void ));
Boolean openfile P((void ));
Boolean getnextfile P((void ));
int16 getrawchar P((void ));
int16 nextchar P((void ));
DigraphBlockPtr NewBlock P((int32 size ));
Boolean insertdigraph P((DigraphBlockPtr *t , uint16 cd ));
void entergroup P((int16 d ));
void buildtable P((void ));
void showtable P((void ));
uint16 Rand16 P((void ));
int32 randint P((int32 max ));
uint16 randchoice32 P((int32 tot , int32 *dist ));
void cleanupquads P((void ));
uint16 randtrip P((uint8 a , uint8 b ));
uint16 randquad P((uint8 a , uint8 b , uint8 c ));
void outchar P((int16 c ));
void generateword P((void ));
void generate P((void ));
void usageerror P((void ));
void processoptions P((void ));
void SeedRand P((void ));
void MakeHeap P((int32 theElement, int32 numElements));
int main P((int argc , uint8 **argv ));
#undef P
/*-------------------------------------------------------------------------*/
/* Memory allocation */
char *trymemory( bytesNeeded, mustGet )
int32 bytesNeeded;
Boolean mustGet;
{
char *result;
result = (char *) malloc( bytesNeeded );
if ((result==NULL) && (mustGet)) {
fprintf( stderr, "Could not get %lu bytes - terminating.%c",
bytesNeeded, NEWLINECHAR );
ExitStatus = 1;
exit( ExitStatus );
}
return( result );
} /* char *trymemory( bytesNeeded, mustGet ) */
void zero( start, numBytes )
char *start;
int32 numBytes;
{
/* Your system may well have a faster way of zeroing memory. */
/* In fact, the static arrays to which this procedure is applied */
/* may be automatically initialised to zero already. */
/* But portability would be impaired by asssuming that. */
int32 remainder, i, num32bits;
remainder = numBytes % ((int32) 4);
for (i=1; i <= remainder; i++) start[numBytes-i] = 0;
num32bits = numBytes / ((int32) 4);
for (i=0; i<num32bits; i++) ((int32 *) start)[i] = 0;
} /* void zero( start, numBytes ) */
void getmemory()
{
int32 i;
table1 = (int32 *) trymemory( NumChars * sizeof(int32), TRUE );
table2 = (int32 *) trymemory( t2size * sizeof(int32), TRUE );
quadtable = (DigraphBlockPtr *) trymemory( t2size * sizeof(DigraphBlockPtr), TRUE );
zero( (char *) table1, NumChars * sizeof(int32) );
zero( (char *) table2, t2size * sizeof(int32) );
for (i=0; i<t2size; i++) quadtable[i] = NULL;
} /* void getmemory() */
/* Preliminary setup */
void setchar( c, accept )
uint8 c;
Boolean accept;
{
Letters[c] = accept;
if (! CaseSignificant) {
if ((A_CHAR <= c) && (c <= Z_CHAR)) Letters[c + A_TO_a] = accept;
if ((a_CHAR <= c) && (c <= z_CHAR)) Letters[c - A_TO_a] = accept;
}
} /* void setchar( c, accept ) */
void setchars( s, accept )
uint8 *s;
Boolean accept;
{
int16 i;
uint8 c;
if (s==NULL) return;
i = 0;
while ((c = s[i++]) != 0) setchar( c, accept );
} /* void setchars( s, accept ) */
void maketranstable()
{
int16 c;
for (c=0; c < NUMCHARS; c++) {
CharToIndex[(uint8)c] = SPACEINDEX;
IndexToChar[(uint8)c] = SPACE_CHAR;
}
NumChars = 1;
if (!CaseSignificant) {
for (c=a_CHAR; c<= z_CHAR; c++) {
if (Letters[(uint8)(c - A_TO_a)] != Letters[(uint8)c]) {
Letters[(uint8)c] = TRUE;
Letters[(uint8)(c - A_TO_a)] = TRUE;
}
}
}
for (c=0; c < NUMCHARS; c++) {
if (Letters[(uint8)c] && (CaseSignificant || (c < A_CHAR) || (Z_CHAR < c))) {
CharToIndex[(uint8)c] = NumChars;
IndexToChar[(uint8)NumChars] = c;
NumChars++;
}
}
if (!CaseSignificant) {
for (c=a_CHAR; c<= z_CHAR; c++) {
CharToIndex[(uint8)(c - A_TO_a)] = CharToIndex[(uint8)c];
}
}
IndexToChar[(uint8)SPACEINDEX] = SPACE_CHAR;
t2size = NumChars*NumChars;
t3size = t2size*NumChars;
t4size = t2size*t2size;
} /* void maketranstable() */
/* Input */
Boolean openfile()
{
FILE *temp;
temp = freopen( Argv[CurFile], "r", stdin );
if (temp == NULL) {
fprintf( stderr, "%s: could not open file \"%s\"%c",
Argv[0], Argv[CurFile], NEWLINECHAR );
ExitStatus = 2;
}
return( (Boolean)( temp != NULL ) );
} /* Boolean openfile() */
Boolean getnextfile()
{
while (((++CurFile) < Argc) && (! openfile())) { /* nothing */ }
return( (Boolean)( CurFile < Argc ) );
} /* Boolean getnextfile() */
int16 getrawchar()
{
int16 c;
c = getchar();
while ((c==EOFCHAR) && getnextfile()) {
c = getchar();
}
return(c);
} /* int16 getrawchar() */
#define WASSPACE 0
#define WASNONSPACE 1
#define END 2
int16 Where = WASSPACE;
int16 nextchar()
{
int16 c;
switch (Where) {
case WASSPACE:
while (((c = getrawchar()) != EOFCHAR) &&
(!Letters[(uint8)c])) {
/* nothing */
}
if (c==EOFCHAR) {
Where = END;
return(-1);
} else {
Where = WASNONSPACE;
return(CharToIndex[(uint8)c]);
}
case WASNONSPACE:
c = getrawchar();
if (c==EOFCHAR) {
Where = END;
return(SPACEINDEX);
} else if (Letters[(uint8)c]) {
return(CharToIndex[(uint8)c]);
} else {
Where = WASSPACE;
return(SPACEINDEX);
}
case END:
return(-1);
}
return(-1); /* Never happens. */
} /* int16 nextchar() */
DigraphBlockPtr NewBlock( size )
int32 size;
{
DigraphBlockPtr temp;
temp = (DigraphBlockPtr) malloc( BLOCKSIZE(size) );
return( temp );
} /* DigraphBlockPtr NewBlock( size ) */
Boolean insertdigraph( t, cd )
DigraphBlockPtr *t;
uint16 cd;
{
DigraphBlockPtr temp;
int32 newSize;
if (t==NULL) return( FALSE );
if (((*t)==NULL) || ((*t)->size >= (*t)->maxsize)) {
newSize = (*t)==NULL ? INITSIZE : ((*t)->size * GROWNUM)/GROWDEN;
temp = NewBlock( newSize );
if (temp==NULL) return( FALSE );
if ((*t)==NULL) {
temp->size = 1;
} else {
BlockMove( (Ptr) (*t), (Ptr) temp, BLOCKSIZE((*t)->size) );
temp->size = (*t)->size + 1;
free( (char *) (*t) );
}
temp->maxsize = newSize;
*t = temp;
(*t)->data[(*t)->size-1] = cd;
} else {
(*t)->data[(*t)->size++] = cd;
}
return( TRUE );
} /* Boolean insertdigraph( t, cd ) */
int16 AA = 0, BB = 0, CC = 0;
void entergroup( d )
int16 d;
{
int32 ab, cd;
ab = AA*NumChars + BB;
cd = CC*NUMCHARS + d;
if (table2[ab] < MAXUINT16) {
if (insertdigraph( &(quadtable[ab]), (uint16) cd )) {
table0++;
table1[d]++;
table2[ab]++;
}
}
AA = BB; BB = CC; CC = d;
} /* void entergroup( d ) */
void buildtable()
{
int16 a0, b0, c0, d;
a0 = nextchar();
if (a0==SPACEINDEX) a0 = nextchar();
b0 = nextchar();
c0 = nextchar();
if (c0 == -1) return;
AA = a0; BB = b0; CC = c0;
while ((d = nextchar()) != (-1)) {
entergroup( d );
}
if (CC==SPACEINDEX) {
entergroup( a0 );
entergroup( b0 );
entergroup( c0 );
} else {
entergroup( SPACEINDEX );
entergroup( a0 );
entergroup( b0 );
entergroup( c0 );
}
} /* void buildtable() */
#ifdef SHOWTABLE
/* Dump the tables. */
/* Only called if SHOWTABLE is defined at compile time. */
void showtable()
{
uint8 i, j, k;
int32 *t2;
uint16 *t4;
for (i=0; i<NumChars; i++) if (table1[i] != 0) {
printf( "%c\t%lu%c", IndexToChar[i], table1[i], NEWLINECHAR );
t2 = table2 + i*NumChars;
for (j=0; j<NumChars; j++) if (t2[j] != 0) {
printf( "%c%c\t%u", IndexToChar[i], IndexToChar[j], t2[j] );
t4 = quadtable[i*NumChars + j]->data;
for (k=0; k<t2[j]; k++) {
if ((k%20==0) && (k>0)) { putchar( NEWLINECHAR ); putchar( '\t' ); }
putchar( ' ' );
putchar( IndexToChar[ FIRSTCHAR(t4[k]) ] );
putchar( IndexToChar[ SECONDCHAR(t4[k]) ] );
}
putchar( NEWLINECHAR );
}
putchar( NEWLINECHAR );
}
fflush( stdout );
} /* void showtable() */
#endif
/* Generation of output */
uint16 Rand16()
{
return( (uint16) Random() );
} /* uint16 Rand16() */
int32 randint( max )
int32 max;
{
if (max==0) return( 0 );
if (max <= MAXUINT16) return( ((int32) Rand16())%max );
return( ((((int32) Random()) << 16) + ((int32) Random())) % max );
} /* int32 randint( max ) */
uint16 randchoice32( tot, dist )
int32 tot;
int32 *dist;
{
int32 i;
uint8 j;
if (tot==0) return(NOTCHOICE);
i = randint( tot );
for (j=0; j<NumChars; j++) {
if (i < dist[j]) return( (uint16)(j) );
i -= dist[j];
}
return((uint16)( NOTCHOICE )); /* Should never happen. */
} /* uint16 randchoice32( tot, dist ) */
void cleanupquads()
{
int32 i;
for (i=0; i<t2size; i++) if (table2[i] > 0) {
SortArray( quadtable[i]->data, quadtable[i]->size );
}
} /* cleanupquads() */
uint16 randtrip( a, b )
uint8 a, b;
{
uint16 aNb;
int32 t2;
uint16 *t4;
int32 r;
aNb = a*NumChars+b;
t2 = table2[ aNb ];
t4 = quadtable[ aNb ]->data;
r = randint( t2 );
return( (uint16) FIRSTCHAR(t4[r]) );
} /* uint16 randtrip( a, b ) */
uint16 randquad( a, b, c )
uint8 a, b, c;
{
uint16 aNb;
int32 t2;
uint16 *t4;
int32 lo, hi, i, r;
uint8 c1;
aNb = a*NumChars+b;
t2 = table2[ aNb ];
t4 = quadtable[ aNb ]->data;
lo = 0;
hi = 0;
for (i=0; i<t2; i++) {
c1 = FIRSTCHAR(t4[i]);
if (c1 <= c){
hi++;
if (c1 < c) lo++;
} else break;
}
if (lo >= hi) {
/* This should never happen. */
return( NOTCHOICE );
}
r = lo + randint( hi-lo );
return( (uint16) SECONDCHAR(t4[r]) );
} /* uint16 randquad( a, b, c ) */
void outchar( c )
int16 c;
{
if (Column < BREAK1) {
putchar(c); Column++;
} else if (c==chartoint(' ')) {
putchar( NEWLINECHAR );
Column = 0; Lines++;
} else if (Column >= BREAK2) {
putchar('-'); putchar( NEWLINECHAR );
Column = 0; Lines++;
if (Lines < MaxLines) {
putchar(c); Column++;
}
} else {
putchar(c); Column++;
}
} /* void outchar( c ) */
void generateword()
{
uint16 a, b, c, d;
a = (uint16)SPACEINDEX;
b = randchoice32( (int32) (table1[a]), table2 + a*NumChars );
if (b==NOTCHOICE) return;
outchar( IndexToChar[(uint8)b] );
if (SeparateWords && (b==SPACEINDEX)) return;
c = randtrip( (uint16)SPACEINDEX, (uint8)b );
outchar( IndexToChar[(uint8)c] );
if (SeparateWords && (c==(uint16)SPACEINDEX)) return;
while (Lines < MaxLines) {
d = Big ? randquad( (uint8)a, (uint8)b, (uint8)c )
: randtrip( (uint8)b, (uint8)c );
if (d==NOTCHOICE) {
outchar( '.' );
return;
}
outchar( IndexToChar[(uint8)d] );
if (SeparateWords && (d==(uint16)SPACEINDEX)) return;
a = b; b = c; c = d;
}
} /* void generateword() */
void generate()
{
if (table0 > 0) while (Lines < MaxLines) generateword();
putchar('\n');
} /* void generate() */
/* Argument parsing */
void usageerror()
{
fprintf( stderr, "Usage: %s [-3] [-s|-w] [-c] [-axxxx] [-dxxxx] [-lnnn] [-rnnn] [file]%c",
Argv[0], NEWLINECHAR );
fprintf( stderr, "\t-3: 3rd-order statistics.%c",
NEWLINECHAR );
fprintf( stderr, "\t-w: Successive words are independent (default).%c",
NEWLINECHAR );
fprintf( stderr, "\t-s: (Sentences) Successive words are dependent.%c",
NEWLINECHAR );
fprintf( stderr, "\t-c: Treat case differences as significant.%c",
NEWLINECHAR );
fprintf( stderr, "\t-axxxx: Accept characters in string \"xxxx\" as 'letters'.%c",
NEWLINECHAR );
fprintf( stderr, "\t-dxxxx: Treat characters in string \"xxxx\" as spaces.%c",
NEWLINECHAR );
fprintf( stderr, "\tSuccessive -a/-d options are processed sequentially.%c",
NEWLINECHAR );
fprintf( stderr, "\t-lnnn: Generate nnn lines of output (default %d).%c",
DEFAULTMAXLINES, NEWLINECHAR );
fprintf( stderr, "\t-rnnn: Specify random generator seed.%c",
DEFAULTMAXLINES, NEWLINECHAR );
fputc( NEWLINECHAR, stderr );
ExitStatus = 1;
exit( ExitStatus );
} /* void usageerror() */
void processoptions()
{
int16 i;
/* getopt()? What's that? :-) */
CaseSignificant = FALSE;
for (i=0; i<NUMCHARS; i++) Letters[(uint8)i] = FALSE;
setchars( (uint8 *) "abcdefghijklmnopqrstuvwxyz", TRUE );
CurFile = Argc;
for (i=1; i<Argc; i++) {
if (Argv[i][0] == '-') {
switch (Argv[i][1]) {
case 's':
SeparateWords = FALSE;
break;
case 'w':
SeparateWords = TRUE;
break;
case 'a':
setchars( &(Argv[i][1]), TRUE );
break;
case 'd':
setchars( &(Argv[i][1]), TRUE );
break;
case 'c':
CaseSignificant = TRUE;
break;
case '3':
Big = FALSE;
break;
case 'l':
if (Argv[i][2]==0) {
MaxLines = MAXUINT32;
} else if ((sscanf( &(Argv[i][2]), "%lu", &MaxLines ) != 1) ||
(MaxLines < 0)) {
usageerror(); /* exits */
}
break;
case 'r':
if ((Argv[i][2] != 0) &&
(sscanf( &(Argv[i][2]), "%lu", &RandSeed ) != 1)) {
usageerror(); /* exits */
}
break;
default:
usageerror(); /* exits */
}
} else if (Argv[i][0] == 0) {
FileArgs = FALSE;
} else {
FileArgs = TRUE;
CurFile = i-1;
(void) getnextfile();
return;
}
}
} /* void processoptions() */
/* Control */
void SeedRand()
{
#if MPW
qd.randSeed = (int32) RandSeed;
#endif
#if UNIX || AMIGA
srandom( RandSeed );
#endif
} /* void SeedRand() */
main( argc, argv )
int argc;
uint8 **argv;
{
Argc = argc; Argv = argv;
#if MPW
InitGraf( &(qd.thePort) ); /* for random numbers */
GetDateTime( &RandSeed );
#endif
#if UNIX
RandSeed = time(0);
#endif
#if AMIGA
RandSeed = time(0);
#endif
processoptions();
SeedRand();
maketranstable();
getmemory();
fprintf( stderr, "Reading input...%c", NEWLINECHAR );
buildtable();
fprintf( stderr, "%d different letters, %u characters input. Randseed = %lu%c",
NumChars-1, table0, RandSeed, NEWLINECHAR );
if (table0 > 0) {
#ifdef SHOWTABLE
showtable();
#endif
if (Big) cleanupquads();
#ifdef SHOWTABLE
showtable();
#endif
generate();
fflush( stdout );
}
exit( ExitStatus );
} /* main() */
/* Heapsort. */
static uint16 *TheArray;
uint16 Temp;
#define SWAPITEM( i, j ) \
Temp = TheArray[(i)]; \
TheArray[(i)] = TheArray[(j)]; \
TheArray[(j)] = Temp \
static void MakeHeap( theElement, numElements )
int32 theElement, numElements;
{
int32 left, right;
while ((left = theElement+theElement+1L) < numElements) {
right = left+1L;
if (TheArray[theElement] < TheArray[left]) {
if ((right < numElements) &&
(TheArray[left] < TheArray[right])) {
/* M<L<R */
SWAPITEM( theElement, right );
theElement = right;
} else { /* M<L, M<R<L, R<M<L */
SWAPITEM( theElement, left );
theElement = left;
}
} else if ((right < numElements) &&
(TheArray[theElement] < TheArray[right])) {
/* L<M<R */
SWAPITEM( theElement, right );
theElement = right;
} else {
/* L<M, L<R<M, R<L<M */
break;
}
}
} /* static void MakeHeap( theElement, numElements ) */
static void SortArray( theArray, length )
uint16 *theArray;
int32 length;
{
int32 i;
TheArray = theArray;
for (i = (length / 2L) - 1L; i >= 0L; i--) {
MakeHeap( i, length );
}
for (i = length-1L; i >= 1L; i--) {
SWAPITEM( 0L, i );
MakeHeap( 0L, i );
}
} /* static void SortArray( theArray, length ) */