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 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); 64 ATF_TC_HEAD(sysv, tc) 65 { 66 atf_tc_set_md_var(tc, "descr", "SysV hash (32-bit)"); 67 } 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); 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 } 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); 163 ATF_TC_HEAD(gnu, tc) 164 { 165 atf_tc_set_md_var(tc, "descr", "GNU hash (djb2)"); 166 } 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 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