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