[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <24bf8aa5d99b38064f796161b4e7f4bb1e24bd0b.camel@postmarketos.org>
Date: Fri, 21 Aug 2026 19:03:43 +0200
From: Pablo Correa Gomez <pabloyoyoista@...tmarketos.org>
To: Rich Felker <dalias@...c.org>, musl@...ts.openwall.com
Subject: Re: Collation data binary format conclusions [was: Re:
Collation weight length frequencies]
El Fri, 21-08-2026 a las 12:57 -0400, Rich Felker escribió:
> On Fri, Aug 21, 2026 at 12:26:54AM -0400, Rich Felker wrote:
> > 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).
>
> Collation data parsing and encoding is now pushed to the draft tooling
> repo:
>
> https://codeberg.org/dalias/musl-locale-tools-
> draft/src/commit/39d8b47e81b9ca16ba13cd91f38d2d5616652bfe
Thank you so much, so happy to see this moving forward.
Best,
Pablo
>
> This is not yet wired up to localedef or to the binary table builder,
> but produces a sorted-by-codepoint-sequence version of the collation
> mappings on stdout with the original standard fractional UCA syntax
> and the binary encoding that goes into the locale file parenthesized
> after each element.
>
> I'm including here an exerpt of the output for the root data (ascii
> punctuation digits and letters, combining marks, unicode spaces and
> dashes) demonstrating how the output encoding, including sufficient
> information to efficiently delimit the weight levels, is generally the
> same size or smaller than just the concatenaed/undelimited weight
> bytes:
>
> 0020 ; [ 04, 05, 05](06 04 )
> 0021 ; [ 07 5a, 05, 05](0e 07 5a )
> 0022 ; [ 09 78, 05, 05](0e 09 78 )
> 0023 ; [ 0a 94, 05, 05](0e 0a 94 )
> 0024 ; [ 0d 83, 05, 05](0e 0d 83 )
> 0025 ; [ 0a 96, 05, 05](0e 0a 96 )
> 0026 ; [ 0a 90, 05, 05](0e 0a 90 )
> 0027 ; [ 09 6a, 05, 05](0e 09 6a )
> 0028 ; [ 09 8e, 05, 05](0e 09 8e )
> 0029 ; [ 09 90, 05, 05](0e 09 90 )
> 002a ; [ 0a 80, 05, 05](0e 0a 80 )
> 002b ; [ 0c 79, 05, 05](0e 0c 79 )
> 002c ; [ 06, 05, 05](06 06 )
> 002d ; [ 05 0e, 05, 05](0e 05 0e )
> 002e ; [ 08, 05, 05](06 08 )
> 002f ; [ 0a 8a, 05, 05](0e 0a 8a )
> 0030 ; [ 13, 05, 05](06 13 )
> 0031 ; [ 15, 05, 05](06 15 )
> 0032 ; [ 17, 05, 05](06 17 )
> 0033 ; [ 19, 05, 05](06 19 )
> 0034 ; [ 1b, 05, 05](06 1b )
> 0035 ; [ 1d, 05, 05](06 1d )
> 0036 ; [ 1f, 05, 05](06 1f )
> 0037 ; [ 21, 05, 05](06 21 )
> 0038 ; [ 23, 05, 05](06 23 )
> 0039 ; [ 25, 05, 05](06 25 )
> 003a ; [ 07 36, 05, 05](0e 07 36 )
> 003b ; [ 07 2a, 05, 05](0e 07 2a )
> 003c ; [ 0c 81, 05, 05](0e 0c 81 )
> 003d ; [ 0c 83, 05, 05](0e 0c 83 )
> 003e ; [ 0c 85, 05, 05](0e 0c 85 )
> 003f ; [ 07 62, 05, 05](0e 07 62 )
> 0040 ; [ 0a 7e, 05, 05](0e 0a 7e )
> 0041 ; [ 2a, 05, 9c](0c 2a 9c )
> 0042 ; [ 2c, 05, 9c](0c 2c 9c )
> 0043 ; [ 2e, 05, 9c](0c 2e 9c )
> ...
> 005f ; [ 05 0a, 05, 05](0e 05 0a )
> 0060 ; [ 0c 04, 05, 05](0e 0c 04 )
> 0061 ; [ 2a, 05, 05](06 2a )
> 0062 ; [ 2c, 05, 05](06 2c )
> 0063 ; [ 2e, 05, 05](06 2e )
> ...
> 007a ; [ 5c, 05, 05](06 5c )
> 007b ; [ 09 96, 05, 05](0e 09 96 )
> 007c ; [ 0c 89, 05, 05](0e 0c 89 )
> 007d ; [ 09 98, 05, 05](0e 09 98 )
> 007e ; [ 0c 8d, 05, 05](0e 0c 8d )
> ...
> 02ff ; [ 0c 38 79, 05, 05](16 0c 38 79 )
> 0300 ; [, 8a, 05](03 8a )
> 0301 ; [, 88, 05](03 88 )
> 0302 ; [, 8e, 05](03 8e )
> 0303 ; [, 9a, 05](03 9a )
> ...
> 2002 ; [ 04, 05, 18](0c 04 18 )
> 2003 ; [ 04, 05, 18](0c 04 18 )
> 2004 ; [ 04, 05, 18](0c 04 18 )
> 2005 ; [ 04, 05, 18](0c 04 18 )
> 2006 ; [ 04, 05, 18](0c 04 18 )
> 2007 ; [ 04, 05, 28](0c 04 28 )
> 2008 ; [ 04, 05, 18](0c 04 18 )
> ...
> 2010 ; [ 05 14, 05, 05](0e 05 14 )
> 2011 ; [ 05 14, 05, 20](10 05 14 )
> 2012 ; [ 05 16, 05, 05](0e 05 16 )
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.
