文章转载自：FPGA的现今未
在基于FPGA的硬件加速领域，字符串匹配是一个常见的加速点。字符串匹配的算法很多很多，比较经典的算法是KMP，读者可以自行参考，本文主要介绍基于该算法演进的shift-and算法以及在FPGA中的实现。为什么shift-and算法比较适合FPGA中实现？我们先看看这个算法实现的过程。
算法讲解
shift-and算法理解起来可能有点复杂，我们先从一个例子来说明该算法的实现步骤。假定我们要在字符串 ashshifttb中检测是否存在字符串shift。其中 ashishifttb称为目标串，shift称为模式串。第一步：根据模式串，先创建一个B表。什么是B表，它是对模式串中某个字符是否存在的标记，它的宽度为模式串的长度。以shift为例，在建立B表时，依次对模式串的每个字符建表，s只在第一位，所以为00001，h只在第二位，所以为00010，对于其他没有的字符，比如a，则为00000。假定模式串为cityhash，对于h来说在第五和第八位，所以为10010000。
第三步：左移，即将当前的匹配结果左移一位，匹配结果为0的，左移一位后还是0；第五步：根据输入的字符查B表，得到该字符在B表中的值，然后与第四步的结果做一个“与”运算，得到一个新的匹配结果D。第六步：取下个字符，重复步骤三、四、五步。完成所有输入目标串的字符匹配。具体的匹配计算过程如下图所示：
如何理解这个算法？重点在匹配结果D，D中bit为1表示的就是在目标串中找到的和模式串有相同字符的最大位置。即模式串的前缀，也是目标串的后缀。比如shift这个字符串的长度为5，所以当D[4] = 1的时候，表示该字符串找到,匹配命中。
再看一个例子，能更好地说明上述算法的原理。假定模式串为zfzfc，目标串为xzfzfzfca，我们看看这个匹配过程：
当输入xzfz的时候，匹配结果是00101，它表示在目标串中找到了2个符合模式串前缀的字符串，分别为z和zfz，都有可能和模式串匹配成功。当输入第2个f的时候，匹配结果变成01010，还是找到了2个符合模式串前缀的字符串，分别为zf和zfzf。当输入第三个z的时候，注意匹配结果D的变化，又变成了00101，符合要求的字符串又变成z和zfz。
通过这个例子，我们可以看到匹配结果D中1的变化，就是匹配中的模式串前缀字符串的变化情况。当一个模式串长度为N的时候，只要D[N-1] = 1，就表示匹配命中。
FPGA的实现
在FPGA中如何实现这个算法？根据前面示例的步骤可以看出，这个是非常的简单，即每次读取一个目标串的字符，然后开始匹配得到匹配结果D，判断是否命中。这也是在FPGA方案中选择这种算法的一个优势。一个很简单的方案，那就是每个时钟周期消耗到一个字符，以200M的时钟为例，性能为200MB/s，这个性能相对较低，提升性能的方法有2个。第一个就是每个时钟周期消耗多个字符，比如4个字符，那么性能可以提升到800MB/s，单周期内消耗的字符越多，组合逻辑越大，所以在实践中需要根据项目的情况来确定单周期内消耗字符的个数；第二个就是多引擎，单个报文同时匹配多个字符串，或者同时匹配多个报文。按照4引擎，单周期消耗4个字符计算，那么性能为 200MB/s * 4 * 4 = 3.2GB/s。字符串匹配在数据中心和网络安全领域使用广泛，匹配算法仅仅是字符串匹配中的一个“核”，外围有大量和业务相关的逻辑，业务逻辑的也是影响性能的一个关键。总之，我们需要根据业务情况选择合适的匹配外围逻辑来达到一个最优的性能。
