Android-Dex 解析之Leb128 知识点

这篇文章上次修改于 1614 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

0x1 介绍

LEB128(little endian base 128)是一种变长的整数压缩编码形式，它是出自于DWARF debug file format。在Android的Dalvik Executable format中使用该编码用于表示32位整数。由于32位整数占用固定的4个字节，可能大多数整数并不需要4个字节，最高几个字节可能为0（正数）或者为1（负数），该编码就是不保存最高位的这些字节。

0x2 原理

LEB128的表现形式都是一样的，如下面表格所示，由于是little endian，因此是从低字节到高字节。每个字节中的最高bit是标识信息，1表示还有后续字节，0表示结束，后面7bits是有效数据。将多个字节的该7bits从低到高组合起来就是所表示的整数。
LEB128分成有符号数和无符号数两种分别进行处理，不过，只是在编码和解码过程有些不同。

0x3 前置知识点

进制间转换

在线工具 https://tool.oschina.net/hexconvert

2、8、16进制->10进制

二进制 → 十进制

　　方法：二进制数从低位到高位（即从右往左）计算，第0位的权值是2的0次方，第1位的权值是2的1次方，第2位的权值是2的2次方，依次递增下去，把最后的结果相加的值就是十进制的值了。

　　例：将二进制的(101011)B转换为十进制的步骤如下：

第0位 1 x 2^0 = 1；
第1位 1 x 2^1 = 2；
第2位 0 x 2^2 = 0；
第3位 1 x 2^3 = 8；
第4位 0 x 2^4 = 0；
第5位 1 x 2^5 = 32；
读数，把结果值相加，1+2+0+8+0+32=43，即(101011)B=(43)D。

八进制 → 十进制

　　方法：八进制数从低位到高位（即从右往左）计算，第0位的权值是8的0次方，第1位的权值是8的1次方，第2位的权值是8的2次方，依次递增下去，把最后的结果相加的值就是十进制的值了。

　　八进制就是逢8进1，八进制数采用 0～7这八数来表达一个数。

　　例：将八进制的(53)O转换为十进制的步骤如下：

第0位 3 x 8^0 = 3；
第1位 5 x 8^1 = 40；
读数，把结果值相加，3+40=43，即(53)O=(43)D。

十六进制 → 十进制

　　方法：十六进制数从低位到高位（即从右往左）计算，第0位的权值是16的0次方，第1位的权值是16的1次方，第2位的权值是16的2次方，依次递增下去，把最后的结果相加的值就是十进制的值了。

　　十六进制就是逢16进1，十六进制的16个数为0123456789ABCDEF。

　　例：将十六进制的(2B)H转换为十进制的步骤如下：

第0位 B x 16^0 = 11；
第1位 2 x 16^1 = 32；
读数，把结果值相加，11+32=43，即(2B)H=(43)D。

10进制->2、8、16进制

十进制 → 二进制

　　方法：除2取余法，即每次将整数部分除以2，余数为该位权上的数，而商继续除以2，余数又为上一个位权上的数，这个步骤一直持续下去，直到商为0为止，最后读数时候，从最后一个余数读起，一直到最前面的一个余数。

　　例：将十进制的(43)D转换为二进制的步骤如下：

将商43除以2，商21余数为1；
将商21除以2，商10余数为1；
将商10除以2，商5余数为0；
将商5除以2，商2余数为1；
将商2除以2，商1余数为0；
将商1除以2，商0余数为1；
读数，因为最后一位是经过多次除以2才得到的，因此它是最高位，读数字从最后的余数向前读，101011，即(43)D=(101011)B。

十进制 → 八进制

　　方法1：除8取余法，即每次将整数部分除以8，余数为该位权上的数，而商继续除以8，余数又为上一个位权上的数，这个步骤一直持续下去，直到商为0为止，最后读数时候，从最后一个余数起，一直到最前面的一个余数。

　　例：将十进制的(796)D转换为八进制的步骤如下：

将商796除以8，商99余数为4；
将商99除以8，商12余数为3；
将商12除以8，商1余数为4；
将商1除以8，商0余数为1；
读数，因为最后一位是经过多次除以8才得到的，因此它是最高位，读数字从最后的余数向前读，1434，即(796)D=(1434)O。

十进制 → 十六进制

　　方法1：除16取余法，即每次将整数部分除以16，余数为该位权上的数，而商继续除以16，余数又为上一个位权上的数，这个步骤一直持续下去，直到商为0为止，最后读数时候，从最后一个余数起，一直到最前面的一个余数。

　　例：将十进制的(796)D转换为十六进制的步骤如下：

将商796除以16，商49余数为12，对应十六进制的C；
将商49除以16，商3余数为1；
将商3除以16，商0余数为3；
读数，因为最后一位是经过多次除以16才得到的，因此它是最高位，读数字从最后的余数向前读，31C，即(796)D=(31C)H。

逻辑与(&)计算

逻辑与计算

5&3

5转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
3转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
----------------------------------------------------
1转换为二进制：0000 0000 0000 0000 0000 0000 0000 0001

从低位到高位，从右往左，开始比较。

1&1=1

0&1=0

1&0=0

...

逻辑或(|)计算

5转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
3转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
----------------------------------------------------
7转换为二进制：0000 0000 0000 0000 0000 0000 0000 0111

从低位到高位，从右往左，开始比较。

1&1=1

0&1=1

1&0=1

0&0=0

...

移位运算(<< or >>)

5<<2 5左移 2 位
首先会将5转为2进制表示形式(java中，整数默认就是int类型,也就是32位):

0000 0000 0000 0000 0000 0000 0000 0101           然后左移2位后，低位补0：
0000 0000 0000 0000 0000 0000 0001 0100           换算成10进制为20

5>>2 5右移 2 位
还是先将5转为2进制表示形式：
0000 0000 0000 0000 0000 0000 0000 0101 然后右移2位，高位补0：
0000 0000 0000 0000 0000 0000 0000 0001

Python 运算符优先级

运算符	描述
**	指数 (最高优先级)
~ + -	按位翻转, 一元加号和减号 (最后两个的方法名为 +@ 和 -@)
* / % //	乘，除，取模和取整除
+ -	加法减法
>> <<	右移，左移运算符
&	位 'AND'
^ \		位运算符
<= < > >=	比较运算符
<> == !=	等于运算符
= %= /= //= -= += = *=	赋值运算符
is is not	身份运算符
in not in	成员运算符
not and or	逻辑运算符

0x4 LEB128编码过程

无符号整数

无符号整数编码步骤如下：

将无符号整数写成二进制形式，
从低位到高位7个bits为一个整体组合成一个字节，
在该字节最高位填入上述所说的标识信息。
按照小端规则存放

下面以10000为例，

编码过程：

二进制形式为	10 0111 0001 0000
以7bits为整体	1001110 0010000
添加标识组合成新的字节(从后往前，即低bits到高bits）	01001110(0x4E) 10010000(0x90) (最高位标识设置为0，表示没有后续字节)
LEB128 则为	0x90 0x4F (小端存放)

解码过程：

LEB128	0x90 0x4E
二进制形式	10010000 01001110
去掉标识信息	0010000（低7bits) 1001110（高7bits）
组合的结果为	10011100010000 （10000）

Python 代码实现

class _U:
    @staticmethod
    def encode(i: int):
        assert i >= 0
        r = []
        while True:
            byte = i & 0x7f
            i = i >> 7
            if i == 0:
                r.append(byte)
                return r
            r.append(0x80 | byte)

    @staticmethod
    def decode(b: list) -> int:
        r = 0
        for i, v in enumerate(b):
            print(f'i={i} e={v}')
            r = r + ((v & 0x7f) << (i * 7))
        return r

有符号数

有符号数分成了正数和负数，在计算机的存储中都是以补码存储，正数和上述无符号数一样的处理，负数的处理会有些区别，以-10000为例说明，

编码过程：

二进制补码	11111111 11111111 11111100 00011000（可以看出最高两字节都是符号扩展的1）
以7bits为整体	1111 1111111 1111111 1111000 0011000
添加标识信息组合新的字节(从后往前，即低bits到高bits）	01111000 10011000（此处结束条件不像上面那么明显，若前面和该7bits的最高位都为1时停止）
LEB128则为	0x98 0x78

解码过程：

LEB128	0x98 0x78
二进制形式	10011000 01111000
去掉标识信息	0011000 1111000 (若最后一个字节中7bits的最高位为1，则前面需要符号扩展都添加1）
组合结果	11111111 11111111 1111100 00011000 (-10000)

Python 代码实现

class _I:
    @staticmethod
    def encode(i: int):
        r = []
        while True:
            byte = i & 0x7f
            i = i >> 7
            if (i == 0 and byte & 0x40 == 0) or (i == -1 and byte & 0x40 != 0):
                r.append(byte)
                return r
            r.append(0x80 | byte)

    @staticmethod
    def decode(b: list) -> int:
        r = 0
        for i, e in enumerate(b):
            r = r + ((e & 0x7f) << (i * 7))
        if e & 0x40 != 0:
            r |= - (1 << (i * 7) + 7)
        return r