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