python-varint
python-varint copied to clipboard
Published
20 hours ago •
fmoo
fmoo
Different results
Why do the results differ?
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)
python-varint
True
0x00
0x00
True
0x7f
0x7f
False
0x80 0x01
0x81 0x00
False
0x80 0x40
0xc0 0x00
True
0xff 0x7f
0xff 0x7f
False
0x80 0x80 0x01
0x81 0x80 0x00
True
0xff 0xff 0x7f
0xff 0xff 0x7f
False
0x80 0x80 0x80 0x01
0x81 0x80 0x80 0x00
False
0x80 0x80 0x80 0x40
0xc0 0x80 0x80 0x00
True
0xff 0xff 0xff 0x7f
0xff 0xff 0xff 0x7f
https://exercism.io/tracks/python/exercises/variable-length-quantity/solutions/ff2630d14772492cabbb6db46f78729c
True
0x00
0x00
True
0x7f
0x7f
True
0x81 0x00
0x81 0x00
True
0xc0 0x00
0xc0 0x00
True
0xff 0x7f
0xff 0x7f
True
0x81 0x80 0x00
0x81 0x80 0x00
True
0xff 0xff 0x7f
0xff 0xff 0x7f
True
0x81 0x80 0x80 0x00
0x81 0x80 0x80 0x00
True
0xc0 0x80 0x80 0x00
0xc0 0x80 0x80 0x00
True
0xff 0xff 0xff 0x7f
0xff 0xff 0xff 0x7f
unwave
True
0x00
0x00
True
0x7f
0x7f
True
0x81 0x00
0x81 0x00
True
0xc0 0x00
0xc0 0x00
True
0xff 0x7f
0xff 0x7f
True
0x81 0x80 0x00
0x81 0x80 0x00
True
0xff 0xff 0x7f
0xff 0xff 0x7f
True
0x81 0x80 0x80 0x00
0x81 0x80 0x80 0x00
True
0xc0 0x80 0x80 0x00
0xc0 0x80 0x80 0x00
True
0xff 0xff 0xff 0x7f
0xff 0xff 0xff 0x7f
https://exercism.io/tracks/python/exercises/variable-length-quantity/solutions/ff2630d14772492cabbb6db46f78729c variable_length_quantity_test.py
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)
Seems worth updating the package metadata to clarify or supporting both at some point, yeah?
