【正文】 可匹配字符長(zhǎng)度就等于 token 高 4 位的值。若 token 高 4 位為 15，則從token 開始向后數(shù) 15 個(gè)字節(jié)，第 1 17 個(gè)字節(jié)便是 literal length。 修改后的 LZ4 格式解壓流程 以下為修改后的 LZ4 格式解壓流程 1）讀取 magic number 判斷文件格式，若是 LZ4 格式的進(jìn)入解壓程序，否則退出。 7）確定匹配字符長(zhǎng)度后，從匹配的位置處開始向后拷貝字符，拷貝字符的長(zhǎng)度和匹配字符的長(zhǎng)度一致。 6）若 token 低 4 位為 15，則從 offset 的兩個(gè)字節(jié)后讀取一個(gè)字節(jié)，若該字節(jié)為 255 則繼續(xù)讀取下一個(gè)，直到不為 255 為止，這時(shí)匹配字符長(zhǎng)度就等 于這些字節(jié)求和后再加上 19。 4）確定不可匹配字符長(zhǎng)度后，將不可匹配字符復(fù)制到輸出緩存中。若 token 高 4 位為 15，則繼續(xù)向后讀取后一個(gè)字節(jié)，若該字節(jié)為 255，則繼續(xù)往下直到 讀取到第一個(gè)小于 255 的字節(jié)為止，不可匹配字符長(zhǎng)度就是這些所有字節(jié)的值求和再加上 15。 解壓 官方 LZ4 格式解壓流程 以下為官方 LZ4 格式解壓流程 [11]： 1）讀取 magic number 判斷文件格式，若是 LZ4 格式的進(jìn)入解壓程序，否則退出。 4）若匹配且后向匹配完成，接著將計(jì)算好了的數(shù)據(jù)寫入輸出緩存中 5）當(dāng)前序列輸出完成后，返回第一步讀取后 4 字節(jié)查找下 一個(gè)匹配。 2）讀取 hash 表的地址，寫入當(dāng)前地址，調(diào)用匹配算法查詢是否匹配。 4） 保存 ip 和 h 的對(duì)應(yīng)關(guān)系。 ）如果 ref 對(duì)應(yīng)的 4 個(gè)字節(jié)和 ip 對(duì)應(yīng)的 4 個(gè)字節(jié)不 一樣，是沖突，繼續(xù)向下查找匹配。 ） ref 不為初始值，有匹配。 3）按照哈希值 h，獲取哈希表中的值 ref。 匹配算法 匹配算法執(zhí)行步驟： 1）令當(dāng)前的地址為 ip，它的哈希值為 h。 2654435761U 是 2 到 2^32 的黃金分割素?cái)?shù)， 2654435761 / 4294967296 = 。當(dāng)前主流的 Intel X86 L1 Data Cache 為 32KB，所以哈希表的大小最好不要超過(guò) 32KB。 2）如果更看重壓縮速度，則哈希表應(yīng)該適中，以便于能裝入 L1 cache。 value 為這 4 個(gè)字節(jié)在數(shù)據(jù)塊中的位置。 算法流程 hash 表 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 8 LZ4 通過(guò)計(jì)算哈希值建立哈希表來(lái)查找匹配字符串。 （ 3） match length 當(dāng) token 低 4 位小于 15 時(shí)， match length 為 0 字節(jié)，實(shí)際匹配長(zhǎng)度為 token 后四位加 4。 圖 修改后的 LZ4 數(shù)據(jù)格式 （ 2） length of literals 當(dāng) token 高 4 位小于 15 時(shí)， literal length 為 0 字節(jié)。所以通過(guò)改變數(shù)據(jù)格式來(lái)提高壓縮速度。 修改后的 LZ4 格式 （ 1）數(shù)據(jù)格式 由于在硬件實(shí)現(xiàn)的時(shí)候，由于是高速流操作，輸入數(shù)據(jù)需要在幾個(gè)時(shí)鐘內(nèi)判斷是否匹配，判斷結(jié)束后不可匹配數(shù)據(jù)需要立即輸出到緩存中。因此一個(gè)文件的最后一個(gè)序列至少有 12 個(gè)字節(jié)數(shù)據(jù)應(yīng)被壓縮為 literals。 （ 7）最后一個(gè)序列規(guī)則 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 7 1）壓縮序列的最后 5 個(gè)字節(jié)必須是 literals。匹配數(shù)據(jù)的最小值為 4，因此，若 token 后 4 位的值為 0，則意味著實(shí)際匹配的數(shù)據(jù)為 4 個(gè)字節(jié)，若 token 后 4 位的值為 15，則意味著實(shí)際匹配的數(shù)據(jù)為 19 字節(jié)。 offset 用小頭結(jié)構(gòu)表示，最大值為 65525。 （ 5） offset 當(dāng)輸入的數(shù)據(jù)經(jīng)查找發(fā)現(xiàn)之前出現(xiàn)過(guò)相同的數(shù)據(jù)時(shí)，此處的數(shù)據(jù)將會(huì)被壓縮，而 offset的值表示這兩處相同數(shù)據(jù)之 間的偏移量。若附加的一字節(jié)數(shù)據(jù)還是不能表示完整的長(zhǎng)度，則繼續(xù)在后面添加一個(gè)字節(jié)，以此類推。每一個(gè)添加的字節(jié)取值范圍為 0 到 255。 （ 3） literal length 如果 token 高 4 位為小于 15，則該值為 0，且不會(huì)輸出到壓縮文件里，表示未壓縮數(shù)據(jù)長(zhǎng)度等于 token 高 4 位的值；如果 token 高 4 位等于 15，表示不可壓縮數(shù)據(jù)大于等于 15，此時(shí)該值等于未壓縮 數(shù)據(jù)長(zhǎng)度減去 15 后的大小。每個(gè)序列格式如圖 [9]所示： 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 6 圖 數(shù)據(jù) 格式 （ 2） token 高 4 位代表不可匹配字符長(zhǎng)度，當(dāng)不可匹配字符長(zhǎng)度大于等于 15 時(shí)高 4 位為 15；當(dāng)不可匹配字符長(zhǎng)度小于 15 時(shí)，高 4 位就等于不可匹配字符長(zhǎng)度。 Stream checksum 則是一個(gè)校驗(yàn)碼，也可以去掉。中間的 Block 就是一個(gè)個(gè) 數(shù)據(jù)塊了，這是壓縮文件的主體。為了實(shí)現(xiàn)流輸入，在后面介紹了修改后的 LZ4 無(wú)損壓縮算法原理以及壓縮后的數(shù)據(jù)格式。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 5 第三章 LZ4 無(wú)損壓縮算法原理 LZ4 無(wú)損數(shù)據(jù)壓縮是當(dāng)今最快的壓縮算法，當(dāng)然不是指只要用 LZ4 壓縮算 法就會(huì)比其他算法實(shí)現(xiàn)更快，而是指這個(gè)算法的流程更少，使用更少的步驟來(lái)完成整個(gè)流程，這樣壓縮算法的速度在相同條件下自然就比其他算法更加快速。預(yù)讀緩存區(qū)是用來(lái)保留當(dāng)前輸入數(shù)據(jù)的前 4 個(gè)字節(jié)，將這4 個(gè)字節(jié)進(jìn)行 hash 計(jì)算后，判斷當(dāng)前字節(jié)是否在滑動(dòng)窗口中出現(xiàn)過(guò)，若在滑動(dòng)窗口中出現(xiàn)過(guò)則可以進(jìn)行匹配，繼續(xù)往后查找匹配，查找結(jié)束后將當(dāng)前字節(jié)與之前出現(xiàn)過(guò)的字節(jié)處的距離表示當(dāng)前這一段數(shù)據(jù)，然后通過(guò)相應(yīng)的格式組合成一個(gè)序列。 LZ4 與 LZ77 算法一樣，擁有一個(gè)滑動(dòng)窗口以及一個(gè)預(yù)讀緩存 區(qū)域。 LZ4 算法也是由 LZ77 算法衍生而來(lái)，不同的是 LZ4 算法更加注重與壓縮和解壓的速度，用最少的步驟實(shí)現(xiàn)匹配查找與編碼，從而提高壓縮速度。這些衍生改進(jìn)的算法統(tǒng)稱為 LZ 系列算法。信源 X 的信息熵 (Entropy) H(x)定義為 [8]： （ ） 信源經(jīng)常由于事件相關(guān)或概率分布不均勻等原因，而使實(shí)際的熵小于其最大熵，這樣就產(chǎn)生了信息的冗余。 信息論中把一個(gè)事件（如字符）所攜帶的信息量定義為 [8]： （ ） 其中 P（ Xi）為實(shí)踐發(fā)生（字符 Xi）的概率。信息論量度信息的基本出發(fā)點(diǎn)，是把獲得的信息看作用以消除不確定性的東西，因此信息數(shù)量的大小，可以用被消除的不確定性的多少來(lái)表示。不過(guò)可以通過(guò)理論來(lái)知道為何數(shù)據(jù)可以被壓縮，也可以通過(guò)這些理論來(lái)指導(dǎo)數(shù)據(jù)壓縮的實(shí)現(xiàn)。從信息論中可以知道什么樣的數(shù)據(jù)壓縮后會(huì)變小，什么樣的數(shù)據(jù)壓縮后占據(jù)空間反而會(huì)變大。 第八章是對(duì)整個(gè)論文的總結(jié)。 第六章是對(duì) LZ4 無(wú)損壓縮算法 的 硬件實(shí)現(xiàn) 做的一些數(shù)據(jù)測(cè)試，計(jì)算了其壓縮率，并將它的壓縮速度與市場(chǎng)上的一些產(chǎn)品做比較。 第四章提供了三個(gè) LZ4 無(wú)損壓縮算法 的 硬件實(shí)現(xiàn)方案 ，并詳細(xì)介紹了每個(gè)方案的實(shí)現(xiàn)流程 以及每個(gè)方案的優(yōu)缺點(diǎn)，同時(shí)對(duì)其性能做出了詳細(xì)的比較。 本文章節(jié)內(nèi)容安排如下： 第一章主要介紹 LZ4 算法的 FPGA 高速實(shí)現(xiàn)的研究背景，介紹了數(shù)據(jù)壓縮的歷史與現(xiàn)狀，并明確了本文 的研究?jī)?nèi)容 ； 第二章分析了數(shù)據(jù)壓縮原理，表明了什么樣的數(shù)據(jù)才能壓縮，并對(duì) LZ 系列算法做了一個(gè)大概的介紹。在對(duì) LZ4算法足夠了解后，將算法細(xì)分成幾個(gè)步驟得出算法流程圖。 本文研究?jī)?nèi)容 和結(jié)構(gòu)安排 本文主要研究 LZ4算法流程、硬件實(shí)現(xiàn)、以及算法優(yōu)化。因?yàn)橛?件方式相比軟件方式實(shí)現(xiàn)的速度快很多，依靠電路實(shí)現(xiàn)不需要循環(huán)的指令計(jì)算，而且能夠采取并行的實(shí)現(xiàn)方式，這樣降低了資源和能源的消耗。用專用硬件提供壓縮解壓可以解決上述軟件壓縮解壓所存在的缺點(diǎn)。所以，如何有效提高壓縮算法的效率，減少龐大數(shù)據(jù)量壓縮解壓給 CPU 和內(nèi)存帶來(lái)的壓力成為了現(xiàn)在壓縮解壓技術(shù)的主要發(fā)展方向。采用軟件方式的壓縮解壓存在一個(gè)致命的弱點(diǎn)，那就是過(guò)多地消耗寶 貴的 CPU 資源而且速度慢?，F(xiàn)在流行的壓縮技術(shù)基本上都是由這些算法衍生而來(lái) [4][5]。但是像程序、電子檔案等類似的需要完全可以復(fù)原的重要信息，就必須采用無(wú)損壓縮技術(shù)，用于這種要求解壓縮后的數(shù)據(jù)與原始數(shù)據(jù)完全一致的場(chǎng)合的常見算法有 LZ7LZSS、 GZIP、 BZIP RAR 等。 數(shù)據(jù)壓縮通常分為無(wú)損壓縮和有損壓縮。將數(shù)據(jù)進(jìn)行有效的壓縮能夠減少存儲(chǔ)所需的空間以及最大限度地利用有限的通信帶寬。 Verilog。 關(guān)鍵詞 ： 無(wú)損壓縮， LZ4， Verilog， FPGA 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 ii FPGA Implementation of Lossless Data Compression Abstract With the rapid development of information technology, the amount of data presents explosive growth. Therefore, more and more attention has been paid to the data pression. Up to date, most of lossless pression algorithms are realized in software. However, software implementation in many occasions cannot meet the real time requirements of highspeed system. The hardware implementation of data pression algorithms is being a research hotspot. Nowadays, there are hardware implementations of the lossless data pression algorithms such as LZ77, LZ78, LZW etc. But they have defects including small search window, low pression rate, and slow processing speed. In this thesis, for the consideration of the hardware implementation, the LZ4 algorithm is appropriately modified to be implemented on Xilinx FPGA KC 705 evaluation board, which offers higher pression rate and speed. Key Words： Lossless pression。目前已有 LZ7 LZ78及 LZW 等算法的硬件實(shí)現(xiàn)，但是都存在搜索窗口較小，壓縮率較低，速度較慢等缺陷。 作者簽名： 年 月 日 （學(xué)號(hào)）： 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 i 無(wú)損數(shù)據(jù)壓縮算法的 FPGA 實(shí)現(xiàn) 摘 要 隨著信息技術(shù)的快速發(fā)展，數(shù)據(jù)量呈現(xiàn)爆炸性增長(zhǎng)，因此數(shù)據(jù)壓縮越來(lái)越受到人們的重視。 編號(hào) 南京航空航天大學(xué) 畢業(yè) 設(shè)計(jì) 題 目 無(wú)損數(shù)據(jù)壓縮算法的 FPGA 實(shí)現(xiàn) 學(xué)生姓名 梅發(fā)強(qiáng) 學(xué) 號(hào) 041220318 學(xué) 院 電子信息工程學(xué)院 專 業(yè) 信息工程 班 級(jí) 0412206 指導(dǎo)教師 劉偉強(qiáng) 副教授 二 〇一六 年五月 南京航空航天大學(xué) 本科畢業(yè)設(shè)計(jì)（論文）誠(chéng)信承諾書 本人鄭重聲明：所呈交的畢業(yè)設(shè)計(jì)（論文）（題目： 無(wú)損數(shù)據(jù)壓縮算法的 FPGA 實(shí)現(xiàn) ）是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的成果。盡本人所知，除了畢業(yè)設(shè)計(jì)（論文）中特別加以標(biāo)注引用的內(nèi)容外，本畢業(yè)設(shè)計(jì)（論文）不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。目前，無(wú)損壓縮算法大多數(shù)都是基于軟件方式的實(shí)現(xiàn)，但是這在很多場(chǎng)合下已經(jīng)不能滿足高速數(shù)字系統(tǒng)的要求，所以基于硬件方 式的實(shí)現(xiàn)成為了新的研究熱點(diǎn)。本文出于硬件實(shí)現(xiàn)的考慮，對(duì) LZ4 算法進(jìn)行了適當(dāng)?shù)男薷模?FPGA 進(jìn)行實(shí)現(xiàn)，經(jīng)實(shí)測(cè)發(fā)現(xiàn)其壓縮率和速度都得到了顯著提升。 LZ4。 FPGA 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 iii 目 錄 摘 要 .................................................................