usr/src/cmd/msgfmt/gnu_hash.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 2001-2002 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 #pragma ident   "%Z%%M% %I%     %E% SMI"
  28
  29 #include "gnu_msgfmt.h"
  30 #include "gnu_prime.h"
  31
  32
  33 /*
  34  * hashpjw
  35  *
  36  * Calculates the hash value from the specified string.
  37  * Actual hashid will be mod(hash value, PRIME_NUMBER).
  38  *
  39  * Ref: Compilers - Principles, Techniques, and Tools
  40  * Aho, Sethi, and Ullman
  41  */
  42 unsigned int
  43 hashpjw(const char *str)
  44 {
  45         const char      *p;
  46         unsigned int    h = 0, g;
  47
  48         for (p = str; *p; p++) {
  49                 h = (h << 4) + *p;
  50                 g = h & 0xf0000000;
  51                 if (g) {
  52                         h = h ^ (g >> 24);
  53                         h = h ^ g;
  54                 }
  55         }
  56
  57         return (h);
  58 }
  59
  60 static unsigned int
  61 find_prime_big(unsigned int n)
  62 {
  63         int     t;
  64         unsigned int    max_tbl_prime, prd;
  65         max_tbl_prime = prime[MAX_PRIME_INDEX] + 2;
  66
  67         for (; ; ) {
  68                 for (t = 1; t <= MAX_PRIME_INDEX; t++) {
  69                         if (n % prime[t] == 0) {
  70                                 /* n is not a prime number */
  71                                 break;
  72                         }
  73                 }
  74                 if (t <= MAX_PRIME_INDEX) {
  75                         n += 2;
  76                         continue;
  77                 }
  78
  79                 prd = max_tbl_prime;
  80                 while ((prd * prd < n) && (n % prd != 0)) {
  81                         prd += 2;
  82                 }
  83                 if (n % prd == 0) {
  84                         n += 2;
  85                         continue;
  86                 }
  87                 return (n);
  88         }
  89         /* NOTREACHED */
  90 }
  91
  92 unsigned int
  93 find_prime(unsigned int tbl_size)
  94 {
  95         int     t, d;
  96         unsigned int    n, prd;
  97
  98         /* for compatibility with GNU msgfmt */
  99         if (tbl_size == 1)
 100                 return (1);
 101         else if (tbl_size == 2)
 102                 return (5);
 103
 104         n = 4 * tbl_size / 3;
 105
 106         /* make n an odd number */
 107         n |= 1;
 108
 109         prd = n / 100;
 110         if (prd <= MAX_INDEX_INDEX) {
 111                 /* first, search the table */
 112                 for (t = index[prd] + 1; t <= MAX_PRIME_INDEX; t++) {
 113                         if (prime[t] >= n)
 114                                 return (prime[t]);
 115                 }
 116                 error(ERR_PRIME, n);
 117                 /* NOTREACHED */
 118         }
 119         t = START_SEARCH_INDEX;
 120         for (; ; ) {
 121                 while (prime[t] * prime[t] < n) {
 122                         if (t == MAX_PRIME_INDEX) {
 123                                 return (find_prime_big(n));
 124                         }
 125                         t++;
 126                 }
 127                 for (d = 1; d <= t; d++) {
 128                         if (n % prime[d] == 0) {
 129                                 /* n is not a prime number */
 130                                 break;
 131                         }
 132                 }
 133                 if (d > t) {
 134                         /* n is a prime number */
 135                         return (n);
 136                 }
 137                 n += 2;
 138         }
 139         /* NOTREACHED */
 140 }
 141
 142 unsigned int
 143 get_hash_index(unsigned int *hash_tbl, unsigned int hash_value,
 144         unsigned int hash_size)
 145 {
 146         unsigned int    idx, inc;
 147
 148         idx = hash_value % hash_size;
 149         inc = 1 + (hash_value % (hash_size - 2));
 150
 151         for (; ; ) {
 152                 if (!hash_tbl[idx])
 153                         return (idx);
 154                 idx = (idx + inc) % hash_size;
 155         }
 156         /* NOTREACHED */
 157 }