LEB128 - Base 128 Varints Algorithm

signed_leb128_encode_decode.py

from unsigned_leb128_encode_decode import decode_unsigned_leb128, encode_unsigned_leb128

# Python 3.7.4


def encode_signed_leb128(number):
    # Higher multiple of 7
    bits_multiple_of_7 = ((number.bit_length() + 7) // 7) * 7
    twos_complement = (1 << bits_multiple_of_7) - number

    return encode_unsigned_leb128(twos_complement)


def decode_signed_leb128(byte_array, offset=0):
    number = decode_unsigned_leb128(byte_array, offset)
    # Lower multiple of 7
    bits_multiple_of_7 = (number.bit_length() // 7) * 7
    twos_complement = (1 << bits_multiple_of_7) - number

    return twos_complement

test_encoding.py

from signed_leb128_encode_decode import encode_signed_leb128, decode_signed_leb128
from unsigned_leb128_encode_decode import encode_unsigned_leb128, decode_unsigned_leb128


def test_signed_encoding(number):
    encoded = encode_signed_leb128(number)
    decoded = decode_signed_leb128(encoded)

    print("number: ", number)
    print("encoded: ", encoded.hex())
    print("decoded: ", decoded)
    print("matched: ", decoded == number)


def test_unsigned_encoding(number):
    encoded = encode_unsigned_leb128(number)
    decoded = decode_unsigned_leb128(encoded)

    print("number: ", number)
    print("encoded: ", encoded.hex())
    print("decoded: ", decoded)
    print("matched: ", decoded == number)

unsigned_leb128_encode_decode.py

# Python 3.7.4

def encode_unsigned_leb128(number):
    result = bytearray()

    # While number is greater than a byte
    while number.bit_length() > 7:
        # Get first 7 bits and append 1 on 8th bit
        single_byte = (number & 0b01111111) | 0b10000000
        # Append the byte to result
        result.append(single_byte)
        # Truncate right 7 bits
        number = number >> 7

    # Append remaining byte to result
    result.append(number)

    # As we appended earlier no need to reverse the bytes
    return result


def decode_unsigned_leb128(byte_array, offset=0):
    needle = offset
    pair_count = 0
    result = 0

    while True:
        single_byte = byte_array[needle]

        # If first bit is 1
        if single_byte & 0b10000000 == 0:
            break

        # Remove first bit
        single_byte = single_byte & 0b01111111

        # Push number of bits we already have calculated
        single_byte = single_byte << (pair_count * 7)

        # Merge byte with result
        result = result | single_byte

        needle = needle + 1
        pair_count = pair_count + 1

    # Merge last byte with result
    single_byte = single_byte << (pair_count * 7)
    result = result | single_byte

    return result