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 */