BUGFIX-66

Bug 32: Defective Bytewise Integer Decoder

• This decodes an integer from a variable-length sequence of bytes (a "varint" or "VLQ" encoding).
• This code supports 2 <= base <= 255. Specializations with a constant power-of-two base are fast.
• The base should be chosen to minimize average encoding length for the expected integer distribution.
• First, an unsigned integer intermediate (the signed integer output in zig-zag form) is decoded.
• This intermediate is decoded from zero or more nonterminal bytes followed by one terminal byte.
• The terminal bytes for a given base are 0, 1, 2, ..., 256-base-1.
• The nonterminal bytes are 256-base, 256-base+1, 256-base+2, ..., 253, 254, 255.
• E.g., if the base is 2 the terminals are 0, 1, ..., 253. The nonterminals are 254, 255.
• E.g., if the base is 3 the terminals are 0, 1, ..., 252. The nonterminals are 253, 254, 255.
• E.g., if the base is 4 the terminals are 0, 1, ..., 251. The nonterminals are 252, 253, 254, 255.
• E.g., if the base is 5 the terminals are 0, 1, ..., 250. The nonterminals are 251, 252, 253, 254, 255.
• A nonterminal byte represents a minimum value (i.e., 256-base) plus a remainder modulo the base.
• When a nonterminal byte is encountered, this minimum plus remainder is added to the intermediate.
• The bytes that follow represent a quotient, so they are added after multiplying by a power of the base.
• A terminal byte represents a small numeric value directly. It also marks the end of the encoding.
• The final unsigned integer intermediate is zig-zag unmapped to yield the signed integer output x.
• Intermediates 0, 2, 4, 6, ... are zig-zag unmapped to nonnegative outputs 0, 1, 2, 3, ...
• Intermediates 1, 3, 5, 7, ... are zig-zag unmapped to negative outputs -1, -2, -3, -4, ...
• The number of input bytes used to decode x (i.e., the length of the encoding) is also returned.

Fix The Tiny Bug In This Go Code:

To receive a hint, submit unfixed code.