1 | /* |
2 | * Copyright (c) 2015-2018, 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 "mcclellan.h" |
30 | |
31 | #include "accel.h" |
32 | #include "mcclellan_internal.h" |
33 | #include "nfa_api.h" |
34 | #include "nfa_api_queue.h" |
35 | #include "nfa_internal.h" |
36 | #include "util/bitutils.h" |
37 | #include "util/compare.h" |
38 | #include "util/simd_utils.h" |
39 | #include "ue2common.h" |
40 | |
41 | #include "mcclellan_common_impl.h" |
42 | |
43 | static really_inline |
44 | char doComplexReport(NfaCallback cb, void *ctxt, const struct mcclellan *m, |
45 | u32 s, u64a loc, char eod, u32 *cached_accept_state, |
46 | u32 *cached_accept_id) { |
47 | DEBUG_PRINTF("reporting state = %u, loc=%llu, eod %hhu\n" , |
48 | s & STATE_MASK, loc, eod); |
49 | |
50 | if (!eod && s == *cached_accept_state) { |
51 | if (cb(0, loc, *cached_accept_id, ctxt) == MO_HALT_MATCHING) { |
52 | return MO_HALT_MATCHING; /* termination requested */ |
53 | } |
54 | |
55 | return MO_CONTINUE_MATCHING; /* continue execution */ |
56 | } |
57 | |
58 | const struct mstate_aux *aux = get_aux(m, s); |
59 | size_t offset = eod ? aux->accept_eod : aux->accept; |
60 | |
61 | assert(offset); |
62 | const struct report_list *rl |
63 | = (const void *)((const char *)m + offset - sizeof(struct NFA)); |
64 | assert(ISALIGNED(rl)); |
65 | |
66 | DEBUG_PRINTF("report list size %u\n" , rl->count); |
67 | u32 count = rl->count; |
68 | |
69 | if (!eod && count == 1) { |
70 | *cached_accept_state = s; |
71 | *cached_accept_id = rl->report[0]; |
72 | |
73 | DEBUG_PRINTF("reporting %u\n" , rl->report[0]); |
74 | if (cb(0, loc, rl->report[0], ctxt) == MO_HALT_MATCHING) { |
75 | return MO_HALT_MATCHING; /* termination requested */ |
76 | } |
77 | |
78 | return MO_CONTINUE_MATCHING; /* continue execution */ |
79 | } |
80 | |
81 | for (u32 i = 0; i < count; i++) { |
82 | DEBUG_PRINTF("reporting %u\n" , rl->report[i]); |
83 | if (cb(0, loc, rl->report[i], ctxt) == MO_HALT_MATCHING) { |
84 | return MO_HALT_MATCHING; /* termination requested */ |
85 | } |
86 | } |
87 | |
88 | return MO_CONTINUE_MATCHING; /* continue execution */ |
89 | } |
90 | |
91 | static really_inline |
92 | const u8 *run_mcclellan_accel(const struct mcclellan *m, |
93 | const struct mstate_aux *aux, u32 s, |
94 | const u8 **min_accel_offset, |
95 | const u8 *c, const u8 *c_end) { |
96 | DEBUG_PRINTF("skipping\n" ); |
97 | u32 accel_offset = aux[s].accel_offset; |
98 | |
99 | assert(aux[s].accel_offset); |
100 | assert(accel_offset >= m->aux_offset); |
101 | assert(!m->sherman_offset || accel_offset < m->sherman_offset); |
102 | |
103 | const union AccelAux *aaux = (const void *)((const char *)m + accel_offset); |
104 | const u8 *c2 = run_accel(aaux, c, c_end); |
105 | |
106 | if (c2 < *min_accel_offset + BAD_ACCEL_DIST) { |
107 | *min_accel_offset = c2 + BIG_ACCEL_PENALTY; |
108 | } else { |
109 | *min_accel_offset = c2 + SMALL_ACCEL_PENALTY; |
110 | } |
111 | |
112 | if (*min_accel_offset >= c_end - ACCEL_MIN_LEN) { |
113 | *min_accel_offset = c_end; |
114 | } |
115 | |
116 | DEBUG_PRINTF("advanced %zd, next accel chance in %zd/%zd\n" , |
117 | c2 - c, *min_accel_offset - c2, c_end - c2); |
118 | |
119 | return c2; |
120 | } |
121 | |
122 | static really_inline |
123 | u32 doNormal16(const struct mcclellan *m, const u8 **c_inout, const u8 *end, |
124 | u32 s, char do_accel, enum MatchMode mode) { |
125 | const u8 *c = *c_inout; |
126 | |
127 | const u16 *succ_table |
128 | = (const u16 *)((const char *)m + sizeof(struct mcclellan)); |
129 | assert(ISALIGNED_N(succ_table, 2)); |
130 | u32 sherman_base = m->sherman_limit; |
131 | const char *sherman_base_offset |
132 | = (const char *)m - sizeof(struct NFA) + m->sherman_offset; |
133 | u32 as = m->alphaShift; |
134 | |
135 | s &= STATE_MASK; |
136 | |
137 | while (c < end && s) { |
138 | u8 cprime = m->remap[*c]; |
139 | DEBUG_PRINTF("c: %02hhx '%c' cp:%02hhx (s=%u)\n" , *c, |
140 | ourisprint(*c) ? *c : '?', cprime, s); |
141 | if (s < sherman_base) { |
142 | DEBUG_PRINTF("doing normal\n" ); |
143 | assert(s < m->state_count); |
144 | s = succ_table[(s << as) + cprime]; |
145 | } else { |
146 | const char *sherman_state |
147 | = findShermanState(m, sherman_base_offset, sherman_base, s); |
148 | DEBUG_PRINTF("doing sherman (%u)\n" , s); |
149 | s = doSherman16(sherman_state, cprime, succ_table, as); |
150 | } |
151 | |
152 | DEBUG_PRINTF("s: %u (%u)\n" , s, s & STATE_MASK); |
153 | c++; |
154 | |
155 | if (do_accel && (s & ACCEL_FLAG)) { |
156 | break; |
157 | } |
158 | if (mode != NO_MATCHES && (s & ACCEPT_FLAG)) { |
159 | break; |
160 | } |
161 | |
162 | s &= STATE_MASK; |
163 | } |
164 | |
165 | *c_inout = c; |
166 | return s; |
167 | } |
168 | |
169 | static really_inline |
170 | u32 doNormalWide16(const struct mcclellan *m, const u8 **c_inout, |
171 | const u8 *end, u32 s, char *qstate, u16 *offset, |
172 | char do_accel, enum MatchMode mode) { |
173 | const u8 *c = *c_inout; |
174 | |
175 | u32 wide_limit = m->wide_limit; |
176 | const char *wide_base |
177 | = (const char *)m - sizeof(struct NFA) + m->wide_offset; |
178 | |
179 | const u16 *succ_table |
180 | = (const u16 *)((const char *)m + sizeof(struct mcclellan)); |
181 | assert(ISALIGNED_N(succ_table, 2)); |
182 | u32 sherman_base = m->sherman_limit; |
183 | const char *sherman_base_offset |
184 | = (const char *)m - sizeof(struct NFA) + m->sherman_offset; |
185 | u32 as = m->alphaShift; |
186 | |
187 | s &= STATE_MASK; |
188 | |
189 | while (c < end && s) { |
190 | u8 cprime = m->remap[*c]; |
191 | DEBUG_PRINTF("c: %02hhx '%c' cp:%02hhx (s=%u) &c: %p\n" , *c, |
192 | ourisprint(*c) ? *c : '?', cprime, s, c); |
193 | |
194 | if (unlikely(s >= wide_limit)) { |
195 | const char *wide_entry |
196 | = findWideEntry16(m, wide_base, wide_limit, s); |
197 | DEBUG_PRINTF("doing wide head (%u)\n" , s); |
198 | s = doWide16(wide_entry, &c, end, m->remap, (u16 *)&s, qstate, |
199 | offset); |
200 | } else if (s >= sherman_base) { |
201 | const char *sherman_state |
202 | = findShermanState(m, sherman_base_offset, sherman_base, s); |
203 | DEBUG_PRINTF("doing sherman (%u)\n" , s); |
204 | s = doSherman16(sherman_state, cprime, succ_table, as); |
205 | } else { |
206 | DEBUG_PRINTF("doing normal\n" ); |
207 | s = succ_table[(s << as) + cprime]; |
208 | } |
209 | |
210 | DEBUG_PRINTF("s: %u (%u)\n" , s, s & STATE_MASK); |
211 | c++; |
212 | |
213 | if (do_accel && (s & ACCEL_FLAG)) { |
214 | break; |
215 | } |
216 | if (mode != NO_MATCHES && (s & ACCEPT_FLAG)) { |
217 | break; |
218 | } |
219 | |
220 | s &= STATE_MASK; |
221 | } |
222 | |
223 | *c_inout = c; |
224 | return s; |
225 | } |
226 | |
227 | static really_inline |
228 | char mcclellanExec16_i(const struct mcclellan *m, u32 *state, char *qstate, |
229 | const u8 *buf, size_t len, u64a offAdj, NfaCallback cb, |
230 | void *ctxt, char single, const u8 **c_final, |
231 | enum MatchMode mode) { |
232 | assert(ISALIGNED_N(state, 2)); |
233 | if (!len) { |
234 | if (mode == STOP_AT_MATCH) { |
235 | *c_final = buf; |
236 | } |
237 | return MO_ALIVE; |
238 | } |
239 | |
240 | u32 s = *state; |
241 | u16 offset = 0; |
242 | const u8 *c = buf; |
243 | const u8 *c_end = buf + len; |
244 | const struct mstate_aux *aux |
245 | = (const struct mstate_aux *)((const char *)m + m->aux_offset |
246 | - sizeof(struct NFA)); |
247 | |
248 | s &= STATE_MASK; |
249 | |
250 | u32 cached_accept_id = 0; |
251 | u32 cached_accept_state = 0; |
252 | |
253 | DEBUG_PRINTF("s: %u, len %zu\n" , s, len); |
254 | |
255 | const u8 *min_accel_offset = c; |
256 | if (!m->has_accel || len < ACCEL_MIN_LEN) { |
257 | min_accel_offset = c_end; |
258 | goto without_accel; |
259 | } |
260 | |
261 | goto with_accel; |
262 | |
263 | without_accel: |
264 | do { |
265 | assert(c < min_accel_offset); |
266 | if (!s) { |
267 | goto exit; |
268 | } |
269 | |
270 | if (unlikely(m->has_wide)) { |
271 | s = doNormalWide16(m, &c, min_accel_offset, s, qstate, &offset, 0, |
272 | mode); |
273 | } else { |
274 | s = doNormal16(m, &c, min_accel_offset, s, 0, mode); |
275 | } |
276 | |
277 | if (mode != NO_MATCHES && (s & ACCEPT_FLAG)) { |
278 | if (mode == STOP_AT_MATCH) { |
279 | *state = s & STATE_MASK; |
280 | *c_final = c - 1; |
281 | return MO_MATCHES_PENDING; |
282 | } |
283 | |
284 | u64a loc = (c - 1) - buf + offAdj + 1; |
285 | |
286 | if (single) { |
287 | DEBUG_PRINTF("reporting %u\n" , m->arb_report); |
288 | if (cb(0, loc, m->arb_report, ctxt) == MO_HALT_MATCHING) { |
289 | return MO_DEAD; /* termination requested */ |
290 | } |
291 | } else if (doComplexReport(cb, ctxt, m, s & STATE_MASK, loc, 0, |
292 | &cached_accept_state, &cached_accept_id) |
293 | == MO_HALT_MATCHING) { |
294 | return MO_DEAD; |
295 | } |
296 | } |
297 | |
298 | assert(c <= min_accel_offset); |
299 | } while (c < min_accel_offset); |
300 | |
301 | s &= STATE_MASK; |
302 | |
303 | if (c == c_end) { |
304 | goto exit; |
305 | } else { |
306 | goto with_accel; |
307 | } |
308 | |
309 | with_accel: |
310 | do { |
311 | assert(c < c_end); |
312 | if (!s) { |
313 | goto exit; |
314 | } |
315 | |
316 | if (s & ACCEL_FLAG) { |
317 | DEBUG_PRINTF("skipping\n" ); |
318 | s &= STATE_MASK; |
319 | c = run_mcclellan_accel(m, aux, s, &min_accel_offset, c, c_end); |
320 | if (c == c_end) { |
321 | goto exit; |
322 | } else { |
323 | goto without_accel; |
324 | } |
325 | } |
326 | |
327 | if (unlikely(m->has_wide)) { |
328 | s = doNormalWide16(m, &c, c_end, s, qstate, &offset, 1, mode); |
329 | } else { |
330 | s = doNormal16(m, &c, c_end, s, 1, mode); |
331 | } |
332 | |
333 | if (mode != NO_MATCHES && (s & ACCEPT_FLAG)) { |
334 | if (mode == STOP_AT_MATCH) { |
335 | *state = s & STATE_MASK; |
336 | *c_final = c - 1; |
337 | return MO_MATCHES_PENDING; |
338 | } |
339 | |
340 | u64a loc = (c - 1) - buf + offAdj + 1; |
341 | |
342 | if (single) { |
343 | DEBUG_PRINTF("reporting %u\n" , m->arb_report); |
344 | if (cb(0, loc, m->arb_report, ctxt) == MO_HALT_MATCHING) { |
345 | return MO_DEAD; /* termination requested */ |
346 | } |
347 | } else if (doComplexReport(cb, ctxt, m, s & STATE_MASK, loc, 0, |
348 | &cached_accept_state, &cached_accept_id) |
349 | == MO_HALT_MATCHING) { |
350 | return MO_DEAD; |
351 | } |
352 | } |
353 | |
354 | assert(c <= c_end); |
355 | } while (c < c_end); |
356 | |
357 | exit: |
358 | s &= STATE_MASK; |
359 | |
360 | if (mode == STOP_AT_MATCH) { |
361 | *c_final = c_end; |
362 | } |
363 | *state = s; |
364 | |
365 | return MO_ALIVE; |
366 | } |
367 | |
368 | static never_inline |
369 | char mcclellanExec16_i_cb(const struct mcclellan *m, u32 *state, char *qstate, |
370 | const u8 *buf, size_t len, u64a offAdj, |
371 | NfaCallback cb, void *ctxt, char single, |
372 | const u8 **final_point) { |
373 | return mcclellanExec16_i(m, state, qstate, buf, len, offAdj, cb, ctxt, |
374 | single, final_point, CALLBACK_OUTPUT); |
375 | } |
376 | |
377 | static never_inline |
378 | char mcclellanExec16_i_sam(const struct mcclellan *m, u32 *state, char *qstate, |
379 | const u8 *buf, size_t len, u64a offAdj, |
380 | NfaCallback cb, void *ctxt, char single, |
381 | const u8 **final_point) { |
382 | return mcclellanExec16_i(m, state, qstate, buf, len, offAdj, cb, ctxt, |
383 | single, final_point, STOP_AT_MATCH); |
384 | } |
385 | |
386 | static never_inline |
387 | char mcclellanExec16_i_nm(const struct mcclellan *m, u32 *state, char *qstate, |
388 | const u8 *buf, size_t len, u64a offAdj, |
389 | NfaCallback cb, void *ctxt, char single, |
390 | const u8 **final_point) { |
391 | return mcclellanExec16_i(m, state, qstate, buf, len, offAdj, cb, ctxt, |
392 | single, final_point, NO_MATCHES); |
393 | } |
394 | |
395 | static really_inline |
396 | char mcclellanExec16_i_ni(const struct mcclellan *m, u32 *state, char *qstate, |
397 | const u8 *buf, size_t len, u64a offAdj, |
398 | NfaCallback cb, void *ctxt, char single, |
399 | const u8 **final_point, enum MatchMode mode) { |
400 | if (mode == CALLBACK_OUTPUT) { |
401 | return mcclellanExec16_i_cb(m, state, qstate, buf, len, offAdj, cb, |
402 | ctxt, single, final_point); |
403 | } else if (mode == STOP_AT_MATCH) { |
404 | return mcclellanExec16_i_sam(m, state, qstate, buf, len, offAdj, cb, |
405 | ctxt, single, final_point); |
406 | } else { |
407 | assert(mode == NO_MATCHES); |
408 | return mcclellanExec16_i_nm(m, state, qstate, buf, len, offAdj, cb, |
409 | ctxt, single, final_point); |
410 | } |
411 | } |
412 | |
413 | static really_inline |
414 | u32 doNormal8(const struct mcclellan *m, const u8 **c_inout, const u8 *end, |
415 | u32 s, char do_accel, enum MatchMode mode) { |
416 | const u8 *c = *c_inout; |
417 | u32 accel_limit = m->accel_limit_8; |
418 | u32 accept_limit = m->accept_limit_8; |
419 | |
420 | const u32 as = m->alphaShift; |
421 | const u8 *succ_table = (const u8 *)((const char *)m |
422 | + sizeof(struct mcclellan)); |
423 | while (c < end && s) { |
424 | u8 cprime = m->remap[*c]; |
425 | DEBUG_PRINTF("c: %02hhx '%c' cp:%02hhx\n" , *c, |
426 | ourisprint(*c) ? *c : '?', cprime); |
427 | s = succ_table[(s << as) + cprime]; |
428 | |
429 | DEBUG_PRINTF("s: %u\n" , s); |
430 | c++; |
431 | if (do_accel) { |
432 | if (s >= accel_limit) { |
433 | break; |
434 | } |
435 | } else { |
436 | if (mode != NO_MATCHES && s >= accept_limit) { |
437 | break; |
438 | } |
439 | } |
440 | } |
441 | *c_inout = c; |
442 | return s; |
443 | } |
444 | |
445 | static really_inline |
446 | char mcclellanExec8_i(const struct mcclellan *m, u32 *state, const u8 *buf, |
447 | size_t len, u64a offAdj, NfaCallback cb, void *ctxt, |
448 | char single, const u8 **c_final, enum MatchMode mode) { |
449 | if (!len) { |
450 | if (mode == STOP_AT_MATCH) { |
451 | *c_final = buf; |
452 | } |
453 | return MO_ALIVE; |
454 | } |
455 | u32 s = *state; |
456 | const u8 *c = buf; |
457 | const u8 *c_end = buf + len; |
458 | |
459 | const struct mstate_aux *aux |
460 | = (const struct mstate_aux *)((const char *)m + m->aux_offset |
461 | - sizeof(struct NFA)); |
462 | u32 accept_limit = m->accept_limit_8; |
463 | |
464 | u32 cached_accept_id = 0; |
465 | u32 cached_accept_state = 0; |
466 | |
467 | DEBUG_PRINTF("accel %hu, accept %u\n" , m->accel_limit_8, accept_limit); |
468 | |
469 | DEBUG_PRINTF("s: %u, len %zu\n" , s, len); |
470 | |
471 | const u8 *min_accel_offset = c; |
472 | if (!m->has_accel || len < ACCEL_MIN_LEN) { |
473 | min_accel_offset = c_end; |
474 | goto without_accel; |
475 | } |
476 | |
477 | goto with_accel; |
478 | |
479 | without_accel: |
480 | do { |
481 | assert(c < min_accel_offset); |
482 | if (!s) { |
483 | goto exit; |
484 | } |
485 | |
486 | s = doNormal8(m, &c, min_accel_offset, s, 0, mode); |
487 | |
488 | if (mode != NO_MATCHES && s >= accept_limit) { |
489 | if (mode == STOP_AT_MATCH) { |
490 | DEBUG_PRINTF("match - pausing\n" ); |
491 | *state = s; |
492 | *c_final = c - 1; |
493 | return MO_MATCHES_PENDING; |
494 | } |
495 | |
496 | u64a loc = (c - 1) - buf + offAdj + 1; |
497 | if (single) { |
498 | DEBUG_PRINTF("reporting %u\n" , m->arb_report); |
499 | if (cb(0, loc, m->arb_report, ctxt) == MO_HALT_MATCHING) { |
500 | return MO_DEAD; |
501 | } |
502 | } else if (doComplexReport(cb, ctxt, m, s, loc, 0, |
503 | &cached_accept_state, &cached_accept_id) |
504 | == MO_HALT_MATCHING) { |
505 | return MO_DEAD; |
506 | } |
507 | } |
508 | |
509 | assert(c <= min_accel_offset); |
510 | } while (c < min_accel_offset); |
511 | |
512 | if (c == c_end) { |
513 | goto exit; |
514 | } |
515 | |
516 | with_accel: |
517 | do { |
518 | u32 accel_limit = m->accel_limit_8; |
519 | assert(c < c_end); |
520 | |
521 | if (!s) { |
522 | goto exit; |
523 | } |
524 | |
525 | if (s >= accel_limit && aux[s].accel_offset) { |
526 | c = run_mcclellan_accel(m, aux, s, &min_accel_offset, c, c_end); |
527 | if (c == c_end) { |
528 | goto exit; |
529 | } else { |
530 | goto without_accel; |
531 | } |
532 | } |
533 | s = doNormal8(m, &c, c_end, s, 1, mode); |
534 | |
535 | if (mode != NO_MATCHES && s >= accept_limit) { |
536 | if (mode == STOP_AT_MATCH) { |
537 | DEBUG_PRINTF("match - pausing\n" ); |
538 | *state = s; |
539 | *c_final = c - 1; |
540 | return MO_MATCHES_PENDING; |
541 | } |
542 | |
543 | u64a loc = (c - 1) - buf + offAdj + 1; |
544 | if (single) { |
545 | DEBUG_PRINTF("reporting %u\n" , m->arb_report); |
546 | if (cb(0, loc, m->arb_report, ctxt) == MO_HALT_MATCHING) { |
547 | return MO_DEAD; |
548 | } |
549 | } else if (doComplexReport(cb, ctxt, m, s, loc, 0, |
550 | &cached_accept_state, &cached_accept_id) |
551 | == MO_HALT_MATCHING) { |
552 | return MO_DEAD; |
553 | } |
554 | } |
555 | |
556 | assert(c <= c_end); |
557 | } while (c < c_end); |
558 | |
559 | exit: |
560 | *state = s; |
561 | if (mode == STOP_AT_MATCH) { |
562 | *c_final = c_end; |
563 | } |
564 | return MO_ALIVE; |
565 | } |
566 | |
567 | static never_inline |
568 | char mcclellanExec8_i_cb(const struct mcclellan *m, u32 *state, const u8 *buf, |
569 | size_t len, u64a offAdj, NfaCallback cb, void *ctxt, |
570 | char single, const u8 **final_point) { |
571 | return mcclellanExec8_i(m, state, buf, len, offAdj, cb, ctxt, single, |
572 | final_point, CALLBACK_OUTPUT); |
573 | } |
574 | |
575 | static never_inline |
576 | char mcclellanExec8_i_sam(const struct mcclellan *m, u32 *state, const u8 *buf, |
577 | size_t len, u64a offAdj, NfaCallback cb, void *ctxt, |
578 | char single, const u8 **final_point) { |
579 | return mcclellanExec8_i(m, state, buf, len, offAdj, cb, ctxt, single, |
580 | final_point, STOP_AT_MATCH); |
581 | } |
582 | |
583 | static never_inline |
584 | char mcclellanExec8_i_nm(const struct mcclellan *m, u32 *state, const u8 *buf, |
585 | size_t len, u64a offAdj, NfaCallback cb, void *ctxt, |
586 | char single, const u8 **final_point) { |
587 | return mcclellanExec8_i(m, state, buf, len, offAdj, cb, ctxt, single, |
588 | final_point, NO_MATCHES); |
589 | } |
590 | |
591 | static really_inline |
592 | char mcclellanExec8_i_ni(const struct mcclellan *m, u32 *state, const u8 *buf, |
593 | size_t len, u64a offAdj, NfaCallback cb, void *ctxt, |
594 | char single, const u8 **final_point, |
595 | enum MatchMode mode) { |
596 | if (mode == CALLBACK_OUTPUT) { |
597 | return mcclellanExec8_i_cb(m, state, buf, len, offAdj, cb, ctxt, single, |
598 | final_point); |
599 | } else if (mode == STOP_AT_MATCH) { |
600 | return mcclellanExec8_i_sam(m, state, buf, len, offAdj, cb, ctxt, |
601 | single, final_point); |
602 | } else { |
603 | assert(mode == NO_MATCHES); |
604 | return mcclellanExec8_i_nm(m, state, buf, len, offAdj, cb, ctxt, single, |
605 | final_point); |
606 | } |
607 | } |
608 | |
609 | static really_inline |
610 | char mcclellanCheckEOD(const struct NFA *nfa, u32 s, u64a offset, |
611 | NfaCallback cb, void *ctxt) { |
612 | const struct mcclellan *m = getImplNfa(nfa); |
613 | const struct mstate_aux *aux = get_aux(m, s); |
614 | |
615 | if (m->has_wide == 1 && s >= m->wide_limit) { |
616 | return MO_CONTINUE_MATCHING; |
617 | } |
618 | |
619 | if (!aux->accept_eod) { |
620 | return MO_CONTINUE_MATCHING; |
621 | } |
622 | return doComplexReport(cb, ctxt, m, s, offset, 1, NULL, NULL); |
623 | } |
624 | |
625 | static really_inline |
626 | char nfaExecMcClellan16_Q2i(const struct NFA *n, u64a offset, const u8 *buffer, |
627 | const u8 *hend, NfaCallback cb, void *context, |
628 | struct mq *q, char single, s64a end, |
629 | enum MatchMode mode) { |
630 | assert(n->type == MCCLELLAN_NFA_16); |
631 | const struct mcclellan *m = getImplNfa(n); |
632 | s64a sp; |
633 | |
634 | assert(ISALIGNED_N(q->state, 2)); |
635 | u32 s = *(u16 *)q->state; |
636 | |
637 | if (q->report_current) { |
638 | assert(s); |
639 | assert(get_aux(m, s)->accept); |
640 | |
641 | int rv; |
642 | if (single) { |
643 | DEBUG_PRINTF("reporting %u\n" , m->arb_report); |
644 | rv = cb(0, q_cur_offset(q), m->arb_report, context); |
645 | } else { |
646 | u32 cached_accept_id = 0; |
647 | u32 cached_accept_state = 0; |
648 | |
649 | rv = doComplexReport(cb, context, m, s, q_cur_offset(q), 0, |
650 | &cached_accept_state, &cached_accept_id); |
651 | } |
652 | |
653 | q->report_current = 0; |
654 | |
655 | if (rv == MO_HALT_MATCHING) { |
656 | return MO_DEAD; |
657 | } |
658 | } |
659 | |
660 | sp = q_cur_loc(q); |
661 | q->cur++; |
662 | |
663 | const u8 *cur_buf = sp < 0 ? hend : buffer; |
664 | |
665 | assert(q->cur); |
666 | if (mode != NO_MATCHES && q->items[q->cur - 1].location > end) { |
667 | DEBUG_PRINTF("this is as far as we go\n" ); |
668 | q->cur--; |
669 | q->items[q->cur].type = MQE_START; |
670 | q->items[q->cur].location = end; |
671 | *(u16 *)q->state = s; |
672 | return MO_ALIVE; |
673 | } |
674 | |
675 | while (1) { |
676 | assert(q->cur < q->end); |
677 | s64a ep = q->items[q->cur].location; |
678 | if (mode != NO_MATCHES) { |
679 | ep = MIN(ep, end); |
680 | } |
681 | |
682 | assert(ep >= sp); |
683 | |
684 | s64a local_ep = ep; |
685 | if (sp < 0) { |
686 | local_ep = MIN(0, ep); |
687 | } |
688 | |
689 | /* do main buffer region */ |
690 | const u8 *final_look; |
691 | char rv = mcclellanExec16_i_ni(m, &s, q->state, cur_buf + sp, |
692 | local_ep - sp, offset + sp, cb, context, |
693 | single, &final_look, mode); |
694 | if (rv == MO_DEAD) { |
695 | *(u16 *)q->state = 0; |
696 | return MO_DEAD; |
697 | } |
698 | if (mode == STOP_AT_MATCH && rv == MO_MATCHES_PENDING) { |
699 | DEBUG_PRINTF("this is as far as we go\n" ); |
700 | DEBUG_PRINTF("state %u final_look %zd\n" , s, final_look - cur_buf); |
701 | |
702 | assert(q->cur); |
703 | assert(final_look != cur_buf + local_ep); |
704 | |
705 | q->cur--; |
706 | q->items[q->cur].type = MQE_START; |
707 | q->items[q->cur].location = final_look - cur_buf + 1; /* due to |
708 | * early -1 */ |
709 | *(u16 *)q->state = s; |
710 | return MO_MATCHES_PENDING; |
711 | } |
712 | |
713 | assert(rv == MO_ALIVE); |
714 | assert(q->cur); |
715 | if (mode != NO_MATCHES && q->items[q->cur].location > end) { |
716 | DEBUG_PRINTF("this is as far as we go\n" ); |
717 | q->cur--; |
718 | q->items[q->cur].type = MQE_START; |
719 | q->items[q->cur].location = end; |
720 | *(u16 *)q->state = s; |
721 | return MO_ALIVE; |
722 | } |
723 | |
724 | sp = local_ep; |
725 | |
726 | if (sp == 0) { |
727 | cur_buf = buffer; |
728 | } |
729 | |
730 | if (sp != ep) { |
731 | continue; |
732 | } |
733 | |
734 | switch (q->items[q->cur].type) { |
735 | case MQE_TOP: |
736 | assert(sp + offset || !s); |
737 | if (sp + offset == 0) { |
738 | s = m->start_anchored; |
739 | break; |
740 | } |
741 | s = mcclellanEnableStarts(m, s); |
742 | break; |
743 | case MQE_END: |
744 | *(u16 *)q->state = s; |
745 | q->cur++; |
746 | return s ? MO_ALIVE : MO_DEAD; |
747 | default: |
748 | assert(!"invalid queue event" ); |
749 | } |
750 | |
751 | q->cur++; |
752 | } |
753 | } |
754 | |
755 | static really_inline |
756 | char nfaExecMcClellan16_Bi(const struct NFA *n, u64a offset, const u8 *buffer, |
757 | size_t length, NfaCallback cb, void *context, |
758 | char single) { |
759 | assert(n->type == MCCLELLAN_NFA_16); |
760 | const struct mcclellan *m = getImplNfa(n); |
761 | u32 s = m->start_anchored; |
762 | |
763 | if (mcclellanExec16_i(m, &s, NULL, buffer, length, offset, cb, context, |
764 | single, NULL, CALLBACK_OUTPUT) |
765 | == MO_DEAD) { |
766 | return s ? MO_ALIVE : MO_DEAD; |
767 | } |
768 | |
769 | if (m->has_wide == 1 && s >= m->wide_limit) { |
770 | return MO_ALIVE; |
771 | } |
772 | |
773 | const struct mstate_aux *aux = get_aux(m, s); |
774 | |
775 | if (aux->accept_eod) { |
776 | doComplexReport(cb, context, m, s, offset + length, 1, NULL, NULL); |
777 | } |
778 | |
779 | return MO_ALIVE; |
780 | } |
781 | |
782 | static really_inline |
783 | char nfaExecMcClellan8_Q2i(const struct NFA *n, u64a offset, const u8 *buffer, |
784 | const u8 *hend, NfaCallback cb, void *context, |
785 | struct mq *q, char single, s64a end, |
786 | enum MatchMode mode) { |
787 | assert(n->type == MCCLELLAN_NFA_8); |
788 | const struct mcclellan *m = getImplNfa(n); |
789 | s64a sp; |
790 | |
791 | u32 s = *(u8 *)q->state; |
792 | |
793 | if (q->report_current) { |
794 | assert(s); |
795 | assert(s >= m->accept_limit_8); |
796 | |
797 | int rv; |
798 | if (single) { |
799 | DEBUG_PRINTF("reporting %u\n" , m->arb_report); |
800 | rv = cb(0, q_cur_offset(q), m->arb_report, context); |
801 | } else { |
802 | u32 cached_accept_id = 0; |
803 | u32 cached_accept_state = 0; |
804 | |
805 | rv = doComplexReport(cb, context, m, s, q_cur_offset(q), 0, |
806 | &cached_accept_state, &cached_accept_id); |
807 | } |
808 | |
809 | q->report_current = 0; |
810 | |
811 | if (rv == MO_HALT_MATCHING) { |
812 | return MO_DEAD; |
813 | } |
814 | } |
815 | |
816 | sp = q_cur_loc(q); |
817 | q->cur++; |
818 | |
819 | const u8 *cur_buf = sp < 0 ? hend : buffer; |
820 | |
821 | if (mode != NO_MATCHES && q->items[q->cur - 1].location > end) { |
822 | DEBUG_PRINTF("this is as far as we go\n" ); |
823 | q->cur--; |
824 | q->items[q->cur].type = MQE_START; |
825 | q->items[q->cur].location = end; |
826 | *(u8 *)q->state = s; |
827 | return MO_ALIVE; |
828 | } |
829 | |
830 | while (1) { |
831 | DEBUG_PRINTF("%s @ %llu\n" , q->items[q->cur].type == MQE_TOP ? "TOP" : |
832 | q->items[q->cur].type == MQE_END ? "END" : "???" , |
833 | q->items[q->cur].location + offset); |
834 | assert(q->cur < q->end); |
835 | s64a ep = q->items[q->cur].location; |
836 | if (mode != NO_MATCHES) { |
837 | ep = MIN(ep, end); |
838 | } |
839 | |
840 | assert(ep >= sp); |
841 | |
842 | s64a local_ep = ep; |
843 | if (sp < 0) { |
844 | local_ep = MIN(0, ep); |
845 | } |
846 | |
847 | const u8 *final_look; |
848 | char rv = mcclellanExec8_i_ni(m, &s, cur_buf + sp, local_ep - sp, |
849 | offset + sp, cb, context, single, |
850 | &final_look, mode); |
851 | |
852 | if (rv == MO_HALT_MATCHING) { |
853 | *(u8 *)q->state = 0; |
854 | return MO_DEAD; |
855 | } |
856 | if (mode == STOP_AT_MATCH && rv == MO_MATCHES_PENDING) { |
857 | DEBUG_PRINTF("this is as far as we go\n" ); |
858 | DEBUG_PRINTF("state %u final_look %zd\n" , s, final_look - cur_buf); |
859 | |
860 | assert(q->cur); |
861 | assert(final_look != cur_buf + local_ep); |
862 | |
863 | q->cur--; |
864 | q->items[q->cur].type = MQE_START; |
865 | q->items[q->cur].location = final_look - cur_buf + 1; /* due to |
866 | * early -1 */ |
867 | *(u8 *)q->state = s; |
868 | return MO_MATCHES_PENDING; |
869 | } |
870 | |
871 | assert(rv == MO_ALIVE); |
872 | assert(q->cur); |
873 | if (mode != NO_MATCHES && q->items[q->cur].location > end) { |
874 | DEBUG_PRINTF("this is as far as we go\n" ); |
875 | assert(q->cur); |
876 | q->cur--; |
877 | q->items[q->cur].type = MQE_START; |
878 | q->items[q->cur].location = end; |
879 | *(u8 *)q->state = s; |
880 | return MO_ALIVE; |
881 | } |
882 | |
883 | sp = local_ep; |
884 | |
885 | if (sp == 0) { |
886 | cur_buf = buffer; |
887 | } |
888 | |
889 | if (sp != ep) { |
890 | continue; |
891 | } |
892 | |
893 | switch (q->items[q->cur].type) { |
894 | case MQE_TOP: |
895 | assert(sp + offset || !s); |
896 | if (sp + offset == 0) { |
897 | s = (u8)m->start_anchored; |
898 | break; |
899 | } |
900 | s = mcclellanEnableStarts(m, s); |
901 | break; |
902 | case MQE_END: |
903 | *(u8 *)q->state = s; |
904 | q->cur++; |
905 | return s ? MO_ALIVE : MO_DEAD; |
906 | default: |
907 | assert(!"invalid queue event" ); |
908 | } |
909 | |
910 | q->cur++; |
911 | } |
912 | } |
913 | |
914 | static really_inline |
915 | char nfaExecMcClellan8_Bi(const struct NFA *n, u64a offset, const u8 *buffer, |
916 | size_t length, NfaCallback cb, void *context, |
917 | char single) { |
918 | assert(n->type == MCCLELLAN_NFA_8); |
919 | const struct mcclellan *m = getImplNfa(n); |
920 | u32 s = m->start_anchored; |
921 | |
922 | if (mcclellanExec8_i(m, &s, buffer, length, offset, cb, context, single, |
923 | NULL, CALLBACK_OUTPUT) |
924 | == MO_DEAD) { |
925 | return MO_DEAD; |
926 | } |
927 | |
928 | const struct mstate_aux *aux = get_aux(m, s); |
929 | |
930 | if (aux->accept_eod) { |
931 | doComplexReport(cb, context, m, s, offset + length, 1, NULL, NULL); |
932 | } |
933 | |
934 | return s ? MO_ALIVE : MO_DEAD; |
935 | } |
936 | |
937 | char nfaExecMcClellan8_B(const struct NFA *n, u64a offset, const u8 *buffer, |
938 | size_t length, NfaCallback cb, void *context) { |
939 | assert(n->type == MCCLELLAN_NFA_8); |
940 | const struct mcclellan *m = getImplNfa(n); |
941 | |
942 | if (m->flags & MCCLELLAN_FLAG_SINGLE) { |
943 | return nfaExecMcClellan8_Bi(n, offset, buffer, length, cb, context, 1); |
944 | } else { |
945 | return nfaExecMcClellan8_Bi(n, offset, buffer, length, cb, context, 0); |
946 | } |
947 | } |
948 | |
949 | char nfaExecMcClellan8_Q(const struct NFA *n, struct mq *q, s64a end) { |
950 | u64a offset = q->offset; |
951 | const u8 *buffer = q->buffer; |
952 | NfaCallback cb = q->cb; |
953 | void *context = q->context; |
954 | assert(n->type == MCCLELLAN_NFA_8); |
955 | const struct mcclellan *m = getImplNfa(n); |
956 | const u8 *hend = q->history + q->hlength; |
957 | |
958 | return nfaExecMcClellan8_Q2i(n, offset, buffer, hend, cb, context, q, |
959 | m->flags & MCCLELLAN_FLAG_SINGLE, end, |
960 | CALLBACK_OUTPUT); |
961 | } |
962 | |
963 | char nfaExecMcClellan16_B(const struct NFA *n, u64a offset, const u8 *buffer, |
964 | size_t length, NfaCallback cb, void *context) { |
965 | assert(n->type == MCCLELLAN_NFA_16); |
966 | const struct mcclellan *m = getImplNfa(n); |
967 | |
968 | if (m->flags & MCCLELLAN_FLAG_SINGLE) { |
969 | return nfaExecMcClellan16_Bi(n, offset, buffer, length, cb, context, 1); |
970 | } else { |
971 | return nfaExecMcClellan16_Bi(n, offset, buffer, length, cb, context, 0); |
972 | } |
973 | } |
974 | |
975 | char nfaExecMcClellan16_Q(const struct NFA *n, struct mq *q, s64a end) { |
976 | u64a offset = q->offset; |
977 | const u8 *buffer = q->buffer; |
978 | NfaCallback cb = q->cb; |
979 | void *context = q->context; |
980 | assert(n->type == MCCLELLAN_NFA_16); |
981 | const struct mcclellan *m = getImplNfa(n); |
982 | const u8 *hend = q->history + q->hlength; |
983 | |
984 | return nfaExecMcClellan16_Q2i(n, offset, buffer, hend, cb, context, q, |
985 | m->flags & MCCLELLAN_FLAG_SINGLE, end, |
986 | CALLBACK_OUTPUT); |
987 | } |
988 | |
989 | char nfaExecMcClellan8_reportCurrent(const struct NFA *n, struct mq *q) { |
990 | const struct mcclellan *m = getImplNfa(n); |
991 | NfaCallback cb = q->cb; |
992 | void *ctxt = q->context; |
993 | u32 s = *(u8 *)q->state; |
994 | u8 single = m->flags & MCCLELLAN_FLAG_SINGLE; |
995 | u64a offset = q_cur_offset(q); |
996 | assert(q_cur_type(q) == MQE_START); |
997 | assert(s); |
998 | |
999 | if (s >= m->accept_limit_8) { |
1000 | if (single) { |
1001 | DEBUG_PRINTF("reporting %u\n" , m->arb_report); |
1002 | cb(0, offset, m->arb_report, ctxt); |
1003 | } else { |
1004 | u32 cached_accept_id = 0; |
1005 | u32 cached_accept_state = 0; |
1006 | |
1007 | doComplexReport(cb, ctxt, m, s, offset, 0, &cached_accept_state, |
1008 | &cached_accept_id); |
1009 | } |
1010 | } |
1011 | |
1012 | return 0; |
1013 | } |
1014 | |
1015 | char nfaExecMcClellan16_reportCurrent(const struct NFA *n, struct mq *q) { |
1016 | const struct mcclellan *m = getImplNfa(n); |
1017 | NfaCallback cb = q->cb; |
1018 | void *ctxt = q->context; |
1019 | u32 s = *(u16 *)q->state; |
1020 | const struct mstate_aux *aux = get_aux(m, s); |
1021 | u8 single = m->flags & MCCLELLAN_FLAG_SINGLE; |
1022 | u64a offset = q_cur_offset(q); |
1023 | assert(q_cur_type(q) == MQE_START); |
1024 | DEBUG_PRINTF("state %u\n" , s); |
1025 | assert(s); |
1026 | |
1027 | if (aux->accept) { |
1028 | if (single) { |
1029 | DEBUG_PRINTF("reporting %u\n" , m->arb_report); |
1030 | cb(0, offset, m->arb_report, ctxt); |
1031 | } else { |
1032 | u32 cached_accept_id = 0; |
1033 | u32 cached_accept_state = 0; |
1034 | |
1035 | doComplexReport(cb, ctxt, m, s, offset, 0, &cached_accept_state, |
1036 | &cached_accept_id); |
1037 | } |
1038 | } |
1039 | |
1040 | return 0; |
1041 | } |
1042 | |
1043 | static |
1044 | char mcclellanHasAccept(const struct mcclellan *m, const struct mstate_aux *aux, |
1045 | ReportID report) { |
1046 | assert(m && aux); |
1047 | |
1048 | if (!aux->accept) { |
1049 | return 0; |
1050 | } |
1051 | |
1052 | const struct report_list *rl = (const struct report_list *) |
1053 | ((const char *)m + aux->accept - sizeof(struct NFA)); |
1054 | assert(ISALIGNED_N(rl, 4)); |
1055 | |
1056 | DEBUG_PRINTF("report list has %u entries\n" , rl->count); |
1057 | |
1058 | for (u32 i = 0; i < rl->count; i++) { |
1059 | if (rl->report[i] == report) { |
1060 | return 1; |
1061 | } |
1062 | } |
1063 | |
1064 | return 0; |
1065 | } |
1066 | |
1067 | char nfaExecMcClellan8_inAccept(const struct NFA *n, ReportID report, |
1068 | struct mq *q) { |
1069 | assert(n && q); |
1070 | |
1071 | const struct mcclellan *m = getImplNfa(n); |
1072 | u8 s = *(u8 *)q->state; |
1073 | DEBUG_PRINTF("checking accepts for %hhu\n" , s); |
1074 | if (s < m->accept_limit_8) { |
1075 | return 0; |
1076 | } |
1077 | |
1078 | return mcclellanHasAccept(m, get_aux(m, s), report); |
1079 | } |
1080 | |
1081 | char nfaExecMcClellan8_inAnyAccept(const struct NFA *n, struct mq *q) { |
1082 | assert(n && q); |
1083 | |
1084 | const struct mcclellan *m = getImplNfa(n); |
1085 | u8 s = *(u8 *)q->state; |
1086 | DEBUG_PRINTF("checking accepts for %hhu\n" , s); |
1087 | assert(s < m->accept_limit_8 || get_aux(m, s)->accept); |
1088 | |
1089 | return s >= m->accept_limit_8; |
1090 | } |
1091 | |
1092 | char nfaExecMcClellan16_inAccept(const struct NFA *n, ReportID report, |
1093 | struct mq *q) { |
1094 | assert(n && q); |
1095 | |
1096 | const struct mcclellan *m = getImplNfa(n); |
1097 | u16 s = *(u16 *)q->state; |
1098 | DEBUG_PRINTF("checking accepts for %hu\n" , s); |
1099 | |
1100 | return (m->has_wide == 1 && s >= m->wide_limit) ? |
1101 | 0 : mcclellanHasAccept(m, get_aux(m, s), report); |
1102 | } |
1103 | |
1104 | char nfaExecMcClellan16_inAnyAccept(const struct NFA *n, struct mq *q) { |
1105 | assert(n && q); |
1106 | |
1107 | const struct mcclellan *m = getImplNfa(n); |
1108 | u16 s = *(u16 *)q->state; |
1109 | DEBUG_PRINTF("checking accepts for %hu\n" , s); |
1110 | |
1111 | return (m->has_wide == 1 && s >= m->wide_limit) ? |
1112 | 0 : !!get_aux(m, s)->accept; |
1113 | } |
1114 | |
1115 | char nfaExecMcClellan8_Q2(const struct NFA *n, struct mq *q, s64a end) { |
1116 | u64a offset = q->offset; |
1117 | const u8 *buffer = q->buffer; |
1118 | NfaCallback cb = q->cb; |
1119 | void *context = q->context; |
1120 | assert(n->type == MCCLELLAN_NFA_8); |
1121 | const struct mcclellan *m = getImplNfa(n); |
1122 | const u8 *hend = q->history + q->hlength; |
1123 | |
1124 | return nfaExecMcClellan8_Q2i(n, offset, buffer, hend, cb, context, q, |
1125 | m->flags & MCCLELLAN_FLAG_SINGLE, end, |
1126 | STOP_AT_MATCH); |
1127 | } |
1128 | |
1129 | char nfaExecMcClellan16_Q2(const struct NFA *n, struct mq *q, s64a end) { |
1130 | u64a offset = q->offset; |
1131 | const u8 *buffer = q->buffer; |
1132 | NfaCallback cb = q->cb; |
1133 | void *context = q->context; |
1134 | assert(n->type == MCCLELLAN_NFA_16); |
1135 | const struct mcclellan *m = getImplNfa(n); |
1136 | const u8 *hend = q->history + q->hlength; |
1137 | |
1138 | return nfaExecMcClellan16_Q2i(n, offset, buffer, hend, cb, context, q, |
1139 | m->flags & MCCLELLAN_FLAG_SINGLE, end, |
1140 | STOP_AT_MATCH); |
1141 | } |
1142 | |
1143 | char nfaExecMcClellan8_QR(const struct NFA *n, struct mq *q, ReportID report) { |
1144 | u64a offset = q->offset; |
1145 | const u8 *buffer = q->buffer; |
1146 | NfaCallback cb = q->cb; |
1147 | void *context = q->context; |
1148 | assert(n->type == MCCLELLAN_NFA_8); |
1149 | const struct mcclellan *m = getImplNfa(n); |
1150 | const u8 *hend = q->history + q->hlength; |
1151 | |
1152 | char rv = nfaExecMcClellan8_Q2i(n, offset, buffer, hend, cb, context, q, |
1153 | m->flags & MCCLELLAN_FLAG_SINGLE, 0 /* end */, |
1154 | NO_MATCHES); |
1155 | if (rv && nfaExecMcClellan8_inAccept(n, report, q)) { |
1156 | return MO_MATCHES_PENDING; |
1157 | } else { |
1158 | return rv; |
1159 | } |
1160 | } |
1161 | |
1162 | char nfaExecMcClellan16_QR(const struct NFA *n, struct mq *q, ReportID report) { |
1163 | u64a offset = q->offset; |
1164 | const u8 *buffer = q->buffer; |
1165 | NfaCallback cb = q->cb; |
1166 | void *context = q->context; |
1167 | assert(n->type == MCCLELLAN_NFA_16); |
1168 | const struct mcclellan *m = getImplNfa(n); |
1169 | const u8 *hend = q->history + q->hlength; |
1170 | |
1171 | char rv = nfaExecMcClellan16_Q2i(n, offset, buffer, hend, cb, context, q, |
1172 | m->flags & MCCLELLAN_FLAG_SINGLE, |
1173 | 0 /* end */, NO_MATCHES); |
1174 | |
1175 | if (rv && nfaExecMcClellan16_inAccept(n, report, q)) { |
1176 | return MO_MATCHES_PENDING; |
1177 | } else { |
1178 | return rv; |
1179 | } |
1180 | } |
1181 | |
1182 | char nfaExecMcClellan8_initCompressedState(const struct NFA *nfa, u64a offset, |
1183 | void *state, UNUSED u8 key) { |
1184 | const struct mcclellan *m = getImplNfa(nfa); |
1185 | u8 s = offset ? m->start_floating : m->start_anchored; |
1186 | if (s) { |
1187 | *(u8 *)state = s; |
1188 | return 1; |
1189 | } |
1190 | return 0; |
1191 | } |
1192 | |
1193 | char nfaExecMcClellan16_initCompressedState(const struct NFA *nfa, u64a offset, |
1194 | void *state, UNUSED u8 key) { |
1195 | const struct mcclellan *m = getImplNfa(nfa); |
1196 | u16 s = offset ? m->start_floating : m->start_anchored; |
1197 | |
1198 | // new byte |
1199 | if (m->has_wide) { |
1200 | unaligned_store_u16((u16 *)state + 1, 0); |
1201 | } |
1202 | |
1203 | if (s) { |
1204 | unaligned_store_u16(state, s); |
1205 | return 1; |
1206 | } |
1207 | return 0; |
1208 | } |
1209 | |
1210 | void nfaExecMcClellan8_SimpStream(const struct NFA *nfa, char *state, |
1211 | const u8 *buf, char top, size_t start_off, |
1212 | size_t len, NfaCallback cb, void *ctxt) { |
1213 | const struct mcclellan *m = getImplNfa(nfa); |
1214 | |
1215 | u32 s = top ? m->start_anchored : *(u8 *)state; |
1216 | |
1217 | if (m->flags & MCCLELLAN_FLAG_SINGLE) { |
1218 | mcclellanExec8_i(m, &s, buf + start_off, len - start_off, |
1219 | start_off, cb, ctxt, 1, NULL, CALLBACK_OUTPUT); |
1220 | } else { |
1221 | mcclellanExec8_i(m, &s, buf + start_off, len - start_off, |
1222 | start_off, cb, ctxt, 0, NULL, CALLBACK_OUTPUT); |
1223 | } |
1224 | |
1225 | *(u8 *)state = s; |
1226 | } |
1227 | |
1228 | void nfaExecMcClellan16_SimpStream(const struct NFA *nfa, char *state, |
1229 | const u8 *buf, char top, size_t start_off, |
1230 | size_t len, NfaCallback cb, void *ctxt) { |
1231 | const struct mcclellan *m = getImplNfa(nfa); |
1232 | u32 s; |
1233 | |
1234 | if (top) { |
1235 | s = m->start_anchored; |
1236 | |
1237 | // new byte |
1238 | if (m->has_wide) { |
1239 | unaligned_store_u16((u16 *)state + 1, 0); |
1240 | } |
1241 | } else { |
1242 | s = unaligned_load_u16(state); |
1243 | } |
1244 | |
1245 | if (m->flags & MCCLELLAN_FLAG_SINGLE) { |
1246 | mcclellanExec16_i(m, &s, state, buf + start_off, len - start_off, |
1247 | start_off, cb, ctxt, 1, NULL, CALLBACK_OUTPUT); |
1248 | } else { |
1249 | mcclellanExec16_i(m, &s, state, buf + start_off, len - start_off, |
1250 | start_off, cb, ctxt, 0, NULL, CALLBACK_OUTPUT); |
1251 | } |
1252 | |
1253 | unaligned_store_u16(state, s); |
1254 | } |
1255 | |
1256 | char nfaExecMcClellan8_testEOD(const struct NFA *nfa, const char *state, |
1257 | UNUSED const char *streamState, u64a offset, |
1258 | NfaCallback callback, void *context) { |
1259 | return mcclellanCheckEOD(nfa, *(const u8 *)state, offset, callback, |
1260 | context); |
1261 | } |
1262 | |
1263 | char nfaExecMcClellan16_testEOD(const struct NFA *nfa, const char *state, |
1264 | UNUSED const char *streamState, u64a offset, |
1265 | NfaCallback callback, void *context) { |
1266 | assert(ISALIGNED_N(state, 2)); |
1267 | return mcclellanCheckEOD(nfa, *(const u16 *)state, offset, callback, |
1268 | context); |
1269 | } |
1270 | |
1271 | char nfaExecMcClellan8_queueInitState(UNUSED const struct NFA *nfa, |
1272 | struct mq *q) { |
1273 | assert(nfa->scratchStateSize == 1); |
1274 | *(u8 *)q->state = 0; |
1275 | return 0; |
1276 | } |
1277 | |
1278 | char nfaExecMcClellan16_queueInitState(UNUSED const struct NFA *nfa, |
1279 | struct mq *q) { |
1280 | const struct mcclellan *m = getImplNfa(nfa); |
1281 | assert(m->has_wide == 1 ? nfa->scratchStateSize == 4 |
1282 | : nfa->scratchStateSize == 2); |
1283 | assert(ISALIGNED_N(q->state, 2)); |
1284 | *(u16 *)q->state = 0; |
1285 | |
1286 | // new byte |
1287 | if (m->has_wide) { |
1288 | unaligned_store_u16((u16 *)q->state + 1, 0); |
1289 | } |
1290 | return 0; |
1291 | } |
1292 | |
1293 | char nfaExecMcClellan8_queueCompressState(UNUSED const struct NFA *nfa, |
1294 | const struct mq *q, UNUSED s64a loc) { |
1295 | void *dest = q->streamState; |
1296 | const void *src = q->state; |
1297 | assert(nfa->scratchStateSize == 1); |
1298 | assert(nfa->streamStateSize == 1); |
1299 | *(u8 *)dest = *(const u8 *)src; |
1300 | return 0; |
1301 | } |
1302 | |
1303 | char nfaExecMcClellan8_expandState(UNUSED const struct NFA *nfa, void *dest, |
1304 | const void *src, UNUSED u64a offset, |
1305 | UNUSED u8 key) { |
1306 | assert(nfa->scratchStateSize == 1); |
1307 | assert(nfa->streamStateSize == 1); |
1308 | *(u8 *)dest = *(const u8 *)src; |
1309 | return 0; |
1310 | } |
1311 | |
1312 | char nfaExecMcClellan16_queueCompressState(UNUSED const struct NFA *nfa, |
1313 | const struct mq *q, |
1314 | UNUSED s64a loc) { |
1315 | const struct mcclellan *m = getImplNfa(nfa); |
1316 | void *dest = q->streamState; |
1317 | const void *src = q->state; |
1318 | assert(m->has_wide == 1 ? nfa->scratchStateSize == 4 |
1319 | : nfa->scratchStateSize == 2); |
1320 | assert(m->has_wide == 1 ? nfa->streamStateSize == 4 |
1321 | : nfa->streamStateSize == 2); |
1322 | |
1323 | assert(ISALIGNED_N(src, 2)); |
1324 | unaligned_store_u16(dest, *(const u16 *)(src)); |
1325 | |
1326 | // new byte |
1327 | if (m->has_wide) { |
1328 | unaligned_store_u16((u16 *)dest + 1, *((const u16 *)src + 1)); |
1329 | } |
1330 | return 0; |
1331 | } |
1332 | |
1333 | char nfaExecMcClellan16_expandState(UNUSED const struct NFA *nfa, void *dest, |
1334 | const void *src, UNUSED u64a offset, |
1335 | UNUSED u8 key) { |
1336 | const struct mcclellan *m = getImplNfa(nfa); |
1337 | assert(m->has_wide == 1 ? nfa->scratchStateSize == 4 |
1338 | : nfa->scratchStateSize == 2); |
1339 | assert(m->has_wide == 1 ? nfa->streamStateSize == 4 |
1340 | : nfa->streamStateSize == 2); |
1341 | |
1342 | assert(ISALIGNED_N(dest, 2)); |
1343 | *(u16 *)dest = unaligned_load_u16(src); |
1344 | |
1345 | // new byte |
1346 | if (m->has_wide) { |
1347 | *((u16 *)dest + 1) = unaligned_load_u16((const u16 *)src + 1); |
1348 | } |
1349 | return 0; |
1350 | } |
1351 | |