# Copyright (C) 2012 Peter Teichman

import array

# A few routines for encoding & decoding varint-encoded integers, as
# described in the Protocol Buffers docs:
# https://developers.google.com/protocol-buffers/docs/encoding#varints
#
# varint is a 7-bit integer encoding with the 8th reserved as a
# continuation bit. This is an implementation of the unsigned encoding
# only (not ZigZag).


def diff(seq):
    if not seq:
        return []

    ret = [seq[0]]
    for i in xrange(1, len(seq)):
        ret.append(seq[i] - seq[i - 1])
    return ret


def undiff(seq):
    if not seq:
        return []

    ret = [seq[0]]
    for i in xrange(1, len(seq)):
        ret.append(seq[i] + ret[i - 1])
    return ret


def encode_one(value):
    if value >= 0:
        return encode((value,))
    raise ValueError("negative numbers not supported")


def encode(values):
    buf = array.array("B")
    append = buf.append

    for value in values:
        bits = value & 0x7f
        value >>= 7
        while value:
            append(0x80 | bits)
            bits = value & 0x7f
            value >>= 7
        append(bits)

    return buf.tostring()


def decode_one(value):
    return decode(value)[0]


def decode(data):
    ret = []
    append = ret.append
    local_ord = ord

    cur = pos = shift = 0
    end = len(data)

    while pos < end:
        b = local_ord(data[pos])
        cur |= ((b & 0x7f) << shift)

        # If the high bit is set, continue reading the current int
        if b & 0x80:
            shift += 7
        else:
            append(cur)
            shift = 0
            cur = 0

        pos += 1

    return ret

@@ -732,61 +732,323 @@
 alue
-):%0A    if value %3E= 0:%0A        return encode((value,))
+, buf=array.array(%22B%22)):%0A    append = buf.append%0A%0A    if value %3E= 0:%0A        bits = value & 0x7f%0A        value %3E%3E= 7%0A        while value:%0A            append(0x80 %7C bits)%0A            bits = value & 0x7f%0A            value %3E%3E= 7%0A        append(bits)%0A%0A        ret = buf.tostring()%0A        del buf%5B:%5D%0A        return ret%0A
 %0A   
@@ -1122,21 +1122,14 @@
 lues
-):%0A   
+,
  buf
- = 
+=
 arra
@@ -1140,16 +1140,18 @@
 ray(%22B%22)
+):
 %0A    app
@@ -1379,19 +1379,18 @@
 %0A    ret
-urn
+ =
  buf.tos
@@ -1401,60 +1401,37 @@
 g()%0A
-%0A%0Adef decode_one(value):%0A    return decode(value)%5B0%5D
+    del buf%5B:%5D%0A    return ret
 %0A%0A%0Ad
@@ -1443,16 +1443,20 @@
 code
+_one
 (data):%0A
     
@@ -1455,45 +1455,8 @@
 a):%0A
-    ret = %5B%5D%0A    append = ret.append%0A
     
@@ -1471,17 +1471,16 @@
 d = ord%0A
-%0A
     cur 
@@ -1484,14 +1484,8 @@
 ur =
- pos =
  shi
@@ -1495,48 +1495,35 @@
 = 0%0A
+%0A
     
-end = len(data)%0A%0A    while pos %3C end
+for byte in iter(data)
 :%0A  
@@ -1546,17 +1546,12 @@
 ord(
-data%5Bpos%5D
+byte
 )%0A  
@@ -1596,68 +1596,413 @@
     
+  
-  # If the high bit is set, continue reading the current int
+if b & 0x80:%0A            shift += 7%0A        else:%0A            return cur%0A%0A%0Adef decode(data):%0A    # At least for small data, it's a significant performance%0A    # improvement to copy the data into a byte array to avoid calling%0A    # ord() on every byte.%0A    bytes = array.array(%22B%22, data)%0A%0A    ret = %5B%5D%0A    append = ret.append%0A%0A    cur = shift = 0%0A    for b in bytes:%0A        cur %7C= ((b & 0x7f) %3C%3C shift)%0A
 %0A   
@@ -2127,26 +2127,8 @@
  0%0A%0A
-        pos += 1%0A%0A
     

Optimize the varint encoder & decoder.