Decoding a list of integer values in unknown format

Question

I'm attempting to reverse engineer a binary file format which is used to encode a list of integer values. I can't work out how this format works, as the number of bytes used to encode each value changes depending on the value itself, yet there's nothing I can see in the format which gives any indication of how many bytes each integer value contains!

Here's a sample of binary file contents vs their expected integer list values:

binary	values
0a 07 0a 05 03 04 06 07 0b	3, 4, 6, 7, 11
0a 04 0a 02 07 0b	7, 11
0a 1a 0a 18 88 0b 89 0b 8a 0b 8b 0b 8c 0b 8d 0b 8e 0b 8f 0b 90 0b 91 0b 92 0b 93 0b	1416, 1417, 1418, 1419, 1420, 1421, 1422, 1423, 1424, 1425, 1426, 1427
0a 0e 0a 0c 01 02 03 04 05 06 07 08 09 0a 0b 0c	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
0a 1e 0a 1c 01 02 03 04 05 06 07 08 09 0a 0b 0c b8 06 86 0b 8e 0b 8f 0b 91 0b 92 0b 93 0b 94 0b	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 824, 1414, 1422, 1423, 1425, 1426, 1427, 1428
0a 04 0a 02 94 0b	1428
0a 03 0a 01 01	1
0a 07 0a 05 d2 85 d8 cc 04	1234567890

Clearly the format starts with 0a total_size 0a list_size followed by the actual list of values, but I can't work out how the values could possibly be encoded!

Any assistance or insights would be greatly appreciated...

Answer 1

it is clear that if the high bit of the first byte is not set then it is just the value of the byte

So we can suspect that the high bit is a signal for extending the number

checking the lone 1428 value which in hex is 0x0594 we can see the sequence start with 94 (which has the high bit set) so it's in little endian followed by 0b and we can calculate 5<<1 | 1 = 0xb

So I presume the decoder code is

acc = 0
shift = 0
for each byte 
   acc |= (byte & 0x7f) << shift
   shift += 7
   if high bit not set
       emit acc
       acc = 0
       shift = 0

This also works with the 824 in one of the givens which matches to b8 06 and (0xb8 & 0x7f) | (0x06 << 7) = 0x338 = 824

Answer 2

The answer from @ratchet freak is correct.

To add a little more information, this format is known as LEB128. It's not uncommon and pops up in various places. For example, DWARF3 debug info and android's dalvik executable files.