1/*	$NetBSD: nbperf-bdz.c,v 1.12 2023/07/31 21:07:50 andvar Exp $	*/
2/*-
3 * Copyright (c) 2009, 2012 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
34#if HAVE_NBTOOL_CONFIG_H
35#include "nbtool_config.h"
36#endif
37
38#include <sys/cdefs.h>
39__RCSID("$NetBSD: nbperf-bdz.c,v 1.12 2023/07/31 21:07:50 andvar Exp $");
40
41#include <err.h>
42#include <inttypes.h>
43#include <stdlib.h>
44#include <stdio.h>
45#include <string.h>
46
47#include "nbperf.h"
48
49/*
50 * A full description of the algorithm can be found in:
51 * "Simple and Space-Efficient Minimal Perfect Hash Functions"
52 * by Botelho, Pagh and Ziviani, proceedings of WADS 2007.
53 */
54
55/*
56 * The algorithm is based on random, acyclic 3-graphs.
57 *
58 * Each edge in the represents a key.  The vertices are the reminder of
59 * the hash function mod n.  n = cm with c > 1.23.  This ensures that
60 * an acyclic graph can be found with a very high probality.
61 *
62 * An acyclic graph has an edge order, where at least one vertex of
63 * each edge hasn't been seen before.   It is declares the first unvisited
64 * vertex as authoritive for the edge and assigns a 2bit value to unvisited
65 * vertices, so that the sum of all vertices of the edge modulo 4 is
66 * the index of the authoritive vertex.
67 */
68
69#define GRAPH_SIZE 3
70#include "graph2.h"
71
72struct state {
73	struct SIZED(graph) graph;
74	uint32_t *visited;
75	uint32_t *holes64k;
76	uint16_t *holes64;
77	uint8_t *g;
78	uint32_t *result_map;
79};
80
81static void
82assign_nodes(struct state *state)
83{
84	struct SIZED(edge) *e;
85	size_t i, j;
86	uint32_t t, r, holes;
87
88	for (i = 0; i < state->graph.v; ++i)
89		state->g[i] = 3;
90
91	for (i = 0; i < state->graph.e; ++i) {
92		j = state->graph.output_order[i];
93		e = &state->graph.edges[j];
94		if (!state->visited[e->vertices[0]]) {
95			r = 0;
96			t = e->vertices[0];
97		} else if (!state->visited[e->vertices[1]]) {
98			r = 1;
99			t = e->vertices[1];
100		} else {
101			if (state->visited[e->vertices[2]])
102				abort();
103			r = 2;
104			t = e->vertices[2];
105		}
106
107		state->visited[t] = 2 + j;
108		if (state->visited[e->vertices[0]] == 0)
109			state->visited[e->vertices[0]] = 1;
110		if (state->visited[e->vertices[1]] == 0)
111			state->visited[e->vertices[1]] = 1;
112		if (state->visited[e->vertices[2]] == 0)
113			state->visited[e->vertices[2]] = 1;
114
115		state->g[t] = (9 + r - state->g[e->vertices[0]] - state->g[e->vertices[1]]
116		    - state->g[e->vertices[2]]) % 3;
117	}
118
119	holes = 0;
120	for (i = 0; i < state->graph.v; ++i) {
121		if (i % 65536 == 0)
122			state->holes64k[i >> 16] = holes;
123
124		if (i % 64 == 0)
125			state->holes64[i >> 6] = holes - state->holes64k[i >> 16];
126
127		if (state->visited[i] > 1) {
128			j = state->visited[i] - 2;
129			state->result_map[j] = i - holes;
130		}
131
132		if (state->g[i] == 3)
133			++holes;
134	}
135}
136
137static void
138print_hash(struct nbperf *nbperf, struct state *state)
139{
140	uint64_t sum;
141	size_t i;
142
143	fprintf(nbperf->output, "#include <stdlib.h>\n");
144	fprintf(nbperf->output, "#include <strings.h>\n\n");
145
146	fprintf(nbperf->output, "%suint32_t\n",
147	    nbperf->static_hash ? "static " : "");
148	fprintf(nbperf->output,
149	    "%s(const void * __restrict key, size_t keylen)\n",
150	    nbperf->hash_name);
151	fprintf(nbperf->output, "{\n");
152
153	fprintf(nbperf->output,
154	    "\tstatic const uint64_t g1[%" PRId32 "] = {\n",
155	    (state->graph.v + 63) / 64);
156	sum = 0;
157	for (i = 0; i < state->graph.v; ++i) {
158		sum |= ((uint64_t)state->g[i] & 1) << (i & 63);
159		if (i % 64 == 63) {
160			fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s",
161			    (i / 64 % 2 == 0 ? "\t    " : " "),
162			    sum,
163			    (i / 64 % 2 == 1 ? "\n" : ""));
164			sum = 0;
165		}
166	}
167	if (i % 64 != 0) {
168		fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s",
169		    (i / 64 % 2 == 0 ? "\t    " : " "),
170		    sum,
171		    (i / 64 % 2 == 1 ? "\n" : ""));
172	}
173	fprintf(nbperf->output, "%s\t};\n", (i % 2 ? "\n" : ""));
174
175	fprintf(nbperf->output,
176	    "\tstatic const uint64_t g2[%" PRId32 "] = {\n",
177	    (state->graph.v + 63) / 64);
178	sum = 0;
179	for (i = 0; i < state->graph.v; ++i) {
180		sum |= (((uint64_t)state->g[i] & 2) >> 1) << (i & 63);
181		if (i % 64 == 63) {
182			fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s",
183			    (i / 64 % 2 == 0 ? "\t    " : " "),
184			    sum,
185			    (i / 64 % 2 == 1 ? "\n" : ""));
186			sum = 0;
187		}
188	}
189	if (i % 64 != 0) {
190		fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s",
191		    (i / 64 % 2 == 0 ? "\t    " : " "),
192		    sum,
193		    (i / 64 % 2 == 1 ? "\n" : ""));
194	}
195	fprintf(nbperf->output, "%s\t};\n", (i % 2 ? "\n" : ""));
196
197	fprintf(nbperf->output,
198	    "\tstatic const uint32_t holes64k[%" PRId32 "] = {\n",
199	    (state->graph.v + 65535) / 65536);
200	for (i = 0; i < state->graph.v; i += 65536)
201		fprintf(nbperf->output, "%s0x%08" PRIx32 ",%s",
202		    (i / 65536 % 4 == 0 ? "\t    " : " "),
203		    state->holes64k[i >> 16],
204		    (i / 65536 % 4 == 3 ? "\n" : ""));
205	fprintf(nbperf->output, "%s\t};\n", (i / 65536 % 4 ? "\n" : ""));
206
207	fprintf(nbperf->output,
208	    "\tstatic const uint16_t holes64[%" PRId32 "] = {\n",
209	    (state->graph.v + 63) / 64);
210	for (i = 0; i < state->graph.v; i += 64)
211		fprintf(nbperf->output, "%s0x%04" PRIx32 ",%s",
212		    (i / 64 % 4 == 0 ? "\t    " : " "),
213		    state->holes64[i >> 6],
214		    (i / 64 % 4 == 3 ? "\n" : ""));
215	fprintf(nbperf->output, "%s\t};\n", (i / 64 % 4 ? "\n" : ""));
216
217	fprintf(nbperf->output, "\tuint64_t m;\n");
218	fprintf(nbperf->output, "\tuint32_t idx, i, idx2;\n");
219	fprintf(nbperf->output, "\tuint32_t h[%zu];\n\n", nbperf->hash_size);
220
221	(*nbperf->print_hash)(nbperf, "\t", "key", "keylen", "h");
222
223	fprintf(nbperf->output, "\n\th[0] = h[0] %% %" PRIu32 ";\n",
224	    state->graph.v);
225	fprintf(nbperf->output, "\th[1] = h[1] %% %" PRIu32 ";\n",
226	    state->graph.v);
227	fprintf(nbperf->output, "\th[2] = h[2] %% %" PRIu32 ";\n",
228	    state->graph.v);
229
230	if (state->graph.hash_fudge & 1)
231		fprintf(nbperf->output, "\th[1] ^= (h[0] == h[1]);\n");
232
233	if (state->graph.hash_fudge & 2) {
234		fprintf(nbperf->output,
235		    "\th[2] ^= (h[0] == h[2] || h[1] == h[2]);\n");
236		fprintf(nbperf->output,
237		    "\th[2] ^= 2 * (h[0] == h[2] || h[1] == h[2]);\n");
238	}
239
240	fprintf(nbperf->output,
241	    "\tidx = 9 + ((g1[h[0] >> 6] >> (h[0] & 63)) &1)\n"
242	    "\t      + ((g1[h[1] >> 6] >> (h[1] & 63)) & 1)\n"
243	    "\t      + ((g1[h[2] >> 6] >> (h[2] & 63)) & 1)\n"
244	    "\t      - ((g2[h[0] >> 6] >> (h[0] & 63)) & 1)\n"
245	    "\t      - ((g2[h[1] >> 6] >> (h[1] & 63)) & 1)\n"
246	    "\t      - ((g2[h[2] >> 6] >> (h[2] & 63)) & 1);\n"
247	    );
248
249	fprintf(nbperf->output,
250	    "\tidx = h[idx %% 3];\n");
251	fprintf(nbperf->output,
252	    "\tidx2 = idx - holes64[idx >> 6] - holes64k[idx >> 16];\n"
253	    "\tidx2 -= popcount64(g1[idx >> 6] & g2[idx >> 6]\n"
254	    "\t                   & (((uint64_t)1 << (idx & 63)) - 1));\n"
255	    "\treturn idx2;\n");
256
257	fprintf(nbperf->output, "}\n");
258
259	if (nbperf->map_output != NULL) {
260		for (i = 0; i < state->graph.e; ++i)
261			fprintf(nbperf->map_output, "%" PRIu32 "\n",
262			    state->result_map[i]);
263	}
264}
265
266int
267bpz_compute(struct nbperf *nbperf)
268{
269	struct state state;
270	int retval = -1;
271	uint32_t v, e;
272
273	if (nbperf->c == 0)
274		nbperf->c = 1.24;
275	if (nbperf->c < 1.24)
276		errx(1, "The argument for option -c must be at least 1.24");
277	if (nbperf->hash_size < 3)
278		errx(1, "The hash function must generate at least 3 values");
279
280	(*nbperf->seed_hash)(nbperf);
281	e = nbperf->n;
282	v = nbperf->c * nbperf->n;
283	if (1.24 * nbperf->n > v)
284		++v;
285	if (v < 10)
286		v = 10;
287	if (nbperf->allow_hash_fudging)
288		v = (v + 3) & ~3;
289
290	graph3_setup(&state.graph, v, e);
291
292	state.holes64k = calloc(sizeof(uint32_t), (v + 65535) / 65536);
293	state.holes64 = calloc(sizeof(uint16_t), (v + 63) / 64 );
294	state.g = calloc(sizeof(uint32_t), v | 63);
295	state.visited = calloc(sizeof(uint32_t), v);
296	state.result_map = calloc(sizeof(uint32_t), e);
297
298	if (state.holes64k == NULL || state.holes64 == NULL ||
299	    state.g == NULL || state.visited == NULL ||
300	    state.result_map == NULL)
301		err(1, "malloc failed");
302
303	if (SIZED2(_hash)(nbperf, &state.graph))
304		goto failed;
305	if (SIZED2(_output_order)(&state.graph))
306		goto failed;
307	assign_nodes(&state);
308	print_hash(nbperf, &state);
309
310	retval = 0;
311
312failed:
313	SIZED2(_free)(&state.graph);
314	free(state.visited);
315	free(state.g);
316	free(state.holes64k);
317	free(state.holes64);
318	free(state.result_map);
319	return retval;
320}
321