[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20260826224942.GP23438@brightrain.aerifal.cx>
Date: Wed, 26 Aug 2026 18:49:43 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: Collation data binary format conclusions
On Sun, Aug 16, 2026 at 11:01:37PM -0400, Rich Felker wrote:
> Some follow-ups on this, to go with implementation of the generating
> code I'm working on now:
>
> On Thu, Jun 18, 2026 at 05:52:56PM -0400, Rich Felker wrote:
> > On Sat, May 23, 2026 at 05:02:18PM -0400, Rich Felker wrote:
> > > However, what it also suggests is maybe having a data-defined
> > > dictionary of header byte values. which would avoid locking in any
> > > assumptions about the FractionalUCA.txt implementation of root data
> > > and instead allow any assignment (e.g. not even necessarily
> > > variable-length/fractional) of weights as non-null byte sequences
> > > compatible with strxfrm.
> > >
> > > From an immediate practical standpoint, this would facilitate eliding
> > > not just one common secondary/tertiary byte value (05), but basically
> > > all of the common secondary/tertiary weight bytes. So that, instead of
> > > most entries in the table being one of (4-6 bytes):
> > >
> > > - hh pp pp pp ss tt
> > > - hh pp pp ss tt
> > > - hh pp ss tt
> > >
> > > most would be (2-4 bytes):
> > >
> > > - hh pp pp pp
> > > - hh pp pp
> > > - hh pp
> > >
> > > We could probably take this even further and let header byte represent
> > > a lead primary byte too. This would drop the 87k ideographic collation
> > > elements from 4 bytes each to 3 bytes each.
> >
> > I don't really see a lot of advantage in special-casing
> >
> > "header dictionary defines the weights for a given level entirely
> > or just defines the length in bytes and the weight bytes
> > themselves are in the rules"
> >
> > versus just doing:
> >
> > "header dictionary defines the total length and a shared prefix of
> > the weight bytes".
>
> I'm going with the latter, more general form. There were no reasons
> not to and it just makes more sense. And, the variant that doesn't
> require scanning for terminators:
Some small addenda that came up during implementation:
The format so far just covered the header dictionary and collation
elements themselves. There are a couple more things needed outside
that:
1. Number of weight levels. Normally this is 3, and I think that's
generally fine for anything built on the UCA root data. However
there's no good reason to hard-code it in the data representation.
The header dictionary entry and direct-coded collation element
formats specified work as-is with the number of weight levels being
an arbitrary parameter (below some ridiculous level where
single-byte offsets and counts no longer work), so let's put that
parameter in a global field in the collation hierarchy of the
locale file.
2. Forward/reverse direction flag for each weight level. In practice
only level 2 needs to be reversible, but any non-initial level is
just as easy as level 2, so allow it. Supporting reversal of the
very first level requires special-casing and an extra pass, so it's
probably not worth doing. It doesn't make sense, and if you really
wanted to make a locale that works that way, you could make a dummy
initial level where all collation elements are full-ignoreable. So,
we need one global key whose contents are an array of direction
flags for each level.
3. Delimiting multiple collation elements in a one-to-many or
many-to-many mapping. Since mapping to multiple CEs is generally
rare, encoding space should not be spent optimizing for the
multi-CE case. The most reasonable choices seem to be a single
reserved lead byte to indicate multi-CE sequence, either followed
by a count byte then the sequence of CEs, or just the sequence of
CEs "null terminated" by a full-ignoreable CE. Null termination
turns out to be a bad choice in that it requires decoding the
header byte at the CE-iteration layer to determine if the CE is
"null", so it turns out an explicit count is a better choice.
Specifics of encoding. First, the multilevel table tree keys:
/3/0: count of weight levels and array of per-weight-level flags
/3/1: collation mappings table [added lead byte for multi-CEs]
/3/2: header dictionary table [no changes]
Contents of /3/0:
First byte is number of levels; we can say values above 10 (way more
than ever needed) are invalid. After that, an array consisting of one
flags byte per level. The only bit defined at this point is bit 0 for
direction (0=forward, 1=reverse). Reverse is invalid for first level.
Special lead bytes in mappings in /3/1:
0x00 - cannot appear [collision with subtable]
0xfd - direct-coded CE (not using header dict)
0xfe - multi-CE sequence follows
0xff - cannot appear [collision with subtable]
Form of multi-CE maps with lead byte 0xfe:
Immediately following byte is a count of CEs present in the mapping.
The sequence of CEs follows with no further delimiting.
Contents of /3/2: Header dictionary is itself a (sub)table, mapping
byte values 0x01-0xfc (any lead byte that is not special) to the
format described before.
Extensibility considerations:
Any extension to collation capability, if used in a locale's data,
would inherently give a mismatching collation order with a version of
the implementation incapable of interpreting the new data. So in
general, this should be avoided. If there is a need to extend
collation functionality at some point, however, there are two ways in
which it can be done. Neither of these requires version labeling now;
both rely on the multi-level table data structure:
1. In the case where a meaningful but imperfect collation order can be
had with old versions of the implementation by ignoring the
unsupported extensions, these extensions can be expressed alongside
the existing data structure, in previously-unused flag bits, an
extended header dictionary in a new key alongside the existing basic
header dictionary at /3/2, or some other new key.
2. In the case where the new extended data cannot be meaningfully
processed with old implementations, it may be placed in completely new
keys (e.g. a new collation mappings table in /3/3). In this case, the
old keys could be left undefined (causing old versions of the
implementation not to use the locale for collation at all), or an
entire parallel collation table in the old form could be placed in the
locale file alongside the new one, with a suitable approximation for
old versions of the implementation to use.
Neither of these is something we should set out planning to do, and no
extensions should be made merely for the sake of optimizing
representation for size or performance. The above should only be
considered if/when there is a legitimate need for new capabilities to
correctly represent an important part of the expected collation
ordering for a locale where Unicode has defined these new
capabilities.
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.
