1 /* $OpenBSD: util.c,v 1.36 2007/10/02 17:59:18 otto Exp $ */
2 /* $FreeBSD: head/usr.bin/grep/fastgrep.c 211496 2010-08-19 09:28:59Z des $ */
3
4 /*-
5 * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
6 * Copyright (C) 2008 Gabor Kovesdan <gabor@FreeBSD.org>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31 /*
32 * XXX: This file is a speed up for grep to cover the defects of the
33 * regex library. These optimizations should practically be implemented
34 * there keeping this code clean. This is a future TODO, but for the
35 * meantime, we need to use this workaround.
36 */
37
38 #if HAVE_NBTOOL_CONFIG_H
39 #include "nbtool_config.h"
40 #endif
41
42 #include <sys/cdefs.h>
43 __RCSID("$NetBSD: fastgrep.c,v 1.6 2024/10/01 14:56:42 christos Exp $");
44
45 #include <limits.h>
46 #include <stdbool.h>
47 #include <stdlib.h>
48 #include <string.h>
49 #include <wchar.h>
50 #include <wctype.h>
51
52 #include "grep.h"
53
54 static inline int grep_cmp(const unsigned char *, const unsigned char *, size_t);
55 static inline void grep_revstr(unsigned char *, int);
56
57 static void
alloc_pattern(fastgrep_t * fg,const char * pat)58 alloc_pattern(fastgrep_t *fg, const char *pat)
59 {
60 unsigned int i;
61
62 fg->pattern = (unsigned char *)grep_strdup(pat);
63 if (!iflag)
64 return;
65 for (i = 0; fg->pattern[i]; i++)
66 fg->pattern[i] = towupper((unsigned char)fg->pattern[i]);
67 }
68
69 static void
map_pattern(fastgrep_t * fg,int hasDot)70 map_pattern(fastgrep_t *fg, int hasDot)
71 {
72 unsigned int i;
73
74 for (i = 0; i <= UCHAR_MAX; i++)
75 fg->qsBc[i] = fg->len - hasDot;
76 for (i = hasDot + 1; i < fg->len; i++) {
77 unsigned char ch = fg->pattern[i];
78 if (iflag) {
79 fg->qsBc[ch] = fg->len - i;
80 ch = towlower(ch);
81 }
82 fg->qsBc[ch] = fg->len - i;
83 }
84 }
85
86 void
fgrepcomp(fastgrep_t * fg,const char * pat)87 fgrepcomp(fastgrep_t *fg, const char *pat)
88 {
89 /* Initialize. */
90 fg->len = strlen(pat);
91 fg->bol = false;
92 fg->eol = false;
93 fg->reversed = false;
94
95 alloc_pattern(fg, pat);
96
97 /* Preprocess pattern. */
98 map_pattern(fg, 0);
99 }
100
101 /*
102 * Returns: -1 on failure, 0 on success
103 */
104 int
fastcomp(fastgrep_t * fg,const char * pat)105 fastcomp(fastgrep_t *fg, const char *pat)
106 {
107 unsigned int i;
108 int firstHalfDot = -1;
109 int firstLastHalfDot = -1;
110 int hasDot = 0;
111 int lastHalfDot = 0;
112
113 /* Initialize. */
114 fg->len = strlen(pat);
115 fg->bol = false;
116 fg->eol = false;
117 fg->reversed = false;
118 fg->word = wflag;
119
120 /* Remove end-of-line character ('$'). */
121 if (fg->len > 0 && pat[fg->len - 1] == '$') {
122 fg->eol = true;
123 fg->len--;
124 }
125
126 /* Remove beginning-of-line character ('^'). */
127 if (pat[0] == '^') {
128 fg->bol = true;
129 fg->len--;
130 pat++;
131 }
132
133 if (fg->len >= 14 &&
134 memcmp(pat, "[[:<:]]", 7) == 0 &&
135 memcmp(pat + fg->len - 7, "[[:>:]]", 7) == 0) {
136 fg->len -= 14;
137 pat += 7;
138 /* Word boundary is handled separately in util.c */
139 fg->word = true;
140 }
141
142 /*
143 * pat has been adjusted earlier to not include '^', '$' or
144 * the word match character classes at the beginning and ending
145 * of the string respectively.
146 */
147 alloc_pattern(fg, pat);
148
149 /* Look for ways to cheat...er...avoid the full regex engine. */
150 for (i = 0; i < fg->len; i++) {
151 /* Can still cheat? */
152 if (fg->pattern[i] == '.') {
153 hasDot = i;
154 if (i < fg->len / 2) {
155 if (firstHalfDot < 0)
156 /* Closest dot to the beginning */
157 firstHalfDot = i;
158 } else {
159 /* Closest dot to the end of the pattern. */
160 lastHalfDot = i;
161 if (firstLastHalfDot < 0)
162 firstLastHalfDot = i;
163 }
164 } else {
165 /* Free memory and let others know this is empty. */
166 free(fg->pattern);
167 fg->pattern = NULL;
168 return (-1);
169 }
170 }
171
172 /*
173 * Determine if a reverse search would be faster based on the placement
174 * of the dots.
175 */
176 if ((!(lflag || cflag)) && ((!(fg->bol || fg->eol)) &&
177 ((lastHalfDot) && ((firstHalfDot < 0) ||
178 ((fg->len - (lastHalfDot + 1)) < (size_t)firstHalfDot)))) &&
179 !oflag && !color) {
180 fg->reversed = true;
181 hasDot = fg->len - (firstHalfDot < 0 ?
182 firstLastHalfDot : firstHalfDot) - 1;
183 grep_revstr(fg->pattern, fg->len);
184 }
185
186 /*
187 * Normal Quick Search would require a shift based on the position the
188 * next character after the comparison is within the pattern. With
189 * wildcards, the position of the last dot effects the maximum shift
190 * distance.
191 * The closer to the end the wild card is the slower the search. A
192 * reverse version of this algorithm would be useful for wildcards near
193 * the end of the string.
194 *
195 * Examples:
196 * Pattern Max shift
197 * ------- ---------
198 * this 5
199 * .his 4
200 * t.is 3
201 * th.s 2
202 * thi. 1
203 */
204
205 /* Preprocess pattern. */
206 map_pattern(fg, hasDot);
207
208 /*
209 * Put pattern back to normal after pre-processing to allow for easy
210 * comparisons later.
211 */
212 if (fg->reversed)
213 grep_revstr(fg->pattern, fg->len);
214
215 return (0);
216 }
217
218 int
grep_search(fastgrep_t * fg,const unsigned char * data,size_t len,regmatch_t * pmatch)219 grep_search(fastgrep_t *fg, const unsigned char *data, size_t len, regmatch_t *pmatch)
220 {
221 unsigned int j;
222 int ret = REG_NOMATCH;
223
224 if (pmatch->rm_so == (ssize_t)len)
225 return (ret);
226
227 if (fg->bol && pmatch->rm_so != 0) {
228 pmatch->rm_so = len;
229 pmatch->rm_eo = len;
230 return (ret);
231 }
232
233 /* No point in going farther if we do not have enough data. */
234 if (len < fg->len)
235 return (ret);
236
237 /* Only try once at the beginning or ending of the line. */
238 if (fg->bol || fg->eol) {
239 /* Simple text comparison. */
240 /* Verify data is >= pattern length before searching on it. */
241 if (len >= fg->len) {
242 /* Determine where in data to start search at. */
243 j = fg->eol ? len - fg->len : 0;
244 if (!((fg->bol && fg->eol) && (len != fg->len)))
245 if (grep_cmp(fg->pattern, data + j,
246 fg->len) == -1) {
247 pmatch->rm_so = j;
248 pmatch->rm_eo = j + fg->len;
249 ret = 0;
250 }
251 }
252 } else if (fg->reversed) {
253 /* Quick Search algorithm. */
254 j = len;
255 do {
256 if (grep_cmp(fg->pattern, data + j - fg->len,
257 fg->len) == -1) {
258 pmatch->rm_so = j - fg->len;
259 pmatch->rm_eo = j;
260 ret = 0;
261 break;
262 }
263 /* Shift if within bounds, otherwise, we are done. */
264 if (j == fg->len)
265 break;
266 j -= fg->qsBc[data[j - fg->len - 1]];
267 } while (j >= fg->len);
268 } else {
269 /* Quick Search algorithm. */
270 j = pmatch->rm_so;
271 do {
272 if (grep_cmp(fg->pattern, data + j, fg->len) == -1) {
273 pmatch->rm_so = j;
274 pmatch->rm_eo = j + fg->len;
275 ret = 0;
276 break;
277 }
278
279 /* Shift if within bounds, otherwise, we are done. */
280 if (j + fg->len == len)
281 break;
282 else
283 j += fg->qsBc[data[j + fg->len]];
284 } while (j <= (len - fg->len));
285 }
286
287 return (ret);
288 }
289
290 /*
291 * Returns: i >= 0 on failure (position that it failed)
292 * -1 on success
293 */
294 static inline int
grep_cmp(const unsigned char * pat,const unsigned char * data,size_t len)295 grep_cmp(const unsigned char *pat, const unsigned char *data, size_t len)
296 {
297 size_t size;
298 wchar_t *wdata, *wpat;
299 unsigned int i;
300
301 if (iflag) {
302 if ((size = mbstowcs(NULL, (const char *)data, 0)) ==
303 ((size_t) - 1))
304 return (-1);
305
306 wdata = grep_malloc(size * sizeof(wint_t));
307
308 if (mbstowcs(wdata, (const char *)data, size) ==
309 ((size_t) - 1))
310 return (-1);
311
312 if ((size = mbstowcs(NULL, (const char *)pat, 0)) ==
313 ((size_t) - 1))
314 return (-1);
315
316 wpat = grep_malloc(size * sizeof(wint_t));
317
318 if (mbstowcs(wpat, (const char *)pat, size) == ((size_t) - 1))
319 return (-1);
320 for (i = 0; i < len; i++) {
321 if ((towlower(wpat[i]) == towlower(wdata[i])) ||
322 ((grepbehave != GREP_FIXED) && wpat[i] == L'.'))
323 continue;
324 free(wpat);
325 free(wdata);
326 return (i);
327 }
328 } else {
329 for (i = 0; i < len; i++) {
330 if ((pat[i] == data[i]) || ((grepbehave != GREP_FIXED) &&
331 pat[i] == '.'))
332 continue;
333 return (i);
334 }
335 }
336 return (-1);
337 }
338
339 static inline void
grep_revstr(unsigned char * str,int len)340 grep_revstr(unsigned char *str, int len)
341 {
342 int i;
343 char c;
344
345 for (i = 0; i < len / 2; i++) {
346 c = str[i];
347 str[i] = str[len - i - 1];
348 str[len - i - 1] = c;
349 }
350 }
351