LEB128相关知识

时间:2024-04-21 10:05:22

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。

参考

https://en.wikipedia.org/wiki/LEB128

http://llvm.org/docs/doxygen/html/LEB128_8h_source.html