1 /* $NetBSD: nbperf-bdz.c,v 1.9 2014/04/30 21:04:58 joerg 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.9 2014/04/30 21:04:58 joerg 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, proceeedings 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 #include "graph3.h" 70 71 struct state { 72 struct graph3 graph; 73 uint32_t *visited; 74 uint32_t *holes64k; 75 uint16_t *holes64; 76 uint8_t *g; 77 uint32_t *result_map; 78 }; 79 80 static void 81 assign_nodes(struct state *state) 82 { 83 struct edge3 *e; 84 size_t i, j; 85 uint32_t t, r, holes; 86 87 for (i = 0; i < state->graph.v; ++i) 88 state->g[i] = 3; 89 90 for (i = 0; i < state->graph.e; ++i) { 91 j = state->graph.output_order[i]; 92 e = &state->graph.edges[j]; 93 if (!state->visited[e->left]) { 94 r = 0; 95 t = e->left; 96 } else if (!state->visited[e->middle]) { 97 r = 1; 98 t = e->middle; 99 } else { 100 if (state->visited[e->right]) 101 abort(); 102 r = 2; 103 t = e->right; 104 } 105 106 state->visited[t] = 2 + j; 107 if (state->visited[e->left] == 0) 108 state->visited[e->left] = 1; 109 if (state->visited[e->middle] == 0) 110 state->visited[e->middle] = 1; 111 if (state->visited[e->right] == 0) 112 state->visited[e->right] = 1; 113 114 state->g[t] = (9 + r - state->g[e->left] - state->g[e->middle] 115 - state->g[e->right]) % 3; 116 } 117 118 holes = 0; 119 for (i = 0; i < state->graph.v; ++i) { 120 if (i % 65536 == 0) 121 state->holes64k[i >> 16] = holes; 122 123 if (i % 64 == 0) 124 state->holes64[i >> 6] = holes - state->holes64k[i >> 16]; 125 126 if (state->visited[i] > 1) { 127 j = state->visited[i] - 2; 128 state->result_map[j] = i - holes; 129 } 130 131 if (state->g[i] == 3) 132 ++holes; 133 } 134 } 135 136 static void 137 print_hash(struct nbperf *nbperf, struct state *state) 138 { 139 uint64_t sum; 140 size_t i; 141 142 fprintf(nbperf->output, "#include <stdlib.h>\n"); 143 fprintf(nbperf->output, "#include <strings.h>\n\n"); 144 145 fprintf(nbperf->output, "%suint32_t\n", 146 nbperf->static_hash ? "static " : ""); 147 fprintf(nbperf->output, 148 "%s(const void * __restrict key, size_t keylen)\n", 149 nbperf->hash_name); 150 fprintf(nbperf->output, "{\n"); 151 152 fprintf(nbperf->output, 153 "\tstatic const uint64_t g1[%" PRId32 "] = {\n", 154 (state->graph.v + 63) / 64); 155 sum = 0; 156 for (i = 0; i < state->graph.v; ++i) { 157 sum |= ((uint64_t)state->g[i] & 1) << (i & 63); 158 if (i % 64 == 63) { 159 fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s", 160 (i / 64 % 2 == 0 ? "\t " : " "), 161 sum, 162 (i / 64 % 2 == 1 ? "\n" : "")); 163 sum = 0; 164 } 165 } 166 if (i % 64 != 0) { 167 fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s", 168 (i / 64 % 2 == 0 ? "\t " : " "), 169 sum, 170 (i / 64 % 2 == 1 ? "\n" : "")); 171 } 172 fprintf(nbperf->output, "%s\t};\n", (i % 2 ? "\n" : "")); 173 174 fprintf(nbperf->output, 175 "\tstatic const uint64_t g2[%" PRId32 "] = {\n", 176 (state->graph.v + 63) / 64); 177 sum = 0; 178 for (i = 0; i < state->graph.v; ++i) { 179 sum |= (((uint64_t)state->g[i] & 2) >> 1) << (i & 63); 180 if (i % 64 == 63) { 181 fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s", 182 (i / 64 % 2 == 0 ? "\t " : " "), 183 sum, 184 (i / 64 % 2 == 1 ? "\n" : "")); 185 sum = 0; 186 } 187 } 188 if (i % 64 != 0) { 189 fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s", 190 (i / 64 % 2 == 0 ? "\t " : " "), 191 sum, 192 (i / 64 % 2 == 1 ? "\n" : "")); 193 } 194 fprintf(nbperf->output, "%s\t};\n", (i % 2 ? "\n" : "")); 195 196 fprintf(nbperf->output, 197 "\tstatic const uint32_t holes64k[%" PRId32 "] = {\n", 198 (state->graph.v + 65535) / 65536); 199 for (i = 0; i < state->graph.v; i += 65536) 200 fprintf(nbperf->output, "%s0x%08" PRIx32 ",%s", 201 (i / 65536 % 4 == 0 ? "\t " : " "), 202 state->holes64k[i >> 16], 203 (i / 65536 % 4 == 3 ? "\n" : "")); 204 fprintf(nbperf->output, "%s\t};\n", (i / 65536 % 4 ? "\n" : "")); 205 206 fprintf(nbperf->output, 207 "\tstatic const uint16_t holes64[%" PRId32 "] = {\n", 208 (state->graph.v + 63) / 64); 209 for (i = 0; i < state->graph.v; i += 64) 210 fprintf(nbperf->output, "%s0x%04" PRIx32 ",%s", 211 (i / 64 % 4 == 0 ? "\t " : " "), 212 state->holes64[i >> 6], 213 (i / 64 % 4 == 3 ? "\n" : "")); 214 fprintf(nbperf->output, "%s\t};\n", (i / 64 % 4 ? "\n" : "")); 215 216 fprintf(nbperf->output, "\tuint64_t m;\n"); 217 fprintf(nbperf->output, "\tuint32_t idx, i, idx2;\n"); 218 fprintf(nbperf->output, "\tuint32_t h[%zu];\n\n", nbperf->hash_size); 219 220 (*nbperf->print_hash)(nbperf, "\t", "key", "keylen", "h"); 221 222 fprintf(nbperf->output, "\n\th[0] = h[0] %% %" PRIu32 ";\n", 223 state->graph.v); 224 fprintf(nbperf->output, "\th[1] = h[1] %% %" PRIu32 ";\n", 225 state->graph.v); 226 fprintf(nbperf->output, "\th[2] = h[2] %% %" PRIu32 ";\n", 227 state->graph.v); 228 229 fprintf(nbperf->output, 230 "\tidx = 9 + ((g1[h[0] >> 6] >> (h[0] & 63)) &1)\n" 231 "\t + ((g1[h[1] >> 6] >> (h[1] & 63)) & 1)\n" 232 "\t + ((g1[h[2] >> 6] >> (h[2] & 63)) & 1)\n" 233 "\t - ((g2[h[0] >> 6] >> (h[0] & 63)) & 1)\n" 234 "\t - ((g2[h[1] >> 6] >> (h[1] & 63)) & 1)\n" 235 "\t - ((g2[h[2] >> 6] >> (h[2] & 63)) & 1);\n" 236 ); 237 238 fprintf(nbperf->output, 239 "\tidx = h[idx %% 3];\n"); 240 fprintf(nbperf->output, 241 "\tidx2 = idx - holes64[idx >> 6] - holes64k[idx >> 16];\n" 242 "\tidx2 -= popcount64(g1[idx >> 6] & g2[idx >> 6]\n" 243 "\t & (((uint64_t)1 << (idx & 63)) - 1));\n" 244 "\treturn idx2;\n"); 245 246 fprintf(nbperf->output, "}\n"); 247 248 if (nbperf->map_output != NULL) { 249 for (i = 0; i < state->graph.e; ++i) 250 fprintf(nbperf->map_output, "%" PRIu32 "\n", 251 state->result_map[i]); 252 } 253 } 254 255 int 256 bpz_compute(struct nbperf *nbperf) 257 { 258 struct state state; 259 int retval = -1; 260 uint32_t v, e; 261 262 if (nbperf->c == 0) 263 nbperf->c = 1.24; 264 if (nbperf->c < 1.24) 265 errx(1, "The argument for option -c must be at least 1.24"); 266 if (nbperf->hash_size < 3) 267 errx(1, "The hash function must generate at least 3 values"); 268 269 (*nbperf->seed_hash)(nbperf); 270 e = nbperf->n; 271 v = nbperf->c * nbperf->n; 272 if (1.24 * nbperf->n > v) 273 ++v; 274 if (v < 10) 275 v = 10; 276 277 graph3_setup(&state.graph, v, e); 278 279 state.holes64k = calloc(sizeof(uint32_t), (v + 65535) / 65536); 280 state.holes64 = calloc(sizeof(uint16_t), (v + 63) / 64 ); 281 state.g = calloc(sizeof(uint32_t), v | 63); 282 state.visited = calloc(sizeof(uint32_t), v); 283 state.result_map = calloc(sizeof(uint32_t), e); 284 285 if (state.holes64k == NULL || state.holes64 == NULL || 286 state.g == NULL || state.visited == NULL || 287 state.result_map == NULL) 288 err(1, "malloc failed"); 289 290 if (graph3_hash(nbperf, &state.graph)) 291 goto failed; 292 if (graph3_output_order(&state.graph)) 293 goto failed; 294 assign_nodes(&state); 295 print_hash(nbperf, &state); 296 297 retval = 0; 298 299 failed: 300 graph3_free(&state.graph); 301 free(state.visited); 302 free(state.g); 303 free(state.holes64k); 304 free(state.holes64); 305 free(state.result_map); 306 return retval; 307 } 308