Wow!!! I use the wonderful packtab to compress the mirroring table now! It

gives an smaller and faster table than the old binary search one!  Moreover,
packtab deals with tables with empty heads much better.  Voila!

5 files changed, 197 insertions, 81 deletions

diff --git a/gen.tab/Makefile.am b/gen.tab/Makefile.am
index dc263df..99354ad 100644
--- a/gen.tab/Makefile.am
+++ b/gen.tab/Makefile.am
@@ -4,7 +4,7 @@ EXTRA_PROGRAMS = \
 		gen-unicode-version
 
 gen_bidi_type_tab_SOURCES = gen-bidi-type-tab.c packtab.c packtab.h
-gen_mirroring_tab_SOURCES = gen-mirroring-tab.c
+gen_mirroring_tab_SOURCES = gen-mirroring-tab.c packtab.c packtab.h
 gen_unicode_version_SOURCES = gen-unicode-version.c
 
 CLEANFILES = $(EXTRA_PROGRAMS)
@@ -74,7 +74,7 @@ BidiMirroring_mirroring.tab.i: \
 		$(gen_mirroring_tab_SOURCES)
 	$(MAKE) $(AM_MAKEFLAGS) $(gen_mirroring_tab)
 	(DATA_FILE_TYPE=`echo $< | sed s,.*/,,`; \
-	./$(gen_mirroring_tab) \
+	./$(gen_mirroring_tab) $(COMPRESSION) \
 	 $$DATA_FILE_TYPE $< > $@ || ($(RM) $@ && false))
 
 mirroring.tab.i:
diff --git a/gen.tab/gen-bidi-type-tab.c b/gen.tab/gen-bidi-type-tab.c
index bd9fe60..3832c4a 100644
--- a/gen.tab/gen-bidi-type-tab.c
+++ b/gen.tab/gen-bidi-type-tab.c
@@ -1,10 +1,10 @@
 /* FriBidi
  * gen-bidi-type-tab.c - generate bidi-type.tab.i for libfribidi
  *
- * $Id: gen-bidi-type-tab.c,v 1.10 2004-06-04 09:41:11 behdad Exp $
+ * $Id: gen-bidi-type-tab.c,v 1.11 2004-06-09 20:01:00 behdad Exp $
  * $Author: behdad $
- * $Date: 2004-06-04 09:41:11 $
- * $Revision: 1.10 $
+ * $Date: 2004-06-09 20:01:00 $
+ * $Revision: 1.11 $
  * $Source: /home/behdad/src/fdo/fribidi/togit/git/../fribidi/fribidi2/gen.tab/gen-bidi-type-tab.c,v $
  *
  * Author:
@@ -135,10 +135,10 @@ get_type (
   return 0;
 }
 
-#define table_name "FriBidiCharTypeData"
+#define table_name "Bid"
 #define macro_name "FRIBIDI_GET_BIDI_TYPE"
 
-static int table[FRIBIDI_UNICODE_CHARS];
+static signed int table[FRIBIDI_UNICODE_CHARS];
 static char s[4000];
 
 static void
@@ -316,10 +316,13 @@ gen_bidi_type_tab (
 	  "#define PACKTAB_UINT32 fribidi_uint32\n\n");
 
   if (!pack_table
-      (table, FRIBIDI_UNICODE_CHARS, 1, max_depth, 3, names,
+      (table, FRIBIDI_UNICODE_CHARS, 1, LTR, max_depth, 3, names,
        "unsigned char", table_name, macro_name, stdout))
     die ("error: insufficient memory, decrease max_depth");
 
+  printf ("#undef PACKTAB_UINT8\n"
+	  "#undef PACKTAB_UINT16\n" "#undef PACKTAB_UINT32\n\n");
+
   printf ("/* End of generated " outputname " */\n");
 }
 
diff --git a/gen.tab/gen-mirroring-tab.c b/gen.tab/gen-mirroring-tab.c
index 92d4ad5..9656468 100644
--- a/gen.tab/gen-mirroring-tab.c
+++ b/gen.tab/gen-mirroring-tab.c
@@ -1,10 +1,10 @@
 /* FriBidi
- * gen-mirroring-tab.c - generate mirroring.tab.i for libfribidi
+ * gen-mirroring-tab.c - generate bidi-mirroring.i for libfribidi
  *
- * $Id: gen-mirroring-tab.c,v 1.7 2004-05-31 18:43:26 behdad Exp $
+ * $Id: gen-mirroring-tab.c,v 1.8 2004-06-09 20:01:00 behdad Exp $
  * $Author: behdad $
- * $Date: 2004-05-31 18:43:26 $
- * $Revision: 1.7 $
+ * $Date: 2004-06-09 20:01:00 $
+ * $Revision: 1.8 $
  * $Source: /home/behdad/src/fdo/fribidi/togit/git/../fribidi/fribidi2/gen.tab/gen-mirroring-tab.c,v $
  *
  * Author:
@@ -54,6 +54,8 @@
 # include <strings.h>
 #endif
 
+#include "packtab.h"
+
 #define appname "gen-mirroring-tab"
 #define outputname "mirroring.tab.i"
 
@@ -92,20 +94,35 @@ die4 (
   exit (1);
 }
 
-static FriBidiChar table[FRIBIDI_UNICODE_CHARS];
-static char s[4000];
+#define table_name "Mir"
+#define macro_name "FRIBIDI_GET_MIRRORING_DELTA"
 
-static int mirroring_count;
+static signed int table[FRIBIDI_UNICODE_CHARS];
+static char s[4000];
+static signed long max_dist;
 
 static void
 init (
 )
 {
-  register FriBidiChar i;
+  max_dist = 0;
+}
 
-  for (i = 0; i < FRIBIDI_UNICODE_CHARS; i++)
-    table[i] = 0;
-  mirroring_count = 0;
+static void
+clear_tab (
+)
+{
+  register FriBidiChar c;
+
+  for (c = 0; c < FRIBIDI_UNICODE_CHARS; c++)
+    table[c] = 0;
+}
+
+static void
+init_tab_bidi_mirroring_txt (
+)
+{
+  clear_tab ();
 }
 
 static void
@@ -119,6 +136,7 @@ read_bidi_mirroring_txt (
   while (fgets (s, sizeof s, f))
     {
       unsigned long i, j;
+      signed long dist;
       int k;
 
       l++;
@@ -127,10 +145,15 @@ read_bidi_mirroring_txt (
 	continue;
 
       k = sscanf (s, "%lx; %lx", &i, &j);
-      if (k != 2 || i >= FRIBIDI_UNICODE_CHARS || j >= FRIBIDI_UNICODE_CHARS)
+      if (k != 2 || i < 0 || i >= FRIBIDI_UNICODE_CHARS || j < 0
+	  || j >= FRIBIDI_UNICODE_CHARS)
 	die4 ("invalid pair in input at line %ld: %04lX, %04lX", l, i, j);
-      table[i] = j;
-      mirroring_count++;
+      dist = ((signed long) j - (signed long) i);
+      table[i] = dist;
+      if (dist > max_dist)
+	max_dist = dist;
+      else if (-dist > max_dist)
+	max_dist = -dist;
     }
 }
 
@@ -156,27 +179,33 @@ read_data (
 
 static void
 gen_mirroring_tab (
+  int max_depth,
   char *data_file_type
 )
 {
-  FriBidiChar i;
+  int key_bytes;
+  char *key_type;
 
-  fprintf (stderr, "Generating output, it may take up to a few seconds\n");
+  fprintf (stderr, "Generating output, it may take up to a few minutes\n");
   printf ("/* " outputname "\n * generated by " appname " (" FRIBIDI_NAME " "
 	  FRIBIDI_VERSION ")\n" " * from the file %s of Unicode version "
 	  FRIBIDI_UNICODE_VERSION ". */\n\n", data_file_type);
 
-  printf ("/* *IND" "ENT-OFF" "* */\n\n");
-  printf
-    ("static const struct _FriBidiMirroredPair FriBidiMirroredChars[] =\n{\n");
-  for (i = 0; i < FRIBIDI_UNICODE_CHARS; i++)
-    if (table[i])
-      printf ("  {0x%04lX, 0x%04lX},\n", (unsigned long) i,
-	      (unsigned long) table[i]);
-  printf ("} ;\n\n");
-  printf ("/* *IND" "ENT-ON* */\n\n");
-  printf ("static const int nFriBidiMirroredChars = %d;\n\n",
-	  mirroring_count);
+  printf ("#define PACKTAB_UINT8 fribidi_uint8\n"
+	  "#define PACKTAB_UINT16 fribidi_uint16\n"
+	  "#define PACKTAB_UINT32 fribidi_uint32\n\n");
+
+  key_bytes = max_dist <= 0x7f ? 1 : max_dist < 0x7fff ? 2 : 4;
+  key_type = key_bytes == 1 ? "fribidi_int8" : key_bytes == 2 ?
+    "fribidi_int16" : "fribidi_int32";
+
+  if (!pack_table
+      (table, FRIBIDI_UNICODE_CHARS, key_bytes, 0, max_depth, 1, NULL,
+       key_type, table_name, macro_name, stdout))
+    die ("error: insufficient memory, decrease max_depth");
+
+  printf ("#undef PACKTAB_UINT8\n"
+	  "#undef PACKTAB_UINT16\n" "#undef PACKTAB_UINT32\n\n");
 
   printf ("/* End of generated " outputname " */\n");
 }
@@ -187,16 +216,20 @@ main (
   char **argv
 )
 {
-  if (argc != 3)
-    die ("usage:\n  " appname " data-file-type data-file-name\n"
-	 "where data-file-type is:\n" "  * BidiMirroring.txt");
+  if (argc != 4)
+    die ("usage:\n  " appname " max-depth data-file-type data-file-name\n"
+	 "where data-file-type is one of these:\n" "  * BidiMirroring.txt");
   {
-    char *data_file_type = argv[1];
-    char *data_file_name = argv[2];
+    int max_depth = atoi (argv[1]);
+    char *data_file_type = argv[2];
+    char *data_file_name = argv[3];
+
+    if (max_depth < 2)
+      die ("invalid depth");
 
     init ();
     read_data (data_file_type, data_file_name);
-    gen_mirroring_tab (data_file_type);
+    gen_mirroring_tab (max_depth, data_file_type);
   }
 
   return 0;
diff --git a/gen.tab/packtab.c b/gen.tab/packtab.c
index 11c4e8a..45f762a 100644
--- a/gen.tab/packtab.c
+++ b/gen.tab/packtab.c
@@ -24,28 +24,97 @@
   int key
   1 <= max_depth <= 21
 */
+
+#if HAVE_CONFIG_H
+# include <config.h>
+#endif /* HAVE_CONFIG_H */
+
 #include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#if STDC_HEADERS
+# include <stdlib.h>
+# include <stddef.h>
+#else
+# if HAVE_STDLIB_H
+#  include <stdlib.h>
+# endif
+#endif
+#if HAVE_STRING_H
+# if !STDC_HEADERS && HAVE_MEMORY_H
+#  include <memory.h>
+# endif
+# include <string.h>
+#endif
+#if HAVE_STRINGS_H
+# include <strings.h>
+#endif
 
 #include "packtab.h"
 
-typedef int uni_table[1024 * 1024 * 2];
-static int n, a, max_depth, N, digits, tab_width, per_row;
+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 int pow[22], cluster, cmpcluster;
-static char **name, *key_type_name, *table_name, *macro_name;
+static long pow[22], cluster, cmpcluster;
+static const char *const *name, *key_type_name, *table_name, *macro_name;
 static FILE *f;
 
-static inline void
+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
 )
 {
-  int i;
+  register int i;
+
+  /* initialize powers of two */
   pow[0] = 1;
   for (i = 1; i <= 21; i++)
-    pow[i] = pow[i - 1] * 2;
-  for (n = 21; pow[n] > N || N % pow[n]; n--)
+    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--)
@@ -67,9 +136,10 @@ compare (
   return 0;
 }
 
-static int lev, p[22], t[22], c[22], clusters[22], s, nn;
-static int best_lev, best_p[22], best_t[22], best_c[22], best_cluster[22],
-  best_s;
+static int lev, p[22], nn;
+static int best_lev, best_p[22];
+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 (
@@ -97,7 +167,8 @@ bt (
   int node_size
 )
 {
-  int i, j, k, y, sbak, key_bytes;
+  long i, j, k, y, sbak;
+  long key_bytes;
 
   if (t[lev] == 1)
     {
@@ -178,11 +249,11 @@ solve (
 
 static void
 write_array (
-  int max_key
+  long max_key
 )
 {
   int i, j, k, y, ii, ofs;
-  char *key_type;
+  const char *key_type;
 
   if (best_t[lev] == 1)
     return;
@@ -228,13 +299,13 @@ write_array (
   key_type = !lev ? key_type_name :
     max_key <= 0xff ? "PACKTAB_UINT8" :
     max_key <= 0xffff ? "PACKTAB_UINT16" : "PACKTAB_UINT32";
-  fprintf (f, "static const %s %sLevel%d[%d*%d] = {", key_type, table_name,
+  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\n#define %sLevel%d_%0*X 0x%0X\n", table_name,
+      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)
@@ -254,7 +325,7 @@ write_array (
 	    }
       else
 	for (j = 0; j < cluster; j++, kk++)
-	  fprintf (f, "\n  %sLevel%d_%0*X,  /* %0*X..%0*X */", table_name,
+	  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,
@@ -288,20 +359,26 @@ write_source (
   write_array (0);
   fprintf (f, "/* *IND" "ENT-ON* */\n\n");
 
-  fprintf (f, "#define %s(x)", macro_name);
+  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 = 1;
   for (i = best_lev - 1; i >= 0; i--)
     {
-      fprintf (f, "\t\\\n\t%sLevel%d[(x)", table_name, i);
+      fprintf (f, " \\\n\t%sLev%d[(x)", table_name, i);
       if (j != 1)
 	fprintf (f, "/%d", j);
       if (i)
-	fprintf (f, "%%%d +", pow[best_p[best_lev - 1 - i]]);
+	fprintf (f, "%%%ld +", pow[best_p[best_lev - 1 - i]]);
       j *= best_cluster[best_lev - 1 - i];
     }
   for (i = 0; i < best_lev; i++)
     fprintf (f, "]");
-  fprintf (f, "\n\n");
+  fprintf (f, ")\n\n");
 }
 
 static void
@@ -313,36 +390,38 @@ write_out (
 	   "  generated by packtab.c version %d\n\n"
 	   "  use %s(key) to access your table\n\n"
 	   "  assumed sizeof(%s): %d\n"
-	   "  required memory: %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, "[%d]", best_cluster[i]);
+    fprintf (f, "[%ld]", best_cluster[i]);
   fprintf (f, "\n" "  different table entries:");
   for (i = best_lev - 1; i >= 0; i--)
-    fprintf (f, " %d", best_c[i]);
+    fprintf (f, " %ld", best_c[i]);
   fprintf (f, "\n*/\n");
   write_source ();
 }
 
 int
 pack_table (
-  int *base,
-  int key_num,
+  const signed int *base,
+  long key_num,
   int key_size,
+  signed int default_key,
   int p_max_depth,
   int p_tab_width,
-  char **p_name,
-  char *p_key_type_name,
-  char *p_table_name,
-  char *p_macro_name,
+  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;
@@ -350,10 +429,10 @@ pack_table (
   table_name = p_table_name;
   macro_name = p_macro_name;
   f = out;
-  init ();
+  init (base);
   if (!(tab = malloc ((n + 1) * sizeof (tab[0]))))
     return 0;
-  memmove (tab[0], base, key_num * sizeof (int));
+  memmove (tab[0], base, N * sizeof (base[0]));
   solve ();
   write_out ();
   free (tab);
diff --git a/gen.tab/packtab.h b/gen.tab/packtab.h
index 26b8b32..45741a7 100644
--- a/gen.tab/packtab.h
+++ b/gen.tab/packtab.h
@@ -30,15 +30,16 @@ extern "C"
 #define packtab_version 2
 
   int pack_table (
-  int *base,
-  int key_num,
+  const signed int *base,
+  long key_num,
   int key_size,
+  signed int default_key,
   int max_depth,
   int tab_width,
-  char **name,
-  char *key_type_name,
-  char *table_name,
-  char *macro_name,
+  const char *const *name,
+  const char *key_type_name,
+  const char *table_name,
+  const char *macro_name,
   FILE *out
   );