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