1/*
2 * Copyright (c) 2015-2016, 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 "gough.h"
30
31#include "accel.h"
32#include "gough_internal.h"
33#include "mcclellan.h"
34#include "nfa_api.h"
35#include "nfa_api_queue.h"
36#include "nfa_internal.h"
37#include "util/bitutils.h"
38#include "util/compare.h"
39#include "util/simd_utils.h"
40#include "util/unaligned.h"
41#include "ue2common.h"
42#include <string.h>
43
44#include "mcclellan_common_impl.h"
45
46#define GOUGH_SOM_EARLY (~0ULL)
47
48static really_inline
49void compressSomValue(u32 comp_slot_width, u64a curr_offset,
50 void *dest_som_base, u32 i, u64a val) {
51 void *dest_som = (u8 *)dest_som_base + i * comp_slot_width;
52 /* gough does not initialise all slots, so may contain garbage */
53 u64a delta = curr_offset - val;
54 switch (comp_slot_width) {
55 case 2:
56 if (delta >= (u16)~0U) {
57 delta = GOUGH_SOM_EARLY;
58 }
59 unaligned_store_u16(dest_som, delta);
60 break;
61 case 4:
62 if (delta >= (u32)~0U) {
63 delta = GOUGH_SOM_EARLY;
64 }
65 unaligned_store_u32(dest_som, delta);
66 break;
67 case 8:
68 if (delta >= ~0ULL) {
69 delta = GOUGH_SOM_EARLY;
70 }
71 unaligned_store_u64a(dest_som, delta);
72 break;
73 default:
74 assert(0);
75 }
76}
77
78static really_inline
79u64a expandSomValue(u32 comp_slot_width, u64a curr_offset,
80 const void *src_som_base, u32 i) {
81 /* Note: gough does not initialise all slots, so we may end up decompressing
82 * garbage */
83
84 const void *src_som = (const u8 *)src_som_base + i * comp_slot_width;
85 u64a val = 0;
86 switch (comp_slot_width) {
87 case 2:
88 val = unaligned_load_u16(src_som);
89 if (val == (u16)~0U) {
90 return GOUGH_SOM_EARLY;
91 }
92 break;
93 case 4:
94 val = unaligned_load_u32(src_som);
95 if (val == (u32)~0U) {
96 return GOUGH_SOM_EARLY;
97 }
98 break;
99 case 8:
100 val = unaligned_load_u64a(src_som);
101 if (val == ~0ULL) {
102 return GOUGH_SOM_EARLY;
103 }
104 break;
105
106 default:
107 assert(0);
108 }
109 return curr_offset - val;
110}
111
112static really_inline
113char doReports(NfaCallback cb, void *ctxt, const struct mcclellan *m,
114 const struct gough_som_info *som, u16 s, u64a loc,
115 char eod, u16 * const cached_accept_state,
116 u32 * const cached_accept_id, u32 * const cached_accept_som) {
117 DEBUG_PRINTF("reporting state = %hu, loc=%llu, eod %hhu\n",
118 (u16)(s & STATE_MASK), loc, eod);
119
120 if (!eod && s == *cached_accept_state) {
121 u64a from = *cached_accept_som == INVALID_SLOT ? loc
122 : som->slots[*cached_accept_som];
123 if (cb(from, loc, *cached_accept_id, ctxt) == MO_HALT_MATCHING) {
124 return MO_HALT_MATCHING; /* termination requested */
125 }
126
127 return MO_CONTINUE_MATCHING; /* continue execution */
128 }
129
130 const struct mstate_aux *aux = get_aux(m, s);
131 size_t offset = eod ? aux->accept_eod : aux->accept;
132
133 assert(offset);
134 const struct gough_report_list *rl
135 = (const void *)((const char *)m + offset - sizeof(struct NFA));
136 assert(ISALIGNED(rl));
137
138 DEBUG_PRINTF("report list size %u\n", rl->count);
139 u32 count = rl->count;
140
141 if (!eod && count == 1) {
142 *cached_accept_state = s;
143 *cached_accept_id = rl->report[0].r;
144 *cached_accept_som = rl->report[0].som;
145
146 u64a from = *cached_accept_som == INVALID_SLOT ? loc
147 : som->slots[*cached_accept_som];
148 DEBUG_PRINTF("reporting %u, using som[%u]=%llu\n", rl->report[0].r,
149 *cached_accept_som, from);
150 if (cb(from, loc, *cached_accept_id, ctxt) == MO_HALT_MATCHING) {
151 return MO_HALT_MATCHING; /* termination requested */
152 }
153
154 return MO_CONTINUE_MATCHING; /* continue execution */
155 }
156
157 for (u32 i = 0; i < count; i++) {
158 u32 slot = rl->report[i].som;
159 u64a from = slot == INVALID_SLOT ? loc : som->slots[slot];
160 DEBUG_PRINTF("reporting %u, using som[%u] = %llu\n",
161 rl->report[i].r, slot, from);
162 if (cb(from, loc, rl->report[i].r, ctxt) == MO_HALT_MATCHING) {
163 return MO_HALT_MATCHING; /* termination requested */
164 }
165 }
166
167 return MO_CONTINUE_MATCHING; /* continue execution */
168}
169
170#ifdef DUMP_SUPPORT
171static UNUSED
172const char *dump_op(u8 op) {
173 switch (op) {
174 case GOUGH_INS_END:
175 return "END";
176 case GOUGH_INS_MOV:
177 return "MOV";
178 case GOUGH_INS_NEW:
179 return "NEW";
180 case GOUGH_INS_MIN:
181 return "MIN";
182 default:
183 return "???";
184 }
185}
186#endif
187
188static really_inline
189void run_prog_i(UNUSED const struct NFA *nfa,
190 const struct gough_ins *pc, u64a som_offset,
191 struct gough_som_info *som) {
192 DEBUG_PRINTF("run prog at som_offset of %llu\n", som_offset);
193 while (1) {
194 assert((const u8 *)pc >= (const u8 *)nfa);
195 assert((const u8 *)pc < (const u8 *)nfa + nfa->length);
196 u32 dest = pc->dest;
197 u32 src = pc->src;
198 assert(pc->op == GOUGH_INS_END
199 || dest < (nfa->scratchStateSize - 16) / 8);
200 DEBUG_PRINTF("%s %u %u\n", dump_op(pc->op), dest, src);
201 switch (pc->op) {
202 case GOUGH_INS_END:
203 return;
204 case GOUGH_INS_MOV:
205 som->slots[dest] = som->slots[src];
206 break;
207 case GOUGH_INS_NEW:
208 /* note: c has already been advanced */
209 DEBUG_PRINTF("current offset %llu; adjust %u\n", som_offset,
210 pc->src);
211 assert(som_offset >= pc->src);
212 som->slots[dest] = som_offset - pc->src;
213 break;
214 case GOUGH_INS_MIN:
215 /* TODO: shift all values along by one so that a normal min works
216 */
217 if (som->slots[src] == GOUGH_SOM_EARLY) {
218 som->slots[dest] = som->slots[src];
219 } else if (som->slots[dest] != GOUGH_SOM_EARLY) {
220 LIMIT_TO_AT_MOST(&som->slots[dest], som->slots[src]);
221 }
222 break;
223 default:
224 assert(0);
225 return;
226 }
227 DEBUG_PRINTF("dest slot[%u] = %llu\n", dest, som->slots[dest]);
228 ++pc;
229 }
230}
231
232static really_inline
233void run_prog(const struct NFA *nfa, const u32 *edge_prog_table,
234 const u8 *buf, u64a offAdj, const u8 *c, u32 edge_num,
235 struct gough_som_info *som) {
236 DEBUG_PRINTF("taking edge %u\n", edge_num);
237 u32 prog_offset = edge_prog_table[edge_num];
238 if (!prog_offset) {
239 DEBUG_PRINTF("no prog on edge\n");
240 return;
241 }
242
243 const struct gough_ins *pc = (const void *)((const u8 *)nfa + prog_offset);
244 u64a curr_offset = (u64a)(c - buf) + offAdj - 1;
245 run_prog_i(nfa, pc, curr_offset, som);
246}
247
248static never_inline
249void run_accel_prog(const struct NFA *nfa, const struct gough_accel *gacc,
250 const u8 *buf, u64a offAdj, const u8 *c, const u8 *c2,
251 struct gough_som_info *som) {
252 assert(gacc->prog_offset);
253 assert(c2 > c);
254
255 const struct gough_ins *pc
256 = (const void *)((const u8 *)nfa + gacc->prog_offset);
257 s64a margin_dist = gacc->margin_dist;
258
259 DEBUG_PRINTF("run accel after skip %lld margin; advanced %zd\n",
260 margin_dist, c2 - c);
261
262 if (c2 - c <= 2 * margin_dist) {
263 while (c < c2) {
264 u64a curr_offset = (u64a)(c - buf) + offAdj;
265 run_prog_i(nfa, pc, curr_offset, som);
266 c++;
267 }
268 } else {
269 u64a curr_offset = (u64a)(c - buf) + offAdj;
270 for (s64a i = 0; i < margin_dist; i++) {
271 run_prog_i(nfa, pc, curr_offset + i, som);
272 }
273
274 curr_offset = (u64a)(c2 - buf) + offAdj - margin_dist;
275 for (s64a i = 0; i < margin_dist; i++) {
276 run_prog_i(nfa, pc, curr_offset + i, som);
277 }
278 }
279}
280
281static never_inline
282u16 goughEnableStarts(const struct mcclellan *m, u16 s, u64a som_offset,
283 struct gough_som_info *som) {
284 DEBUG_PRINTF("top triggered while at %hu\n", s);
285 const struct mstate_aux *aux = get_aux(m, s);
286 DEBUG_PRINTF("now going to state %hu\n", aux->top);
287
288 const u32 *top_offsets = get_gough_top_offsets(m);
289 if (!top_offsets) {
290 return aux->top;
291 }
292
293 u32 prog_offset = top_offsets[s];
294 if (!prog_offset) {
295 return aux->top;
296 }
297
298 DEBUG_PRINTF("doing som for top\n");
299 const struct NFA *nfa
300 = (const struct NFA *)((const char *)m - sizeof(struct NFA));
301 const struct gough_ins *pc = (const void *)((const u8 *)nfa
302 + prog_offset);
303 run_prog_i(nfa, pc, som_offset, som);
304 return aux->top;
305}
306
307static really_inline
308char goughExec16_i(const struct mcclellan *m, struct gough_som_info *som,
309 u16 *state, const u8 *buf, size_t len, u64a offAdj,
310 NfaCallback cb, void *ctxt, const u8 **c_final,
311 enum MatchMode mode) {
312 assert(ISALIGNED_N(state, 2));
313
314 u16 s = *state;
315 const struct NFA *nfa
316 = (const struct NFA *)((const char *)m - sizeof(struct NFA));
317 const u8 *c = buf, *c_end = buf + len;
318 const u16 *succ_table = (const u16 *)((const char *)m
319 + sizeof(struct mcclellan));
320 assert(ISALIGNED_N(succ_table, 2));
321 const u16 sherman_base = m->sherman_limit;
322 const char *sherman_base_offset
323 = (const char *)nfa + m->sherman_offset;
324 const u32 as = m->alphaShift;
325
326 s &= STATE_MASK;
327
328 u32 cached_accept_id = 0;
329 u16 cached_accept_state = 0;
330 u32 cached_accept_som = 0;
331
332 const u32 *edge_prog_table = (const u32 *)(get_gough(m) + 1);
333
334 DEBUG_PRINTF("s: %hu, len %zu\n", s, len);
335
336 const u8 *min_accel_offset = c;
337 if (!m->has_accel || len < ACCEL_MIN_LEN) {
338 min_accel_offset = c_end;
339 goto without_accel;
340 }
341
342 goto with_accel;
343
344without_accel:
345 while (c < min_accel_offset && s) {
346 u8 cprime = m->remap[*(c++)];
347 DEBUG_PRINTF("c: %02hhx cp:%02hhx (s=%hu)\n", *(c-1), cprime, s);
348
349 u32 edge_num = ((u32)s << as) + cprime;
350 run_prog(nfa, edge_prog_table, buf, offAdj, c, edge_num, som);
351 if (s < sherman_base) {
352 DEBUG_PRINTF("doing normal\n");
353 assert(s < m->state_count);
354 s = succ_table[edge_num];
355 } else {
356 const char *sherman_state
357 = findShermanState(m, sherman_base_offset, sherman_base, s);
358 DEBUG_PRINTF("doing sherman\n");
359 s = doSherman16(sherman_state, cprime, succ_table, as);
360 }
361 DEBUG_PRINTF("s: %hu (%hu)\n", s, (u16)(s & STATE_MASK));
362
363 if (mode != NO_MATCHES && (s & ACCEPT_FLAG)) {
364 if (mode == STOP_AT_MATCH) {
365 *state = s & STATE_MASK;
366 *c_final = c - 1;
367 return MO_CONTINUE_MATCHING;
368 }
369
370 u64a loc = (c - 1) - buf + offAdj + 1;
371 if (doReports(cb, ctxt, m, som, s & STATE_MASK, loc, 0,
372 &cached_accept_state, &cached_accept_id,
373 &cached_accept_som) == MO_HALT_MATCHING) {
374 return MO_HALT_MATCHING;
375 }
376 }
377
378 s &= STATE_MASK;
379 }
380
381with_accel:
382 while (c < c_end && s) {
383 u8 cprime = m->remap[*(c++)];
384 DEBUG_PRINTF("c: %02hhx cp:%02hhx (s=%hu)\n", *(c-1), cprime, s);
385
386 u32 edge_num = ((u32)s << as) + cprime;
387 run_prog(nfa, edge_prog_table, buf, offAdj, c, edge_num, som);
388 if (s < sherman_base) {
389 DEBUG_PRINTF("doing normal\n");
390 assert(s < m->state_count);
391 s = succ_table[edge_num];
392 } else {
393 const char *sherman_state
394 = findShermanState(m, sherman_base_offset, sherman_base, s);
395 DEBUG_PRINTF("doing sherman\n");
396 s = doSherman16(sherman_state, cprime, succ_table, as);
397 }
398 DEBUG_PRINTF("s: %hu (%hu)\n", s, (u16)(s & STATE_MASK));
399
400 if (mode != NO_MATCHES && (s & ACCEPT_FLAG)) {
401 if (mode == STOP_AT_MATCH) {
402 *state = s & STATE_MASK;
403 *c_final = c - 1;
404 return MO_CONTINUE_MATCHING;
405 }
406
407 u64a loc = (c - 1) - buf + offAdj + 1;
408
409 if (doReports(cb, ctxt, m, som, s & STATE_MASK, loc, 0,
410 &cached_accept_state, &cached_accept_id,
411 &cached_accept_som)
412 == MO_HALT_MATCHING) {
413 return MO_HALT_MATCHING;
414 }
415 } else if (s & ACCEL_FLAG) {
416 DEBUG_PRINTF("skipping\n");
417 const struct mstate_aux *this_aux = get_aux(m, s & STATE_MASK);
418 u32 accel_offset = this_aux->accel_offset;
419
420 assert(accel_offset >= m->aux_offset);
421 assert(accel_offset < m->sherman_offset);
422
423 const struct gough_accel *gacc
424 = (const void *)((const char *)m + accel_offset);
425 assert(!gacc->prog_offset == !gacc->margin_dist);
426 const u8 *c2 = run_accel(&gacc->accel, c, c_end);
427
428 if (c2 != c && gacc->prog_offset) {
429 run_accel_prog(nfa, gacc, buf, offAdj, c, c2, som);
430 }
431
432 if (c2 < min_accel_offset + BAD_ACCEL_DIST) {
433 min_accel_offset = c2 + BIG_ACCEL_PENALTY;
434 } else {
435 min_accel_offset = c2 + SMALL_ACCEL_PENALTY;
436 }
437
438 if (min_accel_offset >= c_end - ACCEL_MIN_LEN) {
439 min_accel_offset = c_end;
440 }
441
442 DEBUG_PRINTF("advanced %zd, next accel chance in %zd/%zd\n",
443 c2 - c, min_accel_offset - c2, c_end - c2);
444
445 c = c2;
446 s &= STATE_MASK;
447 goto without_accel;
448 }
449
450 s &= STATE_MASK;
451 }
452
453 if (mode == STOP_AT_MATCH) {
454 *c_final = c_end;
455 }
456 *state = s;
457
458 return MO_CONTINUE_MATCHING;
459}
460
461static really_inline
462char goughExec8_i(const struct mcclellan *m, struct gough_som_info *som,
463 u8 *state, const u8 *buf, size_t len, u64a offAdj,
464 NfaCallback cb, void *ctxt, const u8 **c_final,
465 enum MatchMode mode) {
466 u8 s = *state;
467 const u8 *c = buf, *c_end = buf + len;
468 const u8 *succ_table = (const u8 *)((const char *)m
469 + sizeof(struct mcclellan));
470 const u32 as = m->alphaShift;
471 const struct mstate_aux *aux;
472
473 const struct NFA *nfa
474 = (const struct NFA *)((const char *)m - sizeof(struct NFA));
475 aux = (const struct mstate_aux *)((const char *)nfa + m->aux_offset);
476
477 const u32 *edge_prog_table = (const u32 *)(get_gough(m) + 1);
478
479 u16 accel_limit = m->accel_limit_8;
480 u16 accept_limit = m->accept_limit_8;
481
482 u32 cached_accept_id = 0;
483 u16 cached_accept_state = 0;
484 u32 cached_accept_som = 0;
485
486 DEBUG_PRINTF("accel %hu, accept %hu\n", accel_limit, accept_limit);
487
488 DEBUG_PRINTF("s: %hhu, len %zu\n", s, len);
489
490 const u8 *min_accel_offset = c;
491 if (!m->has_accel || len < ACCEL_MIN_LEN) {
492 min_accel_offset = c_end;
493 goto without_accel;
494 }
495
496 goto with_accel;
497
498without_accel:
499 while (c < min_accel_offset && s) {
500 u8 cprime = m->remap[*(c++)];
501 DEBUG_PRINTF("c: %02hhx '%c' cp:%02hhx\n", *(c-1),
502 ourisprint(*(c-1)) ? *(c-1) : '?', cprime);
503
504 u32 edge_num = ((u32)s << as) + cprime;
505
506 run_prog(nfa, edge_prog_table, buf, offAdj, c, edge_num, som);
507
508 s = succ_table[edge_num];
509 DEBUG_PRINTF("s: %hhu\n", s);
510
511 if (mode != NO_MATCHES && s >= accept_limit) {
512 if (mode == STOP_AT_MATCH) {
513 DEBUG_PRINTF("match - pausing\n");
514 *state = s;
515 *c_final = c - 1;
516 return MO_CONTINUE_MATCHING;
517 }
518
519 u64a loc = (c - 1) - buf + offAdj + 1;
520 if (doReports(cb, ctxt, m, som, s, loc, 0,
521 &cached_accept_state, &cached_accept_id,
522 &cached_accept_som)
523 == MO_HALT_MATCHING) {
524 return MO_HALT_MATCHING;
525 }
526 }
527 }
528
529with_accel:
530 while (c < c_end && s) {
531 u8 cprime = m->remap[*(c++)];
532 DEBUG_PRINTF("c: %02hhx '%c' cp:%02hhx\n", *(c-1),
533 ourisprint(*(c-1)) ? *(c-1) : '?', cprime);
534
535 u32 edge_num = ((u32)s << as) + cprime;
536
537 run_prog(nfa, edge_prog_table, buf, offAdj, c, edge_num, som);
538
539 s = succ_table[edge_num];
540 DEBUG_PRINTF("s: %hhu\n", s);
541
542 if (s >= accel_limit) { /* accept_limit >= accel_limit */
543 if (mode != NO_MATCHES && s >= accept_limit) {
544 if (mode == STOP_AT_MATCH) {
545 DEBUG_PRINTF("match - pausing\n");
546 *state = s;
547 *c_final = c - 1;
548 return MO_CONTINUE_MATCHING;
549 }
550
551 u64a loc = (c - 1) - buf + offAdj + 1;
552 if (doReports(cb, ctxt, m, som, s, loc, 0,
553 &cached_accept_state, &cached_accept_id,
554 &cached_accept_som)
555 == MO_HALT_MATCHING) {
556 return MO_HALT_MATCHING;
557 }
558 } else if (aux[s].accel_offset) {
559 DEBUG_PRINTF("skipping\n");
560
561 const struct gough_accel *gacc
562 = (const void *)((const char *)m + aux[s].accel_offset);
563 const u8 *c2 = run_accel(&gacc->accel, c, c_end);
564
565 if (c2 != c && gacc->prog_offset) {
566 run_accel_prog(nfa, gacc, buf, offAdj, c, c2, som);
567 }
568
569 if (c2 < min_accel_offset + BAD_ACCEL_DIST) {
570 min_accel_offset = c2 + BIG_ACCEL_PENALTY;
571 } else {
572 min_accel_offset = c2 + SMALL_ACCEL_PENALTY;
573 }
574
575 if (min_accel_offset >= c_end - ACCEL_MIN_LEN) {
576 min_accel_offset = c_end;
577 }
578
579 DEBUG_PRINTF("advanced %zd, next accel chance in %zd/%zd\n",
580 c2 - c, min_accel_offset - c2, c_end - c2);
581
582 c = c2;
583 goto without_accel;
584 }
585 }
586 }
587
588 *state = s;
589 if (mode == STOP_AT_MATCH) {
590 *c_final = c_end;
591 }
592 return MO_CONTINUE_MATCHING;
593}
594
595static never_inline
596char goughExec8_i_ni(const struct mcclellan *m, struct gough_som_info *som,
597 u8 *state, const u8 *buf, size_t len, u64a offAdj,
598 NfaCallback cb, void *ctxt, const u8 **final_point,
599 enum MatchMode mode) {
600 return goughExec8_i(m, som, state, buf, len, offAdj, cb, ctxt, final_point,
601 mode);
602}
603
604static never_inline
605char goughExec16_i_ni(const struct mcclellan *m, struct gough_som_info *som,
606 u16 *state, const u8 *buf, size_t len, u64a offAdj,
607 NfaCallback cb, void *ctxt, const u8 **final_point,
608 enum MatchMode mode) {
609 return goughExec16_i(m, som, state, buf, len, offAdj, cb, ctxt, final_point,
610 mode);
611}
612
613static really_inline
614struct gough_som_info *getSomInfo(char *state_base) {
615 return (struct gough_som_info *)(state_base + 16);
616}
617
618static really_inline
619const struct gough_som_info *getSomInfoConst(const char *state_base) {
620 return (const struct gough_som_info *)(state_base + 16);
621}
622
623static really_inline
624char nfaExecGough8_Q2i(const struct NFA *n, u64a offset, const u8 *buffer,
625 const u8 *hend, NfaCallback cb, void *context,
626 struct mq *q, s64a end, enum MatchMode mode) {
627 DEBUG_PRINTF("enter\n");
628 struct gough_som_info *som = getSomInfo(q->state);
629 assert(n->type == GOUGH_NFA_8);
630 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(n);
631 s64a sp;
632 u8 s = *(u8 *)q->state;
633
634 if (q->report_current) {
635 assert(s);
636 assert(s >= m->accept_limit_8);
637
638 u32 cached_accept_id = 0;
639 u16 cached_accept_state = 0;
640 u32 cached_accept_som = 0;
641
642 int rv = doReports(cb, context, m, som, s, q_cur_offset(q), 0,
643 &cached_accept_state, &cached_accept_id,
644 &cached_accept_som);
645
646 q->report_current = 0;
647
648 if (rv == MO_HALT_MATCHING) {
649 return MO_HALT_MATCHING;
650 }
651 }
652
653 sp = q_cur_loc(q);
654 q->cur++;
655
656 const u8 *cur_buf = sp < 0 ? hend : buffer;
657
658 if (mode != NO_MATCHES && q->items[q->cur - 1].location > end) {
659 /* this is as far as we go */
660 q->cur--;
661 q->items[q->cur].type = MQE_START;
662 q->items[q->cur].location = end;
663 *(u8 *)q->state = s;
664 return MO_ALIVE;
665 }
666
667 while (1) {
668 DEBUG_PRINTF("%s @ %llu [som %llu]\n",
669 q->items[q->cur].type == MQE_TOP ? "TOP" :
670 q->items[q->cur].type == MQE_END ? "END" : "???",
671 q->items[q->cur].location + offset, q->items[q->cur].som);
672 assert(q->cur < q->end);
673 s64a ep = q->items[q->cur].location;
674 if (mode != NO_MATCHES) {
675 ep = MIN(ep, end);
676 }
677
678 assert(ep >= sp);
679 DEBUG_PRINTF("run to %lld from %lld\n", ep, sp);
680
681 s64a local_ep = ep;
682 if (sp < 0) {
683 local_ep = MIN(0, ep);
684 }
685
686 const u8 *final_look;
687 if (goughExec8_i_ni(m, som, &s, cur_buf + sp, local_ep - sp,
688 offset + sp, cb, context, &final_look, mode)
689 == MO_HALT_MATCHING) {
690 *(u8 *)q->state = 0;
691 return 0;
692 }
693 if (mode == STOP_AT_MATCH && final_look != cur_buf + local_ep) {
694 /* found a match */
695 DEBUG_PRINTF("found a match\n");
696 assert(q->cur);
697 q->cur--;
698 q->items[q->cur].type = MQE_START;
699 q->items[q->cur].location = final_look - cur_buf + 1; /* due to
700 * early -1 */
701 *(u8 *)q->state = s;
702 return MO_MATCHES_PENDING;
703 }
704
705 assert(q->cur);
706 if (mode != NO_MATCHES && q->items[q->cur].location > end) {
707 /* this is as far as we go */
708 assert(q->cur);
709 q->cur--;
710 q->items[q->cur].type = MQE_START;
711 q->items[q->cur].location = end;
712 *(u8 *)q->state = s;
713 return MO_ALIVE;
714 }
715
716 sp = local_ep;
717
718 if (sp == 0) {
719 cur_buf = buffer;
720 }
721
722 if (sp != ep) {
723 continue;
724 }
725
726 switch (q->items[q->cur].type) {
727 case MQE_TOP:
728 assert(!s || sp + offset > 0);
729 if (sp + offset == 0) {
730 s = (u8)m->start_anchored;
731 break;
732 }
733 s = goughEnableStarts(m, s, q->items[q->cur].som, som);
734 break;
735 case MQE_END:
736 *(u8 *)q->state = s;
737 q->cur++;
738 return s ? MO_ALIVE : 0;
739 default:
740 assert(!"invalid queue event");
741 }
742
743 q->cur++;
744 }
745}
746
747
748static really_inline
749char nfaExecGough16_Q2i(const struct NFA *n, u64a offset, const u8 *buffer,
750 const u8 *hend, NfaCallback cb, void *context,
751 struct mq *q, s64a end, enum MatchMode mode) {
752 struct gough_som_info *som = getSomInfo(q->state);
753 assert(n->type == GOUGH_NFA_16);
754 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(n);
755 s64a sp;
756
757 assert(ISALIGNED_N(q->state, 2));
758 u16 s = *(u16 *)q->state;
759
760 if (q->report_current) {
761 assert(s);
762 assert(get_aux(m, s)->accept);
763
764 u32 cached_accept_id = 0;
765 u16 cached_accept_state = 0;
766 u32 cached_accept_som = 0;
767
768 int rv = doReports(cb, context, m, som, s, q_cur_offset(q), 0,
769 &cached_accept_state, &cached_accept_id,
770 &cached_accept_som);
771
772 q->report_current = 0;
773
774 if (rv == MO_HALT_MATCHING) {
775 return MO_HALT_MATCHING;
776 }
777 }
778
779 sp = q_cur_loc(q);
780 q->cur++;
781
782 const u8 *cur_buf = sp < 0 ? hend : buffer;
783
784 assert(q->cur);
785 if (mode != NO_MATCHES && q->items[q->cur - 1].location > end) {
786 /* this is as far as we go */
787 q->cur--;
788 q->items[q->cur].type = MQE_START;
789 q->items[q->cur].location = end;
790 *(u16 *)q->state = s;
791 return MO_ALIVE;
792 }
793
794 while (1) {
795 assert(q->cur < q->end);
796 s64a ep = q->items[q->cur].location;
797 if (mode != NO_MATCHES) {
798 ep = MIN(ep, end);
799 }
800
801 assert(ep >= sp);
802
803 s64a local_ep = ep;
804 if (sp < 0) {
805 local_ep = MIN(0, ep);
806 }
807
808 /* do main buffer region */
809 const u8 *final_look;
810 if (goughExec16_i_ni(m, som, &s, cur_buf + sp, local_ep - sp,
811 offset + sp, cb, context, &final_look, mode)
812 == MO_HALT_MATCHING) {
813 *(u16 *)q->state = 0;
814 return 0;
815 }
816 if (mode == STOP_AT_MATCH && final_look != cur_buf + local_ep) {
817 /* this is as far as we go */
818 assert(q->cur);
819 DEBUG_PRINTF("state %hu final_look %zd\n", s,
820 final_look - cur_buf);
821 q->cur--;
822 q->items[q->cur].type = MQE_START;
823 q->items[q->cur].location = final_look - cur_buf + 1; /* due to
824 * early -1 */
825 *(u16 *)q->state = s;
826 return MO_MATCHES_PENDING;
827 }
828
829 assert(q->cur);
830 if (mode != NO_MATCHES && q->items[q->cur].location > end) {
831 /* this is as far as we go */
832 q->cur--;
833 q->items[q->cur].type = MQE_START;
834 q->items[q->cur].location = end;
835 *(u16 *)q->state = s;
836 return MO_ALIVE;
837 }
838
839 sp = local_ep;
840
841 if (sp == 0) {
842 cur_buf = buffer;
843 }
844
845 if (sp != ep) {
846 continue;
847 }
848
849 switch (q->items[q->cur].type) {
850 case MQE_TOP:
851 assert(!s || sp + offset > 0);
852 if (sp + offset == 0) {
853 s = m->start_anchored;
854 break;
855 }
856 s = goughEnableStarts(m, s, q->items[q->cur].som, som);
857 break;
858 case MQE_END:
859 *(u16 *)q->state = s;
860 q->cur++;
861 return s ? MO_ALIVE : 0;
862 default:
863 assert(!"invalid queue event");
864 }
865
866 q->cur++;
867 }
868}
869
870char nfaExecGough8_Q(const struct NFA *n, struct mq *q, s64a end) {
871 u64a offset = q->offset;
872 const u8 *buffer = q->buffer;
873 NfaCallback cb = q->cb;
874 void *context = q->context;
875 assert(n->type == GOUGH_NFA_8);
876 const u8 *hend = q->history + q->hlength;
877
878 return nfaExecGough8_Q2i(n, offset, buffer, hend, cb, context, q, end,
879 CALLBACK_OUTPUT);
880}
881
882char nfaExecGough16_Q(const struct NFA *n, struct mq *q, s64a end) {
883 u64a offset = q->offset;
884 const u8 *buffer = q->buffer;
885 NfaCallback cb = q->cb;
886 void *context = q->context;
887 assert(n->type == GOUGH_NFA_16);
888 const u8 *hend = q->history + q->hlength;
889
890 return nfaExecGough16_Q2i(n, offset, buffer, hend, cb, context, q, end,
891 CALLBACK_OUTPUT);
892}
893
894char nfaExecGough8_Q2(const struct NFA *n, struct mq *q, s64a end) {
895 u64a offset = q->offset;
896 const u8 *buffer = q->buffer;
897 NfaCallback cb = q->cb;
898 void *context = q->context;
899 assert(n->type == GOUGH_NFA_8);
900 const u8 *hend = q->history + q->hlength;
901
902 return nfaExecGough8_Q2i(n, offset, buffer, hend, cb, context, q, end,
903 STOP_AT_MATCH);
904}
905
906char nfaExecGough16_Q2(const struct NFA *n, struct mq *q, s64a end) {
907 u64a offset = q->offset;
908 const u8 *buffer = q->buffer;
909 NfaCallback cb = q->cb;
910 void *context = q->context;
911 assert(n->type == GOUGH_NFA_16);
912 const u8 *hend = q->history + q->hlength;
913
914 return nfaExecGough16_Q2i(n, offset, buffer, hend, cb, context, q, end,
915 STOP_AT_MATCH);
916}
917
918char nfaExecGough8_QR(const struct NFA *n, struct mq *q, ReportID report) {
919 u64a offset = q->offset;
920 const u8 *buffer = q->buffer;
921 NfaCallback cb = q->cb;
922 void *context = q->context;
923 assert(n->type == GOUGH_NFA_8);
924 const u8 *hend = q->history + q->hlength;
925
926 char rv = nfaExecGough8_Q2i(n, offset, buffer, hend, cb, context, q,
927 0 /* end */, NO_MATCHES);
928 if (rv && nfaExecMcClellan8_inAccept(n, report, q)) {
929 return MO_MATCHES_PENDING;
930 } else {
931 return rv;
932 }
933}
934
935char nfaExecGough16_QR(const struct NFA *n, struct mq *q, ReportID report) {
936 u64a offset = q->offset;
937 const u8 *buffer = q->buffer;
938 NfaCallback cb = q->cb;
939 void *context = q->context;
940 assert(n->type == GOUGH_NFA_16);
941 const u8 *hend = q->history + q->hlength;
942
943 char rv = nfaExecGough16_Q2i(n, offset, buffer, hend, cb, context, q,
944 0 /* end */, NO_MATCHES);
945
946 if (rv && nfaExecMcClellan16_inAccept(n, report, q)) {
947 return MO_MATCHES_PENDING;
948 } else {
949 return rv;
950 }
951}
952
953char nfaExecGough8_initCompressedState(const struct NFA *nfa, u64a offset,
954 void *state, UNUSED u8 key) {
955 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(nfa);
956 memset(state, 0, nfa->streamStateSize);
957 u8 s = offset ? m->start_floating : m->start_anchored;
958 if (s) {
959 *(u8 *)state = s;
960 return 1;
961 }
962 return 0;
963}
964
965char nfaExecGough16_initCompressedState(const struct NFA *nfa, u64a offset,
966 void *state, UNUSED u8 key) {
967 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(nfa);
968 memset(state, 0, nfa->streamStateSize);
969 u16 s = offset ? m->start_floating : m->start_anchored;
970 if (s) {
971 unaligned_store_u16(state, s);
972 return 1;
973 }
974 return 0;
975}
976
977
978char nfaExecGough8_reportCurrent(const struct NFA *n, struct mq *q) {
979 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(n);
980 NfaCallback cb = q->cb;
981 void *ctxt = q->context;
982 u8 s = *(u8 *)q->state;
983 u64a offset = q_cur_offset(q);
984 struct gough_som_info *som = getSomInfo(q->state);
985 assert(q_cur_type(q) == MQE_START);
986 assert(s);
987
988 if (s >= m->accept_limit_8) {
989 u32 cached_accept_id = 0;
990 u16 cached_accept_state = 0;
991 u32 cached_accept_som = 0;
992
993 doReports(cb, ctxt, m, som, s, offset, 0, &cached_accept_state,
994 &cached_accept_id, &cached_accept_som);
995 }
996
997 return 0;
998}
999
1000char nfaExecGough16_reportCurrent(const struct NFA *n, struct mq *q) {
1001 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(n);
1002 NfaCallback cb = q->cb;
1003 void *ctxt = q->context;
1004 u16 s = *(u16 *)q->state;
1005 const struct mstate_aux *aux = get_aux(m, s);
1006 u64a offset = q_cur_offset(q);
1007 struct gough_som_info *som = getSomInfo(q->state);
1008 assert(q_cur_type(q) == MQE_START);
1009 DEBUG_PRINTF("state %hu\n", s);
1010 assert(s);
1011
1012 if (aux->accept) {
1013 u32 cached_accept_id = 0;
1014 u16 cached_accept_state = 0;
1015 u32 cached_accept_som = 0;
1016
1017 doReports(cb, ctxt, m, som, s, offset, 0, &cached_accept_state,
1018 &cached_accept_id, &cached_accept_som);
1019 }
1020
1021 return 0;
1022}
1023
1024char nfaExecGough8_inAccept(const struct NFA *n, ReportID report,
1025 struct mq *q) {
1026 return nfaExecMcClellan8_inAccept(n, report, q);
1027}
1028
1029char nfaExecGough16_inAccept(const struct NFA *n, ReportID report,
1030 struct mq *q) {
1031 return nfaExecMcClellan16_inAccept(n, report, q);
1032}
1033
1034char nfaExecGough8_inAnyAccept(const struct NFA *n, struct mq *q) {
1035 return nfaExecMcClellan8_inAnyAccept(n, q);
1036}
1037
1038char nfaExecGough16_inAnyAccept(const struct NFA *n, struct mq *q) {
1039 return nfaExecMcClellan16_inAnyAccept(n, q);
1040}
1041
1042static
1043char goughCheckEOD(const struct NFA *nfa, u16 s,
1044 const struct gough_som_info *som,
1045 u64a offset, NfaCallback cb, void *ctxt) {
1046 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(nfa);
1047 const struct mstate_aux *aux = get_aux(m, s);
1048
1049 if (!aux->accept_eod) {
1050 return MO_CONTINUE_MATCHING;
1051 }
1052 return doReports(cb, ctxt, m, som, s, offset, 1, NULL, NULL, NULL);
1053}
1054
1055char nfaExecGough8_testEOD(const struct NFA *nfa, const char *state,
1056 UNUSED const char *streamState, u64a offset,
1057 NfaCallback callback, void *context) {
1058 const struct gough_som_info *som = getSomInfoConst(state);
1059 return goughCheckEOD(nfa, *(const u8 *)state, som, offset, callback,
1060 context);
1061}
1062
1063char nfaExecGough16_testEOD(const struct NFA *nfa, const char *state,
1064 UNUSED const char *streamState, u64a offset,
1065 NfaCallback callback, void *context) {
1066 assert(ISALIGNED_N(state, 8));
1067 const struct gough_som_info *som = getSomInfoConst(state);
1068 return goughCheckEOD(nfa, *(const u16 *)state, som, offset, callback,
1069 context);
1070}
1071
1072char nfaExecGough8_queueInitState(UNUSED const struct NFA *nfa, struct mq *q) {
1073 memset(q->state, 0, nfa->scratchStateSize);
1074 return 0;
1075}
1076
1077char nfaExecGough16_queueInitState(UNUSED const struct NFA *nfa, struct mq *q) {
1078 memset(q->state, 0, nfa->scratchStateSize);
1079 assert(ISALIGNED_N(q->state, 2));
1080 return 0;
1081}
1082
1083static really_inline
1084void compSomSpace(const struct NFA *nfa, u8 *dest_som_base,
1085 const struct gough_som_info *src, u64a curr_offset) {
1086 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(nfa);
1087 const struct gough_info *gi = get_gough(m);
1088 u32 count = gi->stream_som_loc_count;
1089 u32 width = gi->stream_som_loc_width;
1090
1091 for (u32 i = 0; i < count; i++) {
1092 compressSomValue(width, curr_offset, dest_som_base, i, src->slots[i]);
1093 }
1094}
1095
1096static really_inline
1097void expandSomSpace(const struct NFA *nfa, struct gough_som_info *som,
1098 const u8 *src_som_base, u64a curr_offset) {
1099 const struct mcclellan *m = (const struct mcclellan *)getImplNfa(nfa);
1100 const struct gough_info *gi = get_gough(m);
1101 u32 count = gi->stream_som_loc_count;
1102 u32 width = gi->stream_som_loc_width;
1103
1104 for (u32 i = 0; i < count; i++) {
1105 som->slots[i] = expandSomValue(width, curr_offset, src_som_base, i);
1106 }
1107}
1108
1109char nfaExecGough8_queueCompressState(const struct NFA *nfa, const struct mq *q,
1110 s64a loc) {
1111 void *dest = q->streamState;
1112 const void *src = q->state;
1113
1114 *(u8 *)dest = *(const u8 *)src;
1115 compSomSpace(nfa, (u8 *)dest + 1, getSomInfoConst(src), q->offset + loc);
1116 return 0;
1117}
1118
1119char nfaExecGough8_expandState(const struct NFA *nfa, void *dest,
1120 const void *src, u64a offset, UNUSED u8 key) {
1121 *(u8 *)dest = *(const u8 *)src;
1122 expandSomSpace(nfa, getSomInfo(dest), (const u8 *)src + 1, offset);
1123 return 0;
1124}
1125
1126char nfaExecGough16_queueCompressState(const struct NFA *nfa,
1127 const struct mq *q, s64a loc) {
1128 void *dest = q->streamState;
1129 const void *src = q->state;
1130
1131 assert(ISALIGNED_N(src, 2));
1132 unaligned_store_u16(dest, *(const u16 *)(src));
1133 compSomSpace(nfa, (u8 *)dest + 2, getSomInfoConst(src), q->offset + loc);
1134 return 0;
1135}
1136
1137char nfaExecGough16_expandState(const struct NFA *nfa, void *dest,
1138 const void *src, u64a offset, UNUSED u8 key) {
1139 assert(ISALIGNED_N(dest, 2));
1140 *(u16 *)dest = unaligned_load_u16(src);
1141 expandSomSpace(nfa, getSomInfo(dest), (const u8 *)src + 2, offset);
1142 return 0;
1143}
1144