Home | History | Annotate | Line # | Download | only in nbperf 
      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 
     72 struct 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 
     81 static void
     82 assign_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 
    137 static void
    138 print_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 
    266 int
    267 bpz_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 
    312 failed:
    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