[發(fā)明專利]并行正則表達(dá)式匹配器

在審

• 申請(qǐng)?zhí)枺?/td>: 202110632853.7
• 申請(qǐng)日: 2021-06-07
• 公開(kāi)（公告）號(hào): CN113360726A
• 公開(kāi)（公告）日: 2021-09-07
• 發(fā)明（設(shè)計(jì)）人: 茍鵬飛;陸泳;劉揚(yáng)帆;徐越;楊浩;施葹
• 申請(qǐng)（專利權(quán)）人: 青芯半導(dǎo)體科技（上海）有限公司
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903;G06F16/901
• 代理公司: 上海智晟知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 31313
• 代理人: 張東梅

1.一種并行正則表達(dá)式匹配器，其特征在于，包括：

軟件預(yù)編譯單元，被配置為將正則表達(dá)式規(guī)則集中的多個(gè)正則表達(dá)式規(guī)則進(jìn)行預(yù)編譯，轉(zhuǎn)換為符合硬件處理行為的格式的正則表達(dá)式規(guī)則，以供硬件匹配電路進(jìn)行匹配；

硬件匹配電路，被配置為將待匹配報(bào)文和符合硬件處理行為的格式的正則表達(dá)式規(guī)則進(jìn)行匹配，得出匹配結(jié)果。

2.如權(quán)利要求1所述的并行正則表達(dá)式匹配器，其特征在于，所述軟件預(yù)編譯單元包括拆分模塊、狀態(tài)歸并模塊和配置表模塊，其中：

所述拆分模塊用于將多個(gè)正則表達(dá)式規(guī)則拆分為純字符串和正則單元；

所述狀態(tài)歸并模塊用于將純字符串和正則單元進(jìn)行狀態(tài)歸并，提取出相同的純字符串和正則單元，區(qū)分相異的純字符串和正則單元；

所述配置表模塊將純字符串和正則單元按符合硬件處理行為的格式封裝成正則表達(dá)式模式庫(kù)，以用于對(duì)硬件匹配電路進(jìn)行參數(shù)配置和狀態(tài)表初始化。

3.如權(quán)利要求2所述的并行正則表達(dá)式匹配器，其特征在于，所述正則表達(dá)式模式庫(kù)包括純字符串組、正則單元組和元數(shù)據(jù)組，其中：

所述純字符串組用于存儲(chǔ)純字符串，并根據(jù)各個(gè)純字符串是否相同而配置純字符串之間的關(guān)系；

所述正則單元組用于存儲(chǔ)正則單元，并根據(jù)各個(gè)正則單元是否相同而配置正則單元之間的關(guān)系；

所述元數(shù)據(jù)組用于存儲(chǔ)元數(shù)據(jù)，并根據(jù)元數(shù)據(jù)配置純字符串與正則單元之間的關(guān)系。

4.如權(quán)利要求3所述的并行正則表達(dá)式匹配器，其特征在于，所述硬件匹配電路包括模式輸入模塊、數(shù)據(jù)輸入模塊、正則匹配核心模塊及匹配結(jié)果輸出模塊，其中：

所述模式輸入模塊根據(jù)純字符串組中的純字符串和正則單元組中的正則單元對(duì)正則匹配核心模塊進(jìn)行參數(shù)配置，以及根據(jù)元數(shù)據(jù)組中的元數(shù)據(jù)對(duì)正則匹配核心模塊進(jìn)行狀態(tài)表初始化；

所述數(shù)據(jù)輸入模塊用于將待匹配報(bào)文提供至正則匹配核心模塊；

所述正則匹配核心模塊用于將待匹配報(bào)文與正則表達(dá)式規(guī)則進(jìn)行匹配，生成匹配結(jié)果；

所述匹配結(jié)果輸出模塊用于輸出匹配結(jié)果；

其中，模式輸入模塊、數(shù)據(jù)輸入模塊和匹配結(jié)果輸出模塊與正則匹配核心模塊進(jìn)行總線協(xié)議橋接或格式轉(zhuǎn)換。

5.如權(quán)利要求4所述的并行正則表達(dá)式匹配器，其特征在于，所述正則匹配核心模塊包括字符串預(yù)處理模塊、操作調(diào)度模塊和執(zhí)行引擎模塊，其中：

所述字符串預(yù)處理模塊用于根據(jù)純字符串組中的純字符串對(duì)待匹配報(bào)文進(jìn)行掃描，生成字符串隊(duì)列；

所述操作調(diào)度模塊用于根據(jù)字符串隊(duì)列執(zhí)行相應(yīng)的程序，生成請(qǐng)求隊(duì)列；

所述執(zhí)行引擎模塊根據(jù)請(qǐng)求隊(duì)列對(duì)待匹配報(bào)文進(jìn)行掃描，判斷待匹配報(bào)文是否匹配。

6.如權(quán)利要求5所述的并行正則表達(dá)式匹配器，其特征在于，所述字符串預(yù)處理模塊包括文本掃描模塊和文本確認(rèn)模塊，其中：

所述文本掃描模塊利用Shift-OR算法電路，根據(jù)純字符串組中的純字符串對(duì)待匹配報(bào)文中的純字符串進(jìn)行預(yù)匹配，得到粗篩結(jié)果；

所述文本確認(rèn)模塊利用硬件哈希算法，根據(jù)純字符串組中的純字符串對(duì)粗篩結(jié)果中的純字符串進(jìn)行再次確認(rèn)，得到細(xì)篩結(jié)果。

7.如權(quán)利要求6所述的并行正則表達(dá)式匹配器，其特征在于，所述Shift-OR算法電路同時(shí)對(duì)16個(gè)字符進(jìn)行流水線掃描；

經(jīng)過(guò)Shift-OR算法電路掃描后，匹配的數(shù)據(jù)包的待確認(rèn)字節(jié)序號(hào)放入文本確認(rèn)模塊的索引數(shù)據(jù)結(jié)構(gòu)的先入先出隊(duì)列，供文本確認(rèn)模塊使用；

文本確認(rèn)模塊將索引數(shù)據(jù)結(jié)構(gòu)的先入先出隊(duì)列讀入，形成并查詢細(xì)篩模塊索引表，以獲得匹配的數(shù)據(jù)包的字節(jié)序號(hào)后計(jì)算哈希值，使用哈希值查找字符串信息表，獲得字符串長(zhǎng)度和字符串地址；

由字符串長(zhǎng)度和字符串地址生成字符串隊(duì)列。

8.如權(quán)利要求7所述的并行正則表達(dá)式匹配器，其特征在于，操作調(diào)度器負(fù)責(zé)根據(jù)字符串請(qǐng)求信息形成相應(yīng)的程序，并選擇相應(yīng)的執(zhí)行引擎模塊，每個(gè)程序包括指令、操作碼和操作數(shù)，將每個(gè)指令送入請(qǐng)求隊(duì)列中，供后續(xù)執(zhí)行引擎模塊調(diào)用。