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 "config.h"
30
31 #include <set>
32
33 #include "gtest/gtest.h"
34 #include "nfa/shufti.h"
35 #include "nfa/shufticompile.h"
36 #include "util/target_info.h"
37
38 using namespace ue2;
39 using std::set;
40 using std::pair;
41 using std::make_pair;
42
TEST(Shufti,BuildMask1)43 TEST(Shufti, BuildMask1) {
44 m128 lomask, himask;
45
46 CharReach chars;
47
48 chars.set('a');
49
50 int ret = shuftiBuildMasks(chars, (u8 *)&lomask, (u8 *)&himask);
51 ASSERT_NE(-1, ret);
52
53 u8 *lo = (u8 *)&lomask;
54 u8 *hi = (u8 *)&himask;
55 for (int i = 0; i < 16; i++) {
56 if (i == 'a' % 16) {
57 ASSERT_EQ(1, lo[i]);
58 } else {
59 ASSERT_EQ(0, lo[i]);
60 }
61
62 if (i == 'a' >> 4) {
63 ASSERT_EQ(1, hi[i]);
64 } else {
65 ASSERT_EQ(0, hi[i]);
66 }
67 }
68 }
69
TEST(Shufti,BuildMask2)70 TEST(Shufti, BuildMask2) {
71 m128 lomask, himask;
72
73 CharReach chars;
74
75 chars.set('a');
76 chars.set('B');
77
78 int ret = shuftiBuildMasks(chars, (u8 *)&lomask, (u8 *)&himask);
79 ASSERT_NE(-1, ret);
80
81 u8 *lo = (u8 *)&lomask;
82 u8 *hi = (u8 *)&himask;
83 ASSERT_TRUE(lo['a' % 16] & hi['a' >> 4]);
84 ASSERT_TRUE(lo['B' % 16] & hi['B' >> 4]);
85 ASSERT_FALSE(lo['a' % 16] & hi['B' >> 4]);
86 ASSERT_FALSE(lo['B' % 16] & hi['a' >> 4]);
87 }
88
TEST(Shufti,BuildMask4)89 TEST(Shufti, BuildMask4) {
90 m128 lomask, himask;
91
92 CharReach chars;
93
94 chars.set('a');
95 chars.set('B');
96 chars.set('A');
97 chars.set('b');
98
99 int ret = shuftiBuildMasks(chars, (u8 *)&lomask, (u8 *)&himask);
100 ASSERT_NE(-1, ret);
101
102 u8 *lo = (u8 *)&lomask;
103 u8 *hi = (u8 *)&himask;
104 ASSERT_TRUE(lo['a' % 16] & hi['a' >> 4]);
105 ASSERT_TRUE(lo['A' % 16] & hi['A' >> 4]);
106 ASSERT_TRUE(lo['b' % 16] & hi['b' >> 4]);
107 ASSERT_TRUE(lo['B' % 16] & hi['B' >> 4]);
108 }
109
TEST(Shufti,ExecNoMatch1)110 TEST(Shufti, ExecNoMatch1) {
111 m128 lo, hi;
112
113 CharReach chars;
114 chars.set('a');
115
116 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
117 ASSERT_NE(-1, ret);
118
119 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
120
121 for (size_t i = 0; i < 32; i++) {
122 const u8 *rv = shuftiExec(lo, hi, (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
123
124 ASSERT_LE(((size_t)t1 + strlen(t1)) & ~0xf, (size_t)rv);
125 }
126 }
127
TEST(Shufti,ExecNoMatch2)128 TEST(Shufti, ExecNoMatch2) {
129 m128 lo, hi;
130
131 CharReach chars;
132 chars.set('a');
133 chars.set('B');
134
135 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
136 ASSERT_NE(-1, ret);
137
138 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
139
140 for (size_t i = 0; i < 16; i++) {
141 const u8 *rv = shuftiExec(lo, hi, (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
142
143 ASSERT_LE(((size_t)t1 + strlen(t1)) & ~0xf, (size_t)rv);
144 }
145 }
146
TEST(Shufti,ExecNoMatch3)147 TEST(Shufti, ExecNoMatch3) {
148 m128 lo, hi;
149
150 CharReach chars;
151 chars.set('V'); /* V = 0x56, e = 0x65 */
152
153 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
154 ASSERT_NE(-1, ret);
155
156 char t1[] = "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
157
158 for (size_t i = 0; i < 16; i++) {
159 const u8 *rv = shuftiExec(lo, hi, (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
160
161 ASSERT_LE(((size_t)t1 + strlen(t1)) & ~0xf, (size_t)rv);
162 }
163 }
164
TEST(Shufti,ExecMatch1)165 TEST(Shufti, ExecMatch1) {
166 m128 lo, hi;
167
168 CharReach chars;
169 chars.set('a');
170
171 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
172 ASSERT_NE(-1, ret);
173
174 /* 0123456789012345678901234567890 */
175 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbabbbbbbbbbbbb";
176
177 for (size_t i = 0; i < 32; i++) {
178 const u8 *rv = shuftiExec(lo, hi, (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
179
180 ASSERT_EQ((size_t)t1 + 33, (size_t)rv);
181 }
182 }
183
TEST(Shufti,ExecMatch2)184 TEST(Shufti, ExecMatch2) {
185 m128 lo, hi;
186
187 CharReach chars;
188 chars.set('a');
189
190 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
191 ASSERT_NE(-1, ret);
192
193 /* 0123456789012345678901234567890 */
194 char t1[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
195
196 for (size_t i = 0; i < 16; i++) {
197 const u8 *rv = shuftiExec(lo, hi, (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
198
199 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
200 }
201 }
202
TEST(Shufti,ExecMatch3)203 TEST(Shufti, ExecMatch3) {
204 m128 lo, hi;
205
206 CharReach chars;
207 chars.set('a');
208 chars.set('B');
209
210 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
211 ASSERT_NE(-1, ret);
212
213 /* 0123456789012345678901234567890 */
214 char t1[] = "bbbbbbbbbbbbbbbbbBaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
215
216 for (size_t i = 0; i < 16; i++) {
217 const u8 *rv = shuftiExec(lo, hi, (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
218
219 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
220 }
221 }
222
TEST(Shufti,ExecMatch4)223 TEST(Shufti, ExecMatch4) {
224 m128 lo, hi;
225
226 CharReach chars;
227 chars.set('a');
228 chars.set('C');
229 chars.set('A');
230 chars.set('c');
231
232 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
233 ASSERT_NE(-1, ret);
234
235 /* 0123456789012345678901234567890 */
236 char t1[] = "bbbbbbbbbbbbbbbbbAaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
237 char t2[] = "bbbbbbbbbbbbbbbbbCaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
238 char t3[] = "bbbbbbbbbbbbbbbbbcaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
239 char t4[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
240
241 for (size_t i = 0; i < 16; i++) {
242 const u8 *rv = shuftiExec(lo, hi, (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
243
244 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
245
246 rv = shuftiExec(lo, hi, (u8 *)t2 + i, (u8 *)t2 + strlen(t1));
247
248 ASSERT_EQ((size_t)t2 + 17, (size_t)rv);
249
250 rv = shuftiExec(lo, hi, (u8 *)t3 + i, (u8 *)t3 + strlen(t3));
251
252 ASSERT_EQ((size_t)t3 + 17, (size_t)rv);
253
254 rv = shuftiExec(lo, hi, (u8 *)t4 + i, (u8 *)t4 + strlen(t4));
255
256 ASSERT_EQ((size_t)t4 + 17, (size_t)rv);
257 }
258 }
259
TEST(Shufti,ExecMatch5)260 TEST(Shufti, ExecMatch5) {
261 m128 lo, hi;
262
263 CharReach chars;
264 chars.set('a');
265
266 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
267 ASSERT_NE(-1, ret);
268
269 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
270
271 for (size_t i = 0; i < 31; i++) {
272 t1[48 - i] = 'a';
273 const u8 *rv = shuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + strlen(t1));
274
275 ASSERT_EQ((size_t)&t1[48 - i], (size_t)rv);
276 }
277 }
278
TEST(DoubleShufti,BuildMask1)279 TEST(DoubleShufti, BuildMask1) {
280 m128 lo1m, hi1m, lo2m, hi2m;
281
282 flat_set<pair<u8, u8>> lits;
283
284 lits.insert(make_pair('a', 'B'));
285
286 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1m, (u8 *)&hi1m,
287 (u8 *)&lo2m, (u8 *)&hi2m);
288 ASSERT_TRUE(ret);
289
290 u8 *lo1 = (u8 *)&lo1m;
291 u8 *lo2 = (u8 *)&lo2m;
292 u8 *hi1 = (u8 *)&hi1m;
293 u8 *hi2 = (u8 *)&hi2m;
294 for (int i = 0; i < 16; i++) {
295 if (i == 'a' % 16) {
296 ASSERT_EQ(254, lo1[i]);
297 } else {
298 ASSERT_EQ(255, lo1[i]);
299 }
300
301 if (i == 'a' >> 4) {
302 ASSERT_EQ(254, hi1[i]);
303 } else {
304 ASSERT_EQ(255, hi1[i]);
305 }
306
307 if (i == 'B' % 16) {
308 ASSERT_EQ(254, lo2[i]);
309 } else {
310 ASSERT_EQ(255, lo2[i]);
311 }
312
313 if (i == 'B' >> 4) {
314 ASSERT_EQ(254, hi2[i]);
315 } else {
316 ASSERT_EQ(255, hi2[i]);
317 }
318 }
319 }
320
TEST(DoubleShufti,BuildMask2)321 TEST(DoubleShufti, BuildMask2) {
322 m128 lo1m, hi1m, lo2m, hi2m;
323
324 flat_set<pair<u8, u8>> lits;
325
326 lits.insert(make_pair('a','z'));
327 lits.insert(make_pair('B','z'));
328
329 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1m, (u8 *)&hi1m,
330 (u8 *)&lo2m, (u8 *)&hi2m);
331 ASSERT_TRUE(ret);
332
333 u8 *lo1 = (u8 *)&lo1m;
334 u8 *lo2 = (u8 *)&lo2m;
335 u8 *hi1 = (u8 *)&hi1m;
336 u8 *hi2 = (u8 *)&hi2m;
337 ASSERT_NE(0xff,
338 lo1['a' % 16] | hi1['a' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
339 ASSERT_NE(0xff,
340 lo1['B' % 16] | hi1['B' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
341 ASSERT_EQ(0xff,
342 lo1['a' % 16] | hi1['B' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
343 ASSERT_EQ(0xff,
344 lo1['B' % 16] | hi1['a' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
345 }
346
TEST(DoubleShufti,BuildMask4)347 TEST(DoubleShufti, BuildMask4) {
348 m128 lo1m, hi1m, lo2m, hi2m;
349
350 flat_set<pair<u8, u8>> lits;
351
352 lits.insert(make_pair('a','z'));
353 lits.insert(make_pair('B','z'));
354 lits.insert(make_pair('A','z'));
355 lits.insert(make_pair('b','z'));
356
357 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1m, (u8 *)&hi1m,
358 (u8 *)&lo2m, (u8 *)&hi2m);
359 ASSERT_TRUE(ret);
360
361 u8 *lo1 = (u8 *)&lo1m;
362 u8 *lo2 = (u8 *)&lo2m;
363 u8 *hi1 = (u8 *)&hi1m;
364 u8 *hi2 = (u8 *)&hi2m;
365 ASSERT_NE(0xff,
366 lo1['a' % 16] | hi1['a' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
367 ASSERT_NE(0xff,
368 lo1['A' % 16] | hi1['A' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
369 ASSERT_NE(0xff,
370 lo1['b' % 16] | hi1['b' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
371 ASSERT_NE(0xff,
372 lo1['B' % 16] | hi1['B' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
373 }
374
TEST(DoubleShufti,BuildMask5)375 TEST(DoubleShufti, BuildMask5) {
376 m128 lo1m, hi1m;
377 m128 lo2m, hi2m;
378
379 flat_set<pair<u8, u8>> lits;
380
381 lits.insert(make_pair('a','z'));
382
383 CharReach bytes;
384 bytes.set('X');
385
386 bool ret = shuftiBuildDoubleMasks(bytes, lits, (u8 *)&lo1m, (u8 *)&hi1m,
387 (u8 *)&lo2m, (u8 *)&hi2m);
388 ASSERT_TRUE(ret);
389
390 u8 *lo1 = (u8 *)&lo1m;
391 u8 *lo2 = (u8 *)&lo2m;
392 u8 *hi1 = (u8 *)&hi1m;
393 u8 *hi2 = (u8 *)&hi2m;
394 ASSERT_NE(0xff,
395 lo1['a' % 16] | hi1['a' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
396 ASSERT_EQ(0xff,
397 lo1['a' % 16] | hi1['a' >> 4] | lo2['X' % 16] | hi2['X' >> 4]);
398 ASSERT_EQ(0xff,
399 lo1['A' % 16] | hi1['A' >> 4] | lo2['X' % 16] | hi2['X' >> 4]);
400 ASSERT_EQ(0xff,
401 lo1['b' % 16] | hi1['b' >> 4] | lo2['X' % 16] | hi2['X' >> 4]);
402 ASSERT_EQ(0xff,
403 lo1['B' % 16] | hi1['B' >> 4] | lo2['X' % 16] | hi2['X' >> 4]);
404 }
405
TEST(DoubleShufti,BuildMask6)406 TEST(DoubleShufti, BuildMask6) {
407 m128 lo1m, hi1m, lo2m, hi2m;
408
409 flat_set<pair<u8, u8>> lits;
410
411 lits.insert(make_pair('a','z'));
412 lits.insert(make_pair('B','z'));
413 lits.insert(make_pair('A','z'));
414 lits.insert(make_pair('b','z'));
415 lits.insert(make_pair('a','y'));
416 lits.insert(make_pair('B','y'));
417 lits.insert(make_pair('A','y'));
418 lits.insert(make_pair('b','y'));
419 lits.insert(make_pair('a','x'));
420 lits.insert(make_pair('B','x'));
421 lits.insert(make_pair('A','x'));
422 lits.insert(make_pair('b','x'));
423
424 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1m, (u8 *)&hi1m,
425 (u8 *)&lo2m, (u8 *)&hi2m);
426 ASSERT_TRUE(ret);
427
428 u8 *lo1 = (u8 *)&lo1m;
429 u8 *lo2 = (u8 *)&lo2m;
430 u8 *hi1 = (u8 *)&hi1m;
431 u8 *hi2 = (u8 *)&hi2m;
432 ASSERT_NE(0xff,
433 lo1['a' % 16] | hi1['a' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
434 ASSERT_NE(0xff,
435 lo1['A' % 16] | hi1['A' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
436 ASSERT_NE(0xff,
437 lo1['b' % 16] | hi1['b' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
438 ASSERT_NE(0xff,
439 lo1['B' % 16] | hi1['B' >> 4] | lo2['z' % 16] | hi2['z' >> 4]);
440 ASSERT_NE(0xff,
441 lo1['a' % 16] | hi1['a' >> 4] | lo2['y' % 16] | hi2['y' >> 4]);
442 ASSERT_NE(0xff,
443 lo1['A' % 16] | hi1['A' >> 4] | lo2['y' % 16] | hi2['y' >> 4]);
444 ASSERT_NE(0xff,
445 lo1['b' % 16] | hi1['b' >> 4] | lo2['y' % 16] | hi2['y' >> 4]);
446 ASSERT_NE(0xff,
447 lo1['B' % 16] | hi1['B' >> 4] | lo2['y' % 16] | hi2['y' >> 4]);
448 ASSERT_NE(0xff,
449 lo1['a' % 16] | hi1['a' >> 4] | lo2['x' % 16] | hi2['x' >> 4]);
450 ASSERT_NE(0xff,
451 lo1['A' % 16] | hi1['A' >> 4] | lo2['x' % 16] | hi2['x' >> 4]);
452 ASSERT_NE(0xff,
453 lo1['b' % 16] | hi1['b' >> 4] | lo2['x' % 16] | hi2['x' >> 4]);
454 ASSERT_NE(0xff,
455 lo1['B' % 16] | hi1['B' >> 4] | lo2['x' % 16] | hi2['x' >> 4]);
456 }
457
TEST(DoubleShufti,BuildMask7)458 TEST(DoubleShufti, BuildMask7) {
459 m128 lo1m, hi1m, lo2m, hi2m;
460
461 flat_set<pair<u8, u8>> lits;
462
463 lits.insert(make_pair('a','b'));
464 lits.insert(make_pair('c','d'));
465 lits.insert(make_pair('e','f'));
466 lits.insert(make_pair('g','h'));
467 lits.insert(make_pair('i','j'));
468 lits.insert(make_pair('k','l'));
469 lits.insert(make_pair('m','n'));
470 lits.insert(make_pair('o','p'));
471 lits.insert(make_pair('q','r'));
472 lits.insert(make_pair('s','t'));
473 lits.insert(make_pair('u','v'));
474 lits.insert(make_pair('w','x'));
475
476 bool rv = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1m, (u8 *)&hi1m,
477 (u8 *)&lo2m, (u8 *)&hi2m);
478 ASSERT_FALSE(rv);
479 }
480
TEST(DoubleShufti,ExecNoMatch1)481 TEST(DoubleShufti, ExecNoMatch1) {
482 m128 lo1, hi1, lo2, hi2;
483
484 flat_set<pair<u8, u8>> lits;
485
486 lits.insert(make_pair('a','b'));
487
488 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
489 (u8 *)&lo2, (u8 *)&hi2);
490 ASSERT_TRUE(ret);
491
492 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
493
494 for (size_t i = 0; i < 16; i++) {
495 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
496 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
497
498 ASSERT_LE(((size_t)t1 + strlen(t1)) & ~0xf, (size_t)rv);
499 }
500 }
501
TEST(DoubleShufti,ExecNoMatch1b)502 TEST(DoubleShufti, ExecNoMatch1b) {
503 m128 lo1, hi1, lo2, hi2;
504
505 flat_set<pair<u8, u8>> lits;
506
507 lits.insert(make_pair('b','a'));
508
509 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
510 (u8 *)&lo2, (u8 *)&hi2);
511 ASSERT_TRUE(ret);
512
513 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
514
515 for (size_t i = 0; i < 16; i++) {
516 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
517 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
518
519 ASSERT_EQ((size_t)t1 + i + 15, (size_t)rv);
520 }
521 }
522
TEST(DoubleShufti,ExecNoMatch2)523 TEST(DoubleShufti, ExecNoMatch2) {
524 m128 lo1, hi1, lo2, hi2;
525
526 flat_set<pair<u8, u8>> lits;
527
528 lits.insert(make_pair('a','b'));
529 lits.insert(make_pair('B','b'));
530
531 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
532 (u8 *)&lo2, (u8 *)&hi2);
533 ASSERT_TRUE(ret);
534
535 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
536
537 for (size_t i = 0; i < 16; i++) {
538 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
539 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
540
541 ASSERT_LE(((size_t)t1 + strlen(t1)) & ~0xf, (size_t)rv);
542 }
543 }
544
TEST(DoubleShufti,ExecNoMatch2b)545 TEST(DoubleShufti, ExecNoMatch2b) {
546 m128 lo1, hi1, lo2, hi2;
547
548 flat_set<pair<u8, u8>> lits;
549
550 lits.insert(make_pair('b','a'));
551 lits.insert(make_pair('b','B'));
552
553 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
554 (u8 *)&lo2, (u8 *)&hi2);
555 ASSERT_TRUE(ret);
556
557 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
558
559 for (size_t i = 0; i < 16; i++) {
560 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2, (u8 *)t1 + i,
561 (u8 *)t1 + strlen(t1));
562
563 ASSERT_EQ((size_t)t1 + i + 15, (size_t)rv);
564 }
565 }
566
TEST(DoubleShufti,ExecNoMatch3)567 TEST(DoubleShufti, ExecNoMatch3) {
568 m128 lo1, hi1, lo2, hi2;
569
570 flat_set<pair<u8, u8>> lits;
571
572 lits.insert(make_pair('V','e'));
573
574 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
575 (u8 *)&lo2, (u8 *)&hi2);
576 ASSERT_TRUE(ret);
577
578 char t1[] = "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
579
580 for (size_t i = 0; i < 16; i++) {
581 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
582 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
583
584 ASSERT_LE(((size_t)t1 + strlen(t1)) & ~0xf, (size_t)rv);
585 }
586 }
587
TEST(DoubleShufti,ExecNoMatch3b)588 TEST(DoubleShufti, ExecNoMatch3b) {
589 m128 lo1, hi1, lo2, hi2;
590
591 flat_set<pair<u8, u8>> lits;
592
593 lits.insert(make_pair('e','V'));
594
595 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
596 (u8 *)&lo2, (u8 *)&hi2);
597 ASSERT_TRUE(ret);
598
599 char t1[] = "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
600
601 for (size_t i = 0; i < 16; i++) {
602 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
603 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
604
605 ASSERT_EQ((size_t)t1 + i + 15, (size_t)rv);
606 }
607 }
608
TEST(DoubleShufti,ExecMatchShort1)609 TEST(DoubleShufti, ExecMatchShort1) {
610 m128 lo1, hi1, lo2, hi2;
611
612 flat_set<pair<u8, u8>> lits;
613
614 lits.insert(make_pair('a','b'));
615
616 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
617 (u8 *)&lo2, (u8 *)&hi2);
618 ASSERT_TRUE(ret);
619
620 /* 0123456789012345678901234567890 */
621 char t1[] = "bbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbb";
622
623 for (size_t i = 0; i < 16; i++) {
624 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
625 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
626
627 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
628 }
629 }
630
TEST(DoubleShufti,ExecMatch1)631 TEST(DoubleShufti, ExecMatch1) {
632 m128 lo1, hi1, lo2, hi2;
633
634 flat_set<pair<u8, u8>> lits;
635
636 lits.insert(make_pair('a','b'));
637
638 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
639 (u8 *)&lo2, (u8 *)&hi2);
640 ASSERT_TRUE(ret);
641
642 /* 0123456789012345678901234567890 */
643 char t1[] = "bbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbb";
644
645 for (size_t i = 0; i < 16; i++) {
646 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
647 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
648
649 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
650 }
651 }
652
TEST(DoubleShufti,ExecMatch2)653 TEST(DoubleShufti, ExecMatch2) {
654 m128 lo1, hi1, lo2, hi2;
655
656 flat_set<pair<u8, u8>> lits;
657
658 lits.insert(make_pair('a','a'));
659
660 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
661 (u8 *)&lo2, (u8 *)&hi2);
662 ASSERT_TRUE(ret);
663
664 /* 0123456789012345678901234567890 */
665 char t1[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
666
667 for (size_t i = 0; i < 16; i++) {
668 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
669 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
670
671 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
672 }
673 }
674
TEST(DoubleShufti,ExecMatch3)675 TEST(DoubleShufti, ExecMatch3) {
676 m128 lo1, hi1, lo2, hi2;
677
678 flat_set<pair<u8, u8>> lits;
679
680 lits.insert(make_pair('B','a'));
681 lits.insert(make_pair('a','a'));
682
683 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
684 (u8 *)&lo2, (u8 *)&hi2);
685 ASSERT_TRUE(ret);
686
687 /* 0123456789012345678901234567890 */
688 char t1[] = "bbbbbbbbbbbbbbbbbBaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
689
690 for (size_t i = 0; i < 16; i++) {
691 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
692 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
693
694 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
695 }
696 }
697
TEST(DoubleShufti,ExecMatch4)698 TEST(DoubleShufti, ExecMatch4) {
699 m128 lo1, hi1, lo2, hi2;
700
701 flat_set<pair<u8, u8>> lits;
702
703 lits.insert(make_pair('A','a'));
704 lits.insert(make_pair('a','a'));
705 lits.insert(make_pair('C','a'));
706 lits.insert(make_pair('c','a'));
707
708 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
709 (u8 *)&lo2, (u8 *)&hi2);
710 ASSERT_TRUE(ret);
711
712 /* 0123456789012345678901234567890 */
713 char t1[] = "bbbbbbbbbbbbbbbbbAaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
714 char t2[] = "bbbbbbbbbbbbbbbbbCaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
715 char t3[] = "bbbbbbbbbbbbbbbbbcaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
716 char t4[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
717
718 for (size_t i = 0; i < 16; i++) {
719 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
720 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
721
722 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
723
724 rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
725 (u8 *)t2 + i, (u8 *)t2 + strlen(t2));
726
727 ASSERT_EQ((size_t)t2 + 17, (size_t)rv);
728
729 rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
730 (u8 *)t3+ i, (u8 *)t3 + strlen(t3));
731
732 ASSERT_EQ((size_t)t3 + 17, (size_t)rv);
733
734 rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
735 (u8 *)t4 + i, (u8 *)t4 + strlen(t4));
736
737 ASSERT_EQ((size_t)t4 + 17, (size_t)rv);
738 }
739 }
740
TEST(DoubleShufti,ExecMatch4b)741 TEST(DoubleShufti, ExecMatch4b) {
742 m128 lo1, hi1, lo2, hi2;
743
744 flat_set<pair<u8, u8>> lits;
745
746 lits.insert(make_pair('a','A'));
747 lits.insert(make_pair('a','a'));
748 lits.insert(make_pair('a','C'));
749 lits.insert(make_pair('a','c'));
750
751 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
752 (u8 *)&lo2, (u8 *)&hi2);
753 ASSERT_TRUE(ret);
754
755 /* 0123456789012345678901234567890 */
756 char t1[] = "bbbbbbbbbbbbbbbbbaAaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
757 char t2[] = "bbbbbbbbbbbbbbbbbaCaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
758 char t3[] = "bbbbbbbbbbbbbbbbbacaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
759 char t4[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb";
760
761 for (size_t i = 0; i < 16; i++) {
762 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
763 (u8 *)t1 + i, (u8 *)t1 + strlen(t1));
764
765 ASSERT_EQ((size_t)t1 + 17, (size_t)rv);
766
767 rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
768 (u8 *)t2 + i, (u8 *)t2 + strlen(t2));
769
770 ASSERT_EQ((size_t)t2 + 17, (size_t)rv);
771
772 rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
773 (u8 *)t3+ i, (u8 *)t3 + strlen(t3));
774
775 ASSERT_EQ((size_t)t3 + 17, (size_t)rv);
776
777 rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
778 (u8 *)t4 + i, (u8 *)t4 + strlen(t4));
779
780 ASSERT_EQ((size_t)t4 + 17, (size_t)rv);
781 }
782 }
783
TEST(DoubleShufti,ExecMatch5)784 TEST(DoubleShufti, ExecMatch5) {
785 m128 lo1, hi1, lo2, hi2;
786
787 flat_set<pair<u8, u8>> lits;
788
789 lits.insert(make_pair('a','A'));
790
791 bool ret = shuftiBuildDoubleMasks(CharReach(), lits, (u8 *)&lo1, (u8 *)&hi1,
792 (u8 *)&lo2, (u8 *)&hi2);
793 ASSERT_TRUE(ret);
794
795 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
796
797 for (size_t i = 0; i < 31; i++) {
798 t1[48 - i] = 'a';
799 t1[48 - i + 1] = 'A';
800 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
801 (u8 *)t1, (u8 *)t1 + strlen(t1));
802
803 ASSERT_EQ((size_t)&t1[48 - i], (size_t)rv);
804 }
805 }
806
TEST(DoubleShufti,ExecMatchMixed1)807 TEST(DoubleShufti, ExecMatchMixed1) {
808 m128 lo1, hi1, lo2, hi2;
809
810 CharReach onebyte;
811 flat_set<pair<u8, u8>> twobyte;
812
813 // just one one-byte literal
814 onebyte.set('a');
815
816 bool ret = shuftiBuildDoubleMasks(onebyte, twobyte, (u8 *)&lo1, (u8 *)&hi1,
817 (u8 *)&lo2, (u8 *)&hi2);
818 ASSERT_TRUE(ret);
819
820 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
821
822 for (size_t i = 0; i < 31; i++) {
823 t1[48 - i] = 'a';
824 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
825 (u8 *)t1, (u8 *)t1 + strlen(t1));
826
827 ASSERT_EQ((size_t)&t1[48 - i], (size_t)rv);
828 }
829 }
830
TEST(DoubleShufti,ExecMatchMixed2)831 TEST(DoubleShufti, ExecMatchMixed2) {
832 m128 lo1, hi1, lo2, hi2;
833
834 CharReach onebyte;
835 flat_set<pair<u8, u8>> twobyte;
836
837 // one of each
838 onebyte.set('a');
839 twobyte.insert(make_pair('x', 'y'));
840
841 bool ret = shuftiBuildDoubleMasks(onebyte, twobyte, (u8 *)&lo1, (u8 *)&hi1,
842 (u8 *)&lo2, (u8 *)&hi2);
843 ASSERT_TRUE(ret);
844
845 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
846 char t2[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
847
848 for (size_t i = 0; i < 31; i++) {
849 t1[48 - i] = 'a';
850 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
851 (u8 *)t1, (u8 *)t1 + strlen(t1));
852
853 ASSERT_EQ((size_t)&t1[48 - i], (size_t)rv);
854 }
855
856 for (size_t i = 0; i < 31; i++) {
857 t2[48 - i] = 'x';
858 t2[48 - i + 1] = 'y';
859 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
860 (u8 *)t2, (u8 *)t2 + strlen(t1));
861
862 ASSERT_EQ((size_t)&t2[48 - i], (size_t)rv);
863 }
864 }
865
TEST(DoubleShufti,ExecMatchMixed3)866 TEST(DoubleShufti, ExecMatchMixed3) {
867 m128 lo1, hi1, lo2, hi2;
868
869 CharReach onebyte;
870 flat_set<pair<u8, u8>> twobyte;
871
872 // one of each
873 onebyte.set('a');
874 twobyte.insert(make_pair('x', 'y'));
875
876 bool ret = shuftiBuildDoubleMasks(onebyte, twobyte, (u8 *)&lo1, (u8 *)&hi1,
877 (u8 *)&lo2, (u8 *)&hi2);
878 ASSERT_TRUE(ret);
879
880 const int len = 420;
881 char t1[len + 1];
882 char t2[len + 2];
883 memset(t1, 'b', len);
884 memset(t2, 'b', len);
885
886 for (size_t i = 0; i < 400; i++) {
887 t1[len - i] = 'a';
888 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
889 (u8 *)t1, (u8 *)t1 + len);
890
891 ASSERT_EQ((size_t)&t1[len - i], (size_t)rv);
892 }
893
894 for (size_t i = 0; i < 400; i++) {
895 t2[len - i] = 'x';
896 t2[len - i + 1] = 'y';
897 const u8 *rv = shuftiDoubleExec(lo1, hi1, lo2, hi2,
898 (u8 *)t2, (u8 *)t2 + len);
899
900 ASSERT_EQ((size_t)&t2[len - i], (size_t)rv);
901 }
902 }
903
TEST(ReverseShufti,ExecNoMatch1)904 TEST(ReverseShufti, ExecNoMatch1) {
905 m128 lo, hi;
906
907 CharReach chars;
908 chars.set('a');
909
910 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
911 ASSERT_NE(-1, ret);
912
913 char t[] = " bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
914 char *t1 = t + 1;
915 size_t len = strlen(t1);
916
917 for (size_t i = 0; i < 16; i++) {
918 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len - i);
919 ASSERT_EQ((const u8 *)t, rv);
920 }
921 }
922
TEST(ReverseShufti,ExecNoMatch2)923 TEST(ReverseShufti, ExecNoMatch2) {
924 m128 lo, hi;
925
926 CharReach chars;
927 chars.set('a');
928 chars.set('B');
929
930 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
931 ASSERT_NE(-1, ret);
932
933 char t[] = " bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
934 char *t1 = t + 1;
935 size_t len = strlen(t1);
936
937 for (size_t i = 0; i < 16; i++) {
938 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len - i);
939 ASSERT_EQ((const u8 *)t, rv);
940 }
941 }
942
TEST(ReverseShufti,ExecNoMatch3)943 TEST(ReverseShufti, ExecNoMatch3) {
944 m128 lo, hi;
945
946 CharReach chars;
947 chars.set('V'); /* V = 0x56, e = 0x65 */
948
949 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
950 ASSERT_NE(-1, ret);
951
952 char t[] = "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
953 char *t1 = t + 1;
954 size_t len = strlen(t1);
955
956 for (size_t i = 0; i < 16; i++) {
957 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len - i);
958 ASSERT_EQ((const u8 *)t, rv);
959 }
960 }
961
TEST(ReverseShufti,ExecMatch1)962 TEST(ReverseShufti, ExecMatch1) {
963 m128 lo, hi;
964
965 CharReach chars;
966 chars.set('a');
967
968 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
969 ASSERT_NE(-1, ret);
970
971 /* 0123456789012345678901234567890 */
972 char t1[] = "bbbbbbabbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
973 size_t len = strlen(t1);
974
975 for (size_t i = 0; i < 16; i++) {
976 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len - i);
977 ASSERT_NE((const u8 *)t1 - 1, rv); // not found
978 EXPECT_EQ('a', (char)*rv);
979 ASSERT_EQ((const u8 *)t1 + 17, rv);
980 }
981 }
982
TEST(ReverseShufti,ExecMatch2)983 TEST(ReverseShufti, ExecMatch2) {
984 m128 lo, hi;
985
986 CharReach chars;
987 chars.set('a');
988
989 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
990 ASSERT_NE(-1, ret);
991
992 /* 0123456789012345678901234567890 */
993 char t1[] = "bbbbabbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbb";
994 size_t len = strlen(t1);
995
996 for (size_t i = 0; i < 16; i++) {
997 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len - i);
998 ASSERT_NE((const u8 *)t1 - 1, rv); // not found
999 EXPECT_EQ('a', (char)*rv);
1000 ASSERT_EQ((const u8 *)t1 + 32, rv);
1001 }
1002 }
1003
TEST(ReverseShufti,ExecMatch3)1004 TEST(ReverseShufti, ExecMatch3) {
1005 m128 lo, hi;
1006
1007 CharReach chars;
1008 chars.set('a');
1009 chars.set('B');
1010
1011 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
1012 ASSERT_NE(-1, ret);
1013
1014 /* 0123456789012345678901234567890 */
1015 char t1[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaBbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
1016 size_t len = strlen(t1);
1017
1018 for (size_t i = 0; i < 16; i++) {
1019 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len - i);
1020 ASSERT_NE((const u8 *)t1 - 1, rv); // not found
1021 EXPECT_EQ('B', (char)*rv);
1022 ASSERT_EQ((const u8 *)t1 + 32, rv);
1023 }
1024
1025 // check that we match the 'a' bytes as well.
1026 ASSERT_EQ('B', t1[32]);
1027 t1[32] = 'b';
1028 for (size_t i = 0; i < 16; i++) {
1029 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len - i);
1030 ASSERT_NE((const u8 *)t1 - 1, rv); // not found
1031 EXPECT_EQ('a', (char)*rv);
1032 ASSERT_EQ((const u8 *)t1 + 31, rv);
1033 }
1034 }
1035
TEST(ReverseShufti,ExecMatch4)1036 TEST(ReverseShufti, ExecMatch4) {
1037 m128 lo, hi;
1038
1039 CharReach chars;
1040 chars.set('a');
1041 chars.set('C');
1042 chars.set('A');
1043 chars.set('c');
1044
1045 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
1046 ASSERT_NE(-1, ret);
1047
1048 /* 0123456789012345678901234567890 */
1049 char t1[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaAbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
1050 char t2[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaCbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
1051 char t3[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaacbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
1052 char t4[] = "bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbb";
1053 size_t len = strlen(t1);
1054
1055 for (size_t i = 0; i < 16; i++) {
1056 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len - i);
1057 EXPECT_EQ('A', (char)*rv);
1058 ASSERT_EQ((const u8 *)t1 + 32, rv);
1059
1060 rv = rshuftiExec(lo, hi, (u8 *)t2, (u8 *)t2 + len - i);
1061 EXPECT_EQ('C', (char)*rv);
1062 ASSERT_EQ((const u8 *)t2 + 32, rv);
1063
1064 rv = rshuftiExec(lo, hi, (u8 *)t3, (u8 *)t3 + len - i);
1065 EXPECT_EQ('c', (char)*rv);
1066 ASSERT_EQ((const u8 *)t3 + 32, rv);
1067
1068 rv = rshuftiExec(lo, hi, (u8 *)t4, (u8 *)t4 + len - i);
1069 EXPECT_EQ('a', (char)*rv);
1070 ASSERT_EQ((const u8 *)t4 + 32, rv);
1071 }
1072 }
1073
TEST(ReverseShufti,ExecMatch5)1074 TEST(ReverseShufti, ExecMatch5) {
1075 m128 lo, hi;
1076
1077 CharReach chars;
1078 chars.set('a');
1079
1080 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
1081 ASSERT_NE(-1, ret);
1082
1083 char t1[] = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
1084 size_t len = strlen(t1);
1085
1086 for (size_t i = 0; i < len; i++) {
1087 t1[i] = 'a';
1088 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len);
1089
1090 ASSERT_EQ((const u8 *)t1 + i, rv);
1091 }
1092 }
1093
TEST(ReverseShufti,ExecMatch6)1094 TEST(ReverseShufti, ExecMatch6) {
1095 m128 lo, hi;
1096
1097 CharReach chars;
1098 chars.set('a');
1099
1100 int ret = shuftiBuildMasks(chars, (u8 *)&lo, (u8 *)&hi);
1101 ASSERT_NE(-1, ret);
1102
1103 const size_t len = 256;
1104 char t1[len];
1105 memset(t1, 'b', len);
1106
1107 for (size_t i = 0; i < len; i++) {
1108 t1[i] = 'a';
1109 const u8 *rv = rshuftiExec(lo, hi, (u8 *)t1, (u8 *)t1 + len);
1110
1111 ASSERT_EQ((const u8 *)t1 + i, rv);
1112 }
1113 }
1114