1 | /* |
2 | * Copyright (c) 2015, 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 Reverse-acceleration optimizations for the NFA API block mode scans. |
31 | */ |
32 | |
33 | #ifndef NFA_REV_API_H |
34 | #define NFA_REV_API_H |
35 | |
36 | #include "accel.h" |
37 | #include "nfa_internal.h" |
38 | #include "vermicelli.h" |
39 | #include "util/unaligned.h" |
40 | |
41 | static really_inline |
42 | size_t nfaRevAccel_i(const struct NFA *nfa, const u8 *buffer, size_t length) { |
43 | DEBUG_PRINTF("checking rev accel mw %u\n" , nfa->minWidth); |
44 | assert(nfa->rAccelOffset >= 1); |
45 | assert(nfa->rAccelOffset <= nfa->minWidth); |
46 | |
47 | const u8 *rv; // result for accel engine |
48 | |
49 | switch (nfa->rAccelType) { |
50 | case ACCEL_RVERM: |
51 | DEBUG_PRINTF("ACCEL_RVERM\n" ); |
52 | if (length + 1 - nfa->rAccelOffset < 16) { |
53 | break; |
54 | } |
55 | |
56 | rv = rvermicelliExec(nfa->rAccelData.c, 0, buffer, |
57 | buffer + length + 1 - nfa->rAccelOffset); |
58 | length = (size_t)(rv - buffer + nfa->rAccelOffset); |
59 | break; |
60 | case ACCEL_RVERM_NOCASE: |
61 | DEBUG_PRINTF("ACCEL_RVERM_NOCASE\n" ); |
62 | if (length + 1 - nfa->rAccelOffset < 16) { |
63 | break; |
64 | } |
65 | |
66 | rv = rvermicelliExec(nfa->rAccelData.c, 1, buffer, |
67 | buffer + length + 1 - nfa->rAccelOffset); |
68 | length = (size_t)(rv - buffer + nfa->rAccelOffset); |
69 | break; |
70 | case ACCEL_RDVERM: |
71 | DEBUG_PRINTF("ACCEL_RDVERM\n" ); |
72 | if (length + 1 - nfa->rAccelOffset < 17) { |
73 | break; |
74 | } |
75 | |
76 | rv = rvermicelliDoubleExec(nfa->rAccelData.array[0], |
77 | nfa->rAccelData.array[1], 0, buffer, |
78 | buffer + length + 1 - nfa->rAccelOffset); |
79 | length = (size_t)(rv - buffer + nfa->rAccelOffset); |
80 | break; |
81 | case ACCEL_RDVERM_NOCASE: |
82 | DEBUG_PRINTF("ACCEL_RVERM_NOCASE\n" ); |
83 | if (length + 1 - nfa->rAccelOffset < 17) { |
84 | break; |
85 | } |
86 | |
87 | rv = rvermicelliDoubleExec(nfa->rAccelData.array[0], |
88 | nfa->rAccelData.array[1], 1, buffer, |
89 | buffer + length + 1 - nfa->rAccelOffset); |
90 | length = (size_t)(rv - buffer + nfa->rAccelOffset); |
91 | break; |
92 | case ACCEL_REOD: |
93 | DEBUG_PRINTF("ACCEL_REOD\n" ); |
94 | if (buffer[length - nfa->rAccelOffset] != nfa->rAccelData.c) { |
95 | return 0; |
96 | } |
97 | break; |
98 | case ACCEL_REOD_NOCASE: |
99 | DEBUG_PRINTF("ACCEL_REOD_NOCASE\n" ); |
100 | if ((buffer[length - nfa->rAccelOffset] & CASE_CLEAR) != |
101 | nfa->rAccelData.c) { |
102 | return 0; |
103 | } |
104 | break; |
105 | case ACCEL_RDEOD: |
106 | DEBUG_PRINTF("ACCEL_RDEOD\n" ); |
107 | if (unaligned_load_u16(buffer + length - nfa->rAccelOffset) != |
108 | nfa->rAccelData.dc) { |
109 | return 0; |
110 | } |
111 | break; |
112 | case ACCEL_RDEOD_NOCASE: |
113 | DEBUG_PRINTF("ACCEL_RDEOD_NOCASE\n" ); |
114 | if ((unaligned_load_u16(buffer + length - nfa->rAccelOffset) & |
115 | DOUBLE_CASE_CLEAR) != nfa->rAccelData.dc) { |
116 | return 0; |
117 | } |
118 | break; |
119 | default: |
120 | assert(!"not here" ); |
121 | } |
122 | |
123 | if (nfa->minWidth > length) { |
124 | DEBUG_PRINTF("post-accel, scan skipped: %zu < min %u bytes\n" , length, |
125 | nfa->minWidth); |
126 | return 0; |
127 | } |
128 | |
129 | return length; |
130 | } |
131 | |
132 | /** \brief Reverse acceleration check. Returns a new length for the block, |
133 | * guaranteeing that a match cannot occur beyond that point. */ |
134 | static really_inline |
135 | size_t nfaRevAccelCheck(const struct NFA *nfa, const u8 *buffer, |
136 | size_t length) { |
137 | assert(nfa); |
138 | |
139 | // If this block is not long enough to satisfy the minimum width |
140 | // constraint on this NFA, we can avoid the scan altogether. |
141 | if (nfa->minWidth > length) { |
142 | DEBUG_PRINTF("scan skipped: %zu < min %u bytes\n" , length, |
143 | nfa->minWidth); |
144 | return 0; |
145 | } |
146 | |
147 | if (nfa->rAccelType == ACCEL_NONE) { |
148 | DEBUG_PRINTF("no rev accel available\n" ); |
149 | return length; |
150 | } |
151 | |
152 | size_t rv_length = nfaRevAccel_i(nfa, buffer, length); |
153 | assert(rv_length <= length); |
154 | return rv_length; |
155 | } |
156 | |
157 | #endif |
158 | |