1 | /* |
2 | * Copyright (c) 2015-2017, 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 | This file provides the internal structures and definitions required for the |
31 | real NFAs (aka limex NFAs ); |
32 | |
33 | Limex NFAs now have variable length in memory. They look like this: |
34 | |
35 | LimExNFA structure |
36 | Fixed length, e.g. LimExNFA256. |
37 | Reachability table |
38 | Variable length array of state bitvectors, mapped into by |
39 | NFACommonXXX.reachMap. |
40 | Tops |
41 | Variable length array of state bitvectors, used for TOP_N events. |
42 | Acceleration structures |
43 | Variable length array of AccelAux structs. |
44 | Accepts |
45 | Variable length array of NFAAccept structs. |
46 | EOD Accepts |
47 | Variable length array of NFAAccept structs. |
48 | Exceptions |
49 | Variable length array of NFAExceptionXXX structs. |
50 | Repeat Structure Offsets |
51 | Array of u32 offsets that point at each "Repeat Structure" (below) |
52 | Repeat Structures |
53 | Variable length repeat structures, addressed via |
54 | NFAException32::repeatOffset etc. |
55 | |
56 | The state associated with the NFA is split into: |
57 | |
58 | -# The "traditional" NFA state as a bitvector. This is stored in the |
59 | first N bytes of the state space (length given in |
60 | NFACommonXXX.stateSize), and may be stored shrunk to CEIL(stateSize/8) |
61 | or compressed. If it is stored compressed, than the |
62 | LIMEX_FLAG_COMPRESS_STATE flag is set in NFACommonXXX.flags. |
63 | -# Extended NFA state, only used in some LimEx NFAs. This consists of a |
64 | variable length array of LimExNFAExtendedState structures, each with |
65 | pointers to a packed list of mmbit structures that follows them. Only |
66 | present when used. |
67 | |
68 | The value of NFA.stateSize gives the total state size in bytes (the sum of |
69 | all the above). |
70 | |
71 | Number of shifts should be always greater or equal to 1 |
72 | Number of shifts 0 means that no appropriate NFA engine was found. |
73 | |
74 | */ |
75 | |
76 | #ifndef LIMEX_INTERNAL_H |
77 | #define LIMEX_INTERNAL_H |
78 | |
79 | #include "nfa_internal.h" |
80 | #include "repeat_internal.h" |
81 | |
82 | // Constants |
83 | #define MAX_SHIFT_COUNT 8 /**< largest number of shifts used by a LimEx NFA */ |
84 | #define MAX_SHIFT_AMOUNT 16 /**< largest shift amount used by a LimEx NFA */ |
85 | |
86 | #define LIMEX_FLAG_COMPRESS_STATE 1 /**< pack state into stream state */ |
87 | #define LIMEX_FLAG_COMPRESS_MASKED 2 /**< use reach mask-based compression */ |
88 | #define LIMEX_FLAG_CANNOT_DIE 4 /**< limex cannot have no states on */ |
89 | |
90 | enum LimExTrigger { |
91 | LIMEX_TRIGGER_NONE = 0, |
92 | LIMEX_TRIGGER_POS = 1, |
93 | LIMEX_TRIGGER_TUG = 2 |
94 | }; |
95 | |
96 | enum LimExSquash { |
97 | LIMEX_SQUASH_NONE = 0, //!< no squash for you! |
98 | LIMEX_SQUASH_CYCLIC = 1, //!< squash due to cyclic state |
99 | LIMEX_SQUASH_TUG = 2, //!< squash due to tug trigger with stale estate |
100 | LIMEX_SQUASH_REPORT = 3 //!< squash when report is raised |
101 | }; |
102 | |
103 | /* uniform looking types for the macros */ |
104 | typedef u8 u_8; |
105 | typedef u16 u_16; |
106 | typedef u32 u_32; |
107 | typedef u64a u_64; |
108 | typedef m128 u_128; |
109 | typedef m256 u_256; |
110 | typedef m384 u_384; |
111 | typedef m512 u_512; |
112 | |
113 | #define CREATE_NFA_LIMEX(size) \ |
114 | struct NFAException##size { \ |
115 | u_##size squash; /**< mask of states to leave on */ \ |
116 | u_##size successors; /**< mask of states to switch on */ \ |
117 | u32 reports; /**< offset to start of reports list, or MO_INVALID_IDX */ \ |
118 | u32 repeatOffset; /**< offset to NFARepeatInfo, or MO_INVALID_IDX */ \ |
119 | u8 hasSquash; /**< from enum LimExSquash */ \ |
120 | u8 trigger; /**< from enum LimExTrigger */ \ |
121 | }; \ |
122 | \ |
123 | struct LimExNFA##size { \ |
124 | u8 reachMap[N_CHARS]; /**< map of char -> entry in reach[] */ \ |
125 | u32 reachSize; /**< number of reach masks */ \ |
126 | u32 accelCount; /**< number of entries in accel table */ \ |
127 | u32 accelTableOffset; /* rel. to start of LimExNFA */ \ |
128 | u32 accelAuxCount; /**< number of entries in aux table */ \ |
129 | u32 accelAuxOffset; /* rel. to start of LimExNFA */ \ |
130 | u32 acceptCount; \ |
131 | u32 acceptOffset; /* rel. to start of LimExNFA */ \ |
132 | u32 acceptEodCount; \ |
133 | u32 acceptEodOffset; /* rel. to start of LimExNFA */ \ |
134 | u32 exceptionCount; \ |
135 | u32 exceptionOffset; /* rel. to start of LimExNFA */ \ |
136 | u32 repeatCount; \ |
137 | u32 repeatOffset; \ |
138 | u32 squashOffset; /* rel. to start of LimExNFA; for accept squashing */ \ |
139 | u32 squashCount; \ |
140 | u32 topCount; \ |
141 | u32 topOffset; /* rel. to start of LimExNFA */ \ |
142 | u32 stateSize; /**< not including extended history */ \ |
143 | u32 flags; \ |
144 | u_##size init; \ |
145 | u_##size initDS; \ |
146 | u_##size accept; /**< mask of accept states */ \ |
147 | u_##size acceptAtEOD; /**< mask of states that accept at EOD */ \ |
148 | u_##size accel; /**< mask of accelerable states */ \ |
149 | u_##size accelPermute; /**< pshufb permute mask (not GPR) */ \ |
150 | u_##size accelCompare; /**< pshufb compare mask (not GPR) */ \ |
151 | u_##size accel_and_friends; /**< mask of accelerable states + likely |
152 | * followers */ \ |
153 | u_##size compressMask; /**< switch off before compress */ \ |
154 | u_##size exceptionMask; \ |
155 | u_##size repeatCyclicMask; /**< also includes tug states */ \ |
156 | u_##size zombieMask; /**< zombie if in any of the set states */ \ |
157 | u_##size shift[MAX_SHIFT_COUNT]; \ |
158 | u32 shiftCount; /**< number of shift masks used */ \ |
159 | u8 shiftAmount[MAX_SHIFT_COUNT]; /**< shift amount for each mask */ \ |
160 | }; |
161 | |
162 | CREATE_NFA_LIMEX(32) |
163 | CREATE_NFA_LIMEX(64) |
164 | CREATE_NFA_LIMEX(128) |
165 | CREATE_NFA_LIMEX(256) |
166 | CREATE_NFA_LIMEX(384) |
167 | CREATE_NFA_LIMEX(512) |
168 | |
169 | /** \brief Structure describing a bounded repeat within the LimEx NFA. |
170 | * |
171 | * This struct is followed in memory by: |
172 | * |
173 | * -# a RepeatInfo structure |
174 | * -# a variable-sized lookup table for REPEAT_SPARSE_OPTIMAL_P repeats |
175 | * -# a TUG mask |
176 | */ |
177 | struct NFARepeatInfo { |
178 | u32 cyclicState; //!< index of this repeat's cyclic state |
179 | u32 ctrlIndex; //!< index of this repeat's control block |
180 | u32 packedCtrlOffset; //!< offset to packed control block in stream state |
181 | u32 stateOffset; //!< offset to repeat state in stream state |
182 | u32 stateSize; //!< total size of packed stream state for this repeat |
183 | u32 tugMaskOffset; //!< offset to tug mask (rel. to NFARepeatInfo) |
184 | }; |
185 | |
186 | struct NFAAccept { |
187 | u8 single_report; //!< If true, 'reports' is report id. |
188 | |
189 | /** |
190 | * \brief If single report is true, this is the report id to fire. |
191 | * Otherwise, it is the offset (relative to the start of the LimExNFA |
192 | * structure) of a list of reports, terminated with MO_INVALID_IDX. |
193 | */ |
194 | u32 reports; |
195 | |
196 | u32 squash; //!< Offset (from LimEx) into squash masks, or MO_INVALID_IDX. |
197 | }; |
198 | |
199 | #endif |
200 | |