[發明專利]用于計算滾動散列的技術

有效

• 申請號: 201580064889.2
• 申請日: 2015-11-25
• 公開（公告）號: CN107004015B
• 公開（公告）日: 2021-01-29
• 發明（設計）人: J·D·吉爾福德;V·戈帕爾;G·B·塔克
• 申請（專利權）人: 英特爾公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23;G06F16/174;H03M7/30
• 代理公司: 永新專利商標代理有限公司 72002
• 代理人: 王英;劉瑜

1.一種用于計算滾動散列的計算設備，所述計算設備包括：

第一散列表，其包括第一多個隨機值條目；

第二散列表，其包括第二多個隨機值條目；

散列生成模塊，其用于：(i)從數據緩沖區取回數據塊，并且(ii)基于所述數據塊、先前生成的散列、所述第一散列表、以及所述第二散列表而生成散列；以及

邊界識別模塊，其用于：(i)確定所生成的散列是否與預先定義的觸發相匹配，并且(ii)響應于確定所述所生成的散列與所述觸發相匹配而記錄數據邊界。

2.根據權利要求1所述的計算設備，其中，從所述數據緩沖區取回所述數據塊包括從所述數據緩沖區取回下一個字節的數據。

3.根據權利要求1所述的計算設備，其中，生成所述散列包括基于按位旋轉運算和按位異或運算來生成散列。

4.根據權利要求1所述的計算設備，其中，所述第二散列表包括被旋轉了表索引數的所述第一散列表中的隨機值條目，所述表索引數等于用于生成所述散列的散列算法的散列窗口大小。

5.根據權利要求4所述的計算設備，其中，生成所述散列包括根據hash＝(hash_prev1)^table1[buf[i]]^table2[buf[i-w]]來生成散列；

其中，hash_prev是所述先前生成的散列；

其中，hash_prev1表示對所述先前生成的散列的按位旋轉；

其中，^表示按位異或運算；

其中，w是所述散列算法的散列窗口大小；

其中，buf[i]是所述數據緩沖區的所取回的數據塊；

其中，buf[i-w]是被偏置了等于所述散列窗口大小的索引差的所述數據緩沖區的先前的數據塊；

其中，table1[buf[i]]是所述第一散列表中與所述所取回的數據塊相對應的隨機值條目；并且

其中，table2[buf[i-w]]是所述第二散列表中與所述先前的數據塊相對應的隨機值條目。

6.根據權利要求1所述的計算設備，其中，確定所述所生成的散列是否與所述預先定義的觸發相匹配包括將位掩碼應用至所述所生成的散列。

7.根據權利要求1所述的計算設備，其中，記錄所述數據邊界包括記錄數據去重邊界，所述數據去重邊界定義針對數據去重的數據分塊的邊界。

8.根據權利要求1所述的計算設備，還包括用于確定初始散列值的初始化模塊。

9.根據權利要求8所述的計算設備，其中，所述先前生成的散列是所述初始散列值。

10.根據權利要求1所述的計算設備，還包括用于將滾動散列算法初始化以生成所述散列的初始化模塊。

11.根據權利要求10所述的計算設備，其中，將所述滾動散列算法初始化包括確定所述數據緩沖區的大小。

12.根據權利要求10所述的計算設備，其中，將所述滾動散列算法初始化包括確定所述散列算法的散列窗口大小。

13.根據權利要求10所述的計算設備，其中，將所述滾動散列算法初始化包括確定與所述數據邊界相關聯的位掩碼和所述觸發。

14.根據權利要求10所述的計算設備，其中，將所述滾動散列算法初始化包括：

將具有所述第一多個隨機值條目的所述第一散列表初始化；以及

將具有所述第二多個隨機值條目的所述第二散列表初始化。