一種基於gzip的壓縮硬體系統及其加速方法

2023-10-04 11:41:49

專利名稱：一種基於gzip的壓縮硬體系統及其加速方法
技術領域：
本發明涉及一種基於GZIP壓縮硬體系統實現與加速方法；屬於數據壓縮技術領域。
背景技術：
隨著雲計算技術的發展，海量數據存儲和傳輸越來越嚴峻。因此，數據無損壓縮技術得到廣泛的應用以減少數據存儲空間、提升數據傳輸效率。GZIPjPGNU ZIP壓縮算法是非常著名的無損壓縮算法，無專利保護，複雜度適中，適合硬體平臺實現。
在傳統的數據壓縮領域中，基於軟體平臺的實現的方案得以廣泛的運用，然而基於軟體平臺的實現方法中，佔用太多CPU,即Central Processing Unit以及內存資源。在本發明中，給出了一種全新的GZIP硬體實現結構並提出了多種加速方案來提升整個系統性能，可以顯著的減少CPU以及內存資源的消耗。高性能系統總線PCIE2. 0作為壓縮卡與計算機之間進行通信橋梁，DMA,即Direct Memory Access通過PCIE2. 0接口把計算機內存中的數據傳輸給GZIP壓縮內核，在內核壓縮完畢之後，DMA再將壓縮過的數據傳遞到就算計的內存中，在數據傳遞和壓縮過程中無需CPU幹預。

發明內容
本發明目的是針對現有技術存在的缺陷提供一種可實現GZIP壓縮算法、做到軟體壓縮相兼容、提升GZIP壓縮的數據吞吐率，使得數據壓縮過程中無需CPU的幹預的GZIP壓縮硬體系統實現與加速方法。本發明為實現上述目的，採用如下技術方案一種基於GZIP的壓縮硬體系統，該系統包括
一個輸入緩存單元，用於對輸入數據進行緩存；
一個LZ77編碼單元，用於對輸入數據進行LZ77編碼；
一個動態新字符/匹配長度Huffman編碼頻率統計控制單元，用於對LZ77編碼單元輸出的新字符以及匹配長度進行統計；
一個動態指回距離Huffman編碼頻率統計控制單元,用於對LZ77編碼單元輸出的指回距離進行統計；
一個動態新字符/匹配長度Huffman編碼單元，用於對LZ77編碼單元輸出的新字符以及匹配長度進行動態Huffman編碼；
一個動態指回距離Huffman編碼單元，用於對LZ77編碼單元輸出的指回距離進行動態Huffman 編碼；
一個動態碼字長度Huffman編碼單元,用於對動態新字符/匹配長度Huffman樹的信息及對動態指回距離Huffman樹的信息進行編碼；一個靜態新字符/匹配長度Huffman編碼單元，用於對LZ77編碼單元輸出之後的新字符/匹配長度進行靜態Huffman編碼；
一個靜態指回距離Huffman編碼單元，用於對LZ77編碼單元輸出之後的指回距離進行靜態Huffman編碼；
一個數據打包單元，用於判斷採用直接存儲、靜態Huffman編碼以及動態Huf fman編碼三種模式中的一種，並按照固定的格式進行編碼輸出；
一個輸出緩存單元，用於緩存數據打包單元輸出的壓縮之後的數據。優選的，所述輸入緩存單元包括
兩個數據塊緩存單元，用於存放待壓縮的原始數據；
兩個數據選擇單元，用於控制數據塊緩存單元的讀寫控制權。優選的,所述LZ77編碼單元包括
兩對Head/Prev Hash表，用於對LZ77編碼單元中編碼字符串的快速匹配查找；
一個只讀存儲單元R0M，用於存放循環冗餘校驗碼CRC32校驗計算時的常數表；
一個新字符/匹配長度緩存單元，用於存放LZ77編碼單元輸出之後的新字符或者是匹配長度；
一個指回距離緩存單元，用於存放LZ77編碼單元輸出之後的指回距離；
一個主控狀態機單元，用於對數據塊緩存單元中的數據進行數據讀取。優選的，所述動態新字符/匹配長度Huffman編碼單元包括
一個新字符/匹配長度頻率緩存單元，用於存放LZ77編碼單元輸出之後新字符以及匹 配長度的頻率；
一個新字符/匹配長度父親節點緩存單元，用於存放新字符以及匹配長度Huffman樹中每一個節點的父親節點，其中根節點除外；
一個新字符/匹配長度深度緩存單元，用於存放新字符以及匹配長度Huffman樹中每一個節點在新字符以及匹配長度Huffman樹中的深度；
一個新字符/匹配長度最小堆緩存單元，用於連續存放新字符以及匹配長度Huffman樹中所有的節點；
一個新字符/匹配長度碼字值緩存單元，用於存放新字符/匹配長度Huffman樹中所有的葉子節點對應的Huffman編碼的值；
一個新字符/匹配長度碼字長度緩存單元，用於存放新字符以及匹配長度Huffman樹中所有節點對應的一個Huffman編碼的有效長度；
3個數據選擇單元，分別用於控制新字符/匹配長度頻率緩存單元、新字符/匹配長度碼字值緩存單元、新字符/匹配長度碼字長度緩存單元的控制權；
一個流水線乘法器單元，用於輔助計算數據塊經過動態新字符以及匹配長度Huffman編碼之後的大小；
一個主控狀態機單元，用來根據新字符/匹配長度頻率緩存單元中存放的待壓縮數據塊中每一個字符的頻率信息，利用新字符/匹配長度父親節點緩存單元、新字符/匹配長度深度緩存單元、新字符/匹配長度最小堆緩存單元去構造Huffman樹,並將Huffman樹的信息存放在新字符/匹配長度最小堆緩存單元中，在得到新字符/匹配長度Huffman樹的信息之後，主控狀態機單元遍歷Huffman樹得出Huffman樹中每一個節點的碼字長度,並對該節點加以判斷；如果是葉子節點，則所述主控狀態機單元繼續從新字符/匹配長度緩存單元中讀取該節點的頻率，並利用流水線乘法器單元去計算出當前的這個字符經過Huffman編碼之後的大小，再根據得出的Huffman樹中每一個節點的碼字長度去計算出Huffman樹中每一個節點的碼字值，主控狀態機單元對這些節點加以判斷，如果是葉子節點就將葉子節點的碼字值存放進新字符/匹配長度碼字值緩存單元中。優選的,所述動態指回距離Huffman編碼單元包括
一個指回距離頻率緩存單元，用於存放LZ77編碼單元輸出之後指回距離的頻率；
一個指回距離父親節點緩存單元，用於存放指回距離Huffman樹中每一個節點的父親節點，其中根節點除外；
一個指回距離深度緩存單元，用於存放指回距離Huffman樹中每一個節點在指回距離Huffman樹中的深度；
一個指回距離最小堆緩存單元，用於連續存放指回距離Huffman樹中所有的節點；
一個指回距離碼字值緩存單元，用於存放指回距離Huffman樹中所有的葉子節點對應的Huffman編碼的值；
一個指回距離碼字長度緩存單元，用於存放指回距離Huffman樹中所有節點對應的Huffman編碼的有效長度；
3個數據選擇單元，分別用於控制指回距離頻率緩存單元、指回距離碼字值緩存單元、指回距離碼字長度緩存單元的控制權；
一個流水線乘法器單元，用於輔助計算數據塊經過動態指回距離Huffman編碼之後的大小；
一個主控狀態機單元，用來根據指回距離頻率緩存單元中存放的待壓縮數據塊中每一個字符的頻率信息，並利用指回距離父親節點緩存單元、指回距離深度緩存單元、指回距離最小堆緩存單元去構造Huffman樹,並將Huffman樹的信息存放在最小堆緩存單元中,在得到指回距離Huffman樹的信息之後，主控狀態機單元遍歷Huffman樹得出Huffman樹中每一個節點的碼字長度，並對該節點加以判斷，如果是葉子節點，主控狀態機單元將從新字符/匹配長度緩存單元中讀取該節點的頻率，利用流水線乘法器單元去計算出當前的這個字符經過Huffman編碼之後的大小,再根據得出的Huffman樹中每一個節點的碼字長度去計算出Huffman樹中每一個節點的碼字值,主控狀態機單元對這些節點加以判斷，如果是葉子節點就將葉子節點的碼字值存放進指回距離碼字值緩存單元中。優選的，所述的動態碼字長度Huffman編碼單元包括
一個碼字長度數據統計單元，用於統計新字符/匹配長度碼字長度緩存單元和指回距離碼字長度緩存單元中每一種碼字長度出現的頻率；
一個碼字長度頻率緩存單元，用於存放碼字長度數據統計單元統計的結果；
一個碼字長度父親節點緩存單元，用於存放碼字長度Huffman樹中每一個節點的父親節點；
一個碼字長度深度緩存單元，用於存放碼字長度Huffman樹中每一個節點的深度； 一個碼字長度小堆緩存單元，用於連續存放碼字長度Huffman樹中所有的節點；
一個碼字長度碼字值緩存單元，用於存放碼字長度Huffman樹中每一個葉子節點對應的Huffman編碼的值；一個碼字長度的碼字長度緩存單元，用於存放碼字長度Huffman樹中所有節點對應的Huffman編碼的碼字長度；
一個碼字長度葉子節點緩存單元，用於存放對新字符/匹配長度碼字長度緩存單元和指回距離碼字長度緩存單元進行遍歷之後得到的碼字長度的葉子節點；
一個碼字長度重複次數緩存單元，用於存放遍歷之後碼字長度的重複次數；
5個數據選擇單元，分別用於控制碼字長度頻率緩存單元、碼字長度碼字值緩存單元、碼字長度的碼字長度緩存單元、碼字長度葉子節點緩存單元、碼字長度重複次數緩存單元的控制權；
一個流水線乘法器單元，用於計算數據塊經過動態碼字長度Huffman編碼之後的大
小;一個碼字長度主控狀態機，用於完成新字符/匹配長度碼字長度緩存單元和指回距離碼字長度緩存單元中遍歷所有葉子節點的碼字長度，並將統計的結果存放在碼字長度葉子節點緩存單元和碼字長度重複次數緩存單元中，將每一個葉子節點的頻率信息存放在碼字長度頻率緩存單元中。優選的,所述的數據打包單元包括
讀取變長碼字單元，用於讀取LZ77編碼單元、動態新字符/匹配長度Huffman編碼單元、動態指回距離Huffman編碼單元和動態碼字長度Huffman編碼單元中相應的信息；變長碼字打包單元，根據讀取變長碼字單元提供的信息從而獲知針對當前數據塊所採用的壓縮模式。一種如上所述的基於GZIP壓縮硬體系統的加速方法，所述加速方法包括
輸入桌球操作在GZIP壓縮硬體系統中的應用，用於提升系統數據的吞吐率；
兩對 Head/Prev Hash 表，分別是 Headl/Prevl Hash 表方法和 Head2/Prev2 Hash 表方法，用來進一步提升系統數據的吞吐率；
Huffman編碼統計提前，用於提升數據的吞吐率；
Huffman編碼清空提前，用於提升數據的吞吐率；
CRC32校驗穿插計算，利用LZ77編碼單元縮減數據處理的時鐘周期，提升數據的吞吐率。本發明的有益效果本壓縮硬體系統及其加速方法可實現GZIP壓縮算法、做到軟體實現壓縮相兼容、提升GZIP壓縮的數據吞吐率，使得數據壓縮過程中無需CPU的幹預。


附加的並且形成說明書一部分的附圖包括在本發明的特定方面的描寫中。本發明以及本發明提供的系統的模塊和流程的更清楚的概念，通過參考示例以及附圖中示出非限制性的實施例將更容易理解。通過參考一個或多個附圖結合本發明的描述可以更好的理解本發明。圖I示出本發明實施例提供的一種GZIP壓縮硬體系統實現結構 圖2示出本發明提供的一種GZIP壓縮硬體系統實現的具體工作流程示意 圖3示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中寫入緩存單元的具體實施方式
的結構示意圖；圖4示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中LZ77編碼單元的具體實施方式
的結構示意 圖5示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態新字符/匹配長度Huffman編碼頻率統計控制單元的具體實施方式
的工作流程示意 圖6示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態指回距離Huffman編碼頻率統計控制單元的具體實施方式
的工作流程示意 圖7示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態新字符/匹配長度Huffman編碼單元的具體實施方式
的結構示意 圖8示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態指回距離Huffman編碼單元的具體實施方式
的示意 圖9示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態碼字長度 Huffman編碼單元的具體實施方式
的結構示意 圖10示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中靜態新字符/匹配長度Huffman編碼單元的具體實施方式
的結構示意 圖11示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中一個靜態指回距離Huffman編碼單元的具體實施方式
的結構示意 圖12示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中數據打包單元的具體實施方式
的結構示意 圖13示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中輸出緩存單元的具體實施方式
的結構示意 圖14示出本發明提供的一種GZIP壓縮硬體系統加速方法中雙Head/Prev加速方法的具體實施方式
結構示意 圖15示出本發明提供的一種GZIP壓縮硬體系統加速方法中雙Head/Prev加速方法的具體實施方式
的工作流程示意 圖16示出本發明提供的一種GZIP壓縮硬體系統加速方法中Huffman提前統計加速方法的具體實施方式
的結構示意 圖17示出本發明提供的一種GZIP壓縮硬體系統加速方法中Huffman提前清空加速方法的具體實施方式
的工作流程示意 圖18示出本發明提供的一種GZIP壓縮硬體系統加速方法中CRC32穿插計算的具體實施方式
的工作流程示意圖。
具體實施例方式下面參照附圖用本發明的示例性實施例對本發明進行更加全面的描述和說明。圖I示出本發明實施例提供的一種GZIP壓縮硬體系統實現結構圖。如圖I所示，本發明提供的一種GZIP壓縮硬體系統實現100主要包括輸入緩存單兀101、新子符/匹配長度頻率統計控制單兀102、指回距尚頻率統計控制單兀103、LZ77編碼單元104、動態新字符/匹配長度Huffman編碼單元105、動態指回距離Huffman編碼單元106、靜態新字符/匹配長度Huffman編碼單元107、靜態指回距離Huffman編碼單元108、動態碼字長度Huffman編碼單元109、數據打包單元110、輸出緩存單元111。
其中，輸入緩存單元101，用於對待壓縮的數據進行緩存，尤其是，原始數據經過數據緩存單元中兩個數據存儲單元可是實現數字電路設計中提升數據吞吐率的桌球操作。新字符/匹配長度頻率統計控制單元102，主要是用於接收從LZ77編碼單元104中輸出的新字符/匹配長度，並作出進一步的判斷，如果是新字符則之直接輸出。否則，就是匹配長度，此時，新字符/匹配長度頻率統計單元102從動態新字符/匹配長度Huffman樹字符表將匹配長度映射到相應的範圍再輸出。指回距離頻率統計控制單元103，主要是用於接收從LZ77編碼單元104中輸出的指回距離，並查詢動態指回距離Huffman樹字符表將指回距離映射到相應的範圍再輸出。LZ77編碼單元104，首先，主要是用於對輸入緩存單元101中的數據進行LZ77編碼，並把編碼的結果分別輸出到新字符/匹配長度頻率統計控制單元102及指回距離頻率統計控制單元103。其次，LZ77編碼單元104是要完成對原始數據的CRC32校驗計算，並把計算的結果反饋給數據打包單元HO。 動態新字符/匹配長度Huffman編碼單元105,主要是用於對LZ77編碼單元104輸出的新字符/匹配長度進行動態Huffman編碼。動態指回距離Huffman編碼單元106，主要是用於對LZ77編碼單元104輸出的指回距離進行動態Huffman編碼。靜態字符/匹配長度Huffman編碼單元107，主要用於對LZ77編碼單元104輸出的新字符/匹配長度進行靜態Huffman編碼。例如，在某些特殊的數據壓縮場合之下，如音視頻領域中，數據的統計特性變化範圍很小。因此，為了提升Huffman編碼的速度，需要對這些統計特性變化很小的數據提前做好Huffman編碼，並將Huffman編碼的結果固化在ROM中，在實際中，即使數據的統計特性有些波動影響到一些壓縮率，但是壓縮的速度卻得以顯著性的提升。靜態指回距離Huffman編碼單元108，主要是用於對LZ77編碼單元的輸出的指回距尚進行靜態Huffman編碼。動態碼字長度Huffman編碼單元109，主要是用於對動態新字符/匹配長度Huffman編碼的碼字長度信息和動態指回距離Huffman編碼的碼字長度信息進行動態Huffman編碼，以此來減小動態Huffman編碼時樹的信息以提升數據的壓縮率。數據打包單元110，根據LZ77編碼單元104給出的原始數據的大小，動態新字符/匹配長度Huffman編碼單元105、動態指回距離Huffman編碼單元106、動態碼字長度Huffman編碼單元109給出的對原始數據塊採用動態Huffman編碼之後的大小,靜態新字符/匹配長度Huffman編碼單元107、靜態指回距離Huffman編碼單元108給出的對原始數據塊進行靜態Huffman編碼之後的大小來決定採用的直接存儲、動態Huffman編碼、靜態Huffman編碼三種壓縮模式中的一種對待壓縮數據塊進行壓縮。輸出緩存單元111，主要是用於接收來自數據打包單元110輸出的壓縮之後的數據。圖2示出本發明提供的一種GZIP壓縮硬體系統實現的具體工作流程。如圖2所示，本發明提供的一種GZIP壓縮硬體系統實現的具體工作流程200主要包括
步驟201，填充輸入緩存單元中的一個數據緩存單元。用來接收待壓縮的原始數據，如果原始數據可以分割成多個數據塊，則交替使用輸入數據緩存單元中兩個數據存儲單元，使得數據的傳輸和數據的處理並行的進行，以此來提升數據的吞吐率，填滿之後進入步驟202。步驟202，通知GZIP壓縮單元中的LZ77編碼單元數據已經填滿。LZ77編碼單元在接收到這個信息之後開始選擇輸入緩存單元中相應的數據緩存單元，進入步驟203。步驟203，LZ77工作。LZ77在獲得輸入緩存單元中相應的數據緩存單元的控制權之後開始工作，並對當前的數據塊進行CRC32校驗計算，進入步驟204。步驟204，判斷LZ77工作是否完成。如果LZ77編碼工作尚未完成就繼續進行LZ77編碼工作，進入步驟203，否則就開始準備啟動後續的工作單元進入步驟205。
步驟205,動態新字符/匹配長度Huffman編碼單元和動態指回距離Huffman編碼單元開始工作。LZ77編碼單元結束之後，就開始啟動動態新字符/匹配長度Huffman編碼單元對LZ77編碼輸出的新字符/匹配長度進行動態Huffman編碼；同時，啟動動態指回距離Huffman編碼單元對LZ77編碼輸出的指回距離進行動態Huffman編碼,接著進入步驟206。步驟206,判斷動態新字符/匹配長度Huffman編碼單元和指回距離Huffman編碼單元工作是否結束。如果沒有結束就繼續進行動態Huffman編碼的過程205，否則，就準備進入步驟207。步驟207，動態碼字長度Huffman編碼單元開始工作。如果動態新字符/匹配長度Huffman編碼單元和動態指回距離Huffman編碼單元都結束,則動態碼字長度Huffman編碼單元開始工作，進入步驟208。步驟208，判斷動態碼字長度Huffman編碼單元工作是否結束。如果沒有結束，繼續進行動態碼字長度Huffman編碼過程，否則，就進入步驟209。步驟209，啟動數據打包單元。在動態碼字長度Huffman編碼單元工作結束之後，數據打包單元開始啟動，並根據LZ77編碼單元給出的結果、動態新字符/匹配長度Huffman編碼單元給出的結果、動態指回距離Huffman編碼單元給出的結果、動態碼字長度Huffman編碼單元給出的結果進行判斷，選擇直接存儲、動態Huffman編碼、靜態Huffman編碼三種壓縮模式中的一種對當前的數據塊進行壓縮，當前數據塊編碼完成之後直接進入步驟210。步驟210，判斷當前處理的數據塊是不是最後一個數據塊。如果是最後一個數據塊，就表示數據壓縮完畢，否則進入步驟201開始處理下一個數據塊。由此可見，原始待壓縮的數據是分割成多個數據塊進行壓縮的，從而使得桌球操作的實現成為可能。圖3示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中寫入緩存單元的具體實施方式
的結構示意圖。如圖3所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中寫入緩存單元300的具體實施方式
的結構進一步包括數據選擇單元301、數據緩存單元302、數據緩存單元303、數據選擇單元304。如圖3所示，其中數據選擇單元301，主要是用於控制數據緩存單元302和數據緩存單元303中的一個進行數據填充。數據緩存單元302和數據緩存單元303，主要是用於緩存待壓縮的數據，實際工作時，一個數據緩存單元用來進行數據編碼，另一個數據緩存單元用來進行數據的填充，使得數據的填充和數據的編碼並行的進行。數據選擇單元304，主要是用於選擇數據緩存單元302和數據緩存單元303中的一個來進行數據的編碼處理。圖4示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中LZ77編碼單元的具體實施方式
的結構示意圖。如圖4所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中LZ77編碼單元的具體實施方式
的結構400進一步包括Headl Hash查找表401、Prevl Hash查找表402、Head2 Hash查找表403、Prev2 Hash查找表404、LZ77主控狀態機單元405、ROM查找表406、新字符/匹配長度緩存單元407、指回距離緩存單元408。其中，HeadlHash 查找表 401、Prevl Hash 查找表 402、Head2 Hash 查找表 403、 Prev2 Hash查找表404，主要是被LZ77主控狀態機單元405用作Hash表進行快速的匹配字符搜索。LZ77 主控狀態機單元 405，主要利用 Headl Hash 表 401、PrevI Hash402 表、Head2Hash表403、Prev2 Hash表404完成對原始數據塊的LZ77編碼過程，並完成對原始數據塊的CRC32校驗過程並統計出原始文件的大小，LZ77主控狀態機也為動態新字符/匹配長度Huffman編碼單元、動態指回距離Huffman編碼單元及數據打包單元提供必要的信息，主要包括CRC32校驗的結果、原始數據塊的大小、待壓縮文件的大小。ROM查找表單元406，在LZ77主控狀態機單元405對原始數據塊CRC32校驗時，需要利用ROM中固化的數據進行計算。新字符/匹配長度緩存單元407，主要用於存放LZ77對原始數據進行編碼輸出的新字符或者是匹配長度。指回距離緩存單元408，主要用於存放LZ77對原始數據進行編碼輸出的指回距離。圖5示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態新字符/匹配長度Huffman編碼頻率統計控制單元的具體實施方式
的工作流程示意圖。如圖5所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態新字符/匹配長度Huffman編碼頻率統計控制單元的具體實施方式
的工作流程500進一步包括
步驟501，動態新字符/匹配長度Huffman編碼頻率統計控制單元的主控狀態機從LZ77編碼模塊中接收一個新字符/匹配長度，進入步驟502。步驟502，動態新字符/匹配長度Huffman編碼頻率統計控制單元的主控狀態機對接收到的這個新字符/匹配長度進行判斷，如果接收到的是匹配長度進入步驟503，否則進入步驟504。步驟503，將接收到的匹配長度查詢動態新字符/匹配長度Huffman樹字符表，將接收到的匹配長度映射到動態新字符/匹配長度Huffman樹字符表中對應的葉子節點，進入步驟504。步驟504，動態新字符/匹配長度Huffman編碼頻率統計控制單元的主控狀態機將新字符/匹配長度頻率緩存單元中對應的節點單元加I，進入步驟505。
步驟505，判斷工作是否結束，如果沒有結束就進入步驟501繼續準備接收下一個字符，否則就進入結束狀態。圖6示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態指回距離Huffman編碼頻率統計控制單元的具體實施方式
的工作流程示意圖。如圖6所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態指回距離Huffman編碼頻率統計控制單元的具體實施方式
的工作流程600進一步包括
步驟601，動態指回距離Huffman編碼頻率統計控制單元的主控狀態機從LZ77編碼單元中接收一個指回距離，進入步驟602。前提是LZ77編碼單元此時發現了匹配字符串，並輸出了指回距離，否則該模塊不工作。步驟602，將接收到的指回距離用作索引查詢動態指回距離Huffman樹字符表，將指回距離映射到動態指回距離Huffman樹字符表中的葉子節點,進入步驟603。
步驟603，動態指回距離Huffman編碼頻率統計控制單元的主控狀態機將指回距離頻率緩存單元中對應的單元加1，進入步驟604。步驟604，判斷工作過程是否結束，如果沒有結束就進入步驟601開始接收下一個LZ77編碼單元輸出的指回距離，否則就進入結束狀態。圖7示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態新字符/匹配長度Huffman編碼單元的具體實施方式
的結構示意圖。如圖7所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態新字符/匹配長度Huffman編碼單元的具體實施方式
的結構700進一步包括
數據選擇單元701，用來控制新字符/匹配長度頻率緩存單元702的控制權，在字符的統計階段，數據選擇單元701選擇動態新字符/匹配長度Huffman頻率統計單元去控制新字符/匹配長度頻率緩存單元702 ;在構建Huffman樹階段，數據選擇單元701選擇動態新字符/匹配長度Huffman編碼主控狀態機單元707去控制新字符/匹配長度頻率緩存單元702。新字符/匹配長度頻率緩存單元702，用來存放動態新字符/匹配長度Huffman樹中每一個節點的頻率，包括葉子節點、中間節點和根節點。數據選擇單元703，用來控制新字符/匹配長度碼字長度緩存單元704的控制權。在構建Huffman樹的過程中，數據選擇單元703選擇動態新字符/匹配長度Huffman編碼主控狀態機707去控制新字符/匹配長度碼字長度緩存單元704 ;在Huffman樹、Huffman表構建完畢數據選擇單元703選擇數據打包單元去控制新字符/匹配長度碼字長度緩存單元 704。新字符/匹配長度碼字長度緩存單元704，主要用來存放動態新字符/匹配長度Huffman樹中每一個節點的碼字長度。數據選擇單元705，主要是用來控制新字符/匹配長度碼字值緩存單元706的控制權。在構建Huffman樹的過程中，數據選擇單元705選擇新字符/匹配長度Huffman編碼主控狀態機去控制碼字值緩存單元706，在得到碼字長度及碼字值之後，數據選擇單元去選擇數據打包單元去控制新字符/匹配長度碼字值緩存單元706。新字符/匹配長度碼字值緩存單元706，主要是用來存放新字符/匹配長度Huffman樹中每一個葉子節點的碼字值。
動態新字符/匹配長度Huffman編碼主控狀態機單元707，在新字符/匹配長度頻率緩存單元702中得到Huffman樹中每一個葉子的頻率之後，動態新字符/匹配長度Huffman主控狀態機單元707根據新字符/匹配長度頻率緩存單元中存放的每一個字符頻率，並利用新字符/匹配長度最小堆緩存單元709、新字符/匹配長度深度緩存單元710、新字符/匹配長度父親節點緩存單元711去構建Huffman樹,並計算出Huffman表,在這個過程中動態新字符/匹配長度Huffman編碼主控狀態機單元707還利用新字符/匹配長度頻率緩存單元702中存放的每一個字符的頻率信息和流水線乘法器單元708去計算待壓縮數據經過動態新字符/匹配長度Huffman編碼之後的大小。流水線乘法器單元708，動態新字符/匹配長度主控狀態機單元707主要用流水線乘法器單元708來計算存放在新字符/匹配長度頻率緩存單元702中字符出現的頻率和新字符/匹配長度碼字長度緩存單元706中對應的Huffman編碼的碼字長度的乘法計算。新字符/匹配長度最小堆緩存單元709，新字符/匹配長度最小堆緩存單元709前 半部分主要用來維護新字符/匹配長度頻率緩存單元702中出現的字符，使得這些字符在物理上呈現連續存儲，在邏輯上構成一棵二叉樹，並且這棵二叉樹滿足左節點和右節點大於或者等於本節點，其中葉子節點除外。新字符/匹配長度最小堆緩存單元709的後半部分主要是用來存放新字符/匹配長度Huffman樹。新字符/匹配長度深度緩存單元710，主要是用來存放新字符/匹配長度Huffman樹中每一個節點的深度，其中根節點的深度最大，葉子節點的深度是O。新字符/匹配長度父親節點緩存單元711，主要是用來存放新字符/匹配長度Huffman樹中每一個節點的父親節點，其中根節點除外。在新字符/匹配長度Huffman工作結束，在新字符/匹配長度碼字長度緩存單元704和碼字值緩存單元706中得到了每一個葉子節點的碼字長度和碼字值，Huffman工作結束，此時新字符/匹配長度Huffman編碼單元就把新字符/匹配長度碼字長度緩存單元704和碼字值緩存單元706的控制權交給數據打包單元。圖8示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態指回距離Huffman編碼單元的具體實施方式
的結構示意圖。如圖8所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態指回距離Huffman編碼單元的具體實施方式
的結構800進一步包括
數據選擇單元801，用來控制指回距離頻率緩存單元802的控制權，在字符的統計階段，數據選擇單元801選擇動態指回距離Huffman頻率統計單元去控制指回距離頻率緩存單元802 ;在構建Huffman樹階段,數據選擇單元801選擇動態指回距離Huffman編碼主控狀態機單元807去控制指回距離頻率緩存單元802。指回距離頻率緩存單元802,用來存放動態指回距離Huffman樹中每一個節點的頻率，包括葉子節點、中間節點和根節點。數據選擇單元803，用來控制指回距離碼字長度緩存單元804的控制權。在構建Huffman樹的過程中，數據選擇單元803選擇動態指回距離Huffman編碼主控狀態機807去控制指回距離碼字長度緩存單元804 ;在Huffman樹、Huffman表構建完畢數據選擇單元803選擇數據打包單元去控制指回距離碼字長度緩存單元804。指回距離碼字長度緩存單元804，主要用來存放動態指回距離Huffman樹中每一個節點的碼字長度。數據選擇單元805，主要是用來控制指回距離碼字值緩存單元806的控制權。在構建Huffman樹的過程中，數據選擇單元805選擇指回距離Huffman編碼主控狀態機去控制碼字值緩存單元806，在得到碼字長度及碼字值之後，數據選擇單元805選擇數據打包單元去控制指回距離碼字值緩存單元806。指回距離碼字值緩存單元806，主要是用來存放指回距離Huffman樹中每一個葉子節點的碼字值。動態指回距離Huffman編碼主控狀態機單元807，在指回距離頻率緩存單元802中得到Huffman樹中每一個葉子的頻率之後,動態指回距離Huffman主控狀態機單元807根據指回距離頻率緩存單元中存放的每一個字符頻率，並利用指回距離最小堆緩存單元809、指回距離深度緩存單元810、指回距離父親節點緩存單元811去構建Huffman樹,並計算出Huffman表,在這個過程中動態指回距離Huffman編碼主控狀態機單元807還利用指回距離頻率緩存單元802中存放的每一個字符的頻率信息和流水線乘法器單元808去計算待壓縮 數據經過動態指回距離Huffman編碼之後的大小。流水線乘法器單元808，動態指回距離主控狀態機單元807主要用流水線乘法器單元808來計算存放在指回距離頻率緩存單元802中字符出現的頻率和指回距離碼字長度緩存單元806中對應的Huffman編碼的碼字長度的乘法計算。指回距離最小堆緩存單元809，指回距離最小堆緩存單元809前半部分主要用來維護指回距離頻率緩存單元802中出現的字符，使得這些字符在物理上呈現連續存儲，在邏輯上構成一棵二叉樹，並且這棵二叉樹滿足左節點和右節點大於或者等於本節點，其中葉子節點除外。指回距離最小堆緩存單元809的後半部分主要是用來存放指回距離Huffman 樹。指回距離深度緩存單元810，主要是用來存放指回距離Huffman樹中每一個節點的深度，其中根節點的深度最大，葉子節點的深度是O。指回距離父親節點緩存單元811，主要是用來存放指回距離Huffman樹中每一個節點的父親節點，其中根節點除外。在指回距離Huffman工作結束，在指回距離碼字長度緩存單元804和碼字值緩存單元806中得到了每一個葉子節點的碼字長度和碼字值，Huffman工作結束，此時指回距離Huffman編碼單元就把指回距離碼字長度緩存單元804和碼字值緩存單元806的控制權交給數據打包單元。圖9示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態碼字長度Huffman編碼單元的具體實施方式
的結構示意圖。如圖9所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中動態碼字長度Huffman編碼單元的具體實施方式
的結構900進一步包括
碼字長度數據統計單元901，主要是用來從圖7中新字符/匹配長度碼字長度緩存單元704和圖8中指回距離碼字長度緩存單元804中讀取每一個葉子節點的碼字長度，並進行統計。數據選擇單元902，用來控制碼字長度頻率緩存單元903的控制權，在字符的統計階段，數據選擇單元902選擇碼字長度數據統計單元901去控制碼字長度頻率緩存單元903 ;在構建Huffman樹階段，數據選擇單元902選擇動態碼字長度Huffman編碼主控狀態機單元910去控制碼字長度頻率緩存單元903。碼字長度頻率緩存單元903，用來存放動態碼字長度Huffman樹中每一個節點的頻率，包括葉子節點、中間節點和根節點。數據選擇單元904，用來控制碼字長度的碼字長度緩存單元905的控制權。在構建Huffman樹的過程中，數據選擇單元904選擇動態碼字長度Huffman編碼主控狀態機910去控制碼字長度的碼字長度緩存單元905 ;在Huffman樹、Huffman表構建完畢數據選擇單元904選擇數據打包單元去控制碼字長度的碼字長度緩存單元905。碼字長度的碼字長度緩存單元905，主要用來存放動態碼字長度Huffman樹中每一個節點的碼字長度。數據選擇單元906，主要是用來控制碼字長度碼字值緩存單元907的控制權。在構 建Huffman樹的過程中，數據選擇單元906選擇碼字長度Huffman編碼主控狀態機單元910去控制碼字長度碼字值緩存單元907，在得到碼字長度及碼字值之後，數據選擇單元906選擇數據打包單元去控制碼字長度碼字值緩存單元907。碼字長度碼字值緩存單元907，主要是用來存放碼字長度Huffman樹中每一個葉子節點的碼字值。數據選擇單元908，主要是用來選擇碼字長度葉子節點緩存單元909的控制權，在數據統計階段，數據選擇單元908選擇動態碼字長度Huffman編碼主控狀態機單元910去控制碼字長度葉子節點緩存單元；在得到碼字長度的碼字長度及碼字長度的碼字值之後，數據選擇單元908選擇數據打包單元去控制碼字長度葉子節點緩存單元909。碼字長度葉子節點緩存單元909，主要是用來存放碼字長度Huffman樹中所有的葉子節點。動態碼字長度Huffman編碼主控狀態機單元910，在碼字長度頻率緩存單元903中得到Huffman樹中每一個葉子的頻率之後,動態碼字長度Huffman主控狀態機單元910根據碼字長度頻率緩存單元903中存放的每一個字符頻率，並利用碼字長度最小堆緩存單元912、碼字長度深度緩存單元913、碼字長度父親節點緩存單元914去構建Huffman樹，並計算出Huffman表,在這個過程中動態碼字長度Huffman編碼主控狀態機單元910還利用碼字長度頻率緩存單元903中存放的每一個字符的頻率信息和流水線乘法器單元911去計算待壓縮數據經過動態碼字長度Huffman編碼之後的大小。流水線乘法器單元911，動態碼字長度主控狀態機單元910主要用流水線乘法器單元911來計算存放在碼字長度頻率緩存單元903中字符出現的頻率和碼字長度的碼字長度緩存單元905中對應的Huffman編碼的碼字長度的乘法計算。碼字長度最小堆緩存單元912，碼字長度最小堆緩存單元912前半部分主要用來維護碼字長度頻率緩存單元903中出現的字符，使得這些字符在物理上呈現連續存儲，在邏輯上構成一棵二叉樹，並且這棵二叉樹滿足左節點和右節點大於或者等於本節點，其中葉子節點除外。碼字長度最小堆緩存單元912的後半部分主要是用來存放碼字長度Huffman 樹。碼字長度深度緩存單元913，主要是用來存放碼字長度Huffman樹中每一個節點的深度，其中根節點的深度最大，葉子節點的深度是O。
碼字長度父親節點緩存單元914，主要是用來存放碼字長度Huffman樹中每一個節點的父親節點，其中根節點除外。數據選擇單元915，主要是用來控制碼字長度重複次數緩存單元916的控制權，在構造Huffman樹的過程中，數據選擇單元915選擇碼字長度Huffman編碼主控狀態機單元910去控制碼字長度重複次數緩存單元916，在碼字長度Huffman樹及碼字長度Huffman表構建完畢，數據選擇單元915選擇數據打包單元去控制碼字長度重複次數緩存單元。碼字長度重複次數緩存單元916，主要是用來存放碼字長度Huffman樹中每一個葉子節點的重複次數。在碼字長度Huffman工作結束，在碼字長度的碼字長度緩存單元905和碼字值緩存單元907中得到了每一個葉子節點的碼字長度和碼字值，Huffman工作結束，此時碼字長度Huffman編碼單元就把碼字長度的碼字長度緩存單元905和碼字值緩存單元907的控制權交給數據打包單元。 圖10示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中靜態新字符/匹配長度Huffman編碼單元的具體實施方式
的結構示意圖。如圖10所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中靜態新字符/匹配長度Huffman編碼單元的具體實施方式
的結構1000進一步包括
數據打包單元1001，主要完成對LZ77編碼單元中存放在新字符/匹配長度緩存單元中的新字符/匹配長度進行靜態Huffman編碼。靜態新字符/匹配長度碼字長度常數表單元1002，主要用來存放新字符/匹配長度對應的Huffman編碼的碼字長度，設計中可以使用R0M，即只讀存儲器去加以實現。靜態新字符/匹配長度碼字值緩存單元1003，主要是用來存放新字符/匹配長度對應的Huffman編碼的碼字值，設計中可以使用R0M，即只讀存儲器加以實現。流水線乘法器單元1004，主要是用來計算對存放在LZ77編碼單元中新字符/匹配長度緩存單元中的新字符/匹配長度進行靜態Huffman編碼之後數據的大小。在圖10中，Literal_length[8:0]是讀取的新字符或者是匹配長度，Code [8:0] >CodeJength [3:0]分別是用來輸出新字符或者是匹配長度對應的靜態Huffman碼字值和碼字長度，Static_literal_length[31:0]主要是輸出待壓縮數據經過靜態新字符/匹配長度Huffman編碼之後的大小。圖11示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中靜態指回距離Huffman編碼單元的具體實施方式
的結構示意圖。如圖11所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中靜態指回距離Huffman編碼單元的具體實施方式
的結構1100進一步包括
數據打包單元1101，主要完成對LZ77編碼單元中存放在指回距離緩存單元中的指回距尚進行靜態Huffman編碼。靜態指回距離碼字值緩存單元1102，主要是用來存放指回距離對應的Huffman編碼的碼字值，設計中可以使用R0M，即只讀存儲器加以實現。流水線乘法器單元1103，主要是用來計算對存放在LZ77編碼單元中指回距離緩存單元中的指回距離進行靜態指回距離Huffman編碼之後數據的大小。在圖11 中，Distance[14:0]是讀取的指回距離，Code[4:0],Code_length[2:0]分別是用來輸出指回距離對應的靜態Huffman碼字值和碼字長度，在靜態指回距離Huffman編碼中碼字長度固定為5比特位寬，Static_literal_length[31:0]主要是輸出待壓縮數據經過靜態指回距離Huffman編碼之後的大小。圖12示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中數據打包單元的具體實施方式
的結構示意圖。在圖12中，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中數據打包單元的具體實施方式
的結構1200進一步包括
動態碼字長度的碼字長度緩存單元1201，主要是用來存放動態碼字長度Huffman樹中每一個節點的碼字長度，與圖9中的動態碼字長度的碼字長度緩存單元905是復用的。動態碼字長度碼字值緩存單元1202，主要是用來存放動態碼字長度Huffman樹中 每一個葉子節點的碼字值，與圖9中的動態碼字長度碼字值緩存單元907是復用的。靜態指回距離碼字值緩存單元1203，主要是用來存放指回距離的靜態Huffman編碼值，與圖11中的靜態指回距離碼字值單元1102是復用的。輸入數據緩存單元1204，主要是用來存放原始的待壓縮的數據，與圖3中的數據緩存單元303及304單元是復用的。新字符/匹配長度緩存單元1205，主要是用來存放LZ77編碼單元輸出的新字符/匹配長度，與圖4中新字符/匹配長度緩存單元407是復用的。指回距離緩存單元1206，主要是用來存放LZ77編碼單元輸出的指回距離，與圖4中的指回距離緩存單元408是復用的。動態新字符/匹配長度碼字值緩存單元1207，主要是用來存放動態新字符/匹配長度Huffman樹中所有葉子節點的碼字值，與圖7中的動態新字符/匹配長度碼字值緩存單元706是復用的。動態新字符/匹配長度碼字長度緩存單元1208，主要是用來存放動態新字符/匹配長度Huffman樹中所有節點的碼字長度，與圖7中的動態新字符/匹配長度碼字長度緩存單元704是復用的。靜態新字符/匹配長度碼字值緩存單元1209，主用是用來存放新字符/匹配長度的靜態Huffman編碼的碼字值，與圖10中的靜態新字符/匹配長度碼字值緩存單元1003是復用的。靜態新字符/匹配長度碼字長度緩存單元1210，主要是用來存放新字符/匹配長度的靜態Huffman編碼的碼字長度，與圖10中的靜態新字符/匹配長度碼字長度緩存單元1002是復用的。動態指回距離碼字值緩存單元1211，主要是用來存放動態指回距離Huffman樹中所有葉子節點的碼字值，與圖8中的動態指回距離碼字值緩存單元806是復用的。變長碼字打包單元1212，主要是接收讀取變長碼字單元送來的碼字值及碼字長度將這些變長碼字打包成64比特位寬輸出到輸出緩存單元中。動態指回距離碼字長度緩存單元1213，主要是用來存放動態指回距離Huffman樹中所有節點的碼字長度，與圖8中的動態指回距離碼字長度緩存單元804是復用的。動態碼字長度重複次數緩存單元1214，主要是用來存放動態碼字長度Huffman樹中所有葉子節點的重複次數，與圖9中動態碼字長度重複次數緩存單元916是復用的。
動態碼字長度葉子節點緩存單元1215，主要是用來存放動態碼字長度Huffman樹中所有的葉子節點，與圖9中的動態碼字長度葉子節點緩存單元909是復用的。讀取變長碼字單元1216，主要是用來根據圖4中LZ77編碼單元、圖7中動態新字符/匹配長度Huffman編碼單元、圖8中動態指回距離Huffman編碼單元、圖9中動態碼字長度Huffman編碼單元、圖10中靜態新字符/匹配長度Huffman編碼單元、圖11中靜態指回距離Huffman編碼單元送出的結果進行判斷，根據判斷的結果採用直接存儲、動態Huffman編碼、靜態Huffman編碼三種壓縮模式中的一種對待壓縮的數據塊進行壓縮，進而從數據緩存單元1201-1211，1213-1215中按照特定的順序讀取數據並將讀取的變長碼字交給變長碼字打包單元輸出。圖13示出本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中輸出緩存單元的具體實施方式
的結構示意圖。如圖13所示，本發明提供的一種GZIP壓縮硬體系統實現的一個實施例中輸出緩存單元的具體實施方式
的結構1300進一步包括
FIFO緩存單元1301，主要是用來接收數據打包單元1302發送出來的壓縮之後的數據。數據打包單元1302，主要是用來編碼輸出數據，與圖12中的數據打包單元是復用的。圖14示出本發明提供的一種GZIP壓縮硬體系統加速方法中雙Head/Prev加速方法的具體實施方式
結構示意圖。如圖14所示，本發明提供的一種GZIP壓縮硬體系統加速方法中雙Head/Prev加速方法的具體實施方式
結構進一步包括
Headl Hash 查找表 1401、Prev I Hash 查找表 1402、Head2 Hash 查找表 1404、Prev2Hash查找表1405，主要是用來存放待壓縮數據中出現的每一個字符的地址，每次使用之前都需要對 Headl Hash 查找表 1401、Prev I Hash 查找表 1402、Head2 Hash 查找表 1404、Prev2 Hash查找表1405進行清空，然後再使用，這裡的Headl Hash查找表1401、Prev IHash 查找表 1402、Head2 Hash 查找表 1404、Prev2 Hash 查找表 1405 與圖 4 中的 HeadlHash 查找表 401、Prevl Hash 查找表 402、Head2 Hash 查找表 403、Prev2 Hash 查找表 404是對應復用的。LZ77主控狀態機單元1403，主要是利用Headl Hash查找表1401、Prev I Hash查找表1402、Head2 Hash查找表1404、Prev2 Hash查找表1405完成數據塊的LZ77編碼過程，與圖4中的LZ77主控狀態機單元405是復用的。圖15示出本發明提供的一種GZIP壓縮硬體系統加速方法中雙Head/Prev加速方法的具體實施方式
的工作流程示意圖。如圖15所示，本發明提供的一種GZIP壓縮硬體系統加速方法中雙Head/Prev加速方法的具體實施方式
的工作流程1500進一步包括
步驟1501，清空Headl和Prevl，清空完成進入步驟1502。步驟1502，利用步驟1501中清空好的Headl Hash查找表和Prevl Hash查找表開始壓縮第一個數據塊，在壓縮第一個數據塊的同時，完成對Head2 Hash表和Prev2 Hash表的清空，處理完成之後就進入步驟1503。步驟1503，利用步驟1502中清空好的Head2 Hash表盒Prev2 Hash表開始壓縮第二個數據塊，在壓縮第二個數據塊的同時也完成對Headl Hash表和Prevl Hash表的清空，處理完成之後就進入步驟1504。步驟1504，開始利用步驟1503中清空好的Headl Hash表和Prevl Hash表對第三個數據塊的壓縮，在壓縮的同時完成對Head2 Hash表和Prev2 Hash表的清空。按照上述的操作步驟，一直到所有的數據塊都被壓縮完畢，這裡首次採用的雙Head和Prev的結構去壓縮數據，顯著地提升了數據的吞吐率。圖16示出本發明提供的一種GZIP壓縮硬體系統加速方法中Huffman提前統計加速方法的具體實施方式
的結構示意圖。如圖16所示，本發明提供的一種GZIP壓縮硬體系統加速方法中Huffman提前統計加速方法的具體實施方式
的結構1600進一步包括 LZ77編碼單元1601，主要完成對待壓縮數據的LZ77編碼，與圖I中LZ77編碼單元104是復用的。新字符/匹配長度或者是指回距離緩存單元1602，主要是用來存放新字符/匹配長度或者是指回距離，與圖4中的新字符/匹配長度緩存單元407或者是指回距離緩存單元408是復用的。頻率統計控制單元1603，主要是用來接收來自LZ77編碼單元輸出的新字符/匹配長度或者是指回距離，並進行統計，與圖I中的動態新字符/匹配長度Huffman編碼頻率統計控制單元102或者是動態指回距離Huffman編碼頻率統計控制單元103是復用的。頻率緩存單元1604，主要是用來存放動態Huffman樹中所有的節點的頻率，與圖7中新字符/匹配長度頻率緩存單元702或者是圖8中的指回距離頻率緩存單元802是復用的。由圖16中可以看出，本發明提供的這種方法可以同時完成字符的存儲及統計，完全並行的工作，從提升了 Huffman編碼的數據吞吐率。圖17示出本發明提供的一種GZIP壓縮硬體系統加速方法中Huffman提前清空加速方法的具體實施方式
的工作流程示意圖。如圖17所示，本發明提供的一種GZIP壓縮硬體系統加速方法中Huffman提前清空加速方法的具體實施方式
的工作流程1700進一步包括
步驟1701，在進行對第一個數據塊進行Huffman編碼之前完成對頻率緩存單元的清空，清空好之後進入步驟1702。步驟1702，主要是完成對待壓縮數據中出現的字符進行統計，統計好之後進入步驟 1705。步驟1705，根據步驟1702統計的結果建立Huffman樹，Huffman樹建好之後就進入步驟1706。步驟1706,根據步驟1705建立的Huffman樹得出Huffman表,得到Huffman表之後存放在頻率緩存單元中的數據就不再有用，接著同時完成步驟1703和步驟1704。步驟1703，完成對待壓縮數據塊的Huffman編碼過程。步驟1704，完成頻率緩存單元的清空，步驟1703和步驟1704是同時進行，在步驟1703和步驟1704都完成之後就進入步驟1702，開始準備處理下一個數據塊。從圖17中可以看出，步驟1703與步驟1704是完全並行的工作，從而提升了Huffman編碼的數據吞吐率。圖18示出本發明提供的一種GZIP壓縮硬體系統加速方法中CRC32穿插計算的具體實施方式
的工作流程示意圖。如圖18所示，本發明提供的一種GZIP壓縮硬體系統加速方法中CRC32穿插計算的具體實施方式
的工作流程1800進一步包括
步驟1801，讀取一個字符，準備進行LZ77編碼，進入步驟1802。步驟1802，從當前的這個字符開始進行匹配字符串的查找過程，利用讀取Hash表的時間去完成當前字符的CRC32校驗計算，進而進入步驟1803。步驟1803，判斷處理是否結束，如果沒有，繼續執行步驟1801，否則就進入結束狀 態。從圖18中可以看出，重複利用了 LZ77逐個處理字符的特性，且在編碼的過程中會查詢Hash表，利用這樣的時間空隙完成CRC32校驗計算，從而數據吞吐率得以提升。參考前述本發明示例性的描述，本領域技術人員可以知曉本發明具有以下優點 本發明提供了一種GZIP壓縮硬體系統實現的方法，並在FPGA上實現了 GZIP壓縮的基
本功能。本發明提供了一種GZIP壓縮硬體系統實現的方法，最終實現硬體實現與軟體實現相兼容，硬體壓縮之後，軟體可以進行正確的解壓。在本發明中，採用兵兵操作、雙Head和Prev Hash結構、Huffman提前統計、Huffman提前清空、CRC32穿插計算來提升GZIP壓縮的數據吞吐率，測試結果表明，GZIP壓縮硬體實現較軟體實現在數據吞吐率上有了大幅度的提升。儘管本發明此處具體化一些特定的例子示出和描述，然而本發明不限制於所示出的細節，因為在不偏離本發明的精神以及在權利要求的範圍和等同範圍內，可以作出多種改進和結構變化。因此，寬範圍地並且如權利要求中所闡明的在某種意義上與本發明的範圍一致地解釋附加的權利要求是適當的。
權利要求
1.一種基於GZIP的壓縮硬體系統，其特徵在於，該系統包括 一個輸入緩存單元，用於對輸入數據進行緩存； 一個LZ77編碼單元，用於對輸入數據進行LZ77編碼； 一個動態新字符/匹配長度Huffman編碼頻率統計控制單元，用於對LZ77編碼單元輸出的新字符以及匹配長度進行統計； 一個動態指回距離Huffman編碼頻率統計控制單元,用於對LZ77編碼單元輸出的指回距離進行統計； 一個動態新字符/匹配長度Huffman編碼單元，用於對LZ77編碼單元輸出的新字符以及匹配長度進行動態Huffman編碼； 一個動態指回距離Huffman編碼單元，用於對LZ77編碼單元輸出的指回距離進行動態Huffman 編碼； 一個動態碼字長度Huffman編碼單元,用於對動態新字符/匹配長度Huffman樹的信息及對動態指回距離Huffman樹的信息進行編碼； 一個靜態新字符/匹配長度Huffman編碼單元，用於對LZ77編碼單元輸出之後的新字符/匹配長度進行靜態Huffman編碼； 一個靜態指回距離Huffman編碼單元，用於對LZ77編碼單元輸出之後的指回距離進行靜態Huffman編碼； 一個數據打包單元，用於判斷採用直接存儲、靜態HufTman編碼以及動態HufTman編碼三種模式中的一種，並按照固定的格式進行編碼輸出； 一個輸出緩存單元，用於緩存數據打包單元輸出的壓縮之後的數據。
2.根據權利要求I所述的基於GZIP的壓縮硬體系統，其特徵在於，所述輸入緩存單元包括 兩個數據塊緩存單元，用於存放待壓縮的原始數據； 兩個數據選擇單元，用於控制數據塊緩存單元的讀寫控制權。
3.根據權利要求I所述的基於GZIP的壓縮硬體系統，其特徵在於，所述LZ77編碼單元包括 兩對Head/Prev Hash表，用於對LZ77編碼單元中編碼字符串的快速匹配查找； 一個只讀存儲單元ROM，用於存放循環冗餘校驗碼CRC32校驗計算時的常數表； 一個新字符/匹配長度緩存單元，用於存放LZ77編碼單元輸出之後的新字符或者是匹配長度； 一個指回距離緩存單元，用於存放LZ77編碼單元輸出之後的指回距離； 一個主控狀態機單元，用於對數據塊緩存單元中的數據進行數據讀取。
4.根據權利要求I所述的基於GZIP的壓縮硬體系統，其特徵在於，所述動態新字符/匹配長度Huffman編碼單元包括 一個新字符/匹配長度頻率緩存單元，用於存放LZ77編碼單元輸出之後新字符以及匹配長度的頻率； 一個新字符/匹配長度父親節點緩存單元，用於存放新字符以及匹配長度Huffman樹中每一個節點的父親節點，其中根節點除外； 一個新字符/匹配長度深度緩存單元，用於存放新字符以及匹配長度Huffman樹中每一個節點在新字符以及匹配長度Huffman樹中的深度； 一個新字符/匹配長度最小堆緩存單元，用於連續存放新字符以及匹配長度Huffman樹中所有的節點； 一個新字符/匹配長度碼字值緩存單元，用於存放新字符/匹配長度Huffman樹中所有的葉子節點對應的Huffman編碼的值； 一個新字符/匹配長度碼字長度緩存單元，用於存放新字符以及匹配長度Huffman樹中所有節點對應的一個Huffman編碼的有效長度； 3個數據選擇單元，分別用於控制新字符/匹配長度頻率緩存單元、新字符/匹配長度碼字值緩存單元、新字符/匹配長度碼字長度緩存單元的控制權；一個流水線乘法器單元，用於輔助計算數據塊經過動態新字符以及匹配長度Huffman編碼之後的大小； 一個主控狀態機單元，用來根據新字符/匹配長度頻率緩存單元中存放的待壓縮數據塊中每一個字符的頻率信息，利用新字符/匹配長度父親節點緩存單元、新字符/匹配長度深度緩存單元、新字符/匹配長度最小堆緩存單元去構造Huffman樹,並將Huffman樹的信息存放在新字符/匹配長度最小堆緩存單元中，在得到新字符/匹配長度Huffman樹的信息之後，主控狀態機單元遍歷Huffman樹得出Huffman樹中每一個節點的碼字長度,並對該節點加以判斷；如果是葉子節點，則所述主控狀態機單元繼續從新字符/匹配長度緩存單元中讀取該節點的頻率，並利用流水線乘法器單元去計算出當前的這個字符經過Huffman編碼之後的大小，再根據得出的Huffman樹中每一個節點的碼字長度去計算出Huffman樹中每一個節點的碼字值，主控狀態機單元對這些節點加以判斷，如果是葉子節點就將葉子節點的碼字值存放進新字符/匹配長度碼字值緩存單元中。
5.根據權利要求I所述的基於GZIP的壓縮硬體系統，其特徵在於，所述動態指回距離Huffman編碼單元包括 一個指回距離頻率緩存單元，用於存放LZ77編碼單元輸出之後指回距離的頻率； 一個指回距離父親節點緩存單元，用於存放指回距離Huffman樹中每一個節點的父親節點，其中根節點除外； 一個指回距離深度緩存單元，用於存放指回距離Huffman樹中每一個節點在指回距離Huffman樹中的深度； 一個指回距離最小堆緩存單元，用於連續存放指回距離Huffman樹中所有的節點； 一個指回距離碼字值緩存單元，用於存放指回距離Huffman樹中所有的葉子節點對應的Huffman編碼的值； 一個指回距離碼字長度緩存單元，用於存放指回距離Huffman樹中所有節點對應的Huffman編碼的有效長度； 3個數據選擇單元，分別用於控制指回距離頻率緩存單元、指回距離碼字值緩存單元、指回距離碼字長度緩存單元的控制權； 一個流水線乘法器單元，用於輔助計算數據塊經過動態指回距離Huffman編碼之後的大小； 一個主控狀態機單元，用來根據指回距離頻率緩存單元中存放的待壓縮數據塊中每一個字符的頻率信息，並利用指回距離父親節點緩存單元、指回距離深度緩存單元、指回距離最小堆緩存單元去構造HufTman樹,並將HufTman樹的信息存放在最小堆緩存單元中,在得到指回距離Huffman樹的信息之後,主控狀態機單元遍歷Huffman樹得出Huffman樹中每一個節點的碼字長度，並對該節點加以判斷，如果是葉子節點，主控狀態機單元將從新字符/匹配長度緩存單元中讀取該節點的頻率，利用流水線乘法器單元去計算出當前的這個字符經過Huffman編碼之後的大小，再根據得出的Huffman樹中每一個節點的碼字長度去計算出Huffman樹中每一個節點的碼字值,主控狀態機單元對這些節點加以判斷，如果是葉子節點就將葉子節點的碼字值存放進指回距離碼字值緩存單元中。
6.根據權利要求I所述的基於GZIP的壓縮硬體系統，其特徵在於，所述的動態碼字長度Huffman編碼單元包括 一個碼字長度數據統計單元，用於統計新字符/匹配長度碼字長度緩存單元和指回距 離碼字長度緩存單元中每一種碼字長度出現的頻率； 一個碼字長度頻率緩存單元，用於存放碼字長度數據統計單元統計的結果； 一個碼字長度父親節點緩存單元，用於存放碼字長度Huffman樹中每一個節點的父親節點； 一個碼字長度深度緩存單元，用於存放碼字長度Huffman樹中每一個節點的深度； 一個碼字長度小堆緩存單元，用於連續存放碼字長度HufTman樹中所有的節點； 一個碼字長度碼字值緩存單元，用於存放碼字長度Huffman樹中每一個葉子節點對應的Huffman編碼的值； 一個碼字長度的碼字長度緩存單元，用於存放碼字長度Huffman樹中所有節點對應的Huffman編碼的碼字長度； 一個碼字長度葉子節點緩存單元，用於存放對新字符/匹配長度碼字長度緩存單元和指回距離碼字長度緩存單元進行遍歷之後得到的碼字長度的葉子節點； 一個碼字長度重複次數緩存單元，用於存放遍歷之後碼字長度的重複次數； 5個數據選擇單元，分別用於控制碼字長度頻率緩存單元、碼字長度碼字值緩存單元、碼字長度的碼字長度緩存單元、碼字長度葉子節點緩存單元、碼字長度重複次數緩存單元的控制權； 一個流水線乘法器單元，用於計算數據塊經過動態碼字長度Huffman編碼之後的大小; 一個碼字長度主控狀態機，用於完成新字符/匹配長度碼字長度緩存單元和指回距離碼字長度緩存單元中遍歷所有葉子節點的碼字長度，並將統計的結果存放在碼字長度葉子節點緩存單元和碼字長度重複次數緩存單元中，將每一個葉子節點的頻率信息存放在碼字長度頻率緩存單元中。
7.根據權利要求I所述的基於GZIP的壓縮硬體系統，其特徵在於，所述的數據打包單元包括 讀取變長碼字單元，用於讀取LZ77編碼單元、動態新字符/匹配長度Huffman編碼單元、動態指回距離Huffman編碼單元和動態碼字長度Huffman編碼單元中相應的信息；變長碼字打包單元，根據讀取變長碼字單元提供的信息從而獲知針對當前數據塊所採用的壓縮模式。
8.—種如權利要求I所述的基於GZIP壓縮硬體系統的加速方法，其特徵在於，所述加速方法包括 輸入桌球操作在GZIP壓縮硬體系統中的應用，用於提升系統數據的吞吐率； 兩對 Head/Prev Hash 表，分別是 Headl/Prevl Hash 表方法和 Head2/Prev2 Hash 表方法，用來進一步提升系統數據的吞吐率； Huffman編碼統計提前，用於提升數據的吞吐率； Huffman編碼清空提前，用於提升數據的吞吐率 ； CRC32校驗穿插計算，利用LZ77編碼單元縮減數據處理的時鐘周期，提升數據的吞吐率。
全文摘要
本發明公布了一種基於GZIP的壓縮硬體系統及其加速方法，包括輸入緩存單元，用於對輸入數據進行緩存；LZ77編碼單元；動態新字符/匹配長度Huffman編碼頻率統計控制單元；動態指回距離Huffman編碼頻率統計控制單元；動態新字符/匹配長度Huffman編碼單元；動態指回距離Huffman編碼單元；動態碼字長度Huffman編碼單元；靜態新字符/匹配長度Huffman編碼單元；靜態指回距離Huffman編碼單元；數據打包單元；輸出緩存單元。本壓縮硬體系統可實現GZIP壓縮算法、做到與軟體實現相兼容、提升GZIP壓縮的數據吞吐率，使得數據壓縮過程中無需CPU的幹預。
文檔編號H03M7/30GK102970043SQ20121045864
公開日2013年3月13日 申請日期2012年11月14日 優先權日2012年11月14日
發明者湯曉東, 狄永清, 李冰, 李瑋 申請人:無錫芯響電子科技有限公司