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
48static really_inline
49size_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
76size_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
84size_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
91size_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
99size_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
111size_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
130size_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
146size_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