1 /* $NetBSD: t_hash.c,v 1.1 2023/07/30 09:22:02 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2023 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <sys/cdefs.h>
30
31 #include <atf-c.h>
32 #include <stdint.h>
33
34 #include "hash.h"
35
36 /* known-answer tests */
37 struct kat {
38 const char *in;
39 unsigned long long out;
40 };
41
42 /*
43 * From the SysV spec, with uint64_t instead of unsigned long to
44 * illustrate the problem on all systems, not just LP64 ones.
45 *
46 * https://www.sco.com/developers/devspecs/gabi41.pdf#page=95
47 */
48 static uint64_t
sysv_broken_hash(const char * name)49 sysv_broken_hash(const char *name)
50 {
51 uint64_t h = 0, g;
52
53 while (*name) {
54 h = (h << 4) + *name++;
55 if ((g = h & 0xf0000000) != 0)
56 h ^= g >> 24;
57 h &= ~g;
58 }
59
60 return h;
61 }
62
63 ATF_TC(sysv);
ATF_TC_HEAD(sysv,tc)64 ATF_TC_HEAD(sysv, tc)
65 {
66 atf_tc_set_md_var(tc, "descr", "SysV hash (32-bit)");
67 }
ATF_TC_BODY(sysv,tc)68 ATF_TC_BODY(sysv, tc)
69 {
70 static const struct kat kat[] = {
71 { "", 0x00000000 },
72 { "a", 0x00000061 },
73 { "aa", 0x00000671 },
74 { "aaa", 0x00006771 },
75 { "aaaa", 0x00067771 },
76 { "aaaaa", 0x00677771 },
77 { "aaaaaa", 0x06777771 },
78 { "aaaaaaa", 0x07777711 },
79 { "aaaaaaaa", 0x07777101 },
80 { "aaaaaaaaa", 0x07771001 },
81 { "ab", 0x00000672 },
82 { "abc", 0x00006783 },
83 { "abcd", 0x00067894 },
84 { "abcde", 0x006789a5 },
85 { "abcdef", 0x06789ab6 },
86 { "abcdefg", 0x0789aba7 },
87 { "abcdefgh", 0x089abaa8 },
88 { "abcdefghi", 0x09abaa69 },
89 /* https://maskray.me/blog/2023-04-12-elf-hash-function */
90 { "Z", 0x0000005a },
91 { "ZZ", 0x000005fa },
92 { "ZZZ", 0x00005ffa },
93 { "ZZZZ", 0x0005fffa },
94 { "ZZZZZ", 0x005ffffa },
95 { "ZZZZZW", 0x05fffff7 },
96 { "ZZZZZW9", 0x0ffffff9 },
97 { "ZZZZZW9p", 0x00000000 },
98 { "pneumonoultramicroscopicsilicovolcanoconiosis",
99 0x051706b3 },
100 };
101 unsigned i;
102
103 for (i = 0; i < __arraycount(kat); i++) {
104 unsigned long long h = _rtld_sysv_hash(kat[i].in);
105
106 ATF_CHECK_EQ_MSG(h, kat[i].out,
107 "[%u] _rtld_hash_sysv(\"%s\") = 0x%08llx != 0x%08llx",
108 i, kat[i].in, h, kat[i].out);
109 }
110 }
111
112 ATF_TC(sysv_broken);
ATF_TC_HEAD(sysv_broken,tc)113 ATF_TC_HEAD(sysv_broken, tc)
114 {
115 atf_tc_set_md_var(tc, "descr",
116 "SysV hash (broken with 64-bit unsigned long)");
117 }
ATF_TC_BODY(sysv_broken,tc)118 ATF_TC_BODY(sysv_broken, tc)
119 {
120 static const struct kat kat[] = {
121 { "", 0x00000000 },
122 { "a", 0x00000061 },
123 { "aa", 0x00000671 },
124 { "aaa", 0x00006771 },
125 { "aaaa", 0x00067771 },
126 { "aaaaa", 0x00677771 },
127 { "aaaaaa", 0x06777771 },
128 { "aaaaaaa", 0x07777711 },
129 { "aaaaaaaa", 0x07777101 },
130 { "aaaaaaaaa", 0x07771001 },
131 { "ab", 0x00000672 },
132 { "abc", 0x00006783 },
133 { "abcd", 0x00067894 },
134 { "abcde", 0x006789a5 },
135 { "abcdef", 0x06789ab6 },
136 { "abcdefg", 0x0789aba7 },
137 { "abcdefgh", 0x089abaa8 },
138 { "abcdefghi", 0x09abaa69 },
139 /* https://maskray.me/blog/2023-04-12-elf-hash-function */
140 { "Z", 0x0000005a },
141 { "ZZ", 0x000005fa },
142 { "ZZZ", 0x00005ffa },
143 { "ZZZZ", 0x0005fffa },
144 { "ZZZZZ", 0x005ffffa },
145 { "ZZZZZW", 0x05fffff7 },
146 { "ZZZZZW9", 0x0ffffff9 },
147 { "ZZZZZW9p", 0x100000000 },
148 { "pneumonoultramicroscopicsilicovolcanoconiosis",
149 0x051706b3 },
150 };
151 unsigned i;
152
153 for (i = 0; i < __arraycount(kat); i++) {
154 unsigned long long h = sysv_broken_hash(kat[i].in);
155
156 ATF_CHECK_EQ_MSG(h, kat[i].out,
157 "[%u] sysv_broken_hash(\"%s\") = 0x%08llx != 0x%08llx",
158 i, kat[i].in, h, kat[i].out);
159 }
160 }
161
162 ATF_TC(gnu);
ATF_TC_HEAD(gnu,tc)163 ATF_TC_HEAD(gnu, tc)
164 {
165 atf_tc_set_md_var(tc, "descr", "GNU hash (djb2)");
166 }
ATF_TC_BODY(gnu,tc)167 ATF_TC_BODY(gnu, tc)
168 {
169 static const struct kat kat[] = {
170 { """", 0x00001505 },
171 { "a", 0x0002b606 },
172 { "aa", 0x00597727 },
173 { "aaa", 0x0b885c68 },
174 { "aaaa", 0x7c93e9c9 },
175 { "aaaaa", 0x0f11234a },
176 { "aaaaaa", 0xf1358ceb },
177 { "aaaaaaa", 0x17e72aac },
178 { "aaaaaaaa", 0x14cc808d },
179 { "aaaaaaaaa", 0xae5c928e },
180 { "ab", 0x00597728 },
181 { "abc", 0x0b885c8b },
182 { "abcd", 0x7c93ee4f },
183 { "abcde", 0x0f11b894 },
184 { "abcdef", 0xf148cb7a },
185 { "abcdefg", 0x1a623b21 },
186 { "abcdefgh", 0x66a99fa9 },
187 { "abcdefghi", 0x3bdd9532 },
188 { "Z", 0x0002b5ff },
189 { "ZZ", 0x00597639 },
190 { "ZZZ", 0x0b883db3 },
191 { "ZZZZ", 0x7c8ff46d },
192 { "ZZZZZ", 0x0e8e8267 },
193 { "ZZZZZW", 0xe05ecf9e },
194 { "ZZZZZW9", 0xec38c397 },
195 { "ZZZZZW9p", 0x735136e7 },
196 { "pneumonoultramicroscopicsilicovolcanoconiosis",
197 0xee6245b5 },
198 };
199 unsigned i;
200
201 for (i = 0; i < __arraycount(kat); i++) {
202 unsigned long long h = _rtld_gnu_hash(kat[i].in);
203
204 ATF_CHECK_EQ_MSG(h, kat[i].out,
205 "[%u] _rtld_gnu_hash(\"%s\") = 0x%08llx != 0x%08llx",
206 i, kat[i].in, h, kat[i].out);
207 }
208 }
209
ATF_TP_ADD_TCS(tp)210 ATF_TP_ADD_TCS(tp)
211 {
212
213 ATF_TP_ADD_TC(tp, gnu);
214 ATF_TP_ADD_TC(tp, sysv);
215 ATF_TP_ADD_TC(tp, sysv_broken);
216
217 return atf_no_error();
218 }
219