From a11a6246c64b186c5547b9527a768a56f3d6b281 Mon Sep 17 00:00:00 2001 From: Rich Felker Date: Fri, 25 Oct 2019 12:33:17 -0400 Subject: [PATCH] overhaul wide character case mapping implementation the existing implementation of case mappings was very small (typically around 1.5k), but unmaintainable, requiring manual addition of new case mappings with each new edition of Unicode. often, it turned out that newly-added case mappings were not easily representable in the existing tightly-constrained table structures, requiring new hacks to be invented and delaying support for new characters. the new implementation added here follows the pattern used for character class membership, with a two-level table allowing Unicode blocks for which no data is needed to be elided. however, rather than single-bit data, each character maps to a one of up to 6 case-mapping rules available to its block, where 6 is floor(cbrt(256)) and allow 3 characters to be represented per byte (vs 8 with bit tables). blocks that would need more than 6 rules designate one as an exception and let lookup pass into a binary search of exceptional cases for the block. the number 6 was chosen empirically; many blocks would be ok with 4 rules (uncased, lower, upper, possible exceptions), some even just with 2, but the latter are rare and fitting 4 characters per byte rather than 3 does not save significant space. moreover, somewhat surprisingly, there are sufficiently many blocks where even 4 rules don't suffice without a lot of exceptions (blocks where some case pairs are laced, others offset) that originally I was looking at supporting variable-width tables, with 1-, 2-, or 3-bit entries, thereby allowing blocks with 8 rules. as implemented in my experiments, that version was significantly larger and involved more memory accesses/cache lines. improvements in size at the expense of some performance might be possible by utilizing iswalpha data or merging the table of case mapping identity with alphabetic identity. these were explored somewhat when the code was first written, and might be worth revisiting in the future. --- src/ctype/casemap.h | 290 +++++++++++++++++++++++++++++++++++ src/ctype/towctrans.c | 345 +++++++----------------------------------- 2 files changed, 345 insertions(+), 290 deletions(-) create mode 100644 src/ctype/casemap.h diff --git a/src/ctype/casemap.h b/src/ctype/casemap.h new file mode 100644 index 00000000..e4f759af --- /dev/null +++ b/src/ctype/casemap.h @@ -0,0 +1,290 @@ +static const unsigned char tab[] = { + 7, 8, 9, 10, 11, 12, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 13, 6, 6, 14, 6, 6, 6, 6, 6, 6, 6, 6, 15, 16, 17, 18, + 6, 19, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 20, 21, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 22, 23, 6, 6, 6, 24, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 25, + 6, 6, 6, 6, 26, 6, 6, 6, 6, 6, 6, 6, 27, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 28, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 29, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, + 43, 43, 43, 43, 43, 43, 43, 43, 1, 0, 84, 86, 86, 86, 86, 86, + 86, 86, 86, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 24, 0, 0, 0, 43, 43, 43, 43, 43, 43, + 43, 7, 43, 43, 91, 86, 86, 86, 86, 86, 86, 86, 74, 86, 86, 5, + 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, + 36, 80, 121, 49, 80, 49, 80, 49, 56, 80, 49, 80, 49, 80, 49, 80, + 49, 80, 49, 80, 49, 80, 49, 80, 78, 49, 2, 78, 13, 13, 78, 3, + 78, 0, 36, 110, 0, 78, 49, 38, 110, 81, 78, 36, 80, 78, 57, 20, + 129, 27, 29, 29, 83, 49, 80, 49, 80, 13, 49, 80, 49, 80, 49, 80, + 27, 83, 36, 80, 49, 2, 92, 123, 92, 123, 92, 123, 92, 123, 92, 123, + 20, 121, 92, 123, 92, 123, 92, 45, 43, 73, 3, 72, 3, 120, 92, 123, + 20, 0, 150, 10, 1, 43, 40, 6, 6, 0, 42, 6, 42, 42, 43, 7, + 187, 187, 43, 30, 0, 43, 7, 43, 43, 43, 1, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 1, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 42, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 205, 70, 205, 43, 0, 37, 43, 7, 1, 6, 1, 85, 86, 86, 86, + 86, 86, 85, 86, 86, 2, 36, 129, 129, 129, 129, 129, 21, 129, 129, 129, + 0, 0, 43, 0, 178, 209, 178, 209, 178, 209, 178, 209, 0, 0, 205, 204, + 1, 0, 215, 215, 215, 215, 215, 131, 129, 129, 129, 129, 129, 129, 129, 129, + 129, 129, 172, 172, 172, 172, 172, 172, 172, 172, 172, 172, 28, 0, 0, 0, + 0, 0, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 2, 0, 0, + 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, + 49, 80, 78, 49, 80, 49, 80, 78, 49, 80, 49, 80, 49, 80, 49, 80, + 49, 80, 49, 80, 49, 80, 49, 2, 135, 166, 135, 166, 135, 166, 135, 166, + 135, 166, 135, 166, 135, 166, 135, 166, 42, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 0, 0, 0, 84, 86, 86, 86, 86, 86, 86, 86, + 86, 86, 86, 86, 86, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 42, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 6, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 42, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 86, 86, 108, 129, 21, 0, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 7, 72, 182, 58, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 6, 72, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, + 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, + 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, + 6, 37, 6, 37, 6, 37, 6, 37, 86, 122, 158, 38, 6, 37, 6, 37, + 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, + 6, 37, 6, 37, 6, 37, 6, 37, 6, 37, 6, 1, 43, 43, 79, 86, + 86, 44, 43, 127, 86, 86, 57, 43, 43, 85, 86, 86, 43, 43, 79, 86, + 86, 44, 43, 127, 86, 86, 129, 55, 117, 91, 123, 92, 43, 43, 79, 86, + 86, 2, 172, 4, 0, 0, 57, 43, 43, 85, 86, 86, 43, 43, 79, 86, + 86, 44, 43, 43, 86, 86, 50, 19, 129, 87, 0, 111, 129, 126, 201, 215, + 126, 45, 129, 129, 14, 126, 57, 127, 111, 87, 0, 129, 129, 126, 21, 0, + 126, 3, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 7, 43, + 36, 43, 151, 43, 43, 43, 43, 43, 43, 43, 43, 43, 42, 43, 43, 43, + 43, 43, 86, 86, 86, 86, 86, 128, 129, 129, 129, 129, 57, 187, 42, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 1, 129, 129, 129, 129, 129, 129, 129, 129, + 129, 129, 129, 129, 129, 129, 129, 201, 172, 172, 172, 172, 172, 172, 172, 172, + 172, 172, 172, 172, 172, 172, 172, 208, 13, 0, 78, 49, 2, 180, 193, 193, + 215, 215, 36, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, + 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, 49, 80, + 49, 80, 49, 80, 215, 215, 83, 193, 71, 212, 215, 215, 215, 5, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 7, 1, 0, 1, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 78, 49, 80, 49, 80, 49, 80, + 49, 80, 49, 80, 49, 80, 49, 80, 13, 0, 0, 0, 0, 0, 36, 80, + 49, 80, 49, 80, 49, 80, 49, 80, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 121, 92, 123, 92, 123, 79, 123, 92, 123, 92, 123, + 92, 123, 92, 123, 92, 123, 92, 123, 92, 123, 92, 123, 92, 123, 92, 45, + 43, 43, 121, 20, 92, 123, 92, 45, 121, 42, 92, 45, 92, 123, 92, 123, + 92, 123, 164, 0, 10, 180, 92, 45, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 72, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 42, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 43, 43, 43, 43, 43, 43, 43, 43, 7, 0, 72, 86, 86, 86, 86, + 86, 86, 86, 86, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 85, 86, 86, 86, 86, 86, 86, + 86, 86, 86, 86, 86, 86, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 36, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 7, 0, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 7, 0, 0, + 0, 0, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, + 86, 86, 86, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 42, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 86, 86, 86, 86, 86, 86, 86, 86, + 86, 86, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 85, 86, 86, 86, 86, 86, 86, + 86, 86, 86, 86, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, +}; +static const int rules[] = { + 0x0, 0x2001, -0x2000, 0x1dbf00, 0x2e700, 0x7900, + 0x2402, 0x101, -0x100, 0x0, 0x201, -0x200, + -0xc6ff, -0xe800, -0x78ff, -0x12c00, 0xc300, 0xd201, + 0xce01, 0xcd01, 0x4f01, 0xca01, 0xcb01, 0xcf01, + 0x6100, 0xd301, 0xd101, 0xa300, 0xd501, 0x8200, + 0xd601, 0xda01, 0xd901, 0xdb01, 0x3800, 0x3, + -0x4f00, -0x60ff, -0x37ff, 0x242702, 0x0, 0x101, + -0x100, -0xcd00, -0xda00, -0x81ff, 0x2a2b01, -0xa2ff, + 0x2a2801, 0x2a3f00, -0xc2ff, 0x4501, 0x4701, 0x2a1f00, + 0x2a1c00, 0x2a1e00, -0xd200, -0xce00, -0xca00, -0xcb00, + 0xa54f00, 0xa54b00, -0xcf00, 0xa52800, 0xa54400, -0xd100, + -0xd300, 0x29f700, 0xa54100, 0x29fd00, -0xd500, -0xd600, + 0x29e700, 0xa52a00, -0x4500, -0xd900, -0x4700, -0xdb00, + 0xa51500, 0xa51200, 0x4b2402, 0x0, 0x2001, -0x2000, + 0x101, -0x100, 0x5400, 0x7401, 0x2601, 0x2501, + 0x4001, 0x3f01, -0x2600, -0x2500, -0x1f00, -0x4000, + -0x3f00, 0x801, -0x3e00, -0x3900, -0x2f00, -0x3600, + -0x800, -0x5600, -0x5000, 0x700, -0x7400, -0x3bff, + -0x6000, -0x6ff, 0x6f1a02, 0x101, -0x100, 0x2001, + -0x2000, 0x5001, 0xf01, -0xf00, 0x0, 0x3001, + -0x3000, 0x101, -0x100, 0x0, 0x1c6001, 0x0, + 0x97d001, 0x801, -0x800, 0x890402, 0x0, -0x186200, + 0x89c200, -0x182500, -0x185c00, -0x186e00, -0x186d00, -0x186400, + -0x186300, 0x0, 0x8a0400, 0xee600, 0x101, -0x100, + 0x0, -0x3b00, -0x1dbeff, 0x8d1d02, 0x800, -0x7ff, + 0x0, 0x5600, -0x55ff, 0x4a00, 0x6400, 0x8000, + 0x7000, 0x7e00, 0x900, -0x49ff, -0x8ff, -0x1c2500, + -0x63ff, -0x6fff, -0x7fff, -0x7dff, 0xaa0502, 0x0, + 0x1001, -0x1000, 0x1c01, 0x101, -0x1d5cff, -0x20beff, + -0x2045ff, -0x1c00, 0xaf0b02, 0x101, -0x100, 0x3001, + -0x3000, 0x0, -0x29f6ff, -0xee5ff, -0x29e6ff, -0x2a2b00, + -0x2a2800, -0x2a1bff, -0x29fcff, -0x2a1eff, -0x2a1dff, -0x2a3eff, + 0x0, -0x1c6000, 0x0, 0x101, -0x100, 0xba0802, + 0x0, 0x101, -0x100, -0xa543ff, 0x3a001, -0x8a03ff, + -0xa527ff, -0xa54eff, -0xa54aff, -0xa540ff, -0xa511ff, -0xa529ff, + -0xa514ff, 0x0, -0x97d000, -0x3a000, 0x0, 0x2001, + -0x2000, 0x0, 0x2801, -0x2800, 0x0, 0x4001, + -0x4000, 0x0, 0x2001, -0x2000, 0x0, 0x2201, + -0x2200, +}; +static const unsigned char rulebases[] = { + 0, 6, 39, 80, 110, 118, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 123, 0, 0, 125, 0, 0, 0, 0, 0, 0, 0, 0, 129, 139, 142, 147, + 0, 166, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 176, 192, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 194, 197, 0, 0, 0, 211, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 214, + 0, 0, 0, 0, 217, 0, 0, 0, 0, 0, 0, 0, 220, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 223, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 226, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, +}; +static const unsigned char exceptions[][2] = { + { 48, 12 }, { 49, 13 }, { 120, 14 }, { 127, 15 }, + { 128, 16 }, { 129, 17 }, { 134, 18 }, { 137, 19 }, + { 138, 19 }, { 142, 20 }, { 143, 21 }, { 144, 22 }, + { 147, 19 }, { 148, 23 }, { 149, 24 }, { 150, 25 }, + { 151, 26 }, { 154, 27 }, { 156, 25 }, { 157, 28 }, + { 158, 29 }, { 159, 30 }, { 166, 31 }, { 169, 31 }, + { 174, 31 }, { 177, 32 }, { 178, 32 }, { 183, 33 }, + { 191, 34 }, { 197, 35 }, { 200, 35 }, { 203, 35 }, + { 221, 36 }, { 242, 35 }, { 246, 37 }, { 247, 38 }, + { 32, 45 }, { 58, 46 }, { 61, 47 }, { 62, 48 }, + { 63, 49 }, { 64, 49 }, { 67, 50 }, { 68, 51 }, + { 69, 52 }, { 80, 53 }, { 81, 54 }, { 82, 55 }, + { 83, 56 }, { 84, 57 }, { 89, 58 }, { 91, 59 }, + { 92, 60 }, { 97, 61 }, { 99, 62 }, { 101, 63 }, + { 102, 64 }, { 104, 65 }, { 105, 66 }, { 106, 64 }, + { 107, 67 }, { 108, 68 }, { 111, 66 }, { 113, 69 }, + { 114, 70 }, { 117, 71 }, { 125, 72 }, { 135, 73 }, + { 137, 74 }, { 138, 75 }, { 139, 75 }, { 140, 76 }, + { 146, 77 }, { 157, 78 }, { 158, 79 }, { 69, 86 }, + { 123, 29 }, { 124, 29 }, { 125, 29 }, { 127, 87 }, + { 134, 88 }, { 136, 89 }, { 137, 89 }, { 138, 89 }, + { 140, 90 }, { 142, 91 }, { 143, 91 }, { 172, 92 }, + { 173, 93 }, { 174, 93 }, { 175, 93 }, { 194, 94 }, + { 204, 95 }, { 205, 96 }, { 206, 96 }, { 207, 97 }, + { 208, 98 }, { 209, 99 }, { 213, 100 }, { 214, 101 }, + { 215, 102 }, { 240, 103 }, { 241, 104 }, { 242, 105 }, + { 243, 106 }, { 244, 107 }, { 245, 108 }, { 249, 109 }, + { 253, 45 }, { 254, 45 }, { 255, 45 }, { 80, 104 }, + { 81, 104 }, { 82, 104 }, { 83, 104 }, { 84, 104 }, + { 85, 104 }, { 86, 104 }, { 87, 104 }, { 88, 104 }, + { 89, 104 }, { 90, 104 }, { 91, 104 }, { 92, 104 }, + { 93, 104 }, { 94, 104 }, { 95, 104 }, { 130, 0 }, + { 131, 0 }, { 132, 0 }, { 133, 0 }, { 134, 0 }, + { 135, 0 }, { 136, 0 }, { 137, 0 }, { 192, 116 }, + { 207, 117 }, { 128, 135 }, { 129, 136 }, { 130, 137 }, + { 133, 138 }, { 112, 153 }, { 113, 153 }, { 118, 154 }, + { 119, 154 }, { 120, 155 }, { 121, 155 }, { 122, 156 }, + { 123, 156 }, { 124, 157 }, { 125, 157 }, { 179, 158 }, + { 186, 159 }, { 187, 159 }, { 188, 160 }, { 190, 161 }, + { 195, 158 }, { 204, 160 }, { 218, 162 }, { 219, 162 }, + { 229, 105 }, { 234, 163 }, { 235, 163 }, { 236, 109 }, + { 243, 158 }, { 248, 164 }, { 249, 164 }, { 250, 165 }, + { 251, 165 }, { 252, 160 }, { 38, 172 }, { 42, 173 }, + { 43, 174 }, { 78, 175 }, { 132, 8 }, { 98, 182 }, + { 99, 183 }, { 100, 184 }, { 101, 185 }, { 102, 186 }, + { 109, 187 }, { 110, 188 }, { 111, 189 }, { 112, 190 }, + { 126, 191 }, { 127, 191 }, { 125, 203 }, { 141, 204 }, + { 171, 205 }, { 172, 206 }, { 173, 207 }, { 176, 208 }, + { 177, 209 }, { 178, 210 }, +}; diff --git a/src/ctype/towctrans.c b/src/ctype/towctrans.c index 9b91b2de..76d13769 100644 --- a/src/ctype/towctrans.c +++ b/src/ctype/towctrans.c @@ -1,308 +1,73 @@ -#include -#include #include -#define CASEMAP(u1,u2,l) { (u1), (l)-(u1), (u2)-(u1)+1 } -#define CASELACE(u1,u2) CASEMAP((u1),(u2),(u1)+1) +static const unsigned char tab[]; -static const struct { - unsigned short upper; - signed char lower; - unsigned char len; -} casemaps[] = { - CASEMAP(0xc0,0xde,0xe0), +static const unsigned char rulebases[512]; +static const int rules[]; - CASELACE(0x0100,0x012e), - CASELACE(0x0132,0x0136), - CASELACE(0x0139,0x0147), - CASELACE(0x014a,0x0176), - CASELACE(0x0179,0x017d), +static const unsigned char exceptions[][2]; - CASELACE(0x370,0x372), - CASEMAP(0x391,0x3a1,0x3b1), - CASEMAP(0x3a3,0x3ab,0x3c3), - CASEMAP(0x400,0x40f,0x450), - CASEMAP(0x410,0x42f,0x430), +#include "casemap.h" - CASELACE(0x460,0x480), - CASELACE(0x48a,0x4be), - CASELACE(0x4c1,0x4cd), - CASELACE(0x4d0,0x50e), - - CASELACE(0x514,0x52e), - CASEMAP(0x531,0x556,0x561), - - CASELACE(0x01a0,0x01a4), - CASELACE(0x01b3,0x01b5), - CASELACE(0x01cd,0x01db), - CASELACE(0x01de,0x01ee), - CASELACE(0x01f8,0x021e), - CASELACE(0x0222,0x0232), - CASELACE(0x03d8,0x03ee), - - CASELACE(0x1e00,0x1e94), - CASELACE(0x1ea0,0x1efe), - - CASEMAP(0x1f08,0x1f0f,0x1f00), - CASEMAP(0x1f18,0x1f1d,0x1f10), - CASEMAP(0x1f28,0x1f2f,0x1f20), - CASEMAP(0x1f38,0x1f3f,0x1f30), - CASEMAP(0x1f48,0x1f4d,0x1f40), - - CASEMAP(0x1f68,0x1f6f,0x1f60), - CASEMAP(0x1f88,0x1f8f,0x1f80), - CASEMAP(0x1f98,0x1f9f,0x1f90), - CASEMAP(0x1fa8,0x1faf,0x1fa0), - CASEMAP(0x1fb8,0x1fb9,0x1fb0), - CASEMAP(0x1fba,0x1fbb,0x1f70), - CASEMAP(0x1fc8,0x1fcb,0x1f72), - CASEMAP(0x1fd8,0x1fd9,0x1fd0), - CASEMAP(0x1fda,0x1fdb,0x1f76), - CASEMAP(0x1fe8,0x1fe9,0x1fe0), - CASEMAP(0x1fea,0x1feb,0x1f7a), - CASEMAP(0x1ff8,0x1ff9,0x1f78), - CASEMAP(0x1ffa,0x1ffb,0x1f7c), - - CASEMAP(0x13f0,0x13f5,0x13f8), - CASELACE(0xa698,0xa69a), - CASELACE(0xa796,0xa79e), - - CASELACE(0x246,0x24e), - CASELACE(0x510,0x512), - CASEMAP(0x2160,0x216f,0x2170), - CASEMAP(0x2c00,0x2c2e,0x2c30), - CASELACE(0x2c67,0x2c6b), - CASELACE(0x2c80,0x2ce2), - CASELACE(0x2ceb,0x2ced), - - CASELACE(0xa640,0xa66c), - CASELACE(0xa680,0xa696), - - CASELACE(0xa722,0xa72e), - CASELACE(0xa732,0xa76e), - CASELACE(0xa779,0xa77b), - CASELACE(0xa77e,0xa786), - - CASELACE(0xa790,0xa792), - CASELACE(0xa7a0,0xa7a8), - - CASELACE(0xa7b4,0xa7b6), - - CASEMAP(0xff21,0xff3a,0xff41), - { 0,0,0 } -}; - -static const unsigned short pairs[][2] = { - { 'I', 0x0131 }, - { 'S', 0x017f }, - { 0x0130, 'i' }, - { 0x0178, 0x00ff }, - { 0x0181, 0x0253 }, - { 0x0182, 0x0183 }, - { 0x0184, 0x0185 }, - { 0x0186, 0x0254 }, - { 0x0187, 0x0188 }, - { 0x0189, 0x0256 }, - { 0x018a, 0x0257 }, - { 0x018b, 0x018c }, - { 0x018e, 0x01dd }, - { 0x018f, 0x0259 }, - { 0x0190, 0x025b }, - { 0x0191, 0x0192 }, - { 0x0193, 0x0260 }, - { 0x0194, 0x0263 }, - { 0x0196, 0x0269 }, - { 0x0197, 0x0268 }, - { 0x0198, 0x0199 }, - { 0x019c, 0x026f }, - { 0x019d, 0x0272 }, - { 0x019f, 0x0275 }, - { 0x01a6, 0x0280 }, - { 0x01a7, 0x01a8 }, - { 0x01a9, 0x0283 }, - { 0x01ac, 0x01ad }, - { 0x01ae, 0x0288 }, - { 0x01af, 0x01b0 }, - { 0x01b1, 0x028a }, - { 0x01b2, 0x028b }, - { 0x01b7, 0x0292 }, - { 0x01b8, 0x01b9 }, - { 0x01bc, 0x01bd }, - { 0x01c4, 0x01c6 }, - { 0x01c4, 0x01c5 }, - { 0x01c5, 0x01c6 }, - { 0x01c7, 0x01c9 }, - { 0x01c7, 0x01c8 }, - { 0x01c8, 0x01c9 }, - { 0x01ca, 0x01cc }, - { 0x01ca, 0x01cb }, - { 0x01cb, 0x01cc }, - { 0x01f1, 0x01f3 }, - { 0x01f1, 0x01f2 }, - { 0x01f2, 0x01f3 }, - { 0x01f4, 0x01f5 }, - { 0x01f6, 0x0195 }, - { 0x01f7, 0x01bf }, - { 0x0220, 0x019e }, - { 0x0386, 0x03ac }, - { 0x0388, 0x03ad }, - { 0x0389, 0x03ae }, - { 0x038a, 0x03af }, - { 0x038c, 0x03cc }, - { 0x038e, 0x03cd }, - { 0x038f, 0x03ce }, - { 0x0399, 0x0345 }, - { 0x0399, 0x1fbe }, - { 0x03a3, 0x03c2 }, - { 0x03f7, 0x03f8 }, - { 0x03fa, 0x03fb }, - { 0x1e60, 0x1e9b }, - { 0x1e9e, 0xdf }, - - { 0x1f59, 0x1f51 }, - { 0x1f5b, 0x1f53 }, - { 0x1f5d, 0x1f55 }, - { 0x1f5f, 0x1f57 }, - { 0x1fbc, 0x1fb3 }, - { 0x1fcc, 0x1fc3 }, - { 0x1fec, 0x1fe5 }, - { 0x1ffc, 0x1ff3 }, - - { 0x23a, 0x2c65 }, - { 0x23b, 0x23c }, - { 0x23d, 0x19a }, - { 0x23e, 0x2c66 }, - { 0x241, 0x242 }, - { 0x243, 0x180 }, - { 0x244, 0x289 }, - { 0x245, 0x28c }, - { 0x37f, 0x3f3 }, - { 0x3f4, 0x3b8 }, - { 0x3f9, 0x3f2 }, - { 0x3fd, 0x37b }, - { 0x3fe, 0x37c }, - { 0x3ff, 0x37d }, - { 0x4c0, 0x4cf }, - - { 0x2126, 0x3c9 }, - { 0x212a, 'k' }, - { 0x212b, 0xe5 }, - { 0x2132, 0x214e }, - { 0x2183, 0x2184 }, - { 0x2c60, 0x2c61 }, - { 0x2c62, 0x26b }, - { 0x2c63, 0x1d7d }, - { 0x2c64, 0x27d }, - { 0x2c6d, 0x251 }, - { 0x2c6e, 0x271 }, - { 0x2c6f, 0x250 }, - { 0x2c70, 0x252 }, - { 0x2c72, 0x2c73 }, - { 0x2c75, 0x2c76 }, - { 0x2c7e, 0x23f }, - { 0x2c7f, 0x240 }, - { 0x2cf2, 0x2cf3 }, - - { 0xa77d, 0x1d79 }, - { 0xa78b, 0xa78c }, - { 0xa78d, 0x265 }, - { 0xa7aa, 0x266 }, - - { 0x10c7, 0x2d27 }, - { 0x10cd, 0x2d2d }, - - /* bogus greek 'symbol' letters */ - { 0x376, 0x377 }, - { 0x39c, 0xb5 }, - { 0x392, 0x3d0 }, - { 0x398, 0x3d1 }, - { 0x3a6, 0x3d5 }, - { 0x3a0, 0x3d6 }, - { 0x39a, 0x3f0 }, - { 0x3a1, 0x3f1 }, - { 0x395, 0x3f5 }, - { 0x3cf, 0x3d7 }, - - { 0xa7ab, 0x25c }, - { 0xa7ac, 0x261 }, - { 0xa7ad, 0x26c }, - { 0xa7ae, 0x26a }, - { 0xa7b0, 0x29e }, - { 0xa7b1, 0x287 }, - { 0xa7b2, 0x29d }, - { 0xa7b3, 0xab53 }, - - /* special cyrillic lowercase forms */ - { 0x412, 0x1c80 }, - { 0x414, 0x1c81 }, - { 0x41e, 0x1c82 }, - { 0x421, 0x1c83 }, - { 0x422, 0x1c84 }, - { 0x422, 0x1c85 }, - { 0x42a, 0x1c86 }, - { 0x462, 0x1c87 }, - { 0xa64a, 0x1c88 }, - - { 0,0 } -}; - - -static wchar_t __towcase(wchar_t wc, int lower) +static int casemap(unsigned c, int dir) { - int i; - int lmul = 2*lower-1; - int lmask = lower-1; - /* no letters with case in these large ranges */ - if (!iswalpha(wc) - || (unsigned)wc - 0x0600 <= 0x0fff-0x0600 - || (unsigned)wc - 0x2e00 <= 0xa63f-0x2e00 - || (unsigned)wc - 0xa800 <= 0xab52-0xa800 - || (unsigned)wc - 0xabc0 <= 0xfeff-0xabc0) - return wc; - /* special case because the diff between upper/lower is too big */ - if (lower && (unsigned)wc - 0x10a0 < 0x2e) - if (wc>0x10c5 && wc != 0x10c7 && wc != 0x10cd) return wc; - else return wc + 0x2d00 - 0x10a0; - if (!lower && (unsigned)wc - 0x2d00 < 0x26) - if (wc>0x2d25 && wc != 0x2d27 && wc != 0x2d2d) return wc; - else return wc + 0x10a0 - 0x2d00; - if (lower && (unsigned)wc - 0x13a0 < 0x50) - return wc + 0xab70 - 0x13a0; - if (!lower && (unsigned)wc - 0xab70 < 0x50) - return wc + 0x13a0 - 0xab70; - for (i=0; casemaps[i].len; i++) { - int base = casemaps[i].upper + (lmask & casemaps[i].lower); - if ((unsigned)wc-base < casemaps[i].len) { - if (casemaps[i].lower == 1) - return wc + lower - ((wc-casemaps[i].upper)&1); - return wc + lmul*casemaps[i].lower; + unsigned b, x, y, v, rt, xb, xn; + int r, rd, c0 = c; + + if (c >= 0x20000) return c; + + b = c>>8; + c &= 255; + x = c/3; + y = c%3; + + /* lookup entry in two-level base-6 table */ + v = tab[tab[b]*86+x]; + static const int mt[] = { 2048, 342, 57 }; + v = (v*mt[y]>>11)%6; + + /* use the bit vector out of the tables as an index into + * a block-specific set of rules and decode the rule into + * a type and a case-mapping delta. */ + r = rules[rulebases[b]+v]; + rt = r & 255; + rd = r >> 8; + + /* rules 0/1 are simple lower/upper case with a delta. + * apply according to desired mapping direction. */ + if (rt < 2) return c0 + (rd & -(rt^dir)); + + /* binary search. endpoints of the binary search for + * this block are stored in the rule delta field. */ + xn = rd & 0xff; + xb = (unsigned)rd >> 8; + while (xn) { + unsigned try = exceptions[xb+xn/2][0]; + if (try == c) { + r = rules[exceptions[xb+xn/2][1]]; + rt = r & 255; + rd = r >> 8; + if (rt < 2) return c0 + (rd & -(rt^dir)); + /* Hard-coded for the four exceptional titlecase */ + return c0 + (dir ? -1 : 1); + } else if (try > c) { + xn /= 2; + } else { + xb += xn/2; + xn -= xn/2; } } - for (i=0; pairs[i][1-lower]; i++) { - if (pairs[i][1-lower] == wc) - return pairs[i][lower]; - } - if ((unsigned)wc - (0x10428 - 0x28*lower) < 0x28) - return wc - 0x28 + 0x50*lower; - if ((unsigned)wc - (0x104d8 - 0x28*lower) < 0x24) - return wc - 0x28 + 0x50*lower; - if ((unsigned)wc - (0x10cc0 - 0x40*lower) < 0x33) - return wc - 0x40 + 0x80*lower; - if ((unsigned)wc - (0x118c0 - 0x20*lower) < 0x20) - return wc - 0x20 + 0x40*lower; - if ((unsigned)wc - (0x1e922 - 0x22*lower) < 0x22) - return wc - 0x22 + 0x44*lower; - return wc; + return c0; } -wint_t towupper(wint_t wc) +wint_t towlower(wint_t wc) { - return (unsigned)wc < 128 ? toupper(wc) : __towcase(wc, 0); + return casemap(wc, 0); } -wint_t towlower(wint_t wc) +wint_t towupper(wint_t wc) { - return (unsigned)wc < 128 ? tolower(wc) : __towcase(wc, 1); + return casemap(wc, 1); } wint_t __towupper_l(wint_t c, locale_t l) -- 2.25.1