aboutsummaryrefslogtreecommitdiff
path: root/libbb
diff options
context:
space:
mode:
Diffstat (limited to 'libbb')
-rw-r--r--libbb/unicode_wcwidth.c356
1 files changed, 306 insertions, 50 deletions
diff --git a/libbb/unicode_wcwidth.c b/libbb/unicode_wcwidth.c
index 515c084c1..8d301f7c3 100644
--- a/libbb/unicode_wcwidth.c
+++ b/libbb/unicode_wcwidth.c
@@ -65,22 +65,49 @@ struct interval {
65}; 65};
66 66
67/* auxiliary function for binary search in interval table */ 67/* auxiliary function for binary search in interval table */
68static int in_table(unsigned ucs, const struct interval *table, unsigned max) 68static int in_interval_table(unsigned ucs, const struct interval *table, unsigned max)
69{ 69{
70 unsigned min = 0; 70 unsigned min;
71 unsigned mid; 71 unsigned mid;
72 72
73 if (ucs < table[0].first || ucs > table[max].last) 73 if (ucs < table[0].first || ucs > table[max].last)
74 return 0; 74 return 0;
75 75
76 min = 0;
76 while (max >= min) { 77 while (max >= min) {
77 mid = (min + max) / 2; 78 mid = (min + max) / 2;
78 if (ucs > table[mid].last) 79 if (ucs > table[mid].last)
79 min = mid + 1; 80 min = mid + 1;
80 else if (ucs < table[mid].first) 81 else if (ucs < table[mid].first)
81 max = mid - 1; 82 max = mid - 1;
82 else 83 else
83 return 1; 84 return 1;
85 }
86 return 0;
87}
88
89static int in_uint16_table(unsigned ucs, const uint16_t *table, unsigned max)
90{
91 unsigned min;
92 unsigned mid;
93 unsigned first, last;
94
95 first = table[0] >> 2;
96 last = first + (table[0] & 3);
97 if (ucs < first || ucs > last)
98 return 0;
99
100 min = 0;
101 while (max >= min) {
102 mid = (min + max) / 2;
103 first = table[mid] >> 2;
104 last = first + (table[mid] & 3);
105 if (ucs > last)
106 min = mid + 1;
107 else if (ucs < first)
108 max = mid - 1;
109 else
110 return 1;
84 } 111 }
85 return 0; 112 return 0;
86} 113}
@@ -122,49 +149,276 @@ static int wcwidth(unsigned ucs)
122 /* sorted list of non-overlapping intervals of non-spacing characters */ 149 /* sorted list of non-overlapping intervals of non-spacing characters */
123 /* generated by "uniset +cat=Me +cat=Mn +cat=Cf -00AD +1160-11FF +200B c" */ 150 /* generated by "uniset +cat=Me +cat=Mn +cat=Cf -00AD +1160-11FF +200B c" */
124 static const struct interval combining[] = { 151 static const struct interval combining[] = {
125 { 0x0300, 0x036F }, { 0x0483, 0x0486 }, { 0x0488, 0x0489 }, 152#define BIG_(a,b) { a, b },
126 { 0x0591, 0x05BD }, { 0x05BF, 0x05BF }, { 0x05C1, 0x05C2 }, 153#define PAIR(a,b)
127 { 0x05C4, 0x05C5 }, { 0x05C7, 0x05C7 }, { 0x0600, 0x0603 }, 154 /* PAIR if < 0x4000 and no more than 4 chars big */
128 { 0x0610, 0x0615 }, { 0x064B, 0x065E }, { 0x0670, 0x0670 }, 155 BIG_(0x0300, 0x036F)
129 { 0x06D6, 0x06E4 }, { 0x06E7, 0x06E8 }, { 0x06EA, 0x06ED }, 156 PAIR(0x0483, 0x0486)
130 { 0x070F, 0x070F }, { 0x0711, 0x0711 }, { 0x0730, 0x074A }, 157 PAIR(0x0488, 0x0489)
131 { 0x07A6, 0x07B0 }, { 0x07EB, 0x07F3 }, { 0x0901, 0x0902 }, 158 BIG_(0x0591, 0x05BD)
132 { 0x093C, 0x093C }, { 0x0941, 0x0948 }, { 0x094D, 0x094D }, 159 PAIR(0x05BF, 0x05BF)
133 { 0x0951, 0x0954 }, { 0x0962, 0x0963 }, { 0x0981, 0x0981 }, 160 PAIR(0x05C1, 0x05C2)
134 { 0x09BC, 0x09BC }, { 0x09C1, 0x09C4 }, { 0x09CD, 0x09CD }, 161 PAIR(0x05C4, 0x05C5)
135 { 0x09E2, 0x09E3 }, { 0x0A01, 0x0A02 }, { 0x0A3C, 0x0A3C }, 162 PAIR(0x05C7, 0x05C7)
136 { 0x0A41, 0x0A42 }, { 0x0A47, 0x0A48 }, { 0x0A4B, 0x0A4D }, 163 PAIR(0x0600, 0x0603)
137 { 0x0A70, 0x0A71 }, { 0x0A81, 0x0A82 }, { 0x0ABC, 0x0ABC }, 164 BIG_(0x0610, 0x0615)
138 { 0x0AC1, 0x0AC5 }, { 0x0AC7, 0x0AC8 }, { 0x0ACD, 0x0ACD }, 165 BIG_(0x064B, 0x065E)
139 { 0x0AE2, 0x0AE3 }, { 0x0B01, 0x0B01 }, { 0x0B3C, 0x0B3C }, 166 PAIR(0x0670, 0x0670)
140 { 0x0B3F, 0x0B3F }, { 0x0B41, 0x0B43 }, { 0x0B4D, 0x0B4D }, 167 BIG_(0x06D6, 0x06E4)
141 { 0x0B56, 0x0B56 }, { 0x0B82, 0x0B82 }, { 0x0BC0, 0x0BC0 }, 168 PAIR(0x06E7, 0x06E8)
142 { 0x0BCD, 0x0BCD }, { 0x0C3E, 0x0C40 }, { 0x0C46, 0x0C48 }, 169 PAIR(0x06EA, 0x06ED)
143 { 0x0C4A, 0x0C4D }, { 0x0C55, 0x0C56 }, { 0x0CBC, 0x0CBC }, 170 PAIR(0x070F, 0x070F)
144 { 0x0CBF, 0x0CBF }, { 0x0CC6, 0x0CC6 }, { 0x0CCC, 0x0CCD }, 171 PAIR(0x0711, 0x0711)
145 { 0x0CE2, 0x0CE3 }, { 0x0D41, 0x0D43 }, { 0x0D4D, 0x0D4D }, 172 BIG_(0x0730, 0x074A)
146 { 0x0DCA, 0x0DCA }, { 0x0DD2, 0x0DD4 }, { 0x0DD6, 0x0DD6 }, 173 BIG_(0x07A6, 0x07B0)
147 { 0x0E31, 0x0E31 }, { 0x0E34, 0x0E3A }, { 0x0E47, 0x0E4E }, 174 BIG_(0x07EB, 0x07F3)
148 { 0x0EB1, 0x0EB1 }, { 0x0EB4, 0x0EB9 }, { 0x0EBB, 0x0EBC }, 175 PAIR(0x0901, 0x0902)
149 { 0x0EC8, 0x0ECD }, { 0x0F18, 0x0F19 }, { 0x0F35, 0x0F35 }, 176 PAIR(0x093C, 0x093C)
150 { 0x0F37, 0x0F37 }, { 0x0F39, 0x0F39 }, { 0x0F71, 0x0F7E }, 177 BIG_(0x0941, 0x0948)
151 { 0x0F80, 0x0F84 }, { 0x0F86, 0x0F87 }, { 0x0F90, 0x0F97 }, 178 PAIR(0x094D, 0x094D)
152 { 0x0F99, 0x0FBC }, { 0x0FC6, 0x0FC6 }, { 0x102D, 0x1030 }, 179 PAIR(0x0951, 0x0954)
153 { 0x1032, 0x1032 }, { 0x1036, 0x1037 }, { 0x1039, 0x1039 }, 180 PAIR(0x0962, 0x0963)
154 { 0x1058, 0x1059 }, { 0x1160, 0x11FF }, { 0x135F, 0x135F }, 181 PAIR(0x0981, 0x0981)
155 { 0x1712, 0x1714 }, { 0x1732, 0x1734 }, { 0x1752, 0x1753 }, 182 PAIR(0x09BC, 0x09BC)
156 { 0x1772, 0x1773 }, { 0x17B4, 0x17B5 }, { 0x17B7, 0x17BD }, 183 PAIR(0x09C1, 0x09C4)
157 { 0x17C6, 0x17C6 }, { 0x17C9, 0x17D3 }, { 0x17DD, 0x17DD }, 184 PAIR(0x09CD, 0x09CD)
158 { 0x180B, 0x180D }, { 0x18A9, 0x18A9 }, { 0x1920, 0x1922 }, 185 PAIR(0x09E2, 0x09E3)
159 { 0x1927, 0x1928 }, { 0x1932, 0x1932 }, { 0x1939, 0x193B }, 186 PAIR(0x0A01, 0x0A02)
160 { 0x1A17, 0x1A18 }, { 0x1B00, 0x1B03 }, { 0x1B34, 0x1B34 }, 187 PAIR(0x0A3C, 0x0A3C)
161 { 0x1B36, 0x1B3A }, { 0x1B3C, 0x1B3C }, { 0x1B42, 0x1B42 }, 188 PAIR(0x0A41, 0x0A42)
162 { 0x1B6B, 0x1B73 }, { 0x1DC0, 0x1DCA }, { 0x1DFE, 0x1DFF }, 189 PAIR(0x0A47, 0x0A48)
163 { 0x200B, 0x200F }, { 0x202A, 0x202E }, { 0x2060, 0x2063 }, 190 PAIR(0x0A4B, 0x0A4D)
164 { 0x206A, 0x206F }, { 0x20D0, 0x20EF }, { 0x302A, 0x302F }, 191 PAIR(0x0A70, 0x0A71)
165 { 0x3099, 0x309A }, { 0xA806, 0xA806 }, { 0xA80B, 0xA80B }, 192 PAIR(0x0A81, 0x0A82)
166 { 0xA825, 0xA826 }, { 0xFB1E, 0xFB1E }, { 0xFE00, 0xFE0F }, 193 PAIR(0x0ABC, 0x0ABC)
167 { 0xFE20, 0xFE23 }, { 0xFEFF, 0xFEFF }, { 0xFFF9, 0xFFFB } 194 BIG_(0x0AC1, 0x0AC5)
195 PAIR(0x0AC7, 0x0AC8)
196 PAIR(0x0ACD, 0x0ACD)
197 PAIR(0x0AE2, 0x0AE3)
198 PAIR(0x0B01, 0x0B01)
199 PAIR(0x0B3C, 0x0B3C)
200 PAIR(0x0B3F, 0x0B3F)
201 PAIR(0x0B41, 0x0B43)
202 PAIR(0x0B4D, 0x0B4D)
203 PAIR(0x0B56, 0x0B56)
204 PAIR(0x0B82, 0x0B82)
205 PAIR(0x0BC0, 0x0BC0)
206 PAIR(0x0BCD, 0x0BCD)
207 PAIR(0x0C3E, 0x0C40)
208 PAIR(0x0C46, 0x0C48)
209 PAIR(0x0C4A, 0x0C4D)
210 PAIR(0x0C55, 0x0C56)
211 PAIR(0x0CBC, 0x0CBC)
212 PAIR(0x0CBF, 0x0CBF)
213 PAIR(0x0CC6, 0x0CC6)
214 PAIR(0x0CCC, 0x0CCD)
215 PAIR(0x0CE2, 0x0CE3)
216 PAIR(0x0D41, 0x0D43)
217 PAIR(0x0D4D, 0x0D4D)
218 PAIR(0x0DCA, 0x0DCA)
219 PAIR(0x0DD2, 0x0DD4)
220 PAIR(0x0DD6, 0x0DD6)
221 PAIR(0x0E31, 0x0E31)
222 BIG_(0x0E34, 0x0E3A)
223 BIG_(0x0E47, 0x0E4E)
224 PAIR(0x0EB1, 0x0EB1)
225 BIG_(0x0EB4, 0x0EB9)
226 PAIR(0x0EBB, 0x0EBC)
227 BIG_(0x0EC8, 0x0ECD)
228 PAIR(0x0F18, 0x0F19)
229 PAIR(0x0F35, 0x0F35)
230 PAIR(0x0F37, 0x0F37)
231 PAIR(0x0F39, 0x0F39)
232 BIG_(0x0F71, 0x0F7E)
233 BIG_(0x0F80, 0x0F84)
234 PAIR(0x0F86, 0x0F87)
235 PAIR(0x0FC6, 0x0FC6)
236 BIG_(0x0F90, 0x0F97)
237 BIG_(0x0F99, 0x0FBC)
238 PAIR(0x102D, 0x1030)
239 PAIR(0x1032, 0x1032)
240 PAIR(0x1036, 0x1037)
241 PAIR(0x1039, 0x1039)
242 PAIR(0x1058, 0x1059)
243 BIG_(0x1160, 0x11FF)
244 PAIR(0x135F, 0x135F)
245 PAIR(0x1712, 0x1714)
246 PAIR(0x1732, 0x1734)
247 PAIR(0x1752, 0x1753)
248 PAIR(0x1772, 0x1773)
249 PAIR(0x17B4, 0x17B5)
250 BIG_(0x17B7, 0x17BD)
251 PAIR(0x17C6, 0x17C6)
252 BIG_(0x17C9, 0x17D3)
253 PAIR(0x17DD, 0x17DD)
254 PAIR(0x180B, 0x180D)
255 PAIR(0x18A9, 0x18A9)
256 PAIR(0x1920, 0x1922)
257 PAIR(0x1927, 0x1928)
258 PAIR(0x1932, 0x1932)
259 PAIR(0x1939, 0x193B)
260 PAIR(0x1A17, 0x1A18)
261 PAIR(0x1B00, 0x1B03)
262 PAIR(0x1B34, 0x1B34)
263 BIG_(0x1B36, 0x1B3A)
264 PAIR(0x1B3C, 0x1B3C)
265 PAIR(0x1B42, 0x1B42)
266 BIG_(0x1B6B, 0x1B73)
267 BIG_(0x1DC0, 0x1DCA)
268 PAIR(0x1DFE, 0x1DFF)
269 BIG_(0x200B, 0x200F)
270 BIG_(0x202A, 0x202E)
271 PAIR(0x2060, 0x2063)
272 BIG_(0x206A, 0x206F)
273 BIG_(0x20D0, 0x20EF)
274 BIG_(0x302A, 0x302F)
275 PAIR(0x3099, 0x309A)
276 /* Too big to be packed in PAIRs: */
277 { 0xA806, 0xA806 },
278 { 0xA80B, 0xA80B },
279 { 0xA825, 0xA826 },
280 { 0xFB1E, 0xFB1E },
281 { 0xFE00, 0xFE0F },
282 { 0xFE20, 0xFE23 },
283 { 0xFEFF, 0xFEFF },
284 { 0xFFF9, 0xFFFB }
285#undef BIG_
286#undef PAIR
287 };
288 static const uint16_t combining1[] = {
289#define BIG_(a,b)
290#define PAIR(a,b) (a << 2) | (b-a),
291 /* Exact copy-n-paste of the above: */
292 BIG_(0x0300, 0x036F)
293 PAIR(0x0483, 0x0486)
294 PAIR(0x0488, 0x0489)
295 BIG_(0x0591, 0x05BD)
296 PAIR(0x05BF, 0x05BF)
297 PAIR(0x05C1, 0x05C2)
298 PAIR(0x05C4, 0x05C5)
299 PAIR(0x05C7, 0x05C7)
300 PAIR(0x0600, 0x0603)
301 BIG_(0x0610, 0x0615)
302 BIG_(0x064B, 0x065E)
303 PAIR(0x0670, 0x0670)
304 BIG_(0x06D6, 0x06E4)
305 PAIR(0x06E7, 0x06E8)
306 PAIR(0x06EA, 0x06ED)
307 PAIR(0x070F, 0x070F)
308 PAIR(0x0711, 0x0711)
309 BIG_(0x0730, 0x074A)
310 BIG_(0x07A6, 0x07B0)
311 BIG_(0x07EB, 0x07F3)
312 PAIR(0x0901, 0x0902)
313 PAIR(0x093C, 0x093C)
314 BIG_(0x0941, 0x0948)
315 PAIR(0x094D, 0x094D)
316 PAIR(0x0951, 0x0954)
317 PAIR(0x0962, 0x0963)
318 PAIR(0x0981, 0x0981)
319 PAIR(0x09BC, 0x09BC)
320 PAIR(0x09C1, 0x09C4)
321 PAIR(0x09CD, 0x09CD)
322 PAIR(0x09E2, 0x09E3)
323 PAIR(0x0A01, 0x0A02)
324 PAIR(0x0A3C, 0x0A3C)
325 PAIR(0x0A41, 0x0A42)
326 PAIR(0x0A47, 0x0A48)
327 PAIR(0x0A4B, 0x0A4D)
328 PAIR(0x0A70, 0x0A71)
329 PAIR(0x0A81, 0x0A82)
330 PAIR(0x0ABC, 0x0ABC)
331 BIG_(0x0AC1, 0x0AC5)
332 PAIR(0x0AC7, 0x0AC8)
333 PAIR(0x0ACD, 0x0ACD)
334 PAIR(0x0AE2, 0x0AE3)
335 PAIR(0x0B01, 0x0B01)
336 PAIR(0x0B3C, 0x0B3C)
337 PAIR(0x0B3F, 0x0B3F)
338 PAIR(0x0B41, 0x0B43)
339 PAIR(0x0B4D, 0x0B4D)
340 PAIR(0x0B56, 0x0B56)
341 PAIR(0x0B82, 0x0B82)
342 PAIR(0x0BC0, 0x0BC0)
343 PAIR(0x0BCD, 0x0BCD)
344 PAIR(0x0C3E, 0x0C40)
345 PAIR(0x0C46, 0x0C48)
346 PAIR(0x0C4A, 0x0C4D)
347 PAIR(0x0C55, 0x0C56)
348 PAIR(0x0CBC, 0x0CBC)
349 PAIR(0x0CBF, 0x0CBF)
350 PAIR(0x0CC6, 0x0CC6)
351 PAIR(0x0CCC, 0x0CCD)
352 PAIR(0x0CE2, 0x0CE3)
353 PAIR(0x0D41, 0x0D43)
354 PAIR(0x0D4D, 0x0D4D)
355 PAIR(0x0DCA, 0x0DCA)
356 PAIR(0x0DD2, 0x0DD4)
357 PAIR(0x0DD6, 0x0DD6)
358 PAIR(0x0E31, 0x0E31)
359 BIG_(0x0E34, 0x0E3A)
360 BIG_(0x0E47, 0x0E4E)
361 PAIR(0x0EB1, 0x0EB1)
362 BIG_(0x0EB4, 0x0EB9)
363 PAIR(0x0EBB, 0x0EBC)
364 BIG_(0x0EC8, 0x0ECD)
365 PAIR(0x0F18, 0x0F19)
366 PAIR(0x0F35, 0x0F35)
367 PAIR(0x0F37, 0x0F37)
368 PAIR(0x0F39, 0x0F39)
369 BIG_(0x0F71, 0x0F7E)
370 BIG_(0x0F80, 0x0F84)
371 PAIR(0x0F86, 0x0F87)
372 PAIR(0x0FC6, 0x0FC6)
373 BIG_(0x0F90, 0x0F97)
374 BIG_(0x0F99, 0x0FBC)
375 PAIR(0x102D, 0x1030)
376 PAIR(0x1032, 0x1032)
377 PAIR(0x1036, 0x1037)
378 PAIR(0x1039, 0x1039)
379 PAIR(0x1058, 0x1059)
380 BIG_(0x1160, 0x11FF)
381 PAIR(0x135F, 0x135F)
382 PAIR(0x1712, 0x1714)
383 PAIR(0x1732, 0x1734)
384 PAIR(0x1752, 0x1753)
385 PAIR(0x1772, 0x1773)
386 PAIR(0x17B4, 0x17B5)
387 BIG_(0x17B7, 0x17BD)
388 PAIR(0x17C6, 0x17C6)
389 BIG_(0x17C9, 0x17D3)
390 PAIR(0x17DD, 0x17DD)
391 PAIR(0x180B, 0x180D)
392 PAIR(0x18A9, 0x18A9)
393 PAIR(0x1920, 0x1922)
394 PAIR(0x1927, 0x1928)
395 PAIR(0x1932, 0x1932)
396 PAIR(0x1939, 0x193B)
397 PAIR(0x1A17, 0x1A18)
398 PAIR(0x1B00, 0x1B03)
399 PAIR(0x1B34, 0x1B34)
400 BIG_(0x1B36, 0x1B3A)
401 PAIR(0x1B3C, 0x1B3C)
402 PAIR(0x1B42, 0x1B42)
403 BIG_(0x1B6B, 0x1B73)
404 BIG_(0x1DC0, 0x1DCA)
405 PAIR(0x1DFE, 0x1DFF)
406 BIG_(0x200B, 0x200F)
407 BIG_(0x202A, 0x202E)
408 PAIR(0x2060, 0x2063)
409 BIG_(0x206A, 0x206F)
410 BIG_(0x20D0, 0x20EF)
411 BIG_(0x302A, 0x302F)
412 PAIR(0x3099, 0x309A)
413#undef BIG_
414#undef PAIR
415 };
416 struct CHECK {
417#define BIG_(a,b) char big##a[b-a <= 3 ? -1 : 1];
418#define PAIR(a,b) char pair##a[b-a > 3 ? -1 : 1];
419 /* Copy-n-paste it here again to verify correctness */
420#undef BIG_
421#undef PAIR
168 }; 422 };
169 static const struct interval combining0x10000[] = { 423 static const struct interval combining0x10000[] = {
170 { 0x0A01, 0x0A03 }, { 0x0A05, 0x0A06 }, { 0x0A0C, 0x0A0F }, 424 { 0x0A01, 0x0A03 }, { 0x0A05, 0x0A06 }, { 0x0A0C, 0x0A0F },
@@ -182,14 +436,16 @@ static int wcwidth(unsigned ucs)
182 return 1; 436 return 1;
183 437
184 /* binary search in table of non-spacing characters */ 438 /* binary search in table of non-spacing characters */
185 if (in_table(ucs, combining, ARRAY_SIZE(combining) - 1)) 439 if (in_interval_table(ucs, combining, ARRAY_SIZE(combining) - 1))
440 return 0;
441 if (in_uint16_table(ucs, combining1, ARRAY_SIZE(combining1) - 1))
186 return 0; 442 return 0;
187 443
188 if (ucs < 0x1100) /* optimization */ 444 if (ucs < 0x1100) /* optimization */
189 return 1; 445 return 1;
190 446
191 /* binary search in table of non-spacing characters, cont. */ 447 /* binary search in table of non-spacing characters, cont. */
192 if (in_table(ucs ^ 0x10000, combining0x10000, ARRAY_SIZE(combining0x10000) - 1)) 448 if (in_interval_table(ucs ^ 0x10000, combining0x10000, ARRAY_SIZE(combining0x10000) - 1))
193 return 0; 449 return 0;
194 if (ucs == 0xE0001 450 if (ucs == 0xE0001
195 || (ucs >= 0xE0020 && ucs <= 0xE007F) 451 || (ucs >= 0xE0020 && ucs <= 0xE007F)
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2026-01-15 09:09:05 +0000