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