Fix the strict varint decoder behind a fuzz test
Your task
You are shipping a fast varint decoder for a network protocol. A varint stores an integer in 7-bit groups, one per byte, and a byte's high bit says another byte follows. The assistant's fuzz test only checked that decoding never crashes, so the team wants a strict decoder to check every decoded value and length against.
An assistant wrote decode_varint(data). It is in the editor. It has a bug. Find it and fix it.
Input and output:
data: a list of integers, meant to be bytes from 0 to 255. It can be empty and can hold any integer.- Return
[value, length], wherelengthis the number of bytes the varint used, or an empty list to refuse the input.
Rules the tests check:
- Read bytes from the start. A byte's low 7 bits (the byte modulo 128) are data. A byte of 128 or more says another byte follows.
- The first byte holds the lowest 7 bits, and each later byte counts 128 times as much as the one before. So the value is the sum of (byte modulo 128) times 128 to the power of its position, starting at position 0.
- The varint ends at the first byte below 128. Bytes after it are not read or checked.
- Return an empty list when any of these happens:
- a byte that is read, up to and including the varint's last byte, is below 0 or above 255;
- the data runs out before a byte below 128 is found;
- the varint is 2 or more bytes long and its last byte is 0, because the same value has a shorter encoding;
- the 9th byte is still 128 or more, because a 10th byte would go past 63 bits.
Examples
decode_varint(data: list[int]) -> list[int]Example 1
Input
decode_varint([0])Output
[0, 1]Example 2
Input
decode_varint([172, 2])Output
[300, 2]Example 3
Input
decode_varint([172])Output
[]