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 | #include "accel.h" |
30 | #include "accelcompile.h" |
31 | #include "shufticompile.h" |
32 | #include "trufflecompile.h" |
33 | #include "nfagraph/ng_limex_accel.h" /* for constants */ |
34 | #include "util/bitutils.h" |
35 | #include "util/verify_types.h" |
36 | |
37 | #include <map> |
38 | #include <set> |
39 | #include <vector> |
40 | |
41 | using namespace std; |
42 | |
43 | namespace ue2 { |
44 | |
45 | static |
46 | void buildAccelSingle(const AccelInfo &info, AccelAux *aux) { |
47 | assert(aux->accel_type == ACCEL_NONE); |
48 | if (info.single_stops.all()) { |
49 | return; |
50 | } |
51 | |
52 | size_t outs = info.single_stops.count(); |
53 | DEBUG_PRINTF("%zu outs\n" , outs); |
54 | assert(outs && outs < 256); |
55 | u32 offset = info.single_offset; |
56 | |
57 | if (outs == 1) { |
58 | aux->accel_type = ACCEL_VERM; |
59 | aux->verm.offset = offset; |
60 | aux->verm.c = info.single_stops.find_first(); |
61 | DEBUG_PRINTF("building vermicelli caseful for 0x%02hhx\n" , aux->verm.c); |
62 | return; |
63 | } |
64 | |
65 | if (outs == 2 && info.single_stops.isCaselessChar()) { |
66 | aux->accel_type = ACCEL_VERM_NOCASE; |
67 | aux->verm.offset = offset; |
68 | aux->verm.c = info.single_stops.find_first() & CASE_CLEAR; |
69 | DEBUG_PRINTF("building vermicelli caseless for 0x%02hhx\n" , |
70 | aux->verm.c); |
71 | return; |
72 | } |
73 | |
74 | DEBUG_PRINTF("attempting shufti for %zu chars\n" , outs); |
75 | if (-1 != shuftiBuildMasks(info.single_stops, (u8 *)&aux->shufti.lo, |
76 | (u8 *)&aux->shufti.hi)) { |
77 | aux->accel_type = ACCEL_SHUFTI; |
78 | aux->shufti.offset = offset; |
79 | DEBUG_PRINTF("shufti built OK\n" ); |
80 | return; |
81 | } else { |
82 | DEBUG_PRINTF("shufti build failed, falling through\n" ); |
83 | } |
84 | |
85 | if (outs <= ACCEL_MAX_STOP_CHAR) { |
86 | DEBUG_PRINTF("building Truffle for %zu chars\n" , outs); |
87 | aux->accel_type = ACCEL_TRUFFLE; |
88 | aux->truffle.offset = offset; |
89 | truffleBuildMasks(info.single_stops, (u8 *)&aux->truffle.mask1, |
90 | (u8 *)&aux->truffle.mask2); |
91 | return; |
92 | } |
93 | |
94 | DEBUG_PRINTF("unable to accelerate case with %zu outs\n" , outs); |
95 | } |
96 | |
97 | bool buildDvermMask(const flat_set<pair<u8, u8>> &escape_set, u8 *m1_out, |
98 | u8 *m2_out) { |
99 | u8 a1 = 0xff; |
100 | u8 a2 = 0xff; |
101 | u8 b1 = 0xff; |
102 | u8 b2 = 0xff; |
103 | |
104 | for (const auto &e : escape_set) { |
105 | DEBUG_PRINTF("%0hhx %0hhx\n" , e.first, e.second); |
106 | a1 &= e.first; |
107 | b1 &= ~e.first; |
108 | a2 &= e.second; |
109 | b2 &= ~e.second; |
110 | } |
111 | |
112 | u8 m1 = a1 | b1; |
113 | u8 m2 = a2 | b2; |
114 | |
115 | u32 holes1 = 8 - popcount32(m1); |
116 | u32 holes2 = 8 - popcount32(m2); |
117 | |
118 | DEBUG_PRINTF("aaaa %0hhx %0hhx\n" , a1, a2); |
119 | DEBUG_PRINTF("bbbb %0hhx %0hhx\n" , b1, b2); |
120 | DEBUG_PRINTF("mask %0hhx %0hhx\n" , m1, m2); |
121 | |
122 | assert(holes1 <= 8 && holes2 <= 8); |
123 | assert(escape_set.size() <= 1U << (holes1 + holes2)); |
124 | if (escape_set.size() != 1U << (holes1 + holes2)) { |
125 | return false; |
126 | } |
127 | |
128 | if (m1_out) { |
129 | *m1_out = m1; |
130 | } |
131 | if (m2_out) { |
132 | *m2_out = m2; |
133 | } |
134 | |
135 | return true; |
136 | } |
137 | |
138 | static |
139 | bool isCaselessDouble(const flat_set<pair<u8, u8>> &stop) { |
140 | // test for vector containing <A,Z> <A,z> <a,Z> <a,z> |
141 | if (stop.size() != 4) { |
142 | return false; |
143 | } |
144 | const u8 a = stop.begin()->first & CASE_CLEAR; |
145 | const u8 b = stop.begin()->second & CASE_CLEAR; |
146 | |
147 | flat_set<pair<u8, u8>>::const_iterator it, ite; |
148 | for (it = stop.begin(), ite = stop.end(); it != ite; ++it) { |
149 | if ((it->first & CASE_CLEAR) != a || (it->second & CASE_CLEAR) != b) { |
150 | return false; |
151 | } |
152 | } |
153 | |
154 | return true; |
155 | } |
156 | |
157 | static |
158 | void buildAccelDouble(const AccelInfo &info, AccelAux *aux) { |
159 | size_t outs1 = info.double_stop1.count(); |
160 | size_t outs2 = info.double_stop2.size(); |
161 | |
162 | u8 offset = verify_u8(info.double_offset); |
163 | DEBUG_PRINTF("outs1=%zu, outs2=%zu\n" , outs1, outs2); |
164 | |
165 | assert(aux->accel_type == ACCEL_NONE); |
166 | |
167 | if (!outs2) { |
168 | /* no double byte accel available */ |
169 | return; |
170 | } |
171 | |
172 | // double-byte accel |
173 | if (outs1 == 0 && outs2 == 1) { |
174 | aux->accel_type = ACCEL_DVERM; |
175 | aux->dverm.offset = offset; |
176 | aux->dverm.c1 = info.double_stop2.begin()->first; |
177 | aux->dverm.c2 = info.double_stop2.begin()->second; |
178 | DEBUG_PRINTF("building double-vermicelli caseful for 0x%02hhx%02hhx\n" , |
179 | aux->dverm.c1, aux->dverm.c2); |
180 | return; |
181 | } |
182 | |
183 | if (outs1 == 0 && isCaselessDouble(info.double_stop2)) { |
184 | aux->accel_type = ACCEL_DVERM_NOCASE; |
185 | aux->dverm.offset = offset; |
186 | aux->dverm.c1 = info.double_stop2.begin()->first & CASE_CLEAR; |
187 | aux->dverm.c2 = info.double_stop2.begin()->second & CASE_CLEAR; |
188 | DEBUG_PRINTF("building double-vermicelli caseless for 0x%02hhx%02hhx\n" , |
189 | aux->dverm.c1, aux->dverm.c2); |
190 | return; |
191 | } |
192 | |
193 | if (outs1 == 0) { |
194 | u8 m1; |
195 | u8 m2; |
196 | |
197 | if (buildDvermMask(info.double_stop2, &m1, &m2)) { |
198 | aux->accel_type = ACCEL_DVERM_MASKED; |
199 | aux->dverm.offset = offset; |
200 | aux->dverm.c1 = info.double_stop2.begin()->first & m1; |
201 | aux->dverm.c2 = info.double_stop2.begin()->second & m2; |
202 | aux->dverm.m1 = m1; |
203 | aux->dverm.m2 = m2; |
204 | DEBUG_PRINTF("building maskeddouble-vermicelli for 0x%02hhx%02hhx\n" , |
205 | aux->dverm.c1, aux->dverm.c2); |
206 | return; |
207 | } |
208 | } |
209 | |
210 | if (outs1 < outs2 && outs1 <= 2) { // Heuristic from UE-438. |
211 | DEBUG_PRINTF("building double-shufti for %zu one-byte and %zu" |
212 | " two-byte literals\n" , outs1, outs2); |
213 | aux->accel_type = ACCEL_DSHUFTI; |
214 | aux->dshufti.offset = offset; |
215 | if (shuftiBuildDoubleMasks( |
216 | info.double_stop1, info.double_stop2, (u8 *)&aux->dshufti.lo1, |
217 | (u8 *)&aux->dshufti.hi1, (u8 *)&aux->dshufti.lo2, |
218 | (u8 *)&aux->dshufti.hi2)) { |
219 | return; |
220 | } |
221 | } |
222 | |
223 | // drop back to attempt single-byte accel |
224 | DEBUG_PRINTF("dropping back to single-byte acceleration\n" ); |
225 | aux->accel_type = ACCEL_NONE; |
226 | } |
227 | |
228 | bool buildAccelAux(const AccelInfo &info, AccelAux *aux) { |
229 | assert(aux->accel_type == ACCEL_NONE); |
230 | if (info.single_stops.none()) { |
231 | DEBUG_PRINTF("picked red tape\n" ); |
232 | aux->accel_type = ACCEL_RED_TAPE; |
233 | aux->generic.offset = info.single_offset; |
234 | } |
235 | if (aux->accel_type == ACCEL_NONE) { |
236 | buildAccelDouble(info, aux); |
237 | } |
238 | if (aux->accel_type == ACCEL_NONE) { |
239 | buildAccelSingle(info, aux); |
240 | } |
241 | |
242 | assert(aux->accel_type == ACCEL_NONE |
243 | || aux->generic.offset == info.single_offset |
244 | || aux->generic.offset == info.double_offset); |
245 | return aux->accel_type != ACCEL_NONE; |
246 | } |
247 | |
248 | } // namespace ue2 |
249 | |