LEB128 介绍

LEB128全称Little Endian Base 128，是一种变长编码格式。LEB128又分为unsinged LEB128 和 signed LEB128，即有符号与无符号两种，解码器必须知道编码值是无符号LEB128还是有符号LEB128。

ULEB128

ULEB128(unsigned LEB128)用于无符号整数的编码或解码，ULEB128中每个字节只有7位有效位，换而言之只有7位用于存储数据。而余下的1位作为标志位。

具体来说，一个字节中，最高位用于标记是否衔接下一个字节。当最高位为1时，代表与下一字节拼接。当最高位为0时，代表数据读取完成。

例如，对12726ULEB128编码，其二进制表示为0011000110110110，很显然12726是一个双字数据。

取低7位0110110，添加标志位得到：10110110，同理取1100011，添加标志位得到：01100011，最后得到0110001110110110。

同理，对此ULEB128解码如下图所示。这里就不再赘述。

下面是C/C++下的实现代码

static void ULEB128Encode(uint64_t val, BYTE *s) {
    unsigned char c;
    BOOL flag;
    do {
        c = val & 0x7f;
        val >>= 7;
        flag = val != 0;
        *s++ = c | (flag ? 0x80 : 0);
    } while (flag);
}

static uint64_t ULEB128Decode(BYTE *s) {
    uint64_t val = 0;
    int shift = 0;
    BOOL flag;
    BYTE c;

    do {
        c = *s++;
        val |= (c & 0x7f) << shift;
        shift += 7;
        flag = c & 0x80;
    } while (flag);
    
    return val;
}

SLEB128

SLEB128(signed LEB128)用于有符号整数的编码或解码，ULEB128与SLEB128的区别在于ULEB128对最后一个字节进行了符号位拓展。

将上文中ULEB128编码得到的0110001110110110，按照SLEB128解码，

取低字节10110110，标志位为1，继续取下一字节，取得01100011，此时标志位为0，拼接后我们取得的二进制表示为11000110110110。

还记得有符号与无符号整数的区别吗？

没错，这里的最高位即符号位。另外计算机中的数都是用补码表示的，所以需要求1000110110110的相反数补码。1000110110110实际占了14Bits，解码时最高位需要填充1，即11000110110110，即-3658。

下面是C/C++下的实现代码

static void SLEB128Encode(int64_t val, BYTE *s)
{
    unsigned char c;
    BOOL flag;

    do {
        c = val & 0x7f;
        val >>= 7;
        flag = c & 0x40 ? val != -1 : val != 0;
        *s++ = c | (flag ? 0x80 : 0);
    } while (flag);
}

static int64_t SLEB128Decode(const BYTE *s)
{
    int64_t c, val = 0;
    int shift = 0;
    int more;

    do {
        c = *s++;
        val |= (c & 0x7f) << shift;
        shift += 7;
        more = c & 0x80;
    } while (more);

    if (c & 0x40 && shift < sizeof(uint64_t) * CHAR_BIT) {
        val |= ~0UL << shift;
    }
    return val;
}

ULEB128p1

ULEB128p1(unsigned LEB128 plus 1)是dalvik中独有的一种变种LEB128编码。

其设计的初衷在于标识-1和非负数。其实现方式也非常简单，只需要在ULEB128的基础上减去1即可。

Reference

LEB128 – Wikipedia

LEB128(Little-Endian Base 128)格式介绍