摘 要：DWARF格式是一种常用的调试信息格式。DWARF格式使用多种方法压缩存储调试信息，以减少对可执行文件存储空间的占用。DWARF使用变长数据LEB128存储整型数。DWARF使用相邻行调试信息的变化存储行号调试信息，并利用该信息的特点将其进一步压缩至1 B。DWARF把相同的内部格式定义数据存储在单独的节区。DWARF格式定义的这些数据压缩方式值得数据压缩相关领域学习和借鉴。
关键词： DWARF；调试信息；数据压缩；LEB128
0 引言
数据压缩是计算机领域一项广泛使用的技术，在多媒体、通信、存储等领域得到广泛应用[1-3]。数据压缩技术分为两大类：无损压缩和有损压缩。无损压缩指压缩过程不丢失信息的压缩方法，可以由压缩数据完整恢复压缩前的数据。有损压缩指压缩过程丢失部分信息的压缩方法，一般应用于多媒体领域。常用的无损压缩方法包括哈夫曼编码方法、算术编码方法、基于字典的压缩方法（如LZ78算法、LZW算法）等。只要涉及数据的存储、传输，都可应用数据压缩方法。
调试信息指在可执行文件中存储的关于源代码的信息。调试信息使程序员可以由程序执行状态追踪至其源代码，也使在源代码的级别对程序进行调试成为可能。所以，调试信息是源代码级调试功能实现必不可少的重要部分。调试信息以固定的格式存储在被调试可执行文件中，常用的调试信息格式包括STABS、COFF、DWARF等。其中DWARF（Debugging with Attributed Record Formats）格式是最常用的调试信息格式，它具有表达功能丰富、内容紧凑等优点[4]。DWARF格式有DWARF1、DWARF2、DWARF3三个版本，最常见的是DWARF2版本，本文介绍的内容是基于DWARF2格式的。
相比于其他调试信息格式，DWARF格式最大的优点就是内容高度紧凑。为了减少调试信息在可执行文件中占用的空间，DWARF格式使用各种方法来压缩调试信息数据。DWARF格式几乎把调试信息的可压缩特点利用到极致，是存储空间最小的调试信息格式。由DWARF格式可以完整解析得到所有调试信息，所以DWARF格式使用的数据压缩方法是一种无损数据压缩方法。
目前，国内几乎还没有研究机构对DWARF格式调试信息进行深入研究。本文对DWARF格式中使用的数据压缩方法进行了归纳、总结、分析，供数据压缩、调试信息生成、分析领域及相关领域学习参考。
1 LEB128数
LEB128（Little Endian Base 128）数是一种变长的存储整数的数据结构，它仅仅存储整数的有效位，可以表示任意范围内的有符号或无符号整型数。LEB128数的存储空间与整数的有效位成正比。若整数的有效位很少，相对于普通整型数的存储方式，LEB128数可以显著减小存储空间。
一些整数在大多数情况下只取很小的值，可以用1 B存储。但由于该数可能取很大的值，不能将其存储空间限制为1 B。若为了存储个别情况下出现的大值而分配4 B或8 B的空间，大多数情况下会造成存储空间的浪费。LEB128的优点在于其存储空间是可变的。若整数很小，最少1 B即可储存LEB128数。若数字很大，LEB128数可以用多个字节表示。LEB128数既可以编码小端存储的数据，也可以编码大端存储的数据。
有符号数与无符号数转化为LEB128数的过程不同。编码与解析程序必须知道该LEB128数是有符号数还是无符号数，否则就会编码或解析错误。
把一个整数编码为LEB128数的过程抽象描述如下：
（1）把该数的二进制有效位分割为若干段，每段7 bit；
（2）把这些7 bit的数放入LEB128的各字节中，最高一位补1；
（3）位于有效位最高位的7 bit，最高一位补0，标志数的结束。
若整数的二进制有效数位小于7 bit，只需1 B的LEB128数即可表示。对于调试信息，大多数情况下整数的取值范围在-128和255之间，可以用1 B的有符号或无符号LEB128数表示。相对于正常的整数存储方式，节省了3/4的存储空间。
图1、图2分别为把无符号整数和有符号整数编码为LEB128数的算法流程图。
2 行号调试信息压缩方法
2.1 行号调试信息简介
行号调试信息是最基本的调试信息，它描述了源代码中每一行代码经编译链接后定位到的程序地址。它可以帮助调试系统由程序地址定位到源代码中的位置，也可以由源代码中的位置定位到程序地址。插入断点、单步调试、暂停等调试功能都需要行号调试信息。常规的调试信息存储方式把行号调试信息存储为“行号，程序地址”对，每对记录源代码中一行代码的行号和程序地址。例如，STABS格式调试信息以“行”为单位存储行号调试信息，每个“行号，程序地址”对占用相等的存储空间，拥有相同的格式[5]。该存储方法的优点是简单易分析，缺点是占用空间较大。一般行号需要使用4 B存储，程序地址也需要4 B存储，一个“行号，程序地址”对至少需要8 B存储。实际上，STABS格式需要15 B来存储一个“行号，程序地址”对。
一般的源代码中，两相邻行源代码的行号差距不会太大，两行源代码的程序地址也不会相差太大。如果使用相邻行的行号差和程序地址差来记录行号调试信息，并通过某种方式把这个信息压缩存储，将会大大减少行号调试信息的存储空间。
2．2 DWARF格式行号调试信息简介
DWARF格式利用相邻行的行号调试信息相差不大的特点，使用与传统方法完全不同的方式存储行号调试信息。DWARF格式的行号调试信息存储于.debug_line节区。DWARF格式首先定义了一个状态机，该状态机包含文件名、行号、程序地址等信息。DWARF格式还定义了一些精简的操作码，这些操作码可以改变该状态机的状态，每存储一个操作码，就相当于存储了一个“行号，程序地址”对。
DWARF格式定义的操作码分为三类，可以对行号调试信息状态机进行全面的操作。表1分别介绍这三类操作码。
三类操作码中，最常用的是特殊操作码，其存储空间固定为1 B，可以改变行号调试信息状态机中的行号和程序地址，并生成一个“行号，程序地址”对调试信息。
标准操作码可以对状态机执行一些特殊操作码无法执行的命令，如设置程序地址、改变文件名等。标准操作码的范围为从1开始的一段连续整数。例如，DWARF2格式预定义了9种标准操作码，其操作码编号分别为1、2、3…8、9。调试信息生成程序可以自定义标准操作码。
扩展操作码用来执行一些标准操作码也无法描述的命令。
2．3 特殊操作码的数据压缩机制
特殊操作码用1 B记录行号改变量和程序地址改变量，并且还可以由该字节准确地计算得到行号改变量和程序地址改变量的原值。
特殊操作码的计算可以用下式抽象描述：
特殊操作码=程序地址改变量×行号改变量范围+行号改变量（1）
其中，行号改变量范围为行号改变量的取值范围，行号改变量应取大于或等于0并小于行号改变量范围的值。
由特殊操作码计算得到行号改变量和程序地址改变量的过程可以抽象描述为：
行号改变量=特殊操作码%行号改变量范围（2）
程序地址改变量=特殊操作码/行号改变量范围（3）
由取模算术运算的特点可知，由一个特殊操作码可以确定唯一的行号改变量和程序地址改变量，而且这个行号改变量和程序地址改变量就是计算该特殊操作码的输入。
在DWARF格式的实际定义中，根据行号调试信息的特点对上述公式进行了修正。行号调试信息的特点包括：
（1）行号改变量可能是负数。对于高级语言（如C语言），其一行源代码产生的程序可能分散在若干个位置，如for、while循环语句。这样的一行源代码会产生若干条行号调试信息，其中混夹着其他行源代码的行号调试信息。所以，相邻的行号调试信息的行号改变量可能是负数。而由取模算术运算的特点可知，要准确由特殊操作码解压缩得到行号调试信息，行号改变必须为正数。所以，式（1）中“行号改变量”应改为行号实际改变量与行号改变量最小可能值之差。
（2）程序地址改变量一定是最小指令长度的倍数。程序段是由指令组成的，所以程序地址改变量实际上是本行源代码生成的指令长度之和。而指令的长度有可能并不为1，例如，对某些机器，其指令长度只能为4，其程序地址改变量一定是4的倍数。所以，为了扩大特殊操作码可描述的程序地址改变范围，上述公式中的“程序地址改变量”应改为程序地址实际改变量除以最小指令长度。
（3）特殊操作码的取值范围受限制。操作码的第一个字节必须可以区分该操作码的种类，否则调试信息解析程序无法判断第一个字节是特殊操作码还是其他两类操作码。所以特殊操作码的取值应大于标准操作码最大编号，并小于或等于255。例如，若标准操作码编号的取值范围为1~9，则特殊操作码的最小可能值为10。所以，由上述公式计算得到的特殊操作码应加上特殊操作码的最小可能值。
根据行号调试信息的以上特点，DWARF2中定义的实际特殊操作码计算公式如下：
特殊操作码=（行号改变量-行号改变量最小值）+（行号改变范围×程序地址改变量/最小指令长度）+特殊操作码最小值（4）
由特殊操作码得到行号改变量和程序地址改变量的公式如下：
行号改变量=（特殊操作码-特殊操作码最小值）%行号改变范围+行号改变量最小值（5）
程序地址改变量=（特殊操作码-特殊操作码最小值）/行号改变范围×最小指令长度（6）
可见，式（4）、（5）、（6）与式（1）、（2）、（3）本质上是一样的，只是在数据压缩前后进行了一些算术处理，它们都可以由特殊操作码准确得到行号调试信息。若一个行号调试信息经过式（4）计算后超过特殊操作码的取值范围，则说明特殊操作码无法描述该行号调试信息。可以使用标准操作码或扩展操作码来描述特殊操作码不能描述的行号调试信息。
式（4）中的行号改变量最小值、行号改变范围、最小指令长度、特殊操作码最小值都可以在解析行号调试信息之前从.debug_line节区获取。其中“行号改变范围”并不是一个源文件中行号改变量的实际最大范围，而是一个适中的可以包含大部分行号改变范围的值。使用太大的“行号改变范围”虽然能够增加特殊操作码来描述的行号改变量，但是也会减少特殊操作码可以描述的程序地址改变量。对于大于“行号改变范围”的行号改变量，可以使用标准操作码来存储。
若式（4）中的“行号改变量最小值”、“行号改变范围”选取得当，绝大多数行号信息都可以通过特殊操作码描述。实际经验表明，一个代码书写规范的C语言文件，80%以上的行号调试信息都可以通过特殊操作码来记录。一个特殊操作码占用1 B，相比STABS格式，至少可以节省90%以上的存储空间。
3 节点缩略信息
DWARF格式中，除行号调试信息外，其他调试信息主要以节点的形式存放在.debug_info节区中。节点可以描述源文件、函数、变量、类型等调试信息。调试信息节点之间存在父子节点或兄弟节点的关系。一个源文件的所有调试信息节点构成一个调试信息节点树，描述源文件本身调试信息的节点是这个树的根节点。节点具有各种属性，调试信息一般存储为节点的属性值。节点可以有多种类型，属性也有多种类型。一种类型的节点具有的属性类型是不固定的，由调试信息生成程序定义。表2为常见的节点类型与可能的属性类型。
同一种属性可以存储为不同的格式。节点属性的格式也是不固定的，由调试信息生成程序定义。表3为常见的节点属性格式。
按照常规的存储方法，.debug_info中存储一个节点的调试信息时，至少需要存储如下几类信息：
（1）节点类型；
（2）节点是否有子节点；
（3）节点的所有属性的类型；
（4）节点的各个属性的格式。
这些信息称为节点的缩略信息。根据DWARF格式的定义，存储节点类型、属性类型、属性格式至少各需要1 B。若一个节点具有N个属性，至少需要2+2×N个字节来存储节点缩略信息。
对大多数程序来说，其多数调试信息节点的缩略信息是相同的。例如，若一个可执行文件由若干个源文件编译而成，则其包含的若干个节点都是源文件调试信息节点。若一个源文件中有若干个函数，则该源文件调试信息节点的若干个子节点都是函数调试信息节点类型。若函数中包含若干个局部变量，则该函数调试信息节点的若干个子节点都是变量类型。DWARF格式利用调试信息的这个特点，把节点的缩略信息抽取出来，放到.debug_abbrev节区中。在.debug_info节区中只需要引用节点的缩略信息，并存储节点属性的值即可。图3为一个源文件节点类型在.debug_abbrev节区中存储的缩略信息内容示意，图4为这个节点的值在.debug_info节区中的存储内容示意。
通过这种方法，可以节省重复类型节点缩略信息的存储空间。例如，若源文件中包括L个变量，一般每个变量调试信息节点有5个属性，这些变量的节点缩略信息只需存储一个即可，可以节省约10×L字节存储空间。显然，编译生成可执行文件的源文件越多、源文件中的代码量越多，通过这种方法节省的空间就越多。
4 结论
数据压缩技术是计算机领域广泛使用的技术。只要存在数据的存储，就可应用数据压缩技术。DWARF格式是一种常用的调试信息格式，它把调试信息存储于可执行文件中。为了减少调试信息占用的可执行文件存储空间，DWARF格式使用了各种方法来压缩数据。由于DWARF格式可以完整地还原调试信息，因此这些数据压缩方法是无损压缩方法。本文介绍的DWARF格式数据压缩方法对数据压缩领域有重要的借鉴意义，对调试信息生成、分析领域也有重要的参考价值。
参考文献
[1] 郑翠芳.几种常用无损数据压缩算法研究[J].计算机技术与发展，2011，21（9）：73-76.
[2] 曾玲，饶志宏.几种数据压缩算法的比较[J].通信技术，2002（9）：12-15.
[3] 袁玫，袁文.数据压缩技术及其应用[M].北京：电子工业出版社，1994.
[4] Unix International Programming Languages SIG. DWARF debugging information format[S]. UNIX International， 1993.
[5] MENAPACE J， KINGDON J， MacKenzie D. The “stabs” debug format[S]. Free Software Foundation， 2003.