I first wrote something like this back in 2001 when I needed it in FriBidi:
https://github.com/fribidi/fribidi/blob/master/gen.tab/packtab.c
In 2019 I wanted to use that to produce more compact Unicode data tables for HarfBuzz, but for convenience I wanted to use it from Python. While I considered wrapping the C code in a module, it occurred to me that I can rewrite it in pure Python in a much cleaner way. That code remains a stain on my resume in terms of readability (or lack thereof!). :D
This Python version builds on the same ideas, but is different from the C version in two major ways:
-
Whereas the C version uses backtracking to find best split opportunities, I found that the same can be achieved using dynamic-programming. So the Python version implements the DP approach, which is much faster.
-
The C version does not try packing multiple items into a single byte. The Python version does. Ie. if items fit, they might get packed into 1, 2, or 4 bits per item.
There's also a bunch of other optimizations, which make (eventually, when complete) the Python version more generic and usable for a wider variety of data tables.
- Reduce code duplication between Inner/Outer genCode().
- Handle empty data array.
- Bake in width multiplier into array data if doing so doesn't enlarge data type. Again, that would save ops.
- If an array is not larger than 64 bits, inline it in code directly as one integer.
- Currently we only cull array of defaults at the end. Do it at beginning as well, and adjust split code to find optimum shift.
- Byte reuse! Much bigger work item.