uleb128 编码

1. 简介

uleb128（无符号小端变长编码）是一种编码格式，主要用于表示无符号整数。它是一种变长编码，可以有效地表示较小的整数，同时也支持较大的整数。ULEB128是DWARF调试信息格式和WebAssembly二进制格式中使用的一种编码方式。
怎么理解uleb128是如何编码的

2. 编码方式

uleb128编码的原理是将整数分成7位的分组，从低位到高位进行编码。每个分组会被编码为一个字节，字节的最高位（第8位）用于表示是否还有更多的字节需要解码。如果最高位为1，则表示后面的字节还有更多的数据；如果最高位为0，则表示这是最后一个字节。
这样，较小的整数可以用较少的字节表示，从而节省存储空间和传输带宽。
举例，假如现在有十六进制数据：

1 2	80 80 01 60 60 28 60 18

则这十六进制数据对应的二进制数据为：

1 2	10000000 10000000 00000001 01100000 01100000 00101000 01100000 00011000

由于uleb128 是可变长度的编码，所以需要一边解析直到读到结束标记位为止，每个分组的长度为一个字节，所以可以逐一字节解析：
第一个字节数据1000 0000（0x80），其最高位为 1，去掉最高位后为000 0000
第二个字节数据 1000 0000（0x80），其最高位为 1，去掉最高位后为000 0000
第三个字节数据 0000 0001（0x01），其最高位为 0，去掉最高位后为 000 0001
由于已经遇到最高位为 0 的字节，则第一个数据长度便是从第一个字节到第三个字节，总长度为三个字节，在小端模式下，这个数据便是去除高位后的七比特位进行拼接，拼接顺序是先第三个字节、第二个字节、第一个字节：000 0001 000 0000 000 0000，这个二进制表示的数据为：16384

现在继续进行解析，从第四个字节开始：
第四个字节数据 0110 0000（0x60），其最高位为 0，去掉最高位后为 110 0000
由于已经遇到最高位为 0 的字节，则第二个数据直接就是第四个字节所表示的数据，表示的数据为： 110 0000，这个二进制表示的数据为：96
参考上面的解析流程，则最后这八个字节解析出来的数据为：

1	16384 96 96 40 96 24

3. uleb128优势

如果不使用可变长度的编码方式，而是固定长度的编码，则每个数据使用多少个字节取决于最大的那个数据，假如一组数据最大值为16384（0x4000），也就是需要两个字节，则

1	16384 96 96 40 96 24

这一组数据所需要总共的字节数为 2 * 6 = 12 个字节，而使用 uleb128 所需要的总字节数为 8 个字节，相比于固定长度的编码，总共节省了 33.3% 。

4. python 解析

下面提供了从一个 byte数组解析成原来数据的代码：

def _parse_uleb128(self, data_bytes: bytes, start_offset: int, end_offset: int) -> List[int]:
    """
    给出一个 byte 数组，解析从[start_offset, end_offset]范围内的数据
    """
    assert 0 <= start_offset < len(data_bytes)
    assert start_offset <= end_offset < len(data_bytes)
    uleb128_result = []
    current_offset = start_offset
    current_num = ''
    while current_offset < end_offset:
        high_bit = (data_bytes[current_offset] & 0x80) >> 7
        seven_bit = data_bytes[current_offset] & 0x7f
        current_num = '{:07b}'.format(seven_bit) + current_num
        if high_bit == 0:  # 后续没有数据了
            uleb128_result.append(int(current_num, 2))
            current_num = ''  # 清空数据
        current_offset += 1
    if len(current_num) > 0:
        uleb128_result.append(int(current_num, 2))
    return uleb128_result