[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Monotone-devel] Revision numbering height compaction
From: |
Paul Crowley |
Subject: |
[Monotone-devel] Revision numbering height compaction |
Date: |
Wed, 14 Feb 2007 22:57:53 +0000 |
User-agent: |
Icedove 1.5.0.9 (X11/20061220) |
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/
- [Monotone-devel] Revision numbering height compaction,
Paul Crowley <=