diff options
Diffstat (limited to 'glib/glib/glib-mirroring-tab')
| -rw-r--r-- | glib/glib/glib-mirroring-tab/Makefile | 11 | ||||
| -rw-r--r-- | glib/glib/glib-mirroring-tab/gen-mirroring-tab.c | 232 | ||||
| -rw-r--r-- | glib/glib/glib-mirroring-tab/packtab.c | 424 | ||||
| -rw-r--r-- | glib/glib/glib-mirroring-tab/packtab.h | 50 |
4 files changed, 717 insertions, 0 deletions
diff --git a/glib/glib/glib-mirroring-tab/Makefile b/glib/glib/glib-mirroring-tab/Makefile new file mode 100644 index 0000000..8ab193c --- /dev/null +++ b/glib/glib/glib-mirroring-tab/Makefile @@ -0,0 +1,11 @@ + +CFLAGS = `pkg-config --cflags glib-2.0` +LIBS = `pkg-config --libs glib-2.0` + + +all: gen-mirroring-tab + +gen-mirroring-tab: gen-mirroring-tab.o packtab.o + +clean: + $(RM) gen-mirroring-tab *.o diff --git a/glib/glib/glib-mirroring-tab/gen-mirroring-tab.c b/glib/glib/glib-mirroring-tab/gen-mirroring-tab.c new file mode 100644 index 0000000..6b16376 --- /dev/null +++ b/glib/glib/glib-mirroring-tab/gen-mirroring-tab.c @@ -0,0 +1,232 @@ +/* gen-mirroring-tab.c - generate gmirroringtable.h for glib + * copied from FriBidi. + * + * $Id$ + * $Author$ + * $Date$ + * $Revision$ + * $Source$ + * + * Author: + * Behdad Esfahbod, 2001, 2002, 2004 + * + * Copyright (C) 2004 Sharif FarsiWeb, Inc + * Copyright (C) 2001,2002,2004 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 <license@farsiweb.info>. + */ + +#include <glib.h> + +#include <stdlib.h> +#include <stdio.h> + +#include "packtab.h" + +#define appname "gen-mirroring-tab" +#define outputname "gmirroringtable.h" + +static void +die ( + const char *msg +) +{ + fprintf (stderr, appname ": %s\n", msg); + exit (1); +} + +static void +die2 ( + const char *fmt, + const char *p +) +{ + fprintf (stderr, appname ": "); + fprintf (stderr, fmt, p); + fprintf (stderr, "\n"); + exit (1); +} + +static void +die4 ( + const char *fmt, + unsigned long l, + unsigned long p, + unsigned long q +) +{ + fprintf (stderr, appname ": "); + fprintf (stderr, fmt, l, p, q); + fprintf (stderr, "\n"); + exit (1); +} + +#define table_name "Mir" +#define macro_name "GLIB_GET_MIRRORING" + +#define UNICODE_CHARS 0x110000 + +static signed int table[UNICODE_CHARS]; +static char buf[4000]; +static signed long max_dist; + +static void +init ( + void +) +{ + max_dist = 0; +} + +static void +clear_tab ( + void +) +{ + register gunichar c; + + for (c = 0; c < UNICODE_CHARS; c++) + table[c] = 0; +} + +static void +init_tab_mirroring_txt ( + void +) +{ + clear_tab (); +} + +static void +read_bidi_mirroring_txt ( + FILE *f +) +{ + unsigned long l; + + init_tab_mirroring_txt (); + + l = 0; + while (fgets (buf, sizeof buf, f)) + { + unsigned long i, j; + signed long dist; + int k; + const char *s = buf; + + l++; + + while (*s == ' ') + s++; + + if (s[0] == '#' || s[0] == '\0' || s[0] == '\n') + continue; + + k = sscanf (s, "%lx; %lx", &i, &j); + if (k != 2 || i >= UNICODE_CHARS || j >= UNICODE_CHARS) + die4 ("invalid pair in input at line %ld: %04lX, %04lX", l, i, j); + 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; + } +} + +static void +read_data ( + const char *data_file_type, + const char *data_file_name +) +{ + FILE *f; + + fprintf (stderr, "Reading `%s'\n", data_file_name); + if (!(f = fopen (data_file_name, "rt"))) + die2 ("error: cannot open `%s' for reading", data_file_name); + + if (!strcmp (data_file_type, "BidiMirroring.txt")) + read_bidi_mirroring_txt (f); + else + die2 ("error: unknown data-file-type %s", data_file_type); + + fclose (f); +} + +static void +gen_mirroring_tab ( + int max_depth, + const char *data_file_type +) +{ + int key_bytes; + const char *key_type; + + fprintf (stderr, + "Generating `" outputname "', it may take up to a few minutes\n"); + printf ("/* " outputname "\n * generated by " appname " " + "\n" " * from the file %s of */\n\n", data_file_type); + + printf ("#define PACKTAB_UINT8 guint8\n" + "#define PACKTAB_UINT16 guint16\n" + "#define PACKTAB_UINT32 guint32\n\n"); + + key_bytes = max_dist <= 0x7f ? 1 : max_dist < 0x7fff ? 2 : 4; + key_type = key_bytes == 1 ? "gint8" : key_bytes == 2 ? + "gint16" : "gint32"; + + if (!pack_table + (table, UNICODE_CHARS, key_bytes, 0, max_depth, 1, NULL, + key_type, table_name, macro_name "_DELTA", stdout)) + die ("error: insufficient memory, decrease max_depth"); + + printf ("#undef PACKTAB_UINT8\n" + "#undef PACKTAB_UINT16\n" "#undef PACKTAB_UINT32\n\n"); + + printf ("#define " macro_name "(x) ((x) + " macro_name "_DELTA(x))\n\n"); + + printf ("/* End of generated " outputname " */\n"); +} + +int +main ( + int argc, + const char **argv +) +{ + const char *data_file_type = "BidiMirroring.txt"; + + if (argc < 3) + die2 ("usage:\n " appname " max-lookups /path/to/%s [junk...]", + data_file_type); + + { + int max_depth = atoi (argv[1]); + const char *data_file_name = argv[2]; + + if (max_depth < 2) + die ("invalid depth"); + + init (); + read_data (data_file_type, data_file_name); + gen_mirroring_tab (max_depth, data_file_type); + } + + return 0; +} diff --git a/glib/glib/glib-mirroring-tab/packtab.c b/glib/glib/glib-mirroring-tab/packtab.c new file mode 100644 index 0000000..7c0ff5d --- /dev/null +++ b/glib/glib/glib-mirroring-tab/packtab.c @@ -0,0 +1,424 @@ +/* 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 */ diff --git a/glib/glib/glib-mirroring-tab/packtab.h b/glib/glib/glib-mirroring-tab/packtab.h new file mode 100644 index 0000000..7cab9be --- /dev/null +++ b/glib/glib/glib-mirroring-tab/packtab.h @@ -0,0 +1,50 @@ +/* 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>. + */ + +#ifndef PACKTAB_H +#define PACKTAB_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +#define packtab_version 3 + + int pack_table ( + const signed int *base, + long key_num, + int key_size, + signed int default_key, + int max_depth, + int tab_width, + const char *const *name, + const char *key_type_name, + const char *table_name, + const char *macro_name, + FILE *out + ); + +#ifdef __cplusplus +} +#endif + +#endif /* PACKTAB_H */ |