想实现硬件regex匹配
想用在项目里，作为将来扩展的设计。不过确实有点困难，无论怎么搞，试试看吧。 沙发一下……对偶来说软件实现一个NFA都没感去想
支持:em02: 确实有难度，因为我需要运算的尽量快。暂时不想去接受所有的regex,而是只去处理DFA限定在一定范围内regex。
不过这也还是先等硬件架构设计完之后再考虑了，呵呵 为了快速匹配以及避免难度，我的思路是准备构造一个状态机的架子，然后把regex等价的状态机往这个架子里填。只要regex的状态机的规模不超过我设置的这个规模（其实我设置的这个规模也不会是很大的，一个很简单的regex的状态机就会很夸张了），那么我就可以填进去 个人觉得可以这样考虑：
不要试图一次提供一个完整的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 发表 http://linux.chinaunix.net/bbs/images/common/back.gif
为了快速匹配以及避免难度，我的思路是准备构造一个状态机的架子，然后把regex等价的状态机往这个架子里填。只要regex的状态机的规模不超过我设置的这个规模（其实我设置的这个规模也不会是很大的，一个很简单的 ...
回复 #5 freearth 的帖子
这个方法不符合我想追求高速度处理的目标，肯定不会采用。我要做的是一个硬件平台，用于网络设备。
一个clock的节省带来的收益也是可观的。
如果引入指令集，我还不如用CPU 对这个话题很感兴趣，不知道楼主有进展否
页:
[1]