想實現(xiàn)硬件regex匹配

cjaizss

想用在項目里，作為將來擴展的設(shè)計。不過確實有點困難，無論怎么搞，試試看吧。

wuchuanren

沙發(fā)一下……
對偶來說軟件實現(xiàn)一個NFA都沒感去想
支持

cjaizss

確實有難度，因為我需要運算的盡量快。暫時不想去接受所有的regex,而是只去處理DFA限定在一定范圍內(nèi)regex。
不過這也還是先等硬件架構(gòu)設(shè)計完之后再考慮了，呵呵

cjaizss

為了快速匹配以及避免難度，我的思路是準(zhǔn)備構(gòu)造一個狀態(tài)機的架子，然后把regex等價的狀態(tài)機往這個架子里填。只要regex的狀態(tài)機的規(guī)模不超過我設(shè)置的這個規(guī)模（其實我設(shè)置的這個規(guī)模也不會是很大的，一個很簡單的regex的狀態(tài)機就會很夸張了），那么我就可以填進(jìn)去

freearth

個人覺得可以這樣考慮：
不要試圖一次提供一個完整的DFA，這樣很難確定應(yīng)該有多少個狀態(tài)。狀態(tài)少的話可能會限制很多應(yīng)用。

建議采用另外一種思路：設(shè)計一套包含十幾條指令的專用指令系統(tǒng)，將狀態(tài)編號以整數(shù)的形式存在主存中（當(dāng)然，運行時在cache中，速度還是夠的）。這樣設(shè)計也許對于很小的DFA而言，不如直接用硬件實現(xiàn)快，但是這樣更加靈活，應(yīng)用面更廣，幾乎可以應(yīng)用所有的DFA。

這個設(shè)計的關(guān)鍵部分就是指令系統(tǒng)怎么設(shè)計。
這個指令系統(tǒng)至少要包含構(gòu)造正則表達(dá)式的幾個常用的操作。
1、原子表達(dá)式。
2、連接、選擇、重復(fù)

一、原子表達(dá)式可以這樣設(shè)計
       match arg
      其中arg是一個字母或者數(shù)字，該指令表示匹配這個字母或數(shù)字

二、連接
      con addr1, addr2
      首先執(zhí)行addr1中的指令，再執(zhí)行addr2中的指令。addr1和addr2中是另外兩個正則表達(dá)式匹配代碼
      選擇和重復(fù)的實現(xiàn)類似

三、輔助操作
      ldr rbase，arg
      rbase寄存器存放待匹配的字符串的首地址，字符串以0結(jié)束

      begin rend, addr2
      使用addr2中的指令進(jìn)行匹配字符串，將匹配到的字符串的最后一個字符的下一個地址放到寄存器rend中

      end
      標(biāo)志一個指令序列的結(jié)束

等等。

上面的東西只是提供一個思路，具體設(shè)計還要更加仔細(xì)的考慮。
另外，樓主的“項目”具體是什么？

原帖由 cjaizss 于 2008-8-13 12:56 發(fā)表
為了快速匹配以及避免難度，我的思路是準(zhǔn)備構(gòu)造一個狀態(tài)機的架子，然后把regex等價的狀態(tài)機往這個架子里填。只要regex的狀態(tài)機的規(guī)模不超過我設(shè)置的這個規(guī)模（其實我設(shè)置的這個規(guī)模也不會是很大的，一個很簡單的 ...

cjaizss

這個方法不符合我想追求高速度處理的目標(biāo)，肯定不會采用。
我要做的是一個硬件平臺，用于網(wǎng)絡(luò)設(shè)備。
一個clock的節(jié)省帶來的收益也是可觀的。
如果引入指令集，我還不如用CPU

ArsenalSrch

對這個話題很感興趣，不知道樓主有進(jìn)展否