[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20260830191405.GS23438@brightrain.aerifal.cx>
Date: Sun, 30 Aug 2026 15:14:05 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: Results of analysis of requirements for collation data
representation
On Sat, May 23, 2026 at 08:27:59PM -0400, Rich Felker wrote:
> For ideographic implicit weights, the data model should pin down the
> particular assignment of weights. This is because the FractionalUCA
> root data contains rules which define an explicit mapping in terms of
> a potentially-implicit ideographic codepoint. If the implicit
> assignment is left as a runtime implementation detail, the definitions
> would not necessarily align at runtime.
>
> None of this particularly informs or constains the high-level or
> implementation details of the data model we use. It's just a
> consideration that requires some representation before this is over.
I'm revisiting this as part of actually writing the code.
Assignment of implicit weights should leave gaps in the last byte so
that it's possible (even if this is in practice not meaningful) for
tailorings to order other characters between implicit-weight
characters. A quick explainer on what this means:
Suppose elements A and B have consecutive weights ending in 01 and 02.
There is no way to insert another element in the order between them.
But if they instead end in 01 and 03, you can insert up to 255
elements of the form 02 xx between them, or up to 65025 elements of
the form 02 xx xx, etc.
This in general is the principle the "fractional UCA" approach to
collation weights takes.
Since we have to avoid the 0 byte, and presumably don't want division
in the collation inner loops, these two constraints together give 6
data bits for the last byte of implicit collation elements: high bit
always 1 to avoid an all-zeros byte, low bit constant to reserve a
fractional slot above and below each. (In the case of 0x80, we have a
lot more than just 1 slot below it, all of 0x01..0x7f.)
Subsequent bytes can have 7 bits of data per byte (high bit always
set, all low 7 bits used) since they *all* are "fraactional".
Since the Core Han Unified Ideographs are in the BMP (16 bits total)
this leaves 3 bits to put in a third data byte. There are 50 lead
bytes reserved in the default root data, so that's plenty to afford
taking 8 to make each CE fit in 3 bytes, if we want to.
The rest of the ideographic characters that can use implicit maps are
currently 18-bit. I think that makes enough lead bytes still to put
them all in 3-byte range, but it's not terribly future-proof against
wacky future assignments Unicode might make, and as explained in the
quoted text above, the mapping we use here should be stable. So it
might be better to use a single lead byte for all of them.
One consideration is that we also need to use this range of lead bytes
to represent collation weights for radical-stroke order. Implicit
weights should not be used if radical-stroke order is in use, but in
practice they may come up whenever the collation data is not
up-to-date with latest Unicode, in which case there will be unmapped
ideographic codepoints that will end up getting implicit weights if
they appear. In this case however, the implicit assignments are fine
being dynamic; they don't have to be stable since they have no order
relation with anything in the collation data.
In radical-stroke order, there are some >80k characters to map, which
presently puts us at 17 bits. with 13 bits in the low 2 bytes, that
requires 4 bits (actually fewer than 16 values for now, but call it
16) of the 50 lead bytes available to fit everything in 3 bytes.
Conclusions:
If using radical-stroke order, weight values are assigned at localedef
time and, as explained above, there is no need for stable assignments
for any additional weights. So all of this is just implementation
details.
At localedef time we can just optimally pack the weights into the lead
byte values which the root data being parsed says are reserved for
ideographic scripts. This is a minor addition I need to make to the
current WIP code.
If using legacy implicit weights, they do need to be stable, but the
space of values is huge.
Placing the Core Han Unified Ideographs with 3-byte even weights
starting at the beginning of the ideographic lead byte range:
7E 80 80
7E 80 82
7E 80 84
...
This isn't quite accurate, because it's actually a mapping of bits,
and the first character in this class is U+4E00, which has low 6 bits
0, next 7 bits 0x38, high bits 0x02. So its implicit weight is:
80 B8 80
The lower 7E and 7F range is just reserved in case (I'm not sure if
Unicode stability allows this) additional characters with lower
codepoint numbers are added to it.
The other block ("All other Han Unified Ideographs") needs to be
mapped to sort after the above. Using a base 8 above the initial lead
byte base (7E+8=86) ensures there's no overlap, and puts the first
character U+3400 at:
87 D0 80
This mapping is parameterized on the range of available lead bytes for
ideographic implicit weight use, which is part of the root data. As
long as the range has length at least 40, it works.
If the range is smaller than 40 but at least 9, the core ideographs
can be mapped efficiently and a single lead byte can be used for all
of the extended ones, as in (just prefixing the single available
byte):
86 87 D0 80
for U+3400.
If the range is smaller than 9 both can be prefixed under the same
prefix byte (in this example, 7E):
U+4E00 = 7E 80 B8 80
U+3400 = 7E 87 D0 80
The compiled locale needs to indicate at least, for each of these two
blocks as well as for unassigned implicit weights (any unicode scalar
value that's not in ideographic ranges):
1. A code indicating the mapping rules described here
2. Any fixed prefix byte(s) (needed as above if range is too small)
3. Base lead byte value
It's not needed to know explicitly the number of lead byte values
available, as the size of the range to be mapped and the mapping code
determine a mapping which fits. For example (excluding any fixed
prefix bytes(s)):
- Core ideographic with the mapping desscribed here is always 3 bytes:
6 bits in low, 7 in mid, 3 bits in high part added to base lead byte
value.
- Extended ideographic with the mapping desscribed here is always 3
bytes: 6 bits in low, 7 in mid, 3 bits in high part added to base
lead byte value.
Unassigned works similar but does not have any real need for stability
so it's not important to detail here.
I'll amend the data format with an item for handling implicit weight
mappings.
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
