摘 要： DWARF格式是一種常用的調(diào)試信息格式,。DWARF格式使用多種方法壓縮存儲調(diào)試信息，以減少對可執(zhí)行文件存儲空間的占用,。DWARF使用變長數(shù)據(jù)LEB128存儲整型數(shù),。DWARF使用相鄰行調(diào)試信息的變化存儲行號調(diào)試信息，并利用該信息的特點(diǎn)將其進(jìn)一步壓縮至1 B,。DWARF把相同的內(nèi)部格式定義數(shù)據(jù)存儲在單獨(dú)的節(jié)區(qū),。DWARF格式定義的這些數(shù)據(jù)壓縮方式值得數(shù)據(jù)壓縮相關(guān)領(lǐng)域?qū)W習(xí)和借鑒。
關(guān)鍵詞： DWARF,；調(diào)試信息,；數(shù)據(jù)壓縮,；LEB128
0 引言
數(shù)據(jù)壓縮是計(jì)算機(jī)領(lǐng)域一項(xiàng)廣泛使用的技術(shù)，在多媒體,、通信,、存儲等領(lǐng)域得到廣泛應(yīng)用[1-3]。數(shù)據(jù)壓縮技術(shù)分為兩大類：無損壓縮和有損壓縮,。無損壓縮指壓縮過程不丟失信息的壓縮方法,，可以由壓縮數(shù)據(jù)完整恢復(fù)壓縮前的數(shù)據(jù),。有損壓縮指壓縮過程丟失部分信息的壓縮方法,，一般應(yīng)用于多媒體領(lǐng)域。常用的無損壓縮方法包括哈夫曼編碼方法,、算術(shù)編碼方法,、基于字典的壓縮方法（如LZ78算法、LZW算法）等,。只要涉及數(shù)據(jù)的存儲,、傳輸，都可應(yīng)用數(shù)據(jù)壓縮方法,。
調(diào)試信息指在可執(zhí)行文件中存儲的關(guān)于源代碼的信息,。調(diào)試信息使程序員可以由程序執(zhí)行狀態(tài)追蹤至其源代碼，也使在源代碼的級別對程序進(jìn)行調(diào)試成為可能,。所以,，調(diào)試信息是源代碼級調(diào)試功能實(shí)現(xiàn)必不可少的重要部分。調(diào)試信息以固定的格式存儲在被調(diào)試可執(zhí)行文件中,，常用的調(diào)試信息格式包括STABS,、COFF、DWARF等,。其中DWARF（Debugging with Attributed Record Formats）格式是最常用的調(diào)試信息格式,，它具有表達(dá)功能豐富、內(nèi)容緊湊等優(yōu)點(diǎn)[4],。DWARF格式有DWARF1,、DWARF2、DWARF3三個版本,，最常見的是DWARF2版本,，本文介紹的內(nèi)容是基于DWARF2格式的。
相比于其他調(diào)試信息格式,，DWARF格式最大的優(yōu)點(diǎn)就是內(nèi)容高度緊湊,。為了減少調(diào)試信息在可執(zhí)行文件中占用的空間，DWARF格式使用各種方法來壓縮調(diào)試信息數(shù)據(jù),。DWARF格式幾乎把調(diào)試信息的可壓縮特點(diǎn)利用到極致,，是存儲空間最小的調(diào)試信息格式,。由DWARF格式可以完整解析得到所有調(diào)試信息，所以DWARF格式使用的數(shù)據(jù)壓縮方法是一種無損數(shù)據(jù)壓縮方法,。
目前,，國內(nèi)幾乎還沒有研究機(jī)構(gòu)對DWARF格式調(diào)試信息進(jìn)行深入研究。本文對DWARF格式中使用的數(shù)據(jù)壓縮方法進(jìn)行了歸納,、總結(jié),、分析，供數(shù)據(jù)壓縮,、調(diào)試信息生成,、分析領(lǐng)域及相關(guān)領(lǐng)域?qū)W習(xí)參考。
1 LEB128數(shù)
LEB128（Little Endian Base 128）數(shù)是一種變長的存儲整數(shù)的數(shù)據(jù)結(jié)構(gòu),，它僅僅存儲整數(shù)的有效位,，可以表示任意范圍內(nèi)的有符號或無符號整型數(shù)。LEB128數(shù)的存儲空間與整數(shù)的有效位成正比,。若整數(shù)的有效位很少,，相對于普通整型數(shù)的存儲方式，LEB128數(shù)可以顯著減小存儲空間,。
一些整數(shù)在大多數(shù)情況下只取很小的值,，可以用1 B存儲。但由于該數(shù)可能取很大的值,，不能將其存儲空間限制為1 B,。若為了存儲個別情況下出現(xiàn)的大值而分配4 B或8 B的空間，大多數(shù)情況下會造成存儲空間的浪費(fèi),。LEB128的優(yōu)點(diǎn)在于其存儲空間是可變的,。若整數(shù)很小，最少1 B即可儲存LEB128數(shù),。若數(shù)字很大,，LEB128數(shù)可以用多個字節(jié)表示。LEB128數(shù)既可以編碼小端存儲的數(shù)據(jù),，也可以編碼大端存儲的數(shù)據(jù),。
有符號數(shù)與無符號數(shù)轉(zhuǎn)化為LEB128數(shù)的過程不同。編碼與解析程序必須知道該LEB128數(shù)是有符號數(shù)還是無符號數(shù),，否則就會編碼或解析錯誤,。
把一個整數(shù)編碼為LEB128數(shù)的過程抽象描述如下：
（1）把該數(shù)的二進(jìn)制有效位分割為若干段,，每段7 bit,；
（2）把這些7 bit的數(shù)放入LEB128的各字節(jié)中,，最高一位補(bǔ)1,；
?。?）位于有效位最高位的7 bit，最高一位補(bǔ)0,，標(biāo)志數(shù)的結(jié)束,。
若整數(shù)的二進(jìn)制有效數(shù)位小于7 bit，只需1 B的LEB128數(shù)即可表示,。對于調(diào)試信息,，大多數(shù)情況下整數(shù)的取值范圍在-128和255之間，可以用1 B的有符號或無符號LEB128數(shù)表示,。相對于正常的整數(shù)存儲方式,，節(jié)省了3/4的存儲空間。
圖1,、圖2分別為把無符號整數(shù)和有符號整數(shù)編碼為LEB128數(shù)的算法流程圖,。
2 行號調(diào)試信息壓縮方法
2.1 行號調(diào)試信息簡介
行號調(diào)試信息是最基本的調(diào)試信息，它描述了源代碼中每一行代碼經(jīng)編譯鏈接后定位到的程序地址,。它可以幫助調(diào)試系統(tǒng)由程序地址定位到源代碼中的位置，也可以由源代碼中的位置定位到程序地址,。插入斷點(diǎn),、單步調(diào)試、暫停等調(diào)試功能都需要行號調(diào)試信息,。常規(guī)的調(diào)試信息存儲方式把行號調(diào)試信息存儲為“行號,，程序地址”對，每對記錄源代碼中一行代碼的行號和程序地址,。例如,，STABS格式調(diào)試信息以“行”為單位存儲行號調(diào)試信息，每個“行號,，程序地址”對占用相等的存儲空間,，擁有相同的格式[5]。該存儲方法的優(yōu)點(diǎn)是簡單易分析,，缺點(diǎn)是占用空間較大,。一般行號需要使用4 B存儲，程序地址也需要4 B存儲,，一個“行號,，程序地址”對至少需要8 B存儲。實(shí)際上,，STABS格式需要15 B來存儲一個“行號,，程序地址”對。
一般的源代碼中,，兩相鄰行源代碼的行號差距不會太大,，兩行源代碼的程序地址也不會相差太大,。如果使用相鄰行的行號差和程序地址差來記錄行號調(diào)試信息，并通過某種方式把這個信息壓縮存儲,，將會大大減少行號調(diào)試信息的存儲空間,。
2．2 DWARF格式行號調(diào)試信息簡介
DWARF格式利用相鄰行的行號調(diào)試信息相差不大的特點(diǎn)，使用與傳統(tǒng)方法完全不同的方式存儲行號調(diào)試信息,。DWARF格式的行號調(diào)試信息存儲于.debug_line節(jié)區(qū),。DWARF格式首先定義了一個狀態(tài)機(jī)，該狀態(tài)機(jī)包含文件名,、行號,、程序地址等信息。DWARF格式還定義了一些精簡的操作碼,，這些操作碼可以改變該狀態(tài)機(jī)的狀態(tài),，每存儲一個操作碼，就相當(dāng)于存儲了一個“行號,，程序地址”對,。
DWARF格式定義的操作碼分為三類，可以對行號調(diào)試信息狀態(tài)機(jī)進(jìn)行全面的操作,。表1分別介紹這三類操作碼,。
三類操作碼中，最常用的是特殊操作碼,，其存儲空間固定為1 B,，可以改變行號調(diào)試信息狀態(tài)機(jī)中的行號和程序地址，并生成一個“行號,，程序地址”對調(diào)試信息,。
標(biāo)準(zhǔn)操作碼可以對狀態(tài)機(jī)執(zhí)行一些特殊操作碼無法執(zhí)行的命令，如設(shè)置程序地址,、改變文件名等,。標(biāo)準(zhǔn)操作碼的范圍為從1開始的一段連續(xù)整數(shù)。例如,，DWARF2格式預(yù)定義了9種標(biāo)準(zhǔn)操作碼,，其操作碼編號分別為1、2,、3…8,、9。調(diào)試信息生成程序可以自定義標(biāo)準(zhǔn)操作碼,。
擴(kuò)展操作碼用來執(zhí)行一些標(biāo)準(zhǔn)操作碼也無法描述的命令,。
2．3 特殊操作碼的數(shù)據(jù)壓縮機(jī)制
特殊操作碼用1 B記錄行號改變量和程序地址改變量，并且還可以由該字節(jié)準(zhǔn)確地計(jì)算得到行號改變量和程序地址改變量的原值。
特殊操作碼的計(jì)算可以用下式抽象描述：
特殊操作碼=程序地址改變量×行號改變量范圍+行號改變量（1）
其中,，行號改變量范圍為行號改變量的取值范圍,，行號改變量應(yīng)取大于或等于0并小于行號改變量范圍的值。
由特殊操作碼計(jì)算得到行號改變量和程序地址改變量的過程可以抽象描述為：
行號改變量=特殊操作碼%行號改變量范圍（2）
程序地址改變量=特殊操作碼/行號改變量范圍（3）
由取模算術(shù)運(yùn)算的特點(diǎn)可知,，由一個特殊操作碼可以確定唯一的行號改變量和程序地址改變量,，而且這個行號改變量和程序地址改變量就是計(jì)算該特殊操作碼的輸入。
在DWARF格式的實(shí)際定義中,，根據(jù)行號調(diào)試信息的特點(diǎn)對上述公式進(jìn)行了修正,。行號調(diào)試信息的特點(diǎn)包括：
（1）行號改變量可能是負(fù)數(shù),。對于高級語言（如C語言）,，其一行源代碼產(chǎn)生的程序可能分散在若干個位置，如for,、while循環(huán)語句,。這樣的一行源代碼會產(chǎn)生若干條行號調(diào)試信息，其中混夾著其他行源代碼的行號調(diào)試信息,。所以,，相鄰的行號調(diào)試信息的行號改變量可能是負(fù)數(shù)。而由取模算術(shù)運(yùn)算的特點(diǎn)可知,，要準(zhǔn)確由特殊操作碼解壓縮得到行號調(diào)試信息,，行號改變必須為正數(shù)。所以,，式（1）中“行號改變量”應(yīng)改為行號實(shí)際改變量與行號改變量最小可能值之差。
?。?）程序地址改變量一定是最小指令長度的倍數(shù),。程序段是由指令組成的，所以程序地址改變量實(shí)際上是本行源代碼生成的指令長度之和,。而指令的長度有可能并不為1,，例如，對某些機(jī)器,，其指令長度只能為4,，其程序地址改變量一定是4的倍數(shù)。所以,，為了擴(kuò)大特殊操作碼可描述的程序地址改變范圍,，上述公式中的“程序地址改變量”應(yīng)改為程序地址實(shí)際改變量除以最小指令長度。
?。?）特殊操作碼的取值范圍受限制,。操作碼的第一個字節(jié)必須可以區(qū)分該操作碼的種類，否則調(diào)試信息解析程序無法判斷第一個字節(jié)是特殊操作碼還是其他兩類操作碼,。所以特殊操作碼的取值應(yīng)大于標(biāo)準(zhǔn)操作碼最大編號,，并小于或等于255,。例如，若標(biāo)準(zhǔn)操作碼編號的取值范圍為1~9,，則特殊操作碼的最小可能值為10,。所以，由上述公式計(jì)算得到的特殊操作碼應(yīng)加上特殊操作碼的最小可能值,。
根據(jù)行號調(diào)試信息的以上特點(diǎn),，DWARF2中定義的實(shí)際特殊操作碼計(jì)算公式如下：
特殊操作碼=（行號改變量-行號改變量最小值）+（行號改變范圍×程序地址改變量/最小指令長度）+特殊操作碼最小值（4）
由特殊操作碼得到行號改變量和程序地址改變量的公式如下：
行號改變量=（特殊操作碼-特殊操作碼最小值）%行號改變范圍+行號改變量最小值（5）
程序地址改變量=（特殊操作碼-特殊操作碼最小值）/行號改變范圍×最小指令長度（6）
可見，式（4）,、（5）,、（6）與式（1）、（2）,、（3）本質(zhì)上是一樣的,，只是在數(shù)據(jù)壓縮前后進(jìn)行了一些算術(shù)處理，它們都可以由特殊操作碼準(zhǔn)確得到行號調(diào)試信息,。若一個行號調(diào)試信息經(jīng)過式（4）計(jì)算后超過特殊操作碼的取值范圍,，則說明特殊操作碼無法描述該行號調(diào)試信息?？梢允褂脴?biāo)準(zhǔn)操作碼或擴(kuò)展操作碼來描述特殊操作碼不能描述的行號調(diào)試信息,。
式（4）中的行號改變量最小值、行號改變范圍,、最小指令長度,、特殊操作碼最小值都可以在解析行號調(diào)試信息之前從.debug_line節(jié)區(qū)獲取。其中“行號改變范圍”并不是一個源文件中行號改變量的實(shí)際最大范圍,，而是一個適中的可以包含大部分行號改變范圍的值,。使用太大的“行號改變范圍”雖然能夠增加特殊操作碼來描述的行號改變量，但是也會減少特殊操作碼可以描述的程序地址改變量,。對于大于“行號改變范圍”的行號改變量,，可以使用標(biāo)準(zhǔn)操作碼來存儲。
若式（4）中的“行號改變量最小值”,、“行號改變范圍”選取得當(dāng),，絕大多數(shù)行號信息都可以通過特殊操作碼描述。實(shí)際經(jīng)驗(yàn)表明,，一個代碼書寫規(guī)范的C語言文件,，80%以上的行號調(diào)試信息都可以通過特殊操作碼來記錄。一個特殊操作碼占用1 B,，相比STABS格式,，至少可以節(jié)省90%以上的存儲空間。
3 節(jié)點(diǎn)縮略信息
DWARF格式中，除行號調(diào)試信息外,，其他調(diào)試信息主要以節(jié)點(diǎn)的形式存放在.debug_info節(jié)區(qū)中,。節(jié)點(diǎn)可以描述源文件、函數(shù),、變量,、類型等調(diào)試信息。調(diào)試信息節(jié)點(diǎn)之間存在父子節(jié)點(diǎn)或兄弟節(jié)點(diǎn)的關(guān)系,。一個源文件的所有調(diào)試信息節(jié)點(diǎn)構(gòu)成一個調(diào)試信息節(jié)點(diǎn)樹,，描述源文件本身調(diào)試信息的節(jié)點(diǎn)是這個樹的根節(jié)點(diǎn)。節(jié)點(diǎn)具有各種屬性,，調(diào)試信息一般存儲為節(jié)點(diǎn)的屬性值,。節(jié)點(diǎn)可以有多種類型，屬性也有多種類型,。一種類型的節(jié)點(diǎn)具有的屬性類型是不固定的,，由調(diào)試信息生成程序定義。表2為常見的節(jié)點(diǎn)類型與可能的屬性類型,。
同一種屬性可以存儲為不同的格式,。節(jié)點(diǎn)屬性的格式也是不固定的，由調(diào)試信息生成程序定義,。表3為常見的節(jié)點(diǎn)屬性格式,。
按照常規(guī)的存儲方法，.debug_info中存儲一個節(jié)點(diǎn)的調(diào)試信息時,，至少需要存儲如下幾類信息：
?。?）節(jié)點(diǎn)類型；
?。?）節(jié)點(diǎn)是否有子節(jié)點(diǎn),；
（3）節(jié)點(diǎn)的所有屬性的類型,；
（4）節(jié)點(diǎn)的各個屬性的格式,。
這些信息稱為節(jié)點(diǎn)的縮略信息,。根據(jù)DWARF格式的定義，存儲節(jié)點(diǎn)類型,、屬性類型,、屬性格式至少各需要1 B。若一個節(jié)點(diǎn)具有N個屬性,，至少需要2+2×N個字節(jié)來存儲節(jié)點(diǎn)縮略信息,。
對大多數(shù)程序來說，其多數(shù)調(diào)試信息節(jié)點(diǎn)的縮略信息是相同的。例如,，若一個可執(zhí)行文件由若干個源文件編譯而成,，則其包含的若干個節(jié)點(diǎn)都是源文件調(diào)試信息節(jié)點(diǎn)。若一個源文件中有若干個函數(shù),，則該源文件調(diào)試信息節(jié)點(diǎn)的若干個子節(jié)點(diǎn)都是函數(shù)調(diào)試信息節(jié)點(diǎn)類型,。若函數(shù)中包含若干個局部變量，則該函數(shù)調(diào)試信息節(jié)點(diǎn)的若干個子節(jié)點(diǎn)都是變量類型,。DWARF格式利用調(diào)試信息的這個特點(diǎn),，把節(jié)點(diǎn)的縮略信息抽取出來，放到.debug_abbrev節(jié)區(qū)中,。在.debug_info節(jié)區(qū)中只需要引用節(jié)點(diǎn)的縮略信息,，并存儲節(jié)點(diǎn)屬性的值即可。圖3為一個源文件節(jié)點(diǎn)類型在.debug_abbrev節(jié)區(qū)中存儲的縮略信息內(nèi)容示意,，圖4為這個節(jié)點(diǎn)的值在.debug_info節(jié)區(qū)中的存儲內(nèi)容示意,。
通過這種方法，可以節(jié)省重復(fù)類型節(jié)點(diǎn)縮略信息的存儲空間,。例如,，若源文件中包括L個變量，一般每個變量調(diào)試信息節(jié)點(diǎn)有5個屬性,，這些變量的節(jié)點(diǎn)縮略信息只需存儲一個即可,，可以節(jié)省約10×L字節(jié)存儲空間。顯然,，編譯生成可執(zhí)行文件的源文件越多,、源文件中的代碼量越多，通過這種方法節(jié)省的空間就越多,。
4 結(jié)論
數(shù)據(jù)壓縮技術(shù)是計(jì)算機(jī)領(lǐng)域廣泛使用的技術(shù),。只要存在數(shù)據(jù)的存儲，就可應(yīng)用數(shù)據(jù)壓縮技術(shù),。DWARF格式是一種常用的調(diào)試信息格式,，它把調(diào)試信息存儲于可執(zhí)行文件中。為了減少調(diào)試信息占用的可執(zhí)行文件存儲空間,，DWARF格式使用了各種方法來壓縮數(shù)據(jù),。由于DWARF格式可以完整地還原調(diào)試信息，因此這些數(shù)據(jù)壓縮方法是無損壓縮方法,。本文介紹的DWARF格式數(shù)據(jù)壓縮方法對數(shù)據(jù)壓縮領(lǐng)域有重要的借鑒意義,，對調(diào)試信息生成、分析領(lǐng)域也有重要的參考價值,。
參考文獻(xiàn)
[1] 鄭翠芳.幾種常用無損數(shù)據(jù)壓縮算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,，2011,，21（9）：73-76.
[2] 曾玲，饒志宏.幾種數(shù)據(jù)壓縮算法的比較[J].通信技術(shù),，2002（9）：12-15.
[3] 袁玫,，袁文.數(shù)據(jù)壓縮技術(shù)及其應(yīng)用[M].北京：電子工業(yè)出版社，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.