1 | /* |
2 | * Copyright (c) 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 "rose_build_lit_accel.h" |
30 | |
31 | #include "grey.h" |
32 | #include "ue2common.h" |
33 | #include "hwlm/hwlm_build.h" |
34 | #include "hwlm/hwlm_internal.h" |
35 | #include "hwlm/hwlm_literal.h" |
36 | #include "nfa/accel.h" |
37 | #include "nfa/shufticompile.h" |
38 | #include "nfa/trufflecompile.h" |
39 | #include "util/compare.h" |
40 | #include "util/dump_charclass.h" |
41 | #include "util/ue2string.h" |
42 | #include "util/verify_types.h" |
43 | |
44 | using namespace std; |
45 | |
46 | namespace ue2 { |
47 | |
48 | static const unsigned int MAX_ACCEL_OFFSET = 16; |
49 | static const unsigned int MAX_SHUFTI_WIDTH = 240; |
50 | |
51 | static |
52 | size_t mask_overhang(const AccelString &lit) { |
53 | size_t msk_true_size = lit.msk.size(); |
54 | assert(msk_true_size <= HWLM_MASKLEN); |
55 | assert(HWLM_MASKLEN <= MAX_ACCEL_OFFSET); |
56 | for (u8 c : lit.msk) { |
57 | if (!c) { |
58 | msk_true_size--; |
59 | } else { |
60 | break; |
61 | } |
62 | } |
63 | |
64 | if (lit.s.length() >= msk_true_size) { |
65 | return 0; |
66 | } |
67 | |
68 | /* only short literals should be able to have a mask which overhangs */ |
69 | assert(lit.s.length() < MAX_ACCEL_OFFSET); |
70 | return msk_true_size - lit.s.length(); |
71 | } |
72 | |
73 | static |
74 | bool findDVerm(const vector<const AccelString *> &lits, AccelAux *aux) { |
75 | const AccelString &first = *lits.front(); |
76 | |
77 | struct candidate { |
78 | candidate(void) |
79 | : c1(0), c2(0), max_offset(0), b5insens(false), valid(false) {} |
80 | candidate(const AccelString &base, u32 offset) |
81 | : c1(base.s[offset]), c2(base.s[offset + 1]), max_offset(0), |
82 | b5insens(false), valid(true) {} |
83 | char c1; |
84 | char c2; |
85 | u32 max_offset; |
86 | bool b5insens; |
87 | bool valid; |
88 | |
89 | bool operator>(const candidate &other) const { |
90 | if (!valid) { |
91 | return false; |
92 | } |
93 | |
94 | if (!other.valid) { |
95 | return true; |
96 | } |
97 | |
98 | if (other.cdiffers() && !cdiffers()) { |
99 | return false; |
100 | } |
101 | |
102 | if (!other.cdiffers() && cdiffers()) { |
103 | return true; |
104 | } |
105 | |
106 | if (!other.b5insens && b5insens) { |
107 | return false; |
108 | } |
109 | |
110 | if (other.b5insens && !b5insens) { |
111 | return true; |
112 | } |
113 | |
114 | if (max_offset > other.max_offset) { |
115 | return false; |
116 | } |
117 | |
118 | return true; |
119 | } |
120 | |
121 | bool cdiffers(void) const { |
122 | if (!b5insens) { |
123 | return c1 != c2; |
124 | } |
125 | return (c1 & CASE_CLEAR) != (c2 & CASE_CLEAR); |
126 | } |
127 | }; |
128 | |
129 | candidate best; |
130 | |
131 | for (u32 i = 0; i < MIN(MAX_ACCEL_OFFSET, first.s.length()) - 1; i++) { |
132 | candidate curr(first, i); |
133 | |
134 | /* check to see if this pair appears in each string */ |
135 | for (const auto &lit_ptr : lits) { |
136 | const AccelString &lit = *lit_ptr; |
137 | if (lit.nocase && (ourisalpha(curr.c1) || ourisalpha(curr.c2))) { |
138 | curr.b5insens = true; /* no choice but to be case insensitive */ |
139 | } |
140 | |
141 | bool found = false; |
142 | bool found_nc = false; |
143 | for (u32 j = 0; |
144 | !found && j < MIN(MAX_ACCEL_OFFSET, lit.s.length()) - 1; j++) { |
145 | found |= curr.c1 == lit.s[j] && curr.c2 == lit.s[j + 1]; |
146 | found_nc |= (curr.c1 & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR) |
147 | && (curr.c2 & CASE_CLEAR) == (lit.s[j + 1] & CASE_CLEAR); |
148 | |
149 | if (curr.b5insens) { |
150 | found = found_nc; |
151 | } |
152 | } |
153 | |
154 | if (!curr.b5insens && !found && found_nc) { |
155 | curr.b5insens = true; |
156 | found = true; |
157 | } |
158 | |
159 | if (!found) { |
160 | goto next_candidate; |
161 | } |
162 | } |
163 | |
164 | /* check to find the max offset where this appears */ |
165 | for (const auto &lit_ptr : lits) { |
166 | const AccelString &lit = *lit_ptr; |
167 | for (u32 j = 0; j < MIN(MAX_ACCEL_OFFSET, lit.s.length()) - 1; |
168 | j++) { |
169 | bool found = false; |
170 | if (curr.b5insens) { |
171 | found = (curr.c1 & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR) |
172 | && (curr.c2 & CASE_CLEAR) == (lit.s[j + 1] & CASE_CLEAR); |
173 | } else { |
174 | found = curr.c1 == lit.s[j] && curr.c2 == lit.s[j + 1]; |
175 | } |
176 | |
177 | if (found) { |
178 | assert(j + mask_overhang(lit) <= MAX_ACCEL_OFFSET); |
179 | ENSURE_AT_LEAST(&curr.max_offset, j + mask_overhang(lit)); |
180 | break; |
181 | } |
182 | } |
183 | } |
184 | |
185 | if (curr > best) { |
186 | best = curr; |
187 | } |
188 | |
189 | next_candidate:; |
190 | } |
191 | |
192 | if (!best.valid) { |
193 | return false; |
194 | } |
195 | |
196 | aux->dverm.offset = verify_u8(best.max_offset); |
197 | |
198 | if (!best.b5insens) { |
199 | aux->dverm.accel_type = ACCEL_DVERM; |
200 | aux->dverm.c1 = best.c1; |
201 | aux->dverm.c2 = best.c2; |
202 | DEBUG_PRINTF("built dverm for %02hhx%02hhx\n" , |
203 | aux->dverm.c1, aux->dverm.c2); |
204 | } else { |
205 | aux->dverm.accel_type = ACCEL_DVERM_NOCASE; |
206 | aux->dverm.c1 = best.c1 & CASE_CLEAR; |
207 | aux->dverm.c2 = best.c2 & CASE_CLEAR; |
208 | DEBUG_PRINTF("built dverm nc for %02hhx%02hhx\n" , |
209 | aux->dverm.c1, aux->dverm.c2); |
210 | } |
211 | return true; |
212 | } |
213 | |
214 | static |
215 | bool findSVerm(const vector<const AccelString *> &lits, AccelAux *aux) { |
216 | const AccelString &first = *lits.front(); |
217 | |
218 | struct candidate { |
219 | candidate(void) |
220 | : c(0), max_offset(0), b5insens(false), valid(false) {} |
221 | candidate(const AccelString &base, u32 offset) |
222 | : c(base.s[offset]), max_offset(0), |
223 | b5insens(false), valid(true) {} |
224 | char c; |
225 | u32 max_offset; |
226 | bool b5insens; |
227 | bool valid; |
228 | |
229 | bool operator>(const candidate &other) const { |
230 | if (!valid) { |
231 | return false; |
232 | } |
233 | |
234 | if (!other.valid) { |
235 | return true; |
236 | } |
237 | |
238 | if (!other.b5insens && b5insens) { |
239 | return false; |
240 | } |
241 | |
242 | if (other.b5insens && !b5insens) { |
243 | return true; |
244 | } |
245 | |
246 | if (max_offset > other.max_offset) { |
247 | return false; |
248 | } |
249 | |
250 | return true; |
251 | } |
252 | }; |
253 | |
254 | candidate best; |
255 | |
256 | for (u32 i = 0; i < MIN(MAX_ACCEL_OFFSET, first.s.length()); i++) { |
257 | candidate curr(first, i); |
258 | |
259 | /* check to see if this pair appears in each string */ |
260 | for (const auto &lit_ptr : lits) { |
261 | const AccelString &lit = *lit_ptr; |
262 | if (lit.nocase && ourisalpha(curr.c)) { |
263 | curr.b5insens = true; /* no choice but to be case insensitive */ |
264 | } |
265 | |
266 | bool found = false; |
267 | bool found_nc = false; |
268 | for (u32 j = 0; |
269 | !found && j < MIN(MAX_ACCEL_OFFSET, lit.s.length()); j++) { |
270 | found |= curr.c == lit.s[j]; |
271 | found_nc |= (curr.c & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR); |
272 | |
273 | if (curr.b5insens) { |
274 | found = found_nc; |
275 | } |
276 | } |
277 | |
278 | if (!curr.b5insens && !found && found_nc) { |
279 | curr.b5insens = true; |
280 | found = true; |
281 | } |
282 | |
283 | if (!found) { |
284 | goto next_candidate; |
285 | } |
286 | } |
287 | |
288 | /* check to find the max offset where this appears */ |
289 | for (const auto &lit_ptr : lits) { |
290 | const AccelString &lit = *lit_ptr; |
291 | for (u32 j = 0; j < MIN(MAX_ACCEL_OFFSET, lit.s.length()); j++) { |
292 | bool found = false; |
293 | if (curr.b5insens) { |
294 | found = (curr.c & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR); |
295 | } else { |
296 | found = curr.c == lit.s[j]; |
297 | } |
298 | |
299 | if (found) { |
300 | assert(j + mask_overhang(lit) <= MAX_ACCEL_OFFSET); |
301 | ENSURE_AT_LEAST(&curr.max_offset, j + mask_overhang(lit)); |
302 | } |
303 | } |
304 | } |
305 | |
306 | if (curr > best) { |
307 | best = curr; |
308 | } |
309 | |
310 | next_candidate:; |
311 | } |
312 | |
313 | if (!best.valid) { |
314 | return false; |
315 | } |
316 | |
317 | if (!best.b5insens) { |
318 | aux->verm.accel_type = ACCEL_VERM; |
319 | aux->verm.c = best.c; |
320 | DEBUG_PRINTF("built verm for %02hhx\n" , aux->verm.c); |
321 | } else { |
322 | aux->verm.accel_type = ACCEL_VERM_NOCASE; |
323 | aux->verm.c = best.c & CASE_CLEAR; |
324 | DEBUG_PRINTF("built verm nc for %02hhx\n" , aux->verm.c); |
325 | } |
326 | aux->verm.offset = verify_u8(best.max_offset); |
327 | |
328 | return true; |
329 | } |
330 | |
331 | static |
332 | void filterLits(const vector<AccelString> &lits, hwlm_group_t expected_groups, |
333 | vector<const AccelString *> *filtered_lits, u32 *min_len) { |
334 | *min_len = MAX_ACCEL_OFFSET; |
335 | |
336 | for (const auto &lit : lits) { |
337 | if (!(lit.groups & expected_groups)) { |
338 | continue; |
339 | } |
340 | |
341 | const size_t lit_len = lit.s.length(); |
342 | if (lit_len < *min_len) { |
343 | *min_len = verify_u32(lit_len); |
344 | } |
345 | |
346 | DEBUG_PRINTF("lit: '%s', nocase=%d, groups=0x%llx\n" , |
347 | escapeString(lit.s).c_str(), lit.nocase ? 1 : 0, |
348 | lit.groups); |
349 | filtered_lits->push_back(&lit); |
350 | } |
351 | } |
352 | |
353 | static |
354 | bool litGuardedByCharReach(const CharReach &cr, const AccelString &lit, |
355 | u32 max_offset) { |
356 | for (u32 i = 0; i <= max_offset && i < lit.s.length(); i++) { |
357 | unsigned char c = lit.s[i]; |
358 | if (lit.nocase) { |
359 | if (cr.test(mytoupper(c)) && cr.test(mytolower(c))) { |
360 | return true; |
361 | } |
362 | } else { |
363 | if (cr.test(c)) { |
364 | return true; |
365 | } |
366 | } |
367 | } |
368 | |
369 | return false; |
370 | } |
371 | |
372 | static |
373 | void findForwardAccelScheme(const vector<AccelString> &lits, |
374 | hwlm_group_t expected_groups, AccelAux *aux) { |
375 | DEBUG_PRINTF("building accel expected=%016llx\n" , expected_groups); |
376 | u32 min_len = MAX_ACCEL_OFFSET; |
377 | vector<const AccelString *> filtered_lits; |
378 | |
379 | filterLits(lits, expected_groups, &filtered_lits, &min_len); |
380 | if (filtered_lits.empty()) { |
381 | return; |
382 | } |
383 | |
384 | if (findDVerm(filtered_lits, aux) |
385 | || findSVerm(filtered_lits, aux)) { |
386 | return; |
387 | } |
388 | |
389 | /* look for shufti/truffle */ |
390 | |
391 | vector<CharReach> reach(MAX_ACCEL_OFFSET, CharReach()); |
392 | for (const auto &lit : lits) { |
393 | if (!(lit.groups & expected_groups)) { |
394 | continue; |
395 | } |
396 | |
397 | u32 overhang = mask_overhang(lit); |
398 | for (u32 i = 0; i < overhang; i++) { |
399 | /* this offset overhangs the start of the real literal; look at the |
400 | * msk/cmp */ |
401 | for (u32 j = 0; j < N_CHARS; j++) { |
402 | if ((j & lit.msk[i]) == lit.cmp[i]) { |
403 | reach[i].set(j); |
404 | } |
405 | } |
406 | } |
407 | for (u32 i = overhang; i < MAX_ACCEL_OFFSET; i++) { |
408 | CharReach &reach_i = reach[i]; |
409 | u32 i_effective = i - overhang; |
410 | |
411 | if (litGuardedByCharReach(reach_i, lit, i_effective)) { |
412 | continue; |
413 | } |
414 | unsigned char c = i_effective < lit.s.length() ? lit.s[i_effective] |
415 | : lit.s.back(); |
416 | if (lit.nocase) { |
417 | reach_i.set(mytoupper(c)); |
418 | reach_i.set(mytolower(c)); |
419 | } else { |
420 | reach_i.set(c); |
421 | } |
422 | } |
423 | } |
424 | |
425 | u32 min_count = ~0U; |
426 | u32 min_offset = ~0U; |
427 | for (u32 i = 0; i < MAX_ACCEL_OFFSET; i++) { |
428 | size_t count = reach[i].count(); |
429 | DEBUG_PRINTF("offset %u is %s (reach %zu)\n" , i, |
430 | describeClass(reach[i]).c_str(), count); |
431 | if (count < min_count) { |
432 | min_count = (u32)count; |
433 | min_offset = i; |
434 | } |
435 | } |
436 | |
437 | if (min_count > MAX_SHUFTI_WIDTH) { |
438 | DEBUG_PRINTF("FAIL: min shufti with %u chars is too wide\n" , min_count); |
439 | return; |
440 | } |
441 | |
442 | const CharReach &cr = reach[min_offset]; |
443 | if (-1 != |
444 | shuftiBuildMasks(cr, (u8 *)&aux->shufti.lo, (u8 *)&aux->shufti.hi)) { |
445 | DEBUG_PRINTF("built shufti for %s (%zu chars, offset %u)\n" , |
446 | describeClass(cr).c_str(), cr.count(), min_offset); |
447 | aux->shufti.accel_type = ACCEL_SHUFTI; |
448 | aux->shufti.offset = verify_u8(min_offset); |
449 | return; |
450 | } |
451 | |
452 | truffleBuildMasks(cr, (u8 *)&aux->truffle.mask1, (u8 *)&aux->truffle.mask2); |
453 | DEBUG_PRINTF("built truffle for %s (%zu chars, offset %u)\n" , |
454 | describeClass(cr).c_str(), cr.count(), min_offset); |
455 | aux->truffle.accel_type = ACCEL_TRUFFLE; |
456 | aux->truffle.offset = verify_u8(min_offset); |
457 | } |
458 | |
459 | void buildForwardAccel(HWLM *h, const vector<AccelString> &lits, |
460 | hwlm_group_t expected_groups) { |
461 | findForwardAccelScheme(lits, expected_groups, &h->accel1); |
462 | findForwardAccelScheme(lits, HWLM_ALL_GROUPS, &h->accel0); |
463 | |
464 | h->accel1_groups = expected_groups; |
465 | } |
466 | |
467 | } // namespace ue2 |
468 | |