Mas0n
to be reverse engineer🐧
翻车鱼

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解码如下图所示。这里就不再赘述。

https://cdn.shi1011.cn/2022/08/a16ceaed82cb23c3de0c891d5185c909.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

下面是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

https://cdn.shi1011.cn/2022/08/864e52ee5191ea08c93cb1188d555cc9.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

下面是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)格式介绍

本文链接:https://blog.shi1011.cn/learn/2323
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可

Mas0n

文章作者

发表评论

textsms
account_circle
email

翻车鱼

LEB128 介绍
LEB128全称Little Endian Base 128,是一种变长编码格式。LEB128又分为unsinged LEB128 和 signed LEB128,即有符号与无符号两种,解码器必须知道编码值是无符号LEB128还是有符号LEB128。…
扫描二维码继续阅读
2022-08-02