nbperf-chm.c revision 1.1
1 /* $NetBSD: nbperf-chm.c,v 1.1 2009/08/15 16:21:05 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 34 #include <sys/cdefs.h> 35 __RCSID("$NetBSD: nbperf-chm.c,v 1.1 2009/08/15 16:21:05 joerg Exp $"); 36 37 #include <err.h> 38 #include <inttypes.h> 39 #include <stdlib.h> 40 #include <stdio.h> 41 #include <string.h> 42 43 #include "nbperf.h" 44 45 #ifdef BUILD_CHM3 46 #include "graph3.h" 47 #else 48 #include "graph2.h" 49 #endif 50 51 /* 52 * A full description of the algorithm can be found in: 53 * "An optimal algorithm for generating minimal perfect hash functions" 54 * by Czech, Havas and Majewski in Information Processing Letters, 55 * 43(5):256-264, October 1992. 56 */ 57 58 /* 59 * The algorithm is based on random, acyclic graphs. 60 * 61 * Each edge in the represents a key. The vertices are the reminder of 62 * the hash function mod n. n = cm with c > 2, otherwise the propability 63 * of finding an acyclic graph is very low (for 2-graphs). The constant 64 * for 3-graphs is 1.24. 65 * 66 * After the hashing phase, the graph is checked for cycles. 67 * A cycle-free graph is either empty or has a vertex of degree 1. 68 * Removing the edge for this vertex doesn't change this property, 69 * so applying this recursively reduces the size of the graph. 70 * If the graph is empty at the end of the process, it was acyclic. 71 * 72 * The assignment step now sets g[i] := 0 and processes the edges 73 * in reverse order of removal. That ensures that at least one vertex 74 * is always unvisited and can be assigned. 75 */ 76 77 struct state { 78 #ifdef BUILD_CHM3 79 struct graph3 graph; 80 #else 81 struct graph2 graph; 82 #endif 83 uint32_t *g; 84 uint8_t *visited; 85 }; 86 87 static void 88 assign_nodes(struct state *state) 89 { 90 #ifdef BUILD_CHM3 91 struct edge3 *e; 92 #else 93 struct edge2 *e; 94 #endif 95 size_t i; 96 uint32_t e_idx; 97 98 for (i = 0; i < state->graph.e; ++i) { 99 e_idx = state->graph.output_order[i]; 100 e = &state->graph.edges[e_idx]; 101 102 #ifdef BUILD_CHM3 103 if (!state->visited[e->left]) { 104 state->g[e->left] = (2 * state->graph.e + e_idx 105 - state->g[e->middle] - state->g[e->right]) 106 % state->graph.e; 107 } else if (!state->visited[e->middle]) { 108 state->g[e->middle] = (2 * state->graph.e + e_idx 109 - state->g[e->left] - state->g[e->right]) 110 % state->graph.e; 111 } else { 112 state->g[e->right] = (2 * state->graph.e + e_idx 113 - state->g[e->left] - state->g[e->middle]) 114 % state->graph.e; 115 } 116 state->visited[e->left] = 1; 117 state->visited[e->middle] = 1; 118 state->visited[e->right] = 1; 119 #else 120 if (!state->visited[e->left]) { 121 state->g[e->left] = (state->graph.e + e_idx 122 - state->g[e->right]) % state->graph.e; 123 } else { 124 state->g[e->right] = (state->graph.e + e_idx 125 - state->g[e->left]) % state->graph.e; 126 } 127 state->visited[e->left] = 1; 128 state->visited[e->right] = 1; 129 #endif 130 } 131 } 132 133 static void 134 print_hash(struct nbperf *nbperf, struct state *state) 135 { 136 uint32_t i; 137 const char *g_type; 138 139 fprintf(nbperf->output, "#include <stdlib.h>\n\n"); 140 141 fprintf(nbperf->output, "%suint32_t\n", 142 nbperf->static_hash ? "static " : ""); 143 fprintf(nbperf->output, 144 "%s(const void * __restrict key, size_t keylen)\n", 145 nbperf->hash_name); 146 fprintf(nbperf->output, "{\n"); 147 if (state->graph.v >= 65536) 148 g_type = "uint32_t"; 149 else if (state->graph.v >= 256) 150 g_type = "uint16_t"; 151 else 152 g_type = "uint8_t"; 153 fprintf(nbperf->output, "\tstatic const %s g[%" PRId32 "] = {\n", 154 g_type, state->graph.v); 155 for (i = 0; i < state->graph.v; ++i) { 156 fprintf(nbperf->output, "%s0x%08" PRIx32 ",%s", 157 (i % 4 == 0 ? "\t " : " "), 158 state->g[i], 159 (i % 4 == 3 ? "\n" : "")); 160 } 161 if (i / 16 % 4 == 3) 162 fprintf(nbperf->output, "\n\t};\n"); 163 else 164 fprintf(nbperf->output, "\t};\n"); 165 fprintf(nbperf->output, "\tuint32_t h[%zu];\n\n", nbperf->hash_size); 166 (*nbperf->print_hash)(nbperf, "\t", "key", "keylen", "h"); 167 #ifdef BUILD_CHM3 168 fprintf(nbperf->output, "\treturn (g[h[0] %% %" PRIu32 "] + " 169 "g[h[1] %% %" PRIu32 "] + " 170 "g[h[2] %% %" PRIu32"]) %% %" PRIu32 ";\n", 171 state->graph.v, state->graph.v, state->graph.v, state->graph.e); 172 #else 173 fprintf(nbperf->output, "\treturn (g[h[0] %% %" PRIu32 "] + " 174 "g[h[1] %% %" PRIu32"]) %% %" PRIu32 ";\n", 175 state->graph.v, state->graph.v, state->graph.e); 176 #endif 177 fprintf(nbperf->output, "}\n"); 178 179 if (nbperf->map_output != NULL) { 180 for (i = 0; i < state->graph.e; ++i) 181 fprintf(nbperf->map_output, "%" PRIu32 "\n", i); 182 } 183 } 184 185 int 186 #ifdef BUILD_CHM3 187 chm3_compute(struct nbperf *nbperf) 188 #else 189 chm_compute(struct nbperf *nbperf) 190 #endif 191 { 192 struct state state; 193 int retval = -1; 194 uint32_t v, e; 195 196 #ifdef BUILD_CHM3 197 if (nbperf->c == 0) 198 nbperf-> c = 1.24; 199 200 if (nbperf->c < 1.24) 201 errx(1, "The argument for option -c must be at least 1.24"); 202 203 if (nbperf->hash_size < 3) 204 errx(1, "The hash function must generate at least 3 values"); 205 #else 206 if (nbperf->c == 0) 207 nbperf-> c = 2; 208 209 if (nbperf->c < 2) 210 errx(1, "The argument for option -c must be at least 2"); 211 212 if (nbperf->hash_size < 2) 213 errx(1, "The hash function must generate at least 2 values"); 214 #endif 215 216 (*nbperf->seed_hash)(nbperf); 217 e = nbperf->n; 218 v = nbperf->c * nbperf->n; 219 #ifdef BUILD_CHM3 220 if (v == 1.24 * nbperf->n) 221 ++v; 222 if (v < 10) 223 v = 10; 224 #else 225 if (v == 2 * nbperf->n) 226 ++v; 227 #endif 228 229 state.g = calloc(sizeof(uint32_t), v); 230 state.visited = calloc(sizeof(uint8_t), v); 231 if (state.g == NULL || state.visited == NULL) 232 err(1, "malloc failed"); 233 234 #ifdef BUILD_CHM3 235 graph3_setup(&state.graph, v, e); 236 if (graph3_hash(nbperf, &state.graph)) 237 goto failed; 238 if (graph3_output_order(&state.graph)) 239 goto failed; 240 #else 241 graph2_setup(&state.graph, v, e); 242 if (graph2_hash(nbperf, &state.graph)) 243 goto failed; 244 if (graph2_output_order(&state.graph)) 245 goto failed; 246 #endif 247 assign_nodes(&state); 248 print_hash(nbperf, &state); 249 250 retval = 0; 251 252 failed: 253 #ifdef BUILD_CHM3 254 graph3_free(&state.graph); 255 #else 256 graph2_free(&state.graph); 257 #endif 258 free(state.g); 259 free(state.visited); 260 return retval; 261 } 262
Indexes created Wed Sep 24 05:09:52 GMT 2025