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