Lookup functions for 3-level tables.
[kopensolaris-gnu/glibc.git] / wctype / wchar-lookup.h
1 /* Copyright (C) 2000 Free Software Foundation, Inc.
2    This file is part of the GNU C Library.
3    Contributed by Bruno Haible <haible@clisp.cons.org>, 2000.
4
5    The GNU C Library is free software; you can redistribute it and/or
6    modify it under the terms of the GNU Library General Public License as
7    published by the Free Software Foundation; either version 2 of the
8    License, or (at your option) any later version.
9
10    The GNU C Library is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    Library General Public License for more details.
14
15    You should have received a copy of the GNU Library General Public
16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18    Boston, MA 02111-1307, USA.  */
19
20 /* Tables indexed by a wide character are compressed through the use
21    of a multi-level lookup.  The compression effect comes from blocks
22    that don't need particular data and from block that can share their
23    data.  */
24
25 /* Bit tables are accessed by cutting wc in four blocks of bits:
26    - the high 32-q-p bits,
27    - the next q bits,
28    - the next p bits,
29    - the next 5 bits.
30
31             +------------------+-----+-----+-----+
32      wc  =  +     32-q-p-5     |  q  |  p  |  5  |
33             +------------------+-----+-----+-----+
34
35    p and q are variable.  For 16-bit Unicode it is sufficient to
36    choose p and q such that q+p+5 <= 16.
37
38    The table contains the following uint32_t words:
39    - q+p+5,
40    - s = upper exclusive bound for wc >> (q+p+5),
41    - p+5,
42    - 2^q-1,
43    - 2^p-1,
44    - 1st-level table: s offsets, pointing into the 2nd-level table,
45    - 2nd-level table: k*2^q offsets, pointing into the 3rd-level table,
46    - 3rd-level table: j*2^p words, each containing 32 bits of data.
47 */
48
49 static __inline int
50 wctype_table_lookup (const char *table, uint32_t wc)
51 {
52   uint32_t shift1 = ((const uint32_t *) table)[0];
53   uint32_t index1 = wc >> shift1;
54   uint32_t bound = ((const uint32_t *) table)[1];
55   if (index1 < bound)
56     {
57       uint32_t lookup1 = ((const uint32_t *) table)[5 + index1];
58       if (lookup1 != 0)
59         {
60           uint32_t shift2 = ((const uint32_t *) table)[2];
61           uint32_t mask2 = ((const uint32_t *) table)[3];
62           uint32_t index2 = (wc >> shift2) & mask2;
63           uint32_t lookup2 = ((const uint32_t *)(table + lookup1))[index2];
64           if (lookup2 != 0)
65             {
66               uint32_t mask3 = ((const uint32_t *) table)[4];
67               uint32_t index3 = (wc >> 5) & mask3;
68               uint32_t lookup3 = ((const uint32_t *)(table + lookup2))[index3];
69
70               return (lookup3 >> (wc & 0x1f)) & 1;
71             }
72         }
73     }
74   return 0;
75 }
76
77 /* Byte tables are similar to bit tables, except that the addressing
78    unit is a single byte, and no 5 bits are used as a word index.  */
79
80 static __inline int
81 wcwidth_table_lookup (const char *table, uint32_t wc)
82 {
83   uint32_t shift1 = ((const uint32_t *) table)[0];
84   uint32_t index1 = wc >> shift1;
85   uint32_t bound = ((const uint32_t *) table)[1];
86   if (index1 < bound)
87     {
88       uint32_t lookup1 = ((const uint32_t *) table)[5 + index1];
89       if (lookup1 != 0)
90         {
91           uint32_t shift2 = ((const uint32_t *) table)[2];
92           uint32_t mask2 = ((const uint32_t *) table)[3];
93           uint32_t index2 = (wc >> shift2) & mask2;
94           uint32_t lookup2 = ((const uint32_t *)(table + lookup1))[index2];
95           if (lookup2 != 0)
96             {
97               uint32_t mask3 = ((const uint32_t *) table)[4];
98               uint32_t index3 = wc & mask3;
99               uint8_t lookup3 = ((const uint8_t *)(table + lookup2))[index3];
100
101               return lookup3;
102             }
103         }
104     }
105   return 0xff;
106 }
107
108 /* Mapping tables are similar to bit tables, except that the
109    addressing unit is a single signed 32-bit word, containing the
110    difference between the desired result and the argument, and no 5
111    bits are used as a word index.  */
112
113 static __inline uint32_t
114 wctrans_table_lookup (const char *table, uint32_t wc)
115 {
116   uint32_t shift1 = ((const uint32_t *) table)[0];
117   uint32_t index1 = wc >> shift1;
118   uint32_t bound = ((const uint32_t *) table)[1];
119   if (index1 < bound)
120     {
121       uint32_t lookup1 = ((const uint32_t *) table)[5 + index1];
122       if (lookup1 != 0)
123         {
124           uint32_t shift2 = ((const uint32_t *) table)[2];
125           uint32_t mask2 = ((const uint32_t *) table)[3];
126           uint32_t index2 = (wc >> shift2) & mask2;
127           uint32_t lookup2 = ((const uint32_t *)(table + lookup1))[index2];
128           if (lookup2 != 0)
129             {
130               uint32_t mask3 = ((const uint32_t *) table)[4];
131               uint32_t index3 = wc & mask3;
132               int32_t lookup3 = ((const int32_t *)(table + lookup2))[index3];
133
134               return wc + lookup3;
135             }
136         }
137     }
138   return wc;
139 }