/* PackTab - Pack a static table

 * Copyright (C) 2001 Behdad Esfahbod. 

 * 

 * This library is free software; you can redistribute it and/or 

 * modify it under the terms of the GNU Lesser General Public 

 * License as published by the Free Software Foundation; either 

 * version 2.1 of the License, or (at your option) any later version. 

 * 

 * This library is distributed in the hope that it will be useful, 

 * but WITHOUT ANY WARRANTY; without even the implied warranty of 

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU 

 * Lesser General Public License for more details. 

 * 

 * You should have received a copy of the GNU Lesser General Public License 

 * along with this library, in a file named COPYING; if not, write to the 

 * Free Software Foundation, Inc., 59 Temple Place, Suite 330, 

 * Boston, MA 02111-1307, USA  

 * 

 * For licensing issues, contact <fwpg@sharif.edu>. 

 */

/*

  8 <= N <= 2^21

  int key

  1 <= max_depth <= 21

*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "packtab.h"

typedef signed int uni_table[1024 * 1024 * 2];

static int n, a, max_depth, digits, tab_width, per_row;

static long N;

signed int def_key;

static uni_table temp, x, perm, *tab;

static long pow[22], cluster, cmpcluster;

static const char *const *name, *key_type_name, *table_name, *macro_name;

static FILE *f;

static long

most_binary (

  long min,

  long max

)

{

  /* min should be less than max */

  register int i, ii;

  if (min == max)

    return max;

  for (i = 21; max < pow[i]; i--)

    ;

  ii = i;

  while (i && !((min ^ max) & pow[i]))

    i--;

  if (ii == i)

    {

      /* min is less than half of max */

      for (i = 21 - 1; min < pow[i]; i--)

	;

      i++;

      return pow[i];

    }

  return max & (pow[i] - 1);

}

static void

init (

  const signed int *table

)

{

  register int i;

  /* initialize powers of two */

  pow[0] = 1;

  for (i = 1; i <= 21; i++)

    pow[i] = pow[i - 1] << 1;

  /* reduce number of elements to get a more binary number */

  {

    long essen;

    /* find number of essential items */

    essen = N - 1;

    while (essen && table[essen] == def_key)

      essen--;

    essen++;

    N = most_binary (essen, N);

  }

  for (n = 21; N % pow[n]; n--)

    ;

  digits = (n + 3) / 4;

  for (i = 6; i; i--)

    if (pow[i] * (tab_width + 1) < 80)

      break;

  per_row = pow[i];

}

static int

compare (

  const void *r,

  const void *s

)

{

  int i;

  for (i = 0; i < cmpcluster; i++)

    if (((int *) r)[i] != ((int *) s)[i])

      return ((int *) r)[i] - ((int *) s)[i];

  return 0;

}

static int lev, best_lev, p[22], best_p[22], nn;

static long c[22], best_c[22], s, best_s;

static long t[22], best_t[22], clusters[22], best_cluster[22];

static void

found (

  void

)

{

  int i;

  if (s < best_s)

    {

      best_s = s;

      best_lev = lev;

      for (i = 0; i <= lev; i++)

	{

	  best_p[i] = p[i];

	  best_c[i] = c[i];

	  best_t[i] = t[i];

	  best_cluster[i] = clusters[i];

	}

    }

}

static void

bt (

  int node_size

)

{

  long i, j, k, y, sbak;

  long key_bytes;

  if (t[lev] == 1)

    {

      found ();

      return;

    }

  if (lev == max_depth)

    return;

  for (i = 1 - t[lev] % 2; i <= nn + (t[lev] >> nn) % 2; i++)

    {

      nn -= (p[lev] = i);

      clusters[lev] = cluster = (i && nn >= 0) ? pow[i] : t[lev];

      cmpcluster = cluster + 1;

      t[lev + 1] = (t[lev] - 1) / cluster + 1;

      for (j = 0; j < t[lev + 1]; j++)

	{

	  memmove (temp + j * cmpcluster, tab[lev] + j * cluster,

		   cluster * sizeof (tab[lev][0]));

	  temp[j * cmpcluster + cluster] = j;

	}

      qsort (temp, t[lev + 1], cmpcluster * sizeof (temp[0]), compare);

      for (j = 0; j < t[lev + 1]; j++)

	{

	  perm[j] = temp[j * cmpcluster + cluster];

	  temp[j * cmpcluster + cluster] = 0;

	}

      k = 1;

      y = 0;

      tab[lev + 1][perm[0]] = perm[0];

      for (j = 1; j < t[lev + 1]; j++)

	{

	  if (compare (temp + y, temp + y + cmpcluster))

	    {

	      k++;

	      tab[lev + 1][perm[j]] = perm[j];

	    }

	  else

	    tab[lev + 1][perm[j]] = tab[lev + 1][perm[j - 1]];

	  y += cmpcluster;

	}

      sbak = s;

      s += k * node_size * cluster;

      c[lev] = k;

      if (s >= best_s)

	{

	  s = sbak;

	  nn += i;

	  return;

	}

      key_bytes = k * cluster;

      key_bytes = key_bytes < 0xff ? 1 : key_bytes < 0xffff ? 2 : 4;

      lev++;

      bt (key_bytes);

      lev--;

      s = sbak;

      nn += i;

    }

}

static void

solve (

  void

)

{

  best_lev = max_depth + 2;

  best_s = N * a * 2;

  lev = 0;

  s = 0;

  nn = n;

  t[0] = N;

  bt (a);

}

static void

write_array (

  long max_key

)

{

  int i, j, k, y, ii, ofs;

  const char *key_type;

  if (best_t[lev] == 1)

    return;

  nn -= (i = best_p[lev]);

  cluster = best_cluster[lev];

  cmpcluster = cluster + 1;

  t[lev + 1] = best_t[lev + 1];

  for (j = 0; j < t[lev + 1]; j++)

    {

      memmove (temp + j * cmpcluster, tab[lev] + j * cluster,

	       cluster * sizeof (tab[lev][0]));

      temp[j * cmpcluster + cluster] = j;

    }

  qsort (temp, t[lev + 1], cmpcluster * sizeof (temp[0]), compare);

  for (j = 0; j < t[lev + 1]; j++)

    {

      perm[j] = temp[j * cmpcluster + cluster];

      temp[j * cmpcluster + cluster] = 0;

    }

  k = 1;

  y = 0;

  tab[lev + 1][perm[0]] = x[0] = perm[0];

  for (j = 1; j < t[lev + 1]; j++)

    {

      if (compare (temp + y, temp + y + cmpcluster))

	{

	  x[k] = perm[j];

	  tab[lev + 1][perm[j]] = x[k];

	  k++;

	}

      else

	tab[lev + 1][perm[j]] = tab[lev + 1][perm[j - 1]];

      y += cmpcluster;

    }

  i = 0;

  for (ii = 1; ii < k; ii++)

    if (x[ii] < x[i])

      i = ii;

  key_type = !lev ? key_type_name :

    max_key <= 0xff ? "PACKTAB_UINT8" :

    max_key <= 0xffff ? "PACKTAB_UINT16" : "PACKTAB_UINT32";

  fprintf (f, "static const %s %sLev%d[%ld*%d] = {", key_type, table_name,

	   best_lev - lev - 1, cluster, k);

  ofs = 0;

  for (ii = 0; ii < k; ii++)

    {

      int kk, jj;

      fprintf (f, "\n#define %sLev%d_%0*lX 0x%0X", table_name,

	       best_lev - lev - 1, digits, x[i] * pow[n - nn], ofs);

      kk = x[i] * cluster;

      if (!lev)

	if (name)

	  for (j = 0; j < cluster; j++)

	    {

	      if (!(j % per_row) && j != cluster - 1)

		fprintf (f, "\n  ");

	      fprintf (f, "%*s,", tab_width, name[tab[lev][kk++]]);

	    }

	else

	  for (j = 0; j < cluster; j++)

	    {

	      if (!(j % per_row) && j != cluster - 1)

		fprintf (f, "\n  ");

	      fprintf (f, "%*d,", tab_width, tab[lev][kk++]);

	    }

      else

	for (j = 0; j < cluster; j++, kk++)

	  fprintf (f, "\n  %sLev%d_%0*lX,  /* %0*lX..%0*lX */", table_name,

		   best_lev - lev, digits,

		   tab[lev][kk] * pow[n - nn - best_p[lev]], digits,

		   x[i] * pow[n - nn] + j * pow[n - nn - best_p[lev]], digits,

		   x[i] * pow[n - nn] + (j + 1) * pow[n - nn - best_p[lev]] -

		   1);

      ofs += cluster;

      jj = i;

      for (j = 0; j < k; j++)

	if (x[j] > x[i] && (x[j] < x[jj] || jj == i))

	  jj = j;

      i = jj;

    }

  fprintf (f, "\n};\n\n");

  lev++;

  write_array (cluster * k);

  lev--;

}

static void

write_source (

  void

)

{

  int i, j;

  lev = 0;

  s = 0;

  nn = n;

  t[0] = N;

  fprintf (f, "\n" "/* *IND" "ENT-OFF* */\n\n");

  write_array (0);

  fprintf (f, "/* *IND" "ENT-ON* */\n\n");

  fprintf (f, "#define %s(x) \\\n", macro_name);

  fprintf (f, "\t((x) >= 0x%lx ? ", N);

  if (name)

    fprintf (f, "%s", name[def_key]);

  else

    fprintf (f, "%d", def_key);

  fprintf (f, " : ");

  j = 0;

  for (i = best_lev - 1; i >= 0; i--)

    {

      fprintf (f, " \\\n\t%sLev%d[((x)", table_name, i);

      if (j != 0)

	fprintf (f, " >> %d", j);

      if (i)

	fprintf (f, " & 0x%02lx) +", pow[best_p[best_lev - 1 - i]] - 1);

      j += best_p[best_lev - 1 - i];

    }

  fprintf (f, ")");

  for (i = 0; i < best_lev; i++)

    fprintf (f, "]");

  fprintf (f, ")\n\n");

}

static void

write_out (

  void

)

{

  int i;

  fprintf (f, "/*\n"

	   "  generated by packtab.c version %d\n\n"

	   "  use %s(key) to access your table\n\n"

	   "  assumed sizeof(%s): %d\n"

	   "  required memory: %ld\n"

	   "  lookups: %d\n"

	   "  partition shape: %s",

	   packtab_version, macro_name, key_type_name, a, best_s, best_lev,

	   table_name);

  for (i = best_lev - 1; i >= 0; i--)

    fprintf (f, "[%ld]", best_cluster[i]);

  fprintf (f, "\n" "  different table entries:");

  for (i = best_lev - 1; i >= 0; i--)

    fprintf (f, " %ld", best_c[i]);

  fprintf (f, "\n*/\n");

  write_source ();

}

int

pack_table (

  const signed int *base,

  long key_num,

  int key_size,

  signed int default_key,

  int p_max_depth,

  int p_tab_width,

  const char *const *p_name,

  const char *p_key_type_name,

  const char *p_table_name,

  const char *p_macro_name,

  FILE *out

)

{

  N = key_num;

  a = key_size;

  def_key = default_key;

  max_depth = p_max_depth;

  tab_width = p_tab_width;

  name = p_name;

  key_type_name = p_key_type_name;

  table_name = p_table_name;

  macro_name = p_macro_name;

  f = out;

  init (base);

  if (!(tab = malloc ((n + 1) * sizeof (tab[0]))))

    return 0;

  memmove (tab[0], base, N * sizeof (base[0]));

  solve ();

  write_out ();

  free (tab);

  return 1;

}

/* End of packtab.c */