1 /* PackTab - Pack a static table
2 * Copyright (C) 2001 Behdad Esfahbod.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this library; if not, see <http://www.gnu.org/licenses/>.
16 *
17 * For licensing issues, contact <fwpg@sharif.edu>.
18 */
19
20 /*
21 8 <= N <= 2^21
22 int key
23 1 <= max_depth <= 21
24 */
25
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "packtab.h"
31
32 typedef signed int uni_table[1024 * 1024 * 2];
33 static int n, a, max_depth, digits, tab_width, per_row;
34 static long N;
35 signed int def_key;
36 static uni_table temp, x, perm, *tab;
37 static long pow[22], cluster, cmpcluster;
38 static const char *const *name, *key_type_name, *table_name, *macro_name;
39 static FILE *f;
40
41 static long
42 most_binary (
43 long min,
44 long max
45 )
46 {
47 /* min should be less than max */
48 register int i, ii;
49
50 if (min == max)
51 return max;
52
53 for (i = 21; max < pow[i]; i--)
54 ;
55 ii = i;
56 while (i && !((min ^ max) & pow[i]))
57 i--;
58
59 if (ii == i)
60 {
61 /* min is less than half of max */
62 for (i = 21 - 1; min < pow[i]; i--)
63 ;
64 i++;
65 return pow[i];
66 }
67
68 return max & (pow[i] - 1);
69 }
70
71 static void
72 init (
73 const signed int *table
74 )
75 {
76 register int i;
77
78 /* initialize powers of two */
79 pow[0] = 1;
80 for (i = 1; i <= 21; i++)
81 pow[i] = pow[i - 1] << 1;
82
83 /* reduce number of elements to get a more binary number */
84 {
85 long essen;
86
87 /* find number of essential items */
88 essen = N - 1;
89 while (essen && table[essen] == def_key)
90 essen--;
91 essen++;
92
93 N = most_binary (essen, N);
94 }
95
96 for (n = 21; N % pow[n]; n--)
97 ;
98 digits = (n + 3) / 4;
99 for (i = 6; i; i--)
100 if (pow[i] * (tab_width + 1) < 80)
101 break;
102 per_row = pow[i];
103 }
104
105 static int
106 compare (
107 const void *r,
108 const void *s
109 )
110 {
111 int i;
112 for (i = 0; i < cmpcluster; i++)
113 if (((int *) r)[i] != ((int *) s)[i])
114 return ((int *) r)[i] - ((int *) s)[i];
115 return 0;
116 }
117
118 static int lev, best_lev, p[22], best_p[22], nn;
119 static long c[22], best_c[22], s, best_s;
120 static long t[22], best_t[22], clusters[22], best_cluster[22];
121
122 static void
123 found (
124 void
125 )
126 {
127 int i;
128
129 if (s < best_s)
130 {
131 best_s = s;
132 best_lev = lev;
133 for (i = 0; i <= lev; i++)
134 {
135 best_p[i] = p[i];
136 best_c[i] = c[i];
137 best_t[i] = t[i];
138 best_cluster[i] = clusters[i];
139 }
140 }
141 }
142
143 static void
144 bt (
145 int node_size
146 )
147 {
148 long i, j, k, y, sbak;
149 long key_bytes;
150
151 if (t[lev] == 1)
152 {
153 found ();
154 return;
155 }
156 if (lev == max_depth)
157 return;
158
159 for (i = 1 - t[lev] % 2; i <= nn + (t[lev] >> nn) % 2; i++)
160 {
161 nn -= (p[lev] = i);
162 clusters[lev] = cluster = (i && nn >= 0) ? pow[i] : t[lev];
163 cmpcluster = cluster + 1;
164
165 t[lev + 1] = (t[lev] - 1) / cluster + 1;
166 for (j = 0; j < t[lev + 1]; j++)
167 {
168 memmove (temp + j * cmpcluster, tab[lev] + j * cluster,
169 cluster * sizeof (tab[lev][0]));
170 temp[j * cmpcluster + cluster] = j;
171 }
172 qsort (temp, t[lev + 1], cmpcluster * sizeof (temp[0]), compare);
173 for (j = 0; j < t[lev + 1]; j++)
174 {
175 perm[j] = temp[j * cmpcluster + cluster];
176 temp[j * cmpcluster + cluster] = 0;
177 }
178 k = 1;
179 y = 0;
180 tab[lev + 1][perm[0]] = perm[0];
181 for (j = 1; j < t[lev + 1]; j++)
182 {
183 if (compare (temp + y, temp + y + cmpcluster))
184 {
185 k++;
186 tab[lev + 1][perm[j]] = perm[j];
187 }
188 else
189 tab[lev + 1][perm[j]] = tab[lev + 1][perm[j - 1]];
190 y += cmpcluster;
191 }
192 sbak = s;
193 s += k * node_size * cluster;
194 c[lev] = k;
195
196 if (s >= best_s)
197 {
198 s = sbak;
199 nn += i;
200 return;
201 }
202
203 key_bytes = k * cluster;
204 key_bytes = key_bytes < 0xff ? 1 : key_bytes < 0xffff ? 2 : 4;
205 lev++;
206 bt (key_bytes);
207 lev--;
208
209 s = sbak;
210 nn += i;
211 }
212 }
213
214 static void
215 solve (
216 void
217 )
218 {
219 best_lev = max_depth + 2;
220 best_s = N * a * 2;
221 lev = 0;
222 s = 0;
223 nn = n;
224 t[0] = N;
225 bt (a);
226 }
227
228 static void
229 write_array (
230 long max_key
231 )
232 {
233 int i, j, k, y, ii, ofs;
234 const char *key_type;
235
236 if (best_t[lev] == 1)
237 return;
238
239 nn -= (i = best_p[lev]);
240 cluster = best_cluster[lev];
241 cmpcluster = cluster + 1;
242
243 t[lev + 1] = best_t[lev + 1];
244 for (j = 0; j < t[lev + 1]; j++)
245 {
246 memmove (temp + j * cmpcluster, tab[lev] + j * cluster,
247 cluster * sizeof (tab[lev][0]));
248 temp[j * cmpcluster + cluster] = j;
249 }
250 qsort (temp, t[lev + 1], cmpcluster * sizeof (temp[0]), compare);
251 for (j = 0; j < t[lev + 1]; j++)
252 {
253 perm[j] = temp[j * cmpcluster + cluster];
254 temp[j * cmpcluster + cluster] = 0;
255 }
256 k = 1;
257 y = 0;
258 tab[lev + 1][perm[0]] = x[0] = perm[0];
259 for (j = 1; j < t[lev + 1]; j++)
260 {
261 if (compare (temp + y, temp + y + cmpcluster))
262 {
263 x[k] = perm[j];
264 tab[lev + 1][perm[j]] = x[k];
265 k++;
266 }
267 else
268 tab[lev + 1][perm[j]] = tab[lev + 1][perm[j - 1]];
269 y += cmpcluster;
270 }
271
272 i = 0;
273 for (ii = 1; ii < k; ii++)
274 if (x[ii] < x[i])
275 i = ii;
276
277 key_type = !lev ? key_type_name :
278 max_key <= 0xff ? "PACKTAB_UINT8" :
279 max_key <= 0xffff ? "PACKTAB_UINT16" : "PACKTAB_UINT32";
280 fprintf (f, "static const %s %sLev%d[%ld*%d] = {", key_type, table_name,
281 best_lev - lev - 1, cluster, k);
282 ofs = 0;
283 for (ii = 0; ii < k; ii++)
284 {
285 int kk, jj;
286 fprintf (f, "\n#define %sLev%d_%0*lX 0x%0X", table_name,
287 best_lev - lev - 1, digits, x[i] * pow[n - nn], ofs);
288 kk = x[i] * cluster;
289 if (!lev)
290 if (name)
291 for (j = 0; j < cluster; j++)
292 {
293 if (!(j % per_row) && j != cluster - 1)
294 fprintf (f, "\n ");
295 fprintf (f, "%*s,", tab_width, name[tab[lev][kk++]]);
296 }
297 else
298 for (j = 0; j < cluster; j++)
299 {
300 if (!(j % per_row) && j != cluster - 1)
301 fprintf (f, "\n ");
302 fprintf (f, "%*d,", tab_width, tab[lev][kk++]);
303 }
304 else
305 for (j = 0; j < cluster; j++, kk++)
306 fprintf (f, "\n %sLev%d_%0*lX, /* %0*lX..%0*lX */", table_name,
307 best_lev - lev, digits,
308 tab[lev][kk] * pow[n - nn - best_p[lev]], digits,
309 x[i] * pow[n - nn] + j * pow[n - nn - best_p[lev]], digits,
310 x[i] * pow[n - nn] + (j + 1) * pow[n - nn - best_p[lev]] -
311 1);
312 ofs += cluster;
313 jj = i;
314 for (j = 0; j < k; j++)
315 if (x[j] > x[i] && (x[j] < x[jj] || jj == i))
316 jj = j;
317 i = jj;
318 }
319 fprintf (f, "\n};\n\n");
320 lev++;
321 write_array (cluster * k);
322 lev--;
323 }
324
325 static void
326 write_source (
327 void
328 )
329 {
330 int i, j;
331
332 lev = 0;
333 s = 0;
334 nn = n;
335 t[0] = N;
336 fprintf (f, "\n" "/* *IND" "ENT-OFF* */\n\n");
337 write_array (0);
338 fprintf (f, "/* *IND" "ENT-ON* */\n\n");
339
340 fprintf (f, "#define %s(x) \\\n", macro_name);
341 fprintf (f, "\t((x) >= 0x%lx ? ", N);
342 if (name)
343 fprintf (f, "%s", name[def_key]);
344 else
345 fprintf (f, "%d", def_key);
346 fprintf (f, " : ");
347 j = 0;
348 for (i = best_lev - 1; i >= 0; i--)
349 {
350 fprintf (f, " \\\n\t%sLev%d[((x)", table_name, i);
351 if (j != 0)
352 fprintf (f, " >> %d", j);
353 if (i)
354 fprintf (f, " & 0x%02lx) +", pow[best_p[best_lev - 1 - i]] - 1);
355 j += best_p[best_lev - 1 - i];
356 }
357 fprintf (f, ")");
358 for (i = 0; i < best_lev; i++)
359 fprintf (f, "]");
360 fprintf (f, ")\n\n");
361 }
362
363 static void
364 write_out (
365 void
366 )
367 {
368 int i;
369 fprintf (f, "/*\n"
370 " generated by packtab.c version %d\n\n"
371 " use %s(key) to access your table\n\n"
372 " assumed sizeof(%s): %d\n"
373 " required memory: %ld\n"
374 " lookups: %d\n"
375 " partition shape: %s",
376 packtab_version, macro_name, key_type_name, a, best_s, best_lev,
377 table_name);
378 for (i = best_lev - 1; i >= 0; i--)
379 fprintf (f, "[%ld]", best_cluster[i]);
380 fprintf (f, "\n" " different table entries:");
381 for (i = best_lev - 1; i >= 0; i--)
382 fprintf (f, " %ld", best_c[i]);
383 fprintf (f, "\n*/\n");
384 write_source ();
385 }
386
387 int
388 pack_table (
389 const signed int *base,
390 long key_num,
391 int key_size,
392 signed int default_key,
393 int p_max_depth,
394 int p_tab_width,
395 const char *const *p_name,
396 const char *p_key_type_name,
397 const char *p_table_name,
398 const char *p_macro_name,
399 FILE *out
400 )
401 {
402 N = key_num;
403 a = key_size;
404 def_key = default_key;
405 max_depth = p_max_depth;
406 tab_width = p_tab_width;
407 name = p_name;
408 key_type_name = p_key_type_name;
409 table_name = p_table_name;
410 macro_name = p_macro_name;
411 f = out;
412 init (base);
413 if (!(tab = malloc ((n + 1) * sizeof (tab[0]))))
414 return 0;
415 memmove (tab[0], base, N * sizeof (base[0]));
416 solve ();
417 write_out ();
418 free (tab);
419 return 1;
420 }
421
422 /* End of packtab.c */