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?