c - 拉宾指纹表

Question

过去几天我一直在研究 rabin 指纹识别。虽然总体思路很简单，但我在理解网络上流传的实现时遇到了很大的困难。特别是所有这些似乎都源自原始 LBFS paper ，即来自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 指纹识别相关的论文中看到讨论这 2 个表的用法和 XOR 操作。我的直觉是这与模运算有关，但我不完全确定。 Git's source code还使用 rabin 指纹识别，但不是动态派生表，而是使用一组预先计算的表。所以我的问题是 - 这些 Xor 操作究竟实现了什么，代码通常看起来与“规范”explanation of the algorithm 有很大不同。

Answer 1

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

最简单的环是整数模 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  .

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

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

为了完整起见，请注意 p << 8等价于 x⁸ 的多项式乘法。