基于FPGA的LZO實(shí)時(shí)無(wú)損壓縮的硬件設(shè)計(jì)

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

　　(1)分離雙端口RAM

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

　　(2)塊標(biāo)記

　　LZO壓縮算法在壓縮每個(gè)數(shù)據(jù)塊之前都要對(duì)字典模塊進(jìn)行初始化為0的操作，即對(duì)RAM進(jìn)行寫0操作，然而寫0操作會(huì)耗費(fèi)若干個(gè)周期。若字典模塊深度為16K，即RAM的深度為16K，當(dāng)進(jìn)行寫0操作時(shí)至少花費(fèi)16K個(gè)周期。通常解決此類問(wèn)題的一種方法是采用乒乓操作的方式，即用兩個(gè)字典來(lái)交替處理。為了解決初始化帶來(lái)的時(shí)間花費(fèi)和資源消耗的問(wèn)題，本文提出一種如圖3(C)所示的塊標(biāo)記字典結(jié)構(gòu)，該結(jié)構(gòu)主要包括：LZSS壓縮控制模塊，用于產(chǎn)生壓縮信息，即字符索引及字符所對(duì)應(yīng)的Hash值;flag產(chǎn)生模塊，用于產(chǎn)生0或者1兩種flag標(biāo)識(shí)，表示是當(dāng)前數(shù)據(jù)塊還是歷史數(shù)據(jù)塊;信息合并模塊，用于將字符索引和flag標(biāo)識(shí)進(jìn)行合并，然后存入字典模塊。整個(gè)結(jié)構(gòu)的工作原理可歸納如下：flag標(biāo)識(shí)0或1表示是當(dāng)前數(shù)據(jù)塊或歷史數(shù)據(jù)塊，如壓縮第一個(gè)數(shù)據(jù)塊時(shí)標(biāo)識(shí)為0，壓縮第二個(gè)數(shù)據(jù)塊時(shí)標(biāo)識(shí)為1，壓縮第三個(gè)數(shù)據(jù)塊時(shí)標(biāo)識(shí)為0，壓縮第四個(gè)數(shù)據(jù)塊時(shí)標(biāo)識(shí)為1，如此進(jìn)行反復(fù);LZSS壓縮控制模塊產(chǎn)生字符索引然后與flag進(jìn)行合并共同存入通過(guò)字符計(jì)算出的Hash值對(duì)應(yīng)的地址處。例如，現(xiàn)假設(shè)已經(jīng)壓縮到第二個(gè)數(shù)據(jù)塊，則根據(jù)上面的工作原理可知，當(dāng)前的標(biāo)識(shí)應(yīng)該為1，在壓縮時(shí)取出字典中的信息并判斷第一個(gè)bit位，如果第一個(gè)bit位為0則說(shuō)明該壓縮信息是歷史數(shù)據(jù)塊，壓縮信息無(wú)效;如果第一個(gè)bit位為1則說(shuō)明可能是當(dāng)前數(shù)據(jù)塊(因?yàn)橐灿锌赡苁呛芫靡郧暗臄?shù)據(jù)塊)，根據(jù)壓縮信息取出相應(yīng)字符進(jìn)行比對(duì)確認(rèn)。

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

　　(3)字典分離

　　軟件在實(shí)現(xiàn)LZO壓縮算法過(guò)程中，當(dāng)碰撞發(fā)生時(shí)，LZO壓縮算法會(huì)進(jìn)行第二次Hash操作，該次Hash操作在第一次Hash操作的基礎(chǔ)上進(jìn)行偏移。為了提升LZO壓縮算法的壓縮率，本文提出一種如圖3(D)所示的字典分離的結(jié)構(gòu)，當(dāng)Hash碰撞發(fā)生時(shí)，LZO壓縮算法進(jìn)行第二次Hash操作，但第二次Hash操作對(duì)應(yīng)的字符串索引不再存入第一個(gè)字典中，而是單獨(dú)開(kāi)辟一塊RAM空間進(jìn)行存儲(chǔ)。字典分離結(jié)構(gòu)的總存儲(chǔ)空間增加了字典2的大小，這樣在壓縮文件的過(guò)程中，文件的壓縮信息量也會(huì)增加?？梢?jiàn)，該結(jié)構(gòu)可以改進(jìn)LZO壓縮算法的壓縮率。