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