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 | #ifndef INFIX_H |
30 | #define INFIX_H |
31 | |
32 | #include "ue2common.h" |
33 | #include "nfa/nfa_api.h" |
34 | #include "nfa/nfa_api_queue.h" |
35 | #include "nfa/nfa_internal.h" |
36 | |
37 | static really_inline |
38 | int infixTooOld(struct mq *q, s64a curr_loc) { |
39 | u32 maxAge = q->nfa->maxWidth; |
40 | |
41 | if (!maxAge) { |
42 | return 0; |
43 | } |
44 | |
45 | return q_last_loc(q) + maxAge < curr_loc; |
46 | } |
47 | |
48 | static really_inline |
49 | int canReduceQueue(const struct mq *q, s64a curr_loc, u32 maxTops, u32 maxAge) { |
50 | u32 qlen = q->end - q->cur; /* includes MQE_START */ |
51 | |
52 | if (maxAge && q->items[q->cur].location + maxAge < curr_loc) { |
53 | return 1; |
54 | } |
55 | |
56 | if (qlen - 1 > maxTops) { |
57 | return 1; |
58 | } |
59 | |
60 | if (qlen - 1 == maxTops |
61 | && q->items[q->cur].location != q->items[q->cur + 1].location) { |
62 | /* we can advance start to the first top location */ |
63 | return 1; |
64 | } |
65 | |
66 | return 0; |
67 | } |
68 | |
69 | /** |
70 | * Removes tops which are known not to affect the final state from the queue. |
71 | * May also reinitialise the engine state if it is unneeded. |
72 | * |
73 | * maxAge is the maximum width of the infix. Any tops/state before this can be |
74 | * ignored. 0 is used to indicate that there is no upper bound on the width of |
75 | * the pattern. |
76 | * |
77 | * maxTops is the maximum number of locations of tops that can affect the top. |
78 | * It is only possible for the last maxTops tops to affect the final state - |
79 | * earlier ones can be safely removed. Also, any state before the max tops may |
80 | * be ignored. |
81 | * |
82 | * This code assumes/requires that there are not multiple tops at the same |
83 | * location in the queue. This code also assumes that it is not a multitop |
84 | * engine. |
85 | */ |
86 | static really_inline |
87 | void reduceInfixQueue(struct mq *q, s64a curr_loc, u32 maxTops, u32 maxAge) { |
88 | assert(q->end > q->cur); |
89 | assert(maxTops); |
90 | u32 qlen = q->end - q->cur; /* includes MQE_START */ |
91 | DEBUG_PRINTF("q=%p, len=%u, maxTops=%u maxAge=%u\n" , q, qlen, maxTops, |
92 | maxAge); |
93 | |
94 | if (!canReduceQueue(q, curr_loc, maxTops, maxAge)) { |
95 | DEBUG_PRINTF("nothing to do\n" ); |
96 | return; |
97 | } |
98 | |
99 | #ifdef DEBUG |
100 | debugQueue(q); |
101 | #endif |
102 | |
103 | char drop_state = qlen - 1 >= maxTops |
104 | || (maxAge && q->items[q->cur].location + maxAge < curr_loc); |
105 | |
106 | LIMIT_TO_AT_MOST(&maxTops, qlen - 1); |
107 | |
108 | // We leave our START where it is, at the front of the queue. |
109 | assert(q->items[q->cur].type == MQE_START); |
110 | |
111 | // We want to shuffle maxQueueLen items from the end of the queue to just |
112 | // after the start, effectively dequeuing old items. We could use memmove |
113 | // for this, but it's probably not a good idea to take the cost of the |
114 | // function call. |
115 | const struct mq_item *src = &q->items[q->cur + qlen - maxTops]; |
116 | |
117 | q->items[0] = q->items[q->cur]; /* shift start event to 0 slot */ |
118 | q->cur = 0; |
119 | q->end = 1; |
120 | struct mq_item *dst = &q->items[1]; |
121 | u32 i = 0; |
122 | if (maxAge) { |
123 | /* any event which is older than maxAge can be dropped */ |
124 | for (; i < maxTops; i++, src++) { |
125 | if (src->location >= curr_loc - maxAge) { |
126 | break; |
127 | } |
128 | } |
129 | } |
130 | |
131 | for (; i < maxTops; i++) { |
132 | *dst = *src; |
133 | src++; |
134 | dst++; |
135 | q->end++; |
136 | } |
137 | |
138 | if (drop_state) { |
139 | /* clear state and shift start up to first top */ |
140 | s64a new_loc; |
141 | if (q->end > 1) { |
142 | new_loc = q->items[1].location; |
143 | } else { |
144 | DEBUG_PRINTF("no tops\n" ); |
145 | new_loc = curr_loc; |
146 | } |
147 | |
148 | DEBUG_PRINTF("advancing start from %lld to %lld\n" , |
149 | q->items[0].location, new_loc); |
150 | assert(new_loc > q->items[0].location); |
151 | q->items[0].location = new_loc; |
152 | nfaQueueInitState(q->nfa, q); |
153 | } |
154 | |
155 | DEBUG_PRINTF("reduced queue to len=%u\n" , q->end - q->cur); |
156 | #ifdef DEBUG |
157 | debugQueue(q); |
158 | #endif |
159 | } |
160 | |
161 | #endif |
162 | |