1/*
2 * Copyright (c) 2015, 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/** \file
30 * \brief Bounded Repeat implementation for the LimEx NFA.
31 */
32
33#ifndef LIMEX_RING_H
34#define LIMEX_RING_H
35
36#include "ue2common.h"
37#include "repeat.h"
38
39#ifdef __cplusplus
40extern "C"
41{
42#endif
43
44/** \brief Return values from \ref processTugTrigger, used to provide feedback
45 * about a bounded repeat to the caller.
46 *
47 * TRIGGER_FAIL does not get cached as we prefer to use TRIGGER_STALE which
48 * allows the exception to squash the cyclic state as well. */
49enum TriggerResult {
50 TRIGGER_FAIL, /**< no valid matches, but history still valid */
51 TRIGGER_SUCCESS, /**< valid match found */
52 TRIGGER_STALE, /**< no valid matches and history is invalid (stale) */
53 TRIGGER_SUCCESS_CACHE /**< valid match found; can cache as the repeat has no
54 upper bound. */
55};
56
57/** \brief Handle a TUG trigger: given an \p offset, returns whether a repeat
58 * matches or not. */
59static really_inline
60enum TriggerResult processTugTrigger(const struct RepeatInfo *info,
61 const union RepeatControl *ctrl,
62 const char *state, u64a offset) {
63 DEBUG_PRINTF("tug trigger, %s history, repeat={%u,%u}, offset=%llu, "
64 "ctrl=%p, state=%p\n",
65 repeatTypeName(info->type), info->repeatMin, info->repeatMax,
66 offset, ctrl, state);
67
68 assert(ISALIGNED(ctrl));
69
70 enum RepeatMatch rv = repeatHasMatch(info, ctrl, state, offset);
71 switch (rv) {
72 case REPEAT_NOMATCH:
73 return TRIGGER_FAIL;
74 case REPEAT_STALE:
75 return TRIGGER_STALE;
76 case REPEAT_MATCH:
77 if (info->repeatMax == REPEAT_INF) {
78 // {N,} repeats can be cached.
79 return TRIGGER_SUCCESS_CACHE;
80 } else {
81 return TRIGGER_SUCCESS;
82 }
83 }
84
85 assert(0); // unreachable
86 return TRIGGER_FAIL;
87}
88
89/** \brief Handle a POS trigger: stores a top in the repeat. */
90static really_inline
91void processPosTrigger(const struct RepeatInfo *info, union RepeatControl *ctrl,
92 char *state, u64a offset, char is_alive) {
93 DEBUG_PRINTF("pos trigger, %s history, repeat={%u,%u}, offset=%llu, "
94 "is_alive=%d\n", repeatTypeName(info->type),
95 info->repeatMin, info->repeatMax, offset, is_alive);
96
97 assert(ISALIGNED(ctrl));
98
99 repeatStore(info, ctrl, state, offset, is_alive);
100}
101
102#ifdef __cplusplus
103}
104#endif
105
106#endif
107