3

在过去的几天里，我一直在研究拉宾指纹。虽然总体思路很简单，但我在理解网络上流传的实现时遇到了很大的麻烦。特别是它们似乎都源自原始的LBFS 论文，即来自librabinpoly的滑动窗口定义为：

33 static u_int64_t slide8(RabinPoly *rp, unsigned char m) {                       
   34         rp->circbuf_pos++;                                                      
   35         if (rp->circbuf_pos >= rp->window_size) {                               
   36                 rp->circbuf_pos = 0;                                            
   37         }                                                                       
   38         unsigned char om = rp->circbuf[rp->circbuf_pos];                        
   39         rp->circbuf[rp->circbuf_pos] = m;                                       
   40         return rp->fingerprint = append8 (rp, rp->fingerprint ^ rp->U[om], m);  
   41 }                                                                               
   42                                                                                 
   43 static u_int64_t append8(RabinPoly *rp, u_int64_t p, unsigned char m) {         
   44         return ((p << 8) | m) ^ rp->T[p >> rp->shift];                          
   45 }

U/T 表是从初始多项式生成的。我没有在任何有关 rabin 指纹识别的论文中看到讨论这两个表的用法和 XOR 操作。我的直觉是这与模运算有关，但我不完全确定。Git 的源代码也使用 rabin 指纹识别，但它们不是动态地派生表，而是使用一组预先计算的表。所以我的问题是 - 这些 Xor 操作究竟能实现什么，并且代码通常看起来与算法的“规范”解释完全不同

4

1 回答 1

1

“规范解释”使用不是拉宾指纹的滚动哈希。不过，它非常相似。在不深入研究抽象代数的情况下，两者背后的想法是评估从特定环中的消息派生的多项式，它有 0、1、加法、减法、乘法但没有除法（整数 mod m 用于规范解释；GF(2 k )用于 Rabin 指纹，也就是说，系数为 2 的多项式，以 k 次不可约多项式为模）。

最简单的环是整数 mod 2，它有 0、1 并定义

+  0 1        -  0 1        *  0 1
------        ------        ------
0  0 1        0  0 1        0  0 0
1  1 0        1  1 0        0  0 1  .

发生了一件很有趣的事情：加号和减号的定义相同，都等价于异或。使用计算机单词来表示系数为 2 的多项式，我们可以使用按位异或来加减多项式。这就是 XOR 出现在 中的原因rp->fingerprint ^ rp->U[om]：我们使用U表格从刚刚离开窗口的字节中减去该术语，因为该术语只有 256 种可能性。

XOR 的另一个用途((p << 8) | m) ^ rp->T[p >> rp->shift]是用不可约多项式修改的表达式，即在规范解释中用 m 修改的等价物。如果我们通过多项式长除法（T大概是如何计算表格）来做到这一点，我们会注意到从被除数中减去的项（在环中）仅由高位决定（p >> rp->shift） . 稍后进行一些代数操作，我们可以缓存和（在环中）并从被除数中减去它（在环中，所以按位异或）（((p << 8) | m)）。

为了完整起见，请注意这p << 8相当于多项式乘以 x 8。

于 2020-08-12T13:53:00.480 回答