1#include "math/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(hash, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "seeds",
6 });
7
8/* We can just use existing values and published known answers, as
9 * these are all published algos, so expected vals below are known answers */
10
11struct hash_vector {
12 const char *input;
13 size_t len;
14 uint32_t expect;
15};
16
17struct murmur_vector {
18 const char *input;
19 size_t len;
20 uint32_t seed;
21 uint32_t expect;
22};
23
24struct hash_vector64 {
25 const char *input;
26 size_t len;
27 uint64_t expect;
28};
29
30static struct test_verdict run_vectors(const struct hash_vector *v, size_t n,
31 uint32_t (*fn)(const void *, size_t),
32 const char *name) {
33 for (size_t i = 0; i < n; i++) {
34 uint32_t got = fn(v[i].input, v[i].len);
35 if (got != v[i].expect) {
36 test_err("%s(\"%s\") = %08x, want %08x", name, v[i].input, got,
37 v[i].expect);
38 return TEST_FAIL(name);
39 }
40 }
41 return TEST_SUCCESS;
42}
43
44static const struct hash_vector djb2_vectors[] = {
45 {"", 0, 0x00001505U}, {"a", 1, 0x0002B606U},
46 {"ab", 2, 0x00597728U}, {"abc", 3, 0x0B885C8BU},
47 {"abcd", 4, 0x7C93EE4FU}, {"abcde", 5, 0x0F11B894U},
48 {"hello", 5, 0x0F923099U}, {"hello, world", 12, 0xB0E4250DU},
49};
50
51static const struct hash_vector sdbm_vectors[] = {
52 {"", 0, 0x00000000U}, {"a", 1, 0x00000061U},
53 {"ab", 2, 0x00611841U}, {"abc", 3, 0x3025F862U},
54 {"abcd", 4, 0xD1BA2082U}, {"abcde", 5, 0xBD500063U},
55 {"hello", 5, 0x28D19932U}, {"hello, world", 12, 0xEE6FB30CU},
56};
57
58static const struct hash_vector fnv1a_vectors[] = {
59 {"", 0, 0x811C9DC5U}, {"a", 1, 0xE40C292CU},
60 {"ab", 2, 0x4D2505CAU}, {"abc", 3, 0x1A47E90BU},
61 {"abcd", 4, 0xCE3479BDU}, {"abcde", 5, 0x749BCF08U},
62 {"hello", 5, 0x4F9F2CABU}, {"hello, world", 12, 0x4D0EA41DU},
63};
64
65static const struct hash_vector64 fnv1a_64_vectors[] = {
66 {"", 0, UINT64_C(0xcbf29ce484222325)},
67 {"a", 1, UINT64_C(0xaf63dc4c8601ec8c)},
68 {"ab", 2, UINT64_C(0x089c4407b545986a)},
69 {"abc", 3, UINT64_C(0xe71fa2190541574b)},
70 {"abcd", 4, UINT64_C(0xfc179f83ee0724dd)},
71 {"abcde", 5, UINT64_C(0x6348c52d762364a8)},
72 {"hello", 5, UINT64_C(0xa430d84680aabd0b)},
73 {"hello, world", 12, UINT64_C(0x17a1a4f267be633d)},
74};
75
76static const struct hash_vector jenkins_vectors[] = {
77 {"", 0, 0x00000000U}, {"a", 1, 0xCA2E9442U},
78 {"ab", 2, 0x45E61E58U}, {"abc", 3, 0xED131F5BU},
79 {"abcd", 4, 0xCD8B6206U}, {"abcde", 5, 0xB98559FCU},
80 {"hello", 5, 0xC8FD181BU}, {"hello, world", 12, 0x1BC6D6A4U},
81};
82
83static const struct hash_vector elf_vectors[] = {
84 {"", 0, 0x00000000U}, {"a", 1, 0x00000061U},
85 {"ab", 2, 0x00000672U}, {"abc", 3, 0x00006783U},
86 {"abcd", 4, 0x00067894U}, {"abcde", 5, 0x006789A5U},
87 {"hello", 5, 0x006EC32FU}, {"hello, world", 12, 0x08925C34U},
88};
89
90static const struct hash_vector bkdr_vectors[] = {
91 {"", 0, 0x00000000U}, {"a", 1, 0x00000061U},
92 {"ab", 2, 0x00003205U}, {"abc", 3, 0x001998F2U},
93 {"abcd", 4, 0x0D19443AU}, {"abcde", 5, 0xB3EDEA13U},
94 {"hello", 5, 0x2F372E8EU}, {"hello, world", 12, 0x81692F4CU},
95};
96
97TEST_DECLARE_UNIT(hash, known_answers) {
98#define RUN(fn, vecs) \
99 do { \
100 struct test_verdict v = \
101 run_vectors(vecs, TEST_ARRAY_LEN(vecs), fn, #fn); \
102 if (v.result != TEST_RESULT_OK) \
103 return v; \
104 } while (0)
105
106 RUN(hash_djb2, djb2_vectors);
107 RUN(hash_sdbm, sdbm_vectors);
108 RUN(hash_fnv1a, fnv1a_vectors);
109 RUN(hash_jenkins_one_at_a_time, jenkins_vectors);
110 RUN(hash_elf, elf_vectors);
111 RUN(hash_bkdr, bkdr_vectors);
112#undef RUN
113
114 for (size_t i = 0; i < TEST_ARRAY_LEN(fnv1a_64_vectors); i++) {
115 const struct hash_vector64 *v = &fnv1a_64_vectors[i];
116 TEST_ASSERT_EQ(hash_fnv1a_64(v->input, v->len), v->expect);
117 }
118
119 uint64_t incremental = HASH_FNV1A_64_OFFSET_BASIS;
120 incremental = hash_fnv1a_64_update(hash: incremental, key: "hello", len: 5);
121 incremental = hash_fnv1a_64_update(hash: incremental, key: ", world", len: 7);
122 TEST_ASSERT_EQ(incremental, hash_fnv1a_64("hello, world", 12));
123
124 return TEST_SUCCESS;
125}
126
127static const struct murmur_vector murmur_vectors[] = {
128 {"", 0, 0U, 0x00000000U},
129 {"a", 1, 0U, 0x3C2569B2U},
130 {"ab", 2, 0U, 0x9BBFD75FU},
131 {"abc", 3, 0U, 0xB3DD93FAU},
132 {"abcd", 4, 0U, 0x43ED676AU},
133 {"abcde", 5, 0U, 0xE89B9AF6U},
134 {"hello", 5, 0U, 0x248BFA47U},
135 {"hello, world", 12, 0U, 0x149BBB7FU},
136 {"", 0, 0x9747B28CU, 0xEBB6C228U},
137 {"a", 1, 0x9747B28CU, 0x7FA09EA6U},
138 {"ab", 2, 0x9747B28CU, 0x74875592U},
139 {"abc", 3, 0x9747B28CU, 0xC84A62DDU},
140 {"abcd", 4, 0x9747B28CU, 0xF0478627U},
141 {"abcde", 5, 0x9747B28CU, 0xE915B832U},
142 {"hello", 5, 0x9747B28CU, 0x5D7F56E8U},
143 {"hello, world", 12, 0x9747B28CU, 0x9A933E00U},
144};
145
146TEST_DECLARE_UNIT(hash, murmur3_known_answers) {
147 for (size_t i = 0; i < TEST_ARRAY_LEN(murmur_vectors); i++) {
148 const struct murmur_vector *v = &murmur_vectors[i];
149 uint32_t got = hash_murmur3_32(key: v->input, len: v->len, seed: v->seed);
150 if (got != v->expect) {
151 test_err("murmur3(\"%s\", seed=%08x) = %08x, want %08x", v->input,
152 v->seed, got, v->expect);
153 return TEST_FAIL("murmur3 known answer");
154 }
155 }
156 return TEST_SUCCESS;
157}
158
159TEST_DECLARE_UNIT(hash, murmur3_seed_sensitivity,
160 TEST_INTENSITY(16, 64, 4096)) {
161 size_t seeds = ctx->intensity_val ? ctx->intensity_val : 64;
162 const char *key = "seed sensitivity";
163 size_t len = strlen(str: key);
164
165 uint32_t base = hash_murmur3_32(key, len, seed: 0);
166 for (uint32_t seed = 1; seed < (uint32_t) seeds; seed++)
167 TEST_ASSERT_NE(hash_murmur3_32(key, len, seed), base);
168
169 return TEST_SUCCESS;
170}
171
172/* Prefix extension bugs */
173TEST_DECLARE_UNIT(hash, respects_length) {
174 static const char padded[] = "abcd\xFF\xFF\xFF\xFF";
175 static const char clean[] = "abcd";
176
177 TEST_ASSERT_EQ(hash_djb2(padded, 4), hash_djb2(clean, 4));
178 TEST_ASSERT_EQ(hash_sdbm(padded, 4), hash_sdbm(clean, 4));
179 TEST_ASSERT_EQ(hash_fnv1a(padded, 4), hash_fnv1a(clean, 4));
180 TEST_ASSERT_EQ(hash_jenkins_one_at_a_time(padded, 4),
181 hash_jenkins_one_at_a_time(clean, 4));
182 TEST_ASSERT_EQ(hash_elf(padded, 4), hash_elf(clean, 4));
183 TEST_ASSERT_EQ(hash_bkdr(padded, 4), hash_bkdr(clean, 4));
184 TEST_ASSERT_EQ(hash_murmur3_32(padded, 4, 0), hash_murmur3_32(clean, 4, 0));
185
186 for (size_t n = 1; n <= 8; n++) {
187 TEST_ASSERT_NE(hash_djb2(padded, n), hash_djb2(padded, n - 1));
188 TEST_ASSERT_NE(hash_fnv1a(padded, n), hash_fnv1a(padded, n - 1));
189 }
190
191 return TEST_SUCCESS;
192}
193
194/* hash_elf masks off the top bit */
195TEST_DECLARE_UNIT(hash, elf_stays_31_bit) {
196 uint8_t buf[16];
197 for (size_t i = 0; i < sizeof(buf); i++)
198 buf[i] = 0xFF;
199
200 for (size_t n = 0; n <= sizeof(buf); n++)
201 TEST_ASSERT_EQ((hash_elf(buf, n) & 0x80000000U), 0);
202
203 return TEST_SUCCESS;
204}
205