??想了解更多關于開源的內容，請訪問：??

??51CTO 開源基礎軟件社區??

??https://ost.51cto.com??

【技術DNA】

【智慧場景】

引言：

著高質量多媒體服務的增加，數據壓縮已成為使用存儲的電子設備的必要條件。

多年來，移動通信和視頻服務的質量不斷提高，傳輸和存儲數據的需求呈爆炸式增長。對大容量存儲和傳輸的需求增長速度至少是存儲和傳輸容量增長的兩倍。本文將為大家介紹一種基于 LZ4 的改進算法和一種優化的移動設備硬件結構。

應用場景

1、移動通信

2、視頻服務

移動設備約束條件

• 近年來，隨著物聯網等場景的不斷發展，一些問題也逐漸的暴露了出來，就比如嵌入式設備上的CPU時鐘頻率?，電源等資源都是有限的；對于部分設備來說可能換個時鐘頻率高的時鐘、換個大的電池確實可以解決問題，但對于手機這種嵌入式移動設備來說，像是要做到便攜、輕薄等等要求，體積就被限制住了，電源也因此被限制住了。
• 因此，需要一種基于硬件的壓縮方法來解決這個問題。

本方案的解法

基于字典的自適應壓縮方法都起源于Lempel-Ziv 算法,LZ4 是最快的壓縮算法之一。

但下面我們將為大家介紹一種先進的算法和硬件架構，提高了壓縮比和速度。為了獲得更高的壓縮比，本算法可變長度格式，而LZ4 采用定長格式。實驗結果表明，該體系結構的壓縮吞吐量可達 3.84Gbps，壓縮比可達4 。

通過這種方式，我們基于硬件的架構以低功耗提高了移動設備的內存性能和電池壽命。

LZ4 分析

• LZ4 是 LZ77 的一個變種算法，是 Collet 在2011年提出的固定的（fixed），面向字節（byte-oriented）的算法。
• LZ4 的伸縮數據如圖所示，它由令牌（Token） 、 字面量長度（Literal length） 、 偏移量（Offset） 和 匹配長度（Match length）組成。
• LZ4 和 LZ77 類似，它有一個滑動窗口，由一個搜索緩沖區?和一個向前查找緩沖區組成。
• LZ4 搜索之前沒有壓縮數據流中的重復數據，并用索引替換它。
• LZ4 通過哈希表來匹配數據，從而提高了壓縮速度。

令牌（Token）

• 令牌（Token） 長一個字節，其中前4個字節為字面量長度（Literal Length）?，其后四個字節為匹配長度（Match Length）。
• Token[3:0]?表示匹配長度，表示 0 ~ 15 的文字長度。
• Token[7:4]?表示字面量長度?，是比較不重要的位，匹配長度從0 ~ 15。

• Token [7:4]的值如果為0，則代表沒有文字。
• Token [7:4]的值如果為15，則表示文字長度必須有從 0~255 的額外字節來表示字面量的完整長度。
• Token [3:0]?的如果值為0，則表示最小匹配長度為4，稱為min match。
• 因此，Token [3:0]?的值從0到15意味著匹配長度值從4到19。如果Token[3:0]的值為15，則匹配長度中有更多字節。

字面量長度（Literal Length）

• 當Token[7:4]?值為 15 時，字面值長度（Literal Length）就是額外的字節。
• 如果字面量長度?為 0~254，則沒有更多的字節。如果字面量長度是255，在下一個字面量長度中有產生更多的字節。

偏移量（Offset）

• 偏移量（Offset）?占用2字節，采用little-endian格式，它表示要復制的匹配的位置。
• 偏移值為 1 表示當前位置為 1 byte。最大偏移量為 65535。

匹配長度（Match Length）

• 匹配長度（Match Length）?類似于上面說到的字面量長度（Literal Length）。
• 當Token[3:0]?達到可能的最高值 15 時，額外的字節被添加到匹配長度中。

總結

• LZ4 總是為偏移量（Match Length）分配 2字節，但其實這對壓縮比的性能影響不大。
• LZ4算法最初是為了在一般處理器上進行軟件實現而提出的，因此在一些硬件上實現 LZ4 存在一定的約束。

改進的LZ4

本文作者改進了LZ4的數據格式的序列?和哈希計算。

• 通過指定壓縮單元的大小，可以優化哈希表的大小。
• 將壓縮單元的大小設置為 4KB，可以為內存頁進行優化并節省內部內存。

數據格式

• 這里作者改變了 LZ4的首部（Header）?和偏移量（Offset），下圖分別是 改進后的 LZ4 與 LZ4 的格式。

首部（Header）

• 頭部位于每個壓縮單元的開頭，包含壓縮大小（Compressed Size）?和原始標志（Raw Flag）。
• 如果壓縮后的數據大小?大于原始數據大小?，則原始標志（Raw Flag）?則被標記為1?，原始數據?將被添加在首部（Header）?之后，壓縮符號將不被添加，解壓器也不需要解壓該壓縮單元。
• 在數據根本沒有壓縮的最壞情況下，原始標志（Raw Flag）使解壓縮程序更快。
• 在最壞的情況下，壓縮單元大小被添加到原始數據的頭部大小中。

偏移量（Offset）

• 偏移量（Offset）?由大小標志（Size Flag）?和偏移量大小（Offset Size）組成。
• 大小標志（Size Flag）?是最重要的位。如果大小標志?值為 0，偏移量大小?則使用 7 bit，即{offset [7]， offset[6:0]}。
• 如果大小標志?值為 1，偏移量大小?則使用 15 bit，即{offset [15]， offset[14:0]}。
• 偏移量大小表示匹配的位置，最大偏移大小值為32768。
• 可變偏移字節長度使我們的方法比LZ4有更好的壓縮比。哈希計算
• 哈希函數的目的是將任意大小的數據映射到固定大小的數據。對于匹配檢測，使用哈希表的搜索算法要比其他算法快得多。
• 理想的哈希表的大小是輸入數據位乘以壓縮單位字節的大小。但是，由于哈希表的大小是有限的，因此哈希計算計算輸入的比特數要比輸入的比特數小。
• 哈希計算的性能取決于不同的輸入得到相同結果的頻率。
• LZ4的哈希計算算法基于Fibonacci哈希原理，計算公式如下：

• 上述公式中的IN?為32位值，LZ4的哈希計算公式在硬件上實現復雜，并且計算周期長。于是作者改進了該哈希計算公式，公式如下：

• 這里壓縮單元大小為4KB，改進后的公式被 12 bit 屏蔽，僅使用位操作就可以將32位輸入映射到12位。因此，一個很小的硬件資源就足以計算改進后的哈希計算公式，并且只需要一兩個周期。

建議的硬件架構

總模塊

• 這里作者提出了一種建議使用的硬件架構。它主要由核心模塊(壓縮模塊和解壓縮模塊)和高級微控制器總線體系結構（AMBA）接口組成，實現應用處理器的互連。
• 核心模塊通過高級外設總線（APB）與處理器?進行控制信號通信。輸入數據和輸出數據通過高級可擴展總線（AXI）處理。
• 下圖為總體的硬件架構：

• 下表描述了是各個模塊的數量，面積以及總面積。

壓縮模塊

• 壓縮模塊主要由SRAM控制組件、哈希計算組件、字節匹配組件和流生成組件?組成，下圖為壓縮模塊的架構圖。

• 為了避免數據輸入的瓶頸，壓縮模塊將輸入數據寫入8個獨立的SRAM。
• 之后壓縮機從SRAM移位寄存器讀取128 bit 數據。
• 對于每個 4 byte 的輸入數據，哈希計算模塊計算哈希值，讀取哈希表來比較和更新索引。
• 如果在哈希表中搜索計算出來的哈希值，則移動到該位置并開始匹配字節。當匹配長度大于4時，因為哈希值已經從前面的文字計算出來了，此時可以跳過哈希計算。
• 壓縮單元最后一次數據處理完畢后，壓縮機檢查壓縮尺寸是否大于原始尺寸。如果大于原始尺寸，壓縮模塊將原始標志（Raw Flag）?設置到首部（Header）并輸出原始數據。
• 當壓縮內存數據時，對于未壓縮的頁，只將頁頭寫入輸出。在這種情況下，CPU讀取頭中的原始標志（Raw Flag）?，解壓時執行memcpy

解壓縮模塊

• 解壓縮模塊比壓縮模塊簡單，它主要由SRAM控制組件、流解析組件和緩沖區組件組成。

• 解析器流通過從SRAM讀取輸入數據來解析報頭和每個符號。
• 字面量通過復制文字長度從輸入數據中獲得的
• 匹配部分是通過匹配長度從已經解壓的數據中的偏移位置復制的。
• 如果與當前數據的偏移距離太近，后續管道可能不會寫入數據。因此便有了緩沖區來保存沒有寫入的數據。

實驗及結果

• 在這里，作者將提出的設計與原來的 LZ4 進行了比較，并展示了壓縮比與壓縮速度以及各種數據類型之間的關系，這些數據類型包括二進制數據、文本數據、Android應用程序包、字體數據、JPEG圖像以及 HTML頁面數據。
• 本實驗所提出設計運行在 400MHz 的處理環境下。數據的吞吐量也取決于總線條件，在考慮總線條件的情況下，要考慮整個模塊的壓縮速率。

• 由圖 【壓縮比與壓縮速度的關系】 可知，壓縮比與壓縮速率呈線性關系。
• 較低的壓縮比意味著大多數的輸入字節都被處理，因此壓縮速率變慢。
• 相反地，壓縮速率很快的情況下，將會跳過部分匹配的字節，壓縮比會增大。
• 總的來說，壓縮速率取決于壓縮比，壓縮速率也與壓縮比呈正比。?

• 由于在LZ4中有一個加速選項，加速值越高，壓縮越快；相應的，壓縮比會降低。這里便有了上述兩圖與LZ4各加速方案進行了比較的實驗。

總結

本文提出了一種改進的 LZ4 算法和硬件結構。可變長的偏移量、優化的哈希算法以及硬件流水線都提高了壓縮速率和壓縮比。

• 該設計可實現高達3.84Gbps的壓縮吞吐量和高達4的壓縮比。
• 它的壓縮速度比 LZ4 算法快4%，壓縮比比 LZ4 算法高5%，但它的最高時鐘頻率比 LZ4 慢。
• 文中所提出的硬件架構可以針對移動設備環境進行優化，因此它不僅可以用于壓縮移動設備中的內部存儲，還可以用于壓縮RAM，從而有望提高內存性能。
• 該硬件架構還可以實現低電流驅動和低功耗驅動，從而提高電池壽命。?

??想了解更多關于開源的內容，請訪問：??

??51CTO 開源基礎軟件社區??

??https://ost.51cto.com??。