Re: a smaller LC_CTYPE locale format

[Bruno Haible <haible at ilog dot fr>]

Addendum to last patch. Here is a more complete set of timings:

                                       before           with the patch
iswalpha
  Markus Kuhn's UTF-8-demo.txt         0.26 usec          0.13 usec
  an average ASCII only text           0.19 usec          0.13 usec
towupper
  Markus Kuhn's UTF-8-demo.txt         0.26 usec          0.13 usec
  an average ASCII only text           0.19 usec          0.13 usec
wcwidth
  Markus Kuhn's UTF-8-demo.txt         0.29 usec          0.20 usec
  an average ASCII only text           0.21 usec          0.20 usec


And here is a small additional patch. It makes the code more robust.
A wrong width table could be generated in some obscure cases without
this patch.


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

	* locale/programs/ld-ctype.c (wctype_table_get): New function.
	(wcwidth_table_get): New function.
	(wcwidth_table_add): Call it.
	(wctrans_table_get): New function.
	(wctrans_table_add): Call it.

*** glibc-20000724/locale/programs/ld-ctype.c.bak	Tue Jul 25 00:06:56 2000
--- glibc-20000724/locale/programs/ld-ctype.c	Tue Jul 25 01:53:16 2000
***************
*** 3262,3267 ****
--- 3262,3294 ----
    t->level3_alloc = t->level3_size = 0;
  }
  
+ /* Retrieve an entry.  */
+ static inline int
+ wctype_table_get (struct wctype_table *t, uint32_t wc)
+ {
+   uint32_t index1 = wc >> (t->q + t->p + 5);
+   if (index1 < t->level1_size)
+     {
+       uint32_t lookup1 = t->level1[index1];
+       if (lookup1 != ~((uint32_t) 0))
+ 	{
+ 	  uint32_t index2 = ((wc >> (t->p + 5)) & ((1 << t->q) - 1))
+ 			    + (lookup1 << t->q);
+ 	  uint32_t lookup2 = t->level2[index2];
+ 	  if (lookup2 != ~((uint32_t) 0))
+ 	    {
+ 	      uint32_t index3 = ((wc >> 5) & ((1 << t->p) - 1))
+ 				+ (lookup2 << t->p);
+ 	      uint32_t lookup3 = t->level3[index3];
+ 	      uint32_t index4 = wc & 0x1f;
+ 
+ 	      return (lookup3 >> index4) & 1;
+ 	    }
+ 	}
+     }
+   return 0;
+ }
+ 
  /* Add one entry.  */
  static void
  wctype_table_add (struct wctype_table *t, uint32_t wc)
***************
*** 3465,3470 ****
--- 3492,3523 ----
    t->level3_alloc = t->level3_size = 0;
  }
  
+ /* Retrieve an entry.  */
+ static inline uint8_t
+ wcwidth_table_get (struct wcwidth_table *t, uint32_t wc)
+ {
+   uint32_t index1 = wc >> (t->q + t->p);
+   if (index1 < t->level1_size)
+     {
+       uint32_t lookup1 = t->level1[index1];
+       if (lookup1 != ~((uint32_t) 0))
+ 	{
+ 	  uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1))
+ 			    + (lookup1 << t->q);
+ 	  uint32_t lookup2 = t->level2[index2];
+ 	  if (lookup2 != ~((uint32_t) 0))
+ 	    {
+ 	      uint32_t index3 = (wc & ((1 << t->p) - 1))
+ 				+ (lookup2 << t->p);
+ 	      uint8_t lookup3 = t->level3[index3];
+ 
+ 	      return lookup3;
+ 	    }
+ 	}
+     }
+   return 0xff;
+ }
+ 
  /* Add one entry.  */
  static void
  wcwidth_table_add (struct wcwidth_table *t, uint32_t wc, uint8_t width)
***************
*** 3474,3480 ****
    uint32_t index3 = wc & ((1 << t->p) - 1);
    size_t i, i1, i2;
  
!   if (width == 0xff)
      return;
  
    if (index1 >= t->level1_size)
--- 3527,3533 ----
    uint32_t index3 = wc & ((1 << t->p) - 1);
    size_t i, i1, i2;
  
!   if (width == wcwidth_table_get (t, wc))
      return;
  
    if (index1 >= t->level1_size)
***************
*** 3674,3679 ****
--- 3727,3758 ----
    t->level3_alloc = t->level3_size = 0;
  }
  
+ /* Retrieve an entry.  */
+ static inline uint32_t
+ wctrans_table_get (struct wctrans_table *t, uint32_t wc)
+ {
+   uint32_t index1 = wc >> (t->q + t->p);
+   if (index1 < t->level1_size)
+     {
+       uint32_t lookup1 = t->level1[index1];
+       if (lookup1 != ~((uint32_t) 0))
+ 	{
+ 	  uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1))
+ 			    + (lookup1 << t->q);
+ 	  uint32_t lookup2 = t->level2[index2];
+ 	  if (lookup2 != ~((uint32_t) 0))
+ 	    {
+ 	      uint32_t index3 = (wc & ((1 << t->p) - 1))
+ 				+ (lookup2 << t->p);
+ 	      int32_t lookup3 = t->level3[index3];
+ 
+ 	      return wc + lookup3;
+ 	    }
+ 	}
+     }
+   return wc;
+ }
+ 
  /* Add one entry.  */
  static void
  wctrans_table_add (struct wctrans_table *t, uint32_t wc, uint32_t mapped_wc)
***************
*** 3681,3691 ****
    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)
      {
--- 3760,3772 ----
    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;
    size_t i, i1, i2;
  
!   if (mapped_wc == wctrans_table_get (t, wc))
      return;
+ 
+   value = (int32_t) mapped_wc - (int32_t) wc;
  
    if (index1 >= t->level1_size)
      {