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     ! 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.