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

File varlenint.py, 12.7 KB (added by retracile, 13 years ago)

Simple implementation of a variable length integer encoding

Line 
1#!/usr/bin/env python
2"""A simplistic implementation of a variable length integer encoding.
3
4You may use this under the MIT license.
5
6Copyright 2012, Eli Carter, elicarter@retracile.net
7"""
8
9def encode(value):
10    """
11    Given a non-negative integer, generates a series of bytes to represent that integer.
12
13    >>> [''.join(encode(x)) for x in [0, 1, 127, 128, 16511, 16512, 536887423, 536887424, 1152921505143734399, 1152921505143734400]]
14    ['\\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']
15
16    >>> [''.join(encode(x)) for x in [10633823966279326984383377987386491007, 10633823966279326984383377987386491008]]
17    ['\\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']
18
19    >>> [''.join(encode(x)) for x in [ 1809251394333065553493296640760748560217977334366913140100908128111029141632 - 1, 1809251394333065553493296640760748560217977334366913140100908128111029141632L]]
20    ['\\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']
21
22    >>> ''.join(encode(7396775681604997398540087132721699209696373596889225166045458700757901414230626882903412188306330901418011007901435398748959249683492489874669224331615055035544786995079268514652297458737865930205396493160415855776243336176136723975030081406816750443400950436104500971119898046464782518449604583539717953229900145646629339958925549845621758660941510790875516954546587916051406217908251209628711686515792632633909655899414132078928000611892934325015631201815867480070695894135094945655998593524416919190375786098465291447627498157472974777300687495925075963062491282836308983496241330663804761707124583167455936640))
23    '\\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'
24
25    >>> ''.join(encode(239041644610554315191288614818563319987479610225078685085502658832692087090657987254827914108657278062642694102731154519192712426342573610060860310634925524432210611696710967637717038757564632792914139559598376364069286843734217699967727970354748523902162454690354241349323436448696581065628351848662878953556886057330731457354791022535002351516627377342107422478414923807462850574334503143550311784750481161472768742290856456245688644581866120751837877296491022037279148192216894607925533420799172688660328087612216881426681445742903936577725545921399708073727072032097196704916228859042132137648604356649519641958026644370663634816291336592368528490943593737711930160382236015013019653102224216204128846301715294650633485757528533605880571918827163866837850190855901971408154992175466931495525659590193072901126776331086490456463995908061313844382605900603243864920480892835357556214359212821037311465625494318109209339103335547862868955010759361454566198434762092547477541659437517799877059260551613449691516389358305189743079627781783843060554523343420853114288907412579953622366074986959791259105040579720843550786027372699096009323983430971052993921944453975478516283138865926949802626207616973865421187786361675500765593728))
26    '\\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'
27    """
28    assert value >= 0 # unsigned values only
29    leading_ones = -1 # Number of leading one bits
30    overflow_value = 0 # smallest value that is too large for the current representation
31    # smaller_overflow_value # smallest value that is too large for the
32    # representation one size smaller
33    while value >= overflow_value:
34        smaller_overflow_value = overflow_value
35        leading_ones += 1
36        num_bytes = 2**leading_ones
37        # There are N leading ones, plus a 0 bit to denote the end of the
38        # leading ones.
39        numeric_representation_bits = 8 * num_bytes - (leading_ones + 1)
40        overflow_value += 1 << numeric_representation_bits
41    #print "Representing %s requires %s bytes" % (value, num_bytes) # DEBUG
42    for n in range(leading_ones // 8):
43        yield '\xff'
44    mixed_byte = (~ ((1 << (8 - leading_ones % 8)) - 1)) & 0xff
45    number_to_encode = value - smaller_overflow_value
46    yield chr(mixed_byte | (number_to_encode >> (8 * (num_bytes - leading_ones // 8 - 1))) & 0xff)
47    for byte_offset in range(num_bytes - (leading_ones // 8) - 1 - 1, -1, -1):
48        yield chr((number_to_encode >> (8*byte_offset)) & 0xff)
49
50
51def decode(stream):
52    """
53    Given a byte stream, reads a single variable-length integer and returns its value.
54
55    >>> import StringIO
56    >>> [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']]
57    [0, 1, 127, 128, 16511, 16512, 536887423, 536887424, 1152921505143734399, 1152921505143734400]
58
59    >>> [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']]
60    [10633823966279326984383377987386491007L, 10633823966279326984383377987386491008L]
61
62    >>> [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']]
63    [1809251394333065553493296640760748560217977334366913140100908128111029141631L, 1809251394333065553493296640760748560217977334366913140100908128111029141632L]
64
65    >>> decode(StringIO.StringIO('\\xff\\x0f' + '\\x00'*(256-2)))
66    7396775681604997398540087132721699209696373596889225166045458700757901414230626882903412188306330901418011007901435398748959249683492489874669224331615055035544786995079268514652297458737865930205396493160415855776243336176136723975030081406816750443400950436104500971119898046464782518449604583539717953229900145646629339958925549845621758660941510790875516954546587916051406217908251209628711686515792632633909655899414132078928000611892934325015631201815867480070695894135094945655998593524416919190375786098465291447627498157472974777300687495925075963062491282836308983496241330663804761707124583167455936640L
67
68    >>> decode(StringIO.StringIO('\\xff\\x8f' + '\\x00'*(512-2)))
69    239041644610554315191288614818563319987479610225078685085502658832692087090657987254827914108657278062642694102731154519192712426342573610060860310634925524432210611696710967637717038757564632792914139559598376364069286843734217699967727970354748523902162454690354241349323436448696581065628351848662878953556886057330731457354791022535002351516627377342107422478414923807462850574334503143550311784750481161472768742290856456245688644581866120751837877296491022037279148192216894607925533420799172688660328087612216881426681445742903936577725545921399708073727072032097196704916228859042132137648604356649519641958026644370663634816291336592368528490943593737711930160382236015013019653102224216204128846301715294650633485757528533605880571918827163866837850190855901971408154992175466931495525659590193072901126776331086490456463995908061313844382605900603243864920480892835357556214359212821037311465625494318109209339103335547862868955010759361454566198434762092547477541659437517799877059260551613449691516389358305189743079627781783843060554523343420853114288907412579953622366074986959791259105040579720843550786027372699096009323983430971052993921944453975478516283138865926949802626207616973865421187786361675500765593728L
70    """
71    leading_ones = 0
72    b = stream.read(1)
73    while b == '\xff':
74        leading_ones += 8
75        b = stream.read(1)
76    n = 7
77    while ord(b) & (1<<n):
78        n -= 1
79    leading_ones += 7 - n
80    value = ord(b) & ((1<<n)-1)
81    remaining_bytes = (1<<leading_ones) - leading_ones // 8 - 1
82    for i in xrange(remaining_bytes):
83        value = value << 8 | ord(stream.read(1))
84    for i in range(leading_ones):
85        numeric_representation_bits = 8 * (1<<i) - (i+1)
86        value += 1 << numeric_representation_bits
87    return value
88
89
90if __name__ == '__main__':
91    import doctest
92    doctest.testmod()