Problem with converting hex values to decimal

Question

I'm reverse-engineering custom binary file format. I'm using 010 Editor to check this file. I found data structure to represent UTF-8 strings, which has header section of one or two bytes in length then the actual UTF-8 string data. The header section seems to store total number of bytes needed for the string data.

╔════════════╦═══════════════╦═══════════════════╗
║ first byte ║ optional byte ║ UTF-8 string data ║
╚════════════╩═══════════════╩═══════════════════╝

The second byte in header is optional and it's only there when UTF-8 string needs more than 128 bytes to be stored. When string length is less or equal 128 bytes, decoding it's length is easy. However, when string length > 128, I'm failing to calculate string length from header section. So I did experiments and generated many binary files with different string length and below is the result. String length is the total number of bytes needed to store the string. First and second columns are first and second optional byte in header section.

╔════╦════╦═══════════════╗
║ 01 ║ 02 ║ String length ║
╠════╬════╬═══════════════╣
║ 7D ║N/A ║           126 ║
║ 7E ║N/A ║           127 ║
║ 7F ║N/A ║           128 ║
║ 80 ║ 01 ║           129 ║
║ 81 ║ 01 ║           130 ║
║ C7 ║ 01 ║           200 ║
║ C8 ║ 01 ║           201 ║
║ F9 ║ 01 ║           250 ║
║ FE ║ 01 ║           255 ║
║ FF ║ 01 ║           256 ║
║ 80 ║ 02 ║           257 ║
║ 81 ║ 02 ║           258 ║
║ 82 ║ 02 ║           259 ║
║ F3 ║ 03 ║           500 ║
║ F4 ║ 03 ║           501 ║
║ F5 ║ 03 ║           502 ║
║ F6 ║ 03 ║           503 ║
║ 80 ║ 04 ║           513 ║
╚════╩════╩═══════════════╝

I read somewhere that Pascal\Delphi is using string format where it has header to save string length instead of null terminated strings like in C, which look similar to my case.

My question is how can I calculate string length when it's greater than 128 bytes in length using values in header section?

Answer 1

This is not the pascal/delphi string format, as those are either constant 1 byte or 4 bytes long length fields.

It does have some resemblance to the ASN1 format, except ASN1 comes with an additional field denoting the type of the object.

Anyways, This looks like the Most significant bit of the first byte is not part of the length and has the special meaning of extending the length by an additional byte.

If you take that table:

In [24]: t
Out[24]:
[['7D', 'N/A', '126'],
 ['7E', 'N/A', '127'],
 ['7F', 'N/A', '128'],
 ['80', '01', '129'],
 ['81', '01', '130'],
 ['C7', '01', '200'],
 ['C8', '01', '201'],
 ['F9', '01', '250'],
 ['FE', '01', '255'],
 ['FF', '01', '256'],
 ['80', '02', '257'],
 ['81', '02', '258'],
 ['82', '02', '259'],
 ['F3', '03', '500'],
 ['F4', '03', '501'],
 ['F5', '03', '502'],
 ['F6', '03', '503'],
 ['80', '04', '513']]

And split the MSB off the first byte:

In [36]: t2=[[int(l[0], 16)&0b10000000>0, hex(int(l[0], 16)&0b01111111)[2:]]+l[1:] for l in t]

In [37]: t2
Out[37]:
[[False, '7d', 'N/A', '126'],
 [False, '7e', 'N/A', '127'],
 [False, '7f', 'N/A', '128'],
 [True, '0', '01', '129'],
 [True, '1', '01', '130'],
 [True, '47', '01', '200'],
 [True, '48', '01', '201'],
 [True, '79', '01', '250'],
 [True, '7e', '01', '255'],
 [True, '7f', '01', '256'],
 [True, '0', '02', '257'],
 [True, '1', '02', '258'],
 [True, '2', '02', '259'],
 [True, '73', '03', '500'],
 [True, '74', '03', '501'],
 [True, '75', '03', '502'],
 [True, '76', '03', '503'],
 [True, '0', '04', '513']]

First, lets note that 0x7D is 125 in decimal, not 126. This is true for all values where MSB is clear, so all of these values are always increased by one.

Then if the MSB is set, values in the second byte are multiplied by 128 and then added to the first byte's result.

Here's an example that calculates the result using the previous two bytes (and appends it as the last value:

In [53]: t3 = [l+[int(l[1], 16) + 1 + (int(l[2], 16)*128 if l[0] else 0)] for l in t2]

In [54]: t3
Out[54]:
[[False, '7d', 'N/A', '126', 126],
 [False, '7e', 'N/A', '127', 127],
 [False, '7f', 'N/A', '128', 128],
 [True, '0', '01', '129', 129],
 [True, '1', '01', '130', 130],
 [True, '47', '01', '200', 200],
 [True, '48', '01', '201', 201],
 [True, '79', '01', '250', 250],
 [True, '7e', '01', '255', 255],
 [True, '7f', '01', '256', 256],
 [True, '0', '02', '257', 257],
 [True, '1', '02', '258', 258],
 [True, '2', '02', '259', 259],
 [True, '73', '03', '500', 500],
 [True, '74', '03', '501', 501],
 [True, '75', '03', '502', 502],
 [True, '76', '03', '503', 503],
 [True, '0', '04', '513', 513]]

The code doing the calculation above is not too pretty, so here's a short python function that does the same:

def calc(first_byte, second_byte):
    value = 1
    value += first_byte & 0x7F
    msb = bool(first_byte >> 7)
    if msb:
        value += second_byte * 128

Another way to look at it, which might be more intuitive, is that the second byte is a continuation of the 7 bits (excluding the MSB) for the first byte. Here's a function doing the same calculation based on that approach:

def calc(first_byte, second_byte):
    value = 1
    value += first_byte & 0x7F
    msb = bool(first_byte >> 7)
    if msb:
        value += second_byte << 7

We're lacking any values having the MSB set on the second byte, but this approach might be sequential, allowing larger ranges using additional bytes by setting the MSBs of all previous bytes.

Answer 2

This looks like the LEB128 encoding. 

 

Essentially, this is a variable length encoding where the lowest 7 bits of each byte store part of the value and highest bit of each byte is set if it's not the last byte. The successive 7-bit values are stored in little-endian order.

 

For more details, and especially for how signed numbers are handled, see either the DWARF Debugging Standard or the Android DEX file format documentation.

 

This is similar to the Variable-Length Quantity format used in MIDI files and ASN.1 encoding which uses big-endian ordering.