usr/src/cmd/spell/hashlook.c

   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 #include <stdlib.h>
  33 #include <stdio.h>
  34 #include "hash.h"
  35 #include "huff.h"
  36
  37 unsigned *table;
  38 int hindex[NI];
  39
  40 #define B (BYTE * sizeof (unsigned))
  41 #define L (BYTE * sizeof (long)-1)
  42 #define MASK (~((unsigned long)1L<<L))
  43
  44 #ifdef pdp11    /* sizeof (unsigned)==sizeof(long)/2 */
  45 #define fetch(wp, bp)\
  46         (((((long)wp[0]<<B)|wp[1])<<(B-bp))|(wp[2]>>bp))
  47 #else           /* sizeof (unsigned)==sizeof(long) */
  48 #define fetch(wp, bp) ((wp[0] << (B - bp)) | (wp[1] >> bp))
  49 #endif
  50
  51 int
  52 hashlook(char *s)
  53 {
  54         unsigned long h;
  55         unsigned long t;
  56         int bp;
  57         unsigned *wp;
  58         long sum;
  59         unsigned *tp;
  60
  61         h = hash(s);
  62         t = h>>(HASHWIDTH-INDEXWIDTH);
  63         wp = &table[hindex[t]];
  64         tp = &table[hindex[t+1]];
  65         bp = B;
  66         sum = (long)t<<(HASHWIDTH-INDEXWIDTH);
  67         for (;;) {
  68                 {
  69                         /*
  70                          * this block is equivalent to:
  71                          * bp -= decode((fetch(wp, bp) >> 1) & MASK, &t);
  72                          */
  73                         long y;
  74                         long v;
  75
  76                         /*
  77                          * shift 32 on those machines leaves destination
  78                          * unchanged
  79                          */
  80                         if (bp == 0)
  81                                 y = 0;
  82                         else
  83                                 y = wp[0] << (B - bp);
  84                         if (bp < 32)
  85                                 y |= (wp[1] >> bp);
  86                         y = (y >> 1) & MASK;
  87                         if (y < cs) {
  88                                 t = y >> (long) (L+1-w);
  89                                 bp -= w-1;
  90                         } else {
  91                                 for (bp -= w, v = v0; y >= qcs;
  92                                     y = (y << 1) & MASK, v += n)
  93                                         bp -= 1;
  94                                 t = v + (y>> (long)(L-w));
  95                         }
  96                 }
  97                 while (bp <= 0) {
  98                         bp += B;
  99                         wp++;
 100                 }
 101                 if (wp >= tp && (wp > tp||bp < B))
 102                         return (0);
 103                 sum += t;
 104                 if (sum < h)
 105                         continue;
 106                 return (sum == h);
 107         }
 108 }
 109
 110
 111 int
 112 prime(char *file)
 113 {
 114         FILE *f;
 115
 116 #ifdef pdp11    /* because of insufficient address space for buffers */
 117         fd = dup(0);
 118         close(0);
 119         if (open(file, O_RDONLY) != 0)
 120                 return (0);
 121         f = stdin;
 122         if (rhuff(f) == 0 || read(fileno(f), (char *)hindex,
 123             NI * sizeof (*hindex)) != NI * sizeof (*hindex) ||
 124             (table = (unsigned *)malloc(hindex[NI-1] * sizeof (*table))) == 0 ||
 125             read(fileno(f), (char *)table, sizeof (*table) * hindex[NI-1]) !=
 126             hindex[NI-1] * sizeof (*table))
 127                 return (0);
 128         close(0);
 129         if (dup(fd) != 0)
 130                 return (0);
 131         close(fd);
 132 #else
 133         if ((f = fopen(file, "r")) == NULL)
 134                 return (0);
 135         if (rhuff(f) == 0 ||
 136             fread((char *)hindex, sizeof (*hindex),  NI, f) != NI ||
 137             (table = (unsigned *)malloc(hindex[NI-1] * sizeof (*table))) == 0 ||
 138             fread((char *)table, sizeof (*table), hindex[NI-1], f) !=
 139             hindex[NI-1])
 140                 return (0);
 141         (void) fclose(f);
 142 #endif
 143         hashinit();
 144         return (1);
 145 }