1 /* $NetBSD: nbperf-chm.c,v 1.5 2021/01/26 21:25:55 joerg Exp $ */
2 /*-
3 * Copyright (c) 2009 The NetBSD Foundation, Inc.
4 * All rights reserved.
5 *
6 * This code is derived from software contributed to The NetBSD Foundation
7 * by Joerg Sonnenberger.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
30 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33 #if HAVE_NBTOOL_CONFIG_H
34 #include "nbtool_config.h"
35 #endif
36
37 #include <sys/cdefs.h>
38 __RCSID("$NetBSD: nbperf-chm.c,v 1.5 2021/01/26 21:25:55 joerg Exp $");
39
40 #include <err.h>
41 #include <inttypes.h>
42 #include <stdlib.h>
43 #include <stdio.h>
44 #include <string.h>
45
46 #include "nbperf.h"
47
48 #include "graph2.h"
49
50 /*
51 * A full description of the algorithm can be found in:
52 * "An optimal algorithm for generating minimal perfect hash functions"
53 * by Czech, Havas and Majewski in Information Processing Letters,
54 * 43(5):256-264, October 1992.
55 */
56
57 /*
58 * The algorithm is based on random, acyclic graphs.
59 *
60 * Each edge in the represents a key. The vertices are the reminder of
61 * the hash function mod n. n = cm with c > 2, otherwise the propability
62 * of finding an acyclic graph is very low (for 2-graphs). The constant
63 * for 3-graphs is 1.24.
64 *
65 * After the hashing phase, the graph is checked for cycles.
66 * A cycle-free graph is either empty or has a vertex of degree 1.
67 * Removing the edge for this vertex doesn't change this property,
68 * so applying this recursively reduces the size of the graph.
69 * If the graph is empty at the end of the process, it was acyclic.
70 *
71 * The assignment step now sets g[i] := 0 and processes the edges
72 * in reverse order of removal. That ensures that at least one vertex
73 * is always unvisited and can be assigned.
74 */
75
76 struct state {
77 struct SIZED(graph) graph;
78 uint32_t *g;
79 uint8_t *visited;
80 };
81
82 #if GRAPH_SIZE == 3
83 static void
assign_nodes(struct state * state)84 assign_nodes(struct state *state)
85 {
86 struct SIZED(edge) *e;
87 size_t i;
88 uint32_t e_idx, v0, v1, v2, g;
89
90 for (i = 0; i < state->graph.e; ++i) {
91 e_idx = state->graph.output_order[i];
92 e = &state->graph.edges[e_idx];
93 if (!state->visited[e->vertices[0]]) {
94 v0 = e->vertices[0];
95 v1 = e->vertices[1];
96 v2 = e->vertices[2];
97 } else if (!state->visited[e->vertices[1]]) {
98 v0 = e->vertices[1];
99 v1 = e->vertices[0];
100 v2 = e->vertices[2];
101 } else {
102 v0 = e->vertices[2];
103 v1 = e->vertices[0];
104 v2 = e->vertices[1];
105 }
106 g = e_idx - state->g[v1] - state->g[v2];
107 if (g >= state->graph.e) {
108 g += state->graph.e;
109 if (g >= state->graph.e)
110 g += state->graph.e;
111 }
112 state->g[v0] = g;
113 state->visited[v0] = 1;
114 state->visited[v1] = 1;
115 state->visited[v2] = 1;
116 }
117 }
118 #else
119 static void
assign_nodes(struct state * state)120 assign_nodes(struct state *state)
121 {
122 struct SIZED(edge) *e;
123 size_t i;
124 uint32_t e_idx, v0, v1, g;
125
126 for (i = 0; i < state->graph.e; ++i) {
127 e_idx = state->graph.output_order[i];
128 e = &state->graph.edges[e_idx];
129 if (!state->visited[e->vertices[0]]) {
130 v0 = e->vertices[0];
131 v1 = e->vertices[1];
132 } else {
133 v0 = e->vertices[1];
134 v1 = e->vertices[0];
135 }
136 g = e_idx - state->g[v1];
137 if (g >= state->graph.e)
138 g += state->graph.e;
139 state->g[v0] = g;
140 state->visited[v0] = 1;
141 state->visited[v1] = 1;
142 }
143 }
144 #endif
145
146 static void
print_hash(struct nbperf * nbperf,struct state * state)147 print_hash(struct nbperf *nbperf, struct state *state)
148 {
149 uint32_t i, per_line;
150 const char *g_type;
151 int g_width;
152
153 fprintf(nbperf->output, "#include <stdlib.h>\n\n");
154
155 fprintf(nbperf->output, "%suint32_t\n",
156 nbperf->static_hash ? "static " : "");
157 fprintf(nbperf->output,
158 "%s(const void * __restrict key, size_t keylen)\n",
159 nbperf->hash_name);
160 fprintf(nbperf->output, "{\n");
161 if (state->graph.v >= 65536) {
162 g_type = "uint32_t";
163 g_width = 8;
164 per_line = 4;
165 } else if (state->graph.v >= 256) {
166 g_type = "uint16_t";
167 g_width = 4;
168 per_line = 8;
169 } else {
170 g_type = "uint8_t";
171 g_width = 2;
172 per_line = 10;
173 }
174 fprintf(nbperf->output, "\tstatic const %s g[%" PRId32 "] = {\n",
175 g_type, state->graph.v);
176 for (i = 0; i < state->graph.v; ++i) {
177 fprintf(nbperf->output, "%s0x%0*" PRIx32 ",%s",
178 (i % per_line == 0 ? "\t " : " "),
179 g_width, state->g[i],
180 (i % per_line == per_line - 1 ? "\n" : ""));
181 }
182 if (i % per_line != 0)
183 fprintf(nbperf->output, "\n\t};\n");
184 else
185 fprintf(nbperf->output, "\t};\n");
186 fprintf(nbperf->output, "\tuint32_t h[%zu];\n\n", nbperf->hash_size);
187 (*nbperf->print_hash)(nbperf, "\t", "key", "keylen", "h");
188
189 fprintf(nbperf->output, "\n\th[0] = h[0] %% %" PRIu32 ";\n",
190 state->graph.v);
191 fprintf(nbperf->output, "\th[1] = h[1] %% %" PRIu32 ";\n",
192 state->graph.v);
193 #if GRAPH_SIZE == 3
194 fprintf(nbperf->output, "\th[2] = h[2] %% %" PRIu32 ";\n",
195 state->graph.v);
196 #endif
197
198 if (state->graph.hash_fudge & 1)
199 fprintf(nbperf->output, "\th[1] ^= (h[0] == h[1]);\n");
200
201 #if GRAPH_SIZE == 3
202 if (state->graph.hash_fudge & 2) {
203 fprintf(nbperf->output,
204 "\th[2] ^= (h[0] == h[2] || h[1] == h[2]);\n");
205 fprintf(nbperf->output,
206 "\th[2] ^= 2 * (h[0] == h[2] || h[1] == h[2]);\n");
207 }
208 #endif
209
210 #if GRAPH_SIZE == 3
211 fprintf(nbperf->output, "\treturn (g[h[0]] + g[h[1]] + g[h[2]]) %% "
212 "%" PRIu32 ";\n", state->graph.e);
213 #else
214 fprintf(nbperf->output, "\treturn (g[h[0]] + g[h[1]]) %% "
215 "%" PRIu32 ";\n", state->graph.e);
216 #endif
217 fprintf(nbperf->output, "}\n");
218
219 if (nbperf->map_output != NULL) {
220 for (i = 0; i < state->graph.e; ++i)
221 fprintf(nbperf->map_output, "%" PRIu32 "\n", i);
222 }
223 }
224
225 int
226 #if GRAPH_SIZE == 3
chm3_compute(struct nbperf * nbperf)227 chm3_compute(struct nbperf *nbperf)
228 #else
229 chm_compute(struct nbperf *nbperf)
230 #endif
231 {
232 struct state state;
233 int retval = -1;
234 uint32_t v, e;
235
236 #if GRAPH_SIZE == 3
237 if (nbperf->c == 0)
238 nbperf-> c = 1.24;
239
240 if (nbperf->c < 1.24)
241 errx(1, "The argument for option -c must be at least 1.24");
242
243 if (nbperf->hash_size < 3)
244 errx(1, "The hash function must generate at least 3 values");
245 #else
246 if (nbperf->c == 0)
247 nbperf-> c = 2;
248
249 if (nbperf->c < 2)
250 errx(1, "The argument for option -c must be at least 2");
251
252 if (nbperf->hash_size < 2)
253 errx(1, "The hash function must generate at least 2 values");
254 #endif
255
256 (*nbperf->seed_hash)(nbperf);
257 e = nbperf->n;
258 v = nbperf->c * nbperf->n;
259 #if GRAPH_SIZE == 3
260 if (v == 1.24 * nbperf->n)
261 ++v;
262 if (v < 10)
263 v = 10;
264 if (nbperf->allow_hash_fudging)
265 v = (v + 3) & ~3;
266 #else
267 if (v == 2 * nbperf->n)
268 ++v;
269 if (nbperf->allow_hash_fudging)
270 v = (v + 1) & ~1;
271 #endif
272
273 state.g = calloc(sizeof(uint32_t), v);
274 state.visited = calloc(sizeof(uint8_t), v);
275 if (state.g == NULL || state.visited == NULL)
276 err(1, "malloc failed");
277
278 SIZED2(_setup)(&state.graph, v, e);
279 if (SIZED2(_hash)(nbperf, &state.graph))
280 goto failed;
281 if (SIZED2(_output_order)(&state.graph))
282 goto failed;
283 assign_nodes(&state);
284 print_hash(nbperf, &state);
285
286 retval = 0;
287
288 failed:
289 SIZED2(_free)(&state.graph);
290 free(state.g);
291 free(state.visited);
292 return retval;
293 }
294