Update.

2000-07-23  Bruno Haible  <haible@clisp.cons.org>

	* wctype/wchar-lookup.h: New file.
	* wctype/iswctype.c: Include "wchar-lookup.h".
	(__iswctype): Support alternate locale format with 3-level tables.
	* wctype/iswctype_l.c (__iswctype_l): Likewise.
	* wctype/towctrans.c (__towctrans): Likewise.
	* wctype/towctrans_l.c (__towctrans_l): Likewise.
	* wctype/wcfuncs.c: Include "wchar-lookup.h".
	(__ctype32_wctype, __ctype32_wctrans): Declare external.
	(__iswalnum, __iswalpha, __iswcntrl, __iswdigit, __iswlower,
	__iswgraph, __iswprint, __iswpunct, __iswspace, __iswupper,
	__iswxdigit, towlower, towupper): Support alternate locale format
	with 3-level tables.
	* wctype/wcextra.c (iswblank): Likewise.
	* wctype/wcfuncs_l.c: Include "wchar-lookup.h".
	(__iswalnum_l, __iswalpha_l, __iswcntrl_l, __iswdigit_l, __iswlower_l,
	__iswgraph_l, __iswprint_l, __iswpunct_l, __iswspace_l, __iswupper_l,
	__iswxdigit_l, __towlower_l, __towupper_l): Support alternate locale
	format with 3-level tables.
	* wctype/wcextra_l.c (__iswblank_l): Likewise.
	* wctype/wctype.c (__wctype): Likewise.  In the alternate locale
	format, return a 3-level table pointer.
	* wctype/wctype_l.c (__wctype_l): Likewise.
	* wctype/wctrans.c (wctrans): Likewise.
	* wctype/wctype.h (__ISwupper, __ISwlower, __ISwalpha, __ISwdigit,
	__ISwxdigit, __ISwspace, __ISwprint, __ISwgraph, __ISwblank,
	__ISwcntrl, __ISwpunct, __ISwalnum): New enum values.
	(iswctype): Remove macro definition.
	* wcsmbs/wcwidth.h: Include "wchar-lookup.h".
	(internal_wcwidth): Support alternate locale format with 3-level
	tables.
	* locale/langinfo.h (_NL_CTYPE_CLASS_OFFSET, _NL_CTYPE_MAP_OFFSET):
	New nl_items.
	* locale/categories.def (_NL_CTYPE_CLASS_OFFSET, _NL_CTYPE_MAP_OFFSET):
	Define them as being type "word".
	* locale/C-ctype.c (_nl_C_LC_CTYPE): Add initializers for them.
	* ctype/ctype-info.c (__ctype32_wctype, __ctype32_wctrans,
	__ctype32_width): New exported variables.
	* locale/lc-ctype.c (_nl_postload_ctype): Initialize them in the
	alternate locale format. Don't initialize __ctype_names and
	__ctype_width in the alternate locale format.
	* locale/programs/localedef.h (oldstyle_tables): New declaration.
	* locale/programs/localedef.c (oldstyle_tables): New variable.
	(OPT_OLDSTYLE): New macro.
	(options): Add --old-style option.
	(parse_opt): Handle --old-style option.
	* locale/programs/ld-ctype.c (locale_ctype_t): Add class_offset,
	map_offset, class_3level, map_3level, width_3level members.
	(ctype_output): Support for alternate locale format: Computation of
	nelems changes. _NL_CTYPE_TOUPPER32, _NL_CTYPE_TOLOWER32 and
	_NL_CTYPE_CLASS32 only 256 characters. _NL_CTYPE_NAMES empty.
	New fields _NL_CTYPE_CLASS_OFFSET, _NL_CTYPE_MAP_OFFSET. Field
	_NL_CTYPE_WIDTH now contains the three-level table. Extra elems
	now contain both class and map tables.
	(struct wctype_table): New type.
	(wctype_table_init, wctype_table_add, wctype_table_finalize): New
	functions.
	(struct wcwidth_table): New type.
	(wcwidth_table_init, wcwidth_table_add, wcwidth_table_finalize): New
	functions.
	(struct wctrans_table): New type.
	(wctrans_table_init, wctrans_table_add, wctrans_table_finalize): New
	functions.
	(allocate_arrays): Support for alternate locale format: Set
	plane_size and plane_cnt to 0. Restrict ctype->ctype32_b to the first
	256 characters. Compute ctype->class_3level. Restrict ctype->map32[idx]
	to the first 256 characters. Compute ctype->map_3level. Set
	ctype->class_offset and ctype->map_offset. Compute ctype->width_3level
	instead of ctype->width.

3 files changed, 1033 insertions, 171 deletions

diff --git a/locale/programs/ld-ctype.c b/locale/programs/ld-ctype.c
index 5dfcec3339..14b174e9f1 100644
--- a/locale/programs/ld-ctype.c
+++ b/locale/programs/ld-ctype.c
@@ -125,6 +125,7 @@ struct locale_ctype_t
   size_t class_collection_max;
   size_t class_collection_act;
   uint32_t class_done;
+  uint32_t class_offset;
 
   struct charseq **mbdigits;
   size_t mbdigits_act;
@@ -148,6 +149,7 @@ struct locale_ctype_t
   size_t map_collection_nr;
   size_t last_map_idx;
   int tomap_done[MAX_NR_CHARMAP];
+  uint32_t map_offset;
 
   /* Transliteration information.  */
   const char *translit_copy_locale;
@@ -168,9 +170,12 @@ struct locale_ctype_t
   uint32_t *names;
   uint32_t **map;
   uint32_t **map32;
+  struct iovec *class_3level;
+  struct iovec *map_3level;
   uint32_t *class_name_ptr;
   uint32_t *map_name_ptr;
   unsigned char *width;
+  struct iovec width_3level;
   uint32_t mb_cur_max;
   const char *codeset_name;
   uint32_t *translit_from_idx;
@@ -834,7 +839,9 @@ ctype_output (struct localedef_t *locale, struct charmap_t *charmap,
   static const char nulbytes[4] = { 0, 0, 0, 0 };
   struct locale_ctype_t *ctype = locale->categories[LC_CTYPE].ctype;
   const size_t nelems = (_NL_ITEM_INDEX (_NL_NUM_LC_CTYPE)
-			 + (ctype->map_collection_nr - 2));
+			 + (oldstyle_tables
+			    ? (ctype->map_collection_nr - 2)
+			    : (ctype->nr_charclass + ctype->map_collection_nr)));
   struct iovec iov[2 + nelems + ctype->nr_charclass
 		  + ctype->map_collection_nr + 2];
   struct locale_file data;
@@ -893,21 +900,28 @@ ctype_output (struct localedef_t *locale, struct charmap_t *charmap,
 
 	  CTYPE_DATA (_NL_CTYPE_TOUPPER32,
 		      ctype->map32[0],
-		      (ctype->plane_size * ctype->plane_cnt)
+		      (oldstyle_tables ? ctype->plane_size * ctype->plane_cnt : 256)
 		      * sizeof (uint32_t));
 	  CTYPE_DATA (_NL_CTYPE_TOLOWER32,
 		      ctype->map32[1],
-		      (ctype->plane_size * ctype->plane_cnt)
+		      (oldstyle_tables ? ctype->plane_size * ctype->plane_cnt : 256)
 		      * sizeof (uint32_t));
 
 	  CTYPE_DATA (_NL_CTYPE_CLASS32,
 		      ctype->ctype32_b,
-		      (ctype->plane_size * ctype->plane_cnt
-		       * sizeof (char_class32_t)));
+		      (oldstyle_tables ? ctype->plane_size * ctype->plane_cnt : 256)
+		      * sizeof (char_class32_t));
 
 	  CTYPE_DATA (_NL_CTYPE_NAMES,
-		      ctype->names, (ctype->plane_size * ctype->plane_cnt
-				     * sizeof (uint32_t)));
+		      ctype->names,
+		      (oldstyle_tables ? ctype->plane_size * ctype->plane_cnt : 0)
+		      * sizeof (uint32_t));
+
+	  CTYPE_DATA (_NL_CTYPE_CLASS_OFFSET,
+		      &ctype->class_offset, sizeof (uint32_t));
+
+	  CTYPE_DATA (_NL_CTYPE_MAP_OFFSET,
+		      &ctype->map_offset, sizeof (uint32_t));
 
 	  CTYPE_DATA (_NL_CTYPE_TRANSLIT_TAB_SIZE,
 		      &ctype->translit_idx_size, sizeof (uint32_t));
@@ -969,8 +983,12 @@ ctype_output (struct localedef_t *locale, struct charmap_t *charmap,
 	    break;
 
 	  CTYPE_DATA (_NL_CTYPE_WIDTH,
-		      ctype->width,
-		      (ctype->plane_size * ctype->plane_cnt + 3) & ~3ul);
+		      (oldstyle_tables
+		       ? ctype->width
+		       : ctype->width_3level.iov_base),
+		      (oldstyle_tables
+		       ? (ctype->plane_size * ctype->plane_cnt + 3) & ~3ul
+		       : ctype->width_3level.iov_len));
 
 	  CTYPE_DATA (_NL_CTYPE_MB_CUR_MAX,
 		      &ctype->mb_cur_max, sizeof (uint32_t));
@@ -1135,14 +1153,32 @@ ctype_output (struct localedef_t *locale, struct charmap_t *charmap,
       else
 	{
 	  /* Handle extra maps.  */
-	  size_t nr = (elem - _NL_ITEM_INDEX (_NL_NUM_LC_CTYPE)) + 2;
+	  if (oldstyle_tables)
+	    {
+	      size_t nr = (elem - _NL_ITEM_INDEX (_NL_NUM_LC_CTYPE)) + 2;
 
-	  iov[2 + elem + offset].iov_base = ctype->map32[nr];
-	  iov[2 + elem + offset].iov_len = ((ctype->plane_size
-					     * ctype->plane_cnt)
-					    * sizeof (uint32_t));
+	      iov[2 + elem + offset].iov_base = ctype->map32[nr];
+	      iov[2 + elem + offset].iov_len = ((ctype->plane_size
+						 * ctype->plane_cnt)
+						* sizeof (uint32_t));
 
-	  idx[elem + 1] = idx[elem] + iov[2 + elem + offset].iov_len;
+	      idx[elem + 1] = idx[elem] + iov[2 + elem + offset].iov_len;
+	    }
+	  else
+	    {
+	      size_t nr = elem - _NL_ITEM_INDEX (_NL_NUM_LC_CTYPE);
+	      if (nr < ctype->nr_charclass)
+		{
+		  iov[2 + elem + offset] = ctype->class_3level[nr];
+		}
+	      else
+		{
+		  nr -= ctype->nr_charclass;
+		  assert (nr < ctype->map_collection_nr);
+		  iov[2 + elem + offset] = ctype->map_3level[nr];
+		}
+	      idx[elem + 1] = idx[elem] + iov[2 + elem + offset].iov_len;
+	    }
 	}
     }
 
@@ -3194,6 +3230,628 @@ no output digits defined and none of the standard names in the charmap"));
 }
 
 
+/* Construction of sparse 3-level tables.
+   See wchar-lookup.h for their structure and the meaning of p and q.  */
+
+struct wctype_table
+{
+  /* Parameters.  */
+  unsigned int p;
+  unsigned int q;
+  /* Working representation.  */
+  size_t level1_alloc;
+  size_t level1_size;
+  uint32_t *level1;
+  size_t level2_alloc;
+  size_t level2_size;
+  uint32_t *level2;
+  size_t level3_alloc;
+  size_t level3_size;
+  uint32_t *level3;
+  /* Compressed representation.  */
+  size_t result_size;
+  char *result;
+};
+
+/* Initialize.  Assumes t->p and t->q have already been set.  */
+static inline void
+wctype_table_init (struct wctype_table *t)
+{
+  t->level1_alloc = t->level1_size = 0;
+  t->level2_alloc = t->level2_size = 0;
+  t->level3_alloc = t->level3_size = 0;
+}
+
+/* Add one entry.  */
+static void
+wctype_table_add (struct wctype_table *t, uint32_t wc)
+{
+  uint32_t index1 = wc >> (t->q + t->p + 5);
+  uint32_t index2 = (wc >> (t->p + 5)) & ((1 << t->q) - 1);
+  uint32_t index3 = (wc >> 5) & ((1 << t->p) - 1);
+  uint32_t index4 = wc & 0x1f;
+  size_t i, i1, i2;
+
+  if (index1 >= t->level1_size)
+    {
+      if (index1 >= t->level1_alloc)
+	{
+	  size_t alloc = 2 * t->level1_alloc;
+	  if (alloc <= index1)
+	    alloc = index1 + 1;
+	  t->level1 = (t->level1_alloc > 0
+		       ? (uint32_t *) xrealloc ((char *) t->level1,
+						alloc * sizeof (uint32_t))
+		       : (uint32_t *) xmalloc (alloc * sizeof (uint32_t)));
+	  t->level1_alloc = alloc;
+	}
+      while (index1 >= t->level1_size)
+	t->level1[t->level1_size++] = ~((uint32_t) 0);
+    }
+
+  if (t->level1[index1] == ~((uint32_t) 0))
+    {
+      if (t->level2_size == t->level2_alloc)
+	{
+	  size_t alloc = 2 * t->level2_alloc + 1;
+	  t->level2 = (t->level2_alloc > 0
+		       ? (uint32_t *) xrealloc ((char *) t->level2,
+						(alloc << t->q) * sizeof (uint32_t))
+		       : (uint32_t *) xmalloc ((alloc << t->q) * sizeof (uint32_t)));
+	  t->level2_alloc = alloc;
+	}
+      i1 = t->level2_size << t->q;
+      i2 = (t->level2_size + 1) << t->q;
+      for (i = i1; i < i2; i++)
+	t->level2[i] = ~((uint32_t) 0);
+      t->level1[index1] = t->level2_size++;
+    }
+
+  index2 += t->level1[index1] << t->q;
+
+  if (t->level2[index2] == ~((uint32_t) 0))
+    {
+      if (t->level3_size == t->level3_alloc)
+	{
+	  size_t alloc = 2 * t->level3_alloc + 1;
+	  t->level3 = (t->level3_alloc > 0
+		       ? (uint32_t *) xrealloc ((char *) t->level3,
+						(alloc << t->p) * sizeof (uint32_t))
+		       : (uint32_t *) xmalloc ((alloc << t->p) * sizeof (uint32_t)));
+	  t->level3_alloc = alloc;
+	}
+      i1 = t->level3_size << t->p;
+      i2 = (t->level3_size + 1) << t->p;
+      for (i = i1; i < i2; i++)
+	t->level3[i] = 0;
+      t->level2[index2] = t->level3_size++;
+    }
+
+  index3 += t->level2[index2] << t->p;
+
+  t->level3[index3] |= (uint32_t)1 << index4;
+}
+
+/* Finalize and shrink.  */
+static void
+wctype_table_finalize (struct wctype_table *t)
+{
+  size_t i, j, k;
+  uint32_t reorder3[t->level3_size];
+  uint32_t reorder2[t->level2_size];
+  uint32_t level1_offset, level2_offset, level3_offset;
+
+  /* Uniquify level3 blocks.  */
+  k = 0;
+  for (j = 0; j < t->level3_size; j++)
+    {
+      for (i = 0; i < k; i++)
+	if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
+		    (1 << t->p) * sizeof (uint32_t)) == 0)
+	  break;
+      /* Relocate block j to block i.  */
+      reorder3[j] = i;
+      if (i == k)
+	{
+	  if (i != j)
+	    memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
+		    (1 << t->p) * sizeof (uint32_t));
+	  k++;
+	}
+    }
+  t->level3_size = k;
+
+  for (i = 0; i < (t->level2_size << t->q); i++)
+    if (t->level2[i] != ~((uint32_t) 0))
+      t->level2[i] = reorder3[t->level2[i]];
+
+  /* Uniquify level2 blocks.  */
+  k = 0;
+  for (j = 0; j < t->level2_size; j++)
+    {
+      for (i = 0; i < k; i++)
+	if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
+		    (1 << t->q) * sizeof (uint32_t)) == 0)
+	  break;
+      /* Relocate block j to block i.  */
+      reorder2[j] = i;
+      if (i == k)
+	{
+	  if (i != j)
+	    memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
+		    (1 << t->q) * sizeof (uint32_t));
+	  k++;
+	}
+    }
+  t->level2_size = k;
+
+  for (i = 0; i < t->level1_size; i++)
+    if (t->level1[i] != ~((uint32_t) 0))
+      t->level1[i] = reorder2[t->level1[i]];
+
+  /* Create and fill the resulting compressed representation.  */
+  t->result_size =
+    5 * sizeof (uint32_t)
+    + t->level1_size * sizeof (uint32_t)
+    + (t->level2_size << t->q) * sizeof (uint32_t)
+    + (t->level3_size << t->p) * sizeof (uint32_t);
+  t->result = (char *) xmalloc (t->result_size);
+
+  level1_offset =
+    5 * sizeof (uint32_t);
+  level2_offset =
+    5 * sizeof (uint32_t)
+    + t->level1_size * sizeof (uint32_t);
+  level3_offset =
+    5 * sizeof (uint32_t)
+    + t->level1_size * sizeof (uint32_t)
+    + (t->level2_size << t->q) * sizeof (uint32_t);
+
+  ((uint32_t *) t->result)[0] = t->q + t->p + 5;
+  ((uint32_t *) t->result)[1] = t->level1_size;
+  ((uint32_t *) t->result)[2] = t->p + 5;
+  ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
+  ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
+
+  for (i = 0; i < t->level1_size; i++)
+    ((uint32_t *) (t->result + level1_offset))[i] =
+      (t->level1[i] == ~((uint32_t) 0)
+       ? 0
+       : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
+
+  for (i = 0; i < (t->level2_size << t->q); i++)
+    ((uint32_t *) (t->result + level2_offset))[i] =
+      (t->level2[i] == ~((uint32_t) 0)
+       ? 0
+       : (t->level2[i] << t->p) * sizeof (uint32_t) + level3_offset);
+
+  for (i = 0; i < (t->level3_size << t->p); i++)
+    ((uint32_t *) (t->result + level3_offset))[i] = t->level3[i];
+
+  if (t->level1_alloc > 0)
+    free (t->level1);
+  if (t->level2_alloc > 0)
+    free (t->level2);
+  if (t->level3_alloc > 0)
+    free (t->level3);
+}
+
+struct wcwidth_table
+{
+  /* Parameters.  */
+  unsigned int p;
+  unsigned int q;
+  /* Working representation.  */
+  size_t level1_alloc;
+  size_t level1_size;
+  uint32_t *level1;
+  size_t level2_alloc;
+  size_t level2_size;
+  uint32_t *level2;
+  size_t level3_alloc;
+  size_t level3_size;
+  uint8_t *level3;
+  /* Compressed representation.  */
+  size_t result_size;
+  char *result;
+};
+
+/* Initialize.  Assumes t->p and t->q have already been set.  */
+static inline void
+wcwidth_table_init (struct wcwidth_table *t)
+{
+  t->level1_alloc = t->level1_size = 0;
+  t->level2_alloc = t->level2_size = 0;
+  t->level3_alloc = t->level3_size = 0;
+}
+
+/* Add one entry.  */
+static void
+wcwidth_table_add (struct wcwidth_table *t, uint32_t wc, uint8_t width)
+{
+  uint32_t index1 = wc >> (t->q + t->p);
+  uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1);
+  uint32_t index3 = wc & ((1 << t->p) - 1);
+  size_t i, i1, i2;
+
+  if (width == 0xff)
+    return;
+
+  if (index1 >= t->level1_size)
+    {
+      if (index1 >= t->level1_alloc)
+	{
+	  size_t alloc = 2 * t->level1_alloc;
+	  if (alloc <= index1)
+	    alloc = index1 + 1;
+	  t->level1 = (t->level1_alloc > 0
+		       ? (uint32_t *) xrealloc ((char *) t->level1,
+						alloc * sizeof (uint32_t))
+		       : (uint32_t *) xmalloc (alloc * sizeof (uint32_t)));
+	  t->level1_alloc = alloc;
+	}
+      while (index1 >= t->level1_size)
+	t->level1[t->level1_size++] = ~((uint32_t) 0);
+    }
+
+  if (t->level1[index1] == ~((uint32_t) 0))
+    {
+      if (t->level2_size == t->level2_alloc)
+	{
+	  size_t alloc = 2 * t->level2_alloc + 1;
+	  t->level2 = (t->level2_alloc > 0
+		       ? (uint32_t *) xrealloc ((char *) t->level2,
+						(alloc << t->q) * sizeof (uint32_t))
+		       : (uint32_t *) xmalloc ((alloc << t->q) * sizeof (uint32_t)));
+	  t->level2_alloc = alloc;
+	}
+      i1 = t->level2_size << t->q;
+      i2 = (t->level2_size + 1) << t->q;
+      for (i = i1; i < i2; i++)
+	t->level2[i] = ~((uint32_t) 0);
+      t->level1[index1] = t->level2_size++;
+    }
+
+  index2 += t->level1[index1] << t->q;
+
+  if (t->level2[index2] == ~((uint32_t) 0))
+    {
+      if (t->level3_size == t->level3_alloc)
+	{
+	  size_t alloc = 2 * t->level3_alloc + 1;
+	  t->level3 = (t->level3_alloc > 0
+		       ? (uint8_t *) xrealloc ((char *) t->level3,
+					       (alloc << t->p) * sizeof (uint8_t))
+		       : (uint8_t *) xmalloc ((alloc << t->p) * sizeof (uint8_t)));
+	  t->level3_alloc = alloc;
+	}
+      i1 = t->level3_size << t->p;
+      i2 = (t->level3_size + 1) << t->p;
+      for (i = i1; i < i2; i++)
+	t->level3[i] = 0xff;
+      t->level2[index2] = t->level3_size++;
+    }
+
+  index3 += t->level2[index2] << t->p;
+
+  t->level3[index3] = width;
+}
+
+/* Finalize and shrink.  */
+static void
+wcwidth_table_finalize (struct wcwidth_table *t)
+{
+  size_t i, j, k;
+  uint32_t reorder3[t->level3_size];
+  uint32_t reorder2[t->level2_size];
+  uint32_t level1_offset, level2_offset, level3_offset, last_offset;
+
+  /* Uniquify level3 blocks.  */
+  k = 0;
+  for (j = 0; j < t->level3_size; j++)
+    {
+      for (i = 0; i < k; i++)
+	if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
+		    (1 << t->p) * sizeof (uint8_t)) == 0)
+	  break;
+      /* Relocate block j to block i.  */
+      reorder3[j] = i;
+      if (i == k)
+	{
+	  if (i != j)
+	    memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
+		    (1 << t->p) * sizeof (uint8_t));
+	  k++;
+	}
+    }
+  t->level3_size = k;
+
+  for (i = 0; i < (t->level2_size << t->q); i++)
+    if (t->level2[i] != ~((uint32_t) 0))
+      t->level2[i] = reorder3[t->level2[i]];
+
+  /* Uniquify level2 blocks.  */
+  k = 0;
+  for (j = 0; j < t->level2_size; j++)
+    {
+      for (i = 0; i < k; i++)
+	if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
+		    (1 << t->q) * sizeof (uint32_t)) == 0)
+	  break;
+      /* Relocate block j to block i.  */
+      reorder2[j] = i;
+      if (i == k)
+	{
+	  if (i != j)
+	    memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
+		    (1 << t->q) * sizeof (uint32_t));
+	  k++;
+	}
+    }
+  t->level2_size = k;
+
+  for (i = 0; i < t->level1_size; i++)
+    if (t->level1[i] != ~((uint32_t) 0))
+      t->level1[i] = reorder2[t->level1[i]];
+
+  /* Create and fill the resulting compressed representation.  */
+  last_offset =
+    5 * sizeof (uint32_t)
+    + t->level1_size * sizeof (uint32_t)
+    + (t->level2_size << t->q) * sizeof (uint32_t)
+    + (t->level3_size << t->p) * sizeof (uint8_t);
+  t->result_size = (last_offset + 3) & ~3ul;
+  t->result = (char *) xmalloc (t->result_size);
+
+  level1_offset =
+    5 * sizeof (uint32_t);
+  level2_offset =
+    5 * sizeof (uint32_t)
+    + t->level1_size * sizeof (uint32_t);
+  level3_offset =
+    5 * sizeof (uint32_t)
+    + t->level1_size * sizeof (uint32_t)
+    + (t->level2_size << t->q) * sizeof (uint32_t);
+
+  ((uint32_t *) t->result)[0] = t->q + t->p;
+  ((uint32_t *) t->result)[1] = t->level1_size;
+  ((uint32_t *) t->result)[2] = t->p;
+  ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
+  ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
+
+  for (i = 0; i < t->level1_size; i++)
+    ((uint32_t *) (t->result + level1_offset))[i] =
+      (t->level1[i] == ~((uint32_t) 0)
+       ? 0
+       : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
+
+  for (i = 0; i < (t->level2_size << t->q); i++)
+    ((uint32_t *) (t->result + level2_offset))[i] =
+      (t->level2[i] == ~((uint32_t) 0)
+       ? 0
+       : (t->level2[i] << t->p) * sizeof (uint8_t) + level3_offset);
+
+  for (i = 0; i < (t->level3_size << t->p); i++)
+    ((uint8_t *) (t->result + level3_offset))[i] = t->level3[i];
+
+  if (last_offset < t->result_size)
+    memset (t->result + last_offset, 0, t->result_size - last_offset);
+
+  if (t->level1_alloc > 0)
+    free (t->level1);
+  if (t->level2_alloc > 0)
+    free (t->level2);
+  if (t->level3_alloc > 0)
+    free (t->level3);
+}
+
+struct wctrans_table
+{
+  /* Parameters.  */
+  unsigned int p;
+  unsigned int q;
+  /* Working representation.  */
+  size_t level1_alloc;
+  size_t level1_size;
+  uint32_t *level1;
+  size_t level2_alloc;
+  size_t level2_size;
+  uint32_t *level2;
+  size_t level3_alloc;
+  size_t level3_size;
+  int32_t *level3;
+  /* Compressed representation.  */
+  size_t result_size;
+  char *result;
+};
+
+/* Initialize.  Assumes t->p and t->q have already been set.  */
+static inline void
+wctrans_table_init (struct wctrans_table *t)
+{
+  t->level1_alloc = t->level1_size = 0;
+  t->level2_alloc = t->level2_size = 0;
+  t->level3_alloc = t->level3_size = 0;
+}
+
+/* Add one entry.  */
+static void
+wctrans_table_add (struct wctrans_table *t, uint32_t wc, uint32_t mapped_wc)
+{
+  uint32_t index1 = wc >> (t->q + t->p);
+  uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1);
+  uint32_t index3 = wc & ((1 << t->p) - 1);
+  int32_t value = (int32_t) mapped_wc - (int32_t) wc;
+  size_t i, i1, i2;
+
+  if (value == 0)
+    return;
+
+  if (index1 >= t->level1_size)
+    {
+      if (index1 >= t->level1_alloc)
+	{
+	  size_t alloc = 2 * t->level1_alloc;
+	  if (alloc <= index1)
+	    alloc = index1 + 1;
+	  t->level1 = (t->level1_alloc > 0
+		       ? (uint32_t *) xrealloc ((char *) t->level1,
+						alloc * sizeof (uint32_t))
+		       : (uint32_t *) xmalloc (alloc * sizeof (uint32_t)));
+	  t->level1_alloc = alloc;
+	}
+      while (index1 >= t->level1_size)
+	t->level1[t->level1_size++] = ~((uint32_t) 0);
+    }
+
+  if (t->level1[index1] == ~((uint32_t) 0))
+    {
+      if (t->level2_size == t->level2_alloc)
+	{
+	  size_t alloc = 2 * t->level2_alloc + 1;
+	  t->level2 = (t->level2_alloc > 0
+		       ? (uint32_t *) xrealloc ((char *) t->level2,
+						(alloc << t->q) * sizeof (uint32_t))
+		       : (uint32_t *) xmalloc ((alloc << t->q) * sizeof (uint32_t)));
+	  t->level2_alloc = alloc;
+	}
+      i1 = t->level2_size << t->q;
+      i2 = (t->level2_size + 1) << t->q;
+      for (i = i1; i < i2; i++)
+	t->level2[i] = ~((uint32_t) 0);
+      t->level1[index1] = t->level2_size++;