/*
   Phonewrd - given a phone number, find all words or phrases in a dictionary
	which fit it.  See the man page for details, type "phonewrd -?" for
	options.

   version 2.2 - 9/1/93

   (c) copyright 1993, Eric Haines, all rights reserved (erich@eye.com)
       (distribute and use freely, just don't use inside commercial code)


   History:

   2.0 - release for comp.sources.misc
   2.1 - added sftolower for non-ANSI machines, added ctype.h include,
	 fixed error msg for GNU dictionary, added function prototypes,
	 made some casts explicit.
   2.2 - fixed infinite loop with "No matches ... trying again", less clunky
	 & dangerous sftolower(), added copyright explanation.
 */

#include <stdlib.h>	/* if you don't have stdlib, use malloc.h instead,
			 * though you might be able to get by without either */
#include <stdio.h>
#include <ctype.h>	/* for tolower() */


/* safe tolower() macro - on some non-ANSI compliant machines, tolower()
 * only works correctly for uppercase values, i.e. it simply subtracts an
 * offset from the value passed in.  So, we need to test if the character is
 * uppercase before using tolower().  If your compiler has a tolower()
 * function that works correctly for all input (most compilers do) and you
 * want the code to run faster, just redefine sftolower as calling tolower:
 * #define	sftolower(c)	tolower((int)(c))
 */
#define sftolower(c)	(isupper((int)(c)) ? tolower((int)(c)) : (c))


/* define USE_STRINGS_H if you use <strings.h> instead of <string.h> */
#ifdef USE_STRINGS_H
    /* BSD string routines. */
#   include <strings.h>
/* Really, should not define USE_STRINGS_H if __STDC__, but be safe. */
#ifndef __STDC__
#   define strchr index
#   define strrchr rindex
#endif /* not __STDC__ */
#else
    /* SYS V string routines. */
#   include <string.h>
#endif /* USE_STRINGS_H */

#include "patchlevel.h"

/*============= default related =========================================== */

/* path to dictionary */
#define	DICT_PATH	"/usr/dict/words"

/* how many numerals are allowed in our phrase? */
#define	NUMERALS_ALLOWED	0

/* minimum length of words: note that 1 always gets bumped to 2, because of
 * OneLetter below.
 */
#define	MIN_LENGTH	1

/* one letter words that are acceptable */
#define	ONE_LETTER	"aio"
/* If you like things like "CDB" (see the bee) or "IM4U, use or modify the
 * array below.  Yes, "j" and "k" are potential names, "m" is only in "I am",
 * "q" is queue, etc - you decide...  This option tends to generate lots of
 * useless goop, but it's good if you're desperate.
 */
/* #define ONE_LETTER	"abcdgimoptuxy248" */

#define	NO_NUMBER	-2

/* to make Q and Z not be anything, set them to NO_NUMBER, else set them
 * to the digit you want (e.g. 0 or 1)
 */
#define	Q	NO_NUMBER
#define	Z	NO_NUMBER

/* translation table for letters to numbers */
int	Letter2Numeral[] =
	/* a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z */
	 { 2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,Q,7,7,8,8,8,9,9,9,Z } ;

/* true if a character is a vowel */
#define	Vowel(c)	strchr( "aeiou", (int)(c) )

/*============= storage space related ===================================== */

#define MAX_DIGITS	14
#define	MAX_INDICES	(((MAX_DIGITS+1)*MAX_DIGITS)/2)

/* increment for word list memory space */
#define	WORD_LIST_SIZE	50

/*============= internal use constants ==================================== */

#define	FIXED_LETTER	-1

#define	BUFSIZE		256
#ifndef	TRUE
#define	TRUE	1
#define	FALSE	0
#endif

/*============= structures ================================================ */

/* array of words, indexed by digit location and length of word.  This list is
 * built up in the first part of the program, as each dictionary word is
 * categorized and put in its list.  Then this structure is traversed to make
 * up the combinations.
 */
typedef	struct {
	char	**p_word ;	/* list of pointers to words */
	int	count ;		/* current count */
	int	size ;		/* allocated size */
} wordlist, *p_wordlist ;

/*============= data and macros =========================================== */

#define	IndexWL( digit_loc, length )	( WLoffset[digit_loc] + length - 1 )

wordlist WL[MAX_INDICES] ;
int	WLoffset[MAX_DIGITS] ;
int	PhoneNum[MAX_DIGITS+1] ;	/* phone number translation */
char	PhoneStr[MAX_DIGITS+1] ;	/* phone number letter, if specified */
int	NumeralMapped[10] ;		/* if TRUE, then index # is mapped */
char	OneLetter[BUFSIZE] ;
char	*DictPath[100] ;
int	DictTot ;
char	*ProgName ;

int	NumDigits ;
int	NumIndices ;
int	NumNumerals ;
int	MinLength ;
int	RollOwn ;
int	Concat ;
int	Verbose ;
int	MatchTot ;
int	Wildcard ;
int	TotBrk ;

int	HoldSize ;
int	HoldCount ;
char	**HoldWord ;

char	OutputGrid[MAX_DIGITS][27] ;

/*============= procedure declarations ==================================== */

#if __STDC__ || defined(__cplusplus)
#define P_(s) s
#else
#define P_(s) ()
#endif

/* phonewrd.c */
int main P_((int argc, char *argv[]));
void usage P_((void));
int phone_check P_((char *numeral_string));
void roll_own P_((void));
void concat_it P_((void));
void concat_letter_out P_((int digit, char *full_string));
void concat_letter_breaks_out P_((int digit, char *full_string));
void init_wl P_((void));
int fit_word P_((char *dict_word, int min_length));
int permute_word P_((char *dict_word, char *new_word));
void hold_word P_((char *word));
int store_word P_((char *word, int digit, int length));
void search_for_match P_((int digit, char *full_string, char *suffix_loc, int numeral_count));
void free_wl P_((void));
int scan_options P_((int argc, char *argv[], int *nargc, char *nargv[]));
char *str_duplicate P_((char *s));

#undef P_

/*============= procedures ================================================ */

main(argc,argv)
int argc;  char *argv[];
{
int	nargc ;
char	*nargv[BUFSIZE], *targv ;
int	i, hdr_out, cont_flag ;

    ProgName = argv[0] ;

    HoldSize = HoldCount = 0 ;

    NumNumerals = NUMERALS_ALLOWED ;
    MinLength = MIN_LENGTH ;
    RollOwn = FALSE ;
    Concat = 0 ;
    Verbose = FALSE ;

    strcpy( OneLetter, ONE_LETTER ) ;
    *DictPath = str_duplicate( DICT_PATH ) ;
    if ( !(*DictPath) ) {
	fprintf( stderr, "Ugh, we're out of memory!\n" ) ;
	exit(1) ;
    }
    DictTot = 1 ;

    /* translate phone number */
    if ( argc < 2 ) {
	fprintf( stderr, "Not enough arguments.\n" ) ;
	usage() ;
	return( 1 ) ;
    }

    cont_flag = scan_options( argc, argv, &nargc, nargv ) ;
    if ( Verbose ) {
	/* always print out the version, etc, even if errors occur */
	fprintf( stdout, "%s %s, patch level %d\n",
		argv[0], VERSION, PATCHLEVEL ) ;
    }

    if ( !cont_flag ) {
	/* bad scan option, so quit */
	return( 1 ) ;
    }

    if ( nargc < 1 ) {
	fprintf( stderr, "No phone number found.\n" ) ;
	usage() ;
	return( 1 ) ;
    }

    /* loop through phone number(s), output headers if more than one */
    hdr_out = ( nargc > 1 ) ;
    for ( i = 0 ; i < nargc ; i++ ) {
	if ( i ) {
	    /* output carriage returns before 2nd, 3rd, etc */
	    fprintf( stdout, "\n" ) ;
	}
	targv = nargv[i] ;
	if ( hdr_out ) {
	    fprintf( stdout, "# %s\n", targv ) ;
	}
	if ( phone_check( targv ) ) {
	    /* something very bad happened, so quit */
	    return( 1 ) ;
	}
    }

    return( 0 ) ;
}

void usage()
{
    fprintf(stderr, "usage: %s [options] phone#[*...]\n", ProgName);
    fprintf(stderr, " [*...] - extra *'s at the end mean optional wildcard letters\n");
    fprintf(stderr, "  -l # - minimum length of words (cur. == %d)\n", MinLength);
    fprintf(stderr, "  -n # - number of numerals allowed in phrase (cur. == %d)\n", NumNumerals);
    if ( Letter2Numeral['q'-'a'] == NO_NUMBER ) {
	fprintf(stderr, "  -q # - mapping of q (none currently)\n" ) ;
    } else {
	fprintf(stderr, "  -q # - mapping of q (cur. == %d)\n",
    		Letter2Numeral['q'-'a'] ) ;
    }
    if ( Letter2Numeral['z'-'a'] == NO_NUMBER ) {
	fprintf(stderr, "  -z # - mapping of z (none currently)\n" ) ;
    } else {
	fprintf(stderr, "  -z # - mapping of z (cur. == %d)\n",
    		Letter2Numeral['z'-'a'] ) ;
    }
    fprintf(stderr, "  -d string - dictionary path (cur. == %s)\n", *DictPath);
    fprintf(stderr, "  -s string - allowed single letter words (cur. == \"%s\")\n", OneLetter);
    fprintf(stderr, "  -m char[26] - mapping of entire alphabet\n");
    fprintf(stderr, "  -r - output the corresponding letters in an array (no dictionary)\n");
    fprintf(stderr, "  -c - output all combinations (no dictionary)\n");
    fprintf(stderr, "  -C - output all combinations and spacings (no dictionary)\n");
    fprintf(stderr, "  -v - verbose output (show words that do fit)\n");
}


int
phone_check( numeral_string )
char	*numeral_string ;
{
int	i, tot, word_count, length, min_length, found_digit, val, nn ;
char	tchr, *tstr, **dp ;
char	dict_word[BUFSIZE] ;
char	out_string[BUFSIZE] ;
p_wordlist	p_wl ;
FILE	*infile ;

    NumDigits = 0 ;
    TotBrk = -1 ;

    tstr = numeral_string ;
    tchr = *tstr++ ;
    found_digit = FALSE ;
    while ( tchr != '\0' && tchr != '*' && (NumDigits <= MAX_DIGITS ) ) {
	if ( ( tchr >= '0' ) && ( tchr <= '9' ) ) {
	    /* convert to digit */
	    PhoneNum[NumDigits] = (int)(tchr - '0') ;
	    PhoneStr[NumDigits++] = tchr ;
	    found_digit = TRUE ;
	} else if ( ( (tchr >= 'A') && (tchr <= 'Z') ) ||
		    ( (tchr >= 'a') && (tchr <= 'z') ) ) {
	    PhoneNum[NumDigits] = FIXED_LETTER ;
	    PhoneStr[NumDigits++] = sftolower( tchr ) ;
	}
	tchr = *tstr++ ;
    }
    PhoneStr[NumDigits]='\0' ;

    if ( NumDigits <= 0 ) {
	fprintf( stderr, "Sorry, no digits input in `%s'\n", numeral_string ) ;
	fprintf( stderr, "Recompile with a higher MAX_DIGITS setting.\n" ) ;
	usage() ;
	return(0) ;
    }

    /* check if we're in roll own mode */
    if ( RollOwn ) {
	roll_own() ;
	return(0) ;
    }

    /* check if we're in concat output mode */
    if ( Concat ) {
	concat_it() ;
	return(0) ;
    }

    /* check if any numbers were input */
    if ( !found_digit ) {
	/* entirely alphabetic input, so translate to number */
	for ( i = 0 ; i < NumDigits ; i++ ) {
	    val = Letter2Numeral[PhoneStr[i]-'a'] ;
	    if ( val != NO_NUMBER ) {
		fprintf( stdout, "%d", val ) ;
	    } else {
		fprintf( stdout, "*" ) ;
	    }
	}
	fprintf( stdout, "\n" ) ;
	return(0) ;
    }

    if ( tchr == '*' ) {
	/* the phone number ends in a wild card - phrases can be longer */
	Wildcard = 1 ;
	while ( *tstr++ == '*' ) {
	    Wildcard++ ;
	}
    } else {
	Wildcard = 0 ;
    }

    if ( NumDigits > MAX_DIGITS ) {
	fprintf(stderr, "Sorry, too many digits input in `%s'; ",
		numeral_string);
	fprintf(stderr, "only %d allowed.\n", MAX_DIGITS);
	usage() ;
	return(0) ;
    }

    /* set up offset array for indexing WL */
    tot = 0 ;
    for ( i = 0 ; i < NumDigits ; i++ ) {
	WLoffset[i] = tot ;
	tot += (NumDigits-i) ;
    }
    NumIndices = ((NumDigits+1)*NumDigits)/2 ;

    /* build WL */
    word_count = 0 ;
    init_wl() ;
    dp = DictPath ;
    i = DictTot ;
    while ( i-- ) {
	infile = fopen( *dp, "r") ;
	min_length = MinLength > 1 ? MinLength : 2 ;
	if ( infile != NULL ) {
	    while ( fgets( dict_word, BUFSIZE, infile ) ) {
		word_count += fit_word( dict_word, min_length ) ;
	    }
	} else {
	    fprintf( stderr, "Sorry, couldn't find dictionary at `%s'.\n",
		    *dp ) ;
	    return(1) ;
	}
	fclose( infile ) ;
	dp++ ;
    }

    if ( Verbose ) {
	for ( i = 0 ; i < NumDigits ; i++ ) {
	    for ( length = 1 ; length <= NumDigits-i ; length++ ) {
		p_wl = &WL[IndexWL( i, length )] ;
		if ( p_wl->count ) {
		    fprintf( stdout, "\nDigit %d, length %d:\n", i+1, length ) ;
		    for ( tot = 0 ; tot < p_wl->count ; tot++ ) {
			fprintf( stdout, " %s\n", p_wl->p_word[tot] ) ;
		    }
		}
	    }
	}
    }

    MatchTot = 0 ;	/* number of words matched */

    /* save NumNumerals around in case it gets incremented */
    nn = NumNumerals ;

    /* search through WL for paths */
    if ( word_count ) {
	/* good, there's something to work with: search away! */
	*out_string = '\0' ;
	while ( !MatchTot && ( NumNumerals <= NumDigits ) ) {
	    search_for_match( 0, out_string, out_string, 0 ) ;
	    if ( !MatchTot ) {
		fprintf( stderr, "No matches with -n %d", NumNumerals ) ;
		if ( NumNumerals++ < NumDigits ) {
		    fprintf( stderr,
			    ", trying again with -n %d\n", NumNumerals ) ;
		} else {
		    fprintf( stderr, "\n" ) ;
		}
	    }
	}
	if ( !MatchTot ) {
	    fprintf( stderr,
	"Bad luck: dictionary words fit, but there's too much numeral goop.\n");
	    fprintf( stderr,
"Maybe try again with the option `-s abcdgimoptuxy248' or try wildcarding.\n"
		    ) ;
	}
    } else {
	fprintf( stderr,
		"Worst luck: no dictionary words fit anywhere in %s.\n",
		PhoneStr ) ;
	fprintf( stderr,
"Maybe try again with the option `-s abcdgimoptuxy248' or try wildcarding.\n"
		    ) ;
    }

    /* restore NumNumerals (yeah, this is sloppy - sue me) */
    NumNumerals = nn ;

    free_wl() ;

    return(0) ;
}

void
roll_own()
{
int	digit_letter[MAX_DIGITS], found_one, search, i, j, k ;

    for ( i = 0 ; i < NumDigits ; i++ ) {
	if ( PhoneNum[i] == FIXED_LETTER ) {
	    digit_letter[i] = -2 ;
	} else {
	    digit_letter[i] = -1 ;
	}
    }
    found_one = TRUE ;
    for ( i = 0 ; i < 26 && found_one ; i++ ) {
	found_one = FALSE ;
	for ( j = 0 ; j < NumDigits ; j++ ) {
	    if ( digit_letter[j] >= 26 ) {
		/* done with this one */
		fprintf( stdout, "   " ) ;
	    } else {
		if ( digit_letter[j] == -2 ) {
		    found_one = TRUE ;
		    digit_letter[j] = 26 ;
		    fprintf( stdout, "  %c", PhoneStr[j] ) ;
		} else {
		    for ( k = digit_letter[j] + 1, search = TRUE
			; k < 26 && search
			; k++ ) {

			if ( Letter2Numeral[k] == PhoneNum[j] ) {
			    search = FALSE ;
			    found_one = TRUE ;
			    fprintf( stdout, "  %c", (char)(k+'a') ) ;
			    digit_letter[j] = k ;
			}
		    }
		    if ( search ) {
			/* no further match found */
			if ( digit_letter[j] < 0 ) {
			    /* numeral is not mapped, so output it directly */
			    fprintf( stdout, "  %c", PhoneStr[j] ) ;
			}
			digit_letter[j] = 26 ;
		    }
		}
	    }
	}
	fprintf( stdout, "\n" ) ;
    }
}

void
concat_it()
{
int	i, j, tot ;
char	full_string[MAX_DIGITS+1] ;

    for ( i = 0 ; i < NumDigits ; i++ ) {
	if ( PhoneNum[i] == FIXED_LETTER ) {
	    OutputGrid[i][0] = PhoneStr[i] ;
	    OutputGrid[i][1] = '\0' ;
	} else {
	    tot = 0 ;
	    for ( j = 0 ; j < 26 ; j++ ) {
		if ( Letter2Numeral[j] == PhoneNum[i] ) {
		    OutputGrid[i][tot++] = (char)(j+'a') ;
		}
	    }
	    if ( !tot ) {
		/* no match found */
		OutputGrid[i][tot++] = PhoneStr[i] ;
	    }
	    OutputGrid[i][tot] = '\0' ;
	}
    }

    if ( Concat == 1 ) {
	concat_letter_out( 0, full_string ) ;
    } else {
	concat_letter_breaks_out( 0, full_string ) ;
    }
}

void
concat_letter_out( digit, full_string )
int	digit ;
char	*full_string ;
{
int	i, length ;
char	*cstr ;

    if ( digit >= NumDigits ) {
	full_string[digit] = '\0' ;
	fprintf( stdout, "%s\n", full_string ) ;
    } else {
	length = strlen( cstr = OutputGrid[digit] ) ;
	for ( i = 0 ; i < length ; i++ ) {
	    full_string[digit] = *cstr++ ;
	    concat_letter_out( digit+1, full_string ) ;
	}
    }
}

void
concat_letter_breaks_out( digit, full_string )
int	digit ;
char	*full_string ;
{
char	brk_string[MAX_DIGITS*2] ;
int	i, j, bny, index, length ;
char	*cstr ;

    if ( digit >= NumDigits ) {
	if ( TotBrk == -1 ) {
	    TotBrk = 1 ;
	    for ( i = 1 ; i < NumDigits ; i++ ) {
		TotBrk *= 2 ;
	    }
	}
	for ( i = 0 ; i < TotBrk ; i++ ) {
	    bny = i ;
	    index = 0 ;
	    for ( j = 0 ; j < NumDigits ; j++ ) {
		brk_string[index++] = full_string[j] ;
		if ( bny & 0x1 ) {
		    brk_string[index++] = ' ' ;
		}
		bny = bny >> 1 ;
	    }
	    brk_string[index] = '\0' ;
	    fprintf( stdout, "%s\n", brk_string ) ;
	}
    } else {
	length = strlen( cstr = OutputGrid[digit] ) ;
	for ( i = 0 ; i < length ; i++ ) {
	    full_string[digit] = *cstr++ ;
	    concat_letter_breaks_out( digit+1, full_string ) ;
	}
    }
}

/* create structures needed for the word list, etc */
void
init_wl()
{
p_wordlist p_wl ;
int	i, j, length, search ;
char	tstr[2] ;

    for ( i = 0, p_wl = WL ; i < NumIndices ; i++, p_wl++ ) {
	p_wl->p_word = NULL ;
	p_wl->count = 0 ;
	p_wl->size = 0 ;
    }

    /* figure out which numerals don't have any letter translations */
    for ( i = 0 ; i < 10 ; i++ ) {
	for ( j = 0, search = TRUE ; j < 26 && search ; j++ ) {
	    if ( i == Letter2Numeral[j] ) {
		search = FALSE ;
	    }
	}
	/* set to TRUE if numeral is mapped by something */
	NumeralMapped[i] = !search ;
    }

    tstr[1] = '\0' ;
    /* add one number values as possible */
    /* we rely on the fact that the first word in the single letter word
     * lists is actually a numeral, so change the following at your own
     * peril.
     */
    for ( i = 0 ; i < 10 ; i++ ) {
	tstr[0] = (char)i + '0' ;
	(void)fit_word( tstr, 1 ) ;
    }

    /* add one letter words as possible */
    length = strlen( OneLetter ) ;
    for ( i = 0 ; i < length ; i++ ) {
	tstr[0] = OneLetter[i] ;
	(void)fit_word( tstr, 1 ) ;
    }
}

/* see if the word fits in the database anywhere */
int
fit_word( dict_word, min_length )
char	*dict_word ;
int	min_length ;
{
int	length, compare_length, true_length, index_length, nl ;
int	i, j, num_match ;
int	word_val[MAX_DIGITS], hit[MAX_DIGITS], *wv, check_length, match, tot ;
char	lc_dict_word[MAX_DIGITS], *wc, *lc, tchr, *cc ;
char	clean_dict_word[BUFSIZE], new_word[BUFSIZE] ;

    /* set new_word to empty string to initialize permute_word */
    tot = 0 ;
    *new_word = '\0' ;
    while( permute_word( dict_word, new_word ) ) {
	/* convert word to numbers */
	length = strlen( new_word ) ;
	compare_length = true_length = 0 ;
	for ( i = 0, wv = word_val, wc = new_word, lc = lc_dict_word,
	      cc = clean_dict_word
	    ; ( i < length ) && ( compare_length < NumDigits )
	    ; i++, wc++ ) {

	    /* remove apostrophes, hyphens, etc for matching */
	    tchr = sftolower(*wc) ;
	    if ( ( tchr >= 'a' ) && ( tchr <= 'z' ) ) {
		*wv++ = Letter2Numeral[(*lc++ = tchr) -'a'] ;
		compare_length++ ;
	    } else if ( ( tchr >= '0' ) && ( tchr <= '9' ) ) {
		*wv++ = (*lc++ = tchr) -'0' ;
		compare_length++ ;
	    }
	    *cc++ = *wc ;
	}
	true_length = compare_length ;

	while ( *wc ) {
	    tchr = *wc++ ;
	    tchr = sftolower( tchr ) ;
	    /* get true length of word in valid characters */
	    if ( ( tchr >= 'a' ) && ( tchr <= 'z' ) ) {
		true_length++ ;
	    } else if ( ( tchr >= '0' ) && ( tchr <= '9' ) ) {
		true_length++ ;
	    }
	    /* copy the rest of the word */
	    *cc++ = tchr ;
	}
	/* end the cleaned word */
	*cc = '\0' ;

	/* is the word too long? */
	if ( true_length > NumDigits + Wildcard ) {
	    /* the word was too long: for ispell words we know that the
	     * first word is going to be as short as it gets, so we bail
	     * out of successive word generation here now.
	     */
	    goto LastWord ;
	}

	/* is the word too short? */
	if ( true_length < min_length ) {
	    /* the word was too short */
	    goto NextWord ;
	}

	/* now look for matches */
	if ( Wildcard ) {
	    check_length = NumDigits - true_length + Wildcard ;
	    if ( check_length >= NumDigits ) {
		/* cannot index into array at higher than NumDigits-1,
		 * so reduce length.
		 */
		check_length = NumDigits - 1 ;
	    }
	} else {
	    check_length = NumDigits - true_length ;
	}

	for ( i = 0, num_match = 0 ; i <= check_length ; i++ ) {
	    index_length = compare_length+i ;
	    if ( Wildcard ) {
		if ( index_length > NumDigits ) {
		    /* cut comparisons down to numerals available */
		    index_length = NumDigits ;
		}
	    }
	    for ( j = i, wv = word_val, match = TRUE
		; match && (j < index_length)
		; j++, wv++ ) {

		/* numerical match? */
		if ( PhoneNum[j] != *wv ) {
		    /* no; exact letter match? */
		    if ( ( PhoneNum[j] != FIXED_LETTER ) ||
			 ( PhoneStr[j] != lc_dict_word[j-i] ) ) {
			/* no match, stop testing */
			match = FALSE ;
		    }
		}
	    }
	    if ( match ) {
		/* word fits, store index */
		hit[num_match++] = i ;
	    }
	}
	/* were there any matches? */
	if ( num_match ) {
	    /* make one copy of the word */
	    wc = str_duplicate( clean_dict_word ) ;
	    if ( !wc ) {
		fprintf( stderr, "Ugh, we're out of memory!\n" ) ;
		exit(1) ;
	    }
	    hold_word( wc ) ;
	    for ( i = 0 ; i < num_match ; i++ ) {
		if ( Wildcard ) {
		    if ( hit[i] + true_length <= NumDigits ) {
			nl = true_length ;
		    } else {
			nl = NumDigits - hit[i] ;
		    }
		    if ( !store_word( wc, hit[i], nl ) ) {
			/* duplicate word, so free it and go to next word */
			free( wc ) ;
			goto NextWord ;
		    }
		} else {
		    if ( !store_word( wc, hit[i], true_length ) ) {
			/* duplicate word, so free it and go to next word */
			free( wc ) ;
			goto NextWord ;
		    }
		}
	    }
	    /* got here, so the word must have been stored */
	    tot++ ;
	}
	NextWord: ;
    }
    LastWord: ;
    return( tot ) ;
}

/* take permutations of word if "/" GNU ispell format detected, else just
 * strip out invalid characters and return new word
 */
int
permute_word( dict_word, new_word )
char	*dict_word ;
char	*new_word ;
{
int	search_word ;
char	*ppc, *psc, *dc, *wc, tchr, ttchr ;
static char perm_word[BUFSIZE], perm_pre_word[BUFSIZE] ;
static char perm_pre_cmd[BUFSIZE], perm_suf_cmd[BUFSIZE] ;
static int  perm_pre_count, perm_suf_count ;
static int  perm_cur_pre_count, perm_cur_suf_count, pre_length ;

    if ( *new_word ) {
	/* on successive call of this routine by calling procedure, so get
	 * a permutation (if available) and return it.
	 */

	/* subtract previous output permutation from count and see if done */
	search_word = 0 ;
	do {
	    if ( perm_cur_suf_count <= 0 ) {
		if ( perm_cur_pre_count <= 0 ) {
		    /* no more permutations */
		    return( 0 ) ;
		}
		perm_cur_suf_count = perm_suf_count ;
		switch( tchr = perm_pre_cmd[--perm_cur_pre_count] ) {
		    case 'A':	/* enter -> reenter */
			strcpy( perm_pre_word, "re" ) ;
			strcat( perm_pre_word, perm_word ) ;
			break ;
		    case 'I':	/* disposed -> indisposed */
			strcpy( perm_pre_word, "re" ) ;
			strcat( perm_pre_word, perm_word ) ;
			break ;
		    case 'U':	/* natural -> unnatural */
			strcpy( perm_pre_word, "un" ) ;
			strcat( perm_pre_word, perm_word ) ;
			break ;
		    default:
			fprintf( stderr,
			"warning:  unrecognized word flag `%c' for word `%s'\n",
			    tchr, perm_word ) ;
			return( 0 ) ;
		}
		pre_length = strlen( perm_pre_word ) ;
		/* for the first prefix addition just return rest of word
		 * without any suffix
		 */
		strcpy( new_word, perm_pre_word ) ;
	    } else {
		strcpy( new_word, perm_pre_word ) ;
		switch( tchr = perm_suf_cmd[--perm_cur_suf_count] ) {
		    case 'V':	/* create -> creative */
			/* use only when there is no prefix */
			if ( perm_cur_pre_count == perm_pre_count ) {
			    tchr = sftolower(new_word[pre_length-1]) ;
			    if ( tchr == 'e' ) {
				new_word[pre_length-1] = '\0' ;
			    }
			    strcat( new_word, "ive" ) ;
			} else {
			    /* invalid combination, so continue */
			    search_word = 1 ;
			}
			break ;
		    case 'N':	/* create -> creation */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'e' ) {
			    new_word[pre_length-1] = '\0' ;
			    strcat( new_word, "ion" ) ;
			} else if ( tchr == 'y' ) {
			    new_word[pre_length-1] = '\0' ;
			    strcat( new_word, "ication" ) ;
			} else {
			    strcat( new_word, "en" ) ;
			}
			break ;
		    case 'X':	/* create -> creations */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'e' ) {
			    new_word[pre_length-1] = '\0' ;
			    strcat( new_word, "ions" ) ;
			} else if ( tchr == 'y' ) {
			    new_word[pre_length-1] = '\0' ;
			    strcat( new_word, "ications" ) ;
			} else {
			    strcat( new_word, "ens" ) ;
			}
			break ;
		    case 'H':	/* twenty -> twentieth */
			/* use only when there is no prefix */
			if ( perm_cur_pre_count == perm_pre_count ) {
			    tchr = sftolower(new_word[pre_length-1]) ;
			    if ( tchr == 'y' ) {
				new_word[pre_length-1] = '\0' ;
				strcat( new_word, "ieth" ) ;
			    } else {
				strcat( new_word, "th" ) ;
			    }
			} else {
			    /* invalid combination, so continue */
			    search_word = 1 ;
			}
			break ;
		    case 'Y':	/* quick -> quickly */
			strcat( new_word, "ly" ) ;
			break ;
		    case 'G':	/* file -> filing */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'e' ) {
			    new_word[pre_length-1] = '\0' ;
			}
			strcat( new_word, "ing" ) ;
			break ;
		    case 'J':	/* file -> filings */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'e' ) {
			    new_word[pre_length-1] = '\0' ;
			}
			strcat( new_word, "ings" ) ;
			break ;
		    case 'D':	/* create -> created */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'e' ) {
			    strcat( new_word, "d" ) ;
			} else if ( tchr == 'y' ) {
			    ttchr = sftolower(new_word[pre_length-2]) ;
			    if ( Vowel(ttchr) ) {
				strcat( new_word, "ed" ) ;
			    } else {
				new_word[pre_length-1] = '\0' ;
				strcat( new_word, "ied" ) ;
			    }
			} else {
			    strcat( new_word, "ed" ) ;
			}
			break ;
		    case 'T':	/* late -> latest */
			/* use only when there is no prefix */
			if ( perm_cur_pre_count == perm_pre_count ) {
			    tchr = sftolower(new_word[pre_length-1]) ;
			    if ( tchr == 'e' ) {
				strcat( new_word, "st" ) ;
			    } else if ( tchr == 'y' ) {
				ttchr = sftolower(new_word[pre_length-2]) ;
				if ( Vowel(ttchr) ) {
				    strcat( new_word, "est" ) ;
				} else {
				    new_word[pre_length-1] = '\0' ;
				    strcat( new_word, "iest" ) ;
				}
			    } else {
				strcat( new_word, "est" ) ;
			    }
			} else {
			    /* invalid combination, so continue */
			    search_word = 1 ;
			}
			break ;
		    case 'R':	/* late -> later */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'e' ) {
			    strcat( new_word, "r" ) ;
			} else if ( tchr == 'y' ) {
			    ttchr = sftolower(new_word[pre_length-2]) ;
			    if ( Vowel(ttchr) ) {
				strcat( new_word, "er" ) ;
			    } else {
				new_word[pre_length-1] = '\0' ;
				strcat( new_word, "ier" ) ;
			    }
			} else {
			    strcat( new_word, "er" ) ;
			}
			break ;
		    case 'Z':	/* skate ->skaters */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'e' ) {
			    strcat( new_word, "rs" ) ;
			} else if ( tchr == 'y' ) {
			    ttchr = sftolower(new_word[pre_length-2]) ;
			    if ( Vowel(ttchr) ) {
				strcat( new_word, "ers" ) ;
			    } else {
				new_word[pre_length-1] = '\0' ;
				strcat( new_word, "iers" ) ;
			    }
			} else {
			    strcat( new_word, "ers" ) ;
			}
			break ;
		    case 'S':	/* imply -> implies */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'y' ) {
			    ttchr = sftolower(new_word[pre_length-2]) ;
			    if ( Vowel(ttchr) ) {
				strcat( new_word, "s" ) ;
			    } else {
				new_word[pre_length-1] = '\0' ;
				strcat( new_word, "ies" ) ;
			    }
			} else {
			    if ( strchr( "sxzh", (int)tchr ) ) {
				strcat( new_word, "es" ) ;
			    } else {
				strcat( new_word, "s" ) ;
			    }
			}
			break ;
		    case 'P':	/* cloudy -> cloudiness */
			tchr = sftolower(new_word[pre_length-1]) ;
			if ( tchr == 'y' ) {
			    ttchr = sftolower(new_word[pre_length-2]) ;
			    if ( Vowel(ttchr) ) {
				strcat( new_word, "ness" ) ;
			    } else {
				new_word[pre_length-1] = '\0' ;
				strcat( new_word, "iness" ) ;
			    }
			} else {
			    strcat( new_word, "ness" ) ;
			}
			break ;
		    case 'M':	/* dog -> dog's */
			strcat( new_word, "'s" ) ;
			break ;
		    default:
			fprintf( stderr,
			"warning:  unrecognized word flag `%c' for word `%s'\n",
			    tchr, perm_word ) ;
			return( 0 ) ;
		}
	    }
	} while ( search_word ) ;
    } else {
	/* first call, so check if we need to permute */
	if ( wc = strchr( dict_word, (int)'/' ) ) {
	    /* GNU ispell format detected, so save word and permutations */
	    strncpy( perm_word, dict_word, wc-dict_word ) ;
	    perm_word[wc-dict_word] = '\0' ;

	    wc++ ;
	    ppc = perm_pre_cmd ;
	    psc = perm_suf_cmd ;
	    perm_pre_count = 0 ;
	    perm_suf_count = 0 ;
	    while ( tchr = toupper( *wc++ ) ) {
		/* save only permutation characters */
		if ( ( tchr >= 'A' ) && ( tchr <= 'Z' ) ) {
		    if ( (tchr == 'A') || (tchr == 'I') || (tchr == 'U') ) {
			*ppc++ = tchr ;
			perm_pre_count++ ;
		    } else {
			*psc++ = tchr ;
			perm_suf_count++ ;
		    }
		}
	    }
	    *ppc = '\0' ;
	    *psc = '\0' ;
	    perm_cur_pre_count = perm_pre_count ;
	    perm_cur_suf_count = perm_suf_count ;
	    strcpy( perm_pre_word, perm_word ) ;
	    pre_length = strlen( perm_pre_word ) ;

	    /* and finally, copy the basic word for use */
	    strcpy( new_word, perm_word ) ;
	} else {
	    /* no permutation, so set permutation list to empty */
	    perm_cur_pre_count = 0 ;
	    perm_cur_suf_count = 0 ;

	    /* cull out line feeds, etc */
	    wc = dict_word ;
	    dc = new_word ;
	    while ( tchr = *wc++ ) {
		if ( tchr > 13 ) {
		    *dc++ = tchr ;
		}
	    }
	    *dc = '\0' ;
	}
    }
    return( 1 ) ;
}

/* yeah, I could combine this with store_word - call me lazy... */
void
hold_word( word )
char	*word ;
{
    if ( HoldSize <= HoldCount ) {
	if ( HoldSize ) {
	    HoldSize += WORD_LIST_SIZE * NumDigits ;
	    HoldWord = (char **)realloc( (void *)HoldWord,
		    HoldSize * sizeof(char *)) ;
	} else {
	    HoldSize = WORD_LIST_SIZE * NumDigits ;
	    HoldWord =
		    (char **)malloc( HoldSize * sizeof(char *)) ;
	}
	if ( HoldWord == NULL ) {
	    fprintf( stderr, "Ugh, we're out of memory!\n" ) ;
	    exit(1) ;
	}
    }
    HoldWord[HoldCount++] = word ;
}

/* store word in the given location, return 1 if word not a duplicate */
int
store_word( word, digit, length )
char	*word ;
int	digit ;
int	length ;
{
p_wordlist	p_wl ;
int	i ;

    p_wl = &WL[IndexWL( digit, length )] ;
    /* check if word is already on list */
    for ( i = 0 ; i < p_wl->count ; i++ ) {
	if ( !strcmp( word, p_wl->p_word[i] ) ) {
	    /* duplicate word - don't store it */
	    return( 0 ) ;
	}
    }

    /* check storage space */
    if ( p_wl->size <= p_wl->count ) {
	if ( p_wl->size ) {
	    p_wl->size += WORD_LIST_SIZE ;
	    p_wl->p_word = (char **)realloc( (void *)p_wl->p_word,
		    p_wl->size * sizeof(char *)) ;
	} else {
	    p_wl->size = WORD_LIST_SIZE ;
	    p_wl->p_word =
		    (char **)malloc( p_wl->size * sizeof(char *)) ;
	}
	if ( p_wl->p_word == NULL ) {
	    fprintf( stderr, "Ugh, we're out of memory!\n" ) ;
	    exit(1) ;
	}
    }
    /* store word in structure */
    p_wl->p_word[p_wl->count++] = word ;

    return( 1 ) ;
}

/* search through the stored words for matches */
void
search_for_match( digit, full_string, suffix_loc, numeral_count )
int	digit ;
char	*full_string ;
char	*suffix_loc ;
int	numeral_count ;
{
int	length, tot_len, tot_word, wn, add_num, val ;
p_wordlist	p_wl ;
char	**p_word ;

    tot_len = NumDigits - digit ;
    /* loop through all possible word lengths from this point */
    /* count down so that the longer strings are output first */
    for ( length = tot_len ; length > 0 ; length-- ) {
	p_wl = &WL[IndexWL( digit, length )] ;
	tot_word = p_wl->count ;
	/* now go through all words on the list */
	if ( ( length == 1 ) && tot_word ) {
	    val = **(p_wl->p_word) - '0' ;
	    /* is the first word a numeral, and is it mapped? */
	    if ( ( val >= 0 ) && ( val <= 9 ) && NumeralMapped[val] ) {
		/* don't include first word (a mapped numeral) if we've used
		 * up our quota.
		 */
		wn = (numeral_count >= NumNumerals ) ;
		add_num = 1 ;
	    } else {
		/* an unmapped numeral, so definitely do it */
		wn = 0 ;
		add_num = 0 ;
	    }
	} else {
	    /* not on the one letter word list, so do all words */
	    wn = 0 ;
	    add_num = 0 ;
	}
	for ( p_word = p_wl->p_word + wn
	    ; wn < tot_word
	    ; wn++, p_word++ ) {

	    strcpy( suffix_loc, *p_word ) ;
	    if ( length == tot_len ) {
		/* finished - output it! */
		fprintf( stdout, "%s\n", full_string ) ;
		MatchTot++ ;
	    } else {
		strcat( suffix_loc, " " ) ;
		/* Add one to numeral_count only if numeral is used */
		search_for_match( digit+length, full_string,
			suffix_loc + strlen( suffix_loc ),
			numeral_count + add_num ) ;
	    }
	}
    }
}

void
free_wl()
{
int i ;
p_wordlist p_wl ;

    for ( i = 0, p_wl = WL ; i < NumIndices ; i++, p_wl++ ) {
	if ( p_wl->size ) {
	    p_wl->size = 0 ;
	    p_wl->count = 0 ;
	    free( p_wl->p_word ) ;
	}
    }

    /* the only function of HoldWord is to be able to free the word memory */
    if ( HoldSize ) {
	for ( i = 0 ; i < HoldCount ; i++ ) {
	    free( HoldWord[i] ) ;
	}
	free( HoldWord ) ;
    }
    HoldCount = HoldSize = 0 ;
}

/* strip out all valid "-" arguments and their values */
int
scan_options( argc, argv, nargc, nargv )
int	argc ;
char	*argv[] ;
int	*nargc ;
char	*nargv[] ;
{
int	num_arg ;
int	i, first_dict ;
char	str[BUFSIZE] ;

    *nargc = num_arg = 0 ;
    first_dict = 1 ;	/* haven't received a dictionary path yet */

    while ( ++num_arg < argc ) {
	if ( *argv[num_arg] == '-' ) {
	    switch( argv[num_arg][1] ) {
		case 'l':	/* minimum length of words */
		    if ( ++num_arg < argc ) {
			sscanf( argv[num_arg], "%d", &i ) ;
			if ( i < 1 ) {
			    fprintf( stderr,
				    "Minimum word length too low!\n" ) ;
			    usage() ;
			    return( FALSE ) ;
			}
			MinLength = i ;
		    } else {
			fprintf( stderr, "No minimum length given for -l.\n" ) ;
			usage() ;
			return( FALSE ) ;
		    }
		    break ;
		case 'n':	/* number of numerals allowed */
		    if ( ++num_arg < argc ) {
			sscanf( argv[num_arg], "%d", &i ) ;
			if ( i < 0 ) {
			    fprintf( stderr, "Number of numerals too low!\n" ) ;
			    usage() ;
			    return( FALSE ) ;
			}
			NumNumerals = i ;
		    } else {
			fprintf( stderr,
				"No number of numerals given for -n.\n" ) ;
			usage() ;
			return( FALSE ) ;
		    }
		    break ;
		case 'q':	/* mapping of q */
		    if ( ++num_arg < argc ) {
			sscanf( argv[num_arg], "%d", &i ) ;
			if ( (i >= 0) && (i <= 9) ) {
			    Letter2Numeral['q'-'a'] = i ;
			}
		    } else {
			fprintf( stderr, "No mapped number given for -q.\n" ) ;
			usage() ;
			return( FALSE ) ;
		    }
		    break ;
		case 'z':	/* mapping of z */
		    if ( ++num_arg < argc ) {
			sscanf( argv[num_arg], "%d", &i ) ;
			if ( (i >= 0) && (i <= 9) ) {
			    Letter2Numeral['z'-'a'] = i ;
			}
		    } else {
			fprintf( stderr, "No mapped number given for -z.\n" ) ;
			usage() ;
			return( FALSE ) ;
		    }
		    break ;
		case 'd':	/* dictionary path */
		    if ( ++num_arg < argc ) {
			if ( first_dict ) {
			    first_dict = 0 ;
			    /* erase first dictionary, since we're
			     * overriding by giving a path.
			     */
			    DictTot = 0 ;
			    free( *DictPath ) ;
			}
			sscanf( argv[num_arg], "%s", str ) ;
			if ( (str[0] == '.') && ( str[1] == NULL ) ) {
			    /* for '.' use the default dictionary */
			    strcpy( str, DICT_PATH ) ;
			}
			DictPath[DictTot] = str_duplicate( str ) ;
			if ( !DictPath[DictTot++] ) {
			    fprintf( stderr, "Ugh, we're out of memory!\n" ) ;
			    exit(1) ;
			}
		    } else {
			fprintf( stderr,
				"No dictionary path given for -d.\n" ) ;
			usage() ;
			return( FALSE ) ;
		    }
		    break ;
		case 's':	/* allowed single letter words */
		    if ( ++num_arg < argc ) {
			sscanf( argv[num_arg], "%s", OneLetter ) ;
		    } else {
			fprintf( stderr,
				"No single letter words given for -s.\n" ) ;
			usage() ;
			return( FALSE ) ;
		    }
		    break ;
		case 'm':	/* mapping of entire alphabet */
		    if ( ++num_arg < argc ) {
			sscanf( argv[num_arg], "%s", str ) ;
			if ( strlen(str) != 26 ) {
			    fprintf( stderr, "Must input all 26 digits\n" ) ;
			    usage() ;
			    return( FALSE ) ;
			}
			for ( i = 0 ; i < 26 ; i++ ) {
			    if ( (str[i] >= '0') && (str[i] <= '9') ) {
				Letter2Numeral[i] = str[i] - '0' ;
			    } else {
				Letter2Numeral[i] = NO_NUMBER ;
			    }
			}
			if ( Verbose ) {
			    fprintf( stderr, "here's your banana: )\n" ) ;
			}
		    } else {
			fprintf( stderr, "No digit map given for -m.\n" ) ;
			usage() ;
			return( FALSE ) ;
		    }
		    break ;
		case 'r':	/* output concatenation */
		    RollOwn = TRUE ;
		    break ;
		case 'c':	/* output concatenation */
		    Concat = 1 ;
		    break ;
		case 'C':	/* output spacing & concatenation */
		    Concat = 2 ;
		    break ;
		case 'v':	/* verbose output */
		    Verbose = TRUE ;
		    break ;
		default:
		    fprintf( stderr, "No such option `-%c'.\n",
			    argv[num_arg][1] ) ;
		    usage() ;
		    return( FALSE ) ;
	    }
	} else {
	    /* not an argument, so pass it on */
	    nargv[(*nargc)++] = argv[num_arg] ;
	}
    }
    return( TRUE ) ;
}

/* strdup for the masses, since strdup is not standard */
char *str_duplicate( s )
char    *s ;
{
char *ps ;

    if ( ps = (char *)malloc( strlen( s ) + 1 ) ) {
	strcpy( ps, s ) ;
    }
    return( ps ) ;
}