Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1139852
  • 博文数量: 196
  • 博客积分: 4141
  • 博客等级: 中将
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2009-03-21 20:04
文章存档

2019年(31)

2016年(1)

2014年(16)

2011年(8)

2010年(25)

2009年(115)

分类: C/C++

2010-05-26 14:21:39

在 Dwarf 文档中随处可见 LEB128( Little Endian Base 128 ) 这个数据格式。它是一个变长的数据格式(所占的字节数可变)其分为 unsinged LEB128 和 signed LEB128 。

  I.Encoding unsigned LEB128

    算法是这样的(Dwarf-2.0.0.pdf Appendix 4 99页)

do { byte = low order 7 bits of value; value >>= 7; if (value != 0) /* more bytes to come */ set high order bit of byte; emit byte; } while (value != 0);

Input:unsigned int  a = 12857(0x3239)

output: unsigned LEB128 result

logic:

  1>. 0x3239转为二进制

a = 0000 0000   0000 0000   0011 0010   0011  1001

  2>. 从最低位截取7bit(灰背 景),组成新的字节

byte0  = 0x39

  3>. 原数据高位补7个0

a = 0000 000 0  0000 0000  0000 0000  0110 0100

 4>.if (a != 0),byte |= 0x80

byte0 = 0x39 + 0x80 = 0xB9

  5>.重复3>,4>,直到a == 0

byte1  = 0x64

a = 0000 000 0  0000 00 00  0000 0000  0000 0000

最终得到结果为:B9 64

II.Decoding unsigned LEB128

算法(Dwarf- 2.0.0.pdf Appendix 4 99页)

result = 0; shift = 0; size = no. of bits in signed integer; while(true) { byte = next byte in input; result |= (low ord

Input:byte* src;  B9 64

output:unsigned int result;

logic

  0>.

x = 0;

  1>.取下一个byte:

bytex = 0xB9

  2>.取其低7位,并放到到第x个7位的位置

result |= (bytex & 0x7F) << (7*x);

  3>.if (!(bytex | 0x80)),继续1>,否则结束。

 byte0  = 0xB9;

result = 0x39;

byte0 & 0x80 == 1

byte1 = 0x64

result = 0x3239

III.LEB128的特点

    1.一个LEB128类型的数据占有的byte数不确定

    2.一个LEB128以字节中最高位是否为0来表示字节流有没有结束。

    3.一个LEB128可能通过编解码与一个unsigned int互相转换。

IV.参考资料:

   1.dwarf-2.0.0.pdf 7.6节 和 Appendix 4

   2.libdwarf Dwarf_leb.c中有LEB128的解码函数。
阅读(7235) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~