[FriBidi-commit] fribidi/gen.tab Makefile.am, 1.10,
1.11 gen-bidi-type-tab.c, 1.10, 1.11 gen-mirroring-tab.c, 1.7,
1.8 packtab.c, 1.3, 1.4 packtab.h, 1.2, 1.3
Behdad Esfahbod
behdad at pdx.freedesktop.org
Wed Jun 9 13:01:02 PDT 2004
- Previous message: [FriBidi-commit] fribidi/charset fribidi-char-sets.c,1.5,1.6
- Next message: [FriBidi-commit] fribidi/lib fribidi-bidi-type.c, 1.10,
1.11 fribidi-bidi-types.h, 1.6, 1.7 fribidi-mirroring.c, 1.9,
1.10 fribidi-types.h, 1.5, 1.6 fribidi.h, 1.4, 1.5
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Update of /cvs/fribidi/fribidi/gen.tab
In directory pdx:/tmp/cvs-serv31109/gen.tab
Modified Files:
Makefile.am gen-bidi-type-tab.c gen-mirroring-tab.c packtab.c
packtab.h
Log Message:
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!
Index: Makefile.am
===================================================================
RCS file: /cvs/fribidi/fribidi/gen.tab/Makefile.am,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- a/Makefile.am 4 Jun 2004 09:41:11 -0000 1.10
+++ b/Makefile.am 9 Jun 2004 20:01:00 -0000 1.11
@@ -4,7 +4,7 @@
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 @@
$(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:
Index: gen-bidi-type-tab.c
===================================================================
RCS file: /cvs/fribidi/fribidi/gen.tab/gen-bidi-type-tab.c,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- a/gen-bidi-type-tab.c 4 Jun 2004 09:41:11 -0000 1.10
+++ b/gen-bidi-type-tab.c 9 Jun 2004 20:01:00 -0000 1.11
@@ -135,10 +135,10 @@
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 @@
"#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");
}
Index: gen-mirroring-tab.c
===================================================================
RCS file: /cvs/fribidi/fribidi/gen.tab/gen-mirroring-tab.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- a/gen-mirroring-tab.c 31 May 2004 18:43:26 -0000 1.7
+++ b/gen-mirroring-tab.c 9 Jun 2004 20:01:00 -0000 1.8
@@ -1,5 +1,5 @@
/* FriBidi
- * gen-mirroring-tab.c - generate mirroring.tab.i for libfribidi
+ * gen-mirroring-tab.c - generate bidi-mirroring.i for libfribidi
*
* $Id$
* $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 @@
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 @@
while (fgets (s, sizeof s, f))
{
unsigned long i, j;
+ signed long dist;
int k;
l++;
@@ -127,10 +145,15 @@
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 @@
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 @@
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;
Index: packtab.c
===================================================================
RCS file: /cvs/fribidi/fribidi/gen.tab/packtab.c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- a/packtab.c 22 May 2004 10:35:30 -0000 1.3
+++ b/packtab.c 9 Jun 2004 20:01:00 -0000 1.4
@@ -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 @@
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 @@
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 @@
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 @@
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 @@
}
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_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 @@
" 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 @@
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);
Index: packtab.h
===================================================================
RCS file: /cvs/fribidi/fribidi/gen.tab/packtab.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- a/packtab.h 22 May 2004 10:35:30 -0000 1.2
+++ b/packtab.h 9 Jun 2004 20:01:00 -0000 1.3
@@ -30,15 +30,16 @@
#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
);
- Previous message: [FriBidi-commit] fribidi/charset fribidi-char-sets.c,1.5,1.6
- Next message: [FriBidi-commit] fribidi/lib fribidi-bidi-type.c, 1.10,
1.11 fribidi-bidi-types.h, 1.6, 1.7 fribidi-mirroring.c, 1.9,
1.10 fribidi-types.h, 1.5, 1.6 fribidi.h, 1.4, 1.5
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the FriBidi-Commit
mailing list