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
29enum MatchMode {
30 CALLBACK_OUTPUT,
31 STOP_AT_MATCH,
32 NO_MATCHES
33};
34
35static really_inline
36const 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
45static really_inline
46u32 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
53static really_inline
54u32 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
86static really_inline
87u16 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
170normal:
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
180partial:
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