2.2 LZO壓縮算法硬件加速方案

　　(1)分離雙端口RAM

　　為了加速LZO壓縮算法字符串的比對過程，本文提出如圖3(B)所示的分離雙端口RAM的結構，圖中的多路選擇器1用于將待壓縮數據交替式寫入雙端口RAM1和雙端口RAM2之一中，多路選擇器2用于將讀取的數據交替式輸出。例如，現有字符ABCDEFGHIJ要存入雙端口RAM中，具體如下：ABCD通過多路選擇器1被寫入RAM1中的data1處，EFGH通過多路選擇器1被寫入RAM2中的data2處，IJ通過多路選擇1被寫入data3，此時LZO壓縮算法模塊需要讀取字符串BCDE，則在讀取RAM1中data1處的BCD的同時讀取RAM2中data2處的E，即給RAM1讀地址的同時可以給RAM2讀地址，這樣同一時刻可以讀2處地址對應的內容。相比于一般性雙端口RAM結構，本結構可以實現一次完成讀取操作。做進一步擴展可得出如下結論：若RAM的寬度為W，則讀取字符數在2W以內時，采用分離雙端口RAM結構可以一次完成讀取操作;則讀取字符數在2~2W以內時，采用一般性雙端口RAM結構可能要讀兩次。當然，不僅RAM的寬度可以增加，RAM的個數也可以增加，當RAM的寬度和RAM個數越大時，完成讀操作只需一次的可能性就越大。

　　(2)塊標記

　　LZO壓縮算法在壓縮每個數據塊之前都要對字典模塊進行初始化為0的操作，即對RAM進行寫0操作，然而寫0操作會耗費若干個周期。若字典模塊深度為16K，即RAM的深度為16K，當進行寫0操作時至少花費16K個周期。通常解決此類問題的一種方法是采用乒乓操作的方式，即用兩個字典來交替處理。為了解決初始化帶來的時間花費和資源消耗的問題，本文提出一種如圖3(C)所示的塊標記字典結構，該結構主要包括：LZSS壓縮控制模塊，用于產生壓縮信息，即字符索引及字符所對應的Hash值;flag產生模塊，用于產生0或者1兩種flag標識，表示是當前數據塊還是歷史數據塊;信息合并模塊，用于將字符索引和flag標識進行合并，然后存入字典模塊。整個結構的工作原理可歸納如下：flag標識0或1表示是當前數據塊或歷史數據塊，如壓縮第一個數據塊時標識為0，壓縮第二個數據塊時標識為1，壓縮第三個數據塊時標識為0，壓縮第四個數據塊時標識為1，如此進行反復;LZSS壓縮控制模塊產生字符索引然后與flag進行合并共同存入通過字符計算出的Hash值對應的地址處。例如，現假設已經壓縮到第二個數據塊，則根據上面的工作原理可知，當前的標識應該為1，在壓縮時取出字典中的信息并判斷第一個bit位，如果第一個bit位為0則說明該壓縮信息是歷史數據塊，壓縮信息無效;如果第一個bit位為1則說明可能是當前數據塊(因為也有可能是很久以前的數據塊)，根據壓縮信息取出相應字符進行比對確認。

　　綜上所述，塊標記字典結構具有如下特點：無需初始化操作，避免了初始化過程帶來的時間花費;摒棄了乒乓操作的思想，節(jié)省了乒乓操作帶來的大量資源的消耗;該結構在片上資源緊缺的情況下是最優(yōu)的選擇。

　　(3)字典分離

　　軟件在實現LZO壓縮算法過程中，當碰撞發(fā)生時，LZO壓縮算法會進行第二次Hash操作，該次Hash操作在第一次Hash操作的基礎上進行偏移。為了提升LZO壓縮算法的壓縮率，本文提出一種如圖3(D)所示的字典分離的結構，當Hash碰撞發(fā)生時，LZO壓縮算法進行第二次Hash操作，但第二次Hash操作對應的字符串索引不再存入第一個字典中，而是單獨開辟一塊RAM空間進行存儲。字典分離結構的總存儲空間增加了字典2的大小，這樣在壓縮文件的過程中，文件的壓縮信息量也會增加?？梢姡摻Y構可以改進LZO壓縮算法的壓縮率。