1 | #!/usr/bin/env python |
---|
2 | """A simplistic implementation of a variable length integer encoding. |
---|
3 | |
---|
4 | You may use this under the MIT license. |
---|
5 | |
---|
6 | Copyright 2012, Eli Carter, elicarter@retracile.net |
---|
7 | """ |
---|
8 | |
---|
9 | def 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 | |
---|
51 | def 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 | |
---|
90 | if __name__ == '__main__': |
---|
91 | import doctest |
---|
92 | doctest.testmod() |
---|