180021Sjasone/* $NetBSD: nbperf-chm.c,v 1.2 2009/08/24 17:12:46 joerg Exp $ */ 280021Sjasone/*- 380021Sjasone * Copyright (c) 2009 The NetBSD Foundation, Inc. 480021Sjasone * All rights reserved. 580021Sjasone * 680021Sjasone * This code is derived from software contributed to The NetBSD Foundation 780021Sjasone * by Joerg Sonnenberger. 880021Sjasone * 980021Sjasone * Redistribution and use in source and binary forms, with or without 1080021Sjasone * modification, are permitted provided that the following conditions 1180021Sjasone * are met: 1280021Sjasone * 1380021Sjasone * 1. Redistributions of source code must retain the above copyright 1480021Sjasone * notice, this list of conditions and the following disclaimer. 1580021Sjasone * 2. Redistributions in binary form must reproduce the above copyright 1680021Sjasone * notice, this list of conditions and the following disclaimer in 1780021Sjasone * the documentation and/or other materials provided with the 1880021Sjasone * distribution. 1980021Sjasone * 2080021Sjasone * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2180021Sjasone * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2280021Sjasone * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 2380021Sjasone * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 2480021Sjasone * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 2580021Sjasone * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 2680021Sjasone * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 2780021Sjasone * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 2880021Sjasone * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 2980021Sjasone * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 3080021Sjasone * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3180021Sjasone * SUCH DAMAGE. 3280021Sjasone */ 3380021Sjasone#if HAVE_NBTOOL_CONFIG_H 34103388Smini#include "nbtool_config.h" 3580021Sjasone#endif 3680021Sjasone 3780021Sjasone#include <sys/cdefs.h> 3880021Sjasone__RCSID("$NetBSD: nbperf-chm.c,v 1.2 2009/08/24 17:12:46 joerg Exp $"); 3980021Sjasone 4080021Sjasone#include <err.h> 4180021Sjasone#include <inttypes.h> 4280021Sjasone#include <stdlib.h> 4380021Sjasone#include <stdio.h> 4480021Sjasone#include <string.h> 45113658Sdeischen 46113658Sdeischen#include "nbperf.h" 47113658Sdeischen 4880021Sjasone#ifdef BUILD_CHM3 49113658Sdeischen#include "graph3.h" 5080021Sjasone#else 5180021Sjasone#include "graph2.h" 5280021Sjasone#endif 53113658Sdeischen 54113658Sdeischen/* 55113658Sdeischen * A full description of the algorithm can be found in: 56113658Sdeischen * "An optimal algorithm for generating minimal perfect hash functions" 5780021Sjasone * by Czech, Havas and Majewski in Information Processing Letters, 58113658Sdeischen * 43(5):256-264, October 1992. 5980021Sjasone */ 6080021Sjasone 61113658Sdeischen/* 62113658Sdeischen * The algorithm is based on random, acyclic graphs. 63113658Sdeischen * 64136190Sdavidxu * Each edge in the represents a key. The vertices are the reminder of 65113658Sdeischen * the hash function mod n. n = cm with c > 2, otherwise the propability 66113658Sdeischen * of finding an acyclic graph is very low (for 2-graphs). The constant 67113658Sdeischen * for 3-graphs is 1.24. 68113658Sdeischen * 69113658Sdeischen * After the hashing phase, the graph is checked for cycles. 70113658Sdeischen * A cycle-free graph is either empty or has a vertex of degree 1. 7180021Sjasone * Removing the edge for this vertex doesn't change this property, 7280021Sjasone * so applying this recursively reduces the size of the graph. 7380021Sjasone * If the graph is empty at the end of the process, it was acyclic. 7480021Sjasone * 7580021Sjasone * The assignment step now sets g[i] := 0 and processes the edges 7680021Sjasone * in reverse order of removal. That ensures that at least one vertex 7780021Sjasone * is always unvisited and can be assigned. 7880021Sjasone */ 7980021Sjasone 8080021Sjasonestruct state { 8180021Sjasone#ifdef BUILD_CHM3 8280021Sjasone struct graph3 graph; 8380021Sjasone#else 8480021Sjasone struct graph2 graph; 8580021Sjasone#endif 8680021Sjasone uint32_t *g; 8780021Sjasone uint8_t *visited; 8880021Sjasone}; 8980021Sjasone 9080021Sjasonestatic void 9180021Sjasoneassign_nodes(struct state *state) 9280021Sjasone{ 9380021Sjasone#ifdef BUILD_CHM3 9480021Sjasone struct edge3 *e; 9580021Sjasone#else 9680021Sjasone struct edge2 *e; 9780021Sjasone#endif 9880021Sjasone size_t i; 9980021Sjasone uint32_t e_idx; 10080021Sjasone 10180021Sjasone for (i = 0; i < state->graph.e; ++i) { 10280021Sjasone e_idx = state->graph.output_order[i]; 10380021Sjasone e = &state->graph.edges[e_idx]; 10480021Sjasone 10580021Sjasone#ifdef BUILD_CHM3 10680021Sjasone if (!state->visited[e->left]) { 10780021Sjasone state->g[e->left] = (2 * state->graph.e + e_idx 10880021Sjasone - state->g[e->middle] - state->g[e->right]) 10980021Sjasone % state->graph.e; 11080021Sjasone } else if (!state->visited[e->middle]) { 11180021Sjasone state->g[e->middle] = (2 * state->graph.e + e_idx 11280021Sjasone - state->g[e->left] - state->g[e->right]) 11380021Sjasone % state->graph.e; 114113658Sdeischen } else { 11580021Sjasone state->g[e->right] = (2 * state->graph.e + e_idx 116120072Sdavidxu - state->g[e->left] - state->g[e->middle]) 117120072Sdavidxu % state->graph.e; 118120072Sdavidxu } 119120072Sdavidxu state->visited[e->left] = 1; 120120072Sdavidxu state->visited[e->middle] = 1; 121120072Sdavidxu state->visited[e->right] = 1; 122120072Sdavidxu#else 123120072Sdavidxu if (!state->visited[e->left]) { 124120072Sdavidxu state->g[e->left] = (state->graph.e + e_idx 125120072Sdavidxu - state->g[e->right]) % state->graph.e; 126120072Sdavidxu } else { 127120072Sdavidxu state->g[e->right] = (state->graph.e + e_idx 128120072Sdavidxu - state->g[e->left]) % state->graph.e; 129113658Sdeischen } 130113658Sdeischen state->visited[e->left] = 1; 13180021Sjasone state->visited[e->right] = 1; 132113658Sdeischen#endif 133113658Sdeischen } 134113658Sdeischen} 135113658Sdeischen 136113658Sdeischenstatic void 137136190Sdavidxuprint_hash(struct nbperf *nbperf, struct state *state) 13880021Sjasone{ 13980021Sjasone uint32_t i, per_line; 140113658Sdeischen const char *g_type; 141113658Sdeischen int g_width; 142113658Sdeischen 143113658Sdeischen fprintf(nbperf->output, "#include <stdlib.h>\n\n"); 144113658Sdeischen 14580021Sjasone fprintf(nbperf->output, "%suint32_t\n", 146120072Sdavidxu nbperf->static_hash ? "static " : ""); 147120072Sdavidxu fprintf(nbperf->output, 148120072Sdavidxu "%s(const void * __restrict key, size_t keylen)\n", 149113658Sdeischen nbperf->hash_name); 150113658Sdeischen fprintf(nbperf->output, "{\n"); 15180021Sjasone if (state->graph.v >= 65536) { 15280021Sjasone g_type = "uint32_t"; 153113658Sdeischen g_width = 8; 154113658Sdeischen per_line = 4; 155113658Sdeischen } else if (state->graph.v >= 256) { 156113658Sdeischen g_type = "uint16_t"; 157113658Sdeischen g_width = 4; 158113658Sdeischen per_line = 8; 159113658Sdeischen } else { 16080021Sjasone g_type = "uint8_t"; 16180021Sjasone g_width = 2; 16280021Sjasone per_line = 10; 163113658Sdeischen } 164113658Sdeischen fprintf(nbperf->output, "\tstatic const %s g[%" PRId32 "] = {\n", 165113658Sdeischen g_type, state->graph.v); 166113658Sdeischen for (i = 0; i < state->graph.v; ++i) { 16780021Sjasone fprintf(nbperf->output, "%s0x%0*" PRIx32 ",%s", 168113658Sdeischen (i % per_line == 0 ? "\t " : " "), 16980021Sjasone g_width, state->g[i], 17080021Sjasone (i % per_line == per_line - 1 ? "\n" : "")); 17180021Sjasone } 17280021Sjasone if (i % per_line != 0) 17380021Sjasone fprintf(nbperf->output, "\n\t};\n"); 17480021Sjasone else 17580021Sjasone fprintf(nbperf->output, "\t};\n"); 17680021Sjasone fprintf(nbperf->output, "\tuint32_t h[%zu];\n\n", nbperf->hash_size); 177113658Sdeischen (*nbperf->print_hash)(nbperf, "\t", "key", "keylen", "h"); 178113658Sdeischen#ifdef BUILD_CHM3 17980021Sjasone fprintf(nbperf->output, "\treturn (g[h[0] %% %" PRIu32 "] + " 18080021Sjasone "g[h[1] %% %" PRIu32 "] + " 181113658Sdeischen "g[h[2] %% %" PRIu32"]) %% %" PRIu32 ";\n", 18280021Sjasone state->graph.v, state->graph.v, state->graph.v, state->graph.e); 18380021Sjasone#else 18480021Sjasone fprintf(nbperf->output, "\treturn (g[h[0] %% %" PRIu32 "] + " 18580021Sjasone "g[h[1] %% %" PRIu32"]) %% %" PRIu32 ";\n", 186113658Sdeischen state->graph.v, state->graph.v, state->graph.e); 187113658Sdeischen#endif 188113658Sdeischen fprintf(nbperf->output, "}\n"); 189113658Sdeischen 190113658Sdeischen if (nbperf->map_output != NULL) { 191113658Sdeischen for (i = 0; i < state->graph.e; ++i) 192113658Sdeischen fprintf(nbperf->map_output, "%" PRIu32 "\n", i); 19385567Speter } 194113658Sdeischen} 195113658Sdeischen 19685567Speterint 19780021Sjasone#ifdef BUILD_CHM3 198136190Sdavidxuchm3_compute(struct nbperf *nbperf) 19980021Sjasone#else 20080021Sjasonechm_compute(struct nbperf *nbperf) 201113658Sdeischen#endif 202113658Sdeischen{ 20380021Sjasone struct state state; 204113658Sdeischen int retval = -1; 205113658Sdeischen uint32_t v, e; 20680021Sjasone 207113658Sdeischen#ifdef BUILD_CHM3 20880021Sjasone if (nbperf->c == 0) 209113658Sdeischen nbperf-> c = 1.24; 210113658Sdeischen 211113658Sdeischen if (nbperf->c < 1.24) 212113658Sdeischen errx(1, "The argument for option -c must be at least 1.24"); 213136190Sdavidxu 214136190Sdavidxu if (nbperf->hash_size < 3) 215136190Sdavidxu errx(1, "The hash function must generate at least 3 values"); 216136190Sdavidxu#else 217136190Sdavidxu if (nbperf->c == 0) 218136190Sdavidxu nbperf-> c = 2; 219136190Sdavidxu 220136190Sdavidxu if (nbperf->c < 2) 221136190Sdavidxu errx(1, "The argument for option -c must be at least 2"); 222136190Sdavidxu 223136190Sdavidxu if (nbperf->hash_size < 2) 224136190Sdavidxu errx(1, "The hash function must generate at least 2 values"); 225136190Sdavidxu#endif 226136190Sdavidxu 22780021Sjasone (*nbperf->seed_hash)(nbperf); 228113658Sdeischen e = nbperf->n; 229113658Sdeischen v = nbperf->c * nbperf->n; 230113658Sdeischen#ifdef BUILD_CHM3 231113658Sdeischen if (v == 1.24 * nbperf->n) 23280021Sjasone ++v; 23380021Sjasone if (v < 10) 234113658Sdeischen v = 10; 23580021Sjasone#else 236113658Sdeischen if (v == 2 * nbperf->n) 23780021Sjasone ++v; 238113658Sdeischen#endif 23980021Sjasone 240113658Sdeischen state.g = calloc(sizeof(uint32_t), v); 241113658Sdeischen state.visited = calloc(sizeof(uint8_t), v); 242113658Sdeischen if (state.g == NULL || state.visited == NULL) 243113658Sdeischen err(1, "malloc failed"); 244120072Sdavidxu 245120072Sdavidxu#ifdef BUILD_CHM3 246113658Sdeischen graph3_setup(&state.graph, v, e); 24780021Sjasone if (graph3_hash(nbperf, &state.graph)) 248113658Sdeischen goto failed; 249113658Sdeischen if (graph3_output_order(&state.graph)) 250113658Sdeischen goto failed; 251113658Sdeischen#else 252113658Sdeischen graph2_setup(&state.graph, v, e); 253113658Sdeischen if (graph2_hash(nbperf, &state.graph)) 254113658Sdeischen goto failed; 255113658Sdeischen if (graph2_output_order(&state.graph)) 256113658Sdeischen goto failed; 25780021Sjasone#endif 25880021Sjasone assign_nodes(&state); 259 print_hash(nbperf, &state); 260 261 retval = 0; 262 263failed: 264#ifdef BUILD_CHM3 265 graph3_free(&state.graph); 266#else 267 graph2_free(&state.graph); 268#endif 269 free(state.g); 270 free(state.visited); 271 return retval; 272} 273