xref: /illumos-gate/usr/src/uts/common/fs/pkp_hash.c (revision 0616fd7f)
1*0616fd7fSPavel Filipensky /*
2*0616fd7fSPavel Filipensky  * CDDL HEADER START
3*0616fd7fSPavel Filipensky  *
4*0616fd7fSPavel Filipensky  * The contents of this file are subject to the terms of the
5*0616fd7fSPavel Filipensky  * Common Development and Distribution License (the "License").
6*0616fd7fSPavel Filipensky  * You may not use this file except in compliance with the License.
7*0616fd7fSPavel Filipensky  *
8*0616fd7fSPavel Filipensky  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9*0616fd7fSPavel Filipensky  * or http://www.opensolaris.org/os/licensing.
10*0616fd7fSPavel Filipensky  * See the License for the specific language governing permissions
11*0616fd7fSPavel Filipensky  * and limitations under the License.
12*0616fd7fSPavel Filipensky  *
13*0616fd7fSPavel Filipensky  * When distributing Covered Code, include this CDDL HEADER in each
14*0616fd7fSPavel Filipensky  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15*0616fd7fSPavel Filipensky  * If applicable, add the following below this CDDL HEADER, with the
16*0616fd7fSPavel Filipensky  * fields enclosed by brackets "[]" replaced with your own identifying
17*0616fd7fSPavel Filipensky  * information: Portions Copyright [yyyy] [name of copyright owner]
18*0616fd7fSPavel Filipensky  *
19*0616fd7fSPavel Filipensky  * CDDL HEADER END
20*0616fd7fSPavel Filipensky  */
21*0616fd7fSPavel Filipensky /*
22*0616fd7fSPavel Filipensky  * Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
23*0616fd7fSPavel Filipensky  */
24*0616fd7fSPavel Filipensky 
25*0616fd7fSPavel Filipensky #include <sys/pkp_hash.h>
26*0616fd7fSPavel Filipensky 
27*0616fd7fSPavel Filipensky /*
28*0616fd7fSPavel Filipensky  * Pearson's string hash
29*0616fd7fSPavel Filipensky  *
30*0616fd7fSPavel Filipensky  * See: Communications of the ACM, June 1990 Vol 33 pp 677-680
31*0616fd7fSPavel Filipensky  * http://portal.acm.org/citation.cfm?doid=78973.78978
32*0616fd7fSPavel Filipensky  */
33*0616fd7fSPavel Filipensky 
34*0616fd7fSPavel Filipensky #define		MOD2(a, pow_of_2)	((a) & ((pow_of_2) - 1))
35*0616fd7fSPavel Filipensky 
36*0616fd7fSPavel Filipensky static uint_t	pkp_tab[PKP_HASH_SIZE] = {
37*0616fd7fSPavel Filipensky 1, 87, 49, 12, 176, 178, 102, 166, 121, 193, 6, 84, 249, 230, 44, 163,
38*0616fd7fSPavel Filipensky 14, 197, 213, 181, 161, 85, 218, 80, 64, 239, 24, 226, 236, 142, 38, 200,
39*0616fd7fSPavel Filipensky 110, 177, 104, 103, 141, 253, 255, 50, 77, 101, 81, 18, 45, 96, 31, 222,
40*0616fd7fSPavel Filipensky 25, 107, 190, 70, 86, 237, 240, 34, 72, 242, 20, 214, 244, 227, 149, 235,
41*0616fd7fSPavel Filipensky 97, 234, 57, 22, 60, 250, 82, 175, 208, 5, 127, 199, 111, 62, 135, 248,
42*0616fd7fSPavel Filipensky 174, 169, 211, 58, 66, 154, 106, 195, 245, 171, 17, 187, 182, 179, 0, 243,
43*0616fd7fSPavel Filipensky 132, 56, 148, 75, 128, 133, 158, 100, 130, 126, 91, 13, 153, 246, 216, 219,
44*0616fd7fSPavel Filipensky 119, 68, 223, 78, 83, 88, 201, 99, 122, 11, 92, 32, 136, 114, 52, 10,
45*0616fd7fSPavel Filipensky 138, 30, 48, 183, 156, 35, 61, 26, 143, 74, 251, 94, 129, 162, 63, 152,
46*0616fd7fSPavel Filipensky 170, 7, 115, 167, 241, 206, 3, 150, 55, 59, 151, 220, 90, 53, 23, 131,
47*0616fd7fSPavel Filipensky 125, 173, 15, 238, 79, 95, 89, 16, 105, 137, 225, 224, 217, 160, 37, 123,
48*0616fd7fSPavel Filipensky 118, 73, 2, 157, 46, 116, 9, 145, 134, 228, 207, 212, 202, 215, 69, 229,
49*0616fd7fSPavel Filipensky 27, 188, 67, 124, 168, 252, 42, 4, 29, 108, 21, 247, 19, 205, 39, 203,
50*0616fd7fSPavel Filipensky 233, 40, 186, 147, 198, 192, 155, 33, 164, 191, 98, 204, 165, 180, 117, 76,
51*0616fd7fSPavel Filipensky 140, 36, 210, 172, 41, 54, 159, 8, 185, 232, 113, 196, 231, 47, 146, 120,
52*0616fd7fSPavel Filipensky 51, 65, 28, 144, 254, 221, 93, 189, 194, 139, 112, 43, 71, 109, 184, 209
53*0616fd7fSPavel Filipensky };
54*0616fd7fSPavel Filipensky 
55*0616fd7fSPavel Filipensky uint_t
pkp_tab_hash(char * str,int len)56*0616fd7fSPavel Filipensky pkp_tab_hash(char *str, int len)
57*0616fd7fSPavel Filipensky {
58*0616fd7fSPavel Filipensky 	uint_t	key = 0x12345678;	/* arbitrary value */
59*0616fd7fSPavel Filipensky 	uint_t	hash;
60*0616fd7fSPavel Filipensky 	int	i;
61*0616fd7fSPavel Filipensky 
62*0616fd7fSPavel Filipensky 	hash = MOD2((key + len), PKP_HASH_SIZE);
63*0616fd7fSPavel Filipensky 
64*0616fd7fSPavel Filipensky 	for (i = 0; i < len; i++) {
65*0616fd7fSPavel Filipensky 		hash = MOD2((hash + str[i]), PKP_HASH_SIZE);
66*0616fd7fSPavel Filipensky 		hash = pkp_tab[hash];
67*0616fd7fSPavel Filipensky 	}
68*0616fd7fSPavel Filipensky 
69*0616fd7fSPavel Filipensky 	return (hash);
70*0616fd7fSPavel Filipensky }
71