varint.py

# Variable-size integer encoding
# Uses the same encoding format as Google's Protocol Buffers described here:
# http://code.google.com/apis/protocolbuffers/docs/encoding.html#varints
# However this code supports arbitrarily large integers instead of fixed 32/64-bit.

def encode_varint(n):
    chars = []
    while n > 0x7f:
        chars.append(chr(0x80 | (n & 0x7f)))
        n >>= 7
    chars.append(chr(n))
    return "".join(chars)

def decode_varint(s):
    n = 0
    shift = 0
    for c in s:
        c = ord(c)
        n |= (c & 0x7f) << shift
        shift += 7
        if (c & 0x80) == 0:
            break
    return n

def zigzag(n):
    return (abs(n) << 1) - (n < 0)

def unzigzag(n):
    return (n >> 1) ^ -(n & 1)

def encode_signed_varint(n):
    return encode_varint(zigzag(n))

def decode_signed_varint(s):
    return unzigzag(decode_varint(s))