摘  要： 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.