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 | /** \file |
30 | \brief Declarations for the main NFA engine types and structures. |
31 | */ |
32 | #ifndef NFA_INTERNAL_H |
33 | #define NFA_INTERNAL_H |
34 | |
35 | #ifdef __cplusplus |
36 | extern "C" |
37 | { |
38 | #endif |
39 | |
40 | #include "ue2common.h" |
41 | |
42 | // Constants |
43 | |
44 | #define MO_INVALID_IDX 0xffffffff /**< index meaning value is invalid */ |
45 | |
46 | // Flags (used in NFA::flags) |
47 | |
48 | #define NFA_ACCEPTS_EOD 1U /**< can produce matches on EOD. */ |
49 | #define NFA_ZOMBIE 2U /**< supports zombies */ |
50 | |
51 | // Common data structures for NFAs |
52 | |
53 | enum NFAEngineType { |
54 | LIMEX_NFA_32, |
55 | LIMEX_NFA_64, |
56 | LIMEX_NFA_128, |
57 | LIMEX_NFA_256, |
58 | LIMEX_NFA_384, |
59 | LIMEX_NFA_512, |
60 | MCCLELLAN_NFA_8, /**< magic pseudo nfa */ |
61 | MCCLELLAN_NFA_16, /**< magic pseudo nfa */ |
62 | GOUGH_NFA_8, /**< magic pseudo nfa */ |
63 | GOUGH_NFA_16, /**< magic pseudo nfa */ |
64 | MPV_NFA, /**< magic pseudo nfa */ |
65 | LBR_NFA_DOT, /**< magic pseudo nfa */ |
66 | LBR_NFA_VERM, /**< magic pseudo nfa */ |
67 | LBR_NFA_NVERM, /**< magic pseudo nfa */ |
68 | LBR_NFA_SHUF, /**< magic pseudo nfa */ |
69 | LBR_NFA_TRUF, /**< magic pseudo nfa */ |
70 | CASTLE_NFA, /**< magic pseudo nfa */ |
71 | SHENG_NFA, /**< magic pseudo nfa */ |
72 | TAMARAMA_NFA, /**< magic nfa container */ |
73 | MCSHENG_NFA_8, /**< magic pseudo nfa */ |
74 | MCSHENG_NFA_16, /**< magic pseudo nfa */ |
75 | /** \brief bogus NFA - not used */ |
76 | INVALID_NFA |
77 | }; |
78 | |
79 | /** \brief header for the NFA implementation. */ |
80 | struct ALIGN_CL_DIRECTIVE NFA { |
81 | u32 flags; |
82 | |
83 | /** \brief The size in bytes of the NFA engine. The engine is |
84 | * serialized to the extent that copying length bytes back into a |
85 | * 16-byte aligned memory location yields a structure that has the same |
86 | * behaviour as the original engine. */ |
87 | u32 length; |
88 | |
89 | /** \brief Active implementation used by this NFAEngineType */ |
90 | u8 type; |
91 | |
92 | u8 rAccelType; |
93 | u8 rAccelOffset; |
94 | u8 maxBiAnchoredWidth; /**< if non zero, max width of the block */ |
95 | |
96 | union { |
97 | u8 c; |
98 | u16 dc; |
99 | u8 array[2]; |
100 | } rAccelData; |
101 | |
102 | u32 queueIndex; /**< index of the associated queue in scratch */ |
103 | |
104 | /** \brief The number of valid positions/states for this NFA. Debug only */ |
105 | u32 nPositions; |
106 | |
107 | /** \brief Size of the state required in scratch space. |
108 | * |
109 | * This state has less strict size requirements (as it doesn't go in stream |
110 | * state) and does not persist between stream writes. |
111 | */ |
112 | u32 scratchStateSize; |
113 | |
114 | /** \brief Size of the state required in stream state. |
115 | * |
116 | * This encompasses all state stored by the engine that must persist between |
117 | * stream writes. */ |
118 | u32 streamStateSize; |
119 | |
120 | u32 maxWidth; /**< longest possible match in this NFA, 0 if unbounded */ |
121 | u32 minWidth; /**< minimum bytes required to match this NFA */ |
122 | u32 maxOffset; /**< non zero: maximum offset this pattern can match at */ |
123 | |
124 | /* Note: implementation (e.g. a LimEx) directly follows struct in memory */ |
125 | } ; |
126 | |
127 | // Accessor macro for the implementation NFA: we do things this way to avoid |
128 | // type-punning warnings. |
129 | #define getImplNfa(nfa) \ |
130 | ((const void *)((const char *)(nfa) + sizeof(struct NFA))) |
131 | |
132 | // Non-const version of the above, used at compile time. |
133 | #define getMutableImplNfa(nfa) ((char *)(nfa) + sizeof(struct NFA)) |
134 | |
135 | static really_inline u32 nfaAcceptsEod(const struct NFA *nfa) { |
136 | return nfa->flags & NFA_ACCEPTS_EOD; |
137 | } |
138 | |
139 | static really_inline u32 nfaSupportsZombie(const struct NFA *nfa) { |
140 | return nfa->flags & NFA_ZOMBIE; |
141 | } |
142 | |
143 | /** \brief True if the given type (from NFA::type) is a McClellan DFA. */ |
144 | static really_inline int isMcClellanType(u8 t) { |
145 | return t == MCCLELLAN_NFA_8 || t == MCCLELLAN_NFA_16; |
146 | } |
147 | |
148 | /** \brief True if the given type (from NFA::type) is a Sheng-McClellan hybrid |
149 | * DFA. */ |
150 | static really_inline int isShengMcClellanType(u8 t) { |
151 | return t == MCSHENG_NFA_8 || t == MCSHENG_NFA_16; |
152 | } |
153 | |
154 | /** \brief True if the given type (from NFA::type) is a Gough DFA. */ |
155 | static really_inline int isGoughType(u8 t) { |
156 | return t == GOUGH_NFA_8 || t == GOUGH_NFA_16; |
157 | } |
158 | |
159 | /** \brief True if the given type (from NFA::type) is a Sheng DFA. */ |
160 | static really_inline int isShengType(u8 t) { |
161 | return t == SHENG_NFA; |
162 | } |
163 | |
164 | /** |
165 | * \brief True if the given type (from NFA::type) is a McClellan, Gough or |
166 | * Sheng DFA. |
167 | */ |
168 | static really_inline int isDfaType(u8 t) { |
169 | return isMcClellanType(t) || isGoughType(t) || isShengType(t) |
170 | || isShengMcClellanType(t); |
171 | } |
172 | |
173 | static really_inline int isBigDfaType(u8 t) { |
174 | return t == MCCLELLAN_NFA_16 || t == MCSHENG_NFA_16 || t == GOUGH_NFA_16; |
175 | } |
176 | |
177 | static really_inline int isSmallDfaType(u8 t) { |
178 | return isDfaType(t) && !isBigDfaType(t); |
179 | } |
180 | |
181 | /** \brief True if the given type (from NFA::type) is an NFA. */ |
182 | static really_inline int isNfaType(u8 t) { |
183 | switch (t) { |
184 | case LIMEX_NFA_32: |
185 | case LIMEX_NFA_64: |
186 | case LIMEX_NFA_128: |
187 | case LIMEX_NFA_256: |
188 | case LIMEX_NFA_384: |
189 | case LIMEX_NFA_512: |
190 | return 1; |
191 | default: |
192 | break; |
193 | } |
194 | return 0; |
195 | } |
196 | |
197 | /** \brief True if the given type (from NFA::type) is an LBR. */ |
198 | static really_inline |
199 | int isLbrType(u8 t) { |
200 | return t == LBR_NFA_DOT || t == LBR_NFA_VERM || t == LBR_NFA_NVERM || |
201 | t == LBR_NFA_SHUF || t == LBR_NFA_TRUF; |
202 | } |
203 | |
204 | /** \brief True if the given type (from NFA::type) is a container engine. */ |
205 | static really_inline |
206 | int isContainerType(u8 t) { |
207 | return t == TAMARAMA_NFA; |
208 | } |
209 | |
210 | static really_inline |
211 | int isMultiTopType(u8 t) { |
212 | return !isDfaType(t) && !isLbrType(t); |
213 | } |
214 | |
215 | /** Macros used in place of unimplemented NFA API functions for a given |
216 | * engine. */ |
217 | #if !defined(_WIN32) |
218 | |
219 | /* Use for functions that return an integer. */ |
220 | #define NFA_API_NO_IMPL(...) \ |
221 | ({ \ |
222 | assert(!"not implemented for this engine!"); \ |
223 | 0; /* return value, for places that need it */ \ |
224 | }) |
225 | |
226 | /* Use for _zombie_status functions. */ |
227 | #define NFA_API_ZOMBIE_NO_IMPL(...) \ |
228 | ({ \ |
229 | assert(!"not implemented for this engine!"); \ |
230 | NFA_ZOMBIE_NO; \ |
231 | }) |
232 | |
233 | #else |
234 | |
235 | /* Simpler implementation for compilers that don't like the GCC extension used |
236 | * above. */ |
237 | #define NFA_API_NO_IMPL(...) 0 |
238 | #define NFA_API_ZOMBIE_NO_IMPL(...) NFA_ZOMBIE_NO |
239 | |
240 | #endif |
241 | |
242 | #ifdef __cplusplus |
243 | } |
244 | #endif |
245 | |
246 | #endif |
247 | |