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
44using namespace std;
45
46namespace ue2 {
47
48static const unsigned int MAX_ACCEL_OFFSET = 16;
49static const unsigned int MAX_SHUFTI_WIDTH = 240;
50
51static
52size_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
73static
74bool 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
214static
215bool 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
331static
332void 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
353static
354bool 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
372static
373void 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
459void 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