def show(bytearray):
print("".join(fr"\x{format(x, '02x')}" for x in bytearray))
def _byte(b):
return bytes((b, ))
def encode(number):
"""Pack `number` into varint bytes"""
buf = b''
while True:
towrite = number & 0x7f
number >>= 7
if number:
buf += _byte(towrite | 0x80)
else:
buf += _byte(towrite)
break
return buf
def encode_2(values):
"""Encode a list of hex numbers to their Variable Length Quantity values"""
encoded = []
for value in values:
bl, length = int.bit_length(value), len(encoded)
encoded.append(value & 127) # compute last 7-bits
while bl > 7:
value >>= 7 # observe 7 bits further
bl -= 7
encoded.insert(length, (value & 127) + 128)
return encoded
def encode_2_wrapper(n):
return encode_2([n])
def vlq_encode(n):
""" https://en.wikipedia.org/wiki/Variable-length_quantity """
result = [n & 127] # 127 -> 011111111
n >>= 7
while n:
result.append(n & 127 | 128) # 128 -> 100000000
n >>= 7
return bytes(reversed(result))
def test_wiki(f):
decimals = (0, 127, 128, 8192, 16383, 16384, 2097151, 2097152, 134217728, 268435455)
vlq_hexes = (('0x00',), ('0x7F',), ('0x81', '0x00',), ('0xC0', '0x00',), ('0xFF', '0x7F',), ('0x81', '0x80', '0x00',), ('0xFF', '0xFF', '0x7F',), ('0x81', '0x80', '0x80', '0x00',), ('0xC0', '0x80', '0x80', '0x00',), ('0xFF', '0xFF', '0xFF', '0x7F',))
for d, h in zip(decimals, vlq_hexes):
my_hexes = [fr"0x{format(x, '02x')}" for x in f(d)]
a = my_hexes
b = [x.lower() for x in h]
print(a == b)
print(*a)
print(*b)
print()
print("python-varint")
test_wiki(encode)
print()
print("https://exercism.io/tracks/python/exercises/variable-length-quantity/solutions/ff2630d14772492cabbb6db46f78729c")
test_wiki(encode_2_wrapper)
print()
print("unwave")
test_wiki(vlq_encode)import unittest
def vlq_encode(n):
""" https://en.wikipedia.org/wiki/Variable-length_quantity """
result = [n & 127] # 127 -> 011111111
n >>= 7
while n:
result.append(n & 127 | 128) # 128 -> 100000000
n >>= 7
return list(reversed(result))
def _byte(b):
return bytes((b, ))
def python_varint(number):
"""Pack `number` into varint bytes"""
buf = b''
while True:
towrite = number & 0x7f
number >>= 7
if number:
buf += _byte(towrite | 0x80)
else:
buf += _byte(towrite)
break
return buf
# Tests adapted from `problem-specifications//canonical-data.json` @ v1.1.0
class VariableLengthQuantityTest(unittest.TestCase):
def test_zero(self):
self.assertEqual(encode([0x0]), [0x0])
def test_arbitrary_single_byte(self):
self.assertEqual(encode([0x40]), [0x40])
def test_largest_single_byte(self):
self.assertEqual(encode([0x7f]), [0x7f])
def test_smallest_double_byte(self):
self.assertEqual(encode([0x80]), [0x81, 0x0])
def test_arbitrary_double_byte(self):
self.assertEqual(encode([0x2000]), [0xc0, 0x0])
def test_largest_double_byte(self):
self.assertEqual(encode([0x3fff]), [0xff, 0x7f])
def test_smallest_triple_byte(self):
self.assertEqual(encode([0x4000]), [0x81, 0x80, 0x0])
def test_arbitrary_triple_byte(self):
self.assertEqual(encode([0x100000]), [0xc0, 0x80, 0x0])
def test_largest_triple_byte(self):
self.assertEqual(encode([0x1fffff]), [0xff, 0xff, 0x7f])
def test_smallest_quadruple_byte(self):
self.assertEqual(encode([0x200000]), [0x81, 0x80, 0x80, 0x0])
def test_arbitrary_quadruple_byte(self):
self.assertEqual(encode([0x8000000]), [0xc0, 0x80, 0x80, 0x0])
def test_largest_quadruple_byte(self):
self.assertEqual(encode([0xfffffff]), [0xff, 0xff, 0xff, 0x7f])
def test_smallest_quintuple_byte(self):
self.assertEqual(encode([0x10000000]), [0x81, 0x80, 0x80, 0x80, 0x0])
def test_arbitrary_quintuple_byte(self):
self.assertEqual(encode([0xff000000]), [0x8f, 0xf8, 0x80, 0x80, 0x0])
def test_maximum_32_bit_integer_input(self):
self.assertEqual(encode([0xffffffff]), [0x8f, 0xff, 0xff, 0xff, 0x7f])
def test_two_single_byte_values(self):
self.assertEqual(encode([0x40, 0x7f]), [0x40, 0x7f])
def test_two_multi_byte_values(self):
self.assertEqual(
encode([0x4000, 0x123456]), [0x81, 0x80, 0x0, 0xc8, 0xe8, 0x56])
def test_many_multi_byte_values(self):
self.assertEqual(
encode([0x2000, 0x123456, 0xfffffff, 0x0, 0x3fff, 0x4000]),
[0xc0, 0x0, 0xc8, 0xe8, 0x56, 0xff, 0xff, 0xff, 0x7f, 0x0, 0xff,
0x7f, 0x81, 0x80, 0x0]
)
# def test_one_byte(self):
# self.assertEqual(decode([0x7f]), [0x7f])
# def test_two_bytes(self):
# self.assertEqual(decode([0xc0, 0x0]), [0x2000])
# def test_three_bytes(self):
# self.assertEqual(decode([0xff, 0xff, 0x7f]), [0x1fffff])
# def test_four_bytes(self):
# self.assertEqual(decode([0x81, 0x80, 0x80, 0x0]), [0x200000])
# def test_maximum_32_bit_integer(self):
# self.assertEqual(decode([0x8f, 0xff, 0xff, 0xff, 0x7f]), [0xffffffff])
# def test_incomplete_sequence_causes_error(self):
# with self.assertRaisesWithMessage(ValueError):
# decode([0xff])
# def test_incomplete_sequence_causes_error_even_if_value_is_zero(self):
# with self.assertRaisesWithMessage(ValueError):
# decode([0x80])
# def test_multiple_values(self):
# self.assertEqual(
# decode([0xc0, 0x0, 0xc8, 0xe8, 0x56, 0xff, 0xff, 0xff, 0x7f,
# 0x0, 0xff, 0x7f, 0x81, 0x80, 0x0]),
# [0x2000, 0x123456, 0xfffffff, 0x0, 0x3fff, 0x4000]
# )
# Utility functions
def setUp(self):
try:
self.assertRaisesRegex
except AttributeError:
self.assertRaisesRegex = self.assertRaisesRegexp
def assertRaisesWithMessage(self, exception):
return self.assertRaisesRegex(exception, r".+")
if __name__ == '__main__':
import sys
sys.argv.append('-v')
def encode(n):
return [i for x in n for i in vlq_encode(x)]
print("vlq_encode")
unittest.main(exit=False)
def encode(n):
return [i for x in n for i in python_varint(x)]
print("python_varint")
unittest.main(exit=False)vlq_encode
test_arbitrary_double_byte (__main__.VariableLengthQuantityTest) ... ok
test_arbitrary_quadruple_byte (__main__.VariableLengthQuantityTest) ... ok
test_arbitrary_quintuple_byte (__main__.VariableLengthQuantityTest) ... ok
test_arbitrary_single_byte (__main__.VariableLengthQuantityTest) ... ok
test_arbitrary_triple_byte (__main__.VariableLengthQuantityTest) ... ok
test_largest_double_byte (__main__.VariableLengthQuantityTest) ... ok
test_largest_quadruple_byte (__main__.VariableLengthQuantityTest) ... ok
test_largest_single_byte (__main__.VariableLengthQuantityTest) ... ok
test_largest_triple_byte (__main__.VariableLengthQuantityTest) ... ok
test_many_multi_byte_values (__main__.VariableLengthQuantityTest) ... ok
test_maximum_32_bit_integer_input (__main__.VariableLengthQuantityTest) ... ok
test_smallest_double_byte (__main__.VariableLengthQuantityTest) ... ok
test_smallest_quadruple_byte (__main__.VariableLengthQuantityTest) ... ok
test_smallest_quintuple_byte (__main__.VariableLengthQuantityTest) ... ok
test_smallest_triple_byte (__main__.VariableLengthQuantityTest) ... ok
test_two_multi_byte_values (__main__.VariableLengthQuantityTest) ... ok
test_two_single_byte_values (__main__.VariableLengthQuantityTest) ... ok
test_zero (__main__.VariableLengthQuantityTest) ... ok
----------------------------------------------------------------------
Ran 18 tests in 0.003s
OK
python_varint
test_arbitrary_double_byte (__main__.VariableLengthQuantityTest) ... FAIL
test_arbitrary_quadruple_byte (__main__.VariableLengthQuantityTest) ... FAIL
test_arbitrary_quintuple_byte (__main__.VariableLengthQuantityTest) ... FAIL
test_arbitrary_single_byte (__main__.VariableLengthQuantityTest) ... ok
test_arbitrary_triple_byte (__main__.VariableLengthQuantityTest) ... FAIL
test_largest_double_byte (__main__.VariableLengthQuantityTest) ... ok
test_largest_quadruple_byte (__main__.VariableLengthQuantityTest) ... ok
test_largest_single_byte (__main__.VariableLengthQuantityTest) ... ok
test_largest_triple_byte (__main__.VariableLengthQuantityTest) ... ok
test_many_multi_byte_values (__main__.VariableLengthQuantityTest) ... FAIL
test_maximum_32_bit_integer_input (__main__.VariableLengthQuantityTest) ... FAIL
test_smallest_double_byte (__main__.VariableLengthQuantityTest) ... FAIL
test_smallest_quadruple_byte (__main__.VariableLengthQuantityTest) ... FAIL
test_smallest_quintuple_byte (__main__.VariableLengthQuantityTest) ... FAIL
test_smallest_triple_byte (__main__.VariableLengthQuantityTest) ... FAIL
test_two_multi_byte_values (__main__.VariableLengthQuantityTest) ... FAIL
test_two_single_byte_values (__main__.VariableLengthQuantityTest) ... ok
test_zero (__main__.VariableLengthQuantityTest) ... ok
======================================================================
FAIL: test_arbitrary_double_byte (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 45, in test_arbitrary_double_byte
self.assertEqual(encode([0x2000]), [0xc0, 0x0])
AssertionError: Lists differ: [128, 64] != [192, 0]
First differing element 0:
128
192
- [128, 64]
+ [192, 0]
======================================================================
FAIL: test_arbitrary_quadruple_byte (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 63, in test_arbitrary_quadruple_byte
self.assertEqual(encode([0x8000000]), [0xc0, 0x80, 0x80, 0x0])
AssertionError: Lists differ: [128, 128, 128, 64] != [192, 128, 128, 0]
First differing element 0:
128
192
- [128, 128, 128, 64]
+ [192, 128, 128, 0]
======================================================================
FAIL: test_arbitrary_quintuple_byte (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 72, in test_arbitrary_quintuple_byte
self.assertEqual(encode([0xff000000]), [0x8f, 0xf8, 0x80, 0x80, 0x0])
AssertionError: Lists differ: [128, 128, 128, 248, 15] != [143, 248, 128, 128, 0]
First differing element 0:
128
143
- [128, 128, 128, 248, 15]
+ [143, 248, 128, 128, 0]
======================================================================
FAIL: test_arbitrary_triple_byte (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 54, in test_arbitrary_triple_byte
self.assertEqual(encode([0x100000]), [0xc0, 0x80, 0x0])
AssertionError: Lists differ: [128, 128, 64] != [192, 128, 0]
First differing element 0:
128
192
- [128, 128, 64]
+ [192, 128, 0]
======================================================================
FAIL: test_many_multi_byte_values (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 88, in test_many_multi_byte_values
0x7f, 0x81, 0x80, 0x0]
AssertionError: Lists differ: [128, 64, 214, 232, 72, 255, 255, 255, 127, 0, 255, 127, 128, 128, 1] != [192, 0, 200, 232, 86, 255, 255, 255, 127, 0, 255, 127, 129, 128, 0]
First differing element 0:
128
192
- [128, 64, 214, 232, 72, 255, 255, 255, 127, 0, 255, 127, 128, 128, 1]
+ [192, 0, 200, 232, 86, 255, 255, 255, 127, 0, 255, 127, 129, 128, 0]
======================================================================
FAIL: test_maximum_32_bit_integer_input (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 75, in test_maximum_32_bit_integer_input
self.assertEqual(encode([0xffffffff]), [0x8f, 0xff, 0xff, 0xff, 0x7f])
AssertionError: Lists differ: [255, 255, 255, 255, 15] != [143, 255, 255, 255, 127]
First differing element 0:
255
143
- [255, 255, 255, 255, 15]
+ [143, 255, 255, 255, 127]
======================================================================
FAIL: test_smallest_double_byte (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 42, in test_smallest_double_byte
self.assertEqual(encode([0x80]), [0x81, 0x0])
AssertionError: Lists differ: [128, 1] != [129, 0]
First differing element 0:
128
129
- [128, 1]
? ^ ^
+ [129, 0]
? ^ ^
======================================================================
FAIL: test_smallest_quadruple_byte (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 60, in test_smallest_quadruple_byte
self.assertEqual(encode([0x200000]), [0x81, 0x80, 0x80, 0x0])
AssertionError: Lists differ: [128, 128, 128, 1] != [129, 128, 128, 0]
First differing element 0:
128
129
- [128, 128, 128, 1]
+ [129, 128, 128, 0]
======================================================================
FAIL: test_smallest_quintuple_byte (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 69, in test_smallest_quintuple_byte
self.assertEqual(encode([0x10000000]), [0x81, 0x80, 0x80, 0x80, 0x0])
AssertionError: Lists differ: [128, 128, 128, 128, 1] != [129, 128, 128, 128, 0]
First differing element 0:
128
129
- [128, 128, 128, 128, 1]
+ [129, 128, 128, 128, 0]
======================================================================
FAIL: test_smallest_triple_byte (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 51, in test_smallest_triple_byte
self.assertEqual(encode([0x4000]), [0x81, 0x80, 0x0])
AssertionError: Lists differ: [128, 128, 1] != [129, 128, 0]
First differing element 0:
128
129
- [128, 128, 1]
+ [129, 128, 0]
======================================================================
FAIL: test_two_multi_byte_values (__main__.VariableLengthQuantityTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\Desktop\test_210505_214413.py", line 82, in test_two_multi_byte_values
encode([0x4000, 0x123456]), [0x81, 0x80, 0x0, 0xc8, 0xe8, 0x56])
AssertionError: Lists differ: [128, 128, 1, 214, 232, 72] != [129, 128, 0, 200, 232, 86]
First differing element 0:
128
129
- [128, 128, 1, 214, 232, 72]
+ [129, 128, 0, 200, 232, 86]
----------------------------------------------------------------------
Ran 18 tests in 0.009s
FAILED (failures=11)
Why do the results differ?
https://exercism.io/tracks/python/exercises/variable-length-quantity/solutions/ff2630d14772492cabbb6db46f78729c
variable_length_quantity_test.py