<div dir="ltr"><div>Google Protocol Buffers use something similar, which they call "<a class="gmail-devsite-back-to-top-link gmail-material-icons" href="https://developers.google.com/protocol-buffers/docs/encoding#top_of_page"></a>Base 128 Varints"</div><div><br></div><div>    <a href="https://developers.google.com/protocol-buffers/docs/encoding#varints">https://developers.google.com/protocol-buffers/docs/encoding#varints</a></div><div><br></div><div>I prefer the way this handles negative numbers.</div><div><br></div><div>- Andrew<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On 10 July 2018 at 02:53, MRAB <span dir="ltr"><<a href="mailto:python@mrabarnett.plus.com" target="_blank">python@mrabarnett.plus.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">In the regex module I use an encoding scheme when pickling pattern objects which is based on the way MIDI encodes variable-length integers, and I think it might have a use in a pickle protocol.<br>
<br>
In the basic format, an integer is split up into 7-bit chunks, each chunk put into a byte, and the most-significant bit of the byte used to signal whether the value continues into the following byte.<br>
<br>
And integer must be encoded into the minimum number of bytes, so an encoded sequence of bytes would never start with 0x80.<br>
<br>
MIDI deviates from the basic idea in order to reduce the number of bytes, so as sequence of bytes in MIDI _can_ start with x080; this is fine for MIDI because it doesn't need to represent negative integers.<br>
<br>
The format I'm suggesting uses an initial 0x80 as a way of letting it encode negative integers.<br>
<br>
Here are a couple of Python functions that summarise the encoding and decoding (minus obvious optimisations for simplicity):<br>
<br>
<br>
def encode_varint(value: int) -> List[int]:<br>
    negative = value < 0<br>
    encoded = []<br>
<br>
    if negative:<br>
        final = -1<br>
    else:<br>
        final = 0<br>
<br>
    while True:<br>
        encoded.append(0x80 | (value & 0x7F))<br>
        value >>= 7<br>
<br>
        if value == final:<br>
            break<br>
<br>
    if negative:<br>
        encoded.append(0x80)<br>
<br>
    encoded.reverse()<br>
<br>
    encoded[-1] &= 0x7F<br>
<br>
    return encoded<br>
<br>
<br>
def decode_varint(encoded: Iterable[int]) -> int:<br>
    byte = next(encoded)<br>
<br>
    if byte == 0x80:<br>
        value = -1<br>
        byte = next(encoded)<br>
    else:<br>
        value = 0<br>
<br>
    value = (value << 7) | (byte & 0x7F)<br>
<br>
    while (byte & 0x80) != 0:<br>
        byte = next(encoded)<br>
        value = (value << 7) | (byte & 0x7F)<br>
<br>
    return value<br>
<br>
<br>
The advantage of encoding integers in this way is that there's no limit to their size, so there's no need to add a new protocol to support larger counts.<br>
<br>
They can also make pickles smaller.<br>
<br>
Example:<br>
<br>
    # Pickle (None, )<br>
    0: \x80 PROTO      4<br>
    2: \x95 FRAME      4<br>
   11: N    NONE<br>
   12: \x85 TUPLE1<br>
   13: \x94 MEMOIZE    (as 0)<br>
   14: .    STOP<br>
<br>
Here, FRAME takes an argument of 8 bytes. If you replaced FRAME with a version that accepted a variable-length count, you could reduce that argument to 1 byte.<br>
<br>
You also wouldn't need to have different fixed-length versions of an opcode, e.g. BINUNICODE and SHORT_BINUNICODE.<br>
<br>
Whether you do anything with this is entirely up to the core devs, I just thought someone might find it useful.<br>
______________________________<wbr>_________________<br>
Python-Dev mailing list<br>
<a href="mailto:Python-Dev@python.org" target="_blank">Python-Dev@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/python-dev" target="_blank" rel="noreferrer">https://mail.python.org/mailma<wbr>n/listinfo/python-dev</a><br>
Unsubscribe: <a href="https://mail.python.org/mailman/options/python-dev/lists%40andros.org.uk" target="_blank" rel="noreferrer">https://mail.python.org/mailma<wbr>n/options/python-dev/lists%<wbr>40andros.org.uk</a><br>
</blockquote></div><br></div>