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
36extern "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
53enum 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. */
80struct 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
135static really_inline u32 nfaAcceptsEod(const struct NFA *nfa) {
136 return nfa->flags & NFA_ACCEPTS_EOD;
137}
138
139static 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. */
144static 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. */
150static 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. */
155static 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. */
160static 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 */
168static really_inline int isDfaType(u8 t) {
169 return isMcClellanType(t) || isGoughType(t) || isShengType(t)
170 || isShengMcClellanType(t);
171}
172
173static really_inline int isBigDfaType(u8 t) {
174 return t == MCCLELLAN_NFA_16 || t == MCSHENG_NFA_16 || t == GOUGH_NFA_16;
175}
176
177static 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. */
182static 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. */
198static really_inline
199int 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. */
205static really_inline
206int isContainerType(u8 t) {
207 return t == TAMARAMA_NFA;
208}
209
210static really_inline
211int 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