[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20260817030136.GC23438@brightrain.aerifal.cx>
Date: Sun, 16 Aug 2026 23:01:37 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Collation data binary format conclusions [was: Re: Collation
weight length frequencies]
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].
Finally, on handling of outliers not representable with the header
byte dictionary:
> An alternative that'd be a bit less costly to process is replacing the
> null terminations with cumulative lengths l1 l2 l3, where l3 is the
> total length, l3-l2 is the lenth of tertiary weight, l2-l1 the length
> of secondary weight, and l1 is the length of primary. This avoids any
> scanning of data when we just need the lengths.
An equivalent way of thinking of l1, l2, and l3 is the offsets to the
second level weight, tertiary level weight, and start of the next
collation element. This seems natural/reasonable, and I think it how
it should be done.
A similar encoding could be used in the header byte dictionary (right
now some of the length/offset data is redundant assuming sequential
storage), but being that there are only O(1) such entries rather than
O(n) collation mappings to deal with, I think it's best to stick with
the more verbose form that avoids runtime calculation.
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.
