Skip to content

Instantly share code, notes, and snippets.

@nazarhussain
Last active July 11, 2021 04:20
Show Gist options
  • Save nazarhussain/78a3e12be1b66b29bcd3f25410f477e4 to your computer and use it in GitHub Desktop.
Save nazarhussain/78a3e12be1b66b29bcd3f25410f477e4 to your computer and use it in GitHub Desktop.
LEB128 - Base 128 Varints Algorithm
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
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)
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment