diff options
author | Ivan Blinkov <ivan@blinkov.ru> | 2022-02-10 16:47:10 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:10 +0300 |
commit | 1aeb9a455974457866f78722ad98114bafc84e8a (patch) | |
tree | e4340eaf1668684d83a0a58c36947c5def5350ad /contrib/libs/hyperscan/src/nfa/limex_common_impl.h | |
parent | bd5ef432f5cfb1e18851381329d94665a4c22470 (diff) | |
download | ydb-1aeb9a455974457866f78722ad98114bafc84e8a.tar.gz |
Restoring authorship annotation for Ivan Blinkov <ivan@blinkov.ru>. Commit 1 of 2.
Diffstat (limited to 'contrib/libs/hyperscan/src/nfa/limex_common_impl.h')
-rw-r--r-- | contrib/libs/hyperscan/src/nfa/limex_common_impl.h | 316 |
1 files changed, 158 insertions, 158 deletions
diff --git a/contrib/libs/hyperscan/src/nfa/limex_common_impl.h b/contrib/libs/hyperscan/src/nfa/limex_common_impl.h index e441945d70..6d72ee464c 100644 --- a/contrib/libs/hyperscan/src/nfa/limex_common_impl.h +++ b/contrib/libs/hyperscan/src/nfa/limex_common_impl.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2016, Intel Corporation + * Copyright (c) 2015-2016, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -31,22 +31,22 @@ /* impl of limex functions which depend only on state size */ -#if !defined(SIZE) || !defined(STATE_T) || !defined(LOAD_FROM_ENG) \ - || !defined(INLINE_ATTR) -# error Must define SIZE, STATE_T, LOAD_FROM_ENG and INLINE_ATTR in includer. +#if !defined(SIZE) || !defined(STATE_T) || !defined(LOAD_FROM_ENG) \ + || !defined(INLINE_ATTR) +# error Must define SIZE, STATE_T, LOAD_FROM_ENG and INLINE_ATTR in includer. #endif #define IMPL_NFA_T JOIN(struct LimExNFA, SIZE) #define TESTEOD_FN JOIN(moNfaTestEod, SIZE) #define LIMEX_INACCEPT_FN JOIN(limexInAccept, SIZE) -#define LIMEX_INANYACCEPT_FN JOIN(limexInAnyAccept, SIZE) +#define LIMEX_INANYACCEPT_FN JOIN(limexInAnyAccept, SIZE) #define EXPIRE_ESTATE_FN JOIN(limexExpireExtendedState, SIZE) #define REPORTCURRENT_FN JOIN(moNfaReportCurrent, SIZE) #define INITIAL_FN JOIN(moNfaInitial, SIZE) #define TOP_FN JOIN(moNfaTop, SIZE) #define TOPN_FN JOIN(moNfaTopN, SIZE) -#define PROCESS_ACCEPTS_IMPL_FN JOIN(moProcessAcceptsImpl, SIZE) +#define PROCESS_ACCEPTS_IMPL_FN JOIN(moProcessAcceptsImpl, SIZE) #define PROCESS_ACCEPTS_FN JOIN(moProcessAccepts, SIZE) #define PROCESS_ACCEPTS_NOSQUASH_FN JOIN(moProcessAcceptsNoSquash, SIZE) #define CONTEXT_T JOIN(NFAContext, SIZE) @@ -61,20 +61,20 @@ #define SQUASH_UNTUG_BR_FN JOIN(lazyTug, SIZE) #define GET_NFA_REPEAT_INFO_FN JOIN(getNfaRepeatInfo, SIZE) -#if defined(ARCH_64_BIT) && (SIZE >= 64) -#define CHUNK_T u64a -#define FIND_AND_CLEAR_FN findAndClearLSB_64 -#define POPCOUNT_FN popcount64 -#define RANK_IN_MASK_FN rank_in_mask64 -#else -#define CHUNK_T u32 -#define FIND_AND_CLEAR_FN findAndClearLSB_32 -#define POPCOUNT_FN popcount32 -#define RANK_IN_MASK_FN rank_in_mask32 -#endif - -#define NUM_STATE_CHUNKS (sizeof(STATE_T) / sizeof(CHUNK_T)) - +#if defined(ARCH_64_BIT) && (SIZE >= 64) +#define CHUNK_T u64a +#define FIND_AND_CLEAR_FN findAndClearLSB_64 +#define POPCOUNT_FN popcount64 +#define RANK_IN_MASK_FN rank_in_mask64 +#else +#define CHUNK_T u32 +#define FIND_AND_CLEAR_FN findAndClearLSB_32 +#define POPCOUNT_FN popcount32 +#define RANK_IN_MASK_FN rank_in_mask32 +#endif + +#define NUM_STATE_CHUNKS (sizeof(STATE_T) / sizeof(CHUNK_T)) + static really_inline void SQUASH_UNTUG_BR_FN(const IMPL_NFA_T *limex, const union RepeatControl *repeat_ctrl, @@ -96,7 +96,7 @@ void SQUASH_UNTUG_BR_FN(const IMPL_NFA_T *limex, const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i); u32 cyclicState = info->cyclicState; - if (!TESTBIT_STATE(*accstate, cyclicState)) { + if (!TESTBIT_STATE(*accstate, cyclicState)) { continue; } @@ -113,85 +113,85 @@ void SQUASH_UNTUG_BR_FN(const IMPL_NFA_T *limex, } } -static really_inline -char PROCESS_ACCEPTS_IMPL_FN(const IMPL_NFA_T *limex, const STATE_T *s, - STATE_T *squash, const STATE_T *acceptMask, - const struct NFAAccept *acceptTable, u64a offset, - NfaCallback callback, void *context) { +static really_inline +char PROCESS_ACCEPTS_IMPL_FN(const IMPL_NFA_T *limex, const STATE_T *s, + STATE_T *squash, const STATE_T *acceptMask, + const struct NFAAccept *acceptTable, u64a offset, + NfaCallback callback, void *context) { assert(s); assert(limex); assert(callback); - const STATE_T accept_mask = *acceptMask; - STATE_T accepts = AND_STATE(*s, accept_mask); - - // Caller must ensure that we have at least one accept state on. - assert(ISNONZERO_STATE(accepts)); - - CHUNK_T chunks[NUM_STATE_CHUNKS]; - memcpy(chunks, &accepts, sizeof(accepts)); - - CHUNK_T mask_chunks[NUM_STATE_CHUNKS]; - memcpy(mask_chunks, &accept_mask, sizeof(accept_mask)); - - u32 base_index = 0; // Cumulative sum of mask popcount up to current chunk. - for (u32 i = 0; i < NUM_STATE_CHUNKS; i++) { - CHUNK_T chunk = chunks[i]; - while (chunk != 0) { - u32 bit = FIND_AND_CLEAR_FN(&chunk); - u32 local_idx = RANK_IN_MASK_FN(mask_chunks[i], bit); - u32 idx = local_idx + base_index; - const struct NFAAccept *a = &acceptTable[idx]; - DEBUG_PRINTF("state %u: firing report list=%u, offset=%llu\n", - bit + i * (u32)sizeof(chunk) * 8, a->reports, offset); - int rv = limexRunAccept((const char *)limex, a, callback, context, - offset); + const STATE_T accept_mask = *acceptMask; + STATE_T accepts = AND_STATE(*s, accept_mask); + + // Caller must ensure that we have at least one accept state on. + assert(ISNONZERO_STATE(accepts)); + + CHUNK_T chunks[NUM_STATE_CHUNKS]; + memcpy(chunks, &accepts, sizeof(accepts)); + + CHUNK_T mask_chunks[NUM_STATE_CHUNKS]; + memcpy(mask_chunks, &accept_mask, sizeof(accept_mask)); + + u32 base_index = 0; // Cumulative sum of mask popcount up to current chunk. + for (u32 i = 0; i < NUM_STATE_CHUNKS; i++) { + CHUNK_T chunk = chunks[i]; + while (chunk != 0) { + u32 bit = FIND_AND_CLEAR_FN(&chunk); + u32 local_idx = RANK_IN_MASK_FN(mask_chunks[i], bit); + u32 idx = local_idx + base_index; + const struct NFAAccept *a = &acceptTable[idx]; + DEBUG_PRINTF("state %u: firing report list=%u, offset=%llu\n", + bit + i * (u32)sizeof(chunk) * 8, a->reports, offset); + int rv = limexRunAccept((const char *)limex, a, callback, context, + offset); if (unlikely(rv == MO_HALT_MATCHING)) { return 1; } - if (squash != NULL && a->squash != MO_INVALID_IDX) { - DEBUG_PRINTF("applying squash mask at offset %u\n", a->squash); - const ENG_STATE_T *sq = - (const ENG_STATE_T *)((const char *)limex + a->squash); - *squash = AND_STATE(*squash, LOAD_FROM_ENG(sq)); + if (squash != NULL && a->squash != MO_INVALID_IDX) { + DEBUG_PRINTF("applying squash mask at offset %u\n", a->squash); + const ENG_STATE_T *sq = + (const ENG_STATE_T *)((const char *)limex + a->squash); + *squash = AND_STATE(*squash, LOAD_FROM_ENG(sq)); } } - base_index += POPCOUNT_FN(mask_chunks[i]); + base_index += POPCOUNT_FN(mask_chunks[i]); } return 0; } static never_inline -char PROCESS_ACCEPTS_FN(const IMPL_NFA_T *limex, STATE_T *s, - const STATE_T *acceptMask, - const struct NFAAccept *acceptTable, u64a offset, - NfaCallback callback, void *context) { - // We have squash masks we might have to apply after firing reports. - STATE_T squash = ONES_STATE; - return PROCESS_ACCEPTS_IMPL_FN(limex, s, &squash, acceptMask, acceptTable, - offset, callback, context); - - *s = AND_STATE(*s, squash); -} - -static never_inline -char PROCESS_ACCEPTS_NOSQUASH_FN(const IMPL_NFA_T *limex, const STATE_T *s, - const STATE_T *acceptMask, - const struct NFAAccept *acceptTable, - u64a offset, NfaCallback callback, - void *context) { - STATE_T *squash = NULL; - return PROCESS_ACCEPTS_IMPL_FN(limex, s, squash, acceptMask, acceptTable, - offset, callback, context); +char PROCESS_ACCEPTS_FN(const IMPL_NFA_T *limex, STATE_T *s, + const STATE_T *acceptMask, + const struct NFAAccept *acceptTable, u64a offset, + NfaCallback callback, void *context) { + // We have squash masks we might have to apply after firing reports. + STATE_T squash = ONES_STATE; + return PROCESS_ACCEPTS_IMPL_FN(limex, s, &squash, acceptMask, acceptTable, + offset, callback, context); + + *s = AND_STATE(*s, squash); } -// Run EOD accepts. Note that repeat_ctrl and repeat_state may be NULL if this -// LimEx contains no repeat structures. +static never_inline +char PROCESS_ACCEPTS_NOSQUASH_FN(const IMPL_NFA_T *limex, const STATE_T *s, + const STATE_T *acceptMask, + const struct NFAAccept *acceptTable, + u64a offset, NfaCallback callback, + void *context) { + STATE_T *squash = NULL; + return PROCESS_ACCEPTS_IMPL_FN(limex, s, squash, acceptMask, acceptTable, + offset, callback, context); +} + +// Run EOD accepts. Note that repeat_ctrl and repeat_state may be NULL if this +// LimEx contains no repeat structures. static really_inline char TESTEOD_FN(const IMPL_NFA_T *limex, const STATE_T *s, const union RepeatControl *repeat_ctrl, - const char *repeat_state, u64a offset, + const char *repeat_state, u64a offset, NfaCallback callback, void *context) { assert(limex && s); @@ -200,16 +200,16 @@ char TESTEOD_FN(const IMPL_NFA_T *limex, const STATE_T *s, return MO_CONTINUE_MATCHING; } - const STATE_T acceptEodMask = LOAD_FROM_ENG(&limex->acceptAtEOD); - STATE_T foundAccepts = AND_STATE(*s, acceptEodMask); + const STATE_T acceptEodMask = LOAD_FROM_ENG(&limex->acceptAtEOD); + STATE_T foundAccepts = AND_STATE(*s, acceptEodMask); - SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, - offset + 1 /* EOD 'symbol' */, &foundAccepts); + SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, + offset + 1 /* EOD 'symbol' */, &foundAccepts); if (unlikely(ISNONZERO_STATE(foundAccepts))) { const struct NFAAccept *acceptEodTable = getAcceptEodTable(limex); - if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &foundAccepts, &acceptEodMask, - acceptEodTable, offset, callback, + if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &foundAccepts, &acceptEodMask, + acceptEodTable, offset, callback, context)) { return MO_HALT_MATCHING; } @@ -225,8 +225,8 @@ char REPORTCURRENT_FN(const IMPL_NFA_T *limex, const struct mq *q) { assert(q->state); assert(q_cur_type(q) == MQE_START); - STATE_T s = *(STATE_T *)q->state; - STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept); + STATE_T s = *(STATE_T *)q->state; + STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept); STATE_T foundAccepts = AND_STATE(s, acceptMask); if (unlikely(ISNONZERO_STATE(foundAccepts))) { @@ -235,8 +235,8 @@ char REPORTCURRENT_FN(const IMPL_NFA_T *limex, const struct mq *q) { const struct NFAAccept *acceptTable = getAcceptTable(limex); u64a offset = q_cur_offset(q); - if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &foundAccepts, &acceptMask, - acceptTable, offset, q->cb, + if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &foundAccepts, &acceptMask, + acceptTable, offset, q->cb, q->context)) { return MO_HALT_MATCHING; } @@ -247,7 +247,7 @@ char REPORTCURRENT_FN(const IMPL_NFA_T *limex, const struct mq *q) { static really_inline STATE_T INITIAL_FN(const IMPL_NFA_T *impl, char onlyDs) { - return LOAD_FROM_ENG(onlyDs ? &impl->initDS : &impl->init); + return LOAD_FROM_ENG(onlyDs ? &impl->initDS : &impl->init); } static really_inline @@ -258,9 +258,9 @@ STATE_T TOP_FN(const IMPL_NFA_T *impl, char onlyDs, STATE_T state) { static really_inline STATE_T TOPN_FN(const IMPL_NFA_T *limex, STATE_T state, u32 n) { assert(n < limex->topCount); - const ENG_STATE_T *topsptr = - (const ENG_STATE_T *)((const char *)limex + limex->topOffset); - STATE_T top = LOAD_FROM_ENG(&topsptr[n]); + const ENG_STATE_T *topsptr = + (const ENG_STATE_T *)((const char *)limex + limex->topOffset); + STATE_T top = LOAD_FROM_ENG(&topsptr[n]); return OR_STATE(top, state); } @@ -276,8 +276,8 @@ void EXPIRE_ESTATE_FN(const IMPL_NFA_T *limex, struct CONTEXT_T *ctx, DEBUG_PRINTF("expire estate at offset %llu\n", offset); - const STATE_T cyclics - = AND_STATE(ctx->s, LOAD_FROM_ENG(&limex->repeatCyclicMask)); + const STATE_T cyclics + = AND_STATE(ctx->s, LOAD_FROM_ENG(&limex->repeatCyclicMask)); if (ISZERO_STATE(cyclics)) { DEBUG_PRINTF("no cyclic states are on\n"); return; @@ -287,7 +287,7 @@ void EXPIRE_ESTATE_FN(const IMPL_NFA_T *limex, struct CONTEXT_T *ctx, const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i); u32 cyclicState = info->cyclicState; - if (!TESTBIT_STATE(cyclics, cyclicState)) { + if (!TESTBIT_STATE(cyclics, cyclicState)) { continue; } @@ -307,14 +307,14 @@ void EXPIRE_ESTATE_FN(const IMPL_NFA_T *limex, struct CONTEXT_T *ctx, last_top, repeat->repeatMax); u64a adj = 0; /* if the cycle's tugs are active at repeat max, it is still alive */ - if (TESTBIT_STATE(LOAD_FROM_ENG(&limex->accept), cyclicState) || - TESTBIT_STATE(LOAD_FROM_ENG(&limex->acceptAtEOD), cyclicState)) { + if (TESTBIT_STATE(LOAD_FROM_ENG(&limex->accept), cyclicState) || + TESTBIT_STATE(LOAD_FROM_ENG(&limex->acceptAtEOD), cyclicState)) { DEBUG_PRINTF("lazy tug possible - may still be inspected\n"); adj = 1; } else { - const ENG_STATE_T *tug_mask = - (const ENG_STATE_T *)((const char *)info + info->tugMaskOffset); - if (ISNONZERO_STATE(AND_STATE(ctx->s, LOAD_FROM_ENG(tug_mask)))) { + const ENG_STATE_T *tug_mask = + (const ENG_STATE_T *)((const char *)info + info->tugMaskOffset); + if (ISNONZERO_STATE(AND_STATE(ctx->s, LOAD_FROM_ENG(tug_mask)))) { DEBUG_PRINTF("tug possible - may still be inspected\n"); adj = 1; } @@ -336,75 +336,75 @@ char LIMEX_INACCEPT_FN(const IMPL_NFA_T *limex, STATE_T state, u64a offset, ReportID report) { assert(limex); - const STATE_T accept_mask = LOAD_FROM_ENG(&limex->accept); - STATE_T accepts = AND_STATE(state, accept_mask); + const STATE_T accept_mask = LOAD_FROM_ENG(&limex->accept); + STATE_T accepts = AND_STATE(state, accept_mask); // Are we in an accept state? - if (ISZERO_STATE(accepts)) { + if (ISZERO_STATE(accepts)) { DEBUG_PRINTF("no accept states are on\n"); return 0; } - SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &accepts); + SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &accepts); DEBUG_PRINTF("looking for report %u\n", report); - const struct NFAAccept *acceptTable = getAcceptTable(limex); - - CHUNK_T chunks[NUM_STATE_CHUNKS]; - memcpy(chunks, &accepts, sizeof(accepts)); - - CHUNK_T mask_chunks[NUM_STATE_CHUNKS]; - memcpy(mask_chunks, &accept_mask, sizeof(accept_mask)); - - u32 base_index = 0; // Cumulative sum of mask popcount up to current chunk. - for (u32 i = 0; i < NUM_STATE_CHUNKS; i++) { - CHUNK_T chunk = chunks[i]; - while (chunk != 0) { - u32 bit = FIND_AND_CLEAR_FN(&chunk); - u32 local_idx = RANK_IN_MASK_FN(mask_chunks[i], bit); - u32 idx = local_idx + base_index; - assert(idx < limex->acceptCount); - const struct NFAAccept *a = &acceptTable[idx]; - DEBUG_PRINTF("state %u is on, report list at %u\n", - bit + i * (u32)sizeof(chunk) * 8, a->reports); - - if (limexAcceptHasReport((const char *)limex, a, report)) { - DEBUG_PRINTF("report %u is on\n", report); - return 1; - } + const struct NFAAccept *acceptTable = getAcceptTable(limex); + + CHUNK_T chunks[NUM_STATE_CHUNKS]; + memcpy(chunks, &accepts, sizeof(accepts)); + + CHUNK_T mask_chunks[NUM_STATE_CHUNKS]; + memcpy(mask_chunks, &accept_mask, sizeof(accept_mask)); + + u32 base_index = 0; // Cumulative sum of mask popcount up to current chunk. + for (u32 i = 0; i < NUM_STATE_CHUNKS; i++) { + CHUNK_T chunk = chunks[i]; + while (chunk != 0) { + u32 bit = FIND_AND_CLEAR_FN(&chunk); + u32 local_idx = RANK_IN_MASK_FN(mask_chunks[i], bit); + u32 idx = local_idx + base_index; + assert(idx < limex->acceptCount); + const struct NFAAccept *a = &acceptTable[idx]; + DEBUG_PRINTF("state %u is on, report list at %u\n", + bit + i * (u32)sizeof(chunk) * 8, a->reports); + + if (limexAcceptHasReport((const char *)limex, a, report)) { + DEBUG_PRINTF("report %u is on\n", report); + return 1; + } } - base_index += POPCOUNT_FN(mask_chunks[i]); + base_index += POPCOUNT_FN(mask_chunks[i]); } return 0; } -static really_inline -char LIMEX_INANYACCEPT_FN(const IMPL_NFA_T *limex, STATE_T state, - union RepeatControl *repeat_ctrl, char *repeat_state, - u64a offset) { - assert(limex); - - const STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept); - STATE_T accstate = AND_STATE(state, acceptMask); - - // Are we in an accept state? - if (ISZERO_STATE(accstate)) { - DEBUG_PRINTF("no accept states are on\n"); - return 0; - } - - SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &accstate); - - return ISNONZERO_STATE(accstate); -} - +static really_inline +char LIMEX_INANYACCEPT_FN(const IMPL_NFA_T *limex, STATE_T state, + union RepeatControl *repeat_ctrl, char *repeat_state, + u64a offset) { + assert(limex); + + const STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept); + STATE_T accstate = AND_STATE(state, acceptMask); + + // Are we in an accept state? + if (ISZERO_STATE(accstate)) { + DEBUG_PRINTF("no accept states are on\n"); + return 0; + } + + SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &accstate); + + return ISNONZERO_STATE(accstate); +} + #undef TESTEOD_FN #undef REPORTCURRENT_FN #undef EXPIRE_ESTATE_FN #undef LIMEX_INACCEPT_FN -#undef LIMEX_INANYACCEPT_FN +#undef LIMEX_INANYACCEPT_FN #undef INITIAL_FN #undef TOP_FN #undef TOPN_FN @@ -418,14 +418,14 @@ char LIMEX_INANYACCEPT_FN(const IMPL_NFA_T *limex, STATE_T state, #undef TESTBIT_STATE #undef ISNONZERO_STATE #undef ISZERO_STATE -#undef PROCESS_ACCEPTS_IMPL_FN +#undef PROCESS_ACCEPTS_IMPL_FN #undef PROCESS_ACCEPTS_FN #undef PROCESS_ACCEPTS_NOSQUASH_FN #undef SQUASH_UNTUG_BR_FN #undef GET_NFA_REPEAT_INFO_FN -#undef CHUNK_T -#undef FIND_AND_CLEAR_FN -#undef POPCOUNT_FN -#undef RANK_IN_MASK_FN -#undef NUM_STATE_CHUNKS +#undef CHUNK_T +#undef FIND_AND_CLEAR_FN +#undef POPCOUNT_FN +#undef RANK_IN_MASK_FN +#undef NUM_STATE_CHUNKS |