usr.bin/grep/fastgrep.c

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