1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* util/support/t_hash.c - tests for hash table code */
3 /*
4 * Copyright (C) 2018 by the Massachusetts Institute of Technology.
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 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * * Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
24 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
26 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
28 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
30 * OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 /* hash.c has no linker dependencies, so we can simply include its source code
34 * to test its static functions and look inside its structures. */
35 #include "hashtab.c"
36
37 /* These match the sip64 test vectors in the reference C implementation of
38 * siphash at https://github.com/veorq/SipHash */
39 const uint64_t vectors[64] = {
40 0x726FDB47DD0E0E31,
41 0x74F839C593DC67FD,
42 0x0D6C8009D9A94F5A,
43 0x85676696D7FB7E2D,
44 0xCF2794E0277187B7,
45 0x18765564CD99A68D,
46 0xCBC9466E58FEE3CE,
47 0xAB0200F58B01D137,
48 0x93F5F5799A932462,
49 0x9E0082DF0BA9E4B0,
50 0x7A5DBBC594DDB9F3,
51 0xF4B32F46226BADA7,
52 0x751E8FBC860EE5FB,
53 0x14EA5627C0843D90,
54 0xF723CA908E7AF2EE,
55 0xA129CA6149BE45E5,
56 0x3F2ACC7F57C29BDB,
57 0x699AE9F52CBE4794,
58 0x4BC1B3F0968DD39C,
59 0xBB6DC91DA77961BD,
60 0xBED65CF21AA2EE98,
61 0xD0F2CBB02E3B67C7,
62 0x93536795E3A33E88,
63 0xA80C038CCD5CCEC8,
64 0xB8AD50C6F649AF94,
65 0xBCE192DE8A85B8EA,
66 0x17D835B85BBB15F3,
67 0x2F2E6163076BCFAD,
68 0xDE4DAAACA71DC9A5,
69 0xA6A2506687956571,
70 0xAD87A3535C49EF28,
71 0x32D892FAD841C342,
72 0x7127512F72F27CCE,
73 0xA7F32346F95978E3,
74 0x12E0B01ABB051238,
75 0x15E034D40FA197AE,
76 0x314DFFBE0815A3B4,
77 0x027990F029623981,
78 0xCADCD4E59EF40C4D,
79 0x9ABFD8766A33735C,
80 0x0E3EA96B5304A7D0,
81 0xAD0C42D6FC585992,
82 0x187306C89BC215A9,
83 0xD4A60ABCF3792B95,
84 0xF935451DE4F21DF2,
85 0xA9538F0419755787,
86 0xDB9ACDDFF56CA510,
87 0xD06C98CD5C0975EB,
88 0xE612A3CB9ECBA951,
89 0xC766E62CFCADAF96,
90 0xEE64435A9752FE72,
91 0xA192D576B245165A,
92 0x0A8787BF8ECB74B2,
93 0x81B3E73D20B49B6F,
94 0x7FA8220BA3B2ECEA,
95 0x245731C13CA42499,
96 0xB78DBFAF3A8D83BD,
97 0xEA1AD565322A1A0B,
98 0x60E61C23A3795013,
99 0x6606D7E446282B93,
100 0x6CA4ECB15C5F91E1,
101 0x9F626DA15C9625F3,
102 0xE51B38608EF25F57,
103 0x958A324CEB064572
104 };
105
106 static void
test_siphash()107 test_siphash()
108 {
109 uint8_t seq[64];
110 uint64_t k0, k1, hval;
111 size_t i;
112
113 for (i = 0; i < sizeof(seq); i++)
114 seq[i] = i;
115 k0 = load_64_le(seq);
116 k1 = load_64_le(seq + 8);
117
118 for (i = 0; i < sizeof(seq); i++) {
119 hval = siphash24(seq, i, k0, k1);
120 assert(hval == vectors[i]);
121 }
122 }
123
124 static void
test_hashtab()125 test_hashtab()
126 {
127 int st;
128 struct k5_hashtab *ht;
129 size_t i;
130 char zeros[100] = { 0 };
131
132 st = k5_hashtab_create(NULL, 4, &ht);
133 assert(st == 0 && ht != NULL && ht->nentries == 0);
134
135 st = k5_hashtab_add(ht, "abc", 3, &st);
136 assert(st == 0 && ht->nentries == 1);
137 assert(k5_hashtab_get(ht, "abc", 3) == &st);
138 assert(k5_hashtab_get(ht, "bcde", 4) == NULL);
139
140 st = k5_hashtab_add(ht, "bcde", 4, &ht);
141 assert(st == 0 && ht->nentries == 2);
142 assert(k5_hashtab_get(ht, "abc", 3) == &st);
143 assert(k5_hashtab_get(ht, "bcde", 4) == &ht);
144
145 k5_hashtab_remove(ht, "abc", 3);
146 assert(ht->nentries == 1);
147 assert(k5_hashtab_get(ht, "abc", 3) == NULL);
148 assert(k5_hashtab_get(ht, "bcde", 4) == &ht);
149
150 k5_hashtab_remove(ht, "bcde", 4);
151 assert(ht->nentries == 0);
152 assert(k5_hashtab_get(ht, "abc", 3) == NULL);
153 assert(k5_hashtab_get(ht, "bcde", 4) == NULL);
154
155 for (i = 0; i < sizeof(zeros); i++) {
156 st = k5_hashtab_add(ht, zeros, i, zeros + i);
157 assert(st == 0 && ht->nentries == i + 1 && ht->nbuckets >= i + 1);
158 }
159 for (i = 0; i < sizeof(zeros); i++) {
160 assert(k5_hashtab_get(ht, zeros, i) == zeros + i);
161 k5_hashtab_remove(ht, zeros, i);
162 assert(ht->nentries == sizeof(zeros) - i - 1);
163 if (i > 0)
164 assert(k5_hashtab_get(ht, zeros, i - 1) == NULL);
165 }
166
167 k5_hashtab_free(ht);
168 }
169
170 int
main()171 main()
172 {
173 test_siphash();
174 test_hashtab();
175 return 0;
176 }
177