xref: /illumos-gate/usr/src/cmd/spell/hash.c (revision 0d8b5334)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
28 /*	  All Rights Reserved  	*/
29 
30 #pragma ident	"%Z%%M%	%I%	%E% SMI"
31 
32 
33 #include <stdlib.h>
34 #include "hash.h"
35 
36 #define	LOCHWIDTH 3
37 #define	HICHWIDTH 3
38 #define	CHARWIDTH (LOCHWIDTH+HICHWIDTH)
39 #define	LOCHMASK ((1<<LOCHWIDTH)-1)
40 
41 /*
42  * if HASHWIDTH + CHARWIDTH < bitsizeof(long)
43  * one could make LOCHWIDTH=6 and HICHWIDTH=0
44  * and simplify accordingly; the hanky-panky
45  * is to avoid overflow in long multiplication
46  */
47 #define	NC 30
48 
49 static long hashsize = HASHSIZE;
50 static long pow2[NC*2];
51 
52 static signed char hashtab[] = {
53 -1,	-1,	-1,	-1,	-1,	-1,	0,	31,	/*  &' */
54 -1,	-1,	-1,	-1,	68,	-1,	65,	-1,
55 2,	25,	20,	35,	54,	61,	40,	39,	/* 0-7 */
56 42,	33,	64,	67,	-1,	-1,	-1,	66,
57 -1,	60,	43,	30,	5,	16,	47,	18,	/* A-G */
58 41,	36,	51,	6,	13,	56,	55,	58,
59 49,	12,	59,	46,	21,	32,	63,	34,
60 57,	52,	3,	-1,	-1,	-1,	-1,	-1,
61 -1,	22,	29,	8,	7,	10,	1,	28,	/* a-g */
62 11,	62,	37,	48,	15,	50,	9,	4,
63 19,	38,	45,	24,	23,	26,	17,	44,
64 27,	14,	53,	-1,	-1,	-1,	-1,	-1
65 };
66 
67 
68 unsigned long
hash(char * s)69 hash(char *s)
70 {
71 	int c;
72 	long *lp;
73 	unsigned long h = 0;
74 	for (lp = pow2; (c = *s++) != 0; ) {
75 		c = hashtab[c-' '];
76 		h += (c&LOCHMASK) * *lp++;
77 		h += (c>>LOCHWIDTH) * *lp++;
78 		h %= hashsize;
79 	}
80 	return (h);
81 }
82 
83 void
hashinit(void)84 hashinit(void)
85 {
86 #if ((1L << (HASHWIDTH+LOCHWIDTH) == 0) || (1L << (HASHWIDTH+HICHWIDTH) == 0))
87 	abort();	/* overflow is imminent */
88 #else
89 	int i;
90 
91 	pow2[0] = 1L<<(HASHWIDTH-CHARWIDTH-2);
92 	for (i = 0; i < 2*NC-3; i += 2) {
93 		pow2[i+1] = (pow2[i]<<LOCHWIDTH) % hashsize;
94 		pow2[i+2] = (pow2[i+1]<<HICHWIDTH) % hashsize;
95 	}
96 #endif
97 }
98