Return to hash.c CVS log

Up to [Research Unix] / researchv8dc / cmd / spell

Annotation of researchv8dc/cmd/spell/hash.c, revision 1.1.1.1

1.1       root        1: /*     @(#)hash.c      1.1     */
                      2: #include "hash.h"
                      3: 
                      4: #define LOCHWIDTH 3
                      5: #define HICHWIDTH 3
                      6: #define CHARWIDTH (LOCHWIDTH+HICHWIDTH)
                      7: #define LOCHMASK ((1<<LOCHWIDTH)-1)
                      8: 
                      9: /* The hash function is first a substitution cipher into 6-bit
                     10:  * characters.  Then the string of 6-bit bytes is interpreted
                     11:  * as a huge integer, and taken mod a big prime (hashsize).
                     12:  * Unhashable trash produces an otherwise impossible value; it
                     13:  * would be prudent not to have that value in the dictionary.
                     14: */
                     15: /* if HASHWIDTH + CHARWIDTH < bitsizeof(long)
                     16:  * one could make LOCHWIDTH=6 and HICHWIDTH=0
                     17:  * and simplify accordingly; the hanky-panky
                     18:  * is to avoid overflow in long multiplication
                     19:  */
                     20: #define NC 30
                     21: 
                     22: long hashsize = HASHSIZE;
                     23: long pow2[NC*2];
                     24: 
                     25: static char hashtab[] = {
                     26: -1,    -1,     -1,     -1,     -1,     -1,     0,      31,     /*  &' */
                     27: -1,    -1,     -1,     -1,     -1,     -1,     -1,     -1,
                     28: 2,     25,     20,     35,     54,     61,     40,     39,     /* 0-7 */
                     29: 42,    33,     -1,     -1,     -1,     -1,     -1,     -1,
                     30: -1,    60,     43,     30,     5,      16,     47,     18,     /* A-G */
                     31: 41,    36,     51,     6,      13,     56,     55,     58,
                     32: 49,    12,     59,     46,     21,     32,     63,     34,
                     33: 57,    52,     3,      -1,     -1,     -1,     -1,     -1,
                     34: -1,    22,     29,     8,      7,      10,     1,      28,     /* a-g */
                     35: 11,    62,     37,     48,     15,     50,     9,      4,
                     36: 19,    38,     45,     24,     23,     26,     17,     44,
                     37: 27,    14,     53,     -1,     -1,     -1,     -1,     -1
                     38: };
                     39: 
                     40: long hash(s)
                     41: char *s;
                     42: {
                     43:        register c;
                     44:        register long *lp;
                     45:        long h = 0;
                     46:        for(lp=pow2; c = *s++&0177; ) {
                     47:                if((c-=' ') >= 0 && (c=hashtab[c]) >= 0
                     48:                   && lp < pow2+(sizeof pow2/sizeof *pow2)) {
                     49:                        h += (c&LOCHMASK) * *lp++;
                     50:                        h += (c>>LOCHWIDTH) * *lp++;
                     51:                        h %= hashsize;
                     52:                } else
                     53:                        return (1L<<HASHWIDTH) - 1;     /*trash value*/
                     54:        }
                     55:        return(h);
                     56: }
                     57: 
                     58: hashinit()
                     59: {
                     60:        register i;
                     61:        if(1L<<(HASHWIDTH+LOCHWIDTH)<=0
                     62:           || 1L<<(HASHWIDTH+HICHWIDTH)<=0)
                     63:                abort();        /* overflow is imminent */
                     64:        pow2[0] = 1L<<(HASHWIDTH-CHARWIDTH-2);
                     65:        for(i=0; i<2*NC-3; i+=2) {
                     66:                pow2[i+1] = (pow2[i]<<LOCHWIDTH) % hashsize;
                     67:                pow2[i+2] = (pow2[i+1]<<HICHWIDTH) % hashsize;
                     68:        }
                     69: }

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