gen.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., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA 02110-1301, 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 #if HAVE_CONFIG_H+0
  29 # include <config.h>
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #include <stdio.h>
  33 #if STDC_HEADERS+0
  34 # include <stdlib.h>
  35 # include <stddef.h>
  36 #else
  37 # if HAVE_STDLIB_H
  38 #  include <stdlib.h>
  39 # endif
  40 #endif
  41 #if HAVE_STRING_H+0
  42 # if !STDC_HEADERS && HAVE_MEMORY_H
  43 #  include <memory.h>
  44 # endif
  45 # include <string.h>
  46 #endif
  47 #if HAVE_STRINGS_H+0
  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 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 < pow[i]; i--)
  75     ;
  76   ii = i;
  77   while (i && !((min ^ max) & pow[i]))
  78     i--;
  79
  80   if (ii == i)
  81     {
  82       /* min is less than half of max */
  83       for (i = 21 - 1; min < pow[i]; i--)
  84         ;
  85       i++;
  86       return pow[i];
  87     }
  88
  89   return max & (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   pow[0] = 1;
 101   for (i = 1; i <= 21; i++)
 102     pow[i] = 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 % pow[n]; n--)
 118     ;
 119   digits = (n + 3) / 4;
 120   for (i = 6; i; i--)
 121     if (pow[i] * (tab_width + 1) < 80)
 122       break;
 123   per_row = 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) ? 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] * 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] * pow[n - nn - best_p[lev]], digits,
 330                    x[i] * pow[n - nn] + j * pow[n - nn - best_p[lev]], digits,
 331                    x[i] * pow[n - nn] + (j + 1) * 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) +", 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 */