本文转载自： FPGA的现今未微信公众号
Hash是FPGA设计中非常常见的一个功能。它是将一个Mbyte长度的数据通过hash计算变成一个Nbyte长度的数据，其中M >> N。即y = f(x)，根据这个特点，Hash在FPGA中最常见的应用场景就是类似bloom filter，比如应用在5元组匹配、字符串匹配等。我们知道不同x通过hash计算得到的y肯定不同，但是不同x通过hash计算可能得到相同的y，这就是hash冲突。常见的解决方案就是增加逃生桶或者链表来解决这个问题，冲突越严重（即大量不同x通过hash计算得到相同的y），FPGA设计的难度也就越大。
这里自然就会想到一个问题，如果hash分布越平均，冲突就相对来说就会越小。CityHash满足这个特性，可以有效地缓解冲突问题。
CityHash算法由Google公司于2013年公布，该算法的开发受到了前人在散列算法方面的巨大启发，尤其是Austin Appleby的MurmurHash，MurMurHash由Austin Appleby在2008年发明，与其它流行的哈希函数相比，对于规律性较强的key，MurMurHash的随机分布特征表现更良好，即冲突相对较小，这对FPGA的设计来说就是优势。
Google源码中有CityHash32、CityHash64、CityHash128，对于FPGA的设计来说，CityHash32是比较合适的，本文以CityHash32为例子来说明算法。
CityHash32根据输入长度的不同，分成4个不同的算法，如下图所示：
Hash32Len0to4：对于输入字符串长度小于等于4时，使用该算法；
Hash32Len5to12：对于输入字符串长度大于4小于等于12，使用该算法；
Hash32Len13to24：对于输入字符串长度大于12小于等于24，使用该算法；
Hash32LenBt24：对于输入字符串长度大于24时，使用该算法；
在介绍CityHash算法前，我们先介绍几个算子，这些算子是构成整个CityHash算法的基础。
Rotate32函数
该函数是对32bit数据进行循环右移操作，如下图：
static uint32 Rotate32(uint32 val, int shift) {
// Avoid shifting by 32: doing so yields an undefined result.
return shift == 0 ? val : ((val >> shift) | (val << (32 - shift)));
}
Mur函数
该函数主要是基于Austin Appleby的MurmurHash算法，实现2个32bit数据的组合，计算流程如下：
说明：
（1）输入为2个32bit无符号整型数据a、h，输出out也是一个32bit无符号整型数据
（2）图中圆圈代表运算符，其中*是截位乘法（即不考虑溢出），^是按位异或，+是截位加法（即不考虑溢出）；
（3）Rota是上文中描述的32bit循环右移，括号中的数字表示循环右移的bit数
（4）c1、c2、c3、c4是常数（其中c1和c2是Murmur3哈希算法使用的魔术字），c1=0xcc9e2d51；c2=0x1b873593；c3=0x5; c4=0xe6546b64。
参考代码如下:
static uint32 Mur(uint32 a, uint32 h) {
// Helper from Murmur3 for combining two 32-bit values.
// c1=0xcc9e2d51；c2=0x1b873593；
a *= c1;
a = Rotate32(a, 17);
a *= c2;
h ^= a;
h = Rotate32(h, 19);
return h * 5 + 0xe6546b64;
}
fmix函数
该函数也是来源于Murmur3哈希算法，主要实现32bit到32bit的整数hash计算，计算流程如下：
说明：
（1）输入in为32bit无符号整数，输出out为32bit无符号整数
（2）图中>>表示逻辑右移，对应下标表示逻辑右移位数；^表示按位异或；*表示截位乘法；+表示截位加法。
（3）c1和c2为常数，其中c1=0x85ebca6b；c2=0xc2b2ae35。
参考代码如下：
static uint32 fmix(uint32 h)
{
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;
return h;
}
下面我们具体看下这4种场景的实现
Hash32Len0to4算法
该算法的实现方案如下图所示：
它主要包含2个步骤：
输入迭代
以输入字节为单位进行多轮迭代计算（计算过程如上图虚线框所示），计算出两个32bit无符号整数值b、c。说明如下：
（1）init表示初始值，对于b的初始值为0，c的初始值为9；
（2）In[i]表示输入字符串中某个字符。i的取值范围是[0, len-1]。每输入1个字符，输出一个b、c结果。当前输入in[i]字符基于in[i-1]计算出来的b、c值进行迭代运算；当in[len-1]最后1个字符计算完成后，输出b、c值进行下一阶段计算（最大迭代次数为4）
（3）迭代运算中c1是常数值，c1=0xcc9e2d51。图中^表示按位异或；*表示截位乘法；+表示截位加法。
Murmur哈希
当输入迭代完成后输出一个b、c值，结合字符串的长度len，进行hash运算。包含了2次Mur运算和1次fmix运算。
实现源码如下图所示：
static uint32 Hash32Len0to4(const char *s, size_t len) {
uint32 b = 0;
uint32 c = 9;
for (size_t i = 0; i < len; i++) {
signed char v = s[i];
b = b * c1 + v;
c ^= b;
}
return fmix(Mur(b, Mur(len, c)));
}
Hash32Len5to12算法
该算法的实现方案如下图所示，相比len0to4要复杂一些。
在流程上，也主要包含2个步骤
输入分割计算
将输入数据按照图中所示分割成3部分，并和长度len或是常数值c1进行计算：
（1）输入in[0:3]和长度len值相加，输出a；
（2）输入in[len-4:le-1]（即取最后4个字节）和len的5倍（c2=0x5）相加，输出b；
（3）当字符串长度len大于等于8时，选择in[4:7]，否则选择in[0:3]和常数c1（c1=-0x9）相加，输出c；
（4）len乘以5，输出d。
Murmur哈希
对a、b、c、d四个数进行哈希计算
（1）a和d进行Mur哈希计算，输出Mur(a,d)
（2）Mur(a,d)和b进行Mur哈希计算，输出Mur(b, Mur(a,d))
（3）Mur(b, Mur(a,d))和c进行Mur哈希计算，输出Mur(c, Mur(b, Mur(a,d))）
（4）Mur(c, Mur(b, Mur(a,d)))执行fmix计算
实现源码如下所示：
static uint32 Hash32Len5to12(const char *s, size_t len) {
uint32 a = len, b = len * 5, c = 9, d = b;
a += Fetch32(s);
b += Fetch32(s + len - 4);
c += Fetch32(s + ((len >> 1) & 4));
return fmix(Mur(c, Mur(b, Mur(a, d))));
}
Hash32Len13to24算法
该算法主要分成2个步骤：
输入分割
将输入分割成6份，每份4字节：
（1）a等于该字符串的中线前4个字符
（2）b等于该字符串起始前8个字符中的后4个字符
（3）c等于该字符串最后8个字符的前4个字符
（4）d等于该字符串的中线后4个字符
（5）e等于该字符串起始前8个字节中的前4个字符
（6）f等于该字符串最后8个字符的后4个字符
Murmur哈希
（1）a和d进行Mur哈希计算，输出Mur(a,d)
（2）Mur(a,d)和b进行Mur哈希计算，输出Mur(b, Mur(a,d))
（3）Mur(b, Mur(a,d))和c进行Mur哈希计算，输出Mur(c, Mur(b, Mur(a,d)))
（4）Mur(c, Mur(b, Mur(a,d)))和d进行哈希计算，输出Mur(d, Mur(c, Mur(b, Mur(a,d))))
（5）Mur(d, Mur(c, Mur(b, Mur(a,d))))和e进行哈希计算，输出Mur(e, Mur(d, Mur(c, Mur(b, Mur(a,d)))))
（6）Mur(e, Mur(d, Mur(c, Mur(b, Mur(a,d)))))和f进行哈希计算，输出Mur(f, Mur(e, Mur(d, Mur(c, Mur(b, Mur(a,d))))))
（7）Mur(f, Mur(e, Mur(d, Mur(c, Mur(b, Mur(a,d))))))进行Fmix哈希计算
源码如下：
static uint32 Hash32Len13to24(const char *s, size_t len) {
uint32 a = Fetch32(s - 4 + (len >> 1));
uint32 b = Fetch32(s + 4);
uint32 c = Fetch32(s + len - 8);
uint32 d = Fetch32(s + (len >> 1));
uint32 e = Fetch32(s);
uint32 f = Fetch32(s + len - 4);
uint32 h = len;
return fmix(Mur(f, Mur(e, Mur(d, Mur(c, Mur(b, Mur(a, h)))))));
}
待续……
关于CityHash更完整的信息可以参考：
CityHash源码：https://github.com/google/cityhash
google主页：https://opensource.googleblog.com/2011/04/introducing-cityhash.html
