Home | History | Annotate | Line # | Download | only in nbperf
      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
     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
    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
    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
    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