?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
t40c term[] count fix
[minix.git] / usr.bin / nbperf / nbperf-bdz.c
blob726c180c35c1224ce902b4ef8785892414adc3d6
1 /* $NetBSD: nbperf-bdz.c,v 1.5 2012/09/25 20:53:46 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.5 2012/09/25 20:53:46 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)"
231 "\t + ((g1[h[1] >> 6] >> (h[1] & 63)) & 1)"
232 "\t + ((g1[h[2] >> 6] >> (h[2] & 63)) & 1)"
233 "\t - ((g2[h[0] >> 6] >> (h[0] & 63)) & 1)"
234 "\t - ((g2[h[1] >> 6] >> (h[1] & 63)) & 1)"
235 "\t - ((g2[h[2] >> 6] >> (h[2] & 63)) & 1);"
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) - 1));\n"
244 "\treturn idx2;");
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 bdz_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 }
MINIX 3 (repo.or.cz mirror)