1 | /* |
2 | * Copyright (c) 2015-2018, 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 | enum MatchMode { |
30 | CALLBACK_OUTPUT, |
31 | STOP_AT_MATCH, |
32 | NO_MATCHES |
33 | }; |
34 | |
35 | static really_inline |
36 | const struct mstate_aux *get_aux(const struct mcclellan *m, u32 s) { |
37 | const char *nfa = (const char *)m - sizeof(struct NFA); |
38 | const struct mstate_aux *aux |
39 | = s + (const struct mstate_aux *)(nfa + m->aux_offset); |
40 | |
41 | assert(ISALIGNED(aux)); |
42 | return aux; |
43 | } |
44 | |
45 | static really_inline |
46 | u32 mcclellanEnableStarts(const struct mcclellan *m, u32 s) { |
47 | const struct mstate_aux *aux = get_aux(m, s); |
48 | |
49 | DEBUG_PRINTF("enabling starts %u->%hu\n" , s, aux->top); |
50 | return aux->top; |
51 | } |
52 | |
53 | static really_inline |
54 | u32 doSherman16(const char *sherman_state, u8 cprime, const u16 *succ_table, |
55 | u32 as) { |
56 | assert(ISALIGNED_N(sherman_state, 16)); |
57 | |
58 | u8 len = *(const u8 *)(sherman_state + SHERMAN_LEN_OFFSET); |
59 | |
60 | if (len) { |
61 | m128 ss_char = load128(sherman_state); |
62 | m128 cur_char = set16x8(cprime); |
63 | |
64 | u32 z = movemask128(eq128(ss_char, cur_char)); |
65 | |
66 | /* remove header cruft: type 1, len 1, daddy 2*/ |
67 | z &= ~0xf; |
68 | z &= (1U << (len + 4)) - 1; |
69 | |
70 | if (z) { |
71 | u32 i = ctz32(z & ~0xf) - 4; |
72 | |
73 | u32 s_out = unaligned_load_u16((const u8 *)sherman_state |
74 | + SHERMAN_STATES_OFFSET(len) |
75 | + sizeof(u16) * i); |
76 | DEBUG_PRINTF("found sherman match at %u/%u for c'=%hhu s=%u\n" , i, |
77 | len, cprime, s_out); |
78 | return s_out; |
79 | } |
80 | } |
81 | |
82 | u32 daddy = *(const u16 *)(sherman_state + SHERMAN_DADDY_OFFSET); |
83 | return succ_table[(daddy << as) + cprime]; |
84 | } |
85 | |
86 | static really_inline |
87 | u16 doWide16(const char *wide_entry, const u8 **c_inout, const u8 *end, |
88 | const u8 *remap, const u16 *s, char *qstate, u16 *offset) { |
89 | // Internal relative offset after the last visit of the wide state. |
90 | if (qstate != NULL) { // stream mode |
91 | *offset = unaligned_load_u16((const u16 *)(qstate + 2)); |
92 | } |
93 | |
94 | u8 successful = 0; |
95 | const u8 *c = *c_inout; |
96 | u32 len_c = end - c; |
97 | |
98 | u16 width = *(const u16 *)(wide_entry + WIDE_WIDTH_OFFSET); |
99 | assert(width >= 8); |
100 | const u8 *symbols = (const u8 *)(wide_entry + WIDE_SYMBOL_OFFSET16); |
101 | const u16 *trans = (const u16 *)(wide_entry + |
102 | WIDE_TRANSITION_OFFSET16(width)); |
103 | |
104 | assert(*offset < width); |
105 | u16 len_w = width - *offset; |
106 | const u8 *sym = symbols + *offset; |
107 | |
108 | char tmp[16]; |
109 | u16 pos = 0; |
110 | |
111 | if (*offset == 0 && remap[*c] != *sym) { |
112 | goto normal; |
113 | } |
114 | |
115 | // both in (16, +oo). |
116 | while (len_w >= 16 && len_c >= 16) { |
117 | m128 str_w = loadu128(sym); |
118 | for (size_t i = 0; i < 16; i++) { |
119 | tmp[i] = remap[*(c + i)]; |
120 | } |
121 | m128 str_c = loadu128(tmp); |
122 | |
123 | u32 z = movemask128(eq128(str_w, str_c)); |
124 | pos = ctz32(~z); |
125 | assert(pos <= 16); |
126 | |
127 | if (pos < 16) { |
128 | goto normal; |
129 | } |
130 | |
131 | sym += 16; |
132 | c += 16; |
133 | len_w -= 16; |
134 | len_c -= 16; |
135 | } |
136 | |
137 | pos = 0; |
138 | // at least one in (0, 16). |
139 | u32 loadLength_w = MIN(len_w, 16); |
140 | u32 loadLength_c = MIN(len_c, 16); |
141 | m128 str_w = loadbytes128(sym, loadLength_w); |
142 | for (size_t i = 0; i < loadLength_c; i++) { |
143 | tmp[i] = remap[*(c + i)]; |
144 | } |
145 | m128 str_c = loadbytes128(tmp, loadLength_c); |
146 | |
147 | u32 z = movemask128(eq128(str_w, str_c)); |
148 | pos = ctz32(~z); |
149 | |
150 | pos = MIN(pos, MIN(loadLength_w, loadLength_c)); |
151 | |
152 | if (loadLength_w <= loadLength_c) { |
153 | assert(pos <= loadLength_w); |
154 | // successful matching. |
155 | if (pos == loadLength_w) { |
156 | c -= 1; |
157 | successful = 1; |
158 | } |
159 | // failure, do nothing. |
160 | } else { |
161 | assert(pos <= loadLength_c); |
162 | // successful partial matching. |
163 | if (pos == loadLength_c) { |
164 | c -= 1; |
165 | goto partial; |
166 | } |
167 | // failure, do nothing. |
168 | } |
169 | |
170 | normal: |
171 | *offset = 0; |
172 | if (qstate != NULL) { |
173 | // Internal relative offset. |
174 | unaligned_store_u16(qstate + 2, *offset); |
175 | } |
176 | c += pos; |
177 | *c_inout = c; |
178 | return successful ? *trans : *(trans + 1 + remap[*c]); |
179 | |
180 | partial: |
181 | *offset = sym - symbols + pos; |
182 | if (qstate != NULL) { |
183 | // Internal relative offset. |
184 | unaligned_store_u16(qstate + 2, *offset); |
185 | } |
186 | c += pos; |
187 | *c_inout = c; |
188 | return *s; |
189 | } |
190 | |