Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Different results #9

Open
unwave opened this issue May 5, 2021 · 2 comments
Open

Different results #9

unwave opened this issue May 5, 2021 · 2 comments

Comments

@unwave
Copy link

unwave commented May 5, 2021

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)
@unwave unwave mentioned this issue Jan 12, 2022
Closed
@unwave
Copy link
Author

unwave commented Jan 13, 2022

This repository implements LEB128 not VLQ.

@unwave unwave closed this as completed Jan 13, 2022
@fmoo fmoo reopened this Jan 13, 2022
@fmoo
Copy link
Owner

fmoo commented Jan 13, 2022

Seems worth updating the package metadata to clarify or supporting both at some point, yeah?

@SgtPooki SgtPooki mentioned this issue Nov 23, 2022
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@fmoo @unwave