intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 1075 insertions, 0 deletions

diff --git a/contrib/libs/hyperscan/src/nfa/limex_runtime_impl.h b/contrib/libs/hyperscan/src/nfa/limex_runtime_impl.h
new file mode 100644
index 0000000000..7b89182bea
--- /dev/null
+++ b/contrib/libs/hyperscan/src/nfa/limex_runtime_impl.h
@@ -0,0 +1,1075 @@
+/*
+ * Copyright (c) 2015-2017, Intel Corporation
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ *  * Redistributions of source code must retain the above copyright notice,
+ *    this list of conditions and the following disclaimer.
+ *  * Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *  * Neither the name of Intel Corporation nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "util/join.h"
+#include <string.h>
+
+/** \file
+  * \brief Limex Execution Engine Or:
+  * How I Learned To Stop Worrying And Love The Preprocessor
+  *
+  * Version 2.0: now with X-Macros, so you get line numbers in your debugger.
+  */
+
+
+#if !defined(SIZE) || !defined(STATE_T) || !defined(LOAD_FROM_ENG)
+#  error Must define SIZE, STATE_T, LOAD_FROM_ENG in includer.
+#endif
+
+#define LIMEX_API_ROOT   JOIN(nfaExecLimEx, SIZE)
+
+#define IMPL_NFA_T          JOIN(struct LimExNFA, SIZE)
+
+#define TESTEOD_FN          JOIN(moNfaTestEod, SIZE)
+#define INITIAL_FN          JOIN(moNfaInitial, SIZE)
+#define TOP_FN              JOIN(moNfaTop, SIZE)
+#define TOPN_FN             JOIN(moNfaTopN, SIZE)
+#define REPORTCURRENT_FN    JOIN(moNfaReportCurrent, SIZE)
+#define COMPRESS_FN         JOIN(moNfaCompressState, SIZE)
+#define EXPAND_FN           JOIN(moNfaExpandState, SIZE)
+#define COMPRESS_REPEATS_FN JOIN(LIMEX_API_ROOT, _Compress_Repeats)
+#define EXPAND_REPEATS_FN   JOIN(LIMEX_API_ROOT, _Expand_Repeats)
+#define PROCESS_ACCEPTS_FN  JOIN(moProcessAccepts, SIZE)
+#define PROCESS_ACCEPTS_NOSQUASH_FN  JOIN(moProcessAcceptsNoSquash, SIZE)
+#define GET_NFA_REPEAT_INFO_FN JOIN(getNfaRepeatInfo, SIZE)
+#define RUN_ACCEL_FN        JOIN(LIMEX_API_ROOT, _Run_Accel)
+#define RUN_EXCEPTIONS_FN   JOIN(LIMEX_API_ROOT, _Run_Exceptions)
+#define REV_STREAM_FN       JOIN(LIMEX_API_ROOT, _Rev_Stream)
+#define LOOP_NOACCEL_FN     JOIN(LIMEX_API_ROOT, _Loop_No_Accel)
+#define STREAM_FN           JOIN(LIMEX_API_ROOT, _Stream)
+#define STREAMCB_FN         JOIN(LIMEX_API_ROOT, _Stream_CB)
+#define STREAMFIRST_FN      JOIN(LIMEX_API_ROOT, _Stream_First)
+#define STREAMSILENT_FN     JOIN(LIMEX_API_ROOT, _Stream_Silent)
+#define CONTEXT_T           JOIN(NFAContext, SIZE)
+#define EXCEPTION_T         JOIN(struct NFAException, SIZE)
+#define AND_STATE           JOIN(and_, STATE_T)
+#define ANDNOT_STATE        JOIN(andnot_, STATE_T)
+#define OR_STATE            JOIN(or_, STATE_T)
+#define LSHIFT_STATE        JOIN(lshift_, STATE_T)
+#define TESTBIT_STATE       JOIN(testbit_, STATE_T)
+#define CLEARBIT_STATE      JOIN(clearbit_, STATE_T)
+#define ZERO_STATE          JOIN(zero_, STATE_T)
+#define ISNONZERO_STATE     JOIN(isNonZero_, STATE_T)
+#define ISZERO_STATE        JOIN(isZero_, STATE_T)
+#define NOTEQ_STATE         JOIN(noteq_, STATE_T)
+
+// Pick an appropriate diffrich function for this platform.
+#ifdef ARCH_64_BIT
+#define DIFFRICH_STATE JOIN(diffrich64_, STATE_T)
+#else
+#define DIFFRICH_STATE JOIN(diffrich_, STATE_T)
+#endif
+
+#define EXPIRE_ESTATE_FN    JOIN(limexExpireExtendedState, SIZE)
+#define SQUASH_UNTUG_BR_FN  JOIN(lazyTug, SIZE)
+
+// Acceleration and exception masks: we load them on the fly for really big
+// models.
+#if SIZE < 256
+#define ACCEL_MASK              accelMask
+#define ACCEL_AND_FRIENDS_MASK  accel_and_friendsMask
+#define EXCEPTION_MASK          exceptionMask
+#else
+#define ACCEL_MASK              LOAD_FROM_ENG(&limex->accel)
+#define ACCEL_AND_FRIENDS_MASK  LOAD_FROM_ENG(&limex->accel_and_friends)
+#define EXCEPTION_MASK          LOAD_FROM_ENG(&limex->exceptionMask)
+#endif
+
+// Run exception processing, if necessary. Returns 0 if scanning should
+// continue, 1 if an accept was fired and the user instructed us to halt.
+static really_inline
+char RUN_EXCEPTIONS_FN(const IMPL_NFA_T *limex, const EXCEPTION_T *exceptions,
+                       STATE_T s, const STATE_T emask, size_t i, u64a offset,
+                       STATE_T *succ, u64a *final_loc, struct CONTEXT_T *ctx,
+                       const char flags, const char in_rev,
+                       const char first_match) {
+    STATE_T estate = AND_STATE(s, emask);
+    u32 diffmask = DIFFRICH_STATE(ZERO_STATE, estate);
+    if (likely(!diffmask)) {
+        return 0; // No exceptions to process.
+    }
+
+    if (first_match && i) {
+        STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept);
+        STATE_T foundAccepts = AND_STATE(s, acceptMask);
+        if (unlikely(ISNONZERO_STATE(foundAccepts))) {
+            DEBUG_PRINTF("first match at %zu\n", i);
+            DEBUG_PRINTF("for nfa %p\n", limex);
+            assert(final_loc);
+            ctx->s = s;
+            *final_loc = i;
+            return 1; // Halt matching.
+        }
+    }
+
+    u64a callback_offset = i + offset;
+    char localflags = (!i && !in_rev) ? NO_OUTPUT | FIRST_BYTE : flags;
+
+    int rv = JOIN(processExceptional, SIZE)(
+        pass_state, pass_estate, diffmask, succ, limex, exceptions,
+        callback_offset, ctx, in_rev, localflags);
+    if (rv == PE_RV_HALT) {
+        return 1; // Halt matching.
+    }
+
+    return 0;
+}
+
+static really_inline
+size_t RUN_ACCEL_FN(const STATE_T s, UNUSED const STATE_T accelMask,
+                    UNUSED const IMPL_NFA_T *limex, const u8 *accelTable,
+                    const union AccelAux *accelAux, const u8 *input, size_t i,
+                    size_t length) {
+    size_t j;
+#if SIZE < 128
+    // For small cases, we pass the state by value.
+    j = JOIN(doAccel, SIZE)(s, accelMask, accelTable, accelAux, input, i,
+                            length);
+#else
+    j = JOIN(doAccel, SIZE)(&s, limex, accelTable, accelAux, input, i, length);
+#endif
+
+    assert(j >= i);
+    assert(i <= length);
+    return j;
+}
+
+// Shift macros for Limited NFAs. Defined in terms of uniform ops.
+// LimExNFAxxx ptr in 'limex' and the current state in 's'
+#define NFA_EXEC_LIM_SHIFT(limex_m, curr_m, shift_idx)                         \
+    LSHIFT_STATE(AND_STATE(curr_m, LOAD_FROM_ENG(&limex_m->shift[shift_idx])), \
+                 limex_m->shiftAmount[shift_idx])
+
+// Calculate the (limited model) successors for a number of variable shifts.
+// Assumes current state in 'curr_m' and places the successors in 'succ_m'.
+#define NFA_EXEC_GET_LIM_SUCC(limex_m, curr_m, succ_m)                         \
+    do {                                                                       \
+        succ_m = NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 0);                       \
+        switch (limex_m->shiftCount) {                                         \
+        case 8:                                                                \
+            succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 7)); \
+            /* fallthrough */                                                  \
+        case 7:                                                                \
+            succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 6)); \
+            /* fallthrough */                                                  \
+        case 6:                                                                \
+            succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 5)); \
+            /* fallthrough */                                                  \
+        case 5:                                                                \
+            succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 4)); \
+            /* fallthrough */                                                  \
+        case 4:                                                                \
+            succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 3)); \
+            /* fallthrough */                                                  \
+        case 3:                                                                \
+            succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 2)); \
+            /* fallthrough */                                                  \
+        case 2:                                                                \
+            succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 1)); \
+            /* fallthrough */                                                  \
+        case 1:                                                                \
+            /* fallthrough */                                                  \
+        case 0:                                                                \
+            ;                                                                  \
+        }                                                                      \
+    } while (0)
+
+/**
+ * \brief LimEx NFAS inner loop without accel.
+ *
+ * Note that the "all zeroes" early death check is only performed if can_die is
+ * true.
+ *
+ */
+static really_inline
+char LOOP_NOACCEL_FN(const IMPL_NFA_T *limex, const u8 *input, size_t *loc,
+                     size_t length, STATE_T *s_ptr, struct CONTEXT_T *ctx,
+                     u64a offset, const char flags, u64a *final_loc,
+                     const char first_match, const char can_die) {
+    const ENG_STATE_T *reach = get_reach_table(limex);
+#if SIZE < 256
+    const STATE_T exceptionMask = LOAD_FROM_ENG(&limex->exceptionMask);
+#endif
+    const EXCEPTION_T *exceptions = getExceptionTable(EXCEPTION_T, limex);
+    STATE_T s = *s_ptr;
+
+    size_t i = *loc;
+    for (; i != length; i++) {
+        DUMP_INPUT(i);
+        if (can_die && ISZERO_STATE(s)) {
+            DEBUG_PRINTF("no states are switched on, early exit\n");
+            break;
+        }
+
+        STATE_T succ;
+        NFA_EXEC_GET_LIM_SUCC(limex, s, succ);
+
+        if (RUN_EXCEPTIONS_FN(limex, exceptions, s, EXCEPTION_MASK, i, offset,
+                              &succ, final_loc, ctx, flags, 0, first_match)) {
+            return MO_HALT_MATCHING;
+        }
+
+        u8 c = input[i];
+        s = AND_STATE(succ, LOAD_FROM_ENG(&reach[limex->reachMap[c]]));
+    }
+
+    *loc = i;
+    *s_ptr = s;
+    return MO_CONTINUE_MATCHING;
+}
+
+static really_inline
+char STREAM_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
+               struct CONTEXT_T *ctx, u64a offset, const char flags,
+               u64a *final_loc, const char first_match) {
+    const ENG_STATE_T *reach = get_reach_table(limex);
+#if SIZE < 256
+    const STATE_T accelMask = LOAD_FROM_ENG(&limex->accel);
+    const STATE_T accel_and_friendsMask
+        = LOAD_FROM_ENG(&limex->accel_and_friends);
+    const STATE_T exceptionMask = LOAD_FROM_ENG(&limex->exceptionMask);
+#endif
+    const u8 *accelTable =
+        (const u8 *)((const char *)limex + limex->accelTableOffset);
+    const union AccelAux *accelAux =
+        (const union AccelAux *)((const char *)limex + limex->accelAuxOffset);
+    const EXCEPTION_T *exceptions = getExceptionTable(EXCEPTION_T, limex);
+    STATE_T s = ctx->s;
+
+    /* assert(ISALIGNED_16(exceptions)); */
+    /* assert(ISALIGNED_16(reach)); */
+
+    size_t i = 0;
+    size_t min_accel_offset = 0;
+    if (!limex->accelCount || length < ACCEL_MIN_LEN) {
+        min_accel_offset = length;
+        goto without_accel;
+    } else {
+        goto with_accel;
+    }
+
+without_accel:
+    if (limex->flags & LIMEX_FLAG_CANNOT_DIE) {
+        const char can_die = 0;
+        if (LOOP_NOACCEL_FN(limex, input, &i, min_accel_offset, &s, ctx, offset,
+                            flags, final_loc, first_match,
+                            can_die) == MO_HALT_MATCHING) {
+            return MO_HALT_MATCHING;
+        }
+    } else {
+        const char can_die = 1;
+        if (LOOP_NOACCEL_FN(limex, input, &i, min_accel_offset, &s, ctx, offset,
+                            flags, final_loc, first_match,
+                            can_die) == MO_HALT_MATCHING) {
+            return MO_HALT_MATCHING;
+        }
+    }
+
+with_accel:
+    for (; i != length; i++) {
+        DUMP_INPUT(i);
+        if (i + 16 <= length &&
+            ISZERO_STATE(ANDNOT_STATE(ACCEL_AND_FRIENDS_MASK, s))) {
+            DEBUG_PRINTF("current states are all accelerable\n");
+            assert(i + 16 <= length);
+            size_t post_idx =
+                RUN_ACCEL_FN(s, ACCEL_MASK, limex, accelTable, accelAux, input,
+                             i, length);
+            if (post_idx != i) {
+                /* squashing any friends as they may no longer be valid;
+                 * offset back off should ensure they weren't doing anything
+                 * important */
+                s = AND_STATE(ACCEL_MASK, s);
+            }
+
+            if (i && post_idx < min_accel_offset + BAD_ACCEL_DIST) {
+                min_accel_offset = post_idx + BIG_ACCEL_PENALTY;
+            } else {
+                min_accel_offset = post_idx + SMALL_ACCEL_PENALTY;
+            }
+
+            if (min_accel_offset >= length - ACCEL_MIN_LEN) {
+                min_accel_offset = length;
+            }
+
+            DEBUG_PRINTF("advanced %zd, next accel chance in %zd/%zd\n",
+                         post_idx - i, min_accel_offset - post_idx,
+                         length - post_idx);
+
+            i = post_idx;
+            if (i == length) {
+                break; /* all chars eaten, break out of loop */
+            }
+            goto without_accel;
+        }
+
+        STATE_T succ;
+        NFA_EXEC_GET_LIM_SUCC(limex, s, succ);
+
+        if (RUN_EXCEPTIONS_FN(limex, exceptions, s, EXCEPTION_MASK, i, offset,
+                              &succ, final_loc, ctx, flags, 0, first_match)) {
+            return MO_HALT_MATCHING;
+        }
+
+        u8 c = input[i];
+        s = AND_STATE(succ, LOAD_FROM_ENG(&reach[limex->reachMap[c]]));
+    }
+
+    ctx->s = s;
+
+    if ((first_match || (flags & CALLBACK_OUTPUT)) && limex->acceptCount) {
+        STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept);
+        const struct NFAAccept *acceptTable = getAcceptTable(limex);
+        STATE_T foundAccepts = AND_STATE(s, acceptMask);
+        if (unlikely(ISNONZERO_STATE(foundAccepts))) {
+            if (first_match) {
+                ctx->s = s;
+                assert(final_loc);
+                *final_loc = length;
+                return MO_HALT_MATCHING;
+            } else if (PROCESS_ACCEPTS_FN(limex, &ctx->s, &acceptMask,
+                                          acceptTable, offset + length,
+                                          ctx->callback, ctx->context)) {
+                return MO_HALT_MATCHING;
+            }
+        }
+    }
+    if (first_match) {
+        assert(final_loc);
+        *final_loc = length;
+    }
+    return MO_CONTINUE_MATCHING;
+}
+
+static never_inline
+char REV_STREAM_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
+                   struct CONTEXT_T *ctx, u64a offset) {
+    const ENG_STATE_T *reach = get_reach_table(limex);
+#if SIZE < 256
+    const STATE_T exceptionMask = LOAD_FROM_ENG(&limex->exceptionMask);
+#endif
+    const EXCEPTION_T *exceptions = getExceptionTable(EXCEPTION_T, limex);
+    STATE_T s = ctx->s;
+
+    /* assert(ISALIGNED_16(exceptions)); */
+    /* assert(ISALIGNED_16(reach)); */
+    const char flags = CALLBACK_OUTPUT;
+    u64a *final_loc = NULL;
+
+    for (size_t i = length; i != 0; i--) {
+        DUMP_INPUT(i - 1);
+        if (ISZERO_STATE(s)) {
+            DEBUG_PRINTF("no states are switched on, early exit\n");
+            ctx->s = s;
+            return MO_CONTINUE_MATCHING;
+        }
+
+        STATE_T succ;
+        NFA_EXEC_GET_LIM_SUCC(limex, s, succ);
+
+        if (RUN_EXCEPTIONS_FN(limex, exceptions, s, EXCEPTION_MASK, i, offset,
+                              &succ, final_loc, ctx, flags, 1, 0)) {
+            return MO_HALT_MATCHING;
+        }
+
+        u8 c = input[i - 1];
+        s = AND_STATE(succ, LOAD_FROM_ENG(&reach[limex->reachMap[c]]));
+    }
+
+    ctx->s = s;
+
+    STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept);
+    const struct NFAAccept *acceptTable = getAcceptTable(limex);
+    const u32 acceptCount = limex->acceptCount;
+    assert(flags & CALLBACK_OUTPUT);
+    if (acceptCount) {
+        STATE_T foundAccepts = AND_STATE(s, acceptMask);
+        if (unlikely(ISNONZERO_STATE(foundAccepts))) {
+            if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &ctx->s, &acceptMask,
+                                            acceptTable, offset, ctx->callback,
+                                            ctx->context)) {
+                return MO_HALT_MATCHING;
+            }
+        }
+    }
+    return MO_CONTINUE_MATCHING;
+}
+
+static really_inline
+void COMPRESS_REPEATS_FN(const IMPL_NFA_T *limex, void *dest, void *src,
+                         u64a offset) {
+    if (!limex->repeatCount) {
+        return;
+    }
+
+    STATE_T s = *(STATE_T *)src;
+
+    if (ISZERO_STATE(AND_STATE(LOAD_FROM_ENG(&limex->repeatCyclicMask), s))) {
+        DEBUG_PRINTF("no cyclics are on\n");
+        return;
+    }
+
+    const union RepeatControl *ctrl =
+        getRepeatControlBaseConst((const char *)src, sizeof(STATE_T));
+    char *state_base = (char *)dest + limex->stateSize;
+
+    for (u32 i = 0; i < limex->repeatCount; i++) {
+        DEBUG_PRINTF("repeat %u\n", i);
+        const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i);
+
+        const ENG_STATE_T *tug_mask =
+            (const ENG_STATE_T *)((const char *)info + info->tugMaskOffset);
+        /* repeat may still be inspected if its tug state is on */
+        if (!TESTBIT_STATE(s, info->cyclicState)
+            && ISZERO_STATE(AND_STATE(s, LOAD_FROM_ENG(tug_mask)))) {
+            DEBUG_PRINTF("is dead\n");
+            continue;
+        }
+
+        const struct RepeatInfo *repeat = getRepeatInfo(info);
+        DEBUG_PRINTF("packing state (packedCtrlOffset=%u)\n",
+                     info->packedCtrlOffset);
+        repeatPack(state_base + info->packedCtrlOffset, repeat, &ctrl[i],
+                   offset);
+    }
+
+    *(STATE_T *)src = s;
+}
+
+char JOIN(LIMEX_API_ROOT, _queueCompressState)(const struct NFA *n,
+                                               const struct mq *q, s64a loc) {
+    void *dest = q->streamState;
+    void *src = q->state;
+    u8 key = queue_prev_byte(q, loc);
+    const IMPL_NFA_T *limex = getImplNfa(n);
+    COMPRESS_REPEATS_FN(limex, dest, src, q->offset + loc);
+    COMPRESS_FN(limex, dest, src, key);
+    return 0;
+}
+
+static really_inline
+void EXPAND_REPEATS_FN(const IMPL_NFA_T *limex, void *dest, const void *src,
+                       u64a offset) {
+    if (!limex->repeatCount) {
+        return;
+    }
+
+    // Note: state has already been expanded into 'dest'.
+    const STATE_T cyclics =
+        AND_STATE(*(STATE_T *)dest, LOAD_FROM_ENG(&limex->repeatCyclicMask));
+    if (ISZERO_STATE(cyclics)) {
+        DEBUG_PRINTF("no cyclics are on\n");
+        return;
+    }
+
+    union RepeatControl *ctrl =
+        getRepeatControlBase((char *)dest, sizeof(STATE_T));
+    const char *state_base = (const char *)src + limex->stateSize;
+
+    for (u32 i = 0; i < limex->repeatCount; i++) {
+        DEBUG_PRINTF("repeat %u\n", i);
+        const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i);
+        const ENG_STATE_T *tug_mask =
+            (const ENG_STATE_T *)((const char *)info + info->tugMaskOffset);
+
+        if (!TESTBIT_STATE(cyclics, info->cyclicState)
+            && ISZERO_STATE(AND_STATE(cyclics, LOAD_FROM_ENG(tug_mask)))) {
+            DEBUG_PRINTF("is dead\n");
+            continue;
+        }
+
+        DEBUG_PRINTF("unpacking state (packedCtrlOffset=%u)\n",
+                     info->packedCtrlOffset);
+        const struct RepeatInfo *repeat = getRepeatInfo(info);
+        repeatUnpack(state_base + info->packedCtrlOffset, repeat, offset,
+                     &ctrl[i]);
+    }
+}
+
+char JOIN(LIMEX_API_ROOT, _expandState)(const struct NFA *n, void *dest,
+                                           const void *src, u64a offset,
+                                           u8 key) {
+    const IMPL_NFA_T *limex = getImplNfa(n);
+    EXPAND_FN(limex, dest, src, key);
+    EXPAND_REPEATS_FN(limex, dest, src, offset);
+    return 0;
+}
+
+char JOIN(LIMEX_API_ROOT, _queueInitState)(const struct NFA *n, struct mq *q) {
+    *(STATE_T *)q->state = ZERO_STATE;
+
+    // Zero every bounded repeat control block in state.
+    const IMPL_NFA_T *limex = getImplNfa(n);
+    union RepeatControl *ctrl = getRepeatControlBase(q->state, sizeof(STATE_T));
+    for (u32 i = 0; i < limex->repeatCount; i++) {
+        memset(&ctrl[i], 0, sizeof(*ctrl));
+    }
+
+    return 0;
+}
+
+char JOIN(LIMEX_API_ROOT, _initCompressedState)(const struct NFA *n,
+                                                   u64a offset, void *state,
+                                                   u8 key) {
+    const IMPL_NFA_T *limex = getImplNfa(n);
+
+    STATE_T s = INITIAL_FN(limex, !!offset);
+    if (ISZERO_STATE(s)) {
+        DEBUG_PRINTF("state went to zero\n");
+        return 0;
+    }
+
+    // NFA is still active, compress its state and ship it out.
+    COMPRESS_FN(limex, state, &s, key);
+
+    // Zero every packed bounded repeat control block in stream state.
+    char *repeat_region = (char *)state + limex->stateSize;
+    for (u32 i = 0; i < limex->repeatCount; i++) {
+        const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i);
+        const struct RepeatInfo *repeat = getRepeatInfo(info);
+
+        memset(repeat_region + info->packedCtrlOffset, 0,
+               repeat->packedCtrlSize);
+    }
+
+    return 1;
+}
+
+// Helper for history buffer scans, which catch up the NFA state but don't emit
+// matches.
+static never_inline
+void STREAMSILENT_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
+                     struct CONTEXT_T *ctx, u64a offset) {
+    const char first_match = 0;
+
+    UNUSED char rv = STREAM_FN(limex, input, length, ctx, offset, NO_OUTPUT,
+                               NULL, first_match);
+    assert(rv != MO_HALT_MATCHING);
+}
+
+static never_inline
+char STREAMCB_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
+                 struct CONTEXT_T *ctx, u64a offset) {
+    const char first_match = 0;
+    assert(ISALIGNED_CL(ctx));
+    return STREAM_FN(limex, input, length, ctx, offset, CALLBACK_OUTPUT, NULL,
+                     first_match);
+}
+
+static never_inline
+char STREAMFIRST_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
+                    struct CONTEXT_T *ctx, u64a offset, u64a *final_loc) {
+    const char first_match = 1; // Run to first match and stop, no callbacks.
+    return STREAM_FN(limex, input, length, ctx, offset, NO_OUTPUT, final_loc,
+                     first_match);
+}
+
+// Common code for handling the current event on the queue.
+static really_inline
+void JOIN(LIMEX_API_ROOT, _HandleEvent)(const IMPL_NFA_T *limex,
+                                           struct mq *q, struct CONTEXT_T *ctx,
+                                           u64a sp) {
+#define DEFINE_CASE(ee)                                                        \
+    case ee:                                                                   \
+        DEBUG_PRINTF(#ee "\n");
+
+    u32 e = q->items[q->cur].type;
+    switch (e) {
+        DEFINE_CASE(MQE_TOP)
+            ctx->s = TOP_FN(limex, !!sp, ctx->s);
+            break;
+        DEFINE_CASE(MQE_START)
+            break;
+        DEFINE_CASE(MQE_END)
+            break;
+        default:
+            assert(e >= MQE_TOP_FIRST);
+            assert(e < MQE_INVALID);
+            DEBUG_PRINTF("MQE_TOP + %d\n", ((int)e - MQE_TOP_FIRST));
+            ctx->s = TOPN_FN(limex, ctx->s, e - MQE_TOP_FIRST);
+    }
+#undef DEFINE_CASE
+}
+
+// "Classic" queue call, used by outfixes
+char JOIN(LIMEX_API_ROOT, _Q)(const struct NFA *n, struct mq *q, s64a end) {
+    const IMPL_NFA_T *limex = getImplNfa(n);
+
+    if (q->report_current) {
+        char rv = REPORTCURRENT_FN(limex, q);
+
+        q->report_current = 0;
+
+        if (rv == MO_HALT_MATCHING) {
+            return MO_HALT_MATCHING;
+        }
+    }
+
+    if (q->cur == q->end) {
+        return 1;
+    }
+
+    assert(q->cur + 1 < q->end); /* require at least two items */
+
+    struct CONTEXT_T ctx;
+    ctx.repeat_ctrl = getRepeatControlBase(q->state, sizeof(STATE_T));
+    ctx.repeat_state = q->streamState + limex->stateSize;
+    ctx.callback = q->cb;
+    ctx.context = q->context;
+    ctx.cached_estate = ZERO_STATE;
+    ctx.cached_br = 0;
+
+    assert(q->items[q->cur].location >= 0);
+    DEBUG_PRINTF("LOAD STATE\n");
+    ctx.s = *(STATE_T *)q->state;
+    assert(q->items[q->cur].type == MQE_START);
+
+    u64a offset = q->offset;
+    u64a sp = offset + q->items[q->cur].location;
+    u64a end_abs = offset + end;
+    q->cur++;
+
+    while (q->cur < q->end && sp <= end_abs) {
+        u64a ep = offset + q->items[q->cur].location;
+        ep = MIN(ep, end_abs);
+        assert(ep >= sp);
+
+        assert(sp >= offset); // We no longer do history buffer scans here.
+
+        if (sp >= ep) {
+            goto scan_done;
+        }
+
+        /* do main buffer region */
+        DEBUG_PRINTF("MAIN BUFFER SCAN\n");
+        assert(ep - offset <= q->length);
+        if (STREAMCB_FN(limex, q->buffer + sp - offset, ep - sp, &ctx, sp)
+                == MO_HALT_MATCHING) {
+            *(STATE_T *)q->state = ZERO_STATE;
+            return 0;
+        }
+
+        DEBUG_PRINTF("SCAN DONE\n");
+    scan_done:
+        sp = ep;
+
+       if (sp != offset + q->items[q->cur].location) {
+           assert(q->cur);
+           DEBUG_PRINTF("bail: sp = %llu end_abs == %llu offset == %llu\n",
+                        sp, end_abs, offset);
+           assert(sp == end_abs);
+           q->cur--;
+           q->items[q->cur].type = MQE_START;
+           q->items[q->cur].location = sp - offset;
+           DEBUG_PRINTF("bailing q->cur %u q->end %u\n", q->cur, q->end);
+           *(STATE_T *)q->state = ctx.s;
+           return MO_ALIVE;
+       }
+
+        JOIN(LIMEX_API_ROOT, _HandleEvent)(limex, q, &ctx, sp);
+
+        q->cur++;
+    }
+
+    EXPIRE_ESTATE_FN(limex, &ctx, sp);
+
+    DEBUG_PRINTF("END\n");
+    *(STATE_T *)q->state = ctx.s;
+
+    if (q->cur != q->end) {
+        q->cur--;
+        q->items[q->cur].type = MQE_START;
+        q->items[q->cur].location = sp - offset;
+        return MO_ALIVE;
+    }
+
+    return ISNONZERO_STATE(ctx.s);
+}
+
+/* used by suffix execution in Rose */
+char JOIN(LIMEX_API_ROOT, _Q2)(const struct NFA *n, struct mq *q, s64a end) {
+    const IMPL_NFA_T *limex = getImplNfa(n);
+
+    if (q->report_current) {
+        char rv = REPORTCURRENT_FN(limex, q);
+
+        q->report_current = 0;
+
+        if (rv == MO_HALT_MATCHING) {
+            return MO_HALT_MATCHING;
+        }
+    }
+
+    if (q->cur == q->end) {
+        return 1;
+    }
+
+    assert(q->cur + 1 < q->end); /* require at least two items */
+
+    struct CONTEXT_T ctx;
+    ctx.repeat_ctrl = getRepeatControlBase(q->state, sizeof(STATE_T));
+    ctx.repeat_state = q->streamState + limex->stateSize;
+    ctx.callback = q->cb;
+    ctx.context = q->context;
+    ctx.cached_estate = ZERO_STATE;
+    ctx.cached_br = 0;
+
+    DEBUG_PRINTF("LOAD STATE\n");
+    ctx.s = *(STATE_T *)q->state;
+    assert(q->items[q->cur].type == MQE_START);
+
+    u64a offset = q->offset;
+    u64a sp = offset + q->items[q->cur].location;
+    u64a end_abs = offset + end;
+    q->cur++;
+
+    while (q->cur < q->end && sp <= end_abs) {
+        u64a ep = offset + q->items[q->cur].location;
+        DEBUG_PRINTF("sp = %llu, ep = %llu, end_abs = %llu\n",
+                     sp, ep, end_abs);
+        ep = MIN(ep, end_abs);
+        assert(ep >= sp);
+
+        if (sp < offset) {
+            DEBUG_PRINTF("HISTORY BUFFER SCAN\n");
+            assert(offset - sp <= q->hlength);
+            u64a local_ep = MIN(offset, ep);
+            u64a final_look = 0;
+            /* we are starting inside the history buffer */
+            if (STREAMFIRST_FN(limex, q->history + q->hlength + sp - offset,
+                               local_ep - sp, &ctx, sp,
+                               &final_look) == MO_HALT_MATCHING) {
+                DEBUG_PRINTF("final_look:%llu sp:%llu end_abs:%llu "
+                             "offset:%llu\n", final_look, sp, end_abs, offset);
+                assert(q->cur);
+                q->cur--;
+                q->items[q->cur].type = MQE_START;
+                q->items[q->cur].location = sp + final_look - offset;
+                *(STATE_T *)q->state = ctx.s;
+                return MO_MATCHES_PENDING;
+            }
+
+            sp = local_ep;
+        }
+
+        if (sp >= ep) {
+            goto scan_done;
+        }
+
+        /* do main buffer region */
+        u64a final_look = 0;
+        assert(ep - offset <= q->length);
+        if (STREAMFIRST_FN(limex, q->buffer + sp - offset, ep - sp, &ctx, sp,
+                           &final_look) == MO_HALT_MATCHING) {
+            DEBUG_PRINTF("final_look:%llu sp:%llu end_abs:%llu offset:%llu\n",
+                         final_look, sp, end_abs, offset);
+            assert(q->cur);
+            q->cur--;
+            q->items[q->cur].type = MQE_START;
+            q->items[q->cur].location = sp + final_look - offset;
+            *(STATE_T *)q->state = ctx.s;
+            return MO_MATCHES_PENDING;
+        }
+
+    scan_done:
+        sp = ep;
+
+        if (sp != offset + q->items[q->cur].location) {
+            assert(q->cur);
+            DEBUG_PRINTF("bail: sp = %llu end_abs == %llu offset == %llu\n",
+                         sp, end_abs, offset);
+            assert(sp == end_abs);
+            q->cur--;
+            q->items[q->cur].type = MQE_START;
+            q->items[q->cur].location = sp - offset;
+            DEBUG_PRINTF("bailing q->cur %u q->end %u\n", q->cur, q->end);
+            *(STATE_T *)q->state = ctx.s;
+            return MO_ALIVE;
+        }
+
+        JOIN(LIMEX_API_ROOT, _HandleEvent)(limex, q, &ctx, sp);
+
+        q->cur++;
+    }
+
+    EXPIRE_ESTATE_FN(limex, &ctx, sp);
+
+    DEBUG_PRINTF("END\n");
+    *(STATE_T *)q->state = ctx.s;
+
+    if (q->cur != q->end) {
+        q->cur--;
+        q->items[q->cur].type = MQE_START;
+        q->items[q->cur].location = sp - offset;
+        return MO_ALIVE;
+    }
+
+    return ISNONZERO_STATE(ctx.s);
+}
+
+// Used for execution Rose prefix/infixes.
+char JOIN(LIMEX_API_ROOT, _QR)(const struct NFA *n, struct mq *q,
+                                  ReportID report) {
+    const IMPL_NFA_T *limex = getImplNfa(n);
+
+    if (q->cur == q->end) {
+        return 1;
+    }
+
+    assert(q->cur + 1 < q->end); /* require at least two items */
+
+    struct CONTEXT_T ctx;
+    ctx.repeat_ctrl = getRepeatControlBase(q->state, sizeof(STATE_T));
+    ctx.repeat_state = q->streamState + limex->stateSize;
+    ctx.callback = NULL;
+    ctx.context = NULL;
+    ctx.cached_estate = ZERO_STATE;
+    ctx.cached_br = 0;
+
+    DEBUG_PRINTF("LOAD STATE\n");
+    ctx.s = *(STATE_T *)q->state;
+    assert(q->items[q->cur].type == MQE_START);
+
+    u64a offset = q->offset;
+    u64a sp = offset + q->items[q->cur].location;
+    q->cur++;
+
+    while (q->cur < q->end) {
+        u64a ep = offset + q->items[q->cur].location;
+        if (n->maxWidth) {
+            if (ep - sp > n->maxWidth) {
+                sp = ep - n->maxWidth;
+                ctx.s = INITIAL_FN(limex, !!sp);
+            }
+        }
+        assert(ep >= sp);
+
+        if (sp < offset) {
+            DEBUG_PRINTF("HISTORY BUFFER SCAN\n");
+            assert(offset - sp <= q->hlength);
+            u64a local_ep = MIN(offset, ep);
+            /* we are starting inside the history buffer */
+            STREAMSILENT_FN(limex, q->history + q->hlength + sp - offset,
+                            local_ep - sp, &ctx, sp);
+
+            sp = local_ep;
+        }
+
+        if (sp >= ep) {
+            goto scan_done;
+        }
+
+        /* do main buffer region */
+        DEBUG_PRINTF("MAIN BUFFER SCAN\n");
+        assert(ep - offset <= q->length);
+        STREAMSILENT_FN(limex, q->buffer + sp - offset, ep - sp, &ctx, sp);
+
+        DEBUG_PRINTF("SCAN DONE\n");
+    scan_done:
+        sp = ep;
+
+        JOIN(LIMEX_API_ROOT, _HandleEvent)(limex, q, &ctx, sp);
+
+        q->cur++;
+    }
+
+    EXPIRE_ESTATE_FN(limex, &ctx, sp);
+
+    DEBUG_PRINTF("END, nfa is %s\n",
+                 ISNONZERO_STATE(ctx.s) ? "still alive" : "dead");
+
+    *(STATE_T *)q->state = ctx.s;
+
+    if (JOIN(limexInAccept, SIZE)(limex, ctx.s, ctx.repeat_ctrl,
+                                  ctx.repeat_state, sp + 1, report)) {
+        return MO_MATCHES_PENDING;
+    }
+
+    return ISNONZERO_STATE(ctx.s);
+}
+
+char JOIN(LIMEX_API_ROOT, _testEOD)(const struct NFA *n, const char *state,
+                                    const char *streamState, u64a offset,
+                                    NfaCallback callback, void *context) {
+    assert(n && state);
+
+    const IMPL_NFA_T *limex = getImplNfa(n);
+    const STATE_T *sptr = (const STATE_T *)state;
+    const union RepeatControl *repeat_ctrl =
+        getRepeatControlBaseConst(state, sizeof(STATE_T));
+    const char *repeat_state = streamState + limex->stateSize;
+    return TESTEOD_FN(limex, sptr, repeat_ctrl, repeat_state, offset, callback,
+                      context);
+}
+
+char JOIN(LIMEX_API_ROOT, _reportCurrent)(const struct NFA *n, struct mq *q) {
+    const IMPL_NFA_T *limex = getImplNfa(n);
+    REPORTCURRENT_FN(limex, q);
+    return 1;
+}
+
+// Block mode reverse scan.
+char JOIN(LIMEX_API_ROOT, _B_Reverse)(const struct NFA *n, u64a offset,
+                                      const u8 *buf, size_t buflen,
+                                      const u8 *hbuf, size_t hlen,
+                                      NfaCallback cb, void *context) {
+    assert(buf || hbuf);
+    assert(buflen || hlen);
+
+    struct CONTEXT_T ctx;
+    ctx.repeat_ctrl = NULL;
+    ctx.repeat_state = NULL;
+    ctx.callback = cb;
+    ctx.context = context;
+    ctx.cached_estate = ZERO_STATE;
+    ctx.cached_br = 0;
+
+    const IMPL_NFA_T *limex = getImplNfa(n);
+    ctx.s = INITIAL_FN(limex, 0); // always anchored
+
+    // 'buf' may be null, for example when we're scanning at EOD time.
+    if (buflen) {
+        assert(buf);
+        DEBUG_PRINTF("MAIN BUFFER SCAN, %zu bytes\n", buflen);
+        offset -= buflen;
+        REV_STREAM_FN(limex, buf, buflen, &ctx, offset);
+    }
+
+    if (hlen) {
+        assert(hbuf);
+        DEBUG_PRINTF("HISTORY BUFFER SCAN, %zu bytes\n", hlen);
+        offset -= hlen;
+        REV_STREAM_FN(limex, hbuf, hlen, &ctx, offset);
+    }
+
+    if (offset == 0 && limex->acceptEodCount && ISNONZERO_STATE(ctx.s)) {
+        const union RepeatControl *repeat_ctrl = NULL;
+        const char *repeat_state = NULL;
+        TESTEOD_FN(limex, &ctx.s, repeat_ctrl, repeat_state, offset, cb,
+                   context);
+    }
+
+    // NOTE: return value is unused.
+    return 0;
+}
+
+char JOIN(LIMEX_API_ROOT, _inAccept)(const struct NFA *nfa,
+                                        ReportID report, struct mq *q) {
+    assert(nfa && q);
+    assert(q->state && q->streamState);
+
+    const IMPL_NFA_T *limex = getImplNfa(nfa);
+    union RepeatControl *repeat_ctrl =
+        getRepeatControlBase(q->state, sizeof(STATE_T));
+    char *repeat_state = q->streamState + limex->stateSize;
+    STATE_T state = *(STATE_T *)q->state;
+    u64a offset = q->offset + q_last_loc(q) + 1;
+
+    return JOIN(limexInAccept, SIZE)(limex, state, repeat_ctrl, repeat_state,
+                                     offset, report);
+}
+
+char JOIN(LIMEX_API_ROOT, _inAnyAccept)(const struct NFA *nfa, struct mq *q) {
+    assert(nfa && q);
+    assert(q->state && q->streamState);
+
+    const IMPL_NFA_T *limex = getImplNfa(nfa);
+    union RepeatControl *repeat_ctrl =
+        getRepeatControlBase(q->state, sizeof(STATE_T));
+    char *repeat_state = q->streamState + limex->stateSize;
+    STATE_T state = *(STATE_T *)q->state;
+    u64a offset = q->offset + q_last_loc(q) + 1;
+
+    return JOIN(limexInAnyAccept, SIZE)(limex, state, repeat_ctrl, repeat_state,
+                                        offset);
+}
+
+enum nfa_zombie_status JOIN(LIMEX_API_ROOT, _zombie_status)(
+                                                         const struct NFA *nfa,
+                                                         struct mq *q,
+                                                         s64a loc) {
+    assert(nfa->flags & NFA_ZOMBIE);
+    const IMPL_NFA_T *limex = getImplNfa(nfa);
+    STATE_T state = *(STATE_T *)q->state;
+    STATE_T zmask = LOAD_FROM_ENG(&limex->zombieMask);
+
+    if (limex->repeatCount) {
+        u64a offset = q->offset + loc + 1;
+        union RepeatControl *repeat_ctrl =
+            getRepeatControlBase(q->state, sizeof(STATE_T));
+        char *repeat_state = q->streamState + limex->stateSize;
+        SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &state);
+    }
+
+    if (ISNONZERO_STATE(AND_STATE(state, zmask))) {
+        return NFA_ZOMBIE_ALWAYS_YES;
+    }
+
+    return NFA_ZOMBIE_NO;
+}
+
+#undef TESTEOD_FN
+#undef INITIAL_FN
+#undef TOP_FN
+#undef TOPN_FN
+#undef REPORTCURRENT_FN
+#undef COMPRESS_FN
+#undef EXPAND_FN
+#undef COMPRESS_REPEATS_FN
+#undef EXPAND_REPEATS_FN
+#undef PROCESS_ACCEPTS_FN
+#undef PROCESS_ACCEPTS_NOSQUASH_FN
+#undef GET_NFA_REPEAT_INFO_FN
+#undef RUN_ACCEL_FN
+#undef RUN_EXCEPTIONS_FN
+#undef REV_STREAM_FN
+#undef LOOP_NOACCEL_FN
+#undef STREAM_FN
+#undef STREAMCB_FN
+#undef STREAMFIRST_FN
+#undef STREAMSILENT_FN
+#undef CONTEXT_T
+#undef EXCEPTION_T
+#undef AND_STATE
+#undef ANDNOT_STATE
+#undef OR_STATE
+#undef LSHIFT_STATE
+#undef TESTBIT_STATE
+#undef CLEARBIT_STATE
+#undef ZERO_STATE
+#undef ISNONZERO_STATE
+#undef ISZERO_STATE
+#undef NOTEQ_STATE
+#undef DIFFRICH_STATE
+#undef INLINE_ATTR_INT
+#undef IMPL_NFA_T
+#undef SQUASH_UNTUG_BR_FN
+#undef ACCEL_MASK
+#undef ACCEL_AND_FRIENDS_MASK
+#undef EXCEPTION_MASK
+#undef LIMEX_API_ROOT