[Monotone-devel] Revision numbering height compaction

[Paul Crowley]

I had such a fine time at the summit - great to see you all!

Either there's a problem with the height compaction proposal on the wiki 
as it currently stands, or I don't understand it.  As far as I can tell

2^14 -1 encodes to FF 7F, while
2^14 encodes to 81 80 00

which as far as I can tell breaks the sort order property.

If I'm right, I can propose an alternative - encode the length of i in 
7-bit blocks as a sequence of 1 bits, followed by a zero, followed by i. 
   You can slightly improve this in various ways to improve compaction. 
 So the sequences go, in order:

00 ... 7F
80 00 .. BF FF
C0 00 00 .. DF FF FF
E0 00 00 00 .. EF FF FF FF
F0 00 00 00 00 .. F7 FF FF FF FF
F8 00 00 00 00 00 .. FB FF FF FF FF FF
FC 00 00 00 00 00 00 .. FD FF FF FF FF FF FF
FE 00 00 00 00 00 00 00 .. FE FF FF FF FF FF FF FF
FF 00 00 00 00 00 00 00 00 .. FF 7F FF FF FF FF FF FF FF
FF 80 00 00 00 00 00 00 00 00 .. FF BF FF FF FF FF FF FF FF
FF C0 00 00 00 00 00 00 00 00 00 .. FF DF FF FF FF FF FF FF FF FF

and that handles all integers up to 2^64 - in fact up to 2^70 and beyond.

I can write some Python to express this if I'm not making sense.  Cheers!
--
  __
\/ o\ Paul Crowley, address@hidden
/\__/ http://www.ciphergoth.org/