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