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