想实现硬件regex匹配

cjaizss

想用在项目里，作为将来扩展的设计。不过确实有点困难，无论怎么搞，试试看吧。

wuchuanren

沙发一下……
对偶来说软件实现一个NFA都没感去想
支持

cjaizss

确实有难度，因为我需要运算的尽量快。暂时不想去接受所有的regex,而是只去处理DFA限定在一定范围内regex。
不过这也还是先等硬件架构设计完之后再考虑了，呵呵

cjaizss

为了快速匹配以及避免难度，我的思路是准备构造一个状态机的架子，然后把regex等价的状态机往这个架子里填。只要regex的状态机的规模不超过我设置的这个规模（其实我设置的这个规模也不会是很大的，一个很简单的regex的状态机就会很夸张了），那么我就可以填进去

freearth

个人觉得可以这样考虑：
不要试图一次提供一个完整的DFA，这样很难确定应该有多少个状态。状态少的话可能会限制很多应用。

建议采用另外一种思路：设计一套包含十几条指令的专用指令系统，将状态编号以整数的形式存在主存中（当然，运行时在cache中，速度还是够的）。这样设计也许对于很小的DFA而言，不如直接用硬件实现快，但是这样更加灵活，应用面更广，几乎可以应用所有的DFA。

这个设计的关键部分就是指令系统怎么设计。
这个指令系统至少要包含构造正则表达式的几个常用的操作。
1、原子表达式。
2、连接、选择、重复

一、原子表达式可以这样设计
       match arg
      其中arg是一个字母或者数字，该指令表示匹配这个字母或数字

二、连接
      con addr1, addr2
      首先执行addr1中的指令，再执行addr2中的指令。addr1和addr2中是另外两个正则表达式匹配代码
      选择和重复的实现类似

三、辅助操作
      ldr rbase，arg
      rbase寄存器存放待匹配的字符串的首地址，字符串以0结束

      begin rend, addr2
      使用addr2中的指令进行匹配字符串，将匹配到的字符串的最后一个字符的下一个地址放到寄存器rend中

      end
      标志一个指令序列的结束

等等。

上面的东西只是提供一个思路，具体设计还要更加仔细的考虑。
另外，楼主的“项目”具体是什么？

原帖由 cjaizss 于 2008-8-13 12:56 发表
为了快速匹配以及避免难度，我的思路是准备构造一个状态机的架子，然后把regex等价的状态机往这个架子里填。只要regex的状态机的规模不超过我设置的这个规模（其实我设置的这个规模也不会是很大的，一个很简单的 ...

cjaizss

这个方法不符合我想追求高速度处理的目标，肯定不会采用。
我要做的是一个硬件平台，用于网络设备。
一个clock的节省带来的收益也是可观的。
如果引入指令集，我还不如用CPU

ArsenalSrch

对这个话题很感兴趣，不知道楼主有进展否