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
76struct state {
77	struct SIZED(graph) graph;
78	uint32_t *g;
79	uint8_t *visited;
80};
81
82#if GRAPH_SIZE == 3
83static void
84assign_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
119static void
120assign_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
146static void
147print_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
225int
226#if GRAPH_SIZE == 3
227chm3_compute(struct nbperf *nbperf)
228#else
229chm_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
288failed:
289	SIZED2(_free)(&state.graph);
290	free(state.g);
291	free(state.visited);
292	return retval;
293}
294