本文转载自： FPGA的现今未微信公众号
注：本文由作者授权转发，如需转载请联系作者本人
前面介绍了CityHash32中前3种场景下的算法实现，这里继续介绍最后一种，也是最复杂的一种，因为输入数据的长度是不固定的。
Hash32LenBt24算法是针对输入字符串总长度大于24所采用的算法，算法过程分为3个主要部分：前处理、输入迭代、后处理。
前处理
Hash32LenBt24算法的前处理主要是将报文长度len和该字符串最后的20个字符（20byte)进行计算，输出h、g、f三个值，作为后续划窗运算的初始值。计算过程如下：
前处理流程说明：
（1）按顺序截取该字符串最后的20个字符，将最后20个字符按照4个字节为一组，划分为5组数据（如图中B0~B4, B0代表最后20个字节的最开始4个字节，而B4代表最后20个字节的最后4个字节)，。
（2）图中的C1和C2均为常数，C1=0xcc9e2d51，C2=0x1b873593
（3）图中的Rote函数为前文介绍的循环右移函数。
（4）图中hMur函数计算过程如下：
（5）函数的名字为自己定义的，这个函数的计算过程其实和Mur函数后半段计算过程一模一样，所以起名hMur，表示halfMur函数。
输入迭代
基于前处理计算的h、g、f值作为迭代运算的三个初始值，同时将输入字符长度按照20个字节为粒度划分成n块（n=(len-1)/20)，执行n轮迭代，每轮迭代的输入为上一轮计算的h、g、f值和当前轮对应的20字节块。输入单次迭代计算过程如下：
输入迭代流程说明：
（1）init: h/f/g为前处理输入的初始值，第1轮迭代时使用，第2轮及后续迭代使用其前1轮迭代h/f/g结果
（2）B0/B1/B2/B3/B4为当前迭代轮输入的20个字节，B0对应起始4个字节，以此类推
（3）C1和C2是常数，C1=0xcc9e2d51，C2=0x1b873593
（4）Bswap为按字节倒序
（5）最后一个方框实现h、f、g数据交换，交换方式是f→h，g→f，h→g接口
（6）n不包括最后1块，即当len是20的整数m倍时，n为倍数m-1。当len不是20的整数倍时，n不包含最后剩余不足20byte的块。
后处理
输入迭代处理完成后，输出h、f、g三个数据，基于这3个数据进行后处理计算，计算过程如下：
后处理流程说明:
（1）C1是常数，C1=0xcc9e2d51
总结，在实际应用中，CityHash32的4种模式并不需要都实现，根据自己业务的场景，选择其中一种模式即可。它良好的分布特性使得非常适合在FPGA上应用，尤其是对冲突设计比较复杂的场景下。
关于CityHash有任何问题，欢迎留言交流。
