LEB128相关知识
介绍
LEB128(little endian base 128)是一种变长的整数压缩编码形式，它是出自于DWARF debug file format。在Android的Dalvik Executable format中使用该编码用于表示32位整数。由于32位整数占用固定的4个字节，可能大多数整数并不需要4个字节，最高几个字节可能为0（正数）或者为1（负数），该编码就是不保存最高位的这些字节。
原理
LEB128的表现形式都是一样的，如下面表格所示，由于是little endian，因此是从低字节到高字节。每个字节中的最高bit是标识信息，1表示还有后续字节，0表示结束，后面7bits是有效数据。将多个字节的该7bits从低到高组合起来就是所表示的整数。
LEB128分成有符号数和无符号数两种分别进行处理，不过，只是在编码和解码过程有些不同。
| 低地址 | +1 | +2 | +3 | +4 |
|---|---|---|---|---|
| 0 xxxxxxx | ||||
| 1 xxxxxxx | 0 xxxxxxx | |||
| 1 xxxxxxx | 1 xxxxxxx | 0 xxxxxxx | ||
| 1 xxxxxxx | 1 xxxxxxx | 1 xxxxxxx | 0 xxxxxxx | |
| 1 xxxxxxx | 1 xxxxxxx | 1 xxxxxxx | 1 xxxxxxx | 0 xxxxxxx |
无符号整数
将无符号整数写成二进制形式，从低位到高位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） |
编码代码为：
void EncodeULEB128(unsigned int value, unsigned char *leb128_buffer)
{
int pos = 0;
while (value != 0) {
leb128_buffer[pos++] = value & 0x7F | 0x80; //每个字节标识信息都设为1
value >>= 7;
}
if (pos > 0)
leb128_buffer[pos-1] &= 0x7F; //将最后一个字节的标识信息设为0
}解码代码为：
void DecodeULEB128(unsigned char *leb128_buffer, unsigned int *value)
{
int pos = 0;
int offset = 0;
while (buffer[pos] != 0) {
*value |= ( (buffer[pos] & 0x7F) << offset ); //从低到高将 bits 合并到一起
offset += 7;
if (buffer[pos] & 0x80 == 0)
break;
pos += 1;
}
}有符号数
有符号数分成了正数和负数，在计算机的存储中都是以补码存储，正数和上述无符号数一样的处理，负数的处理会有些区别，以-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) |
编码代码为：
void EncodeLEB128(int value, unsigned char *buffer)
{
int pos = 0;
int more = 1;
while (more) {
unsigned char byte = value & 0x7F;
value >>= 7;
if ( ((value == 0) && (byte & 0x40) == 0) || //正数
((value == -1) && (byte & 0x40) != 0) ) //负数
more = 0;
if (more != 0)
byte != 0x80;
buffer[pos++] = byte;
}
}编码代码为：
void DecodeLEB128(unsigned char *buffer, int *value)
{
int pos = 0;
int offset = 0;
unsigned char byte = buffer[pos++];
while (byte >= 0x80) {
*value |= (byte & 0x7f) << offset;
offset += 7;
byte = buffer[pos++];
}
if (byte & 0x40)
*value |= -(1 << offset);
}总结
LEB128的理解难点是在有符号数上，编码结束条件不像无符号数那么明显（value等于0），分两种情况：
1. 若为正数，7bits中的最高位为0 并且 value == 0结束，value ==0 表示高字节没有数据，而7bits最高位为0用于表示是正数，用于解码；
2. 若为负数，7bits中的最高位为1 并且 value == -1结束， value == -1表示高字节都是符号扩展出来的1， 7bits最高位为1用于表示是负数，在解码时高位填充1。