Blog: On Variable-length Integer Encoding: varlenint.py

#!/usr/bin/env python
"""A simplistic implementation of a variable length integer encoding.

You may use this under the MIT license.

Copyright 2012, Eli Carter, elicarter@retracile.net
"""

def encode(value):
    """
    Given a non-negative integer, generates a series of bytes to represent that integer.

    >>> [''.join(encode(x)) for x in [0, 1, 127, 128, 16511, 16512, 536887423, 536887424, 1152921505143734399, 1152921505143734400]]
    ['\\x00', '\\x01', '\\x7f', '\\x80\\x00', '\\xbf\\xff', '\\xc0\\x00\\x00\\x00', '\\xdf\\xff\\xff\\xff', '\\xe0\\x00\\x00\\x00\\x00\\x00\\x00\\x00', '\\xef\\xff\\xff\\xff\\xff\\xff\\xff\\xff', '\\xf0\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00']

    >>> [''.join(encode(x)) for x in [10633823966279326984383377987386491007, 10633823966279326984383377987386491008]]
    ['\\xf7\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff', '\\xf8\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00']

    >>> [''.join(encode(x)) for x in [ 1809251394333065553493296640760748560217977334366913140100908128111029141632 - 1, 1809251394333065553493296640760748560217977334366913140100908128111029141632L]]
    ['\\xfb\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff', '\\xfc\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00']

    >>> ''.join(encode(7396775681604997398540087132721699209696373596889225166045458700757901414230626882903412188306330901418011007901435398748959249683492489874669224331615055035544786995079268514652297458737865930205396493160415855776243336176136723975030081406816750443400950436104500971119898046464782518449604583539717953229900145646629339958925549845621758660941510790875516954546587916051406217908251209628711686515792632633909655899414132078928000611892934325015631201815867480070695894135094945655998593524416919190375786098465291447627498157472974777300687495925075963062491282836308983496241330663804761707124583167455936640))
    '\\xff\\x0f\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'

    >>> ''.join(encode(239041644610554315191288614818563319987479610225078685085502658832692087090657987254827914108657278062642694102731154519192712426342573610060860310634925524432210611696710967637717038757564632792914139559598376364069286843734217699967727970354748523902162454690354241349323436448696581065628351848662878953556886057330731457354791022535002351516627377342107422478414923807462850574334503143550311784750481161472768742290856456245688644581866120751837877296491022037279148192216894607925533420799172688660328087612216881426681445742903936577725545921399708073727072032097196704916228859042132137648604356649519641958026644370663634816291336592368528490943593737711930160382236015013019653102224216204128846301715294650633485757528533605880571918827163866837850190855901971408154992175466931495525659590193072901126776331086490456463995908061313844382605900603243864920480892835357556214359212821037311465625494318109209339103335547862868955010759361454566198434762092547477541659437517799877059260551613449691516389358305189743079627781783843060554523343420853114288907412579953622366074986959791259105040579720843550786027372699096009323983430971052993921944453975478516283138865926949802626207616973865421187786361675500765593728))
    '\\xff\\x8f\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'
    """
    assert value >= 0 # unsigned values only
    leading_ones = -1 # Number of leading one bits
    overflow_value = 0 # smallest value that is too large for the current representation
    # smaller_overflow_value # smallest value that is too large for the
    # representation one size smaller
    while value >= overflow_value:
        smaller_overflow_value = overflow_value
        leading_ones += 1
        num_bytes = 2**leading_ones
        # There are N leading ones, plus a 0 bit to denote the end of the
        # leading ones.
        numeric_representation_bits = 8 * num_bytes - (leading_ones + 1)
        overflow_value += 1 << numeric_representation_bits
    #print "Representing %s requires %s bytes" % (value, num_bytes) # DEBUG
    for n in range(leading_ones // 8):
        yield '\xff'
    mixed_byte = (~ ((1 << (8 - leading_ones % 8)) - 1)) & 0xff
    number_to_encode = value - smaller_overflow_value
    yield chr(mixed_byte | (number_to_encode >> (8 * (num_bytes - leading_ones // 8 - 1))) & 0xff)
    for byte_offset in range(num_bytes - (leading_ones // 8) - 1 - 1, -1, -1):
        yield chr((number_to_encode >> (8*byte_offset)) & 0xff)


def decode(stream):
    """
    Given a byte stream, reads a single variable-length integer and returns its value.

    >>> import StringIO
    >>> [decode(StringIO.StringIO(s)) for s in ['\\x00', '\\x01', '\\x7f', '\\x80\\x00', '\\xbf\\xff', '\\xc0\\x00\\x00\\x00', '\\xdf\\xff\\xff\\xff', '\\xe0\\x00\\x00\\x00\\x00\\x00\\x00\\x00', '\\xef\\xff\\xff\\xff\\xff\\xff\\xff\\xff', '\\xf0\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00']]
    [0, 1, 127, 128, 16511, 16512, 536887423, 536887424, 1152921505143734399, 1152921505143734400]

    >>> [decode(StringIO.StringIO(s)) for s in ['\\xf7\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff', '\\xf8\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00']]
    [10633823966279326984383377987386491007L, 10633823966279326984383377987386491008L]

    >>> [decode(StringIO.StringIO(s)) for s in ['\\xfb\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xff', '\\xfc\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00']]
    [1809251394333065553493296640760748560217977334366913140100908128111029141631L, 1809251394333065553493296640760748560217977334366913140100908128111029141632L]

    >>> decode(StringIO.StringIO('\\xff\\x0f' + '\\x00'*(256-2)))
    7396775681604997398540087132721699209696373596889225166045458700757901414230626882903412188306330901418011007901435398748959249683492489874669224331615055035544786995079268514652297458737865930205396493160415855776243336176136723975030081406816750443400950436104500971119898046464782518449604583539717953229900145646629339958925549845621758660941510790875516954546587916051406217908251209628711686515792632633909655899414132078928000611892934325015631201815867480070695894135094945655998593524416919190375786098465291447627498157472974777300687495925075963062491282836308983496241330663804761707124583167455936640L

    >>> decode(StringIO.StringIO('\\xff\\x8f' + '\\x00'*(512-2)))
    239041644610554315191288614818563319987479610225078685085502658832692087090657987254827914108657278062642694102731154519192712426342573610060860310634925524432210611696710967637717038757564632792914139559598376364069286843734217699967727970354748523902162454690354241349323436448696581065628351848662878953556886057330731457354791022535002351516627377342107422478414923807462850574334503143550311784750481161472768742290856456245688644581866120751837877296491022037279148192216894607925533420799172688660328087612216881426681445742903936577725545921399708073727072032097196704916228859042132137648604356649519641958026644370663634816291336592368528490943593737711930160382236015013019653102224216204128846301715294650633485757528533605880571918827163866837850190855901971408154992175466931495525659590193072901126776331086490456463995908061313844382605900603243864920480892835357556214359212821037311465625494318109209339103335547862868955010759361454566198434762092547477541659437517799877059260551613449691516389358305189743079627781783843060554523343420853114288907412579953622366074986959791259105040579720843550786027372699096009323983430971052993921944453975478516283138865926949802626207616973865421187786361675500765593728L
    """
    leading_ones = 0
    b = stream.read(1)
    while b == '\xff':
        leading_ones += 8
        b = stream.read(1)
    n = 7
    while ord(b) & (1<<n):
        n -= 1
    leading_ones += 7 - n
    value = ord(b) & ((1<<n)-1)
    remaining_bytes = (1<<leading_ones) - leading_ones // 8 - 1
    for i in xrange(remaining_bytes):
        value = value << 8 | ord(stream.read(1))
    for i in range(leading_ones):
        numeric_representation_bits = 8 * (1<<i) - (i+1)
        value += 1 << numeric_representation_bits
    return value


if __name__ == '__main__':
    import doctest
    doctest.testmod()