xref: /illumos-gate/usr/src/cmd/spell/hashlook.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 #include <stdlib.h>
337c478bd9Sstevel@tonic-gate #include <stdio.h>
347c478bd9Sstevel@tonic-gate #include "hash.h"
357c478bd9Sstevel@tonic-gate #include "huff.h"
367c478bd9Sstevel@tonic-gate 
377c478bd9Sstevel@tonic-gate unsigned *table;
387c478bd9Sstevel@tonic-gate int hindex[NI];
397c478bd9Sstevel@tonic-gate 
407c478bd9Sstevel@tonic-gate #define	B (BYTE * sizeof (unsigned))
417c478bd9Sstevel@tonic-gate #define	L (BYTE * sizeof (long)-1)
427c478bd9Sstevel@tonic-gate #define	MASK (~((unsigned long)1L<<L))
437c478bd9Sstevel@tonic-gate 
447c478bd9Sstevel@tonic-gate #ifdef pdp11	/* sizeof (unsigned)==sizeof(long)/2 */
457c478bd9Sstevel@tonic-gate #define	fetch(wp, bp)\
467c478bd9Sstevel@tonic-gate 	(((((long)wp[0]<<B)|wp[1])<<(B-bp))|(wp[2]>>bp))
477c478bd9Sstevel@tonic-gate #else 		/* sizeof (unsigned)==sizeof(long) */
487c478bd9Sstevel@tonic-gate #define	fetch(wp, bp) ((wp[0] << (B - bp)) | (wp[1] >> bp))
497c478bd9Sstevel@tonic-gate #endif
507c478bd9Sstevel@tonic-gate 
517c478bd9Sstevel@tonic-gate int
hashlook(char * s)527c478bd9Sstevel@tonic-gate hashlook(char *s)
537c478bd9Sstevel@tonic-gate {
547c478bd9Sstevel@tonic-gate 	unsigned long h;
557c478bd9Sstevel@tonic-gate 	unsigned long t;
56*0d8b5334Sceastha 	int bp;
57*0d8b5334Sceastha 	unsigned *wp;
587c478bd9Sstevel@tonic-gate 	long sum;
597c478bd9Sstevel@tonic-gate 	unsigned *tp;
607c478bd9Sstevel@tonic-gate 
617c478bd9Sstevel@tonic-gate 	h = hash(s);
627c478bd9Sstevel@tonic-gate 	t = h>>(HASHWIDTH-INDEXWIDTH);
637c478bd9Sstevel@tonic-gate 	wp = &table[hindex[t]];
647c478bd9Sstevel@tonic-gate 	tp = &table[hindex[t+1]];
657c478bd9Sstevel@tonic-gate 	bp = B;
667c478bd9Sstevel@tonic-gate 	sum = (long)t<<(HASHWIDTH-INDEXWIDTH);
677c478bd9Sstevel@tonic-gate 	for (;;) {
687c478bd9Sstevel@tonic-gate 		{
697c478bd9Sstevel@tonic-gate 			/*
707c478bd9Sstevel@tonic-gate 			 * this block is equivalent to:
717c478bd9Sstevel@tonic-gate 			 * bp -= decode((fetch(wp, bp) >> 1) & MASK, &t);
727c478bd9Sstevel@tonic-gate 			 */
737c478bd9Sstevel@tonic-gate 			long y;
747c478bd9Sstevel@tonic-gate 			long v;
757c478bd9Sstevel@tonic-gate 
767c478bd9Sstevel@tonic-gate 			/*
777c478bd9Sstevel@tonic-gate 			 * shift 32 on those machines leaves destination
787c478bd9Sstevel@tonic-gate 			 * unchanged
797c478bd9Sstevel@tonic-gate 			 */
807c478bd9Sstevel@tonic-gate 			if (bp == 0)
817c478bd9Sstevel@tonic-gate 				y = 0;
827c478bd9Sstevel@tonic-gate 			else
837c478bd9Sstevel@tonic-gate 				y = wp[0] << (B - bp);
847c478bd9Sstevel@tonic-gate 			if (bp < 32)
857c478bd9Sstevel@tonic-gate 				y |= (wp[1] >> bp);
867c478bd9Sstevel@tonic-gate 			y = (y >> 1) & MASK;
877c478bd9Sstevel@tonic-gate 			if (y < cs) {
887c478bd9Sstevel@tonic-gate 				t = y >> (long) (L+1-w);
897c478bd9Sstevel@tonic-gate 				bp -= w-1;
907c478bd9Sstevel@tonic-gate 			} else {
917c478bd9Sstevel@tonic-gate 				for (bp -= w, v = v0; y >= qcs;
927c478bd9Sstevel@tonic-gate 				    y = (y << 1) & MASK, v += n)
937c478bd9Sstevel@tonic-gate 					bp -= 1;
947c478bd9Sstevel@tonic-gate 				t = v + (y>> (long)(L-w));
957c478bd9Sstevel@tonic-gate 			}
967c478bd9Sstevel@tonic-gate 		}
977c478bd9Sstevel@tonic-gate 		while (bp <= 0) {
987c478bd9Sstevel@tonic-gate 			bp += B;
997c478bd9Sstevel@tonic-gate 			wp++;
1007c478bd9Sstevel@tonic-gate 		}
1017c478bd9Sstevel@tonic-gate 		if (wp >= tp && (wp > tp||bp < B))
1027c478bd9Sstevel@tonic-gate 			return (0);
1037c478bd9Sstevel@tonic-gate 		sum += t;
1047c478bd9Sstevel@tonic-gate 		if (sum < h)
1057c478bd9Sstevel@tonic-gate 			continue;
1067c478bd9Sstevel@tonic-gate 		return (sum == h);
1077c478bd9Sstevel@tonic-gate 	}
1087c478bd9Sstevel@tonic-gate }
1097c478bd9Sstevel@tonic-gate 
1107c478bd9Sstevel@tonic-gate 
1117c478bd9Sstevel@tonic-gate int
prime(char * file)1127c478bd9Sstevel@tonic-gate prime(char *file)
1137c478bd9Sstevel@tonic-gate {
114*0d8b5334Sceastha 	FILE *f;
1157c478bd9Sstevel@tonic-gate 
1167c478bd9Sstevel@tonic-gate #ifdef pdp11	/* because of insufficient address space for buffers */
1177c478bd9Sstevel@tonic-gate 	fd = dup(0);
1187c478bd9Sstevel@tonic-gate 	close(0);
1197c478bd9Sstevel@tonic-gate 	if (open(file, 0) != 0)
1207c478bd9Sstevel@tonic-gate 		return (0);
1217c478bd9Sstevel@tonic-gate 	f = stdin;
1227c478bd9Sstevel@tonic-gate 	if (rhuff(f) == 0 || read(fileno(f), (char *)hindex,
1237c478bd9Sstevel@tonic-gate 	    NI * sizeof (*hindex)) != NI * sizeof (*hindex) ||
1247c478bd9Sstevel@tonic-gate 	    (table = (unsigned *)malloc(hindex[NI-1] * sizeof (*table))) == 0 ||
1257c478bd9Sstevel@tonic-gate 	    read(fileno(f), (char *)table, sizeof (*table) * hindex[NI-1]) !=
1267c478bd9Sstevel@tonic-gate 	    hindex[NI-1] * sizeof (*table))
1277c478bd9Sstevel@tonic-gate 		return (0);
1287c478bd9Sstevel@tonic-gate 	close(0);
1297c478bd9Sstevel@tonic-gate 	if (dup(fd) != 0)
1307c478bd9Sstevel@tonic-gate 		return (0);
1317c478bd9Sstevel@tonic-gate 	close(fd);
1327c478bd9Sstevel@tonic-gate #else
1337c478bd9Sstevel@tonic-gate 	if ((f = fopen(file, "r")) == NULL)
1347c478bd9Sstevel@tonic-gate 		return (0);
1357c478bd9Sstevel@tonic-gate 	if (rhuff(f) == 0 ||
1367c478bd9Sstevel@tonic-gate 	    fread((char *)hindex, sizeof (*hindex),  NI, f) != NI ||
1377c478bd9Sstevel@tonic-gate 	    (table = (unsigned *)malloc(hindex[NI-1] * sizeof (*table))) == 0 ||
1387c478bd9Sstevel@tonic-gate 	    fread((char *)table, sizeof (*table), hindex[NI-1], f) !=
1397c478bd9Sstevel@tonic-gate 	    hindex[NI-1])
1407c478bd9Sstevel@tonic-gate 		return (0);
1417c478bd9Sstevel@tonic-gate 	(void) fclose(f);
1427c478bd9Sstevel@tonic-gate #endif
1437c478bd9Sstevel@tonic-gate 	hashinit();
1447c478bd9Sstevel@tonic-gate 	return (1);
1457c478bd9Sstevel@tonic-gate }
146