1/*
2 * Copyright (c) 2015-2017, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#include "util/join.h"
30#include <string.h>
31
32/** \file
33 * \brief Limex Execution Engine Or:
34 * How I Learned To Stop Worrying And Love The Preprocessor
35 *
36 * Version 2.0: now with X-Macros, so you get line numbers in your debugger.
37 */
38
39
40#if !defined(SIZE) || !defined(STATE_T) || !defined(LOAD_FROM_ENG)
41# error Must define SIZE, STATE_T, LOAD_FROM_ENG in includer.
42#endif
43
44#define LIMEX_API_ROOT JOIN(nfaExecLimEx, SIZE)
45
46#define IMPL_NFA_T JOIN(struct LimExNFA, SIZE)
47
48#define TESTEOD_FN JOIN(moNfaTestEod, SIZE)
49#define INITIAL_FN JOIN(moNfaInitial, SIZE)
50#define TOP_FN JOIN(moNfaTop, SIZE)
51#define TOPN_FN JOIN(moNfaTopN, SIZE)
52#define REPORTCURRENT_FN JOIN(moNfaReportCurrent, SIZE)
53#define COMPRESS_FN JOIN(moNfaCompressState, SIZE)
54#define EXPAND_FN JOIN(moNfaExpandState, SIZE)
55#define COMPRESS_REPEATS_FN JOIN(LIMEX_API_ROOT, _Compress_Repeats)
56#define EXPAND_REPEATS_FN JOIN(LIMEX_API_ROOT, _Expand_Repeats)
57#define PROCESS_ACCEPTS_FN JOIN(moProcessAccepts, SIZE)
58#define PROCESS_ACCEPTS_NOSQUASH_FN JOIN(moProcessAcceptsNoSquash, SIZE)
59#define GET_NFA_REPEAT_INFO_FN JOIN(getNfaRepeatInfo, SIZE)
60#define RUN_ACCEL_FN JOIN(LIMEX_API_ROOT, _Run_Accel)
61#define RUN_EXCEPTIONS_FN JOIN(LIMEX_API_ROOT, _Run_Exceptions)
62#define REV_STREAM_FN JOIN(LIMEX_API_ROOT, _Rev_Stream)
63#define LOOP_NOACCEL_FN JOIN(LIMEX_API_ROOT, _Loop_No_Accel)
64#define STREAM_FN JOIN(LIMEX_API_ROOT, _Stream)
65#define STREAMCB_FN JOIN(LIMEX_API_ROOT, _Stream_CB)
66#define STREAMFIRST_FN JOIN(LIMEX_API_ROOT, _Stream_First)
67#define STREAMSILENT_FN JOIN(LIMEX_API_ROOT, _Stream_Silent)
68#define CONTEXT_T JOIN(NFAContext, SIZE)
69#define EXCEPTION_T JOIN(struct NFAException, SIZE)
70#define AND_STATE JOIN(and_, STATE_T)
71#define ANDNOT_STATE JOIN(andnot_, STATE_T)
72#define OR_STATE JOIN(or_, STATE_T)
73#define LSHIFT_STATE JOIN(lshift_, STATE_T)
74#define TESTBIT_STATE JOIN(testbit_, STATE_T)
75#define CLEARBIT_STATE JOIN(clearbit_, STATE_T)
76#define ZERO_STATE JOIN(zero_, STATE_T)
77#define ISNONZERO_STATE JOIN(isNonZero_, STATE_T)
78#define ISZERO_STATE JOIN(isZero_, STATE_T)
79#define NOTEQ_STATE JOIN(noteq_, STATE_T)
80
81// Pick an appropriate diffrich function for this platform.
82#ifdef ARCH_64_BIT
83#define DIFFRICH_STATE JOIN(diffrich64_, STATE_T)
84#else
85#define DIFFRICH_STATE JOIN(diffrich_, STATE_T)
86#endif
87
88#define EXPIRE_ESTATE_FN JOIN(limexExpireExtendedState, SIZE)
89#define SQUASH_UNTUG_BR_FN JOIN(lazyTug, SIZE)
90
91// Acceleration and exception masks: we load them on the fly for really big
92// models.
93#if SIZE < 256
94#define ACCEL_MASK accelMask
95#define ACCEL_AND_FRIENDS_MASK accel_and_friendsMask
96#define EXCEPTION_MASK exceptionMask
97#else
98#define ACCEL_MASK LOAD_FROM_ENG(&limex->accel)
99#define ACCEL_AND_FRIENDS_MASK LOAD_FROM_ENG(&limex->accel_and_friends)
100#define EXCEPTION_MASK LOAD_FROM_ENG(&limex->exceptionMask)
101#endif
102
103// Run exception processing, if necessary. Returns 0 if scanning should
104// continue, 1 if an accept was fired and the user instructed us to halt.
105static really_inline
106char RUN_EXCEPTIONS_FN(const IMPL_NFA_T *limex, const EXCEPTION_T *exceptions,
107 STATE_T s, const STATE_T emask, size_t i, u64a offset,
108 STATE_T *succ, u64a *final_loc, struct CONTEXT_T *ctx,
109 const char flags, const char in_rev,
110 const char first_match) {
111 STATE_T estate = AND_STATE(s, emask);
112 u32 diffmask = DIFFRICH_STATE(ZERO_STATE, estate);
113 if (likely(!diffmask)) {
114 return 0; // No exceptions to process.
115 }
116
117 if (first_match && i) {
118 STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept);
119 STATE_T foundAccepts = AND_STATE(s, acceptMask);
120 if (unlikely(ISNONZERO_STATE(foundAccepts))) {
121 DEBUG_PRINTF("first match at %zu\n", i);
122 DEBUG_PRINTF("for nfa %p\n", limex);
123 assert(final_loc);
124 ctx->s = s;
125 *final_loc = i;
126 return 1; // Halt matching.
127 }
128 }
129
130 u64a callback_offset = i + offset;
131 char localflags = (!i && !in_rev) ? NO_OUTPUT | FIRST_BYTE : flags;
132
133 int rv = JOIN(processExceptional, SIZE)(
134 pass_state, pass_estate, diffmask, succ, limex, exceptions,
135 callback_offset, ctx, in_rev, localflags);
136 if (rv == PE_RV_HALT) {
137 return 1; // Halt matching.
138 }
139
140 return 0;
141}
142
143static really_inline
144size_t RUN_ACCEL_FN(const STATE_T s, UNUSED const STATE_T accelMask,
145 UNUSED const IMPL_NFA_T *limex, const u8 *accelTable,
146 const union AccelAux *accelAux, const u8 *input, size_t i,
147 size_t length) {
148 size_t j;
149#if SIZE < 128
150 // For small cases, we pass the state by value.
151 j = JOIN(doAccel, SIZE)(s, accelMask, accelTable, accelAux, input, i,
152 length);
153#else
154 j = JOIN(doAccel, SIZE)(&s, limex, accelTable, accelAux, input, i, length);
155#endif
156
157 assert(j >= i);
158 assert(i <= length);
159 return j;
160}
161
162// Shift macros for Limited NFAs. Defined in terms of uniform ops.
163// LimExNFAxxx ptr in 'limex' and the current state in 's'
164#define NFA_EXEC_LIM_SHIFT(limex_m, curr_m, shift_idx) \
165 LSHIFT_STATE(AND_STATE(curr_m, LOAD_FROM_ENG(&limex_m->shift[shift_idx])), \
166 limex_m->shiftAmount[shift_idx])
167
168// Calculate the (limited model) successors for a number of variable shifts.
169// Assumes current state in 'curr_m' and places the successors in 'succ_m'.
170#define NFA_EXEC_GET_LIM_SUCC(limex_m, curr_m, succ_m) \
171 do { \
172 succ_m = NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 0); \
173 switch (limex_m->shiftCount) { \
174 case 8: \
175 succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 7)); \
176 /* fallthrough */ \
177 case 7: \
178 succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 6)); \
179 /* fallthrough */ \
180 case 6: \
181 succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 5)); \
182 /* fallthrough */ \
183 case 5: \
184 succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 4)); \
185 /* fallthrough */ \
186 case 4: \
187 succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 3)); \
188 /* fallthrough */ \
189 case 3: \
190 succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 2)); \
191 /* fallthrough */ \
192 case 2: \
193 succ_m = OR_STATE(succ_m, NFA_EXEC_LIM_SHIFT(limex_m, curr_m, 1)); \
194 /* fallthrough */ \
195 case 1: \
196 /* fallthrough */ \
197 case 0: \
198 ; \
199 } \
200 } while (0)
201
202/**
203 * \brief LimEx NFAS inner loop without accel.
204 *
205 * Note that the "all zeroes" early death check is only performed if can_die is
206 * true.
207 *
208 */
209static really_inline
210char LOOP_NOACCEL_FN(const IMPL_NFA_T *limex, const u8 *input, size_t *loc,
211 size_t length, STATE_T *s_ptr, struct CONTEXT_T *ctx,
212 u64a offset, const char flags, u64a *final_loc,
213 const char first_match, const char can_die) {
214 const ENG_STATE_T *reach = get_reach_table(limex);
215#if SIZE < 256
216 const STATE_T exceptionMask = LOAD_FROM_ENG(&limex->exceptionMask);
217#endif
218 const EXCEPTION_T *exceptions = getExceptionTable(EXCEPTION_T, limex);
219 STATE_T s = *s_ptr;
220
221 size_t i = *loc;
222 for (; i != length; i++) {
223 DUMP_INPUT(i);
224 if (can_die && ISZERO_STATE(s)) {
225 DEBUG_PRINTF("no states are switched on, early exit\n");
226 break;
227 }
228
229 STATE_T succ;
230 NFA_EXEC_GET_LIM_SUCC(limex, s, succ);
231
232 if (RUN_EXCEPTIONS_FN(limex, exceptions, s, EXCEPTION_MASK, i, offset,
233 &succ, final_loc, ctx, flags, 0, first_match)) {
234 return MO_HALT_MATCHING;
235 }
236
237 u8 c = input[i];
238 s = AND_STATE(succ, LOAD_FROM_ENG(&reach[limex->reachMap[c]]));
239 }
240
241 *loc = i;
242 *s_ptr = s;
243 return MO_CONTINUE_MATCHING;
244}
245
246static really_inline
247char STREAM_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
248 struct CONTEXT_T *ctx, u64a offset, const char flags,
249 u64a *final_loc, const char first_match) {
250 const ENG_STATE_T *reach = get_reach_table(limex);
251#if SIZE < 256
252 const STATE_T accelMask = LOAD_FROM_ENG(&limex->accel);
253 const STATE_T accel_and_friendsMask
254 = LOAD_FROM_ENG(&limex->accel_and_friends);
255 const STATE_T exceptionMask = LOAD_FROM_ENG(&limex->exceptionMask);
256#endif
257 const u8 *accelTable =
258 (const u8 *)((const char *)limex + limex->accelTableOffset);
259 const union AccelAux *accelAux =
260 (const union AccelAux *)((const char *)limex + limex->accelAuxOffset);
261 const EXCEPTION_T *exceptions = getExceptionTable(EXCEPTION_T, limex);
262 STATE_T s = ctx->s;
263
264 /* assert(ISALIGNED_16(exceptions)); */
265 /* assert(ISALIGNED_16(reach)); */
266
267 size_t i = 0;
268 size_t min_accel_offset = 0;
269 if (!limex->accelCount || length < ACCEL_MIN_LEN) {
270 min_accel_offset = length;
271 goto without_accel;
272 } else {
273 goto with_accel;
274 }
275
276without_accel:
277 if (limex->flags & LIMEX_FLAG_CANNOT_DIE) {
278 const char can_die = 0;
279 if (LOOP_NOACCEL_FN(limex, input, &i, min_accel_offset, &s, ctx, offset,
280 flags, final_loc, first_match,
281 can_die) == MO_HALT_MATCHING) {
282 return MO_HALT_MATCHING;
283 }
284 } else {
285 const char can_die = 1;
286 if (LOOP_NOACCEL_FN(limex, input, &i, min_accel_offset, &s, ctx, offset,
287 flags, final_loc, first_match,
288 can_die) == MO_HALT_MATCHING) {
289 return MO_HALT_MATCHING;
290 }
291 }
292
293with_accel:
294 for (; i != length; i++) {
295 DUMP_INPUT(i);
296 if (i + 16 <= length &&
297 ISZERO_STATE(ANDNOT_STATE(ACCEL_AND_FRIENDS_MASK, s))) {
298 DEBUG_PRINTF("current states are all accelerable\n");
299 assert(i + 16 <= length);
300 size_t post_idx =
301 RUN_ACCEL_FN(s, ACCEL_MASK, limex, accelTable, accelAux, input,
302 i, length);
303 if (post_idx != i) {
304 /* squashing any friends as they may no longer be valid;
305 * offset back off should ensure they weren't doing anything
306 * important */
307 s = AND_STATE(ACCEL_MASK, s);
308 }
309
310 if (i && post_idx < min_accel_offset + BAD_ACCEL_DIST) {
311 min_accel_offset = post_idx + BIG_ACCEL_PENALTY;
312 } else {
313 min_accel_offset = post_idx + SMALL_ACCEL_PENALTY;
314 }
315
316 if (min_accel_offset >= length - ACCEL_MIN_LEN) {
317 min_accel_offset = length;
318 }
319
320 DEBUG_PRINTF("advanced %zd, next accel chance in %zd/%zd\n",
321 post_idx - i, min_accel_offset - post_idx,
322 length - post_idx);
323
324 i = post_idx;
325 if (i == length) {
326 break; /* all chars eaten, break out of loop */
327 }
328 goto without_accel;
329 }
330
331 STATE_T succ;
332 NFA_EXEC_GET_LIM_SUCC(limex, s, succ);
333
334 if (RUN_EXCEPTIONS_FN(limex, exceptions, s, EXCEPTION_MASK, i, offset,
335 &succ, final_loc, ctx, flags, 0, first_match)) {
336 return MO_HALT_MATCHING;
337 }
338
339 u8 c = input[i];
340 s = AND_STATE(succ, LOAD_FROM_ENG(&reach[limex->reachMap[c]]));
341 }
342
343 ctx->s = s;
344
345 if ((first_match || (flags & CALLBACK_OUTPUT)) && limex->acceptCount) {
346 STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept);
347 const struct NFAAccept *acceptTable = getAcceptTable(limex);
348 STATE_T foundAccepts = AND_STATE(s, acceptMask);
349 if (unlikely(ISNONZERO_STATE(foundAccepts))) {
350 if (first_match) {
351 ctx->s = s;
352 assert(final_loc);
353 *final_loc = length;
354 return MO_HALT_MATCHING;
355 } else if (PROCESS_ACCEPTS_FN(limex, &ctx->s, &acceptMask,
356 acceptTable, offset + length,
357 ctx->callback, ctx->context)) {
358 return MO_HALT_MATCHING;
359 }
360 }
361 }
362 if (first_match) {
363 assert(final_loc);
364 *final_loc = length;
365 }
366 return MO_CONTINUE_MATCHING;
367}
368
369static never_inline
370char REV_STREAM_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
371 struct CONTEXT_T *ctx, u64a offset) {
372 const ENG_STATE_T *reach = get_reach_table(limex);
373#if SIZE < 256
374 const STATE_T exceptionMask = LOAD_FROM_ENG(&limex->exceptionMask);
375#endif
376 const EXCEPTION_T *exceptions = getExceptionTable(EXCEPTION_T, limex);
377 STATE_T s = ctx->s;
378
379 /* assert(ISALIGNED_16(exceptions)); */
380 /* assert(ISALIGNED_16(reach)); */
381 const char flags = CALLBACK_OUTPUT;
382 u64a *final_loc = NULL;
383
384 for (size_t i = length; i != 0; i--) {
385 DUMP_INPUT(i - 1);
386 if (ISZERO_STATE(s)) {
387 DEBUG_PRINTF("no states are switched on, early exit\n");
388 ctx->s = s;
389 return MO_CONTINUE_MATCHING;
390 }
391
392 STATE_T succ;
393 NFA_EXEC_GET_LIM_SUCC(limex, s, succ);
394
395 if (RUN_EXCEPTIONS_FN(limex, exceptions, s, EXCEPTION_MASK, i, offset,
396 &succ, final_loc, ctx, flags, 1, 0)) {
397 return MO_HALT_MATCHING;
398 }
399
400 u8 c = input[i - 1];
401 s = AND_STATE(succ, LOAD_FROM_ENG(&reach[limex->reachMap[c]]));
402 }
403
404 ctx->s = s;
405
406 STATE_T acceptMask = LOAD_FROM_ENG(&limex->accept);
407 const struct NFAAccept *acceptTable = getAcceptTable(limex);
408 const u32 acceptCount = limex->acceptCount;
409 assert(flags & CALLBACK_OUTPUT);
410 if (acceptCount) {
411 STATE_T foundAccepts = AND_STATE(s, acceptMask);
412 if (unlikely(ISNONZERO_STATE(foundAccepts))) {
413 if (PROCESS_ACCEPTS_NOSQUASH_FN(limex, &ctx->s, &acceptMask,
414 acceptTable, offset, ctx->callback,
415 ctx->context)) {
416 return MO_HALT_MATCHING;
417 }
418 }
419 }
420 return MO_CONTINUE_MATCHING;
421}
422
423static really_inline
424void COMPRESS_REPEATS_FN(const IMPL_NFA_T *limex, void *dest, void *src,
425 u64a offset) {
426 if (!limex->repeatCount) {
427 return;
428 }
429
430 STATE_T s = *(STATE_T *)src;
431
432 if (ISZERO_STATE(AND_STATE(LOAD_FROM_ENG(&limex->repeatCyclicMask), s))) {
433 DEBUG_PRINTF("no cyclics are on\n");
434 return;
435 }
436
437 const union RepeatControl *ctrl =
438 getRepeatControlBaseConst((const char *)src, sizeof(STATE_T));
439 char *state_base = (char *)dest + limex->stateSize;
440
441 for (u32 i = 0; i < limex->repeatCount; i++) {
442 DEBUG_PRINTF("repeat %u\n", i);
443 const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i);
444
445 const ENG_STATE_T *tug_mask =
446 (const ENG_STATE_T *)((const char *)info + info->tugMaskOffset);
447 /* repeat may still be inspected if its tug state is on */
448 if (!TESTBIT_STATE(s, info->cyclicState)
449 && ISZERO_STATE(AND_STATE(s, LOAD_FROM_ENG(tug_mask)))) {
450 DEBUG_PRINTF("is dead\n");
451 continue;
452 }
453
454 const struct RepeatInfo *repeat = getRepeatInfo(info);
455 DEBUG_PRINTF("packing state (packedCtrlOffset=%u)\n",
456 info->packedCtrlOffset);
457 repeatPack(state_base + info->packedCtrlOffset, repeat, &ctrl[i],
458 offset);
459 }
460
461 *(STATE_T *)src = s;
462}
463
464char JOIN(LIMEX_API_ROOT, _queueCompressState)(const struct NFA *n,
465 const struct mq *q, s64a loc) {
466 void *dest = q->streamState;
467 void *src = q->state;
468 u8 key = queue_prev_byte(q, loc);
469 const IMPL_NFA_T *limex = getImplNfa(n);
470 COMPRESS_REPEATS_FN(limex, dest, src, q->offset + loc);
471 COMPRESS_FN(limex, dest, src, key);
472 return 0;
473}
474
475static really_inline
476void EXPAND_REPEATS_FN(const IMPL_NFA_T *limex, void *dest, const void *src,
477 u64a offset) {
478 if (!limex->repeatCount) {
479 return;
480 }
481
482 // Note: state has already been expanded into 'dest'.
483 const STATE_T cyclics =
484 AND_STATE(*(STATE_T *)dest, LOAD_FROM_ENG(&limex->repeatCyclicMask));
485 if (ISZERO_STATE(cyclics)) {
486 DEBUG_PRINTF("no cyclics are on\n");
487 return;
488 }
489
490 union RepeatControl *ctrl =
491 getRepeatControlBase((char *)dest, sizeof(STATE_T));
492 const char *state_base = (const char *)src + limex->stateSize;
493
494 for (u32 i = 0; i < limex->repeatCount; i++) {
495 DEBUG_PRINTF("repeat %u\n", i);
496 const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i);
497 const ENG_STATE_T *tug_mask =
498 (const ENG_STATE_T *)((const char *)info + info->tugMaskOffset);
499
500 if (!TESTBIT_STATE(cyclics, info->cyclicState)
501 && ISZERO_STATE(AND_STATE(cyclics, LOAD_FROM_ENG(tug_mask)))) {
502 DEBUG_PRINTF("is dead\n");
503 continue;
504 }
505
506 DEBUG_PRINTF("unpacking state (packedCtrlOffset=%u)\n",
507 info->packedCtrlOffset);
508 const struct RepeatInfo *repeat = getRepeatInfo(info);
509 repeatUnpack(state_base + info->packedCtrlOffset, repeat, offset,
510 &ctrl[i]);
511 }
512}
513
514char JOIN(LIMEX_API_ROOT, _expandState)(const struct NFA *n, void *dest,
515 const void *src, u64a offset,
516 u8 key) {
517 const IMPL_NFA_T *limex = getImplNfa(n);
518 EXPAND_FN(limex, dest, src, key);
519 EXPAND_REPEATS_FN(limex, dest, src, offset);
520 return 0;
521}
522
523char JOIN(LIMEX_API_ROOT, _queueInitState)(const struct NFA *n, struct mq *q) {
524 *(STATE_T *)q->state = ZERO_STATE;
525
526 // Zero every bounded repeat control block in state.
527 const IMPL_NFA_T *limex = getImplNfa(n);
528 union RepeatControl *ctrl = getRepeatControlBase(q->state, sizeof(STATE_T));
529 for (u32 i = 0; i < limex->repeatCount; i++) {
530 memset(&ctrl[i], 0, sizeof(*ctrl));
531 }
532
533 return 0;
534}
535
536char JOIN(LIMEX_API_ROOT, _initCompressedState)(const struct NFA *n,
537 u64a offset, void *state,
538 u8 key) {
539 const IMPL_NFA_T *limex = getImplNfa(n);
540
541 STATE_T s = INITIAL_FN(limex, !!offset);
542 if (ISZERO_STATE(s)) {
543 DEBUG_PRINTF("state went to zero\n");
544 return 0;
545 }
546
547 // NFA is still active, compress its state and ship it out.
548 COMPRESS_FN(limex, state, &s, key);
549
550 // Zero every packed bounded repeat control block in stream state.
551 char *repeat_region = (char *)state + limex->stateSize;
552 for (u32 i = 0; i < limex->repeatCount; i++) {
553 const struct NFARepeatInfo *info = GET_NFA_REPEAT_INFO_FN(limex, i);
554 const struct RepeatInfo *repeat = getRepeatInfo(info);
555
556 memset(repeat_region + info->packedCtrlOffset, 0,
557 repeat->packedCtrlSize);
558 }
559
560 return 1;
561}
562
563// Helper for history buffer scans, which catch up the NFA state but don't emit
564// matches.
565static never_inline
566void STREAMSILENT_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
567 struct CONTEXT_T *ctx, u64a offset) {
568 const char first_match = 0;
569
570 UNUSED char rv = STREAM_FN(limex, input, length, ctx, offset, NO_OUTPUT,
571 NULL, first_match);
572 assert(rv != MO_HALT_MATCHING);
573}
574
575static never_inline
576char STREAMCB_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
577 struct CONTEXT_T *ctx, u64a offset) {
578 const char first_match = 0;
579 assert(ISALIGNED_CL(ctx));
580 return STREAM_FN(limex, input, length, ctx, offset, CALLBACK_OUTPUT, NULL,
581 first_match);
582}
583
584static never_inline
585char STREAMFIRST_FN(const IMPL_NFA_T *limex, const u8 *input, size_t length,
586 struct CONTEXT_T *ctx, u64a offset, u64a *final_loc) {
587 const char first_match = 1; // Run to first match and stop, no callbacks.
588 return STREAM_FN(limex, input, length, ctx, offset, NO_OUTPUT, final_loc,
589 first_match);
590}
591
592// Common code for handling the current event on the queue.
593static really_inline
594void JOIN(LIMEX_API_ROOT, _HandleEvent)(const IMPL_NFA_T *limex,
595 struct mq *q, struct CONTEXT_T *ctx,
596 u64a sp) {
597#define DEFINE_CASE(ee) \
598 case ee: \
599 DEBUG_PRINTF(#ee "\n");
600
601 u32 e = q->items[q->cur].type;
602 switch (e) {
603 DEFINE_CASE(MQE_TOP)
604 ctx->s = TOP_FN(limex, !!sp, ctx->s);
605 break;
606 DEFINE_CASE(MQE_START)
607 break;
608 DEFINE_CASE(MQE_END)
609 break;
610 default:
611 assert(e >= MQE_TOP_FIRST);
612 assert(e < MQE_INVALID);
613 DEBUG_PRINTF("MQE_TOP + %d\n", ((int)e - MQE_TOP_FIRST));
614 ctx->s = TOPN_FN(limex, ctx->s, e - MQE_TOP_FIRST);
615 }
616#undef DEFINE_CASE
617}
618
619// "Classic" queue call, used by outfixes
620char JOIN(LIMEX_API_ROOT, _Q)(const struct NFA *n, struct mq *q, s64a end) {
621 const IMPL_NFA_T *limex = getImplNfa(n);
622
623 if (q->report_current) {
624 char rv = REPORTCURRENT_FN(limex, q);
625
626 q->report_current = 0;
627
628 if (rv == MO_HALT_MATCHING) {
629 return MO_HALT_MATCHING;
630 }
631 }
632
633 if (q->cur == q->end) {
634 return 1;
635 }
636
637 assert(q->cur + 1 < q->end); /* require at least two items */
638
639 struct CONTEXT_T ctx;
640 ctx.repeat_ctrl = getRepeatControlBase(q->state, sizeof(STATE_T));
641 ctx.repeat_state = q->streamState + limex->stateSize;
642 ctx.callback = q->cb;
643 ctx.context = q->context;
644 ctx.cached_estate = ZERO_STATE;
645 ctx.cached_br = 0;
646
647 assert(q->items[q->cur].location >= 0);
648 DEBUG_PRINTF("LOAD STATE\n");
649 ctx.s = *(STATE_T *)q->state;
650 assert(q->items[q->cur].type == MQE_START);
651
652 u64a offset = q->offset;
653 u64a sp = offset + q->items[q->cur].location;
654 u64a end_abs = offset + end;
655 q->cur++;
656
657 while (q->cur < q->end && sp <= end_abs) {
658 u64a ep = offset + q->items[q->cur].location;
659 ep = MIN(ep, end_abs);
660 assert(ep >= sp);
661
662 assert(sp >= offset); // We no longer do history buffer scans here.
663
664 if (sp >= ep) {
665 goto scan_done;
666 }
667
668 /* do main buffer region */
669 DEBUG_PRINTF("MAIN BUFFER SCAN\n");
670 assert(ep - offset <= q->length);
671 if (STREAMCB_FN(limex, q->buffer + sp - offset, ep - sp, &ctx, sp)
672 == MO_HALT_MATCHING) {
673 *(STATE_T *)q->state = ZERO_STATE;
674 return 0;
675 }
676
677 DEBUG_PRINTF("SCAN DONE\n");
678 scan_done:
679 sp = ep;
680
681 if (sp != offset + q->items[q->cur].location) {
682 assert(q->cur);
683 DEBUG_PRINTF("bail: sp = %llu end_abs == %llu offset == %llu\n",
684 sp, end_abs, offset);
685 assert(sp == end_abs);
686 q->cur--;
687 q->items[q->cur].type = MQE_START;
688 q->items[q->cur].location = sp - offset;
689 DEBUG_PRINTF("bailing q->cur %u q->end %u\n", q->cur, q->end);
690 *(STATE_T *)q->state = ctx.s;
691 return MO_ALIVE;
692 }
693
694 JOIN(LIMEX_API_ROOT, _HandleEvent)(limex, q, &ctx, sp);
695
696 q->cur++;
697 }
698
699 EXPIRE_ESTATE_FN(limex, &ctx, sp);
700
701 DEBUG_PRINTF("END\n");
702 *(STATE_T *)q->state = ctx.s;
703
704 if (q->cur != q->end) {
705 q->cur--;
706 q->items[q->cur].type = MQE_START;
707 q->items[q->cur].location = sp - offset;
708 return MO_ALIVE;
709 }
710
711 return ISNONZERO_STATE(ctx.s);
712}
713
714/* used by suffix execution in Rose */
715char JOIN(LIMEX_API_ROOT, _Q2)(const struct NFA *n, struct mq *q, s64a end) {
716 const IMPL_NFA_T *limex = getImplNfa(n);
717
718 if (q->report_current) {
719 char rv = REPORTCURRENT_FN(limex, q);
720
721 q->report_current = 0;
722
723 if (rv == MO_HALT_MATCHING) {
724 return MO_HALT_MATCHING;
725 }
726 }
727
728 if (q->cur == q->end) {
729 return 1;
730 }
731
732 assert(q->cur + 1 < q->end); /* require at least two items */
733
734 struct CONTEXT_T ctx;
735 ctx.repeat_ctrl = getRepeatControlBase(q->state, sizeof(STATE_T));
736 ctx.repeat_state = q->streamState + limex->stateSize;
737 ctx.callback = q->cb;
738 ctx.context = q->context;
739 ctx.cached_estate = ZERO_STATE;
740 ctx.cached_br = 0;
741
742 DEBUG_PRINTF("LOAD STATE\n");
743 ctx.s = *(STATE_T *)q->state;
744 assert(q->items[q->cur].type == MQE_START);
745
746 u64a offset = q->offset;
747 u64a sp = offset + q->items[q->cur].location;
748 u64a end_abs = offset + end;
749 q->cur++;
750
751 while (q->cur < q->end && sp <= end_abs) {
752 u64a ep = offset + q->items[q->cur].location;
753 DEBUG_PRINTF("sp = %llu, ep = %llu, end_abs = %llu\n",
754 sp, ep, end_abs);
755 ep = MIN(ep, end_abs);
756 assert(ep >= sp);
757
758 if (sp < offset) {
759 DEBUG_PRINTF("HISTORY BUFFER SCAN\n");
760 assert(offset - sp <= q->hlength);
761 u64a local_ep = MIN(offset, ep);
762 u64a final_look = 0;
763 /* we are starting inside the history buffer */
764 if (STREAMFIRST_FN(limex, q->history + q->hlength + sp - offset,
765 local_ep - sp, &ctx, sp,
766 &final_look) == MO_HALT_MATCHING) {
767 DEBUG_PRINTF("final_look:%llu sp:%llu end_abs:%llu "
768 "offset:%llu\n", final_look, sp, end_abs, offset);
769 assert(q->cur);
770 q->cur--;
771 q->items[q->cur].type = MQE_START;
772 q->items[q->cur].location = sp + final_look - offset;
773 *(STATE_T *)q->state = ctx.s;
774 return MO_MATCHES_PENDING;
775 }
776
777 sp = local_ep;
778 }
779
780 if (sp >= ep) {
781 goto scan_done;
782 }
783
784 /* do main buffer region */
785 u64a final_look = 0;
786 assert(ep - offset <= q->length);
787 if (STREAMFIRST_FN(limex, q->buffer + sp - offset, ep - sp, &ctx, sp,
788 &final_look) == MO_HALT_MATCHING) {
789 DEBUG_PRINTF("final_look:%llu sp:%llu end_abs:%llu offset:%llu\n",
790 final_look, sp, end_abs, offset);
791 assert(q->cur);
792 q->cur--;
793 q->items[q->cur].type = MQE_START;
794 q->items[q->cur].location = sp + final_look - offset;
795 *(STATE_T *)q->state = ctx.s;
796 return MO_MATCHES_PENDING;
797 }
798
799 scan_done:
800 sp = ep;
801
802 if (sp != offset + q->items[q->cur].location) {
803 assert(q->cur);
804 DEBUG_PRINTF("bail: sp = %llu end_abs == %llu offset == %llu\n",
805 sp, end_abs, offset);
806 assert(sp == end_abs);
807 q->cur--;
808 q->items[q->cur].type = MQE_START;
809 q->items[q->cur].location = sp - offset;
810 DEBUG_PRINTF("bailing q->cur %u q->end %u\n", q->cur, q->end);
811 *(STATE_T *)q->state = ctx.s;
812 return MO_ALIVE;
813 }
814
815 JOIN(LIMEX_API_ROOT, _HandleEvent)(limex, q, &ctx, sp);
816
817 q->cur++;
818 }
819
820 EXPIRE_ESTATE_FN(limex, &ctx, sp);
821
822 DEBUG_PRINTF("END\n");
823 *(STATE_T *)q->state = ctx.s;
824
825 if (q->cur != q->end) {
826 q->cur--;
827 q->items[q->cur].type = MQE_START;
828 q->items[q->cur].location = sp - offset;
829 return MO_ALIVE;
830 }
831
832 return ISNONZERO_STATE(ctx.s);
833}
834
835// Used for execution Rose prefix/infixes.
836char JOIN(LIMEX_API_ROOT, _QR)(const struct NFA *n, struct mq *q,
837 ReportID report) {
838 const IMPL_NFA_T *limex = getImplNfa(n);
839
840 if (q->cur == q->end) {
841 return 1;
842 }
843
844 assert(q->cur + 1 < q->end); /* require at least two items */
845
846 struct CONTEXT_T ctx;
847 ctx.repeat_ctrl = getRepeatControlBase(q->state, sizeof(STATE_T));
848 ctx.repeat_state = q->streamState + limex->stateSize;
849 ctx.callback = NULL;
850 ctx.context = NULL;
851 ctx.cached_estate = ZERO_STATE;
852 ctx.cached_br = 0;
853
854 DEBUG_PRINTF("LOAD STATE\n");
855 ctx.s = *(STATE_T *)q->state;
856 assert(q->items[q->cur].type == MQE_START);
857
858 u64a offset = q->offset;
859 u64a sp = offset + q->items[q->cur].location;
860 q->cur++;
861
862 while (q->cur < q->end) {
863 u64a ep = offset + q->items[q->cur].location;
864 if (n->maxWidth) {
865 if (ep - sp > n->maxWidth) {
866 sp = ep - n->maxWidth;
867 ctx.s = INITIAL_FN(limex, !!sp);
868 }
869 }
870 assert(ep >= sp);
871
872 if (sp < offset) {
873 DEBUG_PRINTF("HISTORY BUFFER SCAN\n");
874 assert(offset - sp <= q->hlength);
875 u64a local_ep = MIN(offset, ep);
876 /* we are starting inside the history buffer */
877 STREAMSILENT_FN(limex, q->history + q->hlength + sp - offset,
878 local_ep - sp, &ctx, sp);
879
880 sp = local_ep;
881 }
882
883 if (sp >= ep) {
884 goto scan_done;
885 }
886
887 /* do main buffer region */
888 DEBUG_PRINTF("MAIN BUFFER SCAN\n");
889 assert(ep - offset <= q->length);
890 STREAMSILENT_FN(limex, q->buffer + sp - offset, ep - sp, &ctx, sp);
891
892 DEBUG_PRINTF("SCAN DONE\n");
893 scan_done:
894 sp = ep;
895
896 JOIN(LIMEX_API_ROOT, _HandleEvent)(limex, q, &ctx, sp);
897
898 q->cur++;
899 }
900
901 EXPIRE_ESTATE_FN(limex, &ctx, sp);
902
903 DEBUG_PRINTF("END, nfa is %s\n",
904 ISNONZERO_STATE(ctx.s) ? "still alive" : "dead");
905
906 *(STATE_T *)q->state = ctx.s;
907
908 if (JOIN(limexInAccept, SIZE)(limex, ctx.s, ctx.repeat_ctrl,
909 ctx.repeat_state, sp + 1, report)) {
910 return MO_MATCHES_PENDING;
911 }
912
913 return ISNONZERO_STATE(ctx.s);
914}
915
916char JOIN(LIMEX_API_ROOT, _testEOD)(const struct NFA *n, const char *state,
917 const char *streamState, u64a offset,
918 NfaCallback callback, void *context) {
919 assert(n && state);
920
921 const IMPL_NFA_T *limex = getImplNfa(n);
922 const STATE_T *sptr = (const STATE_T *)state;
923 const union RepeatControl *repeat_ctrl =
924 getRepeatControlBaseConst(state, sizeof(STATE_T));
925 const char *repeat_state = streamState + limex->stateSize;
926 return TESTEOD_FN(limex, sptr, repeat_ctrl, repeat_state, offset, callback,
927 context);
928}
929
930char JOIN(LIMEX_API_ROOT, _reportCurrent)(const struct NFA *n, struct mq *q) {
931 const IMPL_NFA_T *limex = getImplNfa(n);
932 REPORTCURRENT_FN(limex, q);
933 return 1;
934}
935
936// Block mode reverse scan.
937char JOIN(LIMEX_API_ROOT, _B_Reverse)(const struct NFA *n, u64a offset,
938 const u8 *buf, size_t buflen,
939 const u8 *hbuf, size_t hlen,
940 NfaCallback cb, void *context) {
941 assert(buf || hbuf);
942 assert(buflen || hlen);
943
944 struct CONTEXT_T ctx;
945 ctx.repeat_ctrl = NULL;
946 ctx.repeat_state = NULL;
947 ctx.callback = cb;
948 ctx.context = context;
949 ctx.cached_estate = ZERO_STATE;
950 ctx.cached_br = 0;
951
952 const IMPL_NFA_T *limex = getImplNfa(n);
953 ctx.s = INITIAL_FN(limex, 0); // always anchored
954
955 // 'buf' may be null, for example when we're scanning at EOD time.
956 if (buflen) {
957 assert(buf);
958 DEBUG_PRINTF("MAIN BUFFER SCAN, %zu bytes\n", buflen);
959 offset -= buflen;
960 REV_STREAM_FN(limex, buf, buflen, &ctx, offset);
961 }
962
963 if (hlen) {
964 assert(hbuf);
965 DEBUG_PRINTF("HISTORY BUFFER SCAN, %zu bytes\n", hlen);
966 offset -= hlen;
967 REV_STREAM_FN(limex, hbuf, hlen, &ctx, offset);
968 }
969
970 if (offset == 0 && limex->acceptEodCount && ISNONZERO_STATE(ctx.s)) {
971 const union RepeatControl *repeat_ctrl = NULL;
972 const char *repeat_state = NULL;
973 TESTEOD_FN(limex, &ctx.s, repeat_ctrl, repeat_state, offset, cb,
974 context);
975 }
976
977 // NOTE: return value is unused.
978 return 0;
979}
980
981char JOIN(LIMEX_API_ROOT, _inAccept)(const struct NFA *nfa,
982 ReportID report, struct mq *q) {
983 assert(nfa && q);
984 assert(q->state && q->streamState);
985
986 const IMPL_NFA_T *limex = getImplNfa(nfa);
987 union RepeatControl *repeat_ctrl =
988 getRepeatControlBase(q->state, sizeof(STATE_T));
989 char *repeat_state = q->streamState + limex->stateSize;
990 STATE_T state = *(STATE_T *)q->state;
991 u64a offset = q->offset + q_last_loc(q) + 1;
992
993 return JOIN(limexInAccept, SIZE)(limex, state, repeat_ctrl, repeat_state,
994 offset, report);
995}
996
997char JOIN(LIMEX_API_ROOT, _inAnyAccept)(const struct NFA *nfa, struct mq *q) {
998 assert(nfa && q);
999 assert(q->state && q->streamState);
1000
1001 const IMPL_NFA_T *limex = getImplNfa(nfa);
1002 union RepeatControl *repeat_ctrl =
1003 getRepeatControlBase(q->state, sizeof(STATE_T));
1004 char *repeat_state = q->streamState + limex->stateSize;
1005 STATE_T state = *(STATE_T *)q->state;
1006 u64a offset = q->offset + q_last_loc(q) + 1;
1007
1008 return JOIN(limexInAnyAccept, SIZE)(limex, state, repeat_ctrl, repeat_state,
1009 offset);
1010}
1011
1012enum nfa_zombie_status JOIN(LIMEX_API_ROOT, _zombie_status)(
1013 const struct NFA *nfa,
1014 struct mq *q,
1015 s64a loc) {
1016 assert(nfa->flags & NFA_ZOMBIE);
1017 const IMPL_NFA_T *limex = getImplNfa(nfa);
1018 STATE_T state = *(STATE_T *)q->state;
1019 STATE_T zmask = LOAD_FROM_ENG(&limex->zombieMask);
1020
1021 if (limex->repeatCount) {
1022 u64a offset = q->offset + loc + 1;
1023 union RepeatControl *repeat_ctrl =
1024 getRepeatControlBase(q->state, sizeof(STATE_T));
1025 char *repeat_state = q->streamState + limex->stateSize;
1026 SQUASH_UNTUG_BR_FN(limex, repeat_ctrl, repeat_state, offset, &state);
1027 }
1028
1029 if (ISNONZERO_STATE(AND_STATE(state, zmask))) {
1030 return NFA_ZOMBIE_ALWAYS_YES;
1031 }
1032
1033 return NFA_ZOMBIE_NO;
1034}
1035
1036#undef TESTEOD_FN
1037#undef INITIAL_FN
1038#undef TOP_FN
1039#undef TOPN_FN
1040#undef REPORTCURRENT_FN
1041#undef COMPRESS_FN
1042#undef EXPAND_FN
1043#undef COMPRESS_REPEATS_FN
1044#undef EXPAND_REPEATS_FN
1045#undef PROCESS_ACCEPTS_FN
1046#undef PROCESS_ACCEPTS_NOSQUASH_FN
1047#undef GET_NFA_REPEAT_INFO_FN
1048#undef RUN_ACCEL_FN
1049#undef RUN_EXCEPTIONS_FN
1050#undef REV_STREAM_FN
1051#undef LOOP_NOACCEL_FN
1052#undef STREAM_FN
1053#undef STREAMCB_FN
1054#undef STREAMFIRST_FN
1055#undef STREAMSILENT_FN
1056#undef CONTEXT_T
1057#undef EXCEPTION_T
1058#undef AND_STATE
1059#undef ANDNOT_STATE
1060#undef OR_STATE
1061#undef LSHIFT_STATE
1062#undef TESTBIT_STATE
1063#undef CLEARBIT_STATE
1064#undef ZERO_STATE
1065#undef ISNONZERO_STATE
1066#undef ISZERO_STATE
1067#undef NOTEQ_STATE
1068#undef DIFFRICH_STATE
1069#undef INLINE_ATTR_INT
1070#undef IMPL_NFA_T
1071#undef SQUASH_UNTUG_BR_FN
1072#undef ACCEL_MASK
1073#undef ACCEL_AND_FRIENDS_MASK
1074#undef EXCEPTION_MASK
1075#undef LIMEX_API_ROOT
1076