1 /* PackTab - Pack a static table
2 * Copyright (C) 2001 Behdad Esfahbod.
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.
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.
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/>.
17 * For licensing issues, contact <fwpg@sharif.edu>.
32 typedef signed int uni_table[1024 * 1024 * 2];
33 static int n, a, max_depth, digits, tab_width, per_row;
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;
47 /* min should be less than max */
53 for (i = 21; max < pow[i]; i--)
56 while (i && !((min ^ max) & pow[i]))
61 /* min is less than half of max */
62 for (i = 21 - 1; min < pow[i]; i--)
68 return max & (pow[i] - 1);
73 const signed int *table
78 /* initialize powers of two */
80 for (i = 1; i <= 21; i++)
81 pow[i] = pow[i - 1] << 1;
83 /* reduce number of elements to get a more binary number */
87 /* find number of essential items */
89 while (essen && table[essen] == def_key)
93 N = most_binary (essen, N);
96 for (n = 21; N % pow[n]; n--)
100 if (pow[i] * (tab_width + 1) < 80)
112 for (i = 0; i < cmpcluster; i++)
113 if (((int *) r)[i] != ((int *) s)[i])
114 return ((int *) r)[i] - ((int *) s)[i];
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];
133 for (i = 0; i <= lev; i++)
138 best_cluster[i] = clusters[i];
148 long i, j, k, y, sbak;
156 if (lev == max_depth)
159 for (i = 1 - t[lev] % 2; i <= nn + (t[lev] >> nn) % 2; i++)
162 clusters[lev] = cluster = (i && nn >= 0) ? pow[i] : t[lev];
163 cmpcluster = cluster + 1;
165 t[lev + 1] = (t[lev] - 1) / cluster + 1;
166 for (j = 0; j < t[lev + 1]; j++)
168 memmove (temp + j * cmpcluster, tab[lev] + j * cluster,
169 cluster * sizeof (tab[lev][0]));
170 temp[j * cmpcluster + cluster] = j;
172 qsort (temp, t[lev + 1], cmpcluster * sizeof (temp[0]), compare);
173 for (j = 0; j < t[lev + 1]; j++)
175 perm[j] = temp[j * cmpcluster + cluster];
176 temp[j * cmpcluster + cluster] = 0;
180 tab[lev + 1][perm[0]] = perm[0];
181 for (j = 1; j < t[lev + 1]; j++)
183 if (compare (temp + y, temp + y + cmpcluster))
186 tab[lev + 1][perm[j]] = perm[j];
189 tab[lev + 1][perm[j]] = tab[lev + 1][perm[j - 1]];
193 s += k * node_size * cluster;
203 key_bytes = k * cluster;
204 key_bytes = key_bytes < 0xff ? 1 : key_bytes < 0xffff ? 2 : 4;
219 best_lev = max_depth + 2;
233 int i, j, k, y, ii, ofs;
234 const char *key_type;
236 if (best_t[lev] == 1)
239 nn -= (i = best_p[lev]);
240 cluster = best_cluster[lev];
241 cmpcluster = cluster + 1;
243 t[lev + 1] = best_t[lev + 1];
244 for (j = 0; j < t[lev + 1]; j++)
246 memmove (temp + j * cmpcluster, tab[lev] + j * cluster,
247 cluster * sizeof (tab[lev][0]));
248 temp[j * cmpcluster + cluster] = j;
250 qsort (temp, t[lev + 1], cmpcluster * sizeof (temp[0]), compare);
251 for (j = 0; j < t[lev + 1]; j++)
253 perm[j] = temp[j * cmpcluster + cluster];
254 temp[j * cmpcluster + cluster] = 0;
258 tab[lev + 1][perm[0]] = x[0] = perm[0];
259 for (j = 1; j < t[lev + 1]; j++)
261 if (compare (temp + y, temp + y + cmpcluster))
264 tab[lev + 1][perm[j]] = x[k];
268 tab[lev + 1][perm[j]] = tab[lev + 1][perm[j - 1]];
273 for (ii = 1; ii < k; ii++)
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);
283 for (ii = 0; ii < k; ii++)
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);
291 for (j = 0; j < cluster; j++)
293 if (!(j % per_row) && j != cluster - 1)
295 fprintf (f, "%*s,", tab_width, name[tab[lev][kk++]]);
298 for (j = 0; j < cluster; j++)
300 if (!(j % per_row) && j != cluster - 1)
302 fprintf (f, "%*d,", tab_width, tab[lev][kk++]);
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]] -
314 for (j = 0; j < k; j++)
315 if (x[j] > x[i] && (x[j] < x[jj] || jj == i))
319 fprintf (f, "\n};\n\n");
321 write_array (cluster * k);
336 fprintf (f, "\n" "/* *IND" "ENT-OFF* */\n\n");
338 fprintf (f, "/* *IND" "ENT-ON* */\n\n");
340 fprintf (f, "#define %s(x) \\\n", macro_name);
341 fprintf (f, "\t((x) >= 0x%lx ? ", N);
343 fprintf (f, "%s", name[def_key]);
345 fprintf (f, "%d", def_key);
348 for (i = best_lev - 1; i >= 0; i--)
350 fprintf (f, " \\\n\t%sLev%d[((x)", table_name, i);
352 fprintf (f, " >> %d", j);
354 fprintf (f, " & 0x%02lx) +", pow[best_p[best_lev - 1 - i]] - 1);
355 j += best_p[best_lev - 1 - i];
358 for (i = 0; i < best_lev; i++)
360 fprintf (f, ")\n\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"
375 " partition shape: %s",
376 packtab_version, macro_name, key_type_name, a, best_s, best_lev,
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");
389 const signed int *base,
392 signed int default_key,
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,
404 def_key = default_key;
405 max_depth = p_max_depth;
406 tab_width = p_tab_width;
408 key_type_name = p_key_type_name;
409 table_name = p_table_name;
410 macro_name = p_macro_name;
413 if (!(tab = malloc ((n + 1) * sizeof (tab[0]))))
415 memmove (tab[0], base, N * sizeof (base[0]));
422 /* End of packtab.c */