Restoring authorship annotation for Ivan Blinkov <ivan@blinkov.ru>. Commit 1 of 2.

1 files changed, 441 insertions, 441 deletions

diff --git a/contrib/libs/hyperscan/src/nfa/tamarama.c b/contrib/libs/hyperscan/src/nfa/tamarama.c
index 43480f0650..8a2f633e09 100644
--- a/contrib/libs/hyperscan/src/nfa/tamarama.c
+++ b/contrib/libs/hyperscan/src/nfa/tamarama.c
@@ -1,441 +1,441 @@
-/*
- * Copyright (c) 2016, 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.
- */
-
-/** \file
-    \brief Tamarama: container engine for exclusive engines, runtime code.
-*/
-#include "config.h"
-
-#include "tamarama.h"
-
-#include "tamarama_internal.h"
-#include "nfa_api.h"
-#include "nfa_api_queue.h"
-#include "nfa_api_util.h"
-#include "nfa_internal.h"
-#include "scratch.h"
-#include "util/partial_store.h"
-
-static really_inline
-u32 getSubOffset(const struct Tamarama *t, u32 num) {
-    DEBUG_PRINTF("subengine:%u\n", num);
-    assert(num < t->numSubEngines);
-    const u32 *sub =
-        (const u32 *)((const char *)t + sizeof(struct Tamarama) +
-                      t->numSubEngines * sizeof(u32));
-    assert(ISALIGNED(sub));
-    return sub[num];
-}
-
-static
-const struct NFA *getSubEngine(const struct Tamarama *t,
-                               const u32 activeIdx) {
-    const u32 offset = getSubOffset(t, activeIdx);
-    DEBUG_PRINTF("activeIdx:%u offsets:%u\n", activeIdx, offset);
-    const char *base = (const char *)t;
-    return (const struct NFA *)(base + offset);
-}
-
-static
-void storeActiveIdx(const struct Tamarama *t, char *state,
-                    const u32 idx) {
-    assert(idx <= t->numSubEngines);
-    partial_store_u32(state, idx, t->activeIdxSize);
-}
-
-static
-u32 loadActiveIdx(const char *state,
-                  const u32 activeIdxSize) {
-    return partial_load_u32(state, activeIdxSize);
-}
-
-static really_inline
-void copyQueueProperties(const struct mq *q1, struct mq *q2,
-                         const u32 activeIdxSize) {
-    q2->state = q1->state;
-    q2->streamState = q1->streamState + activeIdxSize;
-    q2->offset = q1->offset;
-    q2->buffer = q1->buffer;
-    q2->length = q1->length;
-    q2->history = q1->history;
-    q2->hlength = q1->hlength;
-    q2->cb = q1->cb;
-    q2->context = q1->context;
-    q2->scratch = q1->scratch;
-    q2->report_current = q1->report_current;
-}
-
-static
-void copyQueueItems(const struct Tamarama *t, const struct NFA *sub,
-                    struct mq *q1, struct mq *q2, const u32 activeIdx) {
-    const u32 *baseTop = (const u32 *)((const char *)t +
-                                       sizeof(struct Tamarama));
-
-    u32 lower = baseTop[activeIdx];
-    u32 upper = activeIdx == t->numSubEngines - 1 ?
-                    ~0U : baseTop[activeIdx + 1];
-    u32 event_base = isMultiTopType(sub->type) ? MQE_TOP_FIRST : MQE_TOP;
-    while (q1->cur < q1->end) {
-        u32 type = q1->items[q1->cur].type;
-        s64a loc = q1->items[q1->cur].location;
-        DEBUG_PRINTF("type:%u lower:%u upper:%u\n", type, lower, upper);
-        if (type >= lower && type < upper) {
-            u32 event = event_base;
-            if (event == MQE_TOP_FIRST) {
-                event += type - lower;
-            }
-            pushQueue(q2, event, loc);
-        } else {
-            pushQueueNoMerge(q2, MQE_END, loc);
-            break;
-        }
-        q1->cur++;
-    }
-}
-
-static
-void copyQueue(const struct Tamarama *t, const struct NFA *sub,
-               struct mq *q1, struct mq *q2, const u32 activeIdx) {
-    copyQueueProperties(q1, q2, t->activeIdxSize);
-
-    // copy MQE_START item
-    u32 cur = q1->cur++;
-    q2->cur = cur;
-    q2->items[cur] = q1->items[cur];
-    q2->end = cur + 1;
-
-    copyQueueItems(t, sub, q1, q2, activeIdx);
-    // restore cur index of the main queue
-    q1->cur = cur;
-}
-
-static
-u32 findEngineForTop(const u32 *baseTop, const u32 cur,
-                     const u32 numSubEngines) {
-    u32 i;
-    for (i = 0; i < numSubEngines; ++i) {
-        DEBUG_PRINTF("cur:%u base:%u\n", cur, baseTop[i]);
-        if (cur >= baseTop[i] &&
-            (i == numSubEngines - 1 || cur < baseTop[i + 1])) {
-            break;
-        }
-    }
-    return i;
-}
-
-static
-void initSubQueue(const struct Tamarama *t, struct mq *q1,
-                  struct mq *q2, const u32 lastActiveIdx,
-                  const u32 activeIdx) {
-    // Push events to the new queue
-    const struct NFA *sub = getSubEngine(t, activeIdx);
-    assert(!isContainerType(sub->type));
-    q2->nfa = sub;
-
-    // Reinitialize state if the last active subengine is different
-    // from current one
-    if (lastActiveIdx == t->numSubEngines ||
-        lastActiveIdx != activeIdx) {
-        nfaQueueInitState(q2->nfa, q2);
-    }
-
-    copyQueueItems(t, sub, q1, q2, activeIdx);
-    if (q1->items[q1->cur].type == MQE_END) {
-        q1->cur++;
-    }
-    DEBUG_PRINTF("update lastIdx:%u\n", activeIdx);
-    storeActiveIdx(t, q1->streamState, activeIdx);
-}
-
-static
-void updateQueues(const struct Tamarama *t, struct mq *q1, struct mq *q2) {
-    q2->cur = q2->end = 0;
-    copyQueueProperties(q1, q2, t->activeIdxSize);
-
-    const u32 numSubEngines = t->numSubEngines;
-    u32 lastActiveIdx = loadActiveIdx(q1->streamState,
-                                      t->activeIdxSize);
-#ifdef DEBUG
-    DEBUG_PRINTF("external queue\n");
-    debugQueue(q1);
-#endif
-
-    // Push MQE_START event to the subqueue
-    s64a loc = q1->items[q1->cur].location;
-    pushQueueAt(q2, 0, MQE_START, loc);
-    char hasStart = 0;
-    if (q1->items[q1->cur].type == MQE_START) {
-        hasStart = 1;
-        q1->cur++;
-    }
-
-    u32 activeIdx = lastActiveIdx;
-    // If we have top events in the main queue, update current active id
-    if (q1->cur < q1->end - 1) {
-        const u32 *baseTop = (const u32 *)((const char *)t +
-                                           sizeof(struct Tamarama));
-        u32 curTop = q1->items[q1->cur].type;
-        activeIdx = findEngineForTop(baseTop, curTop, numSubEngines);
-    }
-
-    assert(activeIdx < numSubEngines);
-    DEBUG_PRINTF("last id:%u, current id:%u, num of subengines:%u\n",
-                 lastActiveIdx, activeIdx, numSubEngines);
-    // Handle unfinished last alive subengine
-    if (lastActiveIdx != activeIdx &&
-        lastActiveIdx != numSubEngines && hasStart) {
-        loc = q1->items[q1->cur].location;
-        pushQueueNoMerge(q2, MQE_END, loc);
-        q2->nfa = getSubEngine(t, lastActiveIdx);
-        return;
-    }
-
-    initSubQueue(t, q1, q2, lastActiveIdx, activeIdx);
-    DEBUG_PRINTF("finish queues\n");
-}
-
-// After processing subqueue items for subengines, we need to copy back
-// remaining items in subqueue if there are any to Tamarama main queue
-static
-void copyBack(const struct  Tamarama *t, struct mq *q, struct mq *q1) {
-    DEBUG_PRINTF("copy back %u, %u\n", q1->cur, q1->end);
-    q->report_current = q1->report_current;
-    if (q->cur >= q->end && q1->cur >= q1->end) {
-        return;
-    }
-
-    const u32 *baseTop = (const u32 *)((const char *)t +
-                                        sizeof(struct Tamarama));
-    const u32 lastIdx = loadActiveIdx(q->streamState,
-                                      t->activeIdxSize);
-    u32 base = 0, event_base = 0;
-    if (lastIdx != t->numSubEngines) {
-        base = baseTop[lastIdx];
-        const struct NFA *sub = getSubEngine(t, lastIdx);
-        event_base = isMultiTopType(sub->type) ? MQE_TOP_FIRST : MQE_TOP;
-    }
-
-    u32 numItems = q1->end > q1->cur + 1 ? q1->end - q1->cur - 1 : 1;
-    // Also need to copy MQE_END if the main queue is empty
-    if (q->cur == q->end) {
-        assert(q->cur > 1 && q1->items[q1->end - 1].type == MQE_END);
-        q->items[--q->cur] = q1->items[q1->end - 1];
-    }
-    u32 cur = q->cur - numItems;
-    q->items[cur] = q1->items[q1->cur++];
-    q->items[cur].type = MQE_START;
-    q->cur = cur++;
-    for (u32 i = 0; i < numItems - 1; ++i) {
-        assert(q1->cur < q1->end);
-        u32 type = q1->items[q1->cur].type;
-        if (type > MQE_END) {
-            q1->items[q1->cur].type = type - event_base + base;
-        }
-        q->items[cur++] = q1->items[q1->cur++];
-    }
-
-#ifdef DEBUG
-    DEBUG_PRINTF("external queue\n");
-    debugQueue(q);
-#endif
-}
-
-char nfaExecTamarama_testEOD(const struct NFA *n, const char *state,
-                             const char *streamState, u64a offset,
-                             NfaCallback callback, void *context) {
-    const struct Tamarama *t = getImplNfa(n);
-    u32 activeIdx = loadActiveIdx(streamState, t->activeIdxSize);
-    if (activeIdx == t->numSubEngines) {
-        return MO_CONTINUE_MATCHING;
-    }
-
-    const struct NFA *sub = getSubEngine(t, activeIdx);
-    if (nfaAcceptsEod(sub)) {
-        assert(!isContainerType(sub->type));
-        const char *subStreamState = streamState + t->activeIdxSize;
-        return nfaCheckFinalState(sub, state, subStreamState, offset, callback,
-                                  context);
-    }
-
-    return MO_CONTINUE_MATCHING;
-}
-
-char nfaExecTamarama_QR(const struct NFA *n, struct mq *q, ReportID report) {
-    DEBUG_PRINTF("exec rose\n");
-    struct mq q1;
-    q1.cur = q1.end = 0;
-    char rv = 0;
-    const struct Tamarama *t = getImplNfa(n);
-    while (q->cur < q->end) {
-        updateQueues(t, q, &q1);
-    }
-
-    if (q1.cur < q1.end) {
-        rv = nfaQueueExecRose(q1.nfa, &q1, report);
-    }
-
-    DEBUG_PRINTF("exec rose rv:%u\n", rv);
-    return rv;
-}
-
-char nfaExecTamarama_reportCurrent(const struct NFA *n, struct mq *q) {
-    const struct Tamarama *t = getImplNfa(n);
-    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize);
-    if (activeIdx == t->numSubEngines) {
-        return 1;
-    }
-
-    const struct NFA *sub = getSubEngine(t, activeIdx);
-    struct mq q1;
-    copyQueue(t, sub, q, &q1, activeIdx);
-    return nfaReportCurrentMatches(sub, &q1);
-}
-
-char nfaExecTamarama_inAccept(const struct NFA *n, ReportID report,
-                              struct mq *q) {
-    const struct Tamarama *t = getImplNfa(n);
-    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize);
-    if (activeIdx == t->numSubEngines) {
-        return 0;
-    }
-    const struct NFA *sub = getSubEngine(t, activeIdx);
-
-    struct mq q1;
-    copyQueue(t, sub, q, &q1, activeIdx);
-    return nfaInAcceptState(sub, report, &q1);
-}
-
-char nfaExecTamarama_inAnyAccept(const struct NFA *n, struct mq *q) {
-    const struct Tamarama *t = getImplNfa(n);
-    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize);
-    if (activeIdx == t->numSubEngines) {
-        return 0;
-    }
-    const struct NFA *sub = getSubEngine(t, activeIdx);
-
-    struct mq q1;
-    copyQueue(t, sub, q, &q1, activeIdx);
-    return nfaInAnyAcceptState(sub, &q1);
-}
-
-char nfaExecTamarama_queueInitState(const struct NFA *n, struct mq *q) {
-    DEBUG_PRINTF("init state\n");
-    const struct Tamarama *t = getImplNfa(n);
-    char *ptr = q->streamState;
-    // Use activeIdxSize as a sentinel value and initialize the state to
-    // an invalid engine as nothing has been triggered yet
-    storeActiveIdx(t, ptr, t->numSubEngines);
-    return 0;
-}
-
-char nfaExecTamarama_queueCompressState(const struct NFA *n, const struct mq *q,
-                                        s64a loc) {
-    const struct Tamarama *t = getImplNfa(n);
-    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize);
-    if (activeIdx == t->numSubEngines) {
-        return 0;
-    }
-
-    const struct NFA *sub = getSubEngine(t, activeIdx);
-
-    struct mq q1;
-    copyQueueProperties(q, &q1, t->activeIdxSize);
-    return nfaQueueCompressState(sub, &q1, loc);
-}
-
-char nfaExecTamarama_expandState(const struct NFA *n, void *dest,
-                                 const void *src, u64a offset, u8 key) {
-    const struct Tamarama *t = getImplNfa(n);
-    u32 activeIdx = loadActiveIdx(src, t->activeIdxSize);
-    if (activeIdx == t->numSubEngines) {
-        return 0;
-    }
-
-    const struct NFA *sub = getSubEngine(t, activeIdx);
-
-    const char *subStreamState = (const char *)src + t->activeIdxSize;
-    return nfaExpandState(sub, dest, subStreamState, offset, key);
-}
-
-enum nfa_zombie_status nfaExecTamarama_zombie_status(const struct NFA *n,
-                                                     struct mq *q, s64a loc) {
-    const struct Tamarama *t = getImplNfa(n);
-    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize);
-    if (activeIdx == t->numSubEngines) {
-        return NFA_ZOMBIE_NO;
-    }
-    const struct NFA *sub = getSubEngine(t, activeIdx);
-
-    struct mq q1;
-    copyQueue(t, sub, q, &q1, activeIdx);
-    return nfaGetZombieStatus(sub, &q1, loc);
-}
-
-char nfaExecTamarama_Q(const struct NFA *n, struct mq *q, s64a end) {
-    DEBUG_PRINTF("exec\n");
-    struct mq q1;
-    char rv = MO_ALIVE;
-    char copy = 0;
-    const struct Tamarama *t = getImplNfa(n);
-    while (q->cur < q->end && q_cur_loc(q) <= end) {
-        updateQueues(t, q, &q1);
-        rv = nfaQueueExec_raw(q1.nfa, &q1, end);
-        q->report_current = q1.report_current;
-        copy = 1;
-        if (can_stop_matching(q->scratch)) {
-            break;
-        }
-    }
-    if (copy) {
-        copyBack(t, q, &q1);
-    }
-    return rv;
-}
-
-char nfaExecTamarama_Q2(const struct NFA *n, struct mq *q, s64a end) {
-    DEBUG_PRINTF("exec to match\n");
-    struct mq q1;
-    char rv = 0;
-    char copy = 0;
-    const struct Tamarama *t = getImplNfa(n);
-    while (q->cur < q->end && q_cur_loc(q) <= end &&
-           rv != MO_MATCHES_PENDING) {
-        updateQueues(t, q, &q1);
-        rv = nfaQueueExec2_raw(q1.nfa, &q1, end);
-        q->report_current = q1.report_current;
-        copy = 1;
-        if (can_stop_matching(q->scratch)) {
-            break;
-        }
-    }
-    if (copy) {
-        copyBack(t, q, &q1);
-    }
-    return rv;
-}
-
+/* 
+ * Copyright (c) 2016, 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. 
+ */ 
+ 
+/** \file 
+    \brief Tamarama: container engine for exclusive engines, runtime code. 
+*/ 
+#include "config.h" 
+ 
+#include "tamarama.h" 
+ 
+#include "tamarama_internal.h" 
+#include "nfa_api.h" 
+#include "nfa_api_queue.h" 
+#include "nfa_api_util.h" 
+#include "nfa_internal.h" 
+#include "scratch.h" 
+#include "util/partial_store.h" 
+ 
+static really_inline 
+u32 getSubOffset(const struct Tamarama *t, u32 num) { 
+    DEBUG_PRINTF("subengine:%u\n", num); 
+    assert(num < t->numSubEngines); 
+    const u32 *sub = 
+        (const u32 *)((const char *)t + sizeof(struct Tamarama) + 
+                      t->numSubEngines * sizeof(u32)); 
+    assert(ISALIGNED(sub)); 
+    return sub[num]; 
+} 
+ 
+static 
+const struct NFA *getSubEngine(const struct Tamarama *t, 
+                               const u32 activeIdx) { 
+    const u32 offset = getSubOffset(t, activeIdx); 
+    DEBUG_PRINTF("activeIdx:%u offsets:%u\n", activeIdx, offset); 
+    const char *base = (const char *)t; 
+    return (const struct NFA *)(base + offset); 
+} 
+ 
+static 
+void storeActiveIdx(const struct Tamarama *t, char *state, 
+                    const u32 idx) { 
+    assert(idx <= t->numSubEngines); 
+    partial_store_u32(state, idx, t->activeIdxSize); 
+} 
+ 
+static 
+u32 loadActiveIdx(const char *state, 
+                  const u32 activeIdxSize) { 
+    return partial_load_u32(state, activeIdxSize); 
+} 
+ 
+static really_inline 
+void copyQueueProperties(const struct mq *q1, struct mq *q2, 
+                         const u32 activeIdxSize) { 
+    q2->state = q1->state; 
+    q2->streamState = q1->streamState + activeIdxSize; 
+    q2->offset = q1->offset; 
+    q2->buffer = q1->buffer; 
+    q2->length = q1->length; 
+    q2->history = q1->history; 
+    q2->hlength = q1->hlength; 
+    q2->cb = q1->cb; 
+    q2->context = q1->context; 
+    q2->scratch = q1->scratch; 
+    q2->report_current = q1->report_current; 
+} 
+ 
+static 
+void copyQueueItems(const struct Tamarama *t, const struct NFA *sub, 
+                    struct mq *q1, struct mq *q2, const u32 activeIdx) { 
+    const u32 *baseTop = (const u32 *)((const char *)t + 
+                                       sizeof(struct Tamarama)); 
+ 
+    u32 lower = baseTop[activeIdx]; 
+    u32 upper = activeIdx == t->numSubEngines - 1 ? 
+                    ~0U : baseTop[activeIdx + 1]; 
+    u32 event_base = isMultiTopType(sub->type) ? MQE_TOP_FIRST : MQE_TOP; 
+    while (q1->cur < q1->end) { 
+        u32 type = q1->items[q1->cur].type; 
+        s64a loc = q1->items[q1->cur].location; 
+        DEBUG_PRINTF("type:%u lower:%u upper:%u\n", type, lower, upper); 
+        if (type >= lower && type < upper) { 
+            u32 event = event_base; 
+            if (event == MQE_TOP_FIRST) { 
+                event += type - lower; 
+            } 
+            pushQueue(q2, event, loc); 
+        } else { 
+            pushQueueNoMerge(q2, MQE_END, loc); 
+            break; 
+        } 
+        q1->cur++; 
+    } 
+} 
+ 
+static 
+void copyQueue(const struct Tamarama *t, const struct NFA *sub, 
+               struct mq *q1, struct mq *q2, const u32 activeIdx) { 
+    copyQueueProperties(q1, q2, t->activeIdxSize); 
+ 
+    // copy MQE_START item 
+    u32 cur = q1->cur++; 
+    q2->cur = cur; 
+    q2->items[cur] = q1->items[cur]; 
+    q2->end = cur + 1; 
+ 
+    copyQueueItems(t, sub, q1, q2, activeIdx); 
+    // restore cur index of the main queue 
+    q1->cur = cur; 
+} 
+ 
+static 
+u32 findEngineForTop(const u32 *baseTop, const u32 cur, 
+                     const u32 numSubEngines) { 
+    u32 i; 
+    for (i = 0; i < numSubEngines; ++i) { 
+        DEBUG_PRINTF("cur:%u base:%u\n", cur, baseTop[i]); 
+        if (cur >= baseTop[i] && 
+            (i == numSubEngines - 1 || cur < baseTop[i + 1])) { 
+            break; 
+        } 
+    } 
+    return i; 
+} 
+ 
+static 
+void initSubQueue(const struct Tamarama *t, struct mq *q1, 
+                  struct mq *q2, const u32 lastActiveIdx, 
+                  const u32 activeIdx) { 
+    // Push events to the new queue 
+    const struct NFA *sub = getSubEngine(t, activeIdx); 
+    assert(!isContainerType(sub->type)); 
+    q2->nfa = sub; 
+ 
+    // Reinitialize state if the last active subengine is different 
+    // from current one 
+    if (lastActiveIdx == t->numSubEngines || 
+        lastActiveIdx != activeIdx) { 
+        nfaQueueInitState(q2->nfa, q2); 
+    } 
+ 
+    copyQueueItems(t, sub, q1, q2, activeIdx); 
+    if (q1->items[q1->cur].type == MQE_END) { 
+        q1->cur++; 
+    } 
+    DEBUG_PRINTF("update lastIdx:%u\n", activeIdx); 
+    storeActiveIdx(t, q1->streamState, activeIdx); 
+} 
+ 
+static 
+void updateQueues(const struct Tamarama *t, struct mq *q1, struct mq *q2) { 
+    q2->cur = q2->end = 0; 
+    copyQueueProperties(q1, q2, t->activeIdxSize); 
+ 
+    const u32 numSubEngines = t->numSubEngines; 
+    u32 lastActiveIdx = loadActiveIdx(q1->streamState, 
+                                      t->activeIdxSize); 
+#ifdef DEBUG 
+    DEBUG_PRINTF("external queue\n"); 
+    debugQueue(q1); 
+#endif 
+ 
+    // Push MQE_START event to the subqueue 
+    s64a loc = q1->items[q1->cur].location; 
+    pushQueueAt(q2, 0, MQE_START, loc); 
+    char hasStart = 0; 
+    if (q1->items[q1->cur].type == MQE_START) { 
+        hasStart = 1; 
+        q1->cur++; 
+    } 
+ 
+    u32 activeIdx = lastActiveIdx; 
+    // If we have top events in the main queue, update current active id 
+    if (q1->cur < q1->end - 1) { 
+        const u32 *baseTop = (const u32 *)((const char *)t + 
+                                           sizeof(struct Tamarama)); 
+        u32 curTop = q1->items[q1->cur].type; 
+        activeIdx = findEngineForTop(baseTop, curTop, numSubEngines); 
+    } 
+ 
+    assert(activeIdx < numSubEngines); 
+    DEBUG_PRINTF("last id:%u, current id:%u, num of subengines:%u\n", 
+                 lastActiveIdx, activeIdx, numSubEngines); 
+    // Handle unfinished last alive subengine 
+    if (lastActiveIdx != activeIdx && 
+        lastActiveIdx != numSubEngines && hasStart) { 
+        loc = q1->items[q1->cur].location; 
+        pushQueueNoMerge(q2, MQE_END, loc); 
+        q2->nfa = getSubEngine(t, lastActiveIdx); 
+        return; 
+    } 
+ 
+    initSubQueue(t, q1, q2, lastActiveIdx, activeIdx); 
+    DEBUG_PRINTF("finish queues\n"); 
+} 
+ 
+// After processing subqueue items for subengines, we need to copy back 
+// remaining items in subqueue if there are any to Tamarama main queue 
+static 
+void copyBack(const struct  Tamarama *t, struct mq *q, struct mq *q1) { 
+    DEBUG_PRINTF("copy back %u, %u\n", q1->cur, q1->end); 
+    q->report_current = q1->report_current; 
+    if (q->cur >= q->end && q1->cur >= q1->end) { 
+        return; 
+    } 
+ 
+    const u32 *baseTop = (const u32 *)((const char *)t + 
+                                        sizeof(struct Tamarama)); 
+    const u32 lastIdx = loadActiveIdx(q->streamState, 
+                                      t->activeIdxSize); 
+    u32 base = 0, event_base = 0; 
+    if (lastIdx != t->numSubEngines) { 
+        base = baseTop[lastIdx]; 
+        const struct NFA *sub = getSubEngine(t, lastIdx); 
+        event_base = isMultiTopType(sub->type) ? MQE_TOP_FIRST : MQE_TOP; 
+    } 
+ 
+    u32 numItems = q1->end > q1->cur + 1 ? q1->end - q1->cur - 1 : 1; 
+    // Also need to copy MQE_END if the main queue is empty 
+    if (q->cur == q->end) { 
+        assert(q->cur > 1 && q1->items[q1->end - 1].type == MQE_END); 
+        q->items[--q->cur] = q1->items[q1->end - 1]; 
+    } 
+    u32 cur = q->cur - numItems; 
+    q->items[cur] = q1->items[q1->cur++]; 
+    q->items[cur].type = MQE_START; 
+    q->cur = cur++; 
+    for (u32 i = 0; i < numItems - 1; ++i) { 
+        assert(q1->cur < q1->end); 
+        u32 type = q1->items[q1->cur].type; 
+        if (type > MQE_END) { 
+            q1->items[q1->cur].type = type - event_base + base; 
+        } 
+        q->items[cur++] = q1->items[q1->cur++]; 
+    } 
+ 
+#ifdef DEBUG 
+    DEBUG_PRINTF("external queue\n"); 
+    debugQueue(q); 
+#endif 
+} 
+ 
+char nfaExecTamarama_testEOD(const struct NFA *n, const char *state, 
+                             const char *streamState, u64a offset, 
+                             NfaCallback callback, void *context) { 
+    const struct Tamarama *t = getImplNfa(n); 
+    u32 activeIdx = loadActiveIdx(streamState, t->activeIdxSize); 
+    if (activeIdx == t->numSubEngines) { 
+        return MO_CONTINUE_MATCHING; 
+    } 
+ 
+    const struct NFA *sub = getSubEngine(t, activeIdx); 
+    if (nfaAcceptsEod(sub)) { 
+        assert(!isContainerType(sub->type)); 
+        const char *subStreamState = streamState + t->activeIdxSize; 
+        return nfaCheckFinalState(sub, state, subStreamState, offset, callback, 
+                                  context); 
+    } 
+ 
+    return MO_CONTINUE_MATCHING; 
+} 
+ 
+char nfaExecTamarama_QR(const struct NFA *n, struct mq *q, ReportID report) { 
+    DEBUG_PRINTF("exec rose\n"); 
+    struct mq q1; 
+    q1.cur = q1.end = 0; 
+    char rv = 0; 
+    const struct Tamarama *t = getImplNfa(n); 
+    while (q->cur < q->end) { 
+        updateQueues(t, q, &q1); 
+    } 
+ 
+    if (q1.cur < q1.end) { 
+        rv = nfaQueueExecRose(q1.nfa, &q1, report); 
+    } 
+ 
+    DEBUG_PRINTF("exec rose rv:%u\n", rv); 
+    return rv; 
+} 
+ 
+char nfaExecTamarama_reportCurrent(const struct NFA *n, struct mq *q) { 
+    const struct Tamarama *t = getImplNfa(n); 
+    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize); 
+    if (activeIdx == t->numSubEngines) { 
+        return 1; 
+    } 
+ 
+    const struct NFA *sub = getSubEngine(t, activeIdx); 
+    struct mq q1; 
+    copyQueue(t, sub, q, &q1, activeIdx); 
+    return nfaReportCurrentMatches(sub, &q1); 
+} 
+ 
+char nfaExecTamarama_inAccept(const struct NFA *n, ReportID report, 
+                              struct mq *q) { 
+    const struct Tamarama *t = getImplNfa(n); 
+    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize); 
+    if (activeIdx == t->numSubEngines) { 
+        return 0; 
+    } 
+    const struct NFA *sub = getSubEngine(t, activeIdx); 
+ 
+    struct mq q1; 
+    copyQueue(t, sub, q, &q1, activeIdx); 
+    return nfaInAcceptState(sub, report, &q1); 
+} 
+ 
+char nfaExecTamarama_inAnyAccept(const struct NFA *n, struct mq *q) { 
+    const struct Tamarama *t = getImplNfa(n); 
+    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize); 
+    if (activeIdx == t->numSubEngines) { 
+        return 0; 
+    } 
+    const struct NFA *sub = getSubEngine(t, activeIdx); 
+ 
+    struct mq q1; 
+    copyQueue(t, sub, q, &q1, activeIdx); 
+    return nfaInAnyAcceptState(sub, &q1); 
+} 
+ 
+char nfaExecTamarama_queueInitState(const struct NFA *n, struct mq *q) { 
+    DEBUG_PRINTF("init state\n"); 
+    const struct Tamarama *t = getImplNfa(n); 
+    char *ptr = q->streamState; 
+    // Use activeIdxSize as a sentinel value and initialize the state to 
+    // an invalid engine as nothing has been triggered yet 
+    storeActiveIdx(t, ptr, t->numSubEngines); 
+    return 0; 
+} 
+ 
+char nfaExecTamarama_queueCompressState(const struct NFA *n, const struct mq *q, 
+                                        s64a loc) { 
+    const struct Tamarama *t = getImplNfa(n); 
+    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize); 
+    if (activeIdx == t->numSubEngines) { 
+        return 0; 
+    } 
+ 
+    const struct NFA *sub = getSubEngine(t, activeIdx); 
+ 
+    struct mq q1; 
+    copyQueueProperties(q, &q1, t->activeIdxSize); 
+    return nfaQueueCompressState(sub, &q1, loc); 
+} 
+ 
+char nfaExecTamarama_expandState(const struct NFA *n, void *dest, 
+                                 const void *src, u64a offset, u8 key) { 
+    const struct Tamarama *t = getImplNfa(n); 
+    u32 activeIdx = loadActiveIdx(src, t->activeIdxSize); 
+    if (activeIdx == t->numSubEngines) { 
+        return 0; 
+    } 
+ 
+    const struct NFA *sub = getSubEngine(t, activeIdx); 
+ 
+    const char *subStreamState = (const char *)src + t->activeIdxSize; 
+    return nfaExpandState(sub, dest, subStreamState, offset, key); 
+} 
+ 
+enum nfa_zombie_status nfaExecTamarama_zombie_status(const struct NFA *n, 
+                                                     struct mq *q, s64a loc) { 
+    const struct Tamarama *t = getImplNfa(n); 
+    u32 activeIdx = loadActiveIdx(q->streamState, t->activeIdxSize); 
+    if (activeIdx == t->numSubEngines) { 
+        return NFA_ZOMBIE_NO; 
+    } 
+    const struct NFA *sub = getSubEngine(t, activeIdx); 
+ 
+    struct mq q1; 
+    copyQueue(t, sub, q, &q1, activeIdx); 
+    return nfaGetZombieStatus(sub, &q1, loc); 
+} 
+ 
+char nfaExecTamarama_Q(const struct NFA *n, struct mq *q, s64a end) { 
+    DEBUG_PRINTF("exec\n"); 
+    struct mq q1; 
+    char rv = MO_ALIVE; 
+    char copy = 0; 
+    const struct Tamarama *t = getImplNfa(n); 
+    while (q->cur < q->end && q_cur_loc(q) <= end) { 
+        updateQueues(t, q, &q1); 
+        rv = nfaQueueExec_raw(q1.nfa, &q1, end); 
+        q->report_current = q1.report_current; 
+        copy = 1; 
+        if (can_stop_matching(q->scratch)) { 
+            break; 
+        } 
+    } 
+    if (copy) { 
+        copyBack(t, q, &q1); 
+    } 
+    return rv; 
+} 
+ 
+char nfaExecTamarama_Q2(const struct NFA *n, struct mq *q, s64a end) { 
+    DEBUG_PRINTF("exec to match\n"); 
+    struct mq q1; 
+    char rv = 0; 
+    char copy = 0; 
+    const struct Tamarama *t = getImplNfa(n); 
+    while (q->cur < q->end && q_cur_loc(q) <= end && 
+           rv != MO_MATCHES_PENDING) { 
+        updateQueues(t, q, &q1); 
+        rv = nfaQueueExec2_raw(q1.nfa, &q1, end); 
+        q->report_current = q1.report_current; 
+        copy = 1; 
+        if (can_stop_matching(q->scratch)) { 
+            break; 
+        } 
+    } 
+    if (copy) { 
+        copyBack(t, q, &q1); 
+    } 
+    return rv; 
+} 
+