pronounce.c

keyring是一种用于保护PALM中关键信息的系统

/* -*- c-file-style: "java"; -*-
 *
 * $Header: /cvsroot/gnukeyring/keyring/pronounce.c,v 1.7 2003/10/26 14:03:41 hoenicke Exp $
 * 
 * Keyring -- store passwords securely on a handheld
 * Copyright (C) 2002-2003 Jochen Hoenicke <[e-mail]>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

/*
                                                 
The following is a listing of the source code referenced in the
Appendix A of the Automated Password Generator Standard, extracted
from http://www.eff.org/Privacy/Newin/New_nist/fips181.txt on 8 May
2002.  There is no licensing information regarding this code in the
above document, however, it seems clear that it is intended to be used
as a reference implementation.  Derivative works would therefore be
OK.

The idea and first implementation to use this code in keyring is due
to Robin Stephenson.

*/

#include "includes.h"

#define IS_FLAG(flag)         (digram[last_unit]][unit] & (flag))
#define MAX_UNACCEPTABLE      20
#define MAX_RETRIES           (4 * pwlen + RULE_SIZE)


/*
 * This is the standard random unit generating routine for
 * get_syllable().  It does not reference the digrams, but assumes
 * that it contains 34 units in a particular order.  This routine
 * attempts to return unit indexes with a distribution approaching
 * that of the distribution of the 34 units in English.  In order to
 * do this, a random number (supposedly uniformly distributed) is used
 * to do a table lookup into an array containing unit indices.  There
 * are 211 entries in the array for the random_unit entry point.  The
 * probability of a particular unit being generated is equal to the
 * fraction of those 211 entries that contain that unit index.  For
 * example, the letter `a' is unit number 1.  Since unit index 1
 * appears 10 times in the array, the probability of selecting an `a'
 * is 10/211.
 *
 * Changes may be made to the digram table without affect to this
 * procedure providing the letter-to-number correspondence of the
 * units does not change.  Likewise, the distribution of the 34 units
 * may be altered (and the array size may be changed) in this
 * procedure without affecting the digram table or any other programs
 * using the random_word subroutine.
 *
 * FIXME:  Do we really want this?  Passwords would be much safer if
 * the characters are more equally distributed, but they may be harder
 * to remember.
 */
static const UInt8 numbers[] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6,
  7, 7, 7, 7, 7, 7,
  8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  9, 9, 9, 9, 9, 9, 9, 9,
  10, 10, 10, 10, 10, 10, 10, 10,
  11, 11, 11, 11, 11, 11,
  12, 12, 12, 12, 12, 12,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  15, 15, 15, 15, 15, 15,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  17, 17, 17, 17, 17, 17, 17, 17,
  18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
  19, 19, 19, 19, 19, 19,
  20, 20, 20, 20, 20, 20, 20, 20,
  21, 21, 21, 21, 21, 21, 21, 21,
  22,
  23, 23, 23, 23, 23, 23, 23, 23,
  24,
  25,
  26,
  27,
  28,
  29, 29,
  30,
  31,
  32,
  33
};


/*
 * This structure has a typical English frequency of vowels.  The
 * value of an entry is the vowel position (a=0, e=4, i=8, o=14, u=19,
 * y=23) in the rules array.  The number of times the value appears is
 * the frequency.  Thus, the letter "a" is assumed to appear 2/12 =
 * 1/6 of the time.  This array may be altered if better data is
 * obtained.  The routines that use vowel_numbers will adjust to the
 * size difference automatically.
 */
static const UInt8 vowel_numbers[] = {
  0, 0, 4, 4, 4, 8, 8, 14, 14, 19, 19, 23
};

/*
 * Select a unit (a letter or a consonant group).  If a vowel is
 * expected, use the vowel_numbers array rather than looping through
 * the numbers array until a vowel is found.
 */
static UInt16 random_unit (register UInt16 type)
{
    register UInt8 rand;
    
    /* 
     * Sometimes, we are asked to explicitly get a vowel (i.e., if a
     * digram pair expects one following it).  This is a shortcut to do
     * that and avoid looping with rejected consonants.
     */
    if (type & VOWEL)
    {
	while ((rand = Secrand_GetByte()) > 12*21) 
	{
	    /* regenerate random. */
	}
	return vowel_numbers[rand % 12];
    }
    else
    {
	while ((rand = Secrand_GetByte()) > 
	       sizeof (numbers) / sizeof (UInt16)) 
	{
	    /* regenerate random. */
	}
	/* 
	 * Get any letter according to the English distribution.
	 */
	return numbers[rand];
    }
}

/*
 * Generate next unit to password, making sure that it follows
 * these rules:
 *   1. Each syllable must contain exactly 1 or 2 consecutive
 *      vowels, where y is considered a vowel.
 *   2. Syllable end is determined as follows:
 *        a. Vowel is generated and previous unit is a
 *           consonant and syllable already has a vowel.  In
 *           this case, new syllable is started and already
 *           contains a vowel.
 *        b. A pair determined to be a "break" pair is encountered.
 *           In this case new syllable is started with second unit
 *           of this pair.
 *        c. End of password is encountered.
 *        d. "begin" pair is encountered legally.  New syllable is
 *           started with this pair.
 *        e. "end" pair is legally encountered.  New syllable has
 *           nothing yet.
 *   3. Try generating another unit if:
 *        a. third consecutive vowel and not y.
 *        b. "break" pair generated but no vowel yet in current
 *           or previous 2 units are "not_end".
 *        c. "begin" pair generated but no vowel in syllable
 *           preceding begin pair, or both previous 2 pairs are
 *          designated "not_end".
 *        d. "end" pair generated but no vowel in current syllable
 *           or in "end" pair.
 *        e. "not_begin" pair generated but new syllable must
 *           begin (because previous syllable ended as defined in
 *           2 above).
 *        f. vowel is generated and 2a is satisfied, but no syllable
 *           break is possible in previous 3 pairs.
 *        g. Second and third units of syllable must begin, and
 *           first unit is "alternate_vowel".
 */
void Pron_GetSyllable (Char *syllable, UInt16 pwlen, 
		       PronStateType *state, void *prondata)
{
    Int16  syll_length;
    UInt16 vowel_count, unit_ptr;
    UInt16 next_vowel;
    UInt16 tries;
    Int16  last_unit, unit;
    Int8   last_flags, flags;
    Int16  length_left;
    Int16  new_length_left;
    UInt16 saved_unit;

    struct unit (*rules);
    UInt8 (*digram)[RULE_SIZE];

    rules  = prondata;
    digram = prondata + RULE_SIZE * sizeof(struct unit);

    /* 
     * Try for a new syllable.  Initialize all pertinent syllable
     * variables.
     */

 retry_syllable:
    tries = 0;
    vowel_count = 0;
    length_left = pwlen;
    next_vowel = NO_SPECIAL_RULE;
    syll_length = state->saved_units;
    unit_ptr = state->unit_length + syll_length;
    last_flags = flags = 0;
    saved_unit = 0;
    syllable[0] = 0;
    
    if (unit_ptr == 0)
	last_unit = -1;
    else
	last_unit = state->units[unit_ptr - 1];

    /* 
     * If there are saved_unit's from the previous syllable,
     * we have to update flags.
     */
    if (syll_length > 0) {
	if ((rules[last_unit].flags & VOWEL) &&
	    !(rules[last_unit].flags & ALTERNATE_VOWEL))
	    vowel_count++;
			     
	length_left -= StrLen(rules[last_unit].unit_code);
	if (syll_length > 1) {
	    UInt8 llunit = state->units[unit_ptr-2];
	    if ((rules[llunit].flags & VOWEL))
		vowel_count++;
	    length_left -= StrLen(rules[llunit].unit_code);
	    last_flags = digram[llunit][last_unit];       
	}
    }


    /*
     * This loop finds all the units for the syllable.
     */
    while (length_left > 0)
    {
	/*
	 * This label is jumped to until a valid unit is found for the
	 * current position within the syllable.
	 */
    retry_unit:

	if (tries++ > MAX_RETRIES)
	    goto retry_syllable;
	
	/* 
	 * If we don't have to scoff the saved units, we