/*
 * Copyright (c) 1997-2007, OpenFWTK Development Group
 * All rights reserved. See LICENSE.
 */

/* maketable.c */

/* Copyright 1997-2000 by Eberhard Mattes <em-gw@windhager.de>
   Donated to the public domain.  No warranty.

   1997-09-06 Initial version
   1997-09-09 Moved code for -h from squid-gw to libem
   2000-04-15 Make NAME_data const (see HASH_IDX); add NAME_descr */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <errno.h>
#include <limits.h>
#include <string.h>
#include "firewall2.h"

static void usage (void)
{
  puts ("Usage:");
  puts ("  maketable -h <name> <size>  Make hash table");
  puts ("  maketable -H <name> <size>  Make variable hash table");
  puts ("  maketable -l                Make lower-case table");
  puts ("  maketable -u                Make upper-case table");
}

static void do_not_edit (void)
{
  puts ("/* DO NOT EDIT THIS FILE -- "
	"it is automatically generated by maketable */\n");
}

/* Build a table which converts upper-case letters to lower-case
   letters (or vice versa if UP is true).  Only 'A' through 'Z' (or
   'a' through 'z', respectively) are converted, all other characters
   are left unchanged.  The table maps an unsigned char to an unsigned
   char.  The output contains just the initialization data, without
   braces. */

static void make_case (int up)
{
  int i, c;

  do_not_edit ();
  i = 0;
  for (;;)
    {
      c = i;
      if (!up && c >= 'A' && c <= 'Z')
	c += 'a' - 'A';
      else if (up && c >= 'a' && c <= 'z')
	c -= 'a' - 'A';
      printf ("0x%.2x", c);
      if (i == UCHAR_MAX)
	break;
      ++i;
      if (i % 8 == 0)
	fputs (",\n", stdout);
      else
	fputs (", ", stdout);
    }
  putchar ('\n');
}

/* Build a hash table.  The input (from stdin) consists of lines
   having this format:

     ";" <COMMENT>
     <NAME> <SPACE> <HANDLER> <SPACE> <FLAGS> [ <SPACE> ";" <COMMENT> ]

   Empty lines and lines starting with ";" (comment lines) are
   ignored.  Other lines must contain three fields; they can also
   contain an optional comment.  The fields are separated by at least
   one space or tab.

   <NAME> is the string to be put as key into the hash table.  It must
   not contain upper-case letters if the lookup is intended to be
   case-insensitive.  <HANDLER> is the name of the function whose
   address will be put into the `handler' member.  <FLAGS> is a number
   which will be put into the `flags' member.  <FLAGS> need not
   contain digits, but must not contain spaces or tabs.

   The output consists of two tables: TABNAME_hash is the bucket
   table, TABNAME_data is the table of data elements, one for each
   input line that is not empty or a comment line. */

/* Return true if N is a prime.  Speed doesn't matter. */
static int is_prime (unsigned n)
{
    double limit, div, tdiv;

    if (n == 2) return 1;
    limit = sqrt((double)n);
    for (div = 3.0; div <= limit; ++div) {
	tdiv = n / div;
	if (ceil(tdiv) == tdiv) return 0;
    }
    return 1;
}

/* Find the smallest prime >= N. */
static unsigned find_prime (unsigned n)
{
  if (n != 2 && n % 2 == 0)
    ++n;
  for (;;)
    {
      if (is_prime (n))
	return n;
      if (n > UINT_MAX - 2)
	usage ();
      n += 2;
    }
}

struct entry
{
  struct entry *next;
  struct entry *thread;
  int index;
  char *name;
  size_t len;
  char *handler;
  char *flags;
};

struct handler
{
  struct handler *next;
  char *name;
};

static struct entry **buckets;
static int *chain_length;
static struct entry *entry_by_code[256];
static struct handler *handlers;
static char line[1024];

static void make_hash (int argc, char *argv[], int verbose, int variable)
{
  int i, lineno, index, collisions, max_chain_len, sum_chain_len, chains;
  int char_code, by_code;
  size_t line_len, name_len, handler_len, flags_len;
  unsigned h, hash_size;
  char *s, *handler, *flags, *tabname, *upper_tabname, *end;
  char next[100];
  struct entry *p, *first, **add;
  struct handler *ph;
  double avg_chain_len;
  long longnum;

  by_code = 0;
  if (argc >= 1 && strcmp (argv[0], "-c") == 0)
    {
      by_code = 1; --argc; ++argv;
    }
  if (argc != 2)
    usage ();
  tabname = argv[0];
  errno = 0;
  longnum = strtol (argv[1], &end, 10);
  if (errno != 0 || end == argv[1] || *end != 0 || longnum < 1
      || longnum > UINT_MAX)
    usage ();

  /* Find an appropriate hash size and allocate the arrays which
     depend on the hash size. */

  hash_size = find_prime ((unsigned)longnum);
  buckets = (struct entry **)xmalloc (hash_size * sizeof (struct entry *));
  chain_length = (int *)xmalloc (hash_size * sizeof (int));

  /* Initialize the arrays. */

  for (i = 0; i < hash_size; ++i)
    {
      buckets[i] = NULL;
      chain_length[i] = 0;
    }
  for (i = 0; i <= UCHAR_MAX; ++i)
    entry_by_code[i] = NULL;

  /* Translate the table name to upper case. */

  upper_tabname = xstrdup (tabname);
  for (i = 0; upper_tabname[i] != 0; ++i)
    if (upper_tabname[i] >= 'a' && upper_tabname[i] <= 'z')
      upper_tabname[i] = upper_tabname[i] - 'a' + 'A';

  /* Read the input file. */
  do_not_edit ();

  lineno = 0; index = 0; collisions = 0;
  first = NULL; add = &first; handlers = NULL;
  while (fgets (line, sizeof (line), stdin) != NULL)
    {
      ++lineno;

      /* Check for unterminated line at EOF or a line which is too
         long.  Remove the newline character. */

      line_len = strlen (line);
      if (line_len == 0 || line[line_len-1] != '\n')
	goto error;
      line[--line_len] = 0;

      /* Ignore empty lines and comment lines. */

      if (line_len == 0 || line[0] == ';')
	continue;

      /* Skip over the name. */

      s = line;
      while (*s != 0 && *s != ' ' && *s != '\t' && *s != ';')
	++s;
      if (*s == 0 || *s == ';')
	goto error;
      name_len = s - line;
      if (name_len == 0)
	goto error;

      /* Skip white space between the name and the handler. */

      while (*s == ' ' || *s == '\t')
	++s;

      /* Skip over the handler. */

      handler = s;
      while (*s != 0 && *s != ' ' && *s != '\t' && *s != ';')
	++s;
      if (*s == 0 || *s == ';')
	goto error;
      handler_len = s - handler;
      if (handler_len == 0)
	goto error;

      /* Skip white space between the handler and the flags. */

      while (*s == ' ' || *s == '\t')
	++s;

      /* Skip over the flags. */

      flags = s;
      while (*s != 0 && *s != ' ' && *s != '\t' && *s != ';')
	++s;
      if (*s == ';')
	goto error;
      flags_len = s - flags;
      if (flags_len == 0)
	goto error;

      /* The rest of the line is a comment and must start with a
	 semicolon if present. */

      while (*s == ' ' || *s == '\t')
	++s;
      if (*s != 0 && *s != ';')
	goto error;

      /* Check if the name is already known. */

      h = hash2 (line, name_len, hash_size);
      for (p = buckets[h]; p != NULL; p = p->next)
	if (p->len == name_len && memcmp (p->name, line, name_len) == 0)
	  goto error;

      /* Check for collision. */

      if (buckets[h] != NULL)
	collisions += 1;
      chain_length[h] += 1;

      /* Add a new entry. */

      p = (struct entry *)xmalloc (sizeof (struct entry));
      p->len = name_len;
      p->name = xstrndup (line, name_len);
      p->handler = xstrndup (handler, handler_len);
      p->flags = xstrndup (flags, flags_len);
      p->index = index++;
      p->next = buckets[h]; buckets[h] = p;
      p->thread = NULL; *add = p; add = &p->thread;

      /* Handle -c.  The FLAGS field is used for the character
         code and must be a number. */

      if (by_code)
	{
	  char_code = 0;
	  for (i = 0; i < flags_len; ++i)
	    {
	      if (flags[i] < '0' || flags[i] > '9')
		goto error;

	      /* This overflow check rejects some values which would
                 not overflow; however the number should not exceed
                 65535 anyway and we assume that `int' has at least 32
                 bits. */

	      if (char_code >= (INT_MAX - 9) / 10)
		goto error;
	      char_code = char_code * 10 + flags[i] - '0';
	    }
	  assert (char_code >= 0);

	  /* Ignore character codes above 255. */

	  if (char_code <= 255)
	    {
	      if (entry_by_code[char_code] != NULL)
		goto error;
	      entry_by_code[char_code] = p;
	    }
	}

      /* Add the handler to our list unless it's NULL. */

      if (strcmp (p->handler, "NULL") != 0)
	{
	  for (ph = handlers; ph != NULL; ph = ph->next)
	    if (strcmp (p->handler, ph->name) == 0)
	      break;
	  if (ph == NULL)
	    {
	      ph = (struct handler *)xmalloc (sizeof (struct handler));
	      ph->name = p->handler;
	      ph->next = handlers; handlers = ph;
	      if (variable)
	      	printf("int\t%s();\n",p->handler);
	    }
	}
    }

  if (ferror (stdin))
    {
      perror ("stdin");
      exit (2);
    }

  printf("\n\n");

  /* Define the hash size. */

  printf ("#define %s_HASH_SIZE %u\n\n", upper_tabname, hash_size);

  /* Produce data table. */

  if (!variable)
  	printf ("static struct hash_entry const %s_data[%d] =\n{\n", tabname, index);
  else
  	printf ("static struct hash_entry %s_data[%d] =\n{\n", tabname, index);
  for (p = first, i = 0; p != NULL; p = p->thread, ++i)
    {
      if (p->index != i)
	abort ();
      if (p->next == NULL)
	strlcpy (next, "NULL", sizeof(next));
      else
	snprintf (next, sizeof(next), "%s_data+%d", tabname, p->next->index);
      printf ("  {\"%s\", %d, %s, %s, %s}",
	      p->name, (int)p->len, next, p->handler, p->flags);
      if (p->thread != NULL)
	putchar (',');
      putchar ('\n');
    }
  printf ("};\n\n");

  /* Produce bucket table. */

  printf ("static const struct hash_entry * const %s_hash[%s_HASH_SIZE] ="
	  "\n{\n", tabname, upper_tabname);
  for (i = 0; i < hash_size; ++i)
    {
      if (buckets[i] == NULL)
	fputs ("  NULL", stdout);
      else
	printf ("  %s_data+%d", tabname, buckets[i]->index);
      if (i != hash_size - 1)
	putchar (',');
      putchar ('\n');
    }
  printf ("};\n");

  /* Produce by-code table. */

  if (by_code)
    {
      printf ("static const struct hash_entry * const %s_by_code[256] =\n{\n",
	      tabname);
      for (i = 0; i <= 255; ++i)
	{
	  if (entry_by_code[i] == NULL)
	    fputs ("  NULL", stdout);
	  else
	    printf ("  %s_data+%d", tabname, entry_by_code[i]->index);
	  if (i != 255)
	    putchar (',');
	  putchar ('\n');
	}
      printf ("};\n");
    }

  /* Produce descriptor. */

  if (!variable)
  	printf ("\nstatic struct hash_descr const %s_descr ="
		  "\n{ %s_data, %s_hash, %s%s, %s_HASH_SIZE };\n",
	 	 tabname, tabname, tabname,
	  	(by_code ? tabname : "0"), (by_code ? "_by_code" : ""),
	  	upper_tabname);
  else
  	printf ("\nstatic struct hash_descr %s_descr ="
		  "\n{ %s_data, %s_hash, %s%s, %s_HASH_SIZE };\n",
	 	 tabname, tabname, tabname,
	  	(by_code ? tabname : "0"), (by_code ? "_by_code" : ""),
	  	upper_tabname);

  /* Produce macro for checking function pointers. */

  if (handlers != NULL)
    {
      printf ("\n#define %s_HANDLER(fp) (", upper_tabname);
      for (ph = handlers; ph != NULL; ph = ph->next)
	printf (" \\\n  %s (fp) == %s",
		ph == handlers ? "  " : "||", ph->name);
      puts (" )");
    }

  max_chain_len = 0; sum_chain_len = 0; chains = 0;
  for (i = 0; i < hash_size; ++i)
    {
      sum_chain_len += chain_length[i];
      if (chain_length[i] > max_chain_len)
	max_chain_len = chain_length[i];
      if (chain_length[i] != 0)
	++chains;
    }
  if (chains == 0)
    avg_chain_len = 0.0;
  else
    avg_chain_len = (double)sum_chain_len / (double)chains;

  printf ("\n/* STATISTICS:\n\n");
  printf ("   Collisions:            %d\n", collisions);
  printf ("   Maximum chain length:  %d\n", max_chain_len);
  printf ("   Average chain length:  %1.2f\n", avg_chain_len);
  printf ("   Hash table population: %1.0f%%\n",
	   100.0 * (double)chains / (double)hash_size);
  printf ("*/\n");

  if (verbose)
    {
      fprintf (stderr, "STATISTICS\n");
      fprintf (stderr, "Collisions:            %d\n", collisions);
      fprintf (stderr, "Maximum chain length:  %d\n", max_chain_len);
      fprintf (stderr, "Average chain length:  %1.2f\n", avg_chain_len);
      fprintf (stderr, "Hash table population: %1.0f%%\n",
	       100.0 * (double)chains / (double)hash_size);
    }
  return;

error:
  fprintf (stderr, "Error in line %d\n", lineno);
  exit (2);
}

int main (int argc, char *argv[])
{
  if (argc >= 4 && strcmp (argv[1], "-h") == 0)
    make_hash (argc - 2, argv + 2, 0, 0);
  else if (argc >= 4 && strcmp (argv[1], "-hv") == 0)
    make_hash (argc - 2, argv + 2, 1, 0);
  else if (argc >= 4 && strcmp (argv[1], "-H") == 0)
    make_hash (argc - 2, argv + 2, 0, 1);
  else if (argc >= 4 && strcmp (argv[1], "-hv") == 0)
    make_hash (argc - 2, argv + 2, 1, 1);
  else if (argc == 2 && strcmp (argv[1], "-l") == 0)
    make_case (0);
  else if (argc == 2 && strcmp (argv[1], "-u") == 0)
    make_case (1);
  else
    usage ();
  if (fflush (stdout) != 0)
    {
      perror ("maketable");
      exit (2);
    }
  return 0;
}