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 | * \brief Limex NFA: acceleration runtime. |
31 | */ |
32 | |
33 | #include "limex_accel.h" |
34 | |
35 | #include "accel.h" |
36 | #include "limex_internal.h" |
37 | #include "limex_limits.h" |
38 | #include "limex_shuffle.h" |
39 | #include "nfa_internal.h" |
40 | #include "shufti.h" |
41 | #include "truffle.h" |
42 | #include "ue2common.h" |
43 | #include "vermicelli.h" |
44 | #include "util/arch.h" |
45 | #include "util/bitutils.h" |
46 | #include "util/simd_utils.h" |
47 | |
48 | static really_inline |
49 | size_t accelScanWrapper(const u8 *accelTable, const union AccelAux *aux, |
50 | const u8 *input, u32 idx, size_t i, size_t end) { |
51 | assert(accelTable); |
52 | assert(aux); |
53 | |
54 | DEBUG_PRINTF("shuffle returned %u -> aux %u\n" , idx, accelTable[idx]); |
55 | assert(idx < (1 << NFA_MAX_ACCEL_STATES)); |
56 | if (!idx) { |
57 | return end; |
58 | } |
59 | |
60 | u8 aux_idx = accelTable[idx]; |
61 | if (!aux_idx) { |
62 | assert(aux[0].accel_type == ACCEL_NONE); |
63 | DEBUG_PRINTF("no accel, bailing\n" ); |
64 | return i; |
65 | } |
66 | |
67 | aux = aux + aux_idx; |
68 | const u8 *ptr = run_accel(aux, &input[i], &input[end]); |
69 | assert(ptr >= &input[i]); |
70 | size_t j = (size_t)(ptr - input); |
71 | DEBUG_PRINTF("accel skipped %zu of %zu chars\n" , (j - i), (end - i)); |
72 | DEBUG_PRINTF("returning j=%zu (i=%zu, end=%zu)\n" , j, i, end); |
73 | return j; |
74 | } |
75 | |
76 | size_t doAccel32(u32 s, u32 accel, const u8 *accelTable, |
77 | const union AccelAux *aux, const u8 *input, size_t i, |
78 | size_t end) { |
79 | u32 idx = pext32(s, accel); |
80 | return accelScanWrapper(accelTable, aux, input, idx, i, end); |
81 | } |
82 | |
83 | #ifdef ARCH_64_BIT |
84 | size_t doAccel64(u64a s, u64a accel, const u8 *accelTable, |
85 | const union AccelAux *aux, const u8 *input, size_t i, |
86 | size_t end) { |
87 | u32 idx = pext64(s, accel); |
88 | return accelScanWrapper(accelTable, aux, input, idx, i, end); |
89 | } |
90 | #else |
91 | size_t doAccel64(m128 s, m128 accel, const u8 *accelTable, |
92 | const union AccelAux *aux, const u8 *input, size_t i, |
93 | size_t end) { |
94 | u32 idx = pext64(movq(s), movq(accel)); |
95 | return accelScanWrapper(accelTable, aux, input, idx, i, end); |
96 | } |
97 | #endif |
98 | |
99 | size_t doAccel128(const m128 *state, const struct LimExNFA128 *limex, |
100 | const u8 *accelTable, const union AccelAux *aux, |
101 | const u8 *input, size_t i, size_t end) { |
102 | u32 idx; |
103 | m128 s = *state; |
104 | DEBUG_PRINTF("using PSHUFB for 128-bit shuffle\n" ); |
105 | m128 accelPerm = limex->accelPermute; |
106 | m128 accelComp = limex->accelCompare; |
107 | idx = packedExtract128(s, accelPerm, accelComp); |
108 | return accelScanWrapper(accelTable, aux, input, idx, i, end); |
109 | } |
110 | |
111 | size_t doAccel256(const m256 *state, const struct LimExNFA256 *limex, |
112 | const u8 *accelTable, const union AccelAux *aux, |
113 | const u8 *input, size_t i, size_t end) { |
114 | u32 idx; |
115 | m256 s = *state; |
116 | DEBUG_PRINTF("using PSHUFB for 256-bit shuffle\n" ); |
117 | m256 accelPerm = limex->accelPermute; |
118 | m256 accelComp = limex->accelCompare; |
119 | #if !defined(HAVE_AVX2) |
120 | u32 idx1 = packedExtract128(s.lo, accelPerm.lo, accelComp.lo); |
121 | u32 idx2 = packedExtract128(s.hi, accelPerm.hi, accelComp.hi); |
122 | assert((idx1 & idx2) == 0); // should be no shared bits |
123 | idx = idx1 | idx2; |
124 | #else |
125 | idx = packedExtract256(s, accelPerm, accelComp); |
126 | #endif |
127 | return accelScanWrapper(accelTable, aux, input, idx, i, end); |
128 | } |
129 | |
130 | size_t doAccel384(const m384 *state, const struct LimExNFA384 *limex, |
131 | const u8 *accelTable, const union AccelAux *aux, |
132 | const u8 *input, size_t i, size_t end) { |
133 | u32 idx; |
134 | m384 s = *state; |
135 | DEBUG_PRINTF("using PSHUFB for 384-bit shuffle\n" ); |
136 | m384 accelPerm = limex->accelPermute; |
137 | m384 accelComp = limex->accelCompare; |
138 | u32 idx1 = packedExtract128(s.lo, accelPerm.lo, accelComp.lo); |
139 | u32 idx2 = packedExtract128(s.mid, accelPerm.mid, accelComp.mid); |
140 | u32 idx3 = packedExtract128(s.hi, accelPerm.hi, accelComp.hi); |
141 | assert((idx1 & idx2 & idx3) == 0); // should be no shared bits |
142 | idx = idx1 | idx2 | idx3; |
143 | return accelScanWrapper(accelTable, aux, input, idx, i, end); |
144 | } |
145 | |
146 | size_t doAccel512(const m512 *state, const struct LimExNFA512 *limex, |
147 | const u8 *accelTable, const union AccelAux *aux, |
148 | const u8 *input, size_t i, size_t end) { |
149 | u32 idx; |
150 | m512 s = *state; |
151 | DEBUG_PRINTF("using PSHUFB for 512-bit shuffle\n" ); |
152 | m512 accelPerm = limex->accelPermute; |
153 | m512 accelComp = limex->accelCompare; |
154 | #if defined(HAVE_AVX512) |
155 | idx = packedExtract512(s, accelPerm, accelComp); |
156 | #elif defined(HAVE_AVX2) |
157 | u32 idx1 = packedExtract256(s.lo, accelPerm.lo, accelComp.lo); |
158 | u32 idx2 = packedExtract256(s.hi, accelPerm.hi, accelComp.hi); |
159 | assert((idx1 & idx2) == 0); // should be no shared bits |
160 | idx = idx1 | idx2; |
161 | #else |
162 | u32 idx1 = packedExtract128(s.lo.lo, accelPerm.lo.lo, accelComp.lo.lo); |
163 | u32 idx2 = packedExtract128(s.lo.hi, accelPerm.lo.hi, accelComp.lo.hi); |
164 | u32 idx3 = packedExtract128(s.hi.lo, accelPerm.hi.lo, accelComp.hi.lo); |
165 | u32 idx4 = packedExtract128(s.hi.hi, accelPerm.hi.hi, accelComp.hi.hi); |
166 | assert((idx1 & idx2 & idx3 & idx4) == 0); // should be no shared bits |
167 | idx = idx1 | idx2 | idx3 | idx4; |
168 | #endif |
169 | return accelScanWrapper(accelTable, aux, input, idx, i, end); |
170 | } |
171 | |