95 lines
3.0 KiB
C
95 lines
3.0 KiB
C
#include <c_BoyerMoore.h>
|
|
|
|
C_STATIC_FORCE_INLINE
|
|
c_int_t max(c_int_t a, c_int_t b) {
|
|
return a > b ? a : b;
|
|
}
|
|
|
|
c_err_t c_BoyerMoore_Init(c_BoyerMoore_t* self, const char* pattern, c_size_t pattern_size, int R, c_Allocator_t* allocator) {
|
|
if (!self || !pattern || pattern_size==0 || R==0) return C_ERR_PARAM;
|
|
|
|
// 前置逆向除法算术溢出防御审计
|
|
if (((c_size_t)-1) / sizeof(c_int_t) < (c_size_t)R) return C_ERR_PARAM;
|
|
if (((c_size_t)-1) / sizeof(char) < pattern_size) return C_ERR_PARAM;
|
|
|
|
self->R = R;
|
|
self->allocator = allocator?*allocator:c_DefaultAllocator;
|
|
|
|
self->pattern = c_Allocator_Alloc(&self->allocator, sizeof(char) * pattern_size);
|
|
self->right = c_Allocator_Alloc(&self->allocator, sizeof(*self->right) * R);
|
|
|
|
if (!self->pattern || !self->right) {
|
|
if (self->pattern) c_Allocator_Free(&self->allocator, self->pattern);
|
|
if (self->right) c_Allocator_Free(&self->allocator, self->right);
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
memcpy(self->pattern, pattern, pattern_size);
|
|
self->pattern_size = pattern_size;
|
|
|
|
for (int c=0; c<R; c++) {
|
|
self->right[c] = -1;
|
|
}
|
|
|
|
// 若在当前模式串内部出现过，则记录其最右侧出现的绝对物理位置下标
|
|
for (c_size_t i = 0; i < pattern_size; i++) {
|
|
unsigned char c = (unsigned char)self->pattern[i];
|
|
|
|
// 防御性高位拦截：若模式串内包含超出指定字母表 R 上限的越界字符，安全抛出异常拦截
|
|
if ((int)c >= R) {
|
|
c_Allocator_Free(&self->allocator, self->pattern);
|
|
c_Allocator_Free(&self->allocator, self->right);
|
|
return C_ERR_OUTOFBOUND;
|
|
}
|
|
self->right[c] = (c_int_t)i;
|
|
}
|
|
|
|
return C_ERR_OK;
|
|
}
|
|
|
|
c_err_t c_BoyerMoore_Search(c_BoyerMoore_t* self, const char* text, c_size_t text_size, c_size_t* index) {
|
|
if (!self || !text || text_size==0 || !self->pattern || self->pattern_size==0) return C_ERR_PARAM;
|
|
|
|
c_size_t m = self->pattern_size;
|
|
c_size_t n = text_size;
|
|
|
|
// 区间饱和过滤：主文本字节宽度短于子串宽度，绝无命中可能，平滑拦截
|
|
if (n < m) {
|
|
return C_ERR_NOTFOUND;
|
|
}
|
|
|
|
c_size_t skip = 0;
|
|
for (c_size_t i=0; i<=n-m; i+=skip) {
|
|
skip = 0;
|
|
for (c_size_t j=m-1; j!=-1; j--) {
|
|
if (self->pattern[j]!=text[i+j]) {
|
|
skip = max(1, j-self->right[text[i+j]]);
|
|
break;
|
|
}
|
|
}
|
|
if (skip==0) {
|
|
if (index) {
|
|
*index = i;
|
|
return C_ERR_OK;
|
|
}
|
|
}
|
|
}
|
|
if (index) {
|
|
*index = n;
|
|
}
|
|
return C_ERR_NOTFOUND;
|
|
}
|
|
|
|
void c_BoyerMoore_Destroy(c_BoyerMoore_t* self) {
|
|
if (!self) return;
|
|
if (self->pattern) {
|
|
c_Allocator_Free(&self->allocator, self->pattern);
|
|
self->pattern = NULL;
|
|
self->pattern_size = 0;
|
|
}
|
|
if (self->right) {
|
|
c_Allocator_Free(&self->allocator, self->right);
|
|
self->right = NULL;
|
|
}
|
|
}
|