* Locale project/LC_COLLATE update: NFD!
@ 2025-06-11 2:56 Rich Felker
2025-06-11 20:22 ` Rich Felker
0 siblings, 1 reply; 2+ messages in thread
From: Rich Felker @ 2025-06-11 2:56 UTC (permalink / raw)
To: musl
[-- Attachment #1: Type: text/plain, Size: 2024 bytes --]
First milestone in the collation part of the locale project: NFD is
working.
For some context, in order to be able to apply the Unicode Collation
Algorithm, it's necessary to be able to normalize the string so that
items don't order differently depending on the choice of ordering of
combining marks or whether to use precomposed forms.
The most natural normalized form for applying collation tables is NFD
(decomposed). So, this is what I've been implementing, as an iterator
that, given a UTF-8 input string, reads off the NFD character sequence
one character at a time, in NFD order.
After writing the last steps to actually emit the tables as C arrays
today, wiring up the Unicode test vectors, and debugging a few small
issues, the full set of test vectors is passing. They are not actually
as comprehensive as I'd like; over the next few days I hope to go back
and add some broad combinatoric tests too.
Code and table size is well under my initial estimates, and not far
above the best-case ones I made along the way. Currently we're at:
.text 1089 0
.data 0 0
.bss 0 0
.rodata 14161 0
This covers characters that participate in the transformation spread
sporadically across the range U+00C0 to U+2FA1D.
The draft tablegen code and runtime code are in a git repo posted at
https://github.com/richfelker/musl-uca-draft. The runtime code is
basically in a state ready for integration when there is collation
code to use it. The tablegen is roughly the same level of polish as
things in musl-chartable-tools (where I intend for it to eventually
live) but it also contains a lot of disabled analytical code that I'll
likely strip out or refactor.
Generated tables are not in git so I'm attaching here in case anyone
wants to read and appreciate (or the opposite) the pretty-printing
without actually figuring out how to run anything.
Next steps: further validation & starting on a data format for the
collation tables themselves.
Rich
[-- Attachment #2: decomp.h --]
[-- Type: text/plain, Size: 79150 bytes --]
static const unsigned char lastlevel[] = {
/* 00c0: */ 128, 63,
1, 3, 5, 7, 9, 11, 0, 13, 15, 17, 19, 21, 23, 25, 27, 29,
0, 31, 33, 35, 37, 39, 41, 0, 0, 43, 45, 47, 49, 51, 0, 0,
53, 55, 57, 59, 61, 63, 0, 65, 67, 69, 71, 73, 75, 77, 79, 81,
0, 83, 85, 87, 89, 91, 93, 0, 0, 95, 97, 99,101,103, 0,105,
56, 57, 56, 58, 56, 59, 56, 60, 56, 61, 56, 62, 63, 64, 65, 57,
65, 58, 65, 59, 65, 61, 66, 57, 66, 58, 66, 59, 66, 61, 67, 60,
68, 57, 68, 58, 68, 59, 68, 60, 68, 61, 69, 57, 69, 58, 69, 59,
69, 61, 70, 58, 71, 57, 71, 58, 71, 59, 71, 60, 71, 61, 71, 62,
72, 64, 73, 57, 73, 58, 73, 59, 73, 61, 74, 57, 74, 58, 74, 59,
74, 61, 75, 60, 76, 57, 76, 58, 76, 59, 76, 60, 76, 61, 77, 57,
77, 58, 77, 59, 77, 61, 78, 58, 78, 61,
/* 0100: */ 128, 62,
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31,
0, 0, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59,
61, 63, 65, 67, 69, 71, 0, 0, 73, 75, 77, 79, 81, 83, 85, 87,
89, 0, 0, 0, 91, 95, 99,101, 0,103,105,107,109,111,113,
56, 79, 71, 79, 56, 80, 71, 80, 56, 81, 71, 81, 63, 58, 72, 58,
63, 59, 72, 59, 63, 82, 72, 82, 63, 83, 72, 83, 84, 83, 85, 83,
65, 79, 73, 79, 65, 80, 73, 80, 65, 82, 73, 82, 65, 81, 73, 81,
65, 83, 73, 83, 86, 59, 87, 59, 86, 80, 87, 80, 86, 82, 87, 82,
86, 64, 87, 64, 88, 59, 89, 59, 66, 60, 74, 60, 66, 79, 74, 79,
66, 80, 74, 80, 66, 81, 74, 81, 66, 82,252, 0, 74, 59,252, 0,
106, 59, 90, 64, 91, 64, 92, 58, 93, 58, 92, 64, 93, 64, 92, 83,
93, 83,
/* 0140: */ 131, 59,
1, 3, 5, 7, 9, 11, 0, 0, 0, 13, 15, 17, 19,
21, 23, 0, 0, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47,
49, 51, 53, 55, 57, 59, 0, 0, 61, 63, 65, 67, 69, 71, 73, 75,
77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99,101,103,105,
67, 58, 75, 58, 67, 64, 75, 64, 67, 83, 75, 83, 68, 79, 76, 79,
68, 80, 76, 80, 68, 94, 76, 94, 95, 58, 96, 58, 95, 64, 96, 64,
95, 83, 96, 83, 97, 58, 98, 58, 97, 59, 98, 59, 97, 64, 98, 64,
97, 83, 98, 83, 99, 64,100, 64, 99, 83,100, 83, 69, 60, 77, 60,
69, 79, 77, 79, 69, 80, 77, 80, 69, 62, 77, 62, 69, 94, 77, 94,
69, 81, 77, 81,101, 59,102, 59, 70, 59, 78, 59, 70, 61,103, 58,
104, 58,103, 82,104, 82,103, 83,104, 83,
/* 0180: */ 160, 16,
1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
7,
68,105, 76,105, 69,105, 77,105,
/* 01c0: */ 205, 50,
1, 4, 7,
10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 0, 49, 52,
55, 58, 61, 66, 0, 0, 71, 74, 77, 80, 83, 86, 89, 92, 95,100,
105, 0, 0, 0,110,113, 0, 0,116,119,122,125,128,133,138,143,
56, 83, 0, 71, 83, 0, 66, 83, 0, 74, 83, 0, 68, 83, 0, 76,
83, 0, 69, 83, 0, 77, 83, 0, 69, 61, 79, 77, 61, 79, 69, 61,
58, 77, 61, 58, 69, 61, 83, 77, 61, 83, 69, 61, 57, 77, 61, 57,
56, 61, 79, 71, 61, 79, 56, 82, 79, 71, 82, 79,252, 0,198, 79,
0,252, 0,230, 79, 0, 86, 83, 0, 87, 83, 0, 90, 83, 0, 91,
83, 0, 68, 81, 0, 76, 81, 0, 68, 81, 79, 76, 81, 79,252, 1,
183, 83, 0,252, 2,146, 83, 0,252, 0,106, 83, 0, 86, 58, 0,
87, 58, 0, 67, 57, 0, 75, 57, 0, 56, 62, 58, 71, 62, 58,252,
0,198, 58, 0,252, 0,230, 58, 0,252, 0,216, 58, 0,252, 0,
248, 58, 0,
/* 0200: */ 192, 51,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 0, 0, 85, 88,
0, 0, 0, 0, 0, 0, 91, 94, 97,100,103,106,109,112,115,118,
121,124,127,130,
56,106, 0, 71,106, 0, 56,107, 0, 71,107, 0, 65,106, 0, 73,
106, 0, 65,107, 0, 73,107, 0, 66,106, 0, 74,106, 0, 66,107,
0, 74,107, 0, 68,106, 0, 76,106, 0, 68,107, 0, 76,107, 0,
95,106, 0, 96,106, 0, 95,107, 0, 96,107, 0, 69,106, 0, 77,
106, 0, 69,107, 0, 77,107, 0, 97,108, 0, 98,108, 0, 99,108,
0,100,108, 0, 88, 83, 0, 89, 83, 0, 56, 82, 0, 71, 82, 0,
65, 64, 0, 73, 64, 0, 68, 61, 79, 76, 61, 79, 68, 60, 79, 76,
60, 79, 68, 82, 0, 76, 82, 0, 68, 82, 79, 76, 82, 79, 70, 79,
0, 78, 79, 0,
/* 0300: */ 64, 63,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 2, 4, 3, 3, 3, 3,
3, 5, 5, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 6, 6, 6, 6, 6, 3, 3, 3, 3, 1, 1, 1,
/* 0340: */ 128, 62,
1, 3, 5, 6, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,
0, 0, 0, 0, 52, 0, 0, 0, 0, 0, 0, 0, 0, 0, 56,
57, 0, 58, 0, 1,109, 0, 61, 58, 7, 1, 3, 3, 3, 1, 1,
1, 3, 3, 1, 1, 1, 3, 3, 3, 3, 1, 2, 3, 3, 1, 8,
9, 9, 8, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1,252, 2,185, 0,252, 0, 59, 0,
/* 0380: */ 197, 43,
1, 4, 7, 11, 14, 17, 0, 20, 0, 23, 26,
29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 35, 38, 41, 44, 47,
50,
110, 58, 0,111, 58, 0,252, 0,183, 0,112, 58, 0,113, 58, 0,
114, 58, 0,115, 58, 0,116, 58, 0,117, 58, 0,118, 61, 58,114,
61, 0,116, 61, 0,119, 58, 0,120, 58, 0,121, 58, 0,118, 58,
0,122, 61, 58,
/* 03c0: */ 138, 10,
1, 3, 5, 7, 9, 0,
0, 0, 0, 11, 15,
118, 61,122, 61,123, 58,122, 58,124, 58,252, 3,210, 58,252, 3,
210, 61,
/* 0400: */ 128, 57,
1, 3, 0, 5, 0, 0, 0, 9, 0, 0, 0, 0, 13, 17, 19, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 23,
125, 57,125, 61,252, 4, 19, 58,252, 4, 6, 61,252, 4, 26, 58,
126, 57,127, 80,126, 80,128, 80,
/* 0440: */ 144, 39,
1, 3, 0, 5, 0, 0, 0, 9, 0, 0, 0, 0, 13, 17, 19, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 21, 25,
129, 57,129, 61,252, 4, 51, 58,252, 4, 86, 61,252, 4, 58, 58,
128, 57,130, 80,252, 4,116,106,252, 4,117,106,
/* 0480: */ 67, 4,
1, 2, 3, 4, 5,
1, 1, 1, 1, 1,
/* 04c0: */ 129, 56,
1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
9, 13, 17, 21, 0, 0, 25, 27, 0, 0, 29, 33, 37, 41, 45, 49,
0, 0, 53, 55, 57, 59, 61, 65, 0, 0, 69, 73, 77, 81, 85, 87,
89, 91, 93, 95, 97,101, 0, 0,105,109,
252, 4, 22, 80,252, 4, 54, 80,252, 4, 16, 80,252, 4, 48, 80,
252, 4, 16, 61,252, 4, 48, 61,125, 80,129, 80,252, 4,216, 61,
252, 4,217, 61,252, 4, 22, 61,252, 4, 54, 61,252, 4, 23, 61,
252, 4, 55, 61,126, 79,128, 79,126, 61,128, 61,252, 4, 30, 61,
252, 4, 62, 61,252, 4,232, 61,252, 4,233, 61,252, 4, 45, 61,
252, 4, 77, 61,127, 79,130, 79,127, 61,130, 61,127, 94,130, 94,
252, 4, 39, 61,252, 4, 71, 61,252, 4, 43, 61,252, 4, 75, 61,
/* 0580: */ 81, 46,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 0, 46,
3, 1, 1, 1, 1, 3, 1, 1, 1, 10, 3, 1, 1, 1, 1, 1,
1, 3, 3, 3, 3, 3, 3, 1, 1, 3, 1, 1, 10, 11, 1, 12,
13, 14, 15, 16, 17, 18, 19, 20, 21, 21, 22, 23, 24, 25,
/* 05c0: */ 65, 6,
1, 2, 0, 3, 4, 0, 5,
26, 27, 1, 3, 20,
/* 0600: */ 144, 22,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 0, 0, 0, 0,
0, 0, 12, 14, 16, 20, 22,
1, 1, 1, 1, 1, 1, 1, 1, 28, 29, 30,131,132,131,133,252,
6, 72,133,131,134,252, 6, 74,133,
/* 0640: */ 75, 37,
1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
22,
31, 32, 33, 28, 29, 30, 34, 35, 1, 1, 3, 3, 1, 1, 1, 1,
1, 3, 1, 1, 3, 36,
/* 06c0: */ 128, 45,
1, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 9, 0, 0, 13, 14, 15, 16, 17, 18, 19, 0, 0, 20,
21, 22, 23, 24, 25, 0, 0, 26, 27, 0, 28, 29, 30, 31,
252, 6,213,133,252, 6,193,133,252, 6,210,133, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 3,
/* 0700: */ 81, 46,
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,
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
37, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 3, 3, 1, 3,
1,
/* 0740: */ 64, 10,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
1, 1, 3, 1, 3, 1, 3, 1, 3, 1, 1,
/* 07c0: */ 107, 18,
1, 2, 3, 4, 5,
6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10,
1, 1, 1, 1, 1, 1, 1, 3, 1, 3,
/* 0800: */ 86, 23,
1, 2, 3, 4, 0, 5, 6, 7, 8, 9,
10, 11, 12, 13, 0, 14, 15, 16, 0, 17, 18, 19, 20, 21,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
/* 0840: */ 89, 2,
1, 2, 3,
3, 3, 3,
/* 0880: */ 87, 8,
1, 2, 3, 4, 5, 6, 7, 8, 9,
1, 1, 3, 3, 3, 1, 1, 1, 1,
/* 08c0: */ 74, 53,
1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
23, 24, 0, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53,
1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1,
1, 1, 3, 3, 3, 31, 32, 33, 1, 1, 1, 3, 1, 1, 3, 3,
1, 1, 1, 1, 1,
/* 0900: */ 169, 19,
1, 0, 0, 0, 0, 0, 0,
0, 5, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 13,
252, 9, 40,135,252, 9, 48,135,252, 9, 51,135, 38,
/* 0940: */ 141, 18,
1, 0, 0,
0, 2, 3, 4, 5, 0, 0, 0, 6, 10, 14, 18, 22, 26, 30, 34,
39, 1, 3, 1, 1,252, 9, 21,135,252, 9, 22,135,252, 9, 23,
135,252, 9, 28,135,252, 9, 33,135,252, 9, 34,135,252, 9, 43,
135,252, 9, 47,135,
/* 0980: */ 124, 0,
1,
38,
/* 09c0: */ 139, 51,
1, 7, 13, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 18, 0, 22,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 26,
252, 9,199,252, 9,190,252, 9,199,252, 9,215, 39,252, 9,161,
136,252, 9,162,136,252, 9,175,136, 1,
/* 0a00: */ 179, 9,
1, 0, 0, 5, 0, 0, 0, 0, 0, 9,
252, 10, 50,137,252, 10, 56,137, 38,
/* 0a40: */ 141, 17,
1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 10, 0, 0, 14,
39,252, 10, 22,137,252, 10, 23,137,252, 10, 28,137,252, 10, 43,
137,
/* 0a80: */ 124, 0,
1,
38,
/* 0ac0: */ 77, 0,
1,
39,
/* 0b00: */ 124, 0,
1,
38,
/* 0b40: */ 136, 21,
1, 0, 0, 5, 9, 13, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 18,
138,252, 11, 86,138,252, 11, 62,138,252, 11, 87, 39,252, 11, 33,
139,252, 11, 34,139,
/* 0b80: */ 148, 0,
1,
252, 11,146,252, 11,215,
/* 0bc0: */ 138, 3,
1, 7, 13, 19,
252, 11,198,252, 11,190,252, 11,199,252, 11,190,252, 11,198,252,
11,215, 39,
/* 0c00: */ 124, 0,
1,
38,
/* 0c40: */ 136, 14,
1, 0, 0, 0, 0, 5, 0, 0,
0, 0, 0, 0, 0, 6, 7,
252, 12, 70,140, 39, 40, 41,
/* 0c80: */ 124, 0,
1,
38,
/* 0cc0: */ 192, 13,
1, 0, 0, 0, 0, 0, 0, 6, 9, 0, 14, 19, 0, 24,
252, 12,191,141, 0,142,141, 0,142,252, 12,214, 0,142,252, 12,
194, 0,142,252, 12,194,141, 39,
/* 0d00: */ 123, 1,
1, 2,
39, 39,
/* 0d40: */ 138, 3,
1, 7, 13, 19,
252, 13, 70,252, 13, 62,252, 13, 71,252, 13, 62,252, 13, 70,252,
13, 87, 39,
/* 0dc0: */ 202, 20,
1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 5, 10, 15,
39,143,144, 0,143,252, 13,207, 0,143,252, 13,207,144,143,252,
13,223, 0,
/* 0e00: */ 120, 2,
1, 2, 3,
42, 42, 39,
/* 0e40: */ 72, 3,
1, 2, 3, 4,
43, 43, 43, 43,
/* 0e80: */ 120, 2,
1, 2, 3,
44, 44, 39,
/* 0ec0: */ 72, 3,
1, 2, 3, 4,
45, 45, 45, 45,
/* 0f00: */ 88, 33,
1, 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, 3, 0, 4, 0, 5,
3, 3, 3, 3, 4,
/* 0f40: */ 131, 58,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0,
0, 0, 9, 0, 0, 0, 0, 13, 0, 0, 0, 0, 17, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 0,
0, 27, 28, 29, 31, 32, 34, 0, 38, 0, 42, 43, 44, 45,
252, 15, 66,145,252, 15, 76,145,252, 15, 81,145,252, 15, 86,145,
252, 15, 91,145,252, 15, 64,252, 15,181, 46, 47,146,147, 48,146,
148,252, 15,178,149,252, 15,179,149, 47, 47, 47, 47,
/* 0f80: */ 128, 57,
1, 2, 4, 5, 6, 0, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 0, 0,
0, 0, 17, 0, 0, 0, 0, 21, 0, 0, 0, 0, 25, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 29,
47,146,149, 1, 1, 39, 1, 1,252, 15,146,145,252, 15,156,145,
252, 15,161,145,252, 15,166,145,252, 15,171,145,252, 15,144,252,
15,181,
/* 0fc0: */ 70, 0,
1,
3,
/* 1000: */ 166, 20,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 7, 0, 8, 9,
252, 16, 37,252, 16, 46, 38, 39, 39,
/* 1080: */ 77, 0,
1,
3,
/* 1340: */ 93, 2,
1, 2, 3,
1, 1, 1,
/* 1700: */ 84, 32,
1, 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, 3,
39, 39, 39,
/* 17c0: */ 82, 11,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2,
39, 1,
/* 1880: */ 105, 0,
1,
11,
/* 1900: */ 121, 2,
1, 2, 3,
10, 1, 3,
/* 1a00: */ 87, 1,
1, 2,
1, 3,
/* 1a40: */ 96, 31,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 10,
39, 1, 1, 1, 1, 1, 1, 1, 1, 3,
/* 1a80: */ 112, 15,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 15,
1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 1, 1, 3, 3,
/* 1ac0: */ 64, 14,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3, 1, 1, 3, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1,
/* 1b00: */ 134, 55,
1, 0, 5, 0, 9, 0, 13, 0, 17, 0,
0, 0, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 25, 0, 0, 0, 0, 0, 0, 26, 0, 30,
252, 27, 5,150,252, 27, 7,150,252, 27, 9,150,252, 27, 11,150,
252, 27, 13,150,252, 27, 17,150, 38,252, 27, 58,150,252, 27, 60,
150,
/* 1b40: */ 128, 51,
1, 5, 0, 9, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 15, 16, 17, 18,
19, 20, 21, 22,
252, 27, 62,150,252, 27, 63,150,252, 27, 66,150, 39, 1, 3, 1,
1, 1, 1, 1, 1, 1,
/* 1b80: */ 106, 1,
1, 2,
39, 39,
/* 1bc0: */ 102, 13,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 2, 3,
38, 39, 39,
/* 1c00: */ 119, 0,
1,
38,
/* 1cc0: */ 80, 41,
1, 2, 3, 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 0, 17, 18, 19, 20, 21, 22, 23, 0, 0, 0, 0, 24, 0, 0,
0, 0, 0, 0, 25, 0, 0, 0, 26, 27,
1, 1, 1, 6, 3, 3, 3, 3, 3, 1, 1, 3, 3, 3, 3, 1,
6, 6, 6, 6, 6, 6, 6, 3, 1, 1, 1,
/* 1dc0: */ 64, 63,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64,
1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 9, 49, 3,
5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 2, 11, 11, 3, 50, 1, 8, 3, 1, 3,
/* 1e00: */ 192, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 96,
101,104,107,110,113,116,119,122,125,128,131,134,137,140,143,146,
149,152,155,158,161,164,167,170,173,176,179,182,185,188,191,194,
56,151, 0, 71,151, 0,152, 82, 0,153, 82, 0,152,154, 0,153,
154, 0,152,155, 0,153,155, 0, 63, 64, 58, 72, 64, 58, 84, 82,
0, 85, 82, 0, 84,154, 0, 85,154, 0, 84,155, 0, 85,155, 0,
84, 64, 0, 85, 64, 0, 84,156, 0, 85,156, 0, 65, 79, 57, 73,
79, 57, 65, 79, 58, 73, 79, 58, 65,156, 0, 73,156, 0, 65,157,
0, 73,157, 0, 65, 64, 80, 73, 64, 80,252, 0, 70, 82, 0,252,
0,102, 82, 0, 86, 79, 0, 87, 79, 0, 88, 82, 0, 89, 82, 0,
88,154, 0, 89,154, 0, 88, 61, 0, 89, 61, 0, 88, 64, 0, 89,
64, 0, 88,158, 0, 89,158, 0, 66,157, 0, 74,157, 0, 66, 61,
58, 74, 61, 58, 90, 58, 0, 91, 58, 0, 90,154, 0, 91,154, 0,
90,155, 0, 91,155, 0, 92,154, 0, 93,154, 0, 92,154, 79, 93,
154, 79, 92,155, 0, 93,155, 0, 92,156, 0, 93,156, 0,159, 58,
0,160, 58, 0,
/* 1e40: */ 192, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 66, 71, 76, 81, 84, 87, 90, 93, 96, 99,102,
105,108,111,114,117,120,123,126,129,132,135,138,141,144,147,150,
153,156,159,162,165,168,171,174,177,180,183,186,189,194,199,204,
159, 82, 0,160, 82, 0,159,154, 0,160,154, 0, 67, 82, 0, 75,
82, 0, 67,154, 0, 75,154, 0, 67,155, 0, 75,155, 0, 67,156,
0, 75,156, 0, 68, 60, 58, 76, 60, 58, 68, 60, 61, 76, 60, 61,
68, 79, 57, 76, 79, 57, 68, 79, 58, 76, 79, 58,252, 0, 80, 58,
0,252, 0,112, 58, 0,252, 0, 80, 82, 0,252, 0,112, 82, 0,
95, 82, 0, 96, 82, 0, 95,154, 0, 96,154, 0, 95,154, 79, 96,
154, 79, 95,155, 0, 96,155, 0, 97, 82, 0, 98, 82, 0, 97,154,
0, 98,154, 0, 97, 58, 82, 98, 58, 82, 97, 83, 82, 98, 83, 82,
97,154, 82, 98,154, 82, 99, 82, 0,100, 82, 0, 99,154, 0,100,
154, 0, 99,155, 0,100,155, 0, 99,156, 0,100,156, 0, 69,161,
0, 77,161, 0, 69,157, 0, 77,157, 0, 69,156, 0, 77,156, 0,
69, 60, 58, 77, 60, 58, 69, 79, 61, 77, 79, 61,252, 0, 86, 60,
0,252, 0,118, 60, 0,252, 0, 86,154, 0,252, 0,118,154, 0,
/* 1e80: */ 192, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 36, 41, 46, 51, 54,
57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 0, 87, 0, 0, 0, 0,
92, 95, 98,101,104,107,110,113,116,119,122,125,128,131,134,137,
140,143,146,149,152,155,158,161,164,167,170,173,176,179,182,185,
101, 57, 0,102, 57, 0,101, 58, 0,102, 58, 0,101, 61, 0,102,
61, 0,101, 82, 0,102, 82, 0,101,154, 0,102,154, 0,252, 0,
88, 82, 0,252, 0,120, 82, 0,252, 0, 88, 61, 0,252, 0,120,
61, 0, 70, 82, 0, 78, 82, 0,103, 59, 0,104, 59, 0,103,154,
0,104,154, 0,103,155, 0,104,155, 0, 89,155, 0,100, 61, 0,
102, 62, 0, 78, 62, 0,252, 1,127, 82, 0, 56,154, 0, 71,154,
0, 56,162, 0, 71,162, 0, 56, 59, 58, 71, 59, 58, 56, 59, 57,
71, 59, 57, 56, 59,162, 71, 59,162, 56, 59, 60, 71, 59, 60, 56,
154, 59, 71,154, 59, 56, 80, 58, 71, 80, 58, 56, 80, 57, 71, 80,
57, 56, 80,162, 71, 80,162, 56, 80, 60, 71, 80, 60, 56,154, 80,
71,154, 80, 65,154, 0, 73,154, 0, 65,162, 0, 73,162, 0, 65,
60, 0, 73, 60, 0, 65, 59, 58, 73, 59, 58,
/* 1ec0: */ 192, 57,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94,
97,100,103,106,109,112,115,118,121,124,127,130,133,136,139,142,
145,148,151,154,157,160,163,166,169,172,
65, 59, 57, 73, 59, 57, 65, 59,162, 73, 59,162, 65, 59, 60, 73,
59, 60, 65,154, 59, 73,154, 59, 66,162, 0, 74,162, 0, 66,154,
0, 74,154, 0, 68,154, 0, 76,154, 0, 68,162, 0, 76,162, 0,
68, 59, 58, 76, 59, 58, 68, 59, 57, 76, 59, 57, 68, 59,162, 76,
59,162, 68, 59, 60, 76, 59, 60, 68,154, 59, 76,154, 59, 68,105,
58, 76,105, 58, 68,105, 57, 76,105, 57, 68,105,162, 76,105,162,
68,105, 60, 76,105, 60, 68,105,154, 76,105,154, 69,154, 0, 77,
154, 0, 69,162, 0, 77,162, 0, 69,105, 58, 77,105, 58, 69,105,
57, 77,105, 57, 69,105,162, 77,105,162, 69,105, 60, 77,105, 60,
69,105,154, 77,105,154, 70, 57, 0, 78, 57, 0, 70,154, 0, 78,
154, 0, 70,162, 0, 78,162, 0, 70, 60, 0, 78, 60, 0,
/* 1f00: */ 192, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 0, 0, 67, 70, 73, 76, 79, 82, 0, 0,
85, 88, 91, 94, 97,100,103,106,109,112,115,118,121,124,127,130,
133,136,139,142,145,148,151,154,157,160,163,166,169,172,175,178,
119,109, 0,119,163, 0,119,109, 57,119,163, 57,119,109, 58,119,
163, 58,119,109,164,119,163,164,111,109, 0,111,163, 0,111,109,
57,111,163, 57,111,109, 58,111,163, 58,111,109,164,111,163,164,
120,109, 0,120,163, 0,120,109, 57,120,163, 57,120,109, 58,120,
163, 58,112,109, 0,112,163, 0,112,109, 57,112,163, 57,112,109,
58,112,163, 58,121,109, 0,121,163, 0,121,109, 57,121,163, 57,
121,109, 58,121,163, 58,121,109,164,121,163,164,113,109, 0,113,
163, 0,113,109, 57,113,163, 57,113,109, 58,113,163, 58,113,109,
164,113,163,164,118,109, 0,118,163, 0,118,109, 57,118,163, 57,
118,109, 58,118,163, 58,118,109,164,118,163,164,114,109, 0,114,
163, 0,114,109, 57,114,163, 57,114,109, 58,114,163, 58,114,109,
164,114,163,164,
/* 1f40: */ 192, 61,
1, 4, 7, 10, 13, 16, 0, 0, 19, 22, 25, 28, 31, 34, 0, 0,
37, 40, 43, 46, 49, 52, 55, 58, 0, 61, 0, 64, 0, 67, 0, 70,
73, 76, 79, 82, 85, 88, 91, 94, 97,100,103,106,109,112,115,118,
121,124,127,130,133,136,139,142,145,148,151,154,157,160,
123,109, 0,123,163, 0,123,109, 57,123,163, 57,123,109, 58,123,
163, 58,115,109, 0,115,163, 0,115,109, 57,115,163, 57,115,109,
58,115,163, 58,122,109, 0,122,163, 0,122,109, 57,122,163, 57,
122,109, 58,122,163, 58,122,109,164,122,163,164,116,163, 0,116,
163, 57,116,163, 58,116,163,164,124,109, 0,124,163, 0,124,109,
57,124,163, 57,124,109, 58,124,163, 58,124,109,164,124,163,164,
117,109, 0,117,163, 0,117,109, 57,117,163, 57,117,109, 58,117,
163, 58,117,109,164,117,163,164,119, 57, 0,119, 58, 0,120, 57,
0,120, 58, 0,121, 57, 0,121, 58, 0,118, 57, 0,118, 58, 0,
123, 57, 0,123, 58, 0,122, 57, 0,122, 58, 0,124, 57, 0,124,
58, 0,
/* 1f80: */ 0, 126,
1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61,
65, 69, 73, 77, 81, 85, 89, 93, 97,101,105,109,113,117,121,125,
129,133,137,141,145,149,153,157,161,165,169,173,177,181,185,189,
193,196,199,203,206, 0,210,213,217,220,223,226,229, 0,232,
119,109,165, 0,119,163,165, 0,119,109, 57,165,119,163, 57,165,
119,109, 58,165,119,163, 58,165,119,109,164,165,119,163,164,165,
111,109,165, 0,111,163,165, 0,111,109, 57,165,111,163, 57,165,
111,109, 58,165,111,163, 58,165,111,109,164,165,111,163,164,165,
121,109,165, 0,121,163,165, 0,121,109, 57,165,121,163, 57,165,
121,109, 58,165,121,163, 58,165,121,109,164,165,121,163,164,165,
113,109,165, 0,113,163,165, 0,113,109, 57,165,113,163, 57,165,
113,109, 58,165,113,163, 58,165,113,109,164,165,113,163,164,165,
124,109,165, 0,124,163,165, 0,124,109, 57,165,124,163, 57,165,
124,109, 58,165,124,163, 58,165,124,109,164,165,124,163,164,165,
117,109,165, 0,117,163,165, 0,117,109, 57,165,117,163, 57,165,
117,109, 58,165,117,163, 58,165,117,109,164,165,117,163,164,165,
119, 80, 0,119, 79, 0,119, 57,165, 0,119,165, 0,119, 58,165,
0,119,164, 0,119,164,165, 0,111, 80, 0,111, 79, 0,111, 57,
0,111, 58, 0,111,165, 0,118, 0,
/* 1fc0: */ 193, 60,
1, 4, 7, 10, 0, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40,
43, 46, 49, 52, 0, 0, 55, 58, 61, 64, 67, 70, 0, 73, 76, 79,
82, 85, 88, 91, 94, 99,104,107,110,113,116,119,122,127,130,133,
0, 0,137,140,143, 0,146,149,152,155,158,161,164,167,
110,164, 0,121, 57,165,121,165, 0,121, 58,165,121,164, 0,121,
164,165,112, 57, 0,112, 58, 0,113, 57, 0,113, 58, 0,113,165,
0,166, 57, 0,166, 58, 0,166,164, 0,118, 80, 0,118, 79, 0,
118, 61, 57,118, 61, 58,118,164, 0,118, 61,164,114, 80, 0,114,
79, 0,114, 57, 0,114, 58, 0,167, 57, 0,167, 58, 0,167,164,
0,122, 80, 0,122, 79, 0,122, 61, 57,122, 61, 58,252, 3,193,
109, 0,252, 3,193,163, 0,122,164, 0,122, 61,164,116, 80, 0,
116, 79, 0,116, 57, 0,116, 58, 0,252, 3,161,163, 0,110, 57,
0,110, 58, 0,252, 0, 96, 0,124, 57,165,124,165, 0,124, 58,
165,124,164, 0,124,164,165,115, 57, 0,115, 58, 0,117, 57, 0,
117, 58, 0,117,165, 0,252, 0,180, 0,
/* 2000: */ 64, 1,
1, 4,
252, 32, 2,252, 32, 3,
/* 20c0: */ 80, 32,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0, 0, 0,
0, 14, 0, 0, 0, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
26,
1, 1, 6, 6, 1, 1, 1, 1, 6, 6, 6, 1, 1, 1, 6, 6,
1, 3, 1, 6, 6, 3, 3, 3, 3, 1,
/* 2100: */ 166, 5,
1, 0, 0, 0, 3, 5,
117, 0, 90, 0, 56, 62,
/* 2180: */ 154, 20,
1, 5, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9,
252, 33,144,168,252, 33,146,168,252, 33,148,168,
/* 21c0: */ 141, 2,
1, 5, 9,
252, 33,208,168,252, 33,212,168,252, 33,210,168,
/* 2200: */ 132, 34,
1, 0, 0, 0, 0, 5, 0, 0, 9, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 13, 0, 17,
252, 34, 3,168,252, 34, 8,168,252, 34, 11,168,252, 34, 35,168,
252, 34, 37,168,
/* 2240: */ 129, 56,
1, 0, 0, 5, 0, 0, 9, 0, 13, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
17, 0, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25, 29, 33,
37, 41, 0, 0, 45, 49, 0, 0, 53, 57,
252, 34, 60,168,252, 34, 67,168,252, 34, 69,168,252, 34, 72,168,
252, 0, 61,168,252, 34, 97,168,252, 34, 77,168,252, 0, 60,168,
252, 0, 62,168,252, 34,100,168,252, 34,101,168,252, 34,114,168,
252, 34,115,168,252, 34,118,168,252, 34,119,168,
/* 2280: */ 128, 47,
1, 5, 0, 0, 9, 13, 0, 0, 17, 21, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25, 29, 33, 37,
252, 34,122,168,252, 34,123,168,252, 34,130,168,252, 34,131,168,
252, 34,134,168,252, 34,135,168,252, 34,162,168,252, 34,168,168,
252, 34,169,168,252, 34,171,168,
/* 22c0: */ 160, 13,
1, 5, 9, 13, 0, 0, 0, 0, 0, 0, 17, 21, 25, 29,
252, 34,124,168,252, 34,125,168,252, 34,145,168,252, 34,146,168,
252, 34,178,168,252, 34,179,168,252, 34,180,168,252, 34,181,168,
/* 2300: */ 105, 1,
1, 4,
252, 48, 8,252, 48, 9,
/* 2ac0: */ 156, 0,
1,
252, 42,221,168,
/* 2cc0: */ 111, 2,
1,
2, 3,
1, 1, 1,
/* 2d40: */ 127, 0,
1,
39,
/* 2dc0: */ 96, 31,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* 3000: */ 106, 5,
1, 2, 3, 4, 5, 6,
50, 11, 2, 10, 51, 51,
/* 3040: */ 140, 49,
1, 0, 5, 0,
9, 0, 13, 0, 17, 0, 21, 0, 25, 0, 29, 0, 33, 0, 37, 0,
41, 0, 45, 0, 0, 49, 0, 53, 0, 57, 0, 0, 0, 0, 0, 0,
61, 65, 0, 69, 73, 0, 77, 81, 0, 85, 89, 0, 93, 97,
252, 48, 75,169,252, 48, 77,169,252, 48, 79,169,252, 48, 81,169,
252, 48, 83,169,252, 48, 85,169,252, 48, 87,169,252, 48, 89,169,
252, 48, 91,169,252, 48, 93,169,252, 48, 95,169,252, 48, 97,169,
252, 48,100,169,252, 48,102,169,252, 48,104,169,252, 48,111,169,
252, 48,111,170,252, 48,114,169,252, 48,114,170,252, 48,117,169,
252, 48,117,170,252, 48,120,169,252, 48,120,170,252, 48,123,169,
252, 48,123,170,
/* 3080: */ 148, 42,
1, 0, 0, 0, 0, 5, 6, 0, 0, 0, 7, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 15, 0,
19, 0, 23, 0, 27, 0, 31, 0, 35, 0, 39, 0, 43, 0, 47,
252, 48, 70,169, 52, 52,252, 48,157,169,252, 48,171,169,252, 48,
173,169,252, 48,175,169,252, 48,177,169,252, 48,179,169,252, 48,
181,169,252, 48,183,169,252, 48,185,169,252, 48,187,169,252, 48,
189,169,
/* 30c0: */ 128, 62,
1, 0, 5, 0, 0, 9, 0, 13, 0, 17, 0, 0, 0, 0, 0, 0,
21, 25, 0, 29, 33, 0, 37, 41, 0, 45, 49, 0, 53, 57, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 61, 0, 0, 65, 69, 73, 77, 0, 0, 0, 81,
252, 48,191,169,252, 48,193,169,252, 48,196,169,252, 48,198,169,
252, 48,200,169,252, 48,207,169,252, 48,207,170,252, 48,210,169,
252, 48,210,170,252, 48,213,169,252, 48,213,170,252, 48,216,169,
252, 48,216,170,252, 48,219,169,252, 48,219,170,252, 48,166,169,
252, 48,239,169,252, 48,240,169,252, 48,241,169,252, 48,242,169,
252, 48,253,169,
/* a640: */ 111, 14,
1,
0, 0, 0, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* a680: */ 94, 1,
1, 2,
1, 1,
/* a6c0: */ 112, 1,
1, 2,
1, 1,
/* a800: */ 70, 38,
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, 2,
39, 39,
/* a8c0: */ 68, 45,
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,
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19,
39, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1,
/* a900: */ 107, 2,
1, 2, 3,
3, 3, 3,
/* a940: */ 83, 0,
1,
39,
/* a980: */ 115, 0,
1,
38,
/* a9c0: */ 64, 0,
1,
39,
/* aa80: */ 112, 15,
1, 0, 2, 3, 4, 0, 0, 5, 6, 0, 0, 0, 0, 0, 7, 8,
1, 1, 1, 3, 1, 1, 1, 1,
/* aac0: */ 65, 53,
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, 2,
1, 39,
/* abc0: */ 109, 0,
1,
39,
/* f900: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 23, 24, 27, 30, 33, 36, 39, 42,
45, 48, 51, 54, 57, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88,
91, 94, 97,100,103,106,109,112,115,118,119,122,125,128,131,134,
137,140,143,146,149,152,155,158,161,164,167,170,173,176,179,182,
252,140, 72,252,102,244,252,142,202,252,140,200,252,110,209,252,
78, 50,252, 83,229,171,171,252, 89, 81,252,145,209,252, 85,135,
252, 89, 72,252, 97,246,252,118,105,252,127,133,252,134, 63,252,
135,186,252,136,248,252,144,143,172,252,109, 27,252,112,217,252,
115,222,252,132, 61,252,145,106,252,153,241,252, 78,130,252, 83,
117,252,107, 4,252,114, 27,252,134, 45,252,158, 30,252, 93, 80,
252,111,235,252,133,205,252,137,100,252, 98,201,252,129,216,252,
136, 31,252, 94,202,173,252,109,106,252,114,252,252,144,206,252,
79,134,252, 81,183,252, 82,222,252,100,196,252,106,211,252,114,
16,252,118,231,252,128, 1,252,134, 6,252,134, 92,252,141,239,
252,151, 50,252,155,111,252,157,250,252,120,140,252,121,127,252,
125,160,252,131,201,252,147, 4,
/* f940: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 86, 89, 92,
93, 96, 99,102,105,108,111,114,117,120,123,126,129,132,135,138,
141,142,145,148,151,154,157,160,163,166,169,172,175,178,181,184,
252,158,127,252,138,214,252, 88,223,252, 95, 4,252,124, 96,252,
128,126,252,114, 98,252,120,202,252,140,194,252,150,247,252, 88,
216,252, 92, 98,252,106, 19,252,109,218,252,111, 15,252,125, 47,
252,126, 55,252,150, 75,252, 82,210,252,128,139,252, 81,220,252,
81,204,252,122, 28,252,125,190,252,131,241,252,150,117,252,139,
128,252, 98,207,172,252,138,254,252, 78, 57,174,252, 96, 18,252,
115,135,252,117,112,252, 83, 23,252,120,251,252, 79,191,252, 95,
169,252, 78, 13,252,108,204,252,101,120,252,125, 34,252, 83,195,
252, 88, 94,252,119, 1,252,132, 73,252,138,170,175,252,143,176,
252,108,136,252, 98,254,252,130,229,252, 99,160,252,117,101,252,
78,174,252, 81,105,252, 81,201,252,104,129,252,124,231,252,130,
111,252,138,210,252,145,207,252, 82,245,
/* f980: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 68, 71, 74, 77, 80, 83, 86, 89, 92,
95, 98,101,104,107,110,113,116,119,122,125,126,129,132,135,138,
141,144,147,150,153,156,159,162,165,168,171,174,177,180,183,186,
252, 84, 66,252, 89,115,252, 94,236,252,101,197,252,111,254,252,
121, 42,252,149,173,252,154,106,252,158,151,252,158,206,252, 82,
155,252,102,198,252,107,119,252,143, 98,252, 94,116,252, 97,144,
252, 98, 0,252,100,154,252,111, 35,252,113, 73,252,116,137,252,
121,202,176,252,128,111,252,143, 38,252,132,238,252,144, 35,252,
147, 74,252, 82, 23,252, 82,163,252, 84,189,252,112,200,252,136,
194,252,138,170,252, 94,201,252, 95,245,252, 99,123,252,107,174,
252,124, 62,252,115,117,252, 78,228,252, 86,249,174,252, 93,186,
252, 96, 28,252,115,178,252,116,105,252,127,154,252,128, 70,252,
146, 52,252,150,246,252,151, 72,252,152, 24,252, 79,139,252,121,
174,252,145,180,252,150,184,252, 96,225,252, 78,134,252, 80,218,
252, 91,238,252, 92, 63,252,101,153,172,
/* f9c0: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 32, 35, 38, 41, 44,
47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92,
95, 98,101,104,107,110,113,116,119,122,125,128,131,134,137,140,
143,146,149,152,155,158,161,164,167,170,173,176,179,182,185,188,
252,113,206,252,118, 66,252,132,252,252,144,124,252,159,141,252,
102,136,252,150, 46,252, 82,137,252,103,123,252,103,243,177,252,
110,156,252,116, 9,252,117, 89,252,120,107,252,125, 16,252,152,
94,252, 81,109,252, 98, 46,252,150,120,252, 80, 43,252, 93, 25,
252,109,234,252,143, 42,252, 95,139,252, 97, 68,252,104, 23,252,
115,135,252,150,134,252, 82, 41,252, 84, 15,252, 92,101,252,102,
19,252,103, 78,252,104,168,252,108,229,252,116, 6,252,117,226,
252,127,121,252,136,207,252,136,225,252,145,204,252,150,226,252,
83, 63,252,110,186,252, 84, 29,252,113,208,252,116,152,252,133,
250,252,150,163,252,156, 87,252,158,159,252,103,151,252,109,203,
252,129,232,252,122,203,252,123, 32,252,124,146,252,114,192,252,
112,153,252,139, 88,252, 78,192,252,131, 54,252, 82, 58,
/* fa00: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 0, 0,
43, 0, 46, 0, 0, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 0,
79, 0, 82, 0, 0, 85, 88, 0, 0, 0, 91, 94, 97,100,103,106,
109,112,115,118,121,124,127,130,133,136,139,142,145,148,151,154,
252, 82, 7,252, 94,166,252, 98,211,252,124,214,252, 91,133,252,
109, 30,252,102,180,252,143, 59,252,136, 76,252,150, 77,252,137,
139,252, 94,211,252, 81, 64,252, 85,192,252, 88, 90,252,102,116,
252, 81,222,252,115, 42,252,118,202,252,121, 60,252,121, 94,252,
121,101,252,121,143,252,151, 86,252,124,190,252,127,189,252,134,
18,252,138,248,252,144, 56,252,144,253,252,152,239,252,152,252,
252,153, 40,252,157,180,252,144,222,252,150,183,252, 79,174,252,
80,231,252, 81, 77,252, 82,201,252, 82,228,252, 83, 81,252, 85,
157,252, 86, 6,252, 86,104,252, 88, 64,252, 88,168,252, 92,100,
252, 92,110,252, 96,148,252, 97,104,178,
/* fa40: */ 64, 63,
1, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44,
47, 50, 53, 56, 59, 62, 65, 68, 69, 72, 75, 78, 79, 82, 85, 88,
91, 94, 97,100,103,106,109,112,115,118,121,124,127,130, 0, 0,
133,136,139,142,145,148,151,154,157,160,163,166,169,172,175,178,
179,252,101, 79,252,101,226,252,102,145,252,104,133,252,109,119,
252,110, 26,252,111, 34,252,113,110,252,114, 43,252,116, 34,252,
120,145,252,121, 62,252,121, 73,252,121, 72,252,121, 80,252,121,
86,252,121, 93,252,121,141,252,121,142,252,122, 64,252,122,129,
252,123,192,176,252,126, 9,252,126, 65,252,127,114,180,252,129,
237,252,130,121,252,130,121,252,132, 87,252,137, 16,252,137,150,
252,139, 1,252,139, 57,252,140,211,252,141, 8,252,143,182,252,
144, 56,252,150,227,252,151,255,252,152, 59,252, 96,117,254, 66,
238,252,130, 24,252, 78, 38,252, 81,181,252, 81,104,252, 79,128,
252, 81, 69,252, 81,128,252, 82,199,252, 82,250,252, 85,157,252,
85, 85,252, 85,153,252, 85,226,252, 88, 90,252, 88,179,252, 89,
68,252, 89, 84,
/* fa80: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 29, 32, 33, 36, 39, 42,
45, 48, 51, 52, 55, 58, 61, 62, 63, 66, 69, 72, 75, 78, 81, 84,
87, 90, 93, 96, 99,102,105,108,111,114,117,120,123,126,129,132,
135,136,139,140,143,146,149,152,155,158,161,164,167,170,173,176,
252, 90, 98,252, 91, 40,252, 94,210,252, 94,217,252, 95,105,252,
95,173,252, 96,216,252, 97, 78,252, 97, 8,178,252, 97, 96,179,
252, 98, 52,252, 99,196,252,100, 28,252,100, 82,252,101, 86,252,
102,116,173,252,103, 27,252,103, 86,252,107,121,175,177,252,110,
219,252,110,203,252,111, 34,252,112, 30,252,113,110,252,119,167,
252,114, 53,252,114,175,252,115, 42,252,116,113,252,117, 6,252,
117, 59,252,118, 29,252,118, 31,252,118,202,252,118,219,252,118,
244,252,119, 74,252,119, 64,252,120,204,252,122,177,252,123,192,
252,124,123,252,125, 91,176,252,127, 62,180,252,131, 82,252,131,
239,252,135,121,252,137, 65,252,137,134,252,137,150,252,138,191,
252,138,248,252,138,203,252,139, 1,252,138,254,252,138,237,252,
139, 57,
/* fac0: */ 64, 25,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 35, 38, 41, 42,
45, 48, 51, 54, 57, 60, 63, 66, 69, 72,
252,139,138,252,141, 8,252,143, 56,252,144,114,252,145,153,252,
146,118,252,150,124,252,150,227,252,151, 86,252,151,219,252,151,
255,181,252,152, 59,252,155, 18,171,254, 40, 74,254, 40, 68,254,
51,213,252, 59,157,252, 64, 24,252, 64, 57,254, 82, 73,254, 92,
208,254,126,211,252,159, 67,252,159,142,
/* fb00: */ 221, 33,
1, 6, 7,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 15, 18, 21, 24, 27,
30, 33, 38, 43, 48, 53, 58, 0, 63, 68, 73, 78, 83, 0, 88,
252, 5,217,182, 0, 53,252, 5,242,183, 0,184,185, 0,184,186,
0,184,187,185,184,187,186,188,183, 0,188,189, 0,188,187, 0,
252, 5,209,187, 0,252, 5,210,187, 0,252, 5,211,187, 0,252,
5,212,187, 0,252, 5,213,187, 0,252, 5,214,187, 0,252, 5,
216,187, 0,252, 5,217,187, 0,252, 5,218,187, 0,252, 5,219,
187, 0,252, 5,220,187, 0,252, 5,222,187, 0,
/* fb40: */ 128, 14,
1, 5, 0, 9, 13, 0, 17, 21, 25, 29, 31, 35, 39, 43, 47,
252, 5,224,187,252, 5,225,187,252, 5,227,187,252, 5,228,187,
252, 5,230,187,252, 5,231,187,252, 5,232,187,184,187,252, 5,
234,187,252, 5,213,190,252, 5,209,191,252, 5,219,191,252, 5,
228,191,
/* fe00: */ 96, 15,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 1, 1,
/* 101c0: */ 125, 0,
1,
3,
/* 102c0: */ 96, 0,
1,
3,
/* 10340: */ 118, 4,
1, 2, 3, 4, 5,
1, 1, 1, 1, 1,
/* 105c0: */ 137, 27,
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, 5,
253, 5,210, 82,253, 5,218, 82,
/* 10a00: */ 77, 50,
1, 0, 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, 3, 4, 5, 0, 0, 0, 0, 6,
3, 1, 1, 6, 3, 39,
/* 10ac0: */ 101, 1,
1, 2,
1, 3,
/* 10d00: */ 100, 3,
1, 2, 3, 4,
1, 1, 1, 1,
/* 10d40: */ 105, 4,
1, 2, 3, 4, 5,
1, 1, 1, 1, 1,
/* 10e80: */ 107, 1,
1, 2,
1, 1,
/* 10ec0: */ 125, 2,
1, 2, 3,
3, 3, 3,
/* 10f40: */ 70, 10,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11,
3, 3, 1, 1, 1, 3, 1, 3, 3, 3, 3,
/* 10f80: */ 66, 3,
1, 2, 3, 4,
1, 3, 1, 3,
/* 11040: */ 70, 57,
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,
2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
39, 39, 39,
/* 11080: */ 154, 32,
1, 0, 5, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 14,
253, 16,153,192,253, 16,155,192,253, 16,165,192, 39, 38,
/* 11100: */ 128, 52,
1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 10,
0, 0, 0, 16, 17,
1, 1, 1,253, 17, 49,253, 17, 39,253, 17, 50,253, 17, 39, 39,
39,
/* 11140: */ 115, 0,
1,
38,
/* 111c0: */ 64, 10,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2,
39, 38,
/* 11200: */ 117, 1,
1, 2,
39, 38,
/* 112c0: */ 105, 1,
1, 2,
38, 39,
/* 11300: */ 123, 1,
1, 2,
38, 38,
/* 11340: */ 139, 41,
1, 7, 13, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 14, 15, 16, 17, 18, 19, 20, 0, 0, 0,
21, 22, 23, 24, 25,
253, 19, 71,253, 19, 62,253, 19, 71,253, 19, 87, 39, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1,
/* 11380: */ 131, 14,
1, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0,
0, 15,
253, 19,130,193,253, 19,132,253, 19,187,253, 19,139,194,253, 19,
144,193,
/* 113c0: */ 133, 11,
1, 0, 3, 7, 0, 0, 0, 0, 0, 9, 10,
11,
194,194,194,253, 19,184,194,193, 39, 39, 39,
/* 11440: */ 66, 28,
1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
39, 38, 1,
/* 11480: */ 187, 3,
1, 5, 0, 9,
195,253, 20,186,195,253, 20,176,195,253, 20,189,
/* 114c0: */ 66, 1,
1, 2,
39, 38,
/* 11580: */ 186, 5,
1, 7, 0, 0, 0, 13,
253, 21,184,253, 21,175,253, 21,185,253, 21,175, 39,
/* 115c0: */ 64, 0,
1,
38,
/* 11600: */ 127, 0,
1,
39,
/* 11680: */ 118, 1,
1, 2,
39, 38,
/* 11700: */ 107, 0,
1,
39,
/* 11800: */ 121, 1,
1, 2,
39, 38,
/* 11900: */ 184, 6,
1, 0, 0, 0, 0, 7, 8,
253, 25, 53,253, 25, 48, 39, 39,
/* 11940: */ 67, 0,
1,
38,
/* 119c0: */ 96, 0,
1,
39,
/* 11a00: */ 116, 0,
1,
39,
/* 11a40: */ 71, 0,
1,
39,
/* 11a80: */ 89, 0,
1,
39,
/* 11c00: */ 127, 0,
1,
39,
/* 11d40: */ 66, 3,
1, 0, 2, 3,
38, 39, 39,
/* 11d80: */ 87, 0,
1,
39,
/* 11f40: */ 65, 1,
1, 2,
39, 39,
/* 16100: */ 225, 14,
1, 4, 7, 10, 13, 18, 21, 24, 0, 0, 0, 0, 0, 0, 29,
196,196, 0,196,197, 0,196,198, 0,197,198, 0,196,253, 97, 32,
0,196,196,198,196,197,198,196,196,253, 97, 32, 39,
/* 16ac0: */ 112, 4,
1, 2, 3, 4, 5,
6, 6, 6, 6, 6,
/* 16b00: */ 112, 6,
1, 2, 3, 4, 5, 6, 7,
1, 1, 1, 1, 1, 1, 1,
/* 16d40: */ 232, 2,
1, 4, 9,
199,199, 0,253,109, 99,199, 0,253,109, 99,199,199,
/* 16fc0: */ 112, 1,
1, 2,
54, 54,
/* 1bc80: */ 94, 0,
1,
6,
/* 1d140: */ 222, 33,
1, 6,
9, 12, 15, 18, 21, 24, 25, 26, 27, 28, 0, 0, 0, 29, 30, 31,
32, 33, 34, 0, 0, 0, 0, 0, 0, 0, 0, 35, 36, 37, 38, 39,
253,209, 87,200, 0,201,200, 0,201,200,202,201,200,203,201,200,
204,201,200,205,201,200,206, 4, 4, 6, 6, 6, 55, 4, 4, 4,
4, 4, 3, 3, 3, 3, 3,
/* 1d180: */ 192, 63,
1, 2, 3, 0, 0, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 12, 13, 14, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 18, 21, 24, 27,
3, 3, 3, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1,207,200,
0,208,200, 0,207,200,202,208,200,202,207,200,203,
/* 1d1c0: */ 192, 0,
1,
208,200,203,
/* 1d240: */ 66, 2,
1, 2, 3,
1, 1, 1,
/* 1e000: */ 64, 42,
1, 2, 3, 4, 5, 6, 7, 0, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 0, 0, 25, 26, 27, 28, 29,
30, 31, 0, 32, 33, 0, 34, 35, 36, 37, 38,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1,
/* 1e080: */ 79, 0,
1,
1,
/* 1e100: */ 112, 6,
1, 2, 3, 4, 5, 6, 7,
1, 1, 1, 1, 1, 1, 1,
/* 1e280: */ 110, 0,
1,
1,
/* 1e2c0: */ 108, 3,
1, 2, 3, 4,
1, 1, 1, 1,
/* 1e4c0: */ 108, 3,
1, 2, 3, 4,
2, 2, 3, 1,
/* 1e5c0: */ 110, 1,
1, 2,
1, 3,
/* 1e8c0: */ 80, 6,
1, 2, 3, 4, 5, 6, 7,
3, 3, 3, 3, 3, 3, 3,
/* 1e940: */ 68, 6,
1, 2, 3, 4, 5, 6, 7,
1, 1, 1, 1, 1, 1, 38,
/* 2f800: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94,
97,100,103,106,109,112,115,118,121,124,127,130,133,136,139,142,
145,148,149,150,151,154,157,160,163,166,169,172,175,178,181,184,
252, 78, 61,252, 78, 56,252, 78, 65,254, 1, 34,252, 79, 96,252,
79,174,252, 79,187,252, 80, 2,252, 80,122,252, 80,153,252, 80,
231,252, 80,207,252, 52,158,254, 6, 58,252, 81, 77,252, 81, 84,
252, 81,100,252, 81,119,254, 5, 28,252, 52,185,252, 81,103,252,
81,141,254, 5, 75,252, 81,151,252, 81,164,252, 78,204,252, 81,
172,252, 81,181,254,145,223,252, 81,245,252, 82, 3,252, 52,223,
252, 82, 59,252, 82, 70,252, 82,114,252, 82,119,252, 53, 21,252,
82,199,252, 82,201,252, 82,228,252, 82,250,252, 83, 5,252, 83,
6,252, 83, 23,252, 83, 73,252, 83, 81,252, 83, 90,252, 83,115,
252, 83,125,209,209,209,254, 10, 44,252,112,112,252, 83,202,252,
83,223,254, 11, 99,252, 83,235,252, 83,241,252, 84, 6,252, 84,
158,252, 84, 56,252, 84, 72,252, 84,104,
/* 2f840: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94,
97,100,103,106,109,112,115,118,121,124,127,130,133,136,139,142,
143,146,149,152,155,158,161,164,167,170,173,176,179,182,185,188,
252, 84,162,252, 84,246,252, 85, 16,252, 85, 83,252, 85, 99,252,
85,132,252, 85,132,252, 85,153,252, 85,171,252, 85,179,252, 85,
194,252, 87, 22,252, 86, 6,252, 87, 23,252, 86, 81,252, 86,116,
252, 82, 7,252, 88,238,252, 87,206,252, 87,244,252, 88, 13,252,
87,139,252, 88, 50,252, 88, 49,252, 88,172,254, 20,228,252, 88,
242,252, 88,247,252, 89, 6,252, 89, 26,252, 89, 34,252, 89, 98,
254, 22,168,254, 22,234,252, 89,236,252, 90, 27,252, 90, 39,252,
89,216,252, 90,102,252, 54,238,252, 54,252,252, 91, 8,252, 91,
62,252, 91, 62,254, 25,200,252, 91,195,252, 91,216,174,252, 91,
243,254, 27, 24,252, 91,255,252, 92, 6,252, 95, 83,252, 92, 34,
252, 55,129,252, 92, 96,252, 92,110,252, 92,192,252, 92,141,254,
29,228,252, 93, 67,254, 29,230,252, 93,110,252, 93,107,
/* 2f880: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94,
97,100,103,106,109,112,115,118,121,124,127,130,131,134,137,140,
143,144,147,150,153,156,159,162,165,168,171,174,177,180,183,186,
252, 93,124,252, 93,225,252, 93,226,252, 56, 47,252, 93,253,252,
94, 40,252, 94, 61,252, 94,105,252, 56, 98,254, 33,131,252, 56,
124,252, 94,176,252, 94,179,252, 94,182,252, 94,202,254,163,146,
252, 94,254,254, 35, 49,254, 35, 49,252,130, 1,252, 95, 34,252,
95, 34,252, 56,199,254, 50,184,254, 97,218,252, 95, 98,252, 95,
107,252, 56,227,252, 95,154,252, 95,205,252, 95,215,252, 95,249,
252, 96,129,252, 57, 58,252, 57, 28,252, 96,148,254, 38,212,252,
96,199,252, 97, 72,252, 97, 76,252, 97, 78,252, 97, 76,252, 97,
122,178,252, 97,178,252, 97,164,252, 97,175,252, 97,222,179,252,
97,246,252, 98, 16,252, 98, 27,252, 98, 93,252, 98,177,252, 98,
212,252, 99, 80,254, 43, 12,252, 99, 61,252, 98,252,252, 99,104,
252, 99,131,252, 99,228,254, 43,241,252,100, 34,
/* 2f8c0: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 74, 77, 80, 83, 86, 89, 92,
95, 98,101,104,107,110,113,116,119,122,125,128,131,134,137,140,
143,146,149,152,155,158,159,162,165,168,171,174,177,180,183,186,
252, 99,197,252, 99,169,252, 58, 46,252,100,105,252,100,126,252,
100,157,252,100,119,252, 58,108,252,101, 79,252,101,108,254, 48,
10,252,101,227,252,102,248,252,102, 73,252, 59, 25,252,102,145,
252, 59, 8,252, 58,228,252, 81,146,252, 81,149,252,103, 0,252,
102,156,252,128,173,252, 67,217,173,252,103, 27,252,103, 33,252,
103, 94,252,103, 83,254, 51,195,252, 59, 73,252,103,250,252,103,
133,252,104, 82,252,104,133,254, 52,109,252,104,142,252,104, 31,
252,105, 20,252, 59,157,252,105, 66,252,105,163,252,105,234,252,
106,168,254, 54,163,252,106,219,252, 60, 24,252,107, 33,254, 56,
167,252,107, 84,252, 60, 78,252,107,114,252,107,159,175,252,107,
187,254, 58,141,254, 29, 11,254, 58,250,252,108, 78,254, 60,188,
252,108,191,252,108,205,252,108,103,252,109, 22,
/* 2f900: */ 64, 63,
1, 4, 7, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44,
47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92,
95, 98,101,104,107,110,113,116,119,122,125,128,131,134,137,140,
143,146,149,152,155,158,161,164,167,170,173,176,179,182,185,188,
252,109, 62,252,109,119,177,252,109,105,252,109,120,252,109,133,
254, 61, 30,252,109, 52,252,110, 47,252,110,110,252, 61, 51,252,
110,203,252,110,199,254, 62,209,252,109,249,252,111,110,254, 63,
94,254, 63,142,252,111,198,252,112, 57,252,112, 30,252,112, 27,
252, 61,150,252,112, 74,252,112,125,252,112,119,252,112,173,254,
5, 37,252,113, 69,254, 66, 99,252,113,156,254, 67,171,252,114,
40,252,114, 53,252,114, 80,254, 70, 8,252,114,128,252,114,149,
254, 71, 53,254, 72, 20,252,115,122,252,115,139,252, 62,172,252,
115,165,252, 62,184,252, 62,184,252,116, 71,252,116, 92,252,116,
113,252,116,133,252,116,202,252, 63, 27,252,117, 36,254, 76, 54,
252,117, 62,254, 76,146,252,117,112,254, 33,159,252,118, 16,254,
79,161,254, 79,184,254, 80, 68,252, 63,252,252, 64, 8,
/* 2f940: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94,
97,100,103,106,109,112,115,118,121,124,127,130,133,136,139,142,
145,148,151,154,157,160,163,166,169,172,175,176,179,182,185,188,
252,118,244,254, 80,243,254, 80,242,254, 81, 25,254, 81, 51,252,
119, 30,252,119, 31,252,119, 31,252,119, 74,252, 64, 57,252,119,
139,252, 64, 70,252, 64,150,254, 84, 29,252,120, 78,252,120,140,
252,120,204,252, 64,227,254, 86, 38,252,121, 86,254, 86,154,254,
86,197,252,121,143,252,121,235,252, 65, 47,252,122, 64,252,122,
74,252,122, 79,254, 89,124,254, 90,167,254, 90,167,252,122,238,
252, 66, 2,254, 91,171,252,123,198,252,123,201,252, 66, 39,254,
92,128,252,124,210,252, 66,160,252,124,232,252,124,227,252,125,
0,254, 95,134,252,125, 99,252, 67, 1,252,125,199,252,126, 2,
252,126, 69,252, 67, 52,254, 98, 40,254, 98, 71,252, 67, 89,254,
98,217,252,127,122,254, 99, 62,252,127,149,252,127,250,180,254,
100,218,254,101, 35,252,128, 96,254,101,168,252,128,112,
/* 2f980: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94,
97,100,103,106,109,112,115,118,121,124,127,130,133,136,139,142,
145,148,151,154,157,160,163,166,169,172,175,178,181,184,187,190,
254, 51, 95,252, 67,213,252,128,178,252,129, 3,252, 68, 11,252,
129, 62,252, 90,181,254,103,167,254,103,181,254, 51,147,254, 51,
156,252,130, 1,252,130, 4,252,143,158,252, 68,107,252,130,145,
252,130,139,252,130,157,252, 82,179,252,130,177,252,130,179,252,
130,189,252,130,230,254,107, 60,252,130,229,252,131, 29,252,131,
99,252,131,173,252,131, 35,252,131,189,252,131,231,252,132, 87,
252,131, 83,252,131,202,252,131,204,252,131,220,254,108, 54,254,
109,107,254,108,213,252, 69, 43,252,132,241,252,132,243,252,133,
22,254,115,202,252,133,100,254,111, 44,252, 69, 93,252, 69, 97,
254,111,177,254,112,210,252, 69,107,252,134, 80,252,134, 92,252,
134,103,252,134,105,252,134,169,252,134,136,252,135, 14,252,134,
226,252,135,121,252,135, 40,252,135,107,252,135,134,252, 69,215,
/* 2f9c0: */ 64, 63,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94,
97,100,103,106,109,112,115,118,121,124,127,130,133,136,139,142,
145,148,151,154,157,160,163,166,169,172,175,178,181,184,187,188,
252,135,225,252,136, 1,252, 69,249,252,136, 96,252,136, 99,254,
118,103,252,136,215,252,136,222,252, 70, 53,252,136,250,252, 52,
187,254,120,174,254,121,102,252, 70,190,252, 70,199,252,138,160,
252,138,237,252,139,138,252,140, 85,254,124,168,252,140,171,252,
140,193,252,141, 27,252,141,119,254,127, 47,254, 8, 4,252,141,
203,252,141,188,252,141,240,254, 8,222,252,142,212,252,143, 56,
254,133,210,254,133,237,252,144,148,252,144,241,252,145, 17,254,
135, 46,252,145, 27,252,146, 56,252,146,215,252,146,216,252,146,
124,252,147,249,252,148, 21,254,139,250,252,149,139,252, 73,149,
252,149,183,254,141,119,252, 73,230,252,150,195,252, 93,178,252,
151, 35,254,145, 69,254,146, 26,252, 74,110,252, 74,118,252,151,
224,254,148, 10,252, 74,178,254,148,150,181,181,
/* 2fa00: */ 64, 29,
1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46,
49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88,
252,152, 41,254,149,182,252,152,226,252, 75, 51,252,153, 41,252,
153,167,252,153,194,252,153,254,252, 75,206,254,155, 48,252,155,
18,252,156, 64,252,156,253,252, 76,206,252, 76,237,252,157,103,
254,160,206,252, 76,248,254,161, 5,254,162, 14,254,162,145,252,
158,187,252, 77, 86,252,158,249,252,158,254,252,159, 5,252,159,
15,252,159, 22,252,159, 59,254,166, 0,
};
static const uint16_t secondlevel[] = {
/* 0000: */ 3843,
1, 173, 352, 520, 547,
747, 0, 0, 0, 933, 1063, 1187, 1285,
1316, 1400, 1470, 1482, 0, 0, 1653, 1748,
1762, 1812, 0, 1874, 1953, 2019, 0, 2043,
2074, 2121, 2129, 2149, 2258, 2293, 2351, 2355,
2435, 2456, 2493, 2497, 2501, 2505, 2550, 2559,
2584, 2588, 2612, 2616, 2656, 2662, 0, 2687,
2729, 2737, 2747, 2755, 2765, 2806, 2912, 3006,
/* 1000: */ 4032,
3010, 0, 3042, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 3046, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3054, 0, 0, 3092,
0, 0, 3108, 0, 3112, 0, 0, 0,
3120, 3126, 3170, 3203, 3235, 3326, 3402, 3408,
3427, 0, 0, 3431, 0, 0, 0, 3502,
3632, 3894, 4168, 4421, 4655, 4901, 5127, 5425,
/* 2000: */ 3520,
5658, 0, 0, 5668, 5729, 0, 5743, 5778,
5795, 5852, 5971, 6061, 6109, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 6119, 0, 0, 0, 0,
0, 0, 0, 6126, 0, 6134, 0, 6138,
/* 3000: */ 192,
6204, 6218, 6370, 6465,
/* a000: */ 1433,
6614, 6642, 6648, 0, 0, 0, 0,
6654, 0, 0, 6697, 6764, 6772, 6776, 6780,
0, 0, 6784, 6810, 0, 0, 0, 6868,
/* f000: */ 1316,
6872, 7122, 7374, 7626,
7882, 8102, 8348, 8592, 8694, 8822, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
8889,
/* 10000: */ 3527,
8923,
0, 0, 0, 8927, 0, 8931, 0, 0,
0, 0, 0, 0, 0, 0, 0, 8943,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
8981, 0, 0, 9040, 0, 0, 0, 0,
0, 0, 0, 0, 9046, 9056, 0, 0,
0, 0, 9068, 9074, 0, 9082, 9106,
/* 11000: */ 3841,
9116, 9179, 0, 9228, 9300, 0, 9304,
9319, 0, 0, 9325, 9331, 9337, 9406, 9441,
0, 9466, 9500, 9518, 0, 0, 9524, 9545,
9549, 0, 9553, 0, 9559, 0, 0, 0,
9563, 0, 0, 0, 9569, 9586, 0, 9590,
9594, 9598, 9602, 0, 0, 0, 0, 0,
9606, 0, 0, 0, 0, 9610, 9619, 0,
0, 0, 0, 0, 0, 9623,
/* 16000: */ 3780,
9629, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 9675, 9687, 0, 0, 0,
0, 0, 0, 0, 0, 9703, 0, 0,
0, 0, 0, 0, 0, 0, 0, 9721,
/* 1b000: */ 50,
9727,
/* 1d000: */ 261,
9731, 9806, 9901,
0, 9907,
/* 1e000: */ 2368,
9915, 0, 9998, 0,10002, 0, 0, 0,
0, 0,10018,10022, 0, 0, 0, 0,
0, 0, 0,10032, 0, 0, 0,10042,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0,10048, 0,10064,
/* 2f000: */ 544,
10080,10332,10588,10842,11096,11352,11608,11866,
12120,
};
static const uint16_t toplevel[] = {
1, 63, 128, 185, 0, 0, 0, 0,
0, 0, 190, 0, 0, 0, 0, 214,
236, 293, 0, 0, 0, 0, 355, 0,
0, 0, 0, 416, 0, 418, 424, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 463,
};
static const uint32_t decomp_map[] = {
0x00000000, 0xe6000000, 0xe8000000, 0xdc000000,
0xd8000000, 0xca000000, 0x01000000, 0xf0000000,
0xe9000000, 0xea000000, 0xde000000, 0xe4000000,
0x0a000000, 0x0b000000, 0x0c000000, 0x0d000000,
0x0e000000, 0x0f000000, 0x10000000, 0x11000000,
0x12000000, 0x13000000, 0x14000000, 0x15000000,
0x16000000, 0x17000000, 0x18000000, 0x19000000,
0x1e000000, 0x1f000000, 0x20000000, 0x1b000000,
0x1c000000, 0x1d000000, 0x21000000, 0x22000000,
0x23000000, 0x24000000, 0x07000000, 0x09000000,
0x54000000, 0x5b000000, 0x67000000, 0x6b000000,
0x76000000, 0x7a000000, 0x81000000, 0x82000000,
0x84000000, 0xd6000000, 0xda000000, 0xe0000000,
0x08000000, 0x1a000000, 0x06000000, 0xe2000000,
0x00000041, 0xe6000300, 0xe6000301, 0xe6000302,
0xe6000303, 0xe6000308, 0xe600030a, 0x00000043,
0xca000327, 0x00000045, 0x00000049, 0x0000004e,
0x0000004f, 0x00000055, 0x00000059, 0x00000061,
0x00000063, 0x00000065, 0x00000069, 0x0000006e,
0x0000006f, 0x00000075, 0x00000079, 0xe6000304,
0xe6000306, 0xca000328, 0xe6000307, 0xe600030c,
0x00000044, 0x00000064, 0x00000047, 0x00000067,
0x00000048, 0x00000068, 0x0000004b, 0x0000006b,
0x0000004c, 0x0000006c, 0xe600030b, 0x00000052,
0x00000072, 0x00000053, 0x00000073, 0x00000054,
0x00000074, 0x00000057, 0x00000077, 0x0000005a,
0x0000007a, 0xd800031b, 0xe600030f, 0xe6000311,
0xdc000326, 0xe6000313, 0x000000a8, 0x00000391,
0x00000395, 0x00000397, 0x00000399, 0x0000039f,
0x000003a5, 0x000003a9, 0x000003b9, 0x000003b1,
0x000003b5, 0x000003b7, 0x000003c5, 0x000003bf,
0x000003c9, 0x00000415, 0x00000418, 0x00000423,
0x00000438, 0x00000435, 0x00000443, 0x00000627,
0xe6000653, 0xe6000654, 0xdc000655, 0x0700093c,
0x070009bc, 0x07000a3c, 0x00000b47, 0x07000b3c,
0x5b000c56, 0x00000cd5, 0x00000cc6, 0x00000dd9,
0x09000dca, 0x00000fb7, 0x81000f71, 0x82000f72,
0x84000f74, 0x82000f80, 0x00001b35, 0xdc000325,
0x00000042, 0x00000062, 0xdc000323, 0xdc000331,
0xdc00032d, 0xdc000330, 0xdc00032e, 0x0000004d,
0x0000006d, 0xdc000324, 0xe6000309, 0xe6000314,
0xe6000342, 0xf0000345, 0x00001fbf, 0x00001ffe,
0x01000338, 0x08003099, 0x0800309a, 0x00009f9c,
0x00006a02, 0x00006717, 0x00005be7, 0x00006bba,
0x00007df4, 0x00006d41, 0x0000618e, 0x000061f2,
0x00008005, 0x0000980b, 0x0e0005b4, 0x110005b7,
0x000005e9, 0x180005c1, 0x190005c2, 0x150005bc,
0x000005d0, 0x120005b8, 0x130005b9, 0x170005bf,
0x070110ba, 0x000113c9, 0x000113c2, 0x000114b9,
0x0001611e, 0x00016129, 0x0001611f, 0x00016d67,
0xd801d165, 0x0001d158, 0xd801d16e, 0xd801d16f,
0xd801d170, 0xd801d171, 0xd801d172, 0x0001d1b9,
0x0001d1ba, 0x0000537f,
};
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: Locale project/LC_COLLATE update: NFD!
2025-06-11 2:56 Locale project/LC_COLLATE update: NFD! Rich Felker
@ 2025-06-11 20:22 ` Rich Felker
0 siblings, 0 replies; 2+ messages in thread
From: Rich Felker @ 2025-06-11 20:22 UTC (permalink / raw)
To: musl
On Tue, Jun 10, 2025 at 10:56:00PM -0400, Rich Felker wrote:
> First milestone in the collation part of the locale project: NFD is
> working.
>
> For some context, in order to be able to apply the Unicode Collation
> Algorithm, it's necessary to be able to normalize the string so that
> items don't order differently depending on the choice of ordering of
> combining marks or whether to use precomposed forms.
>
> The most natural normalized form for applying collation tables is NFD
> (decomposed). So, this is what I've been implementing, as an iterator
> that, given a UTF-8 input string, reads off the NFD character sequence
> one character at a time, in NFD order.
>
> After writing the last steps to actually emit the tables as C arrays
> today, wiring up the Unicode test vectors, and debugging a few small
> issues, the full set of test vectors is passing. They are not actually
> as comprehensive as I'd like; over the next few days I hope to go back
> and add some broad combinatoric tests too.
>
> Code and table size is well under my initial estimates, and not far
> above the best-case ones I made along the way. Currently we're at:
>
> ..text 1089 0
> ..data 0 0
> ..bss 0 0
> ..rodata 14161 0
>
> This covers characters that participate in the transformation spread
> sporadically across the range U+00C0 to U+2FA1D.
>
> The draft tablegen code and runtime code are in a git repo posted at
> https://github.com/richfelker/musl-uca-draft. The runtime code is
> basically in a state ready for integration when there is collation
> code to use it. The tablegen is roughly the same level of polish as
> things in musl-chartable-tools (where I intend for it to eventually
> live) but it also contains a lot of disabled analytical code that I'll
> likely strip out or refactor.
>
> Generated tables are not in git so I'm attaching here in case anyone
> wants to read and appreciate (or the opposite) the pretty-printing
> without actually figuring out how to run anything.
>
> Next steps: further validation & starting on a data format for the
> collation tables themselves.
Further validation continues to pass. The test I've added asserts
that, for each line in UnicodeData.txt,
- If field6 doesn't have a canonical decomposition,
nfd(field1)==field1, i.e. character is unchanged by NFD.
- If field6 does have a canonical decomposition,
nfd(field1)==nfd(field6).
This is not testing anything fancy about reordering, just that the
table generation or application of the table contents did not overlook
any characters that should have mappings, or wrongly get applied to
any that shouldn't.
I think this should give good overall coverage, though. The Unicode
tests were already designed to cover most(/all?) corner cases from the
standpoint of the algorithm, and the ones I've added supplement to
cover anything that might be a corner case for the table
representation.
Rich
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2025-06-11 20:22 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-06-11 2:56 Locale project/LC_COLLATE update: NFD! Rich Felker
2025-06-11 20:22 ` Rich Felker
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).