Challenging variable-length integer encoding

Question

I have a piece of binary data I'm trying to investigate. My guess is that it should be part of simple filesystem-like index. There are 2 parts in the file. First part has a very simple format:

• number of bytes for the first part
• lots of zero-terminated strings that look like file names (1256 of them)

Naturally, I expect to find increasing pointers to some files named with these strings later. However, the rest of the file is 0x5c47 bytes long and it looks like it has a number of records (int32, little endian = 0x4e0), then a sequence of records itselves. However, the trick is that obviously record length is not constant: (0x5c47 - 4) / 0x4e0 ~ 18.9254807. I see a certain pattern here, let me demonstrate:

E0 04 00 00

As I said, it starts with number of records, 0x4e0 = 1248. Note that 1248 records is fairly close to number of strings I've found earlier (1256), but not exactly matching. Then I see some 14-byte long records:

90 00   |90 0D|90 16 02 90 22 90 2A 90 39|00
90 46   |90 0D|90 16 02 90 22 90 2A 90 39|01
90 53   |90 0D|90 16 02 90 22 90 2A 90 39|02
90 61   |90 0D|90 16 02 90 22 90 2A 90 39|03
90 6E   |90 0D|90 16 02 90 22 90 2A 90 39|04

Last byte seems to be record number counter. As for others, so far, only 2nd byte changes. However, next we see some 15-byte long records:

91 82 00|90 0D|90 16 02 90 22 90 2A 90 39|05
91 97 00|90 0D|90 16 02 90 22 90 2A 90 39|06
91 A4 00|90 0D|90 16 02 90 22 90 2A 90 39|07
...
91 14 01|90 0D|90 16 02 90 22 90 2A 90 39|0E

It seems that there are some variable length integers involved, i.e. first value of a record starts with 90 00, 90 46, then it eventually overflows and becomes 91 82 00, 91 97 00, ... 91 26 01, etc. However, it's not the normal (BER, AKA VLQ, AKA Base128, etc) encoding for variable length integers I've used to. Let's check how contents of the record would expand once it will become 16-byte long record:

91 26 01|90 0D|90 16 02 90 22 90 2A 90 39|0F
91 39 01|90 0D|90 16 02 90 22 90 2A 90 39|80 10
91 4E 01|90 0D|90 16 02 90 22 90 2A 90 39|80 11
91 6C 01|90 0D|90 16 02 90 22 90 2A 90 39|80 12
91 8B 01|90 0D|90 16 02 90 22 90 2A 90 39|80 13
...

Whoa, it was just 05, 06, 07, ... 0E, 0F (which presumably encoded record #0..15), then it jumped to 80 10 to designate record #16. First field seems to continue being 3-byte integer. Next switch to 17-byte long recods looks like that:

...
91 7C 08|90 0D|90 16 02 90 22 90 2A 90 39|80 7D
91 8A 08|90 0D|90 16 02 90 22 90 2A 90 39|80 7E
91 98 08|90 0D|90 16 02 90 22 90 2A 90 39|81 7F 00
91 A6 08|90 0D|90 16 02 90 22 90 2A 90 39|81 80 00
91 B4 08|90 0D|90 16 02 90 22 90 2A 90 39|81 81 00
91 C2 08|90 0D|90 16 02 90 22 90 2A 90 39|81 82 00
...

There are some vague resemblance with the trick that we've seen earlier with 90 becoming 91: here 80 becomes 81 presumably to designate switch from #126 = 0x7e (encoded as 80 7E) to #127 = 0x7f (encoded as 81 7F 00).

Further in the file there seems to be a major format switch for 18-byte long record which I guess lines up somewhat like that:

...
91 5D 14|90 0D   |90 16   |02|90 22|90 2A   |90 39|81 5C 01
91 6A 14|90 0D   |90 16   |02|90 22|90 2A   |90 39|81 5D 01
91 77 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|00
91 AA 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|01
91 B5 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|02
91 C0 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|03
91 CB 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|04
...

This change expands many of the fields (and actually makes it somewhat cleared what the fields boundaries are) and resets last field back to 0.

There are some vague resemblance with the trick that we've seen earlier with 90 becoming 91: here 80 becomes 81 presumably to designate switch from #126 = 0x7e (encoded as 80 7E) to #127 = 0x7f (encoded as 81 7F 00). Records at the end of the file are 20 bytes long and look like that:

...
91 32 34|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|81 7F 03
91 3B 34|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|81 80 03
91 44 34|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|81 81 03

My best bet here is that many intermediate values have increased and 90 xx became 91 xx yy.

To summarize what I've learned so far, it looks like these records use variable-length encoded integers, encoding scheme is something like:

• 0x0 = 00 = 0000_0000
• 0x1 = 01 = 0000_0001
• ...
• 0xf = 0F = 0000_1111
• 0x10 = 80 10 = 1000_0000|0001_0000
• 0x11 = 80 11 = 1000_0000|0001_0001
• ...
• 0x7e = 80 7E = 1000_0000|0111_1110
• 0x7f = 81 7F 00 = 1000_0001|0111_1111|0000_0000
• 0x80 = 81 80 00 = 1000_0001|1000_0000|0000_0000
• ...
• 0x15d = 81 5D 01 = 1000_0001|0101_1101|0000_0001

Does anyone know of any standard format / encoding scheme that looks like that? Any ideas on how to properly decode 90 xx and 91 xx yy values?

Answer 1

Each of the eight fields in the record has a one-byte header.

In the header, high nybble 8 means unsigned and high nybble 9 means signed (or possibly the other way around, can't be sure); low nybble is then the number of bytes needed to encode the number (not counting the header byte), decremented by one.
If the high nybble of the header is 0, that's a special code for very small unsigneds (more precisely: very small numbers of same type as 8) and in that case the low nybble is the entire number.

Now, the tricky thing that's been making this hard is that (for types 8 and 9) the rest of the number is encoded using a method that signals the encoding length on its own, wastefully unaware that the header has already told us how many bytes will be needed for the encoding. My guess is that the header byte was "invented" for this application after this inner encoding was already decided upon.

For positive integers, that inner encoding is very similar to VLQ (thanks for dropping the names, I wasn't aware of them): output lowest 7 bits of the number as a single byte, and set the MSB of that byte to 1 if there are more bytes to follow, or to 0 if not; continue with the next 7 bits, etc.
The difference from VLQ is that the bit sequence 7F is treated as non-terminating, which may be an Obi-Wan bug in the encoder, or some kind of a genuine design decision that I don't really understand. (It can't be about signalling that the number shouldn't be sign-extended as negative, because then the same would apply for 40-7e.)

It would be interesting to see the 4th record from the end - it should end with the value 0x1fe, and I expect it would be encoded as 81 FE 03 (noting that 0x1ff is encoded as 81 7f 03, implying that this encoding never uses the value FF anywhere.)

We don't have examples of negative numbers in your sample, so we can't tell how they would be encoded.