1 /*
2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3 *
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
14 * PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 /* $Id: hash.c,v 1.7 2020/09/14 08:40:44 florian Exp $ */
18
19 /*! \file
20 * Some portion of this code was derived from universal hash function
21 * libraries of Rice University.
22 \section license UH Universal Hashing Library
23
24 Copyright ((c)) 2002, Rice University
25 All rights reserved.
26
27 Redistribution and use in source and binary forms, with or without
28 modification, are permitted provided that the following conditions are
29 met:
30
31 * Redistributions of source code must retain the above copyright
32 notice, this list of conditions and the following disclaimer.
33
34 * Redistributions in binary form must reproduce the above
35 copyright notice, this list of conditions and the following
36 disclaimer in the documentation and/or other materials provided
37 with the distribution.
38
39 * Neither the name of Rice University (RICE) nor the names of its
40 contributors may be used to endorse or promote products derived
41 from this software without specific prior written permission.
42
43 This software is provided by RICE and the contributors on an "as is"
44 basis, without any representations or warranties of any kind, express
45 or implied including, but not limited to, representations or
46 warranties of non-infringement, merchantability or fitness for a
47 particular purpose. In no event shall RICE or contributors be liable
48 for any direct, indirect, incidental, special, exemplary, or
49 consequential damages (including, but not limited to, procurement of
50 substitute goods or services; loss of use, data, or profits; or
51 business interruption) however caused and on any theory of liability,
52 whether in contract, strict liability, or tort (including negligence
53 or otherwise) arising in any way out of the use of this software, even
54 if advised of the possibility of such damage.
55 */
56
57 #include <stdlib.h>
58
59 #include <isc/hash.h>
60 #include <isc/util.h>
61
62 static unsigned char maptolower[] = {
63 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
64 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
65 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
66 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
67 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
68 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
69 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
70 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
71 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
72 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
73 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
74 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
75 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
76 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
77 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
78 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
79 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
80 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
81 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
82 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
83 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
84 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
85 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
86 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
87 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
88 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
89 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
90 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
91 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
92 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
93 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
94 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
95 };
96
97 static uint32_t fnv_offset_basis;
98 static int fnv_once = 0;
99
100 static void
fnv_initialize(void)101 fnv_initialize(void) {
102 /*
103 * This function should not leave fnv_offset_basis set to
104 * 0. Also, after this function has been called, if it is called
105 * again, it should not change fnv_offset_basis.
106 */
107 while (fnv_offset_basis == 0) {
108 fnv_offset_basis = arc4random();
109 }
110 }
111
112 uint32_t
isc_hash_function_reverse(const void * data,size_t length,int case_sensitive,const uint32_t * previous_hashp)113 isc_hash_function_reverse(const void *data, size_t length,
114 int case_sensitive,
115 const uint32_t *previous_hashp)
116 {
117 uint32_t hval;
118 const unsigned char *bp;
119 const unsigned char *be;
120
121 REQUIRE(length == 0 || data != NULL);
122 if (!fnv_once) {
123 fnv_once = 1;
124 fnv_initialize();
125 }
126
127 hval = previous_hashp != NULL ?
128 *previous_hashp : fnv_offset_basis;
129
130 if (length == 0)
131 return (hval);
132
133 bp = (const unsigned char *) data;
134 be = bp + length;
135
136 /*
137 * Fowler-Noll-Vo FNV-1a hash function.
138 *
139 * NOTE: A random fnv_offset_basis is used by default to avoid
140 * collision attacks as the hash function is reversible. This
141 * makes the mapping non-deterministic, but the distribution in
142 * the domain is still uniform.
143 */
144
145 if (case_sensitive) {
146 while (be >= bp + 4) {
147 be -= 4;
148 hval ^= (uint32_t) be[3];
149 hval *= 16777619;
150 hval ^= (uint32_t) be[2];
151 hval *= 16777619;
152 hval ^= (uint32_t) be[1];
153 hval *= 16777619;
154 hval ^= (uint32_t) be[0];
155 hval *= 16777619;
156 }
157 while (--be >= bp) {
158 hval ^= (uint32_t) *be;
159 hval *= 16777619;
160 }
161 } else {
162 while (be >= bp + 4) {
163 be -= 4;
164 hval ^= (uint32_t) maptolower[be[3]];
165 hval *= 16777619;
166 hval ^= (uint32_t) maptolower[be[2]];
167 hval *= 16777619;
168 hval ^= (uint32_t) maptolower[be[1]];
169 hval *= 16777619;
170 hval ^= (uint32_t) maptolower[be[0]];
171 hval *= 16777619;
172 }
173 while (--be >= bp) {
174 hval ^= (uint32_t) maptolower[*be];
175 hval *= 16777619;
176 }
177 }
178
179 return (hval);
180 }
181