[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20260821042654.GH23438@brightrain.aerifal.cx>
Date: Fri, 21 Aug 2026 00:26:54 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: Collation data binary format conclusions [was: Re:
Collation weight length frequencies]
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:
>
> > Since there are at most 254 header dictionary entries, there's no
> > reason to make them tightly packed. It's better to just focus on
> > having them efficient to access/process. My leaning is something like
> > (all numeric fields single unsigned bytes):
>
> That means:
>
> > Opening header:
> > - total length for weights at all levels
> > - total length explicitly stored in mapping (not implicit in header),
> > aka offset to next collation element in the mapping
> >
> > For each level:
> > - offset to explicit tail
> > - length of explicit tail
> > - offset to common prefix bytes
> > - length of common prefix bytes
>
> This yields 2+4*nlevels = 14 bytes (nlevels=3) of fixed-size data per
> dictionary entry, plus any prefix bytes.
>
> Because these are variable-length, we need an index of offsets to
> them, and I think the normal multi-level table structure works fine.
> This leaves collation data with the following tables:
>
> - collation mappings table (multi-level itself; indexed by paths of
> base char followed by prefixes then suffixes)
>
> - collation element header byte dictionary (indexed by a single byte)
>
> - parameters/flags (single item with a small number of miscellaneous
> values, so far only whether second level is forward of reverse
> order)
>
> Collation processing will of course look up the roots of these tables
> once (either at the start of the operation, or at locale load time)
> and reuse them for the duration of the operation rather than repeating
> multi-level lookups from the locale root over and over. In particular,
> the header byte dictionary lookup collapses to just reading an offset
> from array[byte-base].
A quick follow-up with empirical results: the above encoding is
working to represent all of the UCA root data with just 27 header
dictionary entries. That leaves well over 200 left that can be used to
shorten the representation of nearly all collation elements with
3-byte primary weights down to 3 bytes total for all 3 weight levels.
Doing this is just a matter of generating the dictionary and can be
done at any later time; it's not blocking progress on the collation
project.
I have code processing the root data into this form, and I'm very
close to done integrating it with the localedef utility. After that
it's on to prototyping the actual runtime collation code
(strcoll/strxfrm).
Rich
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.
