Return to spell.h CVS log

Up to [CSRG BSD Unix] / 40BSD / cmd / spell

Annotation of 40BSD/cmd/spell/spell.h, revision 1.1.1.1

1.1       root        1: #include <stdio.h>
                      2: #include <ctype.h>
                      3: 
                      4: #ifndef unix
                      5: #define SHIFT  5
                      6: #define TABSIZE (int)(400000/(1<<SHIFT))
                      7: int    *tab;   /*honeywell loader deficiency*/
                      8: #else
                      9: #define Tolower(c)     (isupper(c)?tolower(c):c) /* ugh!!! */
                     10: #define SHIFT  4
                     11: #define TABSIZE 25000  /*(int)(400000/(1<<shift))--pdp11 compiler deficiency*/
                     12: short  tab[TABSIZE];
                     13: #endif
                     14: long   p[] = {
                     15:        399871,
                     16:        399887,
                     17:        399899,
                     18:        399911,
                     19:        399913,
                     20:        399937,
                     21:        399941,
                     22:        399953,
                     23:        399979,
                     24:        399983,
                     25:        399989,
                     26: };
                     27: #define        NP      (sizeof(p)/sizeof(p[0]))
                     28: #define        NW      30
                     29: 
                     30: /*
                     31: * Hash table for spelling checker has n bits.
                     32: * Each word w is hashed by k different (modular) hash functions, hi.
                     33: * The bits hi(w), i=1..k, are set for words in the dictionary.
                     34: * Assuming independence, the probability that no word of a d-word
                     35: * dictionary sets a particular bit is given by the Poisson formula
                     36: * P = exp(-y)*y**0/0!, where y=d*k/n.
                     37: * The probability that a random string is recognized as a word is then
                     38: * (1-P)**k.  For given n and d this is minimum when y=log(2), P=1/2,
                     39: * whence one finds, for example, that a 25000-word dictionary in a
                     40: * 400000-bit table works best with k=11.
                     41: */
                     42: 
                     43: long   pow2[NP][NW];
                     44: 
                     45: prime(argc, argv) register char **argv;
                     46: {
                     47:        int i, j;
                     48:        long h;
                     49:        register long *lp;
                     50: 
                     51: #ifndef unix
                     52:        if ((tab = (int *)calloc(sizeof(*tab), TABSIZE)) == NULL)
                     53:                return(0);
                     54: #endif
                     55:        if (argc > 1) {
                     56:                FILE *f;
                     57:                if ((f = fopen(argv[1], "ri")) == NULL)
                     58:                        return(0);
                     59:                if (fread((char *)tab, sizeof(*tab), TABSIZE, f) != TABSIZE)
                     60:                        return(0);
                     61:                fclose(f);
                     62:        }
                     63:        for (i=0; i<NP; i++) {
                     64:                h = *(lp = pow2[i]) = 1<<14;
                     65:                for (j=1; j<NW; j++)
                     66:                        h = *++lp = (h<<7) % p[i];
                     67:        }
                     68:        return(1);
                     69: }
                     70: 
                     71: #define get(h) (tab[h>>SHIFT]&(1<<((int)h&((1<<SHIFT)-1))))
                     72: #define set(h) tab[h>>SHIFT] |= 1<<((int)h&((1<<SHIFT)-1))

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.