[發(fā)明專(zhuān)利]用于加速壓縮和解壓縮操作的處理器和方法以及相關(guān)聯(lián)的非瞬態(tài)機(jī)器可讀存儲(chǔ)介質(zhì)

有效

• 申請(qǐng)?zhí)枺?/td>: 201480031123.X
• 申請(qǐng)日: 2014-06-13
• 公開(kāi)（公告）號(hào): CN105264490B
• 公開(kāi)（公告）日: 2018-07-24
• 發(fā)明（設(shè)計(jì)）人: V·戈帕爾;J·D·吉爾福德;G·M·沃爾里齊
• 申請(qǐng)（專(zhuān)利權(quán)）人: 英特爾公司
• 主分類(lèi)號(hào): G06F9/30
• 分類(lèi)號(hào): G06F9/30;G06F9/38
• 代理公司: 上海專(zhuān)利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 高見(jiàn)

描述了一種處理器，該處理器包括具有指令獲取單元以獲取和解碼指令的指令執(zhí)行流水線(xiàn)。該處理器還具有用于執(zhí)行指令的執(zhí)行單元。該執(zhí)行單元具有狀態(tài)機(jī)和內(nèi)容可尋址存儲(chǔ)器(CAM)電路。狀態(tài)機(jī)將接收指向DEFLATE編碼信息流的指針，獲取DEFLATE編碼的信息的部分，并將DEFLATE編碼信息的該部分應(yīng)用到CAM，以獲得解碼的DEFLATE信息。

技術(shù)領(lǐng)域

本申請(qǐng)涉及計(jì)算機(jī)架構(gòu)的領(lǐng)域，更具體地，涉及用于加速壓縮和解壓縮操作的設(shè)備以及方法。

背景技術(shù)

LZ77壓縮算法。壓縮算法力求減少數(shù)據(jù)量，而不會(huì)犧牲數(shù)據(jù)內(nèi)的信息。被稱(chēng)為L(zhǎng)Z77算法的一種壓縮算法，通過(guò)參考在輸入(未經(jīng)壓縮的)數(shù)據(jù)流中較早存在的數(shù)據(jù)的單個(gè)復(fù)制，替換該數(shù)據(jù)的重復(fù)的出現(xiàn)，來(lái)實(shí)現(xiàn)壓縮。通過(guò)叫做長(zhǎng)度-距離對(duì)的一對(duì)數(shù)字(“距離”有時(shí)叫做“偏移”)，來(lái)編碼匹配。

為對(duì)準(zhǔn)匹配，編碼器跟蹤某些量的最近的數(shù)據(jù)，諸如最后2kB、4kB，或32kB。此數(shù)據(jù)被保留在其中的結(jié)構(gòu)叫做“滑動(dòng)窗口”(如此，LZ77有時(shí)叫做滑動(dòng)窗口壓縮)。編碼器將最近的數(shù)據(jù)保留在滑動(dòng)窗口內(nèi)，以查找匹配(解碼器同樣保留此數(shù)據(jù)，以解釋編碼器引用的匹配)。

圖1示出了LZ77編碼方案的簡(jiǎn)單示例。如在圖1中觀察到的，將比特流100的在前(較早或較舊)部分101的比特模式與比特流的當(dāng)前部分102 進(jìn)行比較。如果在當(dāng)前部分102中發(fā)現(xiàn)匹配在前部分101中的比特序列的比特序列，則將當(dāng)前部分102的比特序列替換為對(duì)較早部分101中的相同比特序列的引用。例如，當(dāng)前部分102的比特序列將被替換為對(duì)較早的部分101的比特序列103的引用。

針對(duì)比特序列102插入的引用標(biāo)識(shí)比特序列102的長(zhǎng)度104(其也與比特序列103的長(zhǎng)度相同)和比特序列103的位置。這里，比特序列103 的位置被表達(dá)為從當(dāng)前部分102到匹配的比特序列103的“距離”105。如此，LZ77壓縮方案將比特序列102編碼為被插入在比特流中代替序列102 的“長(zhǎng)度,距離對(duì)”。在解碼壓縮流時(shí)，當(dāng)解碼器到達(dá)被嵌入到比特流中代替比特序列102的長(zhǎng)度,距離對(duì)時(shí)，它簡(jiǎn)單地使用長(zhǎng)度,距離對(duì)的距離部分，以回頭引用比特序列103的開(kāi)始，并通過(guò)再現(xiàn)從比特序列103的開(kāi)始起的等于長(zhǎng)度,距離對(duì)的長(zhǎng)度分量的比特的數(shù)量，來(lái)再現(xiàn)解碼的流的部分102的正確的比特序列。

DEFLATE(緊縮)壓縮算法。被用來(lái)壓縮gzip、Zlib、PKZip和WinZip 文件的DEFLATE壓縮方案，與其他壓縮方案一起使用LZ77壓縮算法來(lái)執(zhí)行綜合的總體壓縮方案。

圖2示出了DEFLATE壓縮算法的總覽。如在圖2中觀察到的，在LZ77 壓縮之后，壓縮的比特流200可以被視為與數(shù)據(jù)符號(hào)(literal)202_1，202_2,... 202_N混合的一系列長(zhǎng)度/距離對(duì)201_1，201_2，...201_M。數(shù)據(jù)符號(hào)對(duì)應(yīng)于原始比特流內(nèi)的在轉(zhuǎn)換到長(zhǎng)度/距離對(duì)的適用的窗口內(nèi)沒(méi)有較早的相同的模式可被標(biāo)識(shí)的比特模式。

然后，DEFLATE壓縮算法繼續(xù)進(jìn)行以包括對(duì)LZ77壓縮流200的下一級(jí)壓縮203。下一級(jí)壓縮203引入了兩種不同類(lèi)型的霍夫曼編碼，它們一起將長(zhǎng)度/距離對(duì)201_1，201_2，...201_M和數(shù)據(jù)符號(hào)202_1，202_2,...202_N 的比較常見(jiàn)的比特模式替換為較小代碼204，并且將長(zhǎng)度/距離對(duì)201_1， 201_2，...201_M和數(shù)據(jù)符號(hào)202_1，202_2,...202_N的不太常見(jiàn)的比特模式替換為較大的代碼205。第一種類(lèi)型的霍夫曼編碼被用來(lái)編碼數(shù)據(jù)符號(hào)和長(zhǎng)度。第二種類(lèi)型的霍夫曼編碼被用來(lái)編碼距離。通過(guò)利用較少的比特來(lái)表示LZ77壓縮流200的更常見(jiàn)的比特模式，應(yīng)該減少在最后的DEFLATE 壓縮流206中存在的信息的總的大小。