[發明專利]一種基于硬件查找表的模式字符的查找方法

有效

• 申請號: 201611249587.5
• 申請日: 2016-12-29
• 公開（公告）號: CN106649836B
• 公開（公告）日: 2019-11-29
• 發明（設計）人: 陳振家;何洪楷
• 申請（專利權）人: 武漢新芯集成電路制造有限公司
• 主分類號: G06F16/9032
• 分類號: G06F16/9032;G06F16/903;G06F16/901
• 代理公司: 31272 上海申新律師事務所
• 代理人: 俞滌炯<國際申請>=<國際公布>=<進入

本發明涉及存儲器技術領域，尤其涉及一種基于硬件查找表的模式字符的查找方法，存儲區包括多個存儲單元，存儲單元于存儲區內的訪問地址的編址方式對應一預定編碼字符集，還提供一模式字符串，存儲單元的位寬等于模式字符串的字符長度，存儲單元的每一位分別順序對應模式字符串中的每個字符，通過將存儲區中對應模式字符串中每個字符的存儲單元的對應位，置邏輯值1，從而通過讀取對應位實現模式字符的查找；上述技術方案采用硬件實現方式的查找匹配過程，不占用CPU資源，提高系統并行處理能力，利用硬件運行速度快的特點，在若干個硬件時鐘周期內即可得到匹配結果，能對實時輸入的高速待匹配數據流進行實時的查找匹配結果輸出。

技術領域

本發明涉及存儲器技術領域，尤其涉及一種基于硬件查找表的模式字符的查找方法。

背景技術

字符串匹配即對一段數據進行指定字符串的查找匹配，可用于對帶有指定特征字符串的一段數據進行篩選、過濾等應用。

現有字符串匹配方法多采用高級編程語言(如C語言,Java等)編程的軟件方式實現匹配算法，例如：哈希、KMP算法等，通過不同的查找順序減少得到匹配結果的時間。

但是，用高級編程語言編程運行于CPU(Central Processing Unit，中央處理器)，以軟件的形式實現字符串匹配的方法并行處理能力相對較差，速度相對較慢，需考慮運行軟件算法的CPU調度問題，不適合用于對實時高速數據流進行字符串匹配。

發明內容

針對上述問題，本發明提出了一種基于硬件查找表的查找模式字符串的方法，所述硬件查找表包括至少一個存儲區；

所述存儲區包括多個存儲單元，所述存儲單元于所述存儲區內的訪問地址的編址方式對應一預定編碼字符集，還提供一模式字符串，所述存儲單元的位寬等于所述模式字符串的字符長度，所述存儲單元的每一位分別順序對應所述模式字符串中的每個字符；

還包括以下步驟：

步驟S1，將所述存儲區中，對應所述模式字符串中每個字符的所述存儲單元的對應位，置邏輯值1；

步驟S2，獲取一目標字符串；

步驟S3，讀取所述目標字符串的第一位；

步驟S4，定義讀取到的所述字符為當前字符；

步驟S5，以所述預定編碼字符集對所述當前字符進行解碼，以獲取所述當前字符對應的編碼；

步驟S6，根據所述編碼于所述存儲區查找對應的所述存儲單元；

步驟S7，于所述步驟S6查找到的所述存儲單元中獲取第一位；

步驟S8，判斷所述步驟S7中獲取的所述第一位的值是否為1，如果是則提供一數字值N，定義N＝1，并執行所述步驟S9，如果否執行所述步驟S17；

步驟S9，判斷所述模式字符串的字符長度是否等于1，如果是執行步驟S16；

步驟S10，判斷所述目標字符串剩余的字符長度是否小于所述模式字符串的長度-N，如果是執行步驟S18；

步驟S11，讀取所述目標字符串的下一位，定義讀取到的字符為第二當前字符；

步驟S12，以所述預定編碼字符集對所述第二當前字符進行解碼，以獲取所述第二當前字符對應的編碼；

步驟S13，根據所述編碼于所述存儲區查找對應的所述存儲單元；

步驟S14，令N＝N+1，于所述步驟S13查找到的所述存儲單元中獲取第N位；

步驟S15，判斷所述步驟S14中獲取的所述第N位的值是否為1，如果是返回執行所述步驟S11，如果否執行所述步驟S17；