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