randomword.c

<B>Digital的Unix操作系统VAX 4.2源码</B>

     /* whb */ ILLEGAL_PAIR,
     /* whc */ ILLEGAL_PAIR,
     /* whd */ ILLEGAL_PAIR,
     /* whe */ BEGIN | NOT_END,
     /* whf */ ILLEGAL_PAIR,
     /* whg */ ILLEGAL_PAIR,
     /* whh */ ILLEGAL_PAIR,
     /* whi */ BEGIN | NOT_END,
     /* whj */ ILLEGAL_PAIR,
     /* whk */ ILLEGAL_PAIR,
     /* whl */ ILLEGAL_PAIR,
     /* whm */ ILLEGAL_PAIR,
     /* whn */ ILLEGAL_PAIR,
     /* who */ BEGIN | NOT_END,
     /* whp */ ILLEGAL_PAIR,
     /* whr */ ILLEGAL_PAIR,
     /* whs */ ILLEGAL_PAIR,
     /* wht */ ILLEGAL_PAIR,
     /* whu */ ILLEGAL_PAIR,
     /* whv */ ILLEGAL_PAIR,
     /* whw */ ILLEGAL_PAIR,
     /* whx */ ILLEGAL_PAIR,
     /* why */ BEGIN | NOT_END,
     /* whz */ ILLEGAL_PAIR,
     /* whch */ ILLEGAL_PAIR,
     /* whgh */ ILLEGAL_PAIR,
     /* whph */ ILLEGAL_PAIR,
     /* whrh */ ILLEGAL_PAIR,
     /* whsh */ ILLEGAL_PAIR,
     /* whth */ ILLEGAL_PAIR,
     /* whwh */ ILLEGAL_PAIR,
     /* whqu */ ILLEGAL_PAIR,
     /* whck */ ILLEGAL_PAIR,
     /* qua */ ANY_COMBINATION,
     /* qub */ ILLEGAL_PAIR,
     /* quc */ ILLEGAL_PAIR,
     /* qud */ ILLEGAL_PAIR,
     /* que */ ANY_COMBINATION,
     /* quf */ ILLEGAL_PAIR,
     /* qug */ ILLEGAL_PAIR,
     /* quh */ ILLEGAL_PAIR,
     /* qui */ ANY_COMBINATION,
     /* quj */ ILLEGAL_PAIR,
     /* quk */ ILLEGAL_PAIR,
     /* qul */ ILLEGAL_PAIR,
     /* qum */ ILLEGAL_PAIR,
     /* qun */ ILLEGAL_PAIR,
     /* quo */ ANY_COMBINATION,
     /* qup */ ILLEGAL_PAIR,
     /* qur */ ILLEGAL_PAIR,
     /* qus */ ILLEGAL_PAIR,
     /* qut */ ILLEGAL_PAIR,
     /* quu */ ILLEGAL_PAIR,
     /* quv */ ILLEGAL_PAIR,
     /* quw */ ILLEGAL_PAIR,
     /* qux */ ILLEGAL_PAIR,
     /* quy */ ILLEGAL_PAIR,
     /* quz */ ILLEGAL_PAIR,
     /* quch */ ILLEGAL_PAIR,
     /* qugh */ ILLEGAL_PAIR,
     /* quph */ ILLEGAL_PAIR,
     /* qurh */ ILLEGAL_PAIR,
     /* qush */ ILLEGAL_PAIR,
     /* quth */ ILLEGAL_PAIR,
     /* quwh */ ILLEGAL_PAIR,
     /* ququ */ ILLEGAL_PAIR,
     /* quck */ ILLEGAL_PAIR,
     /* cka */ NOT_BEGIN | BREAK | NOT_END,
     /* ckb */ NOT_BEGIN | BREAK | NOT_END,
     /* ckc */ NOT_BEGIN | BREAK | NOT_END,
     /* ckd */ NOT_BEGIN | BREAK | NOT_END,
     /* cke */ NOT_BEGIN | BREAK | NOT_END,
     /* ckf */ NOT_BEGIN | BREAK | NOT_END,
     /* ckg */ NOT_BEGIN | BREAK | NOT_END,
     /* ckh */ NOT_BEGIN | BREAK | NOT_END,
     /* cki */ NOT_BEGIN | BREAK | NOT_END,
     /* ckj */ NOT_BEGIN | BREAK | NOT_END,
     /* ckk */ NOT_BEGIN | BREAK | NOT_END,
     /* ckl */ NOT_BEGIN | BREAK | NOT_END,
     /* ckm */ NOT_BEGIN | BREAK | NOT_END,
     /* ckn */ NOT_BEGIN | BREAK | NOT_END,
     /* cko */ NOT_BEGIN | BREAK | NOT_END,
     /* ckp */ NOT_BEGIN | BREAK | NOT_END,
     /* ckr */ NOT_BEGIN | BREAK | NOT_END,
     /* cks */ NOT_BEGIN,
     /* ckt */ NOT_BEGIN | BREAK | NOT_END,
     /* cku */ NOT_BEGIN | BREAK | NOT_END,
     /* ckv */ NOT_BEGIN | BREAK | NOT_END,
     /* ckw */ NOT_BEGIN | BREAK | NOT_END,
     /* ckx */ ILLEGAL_PAIR,
     /* cky */ NOT_BEGIN,
     /* ckz */ NOT_BEGIN | BREAK | NOT_END,
     /* ckch */ NOT_BEGIN | BREAK | NOT_END,
     /* ckgh */ NOT_BEGIN | BREAK | NOT_END,
     /* ckph */ NOT_BEGIN | BREAK | NOT_END,
     /* ckrh */ ILLEGAL_PAIR,
     /* cksh */ NOT_BEGIN | BREAK | NOT_END,
     /* ckth */ NOT_BEGIN | BREAK | NOT_END,
     /* ckwh */ ILLEGAL_PAIR,
     /* ckqu */ NOT_BEGIN | BREAK | NOT_END,
     /* ckck */ ILLEGAL_PAIR
};


static int *tab;		/* honeywell loader deficiency */
static long p[] =
{
    399871,
    399887,
    399899,
    399911,
    399913,
    399937,
    399941,
    399953,
    399979,
    399983,
    399989,
};

/*
* Hash table for spelling checker has n bits.
* Each word w is hashed by k different (modular) hash functions, hi.
* The bits hi(w), i=1..k, are set for words in the dictionary.
* Assuming independence, the probability that no word of a d-word
* dictionary sets a particular bit is given by the Poisson formula
* P = exp(-y)*y**0/0!, where y=d*k/n.
* The probability that a random string is recognized as a word is then
* (1-P)**k.  For given n and d this is minimum when y=log(2), P=1/2,
* whence one finds, for example, that a 25000-word dictionary in a
* 400000-bit table works best with k=11.
*/

static long pow2[NP][NW];


/*
 *	Copyright August, 1983		Steven M. Kramer
 *
 * Randomword will generate a random word and place it in the
 * buffer word.  Also, the hyphenated word will be placed into
 * the buffer hyphenated_word.  Both word and hyphenated_word must
 * be pre-allocated.  The words generated will have sizes between
 * min and max.  If limit is TRUE, words will not be generated that
 * appear as login names or as entries in the on-line dictionary.
 * This algorithm was initially worded out by Morrie Gasser in 1975.
 * Any changes here are minimal so that as many word combinations
 * can be produced as possible (and thus keep the words random).
 * The length of the unhyphenated word is returned.
 */
randomword (word, hyphenated_word, min, max, limit)
register char  *word;
register char  *hyphenated_word;
register unsigned short int min;
register unsigned short int max;
register    boolean limit;
{
    static  been_here_before;
    static  dict_error;
    int     length;
    int     i;
    int     j;
    long    h;
    register long  *lp;
    FILE * f;

 /* 
  * Check for min==0 and min>max.  Return null words
  * and a length of 0.
  */
    if ((min == 0) || (min > max))
    {
	word[0] = '\0';
	hyphenated_word[0] = '\0';
	return (0);
    }

 /* 
  * Execute this upon startup.  This initializes the
  * environment, including seed'ing the random number
  * generator and loading the online dictionary.
  */
    if (!been_here_before)
    {
	been_here_before = TRUE;

/*
	srandom ((int) time ((time_t *) 0));
*/
	{ 
		char buff[18];
		makeseed(buff, sizeof buff);
		randseed(&buff[0]);
	}

	if (limit)
	/* 
	 Read in the hashed dictionary from disk.
	 Then initialize the hashing function.
	 */
	    if (((tab = (int *) calloc (sizeof (*tab), TABSIZE)) == NULL)
		    || ((f = fopen (WORDS, "r")) == NULL))
		dict_error = TRUE;
	    else
	    {
		if (fread ((char *) tab, sizeof (*tab),
			    TABSIZE, f) != TABSIZE)
		    dict_error = TRUE;
		(void) fclose (f);
		if (!dict_error)
		    for (i = 0; i < NP; i++)
		    {
			h = *(lp = pow2[i]) = 1 << 14;
			for (j = 1; j < NW; j++)
			    h = *++lp = (h << 7) % p[i];
		    }
	    }
    }

 /* 
  * Continue finding words until the criteria are satisfied.
  * The criteria are, if limit is set, that if the word appears
  * as either a login name or as part of the online dictionary,
  * throw out the word and look for another.
  */
    do
    {
    /* 
     * Get a random word.  Its length is a random quantity
     * from with the limits specified in the call to
     * randomword().
     */
	length = get_word (word, hyphenated_word, get_random (min, max));

	if (limit)
	    limit = been_here_before && ((!dict_error && lookup (word)) ||
		    (getpwnam (word) != NULL));
    }
    while (limit && been_here_before);

    return (length);
}


/*
	Given that the online dictionary is loaded, the lookup()
	routine checks a word against all the words in the (hashed)
	online incore dictionary.  It returns true if the word has
	been found in the dictionary.
*/
boolean lookup (word)
register char  *word;
{
    register int    length;
    register int    scan;
    register long   h;
    register long  *lp;
    register int    i;

    length = strlen (word);
    for (i = 0; i < NP; i++)
    {
	for (scan = 0, h = 0, lp = pow2[i]; scan < length;
		++scan, ++lp)
	    h += word[scan] * *lp;
	h += '\n' * *lp;
	h %= p[i];
	if (get (h) == 0)
	    return (0);
    }
    return (1);
}


/*
	This is the routine that returns a random word -- as
	yet unchecked against the passwd file or the dictionary.
	It collects random syllables until a predetermined
	word length is found.  If a retry threshold is reached,
	another word is tried.  Given that the random number
	generator is uniformly distributed, eventually a word
	will be found if the retry limit is adqeuately large enough.
*/
get_word (word, hyphenated_word, length)
char   *word;
char   *hyphenated_word;
unsigned short int  length;
{
    register unsigned short int word_length;
    register unsigned short int syllable_length;
    register char  *new_syllable;
    register unsigned short int *syllable_units;
    register unsigned short int word_size;
    register unsigned short int word_place;
    int unsigned short *word_units;
    int unsigned short  syllable_size;
    int unsigned    tries;

 /* 	Keep count of retries.	 */
    tries = 0;

 /* 	The length of the word in characters.	 */
    word_length = 0;

 /* 	The length of the word in character units (each of which is one or
    two characters long.	 */
    word_size = 0;

 /* 	Initialize the array storing the word units.  Since we know the
    length of the word, we only need one of that length.  This method is
    preferable to a static array, since it allows us flexibility in
    choosing arbitrarily long word lengths.  Since a word can contain one
    syllable, we should make syllable_units, the array holding the
    analgous units for an individual syllable, the same length.  No
    explicit rule limits the length of syllables, but digram rules and
    heuristics do so indirectly. */
    word_units =
	(unsigned short int *)
	calloc (sizeof (unsigned short int), length);
    syllable_units =
	(unsigned short int *)
	calloc (sizeof (unsigned short int), length);
    new_syllable =
	calloc (sizeof (unsigned short int), length);

 /* 	Find syllables until the entire word is constructed.	 */
    while (word_length < length)
    {
    /* 	Get the syllable and find its length.	 */
	(void) get_syllable (new_syllable, length - word_length,
		syllable_units, &syllable_size);
	syllable_length = strlen (new_syllable);

    /* 	Append the syllable units to the word units.	 */
	for (word_place = 0; word_place <= syllable_size; word_place++)
	    word_units[word_size + word_place] =
		syllable_units[word_place];
	word_size += syllable_size + 1;

    /* 
     If the word has been improperly formed, throw out
     the syllable.  The checks performed here are those
     trhat must be formed on a word basis.  The other
     tests are performed entirely within the syllable.
     Otherwise, append the syllable to the word and
     append the syllable to the hyphenated version of
     the word.
     */
	if (improper_word (word_units, word_size) ||
		((word_length == 0) &&
		    have_initial_y (syllable_units, syllable_size)) ||
		((word_length + syllable_length == length) &&
		    have_final_split (syllable_units, syllable_size)))
	    word_size -= syllable_size + 1;
	else
	{
	    if (word_length == 0)
	    {
		(void) strcpy (word, new_syllable);
		(void) strcpy (hyphenated_word, new_syllable);
	    }
	    else
	    {
		(void) strcat (word, new_syllable);
		(void) strcat (hyphenated_word, "-");
		(void) strcat (hyphenated_word, new_syllable);
	    }
	    word_length += syllable_length;
	}

    /* 
     * Keep track of the times we have tried to get
     * syllables.  If we have exceeded the threshold,
     * reinitialize the length and size variables, clear
     * out the word arrays, and start from scratch.
     */
	tries++;
	if (tries > MAX_RETRIES)
	{
	    word_length = 0;
	    word_size = 0;
	    tries = 0;
	    (void) strcpy (word, "");
	    (void) strcpy (hyphenated_word, "");
	}
    }

 /* 
  * The units arrays and syllable storage are internal to this
  * routine.  Since the caller has no need for them, we
  * release the space.
  */
    free ((char *) new_syllable);
    free ((char *) syllable_units);
    free ((char *) word_units);

    return ((int) word_length);