xref: /illumos-gate/usr/src/cmd/spell/hash.c (revision 0d8b5334)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate  * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate  * (the "License").  You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate  * with the License.
87c478bd9Sstevel@tonic-gate  *
97c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate  * and limitations under the License.
137c478bd9Sstevel@tonic-gate  *
147c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate  *
207c478bd9Sstevel@tonic-gate  * CDDL HEADER END
217c478bd9Sstevel@tonic-gate  */
227c478bd9Sstevel@tonic-gate /*
23*0d8b5334Sceastha  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
247c478bd9Sstevel@tonic-gate  * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate  */
267c478bd9Sstevel@tonic-gate 
277c478bd9Sstevel@tonic-gate /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
287c478bd9Sstevel@tonic-gate /*	  All Rights Reserved  	*/
297c478bd9Sstevel@tonic-gate 
307c478bd9Sstevel@tonic-gate #pragma ident	"%Z%%M%	%I%	%E% SMI"
317c478bd9Sstevel@tonic-gate 
327c478bd9Sstevel@tonic-gate 
337c478bd9Sstevel@tonic-gate #include <stdlib.h>
347c478bd9Sstevel@tonic-gate #include "hash.h"
357c478bd9Sstevel@tonic-gate 
367c478bd9Sstevel@tonic-gate #define	LOCHWIDTH 3
377c478bd9Sstevel@tonic-gate #define	HICHWIDTH 3
387c478bd9Sstevel@tonic-gate #define	CHARWIDTH (LOCHWIDTH+HICHWIDTH)
397c478bd9Sstevel@tonic-gate #define	LOCHMASK ((1<<LOCHWIDTH)-1)
407c478bd9Sstevel@tonic-gate 
417c478bd9Sstevel@tonic-gate /*
427c478bd9Sstevel@tonic-gate  * if HASHWIDTH + CHARWIDTH < bitsizeof(long)
437c478bd9Sstevel@tonic-gate  * one could make LOCHWIDTH=6 and HICHWIDTH=0
447c478bd9Sstevel@tonic-gate  * and simplify accordingly; the hanky-panky
457c478bd9Sstevel@tonic-gate  * is to avoid overflow in long multiplication
467c478bd9Sstevel@tonic-gate  */
477c478bd9Sstevel@tonic-gate #define	NC 30
487c478bd9Sstevel@tonic-gate 
497c478bd9Sstevel@tonic-gate static long hashsize = HASHSIZE;
507c478bd9Sstevel@tonic-gate static long pow2[NC*2];
517c478bd9Sstevel@tonic-gate 
527c478bd9Sstevel@tonic-gate static signed char hashtab[] = {
537c478bd9Sstevel@tonic-gate -1,	-1,	-1,	-1,	-1,	-1,	0,	31,	/*  &' */
547c478bd9Sstevel@tonic-gate -1,	-1,	-1,	-1,	68,	-1,	65,	-1,
557c478bd9Sstevel@tonic-gate 2,	25,	20,	35,	54,	61,	40,	39,	/* 0-7 */
567c478bd9Sstevel@tonic-gate 42,	33,	64,	67,	-1,	-1,	-1,	66,
577c478bd9Sstevel@tonic-gate -1,	60,	43,	30,	5,	16,	47,	18,	/* A-G */
587c478bd9Sstevel@tonic-gate 41,	36,	51,	6,	13,	56,	55,	58,
597c478bd9Sstevel@tonic-gate 49,	12,	59,	46,	21,	32,	63,	34,
607c478bd9Sstevel@tonic-gate 57,	52,	3,	-1,	-1,	-1,	-1,	-1,
617c478bd9Sstevel@tonic-gate -1,	22,	29,	8,	7,	10,	1,	28,	/* a-g */
627c478bd9Sstevel@tonic-gate 11,	62,	37,	48,	15,	50,	9,	4,
637c478bd9Sstevel@tonic-gate 19,	38,	45,	24,	23,	26,	17,	44,
647c478bd9Sstevel@tonic-gate 27,	14,	53,	-1,	-1,	-1,	-1,	-1
657c478bd9Sstevel@tonic-gate };
667c478bd9Sstevel@tonic-gate 
677c478bd9Sstevel@tonic-gate 
687c478bd9Sstevel@tonic-gate unsigned long
hash(char * s)697c478bd9Sstevel@tonic-gate hash(char *s)
707c478bd9Sstevel@tonic-gate {
71*0d8b5334Sceastha 	int c;
72*0d8b5334Sceastha 	long *lp;
737c478bd9Sstevel@tonic-gate 	unsigned long h = 0;
747c478bd9Sstevel@tonic-gate 	for (lp = pow2; (c = *s++) != 0; ) {
757c478bd9Sstevel@tonic-gate 		c = hashtab[c-' '];
767c478bd9Sstevel@tonic-gate 		h += (c&LOCHMASK) * *lp++;
777c478bd9Sstevel@tonic-gate 		h += (c>>LOCHWIDTH) * *lp++;
787c478bd9Sstevel@tonic-gate 		h %= hashsize;
797c478bd9Sstevel@tonic-gate 	}
807c478bd9Sstevel@tonic-gate 	return (h);
817c478bd9Sstevel@tonic-gate }
827c478bd9Sstevel@tonic-gate 
837c478bd9Sstevel@tonic-gate void
hashinit(void)847c478bd9Sstevel@tonic-gate hashinit(void)
857c478bd9Sstevel@tonic-gate {
867c478bd9Sstevel@tonic-gate #if ((1L << (HASHWIDTH+LOCHWIDTH) == 0) || (1L << (HASHWIDTH+HICHWIDTH) == 0))
877c478bd9Sstevel@tonic-gate 	abort();	/* overflow is imminent */
887c478bd9Sstevel@tonic-gate #else
89*0d8b5334Sceastha 	int i;
907c478bd9Sstevel@tonic-gate 
917c478bd9Sstevel@tonic-gate 	pow2[0] = 1L<<(HASHWIDTH-CHARWIDTH-2);
927c478bd9Sstevel@tonic-gate 	for (i = 0; i < 2*NC-3; i += 2) {
937c478bd9Sstevel@tonic-gate 		pow2[i+1] = (pow2[i]<<LOCHWIDTH) % hashsize;
947c478bd9Sstevel@tonic-gate 		pow2[i+2] = (pow2[i+1]<<HICHWIDTH) % hashsize;
957c478bd9Sstevel@tonic-gate 	}
967c478bd9Sstevel@tonic-gate #endif
977c478bd9Sstevel@tonic-gate }
98