一種基于GZIP 的壓縮與高效解壓系統

李 博，袁興峰，李 隆

（合肥工業大學電子科學與應用物理學院，安徽合肥 230009）

在一些嵌入式系統中，系統的正常工作需要大量的數據支持，數據量的大小和數據的傳遞速度直接影響了工作系統的成本和性能。采用數據壓縮的方法可以很好地緩解數據量巨大給嵌入式系統帶來的壓力。但是，在一般壓縮與解壓系統中無法滿足對任意段數據的解壓和提取[1-3]，即如果需要壓縮包中的某段數據時，必須對所有數據進行解壓[4-6]。這種做法將降低解壓效率和系統性能。文中提出了一種優化的壓縮與解壓系統，提高了解壓的效率，降低了數據傳輸對帶寬的壓力。

1 系統構架

該文完成的是一種軟件壓縮硬解壓的數據壓縮與解壓系統。數據壓縮是利用壓縮軟件完成的，解壓是在FPGA 端離線進行的，系統并不需要關注軟件壓縮時的耗時，如液晶儀表顯示系統[7-8]和識別系統[9-11]等。在軟件壓縮端，需要關注的是壓縮數據和校驗碼生成的正確性。在硬件解壓端，需要關注解壓的正確性、速度和效率。系統框架圖如圖1 所示。

圖1 系統構架

據圖1 可以看到數據首先通過PC 端進行軟件壓縮，在壓縮過程中保證數據的準確性。數據壓縮完成后，將壓縮后的數據燒錄至嵌入式系統中的存儲器件如flash 等。至此，數據完成了壓縮與存儲。之后的操作脫離PC 端，數據的解壓操作將在嵌入式系統中進行，系統運行步驟如下所示：

1）嵌入式系統發出指令和地址到硬件數據解壓模塊；

2）硬件解壓模塊接收指令和地址，將地址轉化為壓縮后數據存儲的地址；

3）硬件解壓模塊根據指令和轉化后地址從存儲器件中取出壓縮數據；

4）硬件解壓模塊接收從存儲器件返回的壓縮數據，并進行解壓；

5）硬件解壓模塊將解壓后的數據輸出到嵌入式系統，供其使用。

經過上述流程，可在嵌入式系統中對壓縮后的存儲數據有效地進行解壓。

2 基于軟件的數據壓縮處理

2.1 DEFLATE壓縮算法

DEFLATE 壓縮算法是一種無損壓縮算法，由LZ77 和Huffman 兩部分組成[3]。

LZ77 算法是一種基于字典查找的壓縮算法。在一個文件中往往存在大量重復出現的字符串，有效地消除這些冗余的字符串，可以達到壓縮效果。在壓縮過程中，數據可以放入兩個窗口中，第一個窗口為已處理數據，第二個窗口為未處理數據，可以將已處理數據窗口中的數據看做字典。在未處理數據窗口中，將找到與已處理數據窗口中匹配長度最長的數據字符串，用一對有用的信息來描述這串字符串，這對有用的信息往往是相對距離和匹配長度。通過這對信息，就可以快速且準確找到它所匹配的數據。將文件中的所有數據經過兩個窗口處理[12]，即可完成LZ77 壓縮。

經過LZ77 算法處理后的數據依然存在很大的壓縮空間。DEFLATE 壓縮算法的Huffman 編碼[5]部分對經過LZ77 算法壓縮后的數據進行進一步壓縮。Huffman 編碼也是無損壓縮算法的一種[13]。其核心思想是對文件中的數據進行重新編碼，給出現頻率高的字符賦予碼長較短的編碼，給出現頻率低的字符賦予碼長較長的編碼，以此來達到平均碼長最短的效果。

2.2 數據壓縮流程與數據結構設計

壓縮后的數據，按照固定的方式進行排序，這樣有利于硬件解壓的實現。通過壓縮算法的介紹，可以明顯地看出，DEFLATE 壓縮算法利用了數據前后的關聯性。因此，數據的解壓也必須是對一個完整的數據包進行解壓[6]。一個系統在提取數據時，可能從內存中的任何一個位置開始，考慮到系統的兼容性和解壓的效率，可以首先將原始數據分為固定大小的數據包，然后，對這些數據包依次進行壓縮。當需要內存中間某段數據時，不必從頭開始進行解壓，只需要通過解析地址提取出包含需要信息的一個或者幾個壓縮包進行解壓即可。下面將以一個16 kB的原始數據包為例，并配合壓縮軟件流程圖對壓縮數據的格式進行說明。

壓縮軟件流程圖如圖2 所示。首先將待壓縮數據以16 kB 為一個壓縮包進行切割，最后不滿16 kB的數據包用0 進行補齊。然后，依次將數據包送入壓縮函數進行壓縮。在一個數據包進行壓縮后，需要判斷壓縮后的數據量比未壓縮前是否變小，如果沒有，即此數據包不進行壓縮添加校驗碼后直接輸出，如果變小了，即此數據包進行壓縮并在添加校驗碼后進行輸出。之后，需要將此數據包的基本信息添加到查找表中，信息中包括是否壓縮、存放位置、壓縮后數據大小。為了方便查找表信息的記錄，壓縮后的數據需要進行1 kB 對齊操作。最后，需要判斷處理的數據包是否為最后一個數據包，如果不是，則重復上述流程對剩余數據包進行處理，如果是，則軟件壓縮流程結束。通過軟件壓縮流程操作后，得到按照固定格式排放的壓縮數據和查找表。

圖2 壓縮軟件流程圖

壓縮后數據結構圖如圖3 所示。在壓縮后數據結構中，前256 kB 用來保存查找表信息，文中規定一個16 kB 的數據包的數據是否壓縮,存儲大小,起始位置信息記錄到4個字節中，通過這種方式，256 kB查找表最多可記錄1 GB 的原始數據經壓縮數據后的信息。查找表信息后存放壓縮后數據，每個數據包包含校驗包頭、壓縮處理后，數據以及4 字節的校驗碼。

圖3 壓縮后數據結構圖

2.3 Zlib函式庫介紹

Zlib 是提供數據壓縮功能的函式庫[13]，此函式庫為自由軟件，使用Zlib 授權。Zlib 支持DEFLATE 算法，可以通過配置參數，實現上文介紹的LZ77 和靜態Huffman 壓縮算法流程。通過Zlib 函式庫，可以對上述算法流程進行快速且可靠的開發。

3 基于硬件的數據解壓模塊設計

通過軟件壓縮系統，得到了壓縮數據包。數據包中包含了解壓需要的查找表和壓縮后數據。在硬件端，需要將查找表的信息進行解析，根據查找表的信息，查詢壓縮數據包的大小位置以及壓縮方式，通過解壓策略對數據進行正確的解壓，并保證解壓出的數據與原始數據的一致性。

3.1 解壓策略

在壓縮過程中，數據首先經過LZ77 算法處理，再經過Huffman 算法處理，得到壓縮后數據[14]。對于壓縮數據包的解壓過程，與此過程相反。首先，需要對壓縮數據包進行靜態Huffman 解壓，之后需要進行LZ77 算法解壓。經過兩次數據處理，即可得到解壓后與原數據相同的數據。

靜態Huffman 的解壓策略如下：需要處理的數據是完整的壓縮數據包，數據包中包含的數據是經過靜態Huffman 編碼之后的數據。在解壓時，每一段不同的二進制編碼都可能代表著一個原始數據、一個長度數據或者一個距離數據。解壓過程需要依賴靜態Huffman 表[1]。首先，對照字符-長度Huffman編碼表[1]，對其進行解碼。在這一步中，可能得到的結果有兩種：第一種是通過解碼得到一個字符數據，此時需要將此數據記錄下來，并且設置標志位以表示此位為一個原始字符；第二種是通過解碼得到一個長度數據，設置一個標志位以表示此位為一個匹配長度信息，同時還包含了另一個重要信息：在此位置的下一個數據是一個匹配距離編碼。因此，在對此位的下一組二進制數進行解碼時，需要使用距離編碼表[1]中的映射關系進行解碼。通過上述解碼過程，即可對原始數據壓縮包進行靜態Huffman 解壓操作，并且生成LZ77 解壓流程所需數據。

經過Huffman 解壓后的數據主要包含兩部分，一部分是需要進行解壓的數據，另一部分是這段數據的標志位。此階段的解壓需要兩部分信息共同操作完成。在進行解壓時，首先需要根據標志位置判斷此數據時原始字符數據還是長度數據。如果是字符數據，則直接進行輸出；如果是長度數據，需要同時讀取此數據位的下一個數據，即與此長度信息相匹配的距離數據。根據長度距離信息對進行匹配數據，將對應數據復制到此長度距離信息對位置，即可完成LZ77 解壓。在解壓完成后會產生一個校驗碼，若此校驗碼和壓縮時所產生的校驗碼一致，則表明壓縮數據包讀取無誤，數據已進行正確解壓。否則，則表明壓縮數據包讀取有誤，此次數據解壓結果錯誤[15]。

3.2 解壓的硬件實現

解壓流程在FPGA 平臺實現,硬件解壓結構圖如圖4 所示。

圖4 硬件解壓結構圖

數據解壓模塊首先需要接收到原始數據地址信息和指令，通過地址解析模塊后，即可將原始地址信息解析為壓縮后的數據包地址信息。這部分的邏輯如下：計算需要提取的數據在原始數據包中的位置。將該位置信息進行解析，根據解析值提取相應的查找表信息即可明確相應壓縮數據包的位置、數據包大小、是否壓縮。根據上述信息即可得索引壓縮包地址。

從存儲器件讀入的壓縮數據包首先需要進入靜態Huffman 解壓模塊。在進行Huffman 解壓時，需要根據靜態Huffman 解壓表對相應的數據進行查找處理。主要硬件思想：輸入足夠的數據位首先需要判斷查找到的數據是字符還是長度，如果是字符數據，即可將其存儲至字符和長度FIFO 中并附加一位標識位0，表明此數據為字符，拼接在數據的最高位。如果是長度數據，需要根據靜態Huffman 字符-長度編碼表[1]進行解碼，將解析出來的長度數據同樣存儲到字符和長度FIFO 中并附加一位標識位1，標識此數據為長度數據。如果在字符-長度編碼表中未找到相匹配的數據，即可對數據進行距離靜態Huffman表[1]的解壓，將距離數據存儲到存儲距離FIFO 中。當解析出停止標識位后，靜態Huffman 解壓結束[16]。

在LZ77 解壓模塊，根據解壓策略可知，需要根據一個字典進行解壓，因此，需要一塊RAM 進行存儲字典數據。主要硬件思想：LZ77 會向字符和距離FIFO 申請數據，得到數據后首先需要根據數據最高位即標識位判斷數據是字符數據還是長度數據，如果是字符數據即標識位為0，對數據進行輸出，同時還需要將數據寫入字典RAM 中，對字典進行更新。如果是長度數據即標識位為1，需要向距離FIFO 中申請一個距離數據，根據此長度距離數據對在RAM中進行查找數據，長度和距離即可表示為數據在RAM 中存儲的地址。RAM 的大小，應該與LZ77 壓縮時已處理數據窗口的大小一致。

RAM 的存儲策略：假設一個指針指向最先進來的數據，距離數據的判斷即為與此指針位置的距離。在找到匹配數據后，需要將相應的數據進行復制輸出，同時用這段數據更新RAM 中的字典數據。

4 系統實現與驗證

系統的壓縮部分實現平臺為Visual Studio 2012，在此平臺上可以根據Zlib 函式庫，結合上述壓縮流程開發出壓縮軟件。系統的解壓部分通過ISE 和modelsim 進行設計和聯合仿真驗證，并在spartan6-xc6slx16上進行實現。

在硬件解壓端，首先需要進行靜態Huffman 解壓。靜態Huffman 解壓模塊接口中，clk 為工作時鐘，頻率為125 MHz。經過靜態Huffman 解壓操作，需要向字符長度FIFO 傳輸寫指令（即模塊中literal_length_wr）和距離FIFO 中的寫指令（即模塊中的distance_out_wr），對應于上述兩個寫指令的分別是輸出的字符和長度的組合數據（literal_length_out）和距離數據（distance）。Bit_cost 信號表示一次靜態Huffman 解壓操作具體消耗的位寬，由于不同的數據消耗位寬不同，需要通過此信號判斷下一次解壓的起始位置。Unzip_done 信號是當檢查到連續出現七位零數據時進行拉高，表示此次數據壓縮包靜態Huffman 解壓操作完成。

經過靜態Huffman 解壓之后，利用存儲在兩個FIFO 中的數據即可進行LZ77 解壓操作。LZ77 解壓模塊接口中，unzip_data_en 為解壓數據輸出使能，unzip_data 為解壓數據輸出端口，dis_fifo_empty 信號是從距離FIFO 中輸入到LZ77 解壓模塊的信號，表示此FIFO 中是否有數據，dis_fifo_rd 是從距離FIFO中讀數據的使能信號，dis_fifo_data 表示從距離FIFO中讀到的數據。len_fifo_empty 信號是從字符長度FIFO 中輸入到LZ77 解壓模塊的信號，表示此FIFO中是否有數據，len_fifo_rd 是從字符距離FIFO 中讀數據的使能信號，len_fifo_data 表示從字符長度FIFO中讀到的數據。

通過上述流程，在進行上板驗證之前，先經過beyond compare 對比軟件，將原始數據包和經過軟件壓縮和硬件解壓之后的數據進行對比。兩邊數據完全一致，驗證了系統邏輯的正確性。

實物驗證圖如圖5 所示，圖（a）為原始數據顯示圖片，圖（b）為經過壓縮和解壓處理后得到驗證圖。此次驗證在FPGA 實驗板上進行，通過液晶屏進行顯示。

圖5 實物驗證圖

在驗證功能的正確性之后，需要驗證壓縮率。測試結果如表1 所示，不同文件（圖像紋理）的壓縮率不同。因為系統使用的壓縮算法是由靜態Huffman 和LZ77 組合而成，這兩種算法雖然都可以完成無損壓縮，但是在壓縮率上是不定的，壓縮效果的好壞與原始數據的結構和不同字符出現的頻率有關。而且在壓縮數據包中，存在一個32 kB 的查找表，所占空間大小固定。原始數據量越大，壓縮效果越好。

表1 壓縮效果對比數據

表2 為傳輸數據量對比表。使用測試向量與表1 相同。其中系統傳輸數據量為嵌入式系統解壓出數據中任意連續的16 kB 數據時所需要從存儲器件中讀取的數據量。一般系統是指直接使用GZIP 算法進行壓縮[1]，其中Huffman 算法設定為使用靜態Huffman 算法。一般系統傳輸數據量即為壓縮包總量，該文系統傳輸數據量為可能的最大傳輸量。解壓效率為目標數據量在解壓出的總數據量所占比重。

表2 系統性能對比表

通過表2 可以得到：第一點，在解壓數據中連續16 kB 數據時，該文系統的數據傳輸量遠低于一般系統，有效緩解了數據傳輸的帶寬壓力；第二點，該系統的解壓效率普遍達到50%，遠高于一般系統，有效減少了系統的無用功，提高了系統性能；第三點，有效解壓數據量占原始數據量越小，一般系統的解壓效率越低，該文系統可根據數據需求量進行分塊傳輸，減少了有效解壓數據量對解壓效率的影響。

5 結束語

該文首先講解了所使用壓縮算法的基本原理和改進方法，并提出相應的解壓策略和其硬件實現思想。然后，實現了基于Visual Studio 2012 平臺的壓縮功能和基于FPGA 的解壓功能。在壓縮時按照固定格式排列并生成了查找表，為穩定地進行解壓操作提供了保證。在解壓側，利用FPGA 的并行性，進行快速且準確的解壓操作。最后，通過實驗驗證了該文系統的解壓效率高于一般系統，以及高效解壓的穩定性。