150479Speter/* $NetBSD: nbperf-bdz.c,v 1.12 2023/07/31 21:07:50 andvar Exp $ */ 22656Srgrimes/*- 32656Srgrimes * Copyright (c) 2009, 2012 The NetBSD Foundation, Inc. 4124033Simp * All rights reserved. 5124033Simp * 6124033Simp * This code is derived from software contributed to The NetBSD Foundation 7260127Sgjb * by Joerg Sonnenberger. 8124033Simp * 9124033Simp * Redistribution and use in source and binary forms, with or without 10124033Simp * modification, are permitted provided that the following conditions 11124033Simp * are met: 12124033Simp * 13124033Simp * 1. Redistributions of source code must retain the above copyright 14124033Simp * notice, this list of conditions and the following disclaimer. 15124033Simp * 2. Redistributions in binary form must reproduce the above copyright 16124033Simp * notice, this list of conditions and the following disclaimer in 17124033Simp * the documentation and/or other materials provided with the 18185403Simp * distribution. 19124033Simp * 20124033Simp * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21185403Simp * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22124033Simp * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 23124033Simp * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 24124033Simp * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 25124033Simp * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 26124033Simp * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 27124033Simp * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 28124033Simp * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 29124033Simp * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 30124033Simp * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31124033Simp * SUCH DAMAGE. 32124033Simp */ 332656Srgrimes 342656Srgrimes#if HAVE_NBTOOL_CONFIG_H 352656Srgrimes#include "nbtool_config.h" 362656Srgrimes#endif 372656Srgrimes 382656Srgrimes#include <sys/cdefs.h> 392656Srgrimes__RCSID("$NetBSD: nbperf-bdz.c,v 1.12 2023/07/31 21:07:50 andvar Exp $"); 402656Srgrimes 412656Srgrimes#include <err.h> 422656Srgrimes#include <inttypes.h> 432656Srgrimes#include <stdlib.h> 442656Srgrimes#include <stdio.h> 452656Srgrimes#include <string.h> 462656Srgrimes 472656Srgrimes#include "nbperf.h" 482656Srgrimes 492656Srgrimes/* 502656Srgrimes * A full description of the algorithm can be found in: 512656Srgrimes * "Simple and Space-Efficient Minimal Perfect Hash Functions" 522656Srgrimes * by Botelho, Pagh and Ziviani, proceedings of WADS 2007. 532656Srgrimes */ 542656Srgrimes 552656Srgrimes/* 562656Srgrimes * The algorithm is based on random, acyclic 3-graphs. 572656Srgrimes * 582656Srgrimes * Each edge in the represents a key. The vertices are the reminder of 592656Srgrimes * the hash function mod n. n = cm with c > 1.23. This ensures that 602656Srgrimes * an acyclic graph can be found with a very high probality. 612656Srgrimes * 622656Srgrimes * An acyclic graph has an edge order, where at least one vertex of 632656Srgrimes * each edge hasn't been seen before. It is declares the first unvisited 642656Srgrimes * vertex as authoritive for the edge and assigns a 2bit value to unvisited 652656Srgrimes * vertices, so that the sum of all vertices of the edge modulo 4 is 662656Srgrimes * the index of the authoritive vertex. 672656Srgrimes */ 682656Srgrimes 692656Srgrimes#define GRAPH_SIZE 3 702656Srgrimes#include "graph2.h" 712656Srgrimes 722656Srgrimesstruct state { 732656Srgrimes struct SIZED(graph) graph; 742656Srgrimes uint32_t *visited; 752656Srgrimes uint32_t *holes64k; 762656Srgrimes uint16_t *holes64; 772656Srgrimes uint8_t *g; 782656Srgrimes uint32_t *result_map; 792656Srgrimes}; 802656Srgrimes 812656Srgrimesstatic void 822656Srgrimesassign_nodes(struct state *state) 832656Srgrimes{ 842656Srgrimes struct SIZED(edge) *e; 852656Srgrimes size_t i, j; 862656Srgrimes uint32_t t, r, holes; 872656Srgrimes 882656Srgrimes for (i = 0; i < state->graph.v; ++i) 892656Srgrimes state->g[i] = 3; 902656Srgrimes 912656Srgrimes for (i = 0; i < state->graph.e; ++i) { 922656Srgrimes j = state->graph.output_order[i]; 932656Srgrimes e = &state->graph.edges[j]; 942656Srgrimes if (!state->visited[e->vertices[0]]) { 9550978Sobrien r = 0; 9650978Sobrien t = e->vertices[0]; 9750978Sobrien } else if (!state->visited[e->vertices[1]]) { 9850978Sobrien r = 1; 9950978Sobrien t = e->vertices[1]; 10050978Sobrien } else { 10150978Sobrien if (state->visited[e->vertices[2]]) 10250978Sobrien abort(); 10350978Sobrien r = 2; 10450978Sobrien t = e->vertices[2]; 10550978Sobrien } 10650978Sobrien 10750978Sobrien state->visited[t] = 2 + j; 10850978Sobrien if (state->visited[e->vertices[0]] == 0) 10950978Sobrien state->visited[e->vertices[0]] = 1; 11050978Sobrien if (state->visited[e->vertices[1]] == 0) 11150978Sobrien state->visited[e->vertices[1]] = 1; 11250978Sobrien if (state->visited[e->vertices[2]] == 0) 11350978Sobrien state->visited[e->vertices[2]] = 1; 11450978Sobrien 11550978Sobrien state->g[t] = (9 + r - state->g[e->vertices[0]] - state->g[e->vertices[1]] 11650978Sobrien - state->g[e->vertices[2]]) % 3; 11750978Sobrien } 11850978Sobrien 11950978Sobrien holes = 0; 12050978Sobrien for (i = 0; i < state->graph.v; ++i) { 12150978Sobrien if (i % 65536 == 0) 12250978Sobrien state->holes64k[i >> 16] = holes; 12350978Sobrien 12450978Sobrien if (i % 64 == 0) 12550978Sobrien state->holes64[i >> 6] = holes - state->holes64k[i >> 16]; 12650978Sobrien 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