1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* 28 * grep - pattern matching program - combined grep, egrep, and fgrep. 29 * Based on MKS grep command, with XCU & Solaris mods. 30 */ 31 32 /* 33 * Copyright 1985, 1992 by Mortice Kern Systems Inc. All rights reserved. 34 * 35 */ 36 37 /* 38 * Copyright 2020 Peter Tribble. 39 * Copyright 2018 RackTop Systems. 40 * Copyright 2018 Nexenta Systems, Inc. 41 * Copyright 2013 Damian Bogel. All rights reserved. 42 * Copyright 2020 Oxide Computer Company 43 */ 44 45 #include <string.h> 46 #include <stdlib.h> 47 #include <ctype.h> 48 #include <stdarg.h> 49 #include <regex.h> 50 #include <limits.h> 51 #include <sys/types.h> 52 #include <sys/stat.h> 53 #include <fcntl.h> 54 #include <stdio.h> 55 #include <locale.h> 56 #include <wchar.h> 57 #include <errno.h> 58 #include <unistd.h> 59 #include <wctype.h> 60 #include <ftw.h> 61 #include <sys/param.h> 62 #include <getopt.h> 63 64 #define STDIN_FILENAME gettext("(standard input)") 65 66 #define BSIZE 512 /* Size of block for -b */ 67 #define BUFSIZE 8192 /* Input buffer size */ 68 #define MAX_DEPTH 1000 /* how deep to recurse */ 69 70 #define AFTER 1 /* 'After' Context */ 71 #define BEFORE 2 /* 'Before' Context */ 72 #define CONTEXT (AFTER|BEFORE) /* Full Context */ 73 74 #define M_CSETSIZE 256 /* singlebyte chars */ 75 static int bmglen; /* length of BMG pattern */ 76 static char *bmgpat; /* BMG pattern */ 77 static int bmgtab[M_CSETSIZE]; /* BMG delta1 table */ 78 79 typedef struct _PATTERN { 80 char *pattern; /* original pattern */ 81 wchar_t *wpattern; /* wide, lowercased pattern */ 82 struct _PATTERN *next; 83 regex_t re; /* compiled pattern */ 84 } PATTERN; 85 86 static PATTERN *patterns; 87 static char errstr[128]; /* regerror string buffer */ 88 static int regflags = 0; /* regcomp options */ 89 static int matched = 0; /* return of the grep() */ 90 static int errors = 0; /* count of errors */ 91 static uchar_t fgrep = 0; /* Invoked as fgrep */ 92 static uchar_t egrep = 0; /* Invoked as egrep */ 93 static boolean_t nvflag = B_TRUE; /* Print matching lines */ 94 static uchar_t cflag; /* Count of matches */ 95 static uchar_t iflag; /* Case insensitve matching */ 96 static uchar_t Hflag; /* Precede lines by file name */ 97 static uchar_t hflag; /* Suppress printing of filename */ 98 static uchar_t lflag; /* Print file names of matches */ 99 static uchar_t Lflag; /* Print file names of non-matches */ 100 static uchar_t nflag; /* Precede lines by line number */ 101 static uchar_t rflag; /* Search directories recursively */ 102 static uchar_t bflag; /* Precede matches by block number */ 103 static uchar_t sflag; /* Suppress file error messages */ 104 static uchar_t qflag; /* Suppress standard output */ 105 static uchar_t wflag; /* Search for expression as a word */ 106 static uchar_t xflag; /* Anchoring */ 107 static uchar_t Eflag; /* Egrep or -E flag */ 108 static uchar_t Fflag; /* Fgrep or -F flag */ 109 static uchar_t Rflag; /* Like rflag, but follow symlinks */ 110 static uchar_t outfn; /* Put out file name */ 111 static uchar_t conflag; /* show context of matches */ 112 static char *cmdname; 113 static char *stdin_label; /* Optional lable for stdin */ 114 115 static int use_wchar, use_bmg, mblocale; 116 117 static size_t outbuflen, prntbuflen, conbuflen; 118 static unsigned long conalen, conblen, conmatches; 119 static char *prntbuf, *conbuf; 120 static wchar_t *outline; 121 122 static void addfile(const char *fn); 123 static void addpattern(char *s); 124 static void fixpatterns(void); 125 static void usage(void); 126 static int grep(int, const char *); 127 static void bmgcomp(char *, int); 128 static char *bmgexec(char *, char *); 129 static int recursive(const char *, const struct stat *, int, struct FTW *); 130 static void process_path(const char *); 131 static void process_file(const char *, int); 132 133 /* 134 * These are values that we use to return from getopt_long. They start at 135 * SHRT_MAX to avoid any possible conflict with the normal options. These are 136 * used for long options that have no short option equivalent. 137 */ 138 enum grep_opts { 139 OPT_LABEL = SHRT_MAX + 1 140 }; 141 142 static struct option grep_options[] = { 143 { "label", required_argument, NULL, OPT_LABEL }, 144 { NULL } 145 }; 146 147 /* 148 * mainline for grep 149 */ 150 int 151 main(int argc, char **argv) 152 { 153 char *ap, *test; 154 int c; 155 int fflag = 0; 156 int i, n_pattern = 0, n_file = 0; 157 char **pattern_list = NULL; 158 char **file_list = NULL; 159 160 (void) setlocale(LC_ALL, ""); 161 #if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */ 162 #define TEXT_DOMAIN "SYS_TEST" /* Use this only if it weren't */ 163 #endif 164 (void) textdomain(TEXT_DOMAIN); 165 166 /* 167 * true if this is running on the multibyte locale 168 */ 169 mblocale = (MB_CUR_MAX > 1); 170 /* 171 * Skip leading slashes 172 */ 173 cmdname = argv[0]; 174 if (ap = strrchr(cmdname, '/')) 175 cmdname = ap + 1; 176 177 ap = cmdname; 178 /* 179 * Detect egrep/fgrep via command name, map to -E and -F options. 180 */ 181 if (*ap == 'e' || *ap == 'E') { 182 regflags |= REG_EXTENDED; 183 egrep++; 184 } else { 185 if (*ap == 'f' || *ap == 'F') { 186 fgrep++; 187 } 188 } 189 190 /* check for non-standard "-line-count" option */ 191 for (i = 1; i < argc; i++) { 192 if (strcmp(argv[i], "--") == 0) 193 break; 194 195 /* isdigit() check prevents negative arguments */ 196 if ((argv[i][0] == '-') && isdigit(argv[i][1])) { 197 if (strlen(&argv[i][1]) != 198 strspn(&argv[i][1], "0123456789")) { 199 (void) fprintf(stderr, gettext( 200 "%s: Bad number flag\n"), argv[0]); 201 usage(); 202 } 203 204 errno = 0; 205 conalen = conblen = strtoul(&argv[i][1], (char **)NULL, 206 10); 207 208 if (errno != 0 || conalen >= ULONG_MAX) { 209 (void) fprintf(stderr, gettext( 210 "%s: Bad context argument\n"), argv[0]); 211 } else if (conalen) 212 conflag = CONTEXT; 213 214 while (i < argc) { 215 argv[i] = argv[i + 1]; 216 i++; 217 } 218 argc--; 219 } 220 } 221 222 while ((c = getopt_long(argc, argv, "+vwchHilLnrbse:f:qxEFIRA:B:C:", 223 grep_options, NULL)) != EOF) { 224 unsigned long tval; 225 switch (c) { 226 case 'v': /* POSIX: negate matches */ 227 nvflag = B_FALSE; 228 break; 229 230 case 'c': /* POSIX: write count */ 231 cflag++; 232 break; 233 234 case 'i': /* POSIX: ignore case */ 235 iflag++; 236 regflags |= REG_ICASE; 237 break; 238 239 /* 240 * The last of -l and -L are honored. 241 */ 242 case 'l': /* POSIX: Write filenames only */ 243 lflag++; 244 Lflag = 0; 245 break; 246 247 case 'L': /* Write non-matching filenames */ 248 Lflag++; 249 lflag = 0; 250 break; 251 252 case 'n': /* POSIX: Write line numbers */ 253 nflag++; 254 break; 255 256 case 'r': /* Solaris: search recursively */ 257 rflag++; 258 break; 259 260 case 'b': /* Solaris: Write file block numbers */ 261 bflag++; 262 break; 263 264 case 's': /* POSIX: No error msgs for files */ 265 sflag++; 266 break; 267 268 case 'e': /* POSIX: pattern list */ 269 n_pattern++; 270 pattern_list = realloc(pattern_list, 271 sizeof (char *) * n_pattern); 272 if (pattern_list == NULL) { 273 (void) fprintf(stderr, 274 gettext("%s: out of memory\n"), 275 cmdname); 276 exit(2); 277 } 278 *(pattern_list + n_pattern - 1) = optarg; 279 break; 280 281 case 'f': /* POSIX: pattern file */ 282 fflag = 1; 283 n_file++; 284 file_list = realloc(file_list, 285 sizeof (char *) * n_file); 286 if (file_list == NULL) { 287 (void) fprintf(stderr, 288 gettext("%s: out of memory\n"), 289 cmdname); 290 exit(2); 291 } 292 *(file_list + n_file - 1) = optarg; 293 break; 294 295 /* based on options order h or H is set as in GNU grep */ 296 case 'h': /* Solaris: suppress printing of file name */ 297 hflag = 1; 298 Hflag = 0; 299 break; 300 /* Solaris: precede every match with file name */ 301 case 'H': 302 Hflag = 1; 303 hflag = 0; 304 break; 305 306 case 'q': /* POSIX: quiet: status only */ 307 qflag++; 308 break; 309 310 case 'w': /* Solaris: treat pattern as word */ 311 wflag++; 312 break; 313 314 case 'x': /* POSIX: full line matches */ 315 xflag++; 316 break; 317 318 case 'E': /* POSIX: Extended RE's */ 319 regflags |= REG_EXTENDED; 320 Eflag++; 321 break; 322 323 case 'F': /* POSIX: strings, not RE's */ 324 Fflag++; 325 break; 326 327 case 'R': /* Solaris: like rflag, but follow symlinks */ 328 Rflag++; 329 rflag++; 330 break; 331 332 case 'A': /* print N lines after each match */ 333 errno = 0; 334 conalen = strtoul(optarg, &test, 10); 335 /* *test will be non-null if optarg is negative */ 336 if (errno != 0 || *test != '\0' || 337 conalen >= ULONG_MAX) { 338 (void) fprintf(stderr, gettext( 339 "%s: Bad context argument: %s\n"), 340 argv[0], optarg); 341 exit(2); 342 } 343 if (conalen) 344 conflag |= AFTER; 345 else 346 conflag &= ~AFTER; 347 break; 348 case 'B': /* print N lines before each match */ 349 errno = 0; 350 conblen = strtoul(optarg, &test, 10); 351 /* *test will be non-null if optarg is negative */ 352 if (errno != 0 || *test != '\0' || 353 conblen >= ULONG_MAX) { 354 (void) fprintf(stderr, gettext( 355 "%s: Bad context argument: %s\n"), 356 argv[0], optarg); 357 exit(2); 358 } 359 if (conblen) 360 conflag |= BEFORE; 361 else 362 conflag &= ~BEFORE; 363 break; 364 case 'C': /* print N lines around each match */ 365 errno = 0; 366 tval = strtoul(optarg, &test, 10); 367 /* *test will be non-null if optarg is negative */ 368 if (errno != 0 || *test != '\0' || tval >= ULONG_MAX) { 369 (void) fprintf(stderr, gettext( 370 "%s: Bad context argument: %s\n"), 371 argv[0], optarg); 372 exit(2); 373 } 374 if (tval) { 375 if ((conflag & BEFORE) == 0) 376 conblen = tval; 377 if ((conflag & AFTER) == 0) 378 conalen = tval; 379 conflag = CONTEXT; 380 } 381 break; 382 383 case OPT_LABEL: 384 stdin_label = optarg; 385 break; 386 387 default: 388 usage(); 389 } 390 } 391 /* 392 * If we're invoked as egrep or fgrep we need to do some checks 393 */ 394 395 if (egrep || fgrep) { 396 /* 397 * Use of -E or -F with egrep or fgrep is illegal 398 */ 399 if (Eflag || Fflag) 400 usage(); 401 /* 402 * Don't allow use of wflag with egrep / fgrep 403 */ 404 if (wflag) 405 usage(); 406 /* 407 * For Solaris the -s flag is equivalent to XCU -q 408 */ 409 if (sflag) 410 qflag++; 411 /* 412 * done with above checks - set the appropriate flags 413 */ 414 if (egrep) 415 Eflag++; 416 else /* Else fgrep */ 417 Fflag++; 418 } 419 420 if (wflag && (Eflag || Fflag)) { 421 /* 422 * -w cannot be specified with grep -F 423 */ 424 usage(); 425 } 426 427 /* 428 * -E and -F flags are mutually exclusive - check for this 429 */ 430 if (Eflag && Fflag) 431 usage(); 432 433 /* 434 * -l or -L overrides -H like in GNU grep 435 */ 436 if (lflag || Lflag) 437 Hflag = 0; 438 439 /* 440 * -c, -l and -q flags are mutually exclusive 441 * We have -c override -l like in Solaris. 442 * -q overrides -l & -c programmatically in grep() function. 443 */ 444 if (cflag && (lflag || Lflag)) { 445 lflag = 0; 446 Lflag = 0; 447 } 448 449 argv += optind - 1; 450 argc -= optind - 1; 451 452 /* 453 * Now handling -e and -f option 454 */ 455 if (pattern_list) { 456 for (i = 0; i < n_pattern; i++) { 457 addpattern(pattern_list[i]); 458 } 459 free(pattern_list); 460 } 461 if (file_list) { 462 for (i = 0; i < n_file; i++) { 463 addfile(file_list[i]); 464 } 465 free(file_list); 466 } 467 468 /* 469 * No -e or -f? Make sure there is one more arg, use it as the pattern. 470 */ 471 if (patterns == NULL && !fflag) { 472 if (argc < 2) 473 usage(); 474 addpattern(argv[1]); 475 argc--; 476 argv++; 477 } 478 479 /* 480 * If -x flag is not specified or -i flag is specified 481 * with fgrep in a multibyte locale, need to use 482 * the wide character APIs. Otherwise, byte-oriented 483 * process will be done. 484 */ 485 use_wchar = Fflag && mblocale && (!xflag || iflag); 486 487 /* 488 * Compile Patterns and also decide if BMG can be used 489 */ 490 fixpatterns(); 491 492 if (stdin_label == NULL) { 493 stdin_label = STDIN_FILENAME; 494 } 495 496 /* Process all files: stdin, or rest of arg list */ 497 if (argc < 2) { 498 matched = grep(0, stdin_label); 499 } else { 500 if (Hflag || (argc > 2 && hflag == 0)) 501 outfn = 1; /* Print filename on match line */ 502 for (argv++; *argv != NULL; argv++) { 503 process_path(*argv); 504 } 505 } 506 /* 507 * Return() here is used instead of exit 508 */ 509 510 (void) fflush(stdout); 511 512 if (errors) 513 return (2); 514 return (matched ? 0 : 1); 515 } 516 517 static void 518 process_path(const char *path) 519 { 520 struct stat st; 521 int walkflags = FTW_CHDIR; 522 char *buf = NULL; 523 524 if (rflag) { 525 if (stat(path, &st) != -1 && 526 (st.st_mode & S_IFMT) == S_IFDIR) { 527 if (!hflag) 528 outfn = 1; /* Print filename unless -h */ 529 530 /* 531 * Add trailing slash if arg 532 * is directory, to resolve symlinks. 533 */ 534 if (path[strlen(path) - 1] != '/') { 535 (void) asprintf(&buf, "%s/", path); 536 if (buf != NULL) 537 path = buf; 538 } 539 540 /* 541 * Search through subdirs if path is directory. 542 * Don't follow symlinks if Rflag is not set. 543 */ 544 if (!Rflag) 545 walkflags |= FTW_PHYS; 546 547 if (nftw(path, recursive, MAX_DEPTH, walkflags) != 0) { 548 if (!sflag) 549 (void) fprintf(stderr, 550 gettext("%s: can't open \"%s\"\n"), 551 cmdname, path); 552 errors = 1; 553 } 554 return; 555 } 556 } 557 process_file(path, 0); 558 } 559 560 /* 561 * Read and process all files in directory recursively. 562 */ 563 static int 564 recursive(const char *name, const struct stat *statp, int info, struct FTW *ftw) 565 { 566 /* 567 * Process files and follow symlinks if Rflag set. 568 */ 569 if (info != FTW_F) { 570 /* Report broken symlinks and unreadable files */ 571 if (!sflag && 572 (info == FTW_SLN || info == FTW_DNR || info == FTW_NS)) { 573 (void) fprintf(stderr, 574 gettext("%s: can't open \"%s\"\n"), cmdname, name); 575 } 576 return (0); 577 } 578 579 580 /* Skip devices and pipes if Rflag is not set */ 581 if (!Rflag && !S_ISREG(statp->st_mode)) 582 return (0); 583 /* Pass offset to relative name from FTW_CHDIR */ 584 process_file(name, ftw->base); 585 return (0); 586 } 587 588 /* 589 * Opens file and call grep function. 590 */ 591 static void 592 process_file(const char *name, int base) 593 { 594 int fd; 595 596 if ((fd = open(name + base, O_RDONLY)) == -1) { 597 errors = 1; 598 if (!sflag) /* Silent mode */ 599 (void) fprintf(stderr, gettext( 600 "%s: can't open \"%s\"\n"), 601 cmdname, name); 602 return; 603 } 604 matched |= grep(fd, name); 605 (void) close(fd); 606 607 if (ferror(stdout)) { 608 (void) fprintf(stderr, gettext( 609 "%s: error writing to stdout\n"), 610 cmdname); 611 (void) fflush(stdout); 612 exit(2); 613 } 614 615 } 616 617 /* 618 * Add a file of strings to the pattern list. 619 */ 620 static void 621 addfile(const char *fn) 622 { 623 FILE *fp; 624 char *inbuf; 625 char *bufp; 626 size_t bufsiz, buflen, bufused; 627 628 /* 629 * Open the pattern file 630 */ 631 if ((fp = fopen(fn, "r")) == NULL) { 632 (void) fprintf(stderr, gettext("%s: can't open \"%s\"\n"), 633 cmdname, fn); 634 exit(2); 635 } 636 bufsiz = BUFSIZE; 637 if ((inbuf = malloc(bufsiz)) == NULL) { 638 (void) fprintf(stderr, 639 gettext("%s: out of memory\n"), cmdname); 640 exit(2); 641 } 642 bufp = inbuf; 643 bufused = 0; 644 /* 645 * Read in the file, reallocing as we need more memory 646 */ 647 while (fgets(bufp, bufsiz - bufused, fp) != NULL) { 648 buflen = strlen(bufp); 649 bufused += buflen; 650 if (bufused + 1 == bufsiz && bufp[buflen - 1] != '\n') { 651 /* 652 * if this line does not fit to the buffer, 653 * realloc larger buffer 654 */ 655 bufsiz += BUFSIZE; 656 if ((inbuf = realloc(inbuf, bufsiz)) == NULL) { 657 (void) fprintf(stderr, 658 gettext("%s: out of memory\n"), 659 cmdname); 660 exit(2); 661 } 662 bufp = inbuf + bufused; 663 continue; 664 } 665 if (bufp[buflen - 1] == '\n') { 666 bufp[--buflen] = '\0'; 667 } 668 addpattern(inbuf); 669 670 bufp = inbuf; 671 bufused = 0; 672 } 673 free(inbuf); 674 free(prntbuf); 675 free(conbuf); 676 (void) fclose(fp); 677 } 678 679 /* 680 * Add a string to the pattern list. 681 */ 682 static void 683 addpattern(char *s) 684 { 685 PATTERN *pp; 686 char *wordbuf; 687 char *np; 688 689 for (; ; ) { 690 np = strchr(s, '\n'); 691 if (np != NULL) 692 *np = '\0'; 693 if ((pp = malloc(sizeof (PATTERN))) == NULL) { 694 (void) fprintf(stderr, gettext( 695 "%s: out of memory\n"), 696 cmdname); 697 exit(2); 698 } 699 if (wflag) { 700 /* 701 * Solaris wflag support: Add '<' '>' to pattern to 702 * select it as a word. Doesn't make sense with -F 703 * but we're Libertarian. 704 */ 705 size_t slen, wordlen; 706 707 slen = strlen(s); 708 wordlen = slen + 5; /* '\\' '<' s '\\' '>' '\0' */ 709 if ((wordbuf = malloc(wordlen)) == NULL) { 710 (void) fprintf(stderr, 711 gettext("%s: out of memory\n"), 712 cmdname); 713 exit(2); 714 } 715 (void) strcpy(wordbuf, "\\<"); 716 (void) strcpy(wordbuf + 2, s); 717 (void) strcpy(wordbuf + 2 + slen, "\\>"); 718 } else { 719 if ((wordbuf = strdup(s)) == NULL) { 720 (void) fprintf(stderr, 721 gettext("%s: out of memory\n"), 722 cmdname); 723 exit(2); 724 } 725 } 726 pp->pattern = wordbuf; 727 pp->next = patterns; 728 patterns = pp; 729 if (np == NULL) 730 break; 731 s = np + 1; 732 } 733 } 734 735 /* 736 * Fix patterns. 737 * Must do after all arguments read, in case later -i option. 738 */ 739 static void 740 fixpatterns(void) 741 { 742 PATTERN *pp; 743 int rv, fix_pattern, npatterns; 744 745 /* 746 * Fix the specified pattern if -x is specified. 747 */ 748 fix_pattern = !Fflag && xflag; 749 750 for (npatterns = 0, pp = patterns; pp != NULL; pp = pp->next) { 751 npatterns++; 752 if (fix_pattern) { 753 char *cp, *cq; 754 size_t plen, nplen; 755 756 plen = strlen(pp->pattern); 757 /* '^' pattern '$' */ 758 nplen = 1 + plen + 1 + 1; 759 if ((cp = malloc(nplen)) == NULL) { 760 (void) fprintf(stderr, 761 gettext("%s: out of memory\n"), 762 cmdname); 763 exit(2); 764 } 765 cq = cp; 766 *cq++ = '^'; 767 cq = strcpy(cq, pp->pattern) + plen; 768 *cq++ = '$'; 769 *cq = '\0'; 770 free(pp->pattern); 771 pp->pattern = cp; 772 } 773 774 if (Fflag) { 775 if (use_wchar) { 776 /* 777 * Fflag && mblocale && iflag 778 * Fflag && mblocale && !xflag 779 */ 780 size_t n; 781 n = strlen(pp->pattern) + 1; 782 if ((pp->wpattern = 783 malloc(sizeof (wchar_t) * n)) == NULL) { 784 (void) fprintf(stderr, 785 gettext("%s: out of memory\n"), 786 cmdname); 787 exit(2); 788 } 789 if (mbstowcs(pp->wpattern, pp->pattern, n) == 790 (size_t)-1) { 791 (void) fprintf(stderr, 792 gettext("%s: failed to convert " 793 "\"%s\" to wide-characters\n"), 794 cmdname, pp->pattern); 795 exit(2); 796 } 797 if (iflag) { 798 wchar_t *wp; 799 for (wp = pp->wpattern; *wp != L'\0'; 800 wp++) { 801 *wp = towlower((wint_t)*wp); 802 } 803 } 804 free(pp->pattern); 805 } else { 806 /* 807 * Fflag && mblocale && !iflag 808 * Fflag && !mblocale && iflag 809 * Fflag && !mblocale && !iflag 810 */ 811 if (iflag) { 812 unsigned char *cp; 813 for (cp = (unsigned char *)pp->pattern; 814 *cp != '\0'; cp++) { 815 *cp = tolower(*cp); 816 } 817 } 818 } 819 /* 820 * fgrep: No regular expressions. 821 */ 822 continue; 823 } 824 825 /* 826 * For non-fgrep, compile the regular expression, 827 * give an informative error message, and exit if 828 * it didn't compile. 829 */ 830 if ((rv = regcomp(&pp->re, pp->pattern, regflags)) != 0) { 831 (void) regerror(rv, &pp->re, errstr, sizeof (errstr)); 832 (void) fprintf(stderr, 833 gettext("%s: RE error in %s: %s\n"), 834 cmdname, pp->pattern, errstr); 835 exit(2); 836 } 837 free(pp->pattern); 838 } 839 840 /* 841 * Decide if we are able to run the Boyer-Moore-Gosper algorithm. 842 * Use the Boyer-Moore-Gosper algorithm if: 843 * - fgrep (Fflag) 844 * - singlebyte locale (!mblocale) 845 * - no ignoring case (!iflag) 846 * - no printing line numbers (!nflag) 847 * - no negating the output (nvflag) 848 * - only one pattern (npatterns == 1) 849 * - non zero length pattern (strlen(patterns->pattern) != 0) 850 * - no context required (conflag == 0) 851 * 852 * It's guaranteed patterns->pattern is still alive 853 * when Fflag && !mblocale. 854 */ 855 use_bmg = Fflag && !mblocale && !iflag && !nflag && nvflag && 856 (npatterns == 1) && (strlen(patterns->pattern) != 0) && 857 conflag == 0; 858 } 859 860 /* 861 * Search a newline from the beginning of the string 862 */ 863 static char * 864 find_nl(const char *ptr, size_t len) 865 { 866 while (len-- != 0) { 867 if (*ptr++ == '\n') { 868 return ((char *)--ptr); 869 } 870 } 871 return (NULL); 872 } 873 874 /* 875 * Search a newline from the end of the string 876 */ 877 static char * 878 rfind_nl(const char *ptr, size_t len) 879 { 880 const char *uptr = ptr + len; 881 while (len--) { 882 if (*--uptr == '\n') { 883 return ((char *)uptr); 884 } 885 } 886 return (NULL); 887 } 888 889 /* 890 * Duplicate the specified string converting each character 891 * into a lower case. 892 */ 893 static char * 894 istrdup(const char *s1) 895 { 896 static size_t ibuflen = 0; 897 static char *ibuf = NULL; 898 size_t slen; 899 char *p; 900 901 slen = strlen(s1); 902 if (slen >= ibuflen) { 903 /* ibuf does not fit to s1 */ 904 ibuflen = slen + 1; 905 ibuf = realloc(ibuf, ibuflen); 906 if (ibuf == NULL) { 907 (void) fprintf(stderr, 908 gettext("%s: out of memory\n"), cmdname); 909 exit(2); 910 } 911 } 912 p = ibuf; 913 do { 914 *p++ = tolower(*s1); 915 } while (*s1++ != '\0'); 916 return (ibuf); 917 } 918 919 /* 920 * Do grep on a single file. 921 * Return true in any lines matched. 922 * 923 * We have two strategies: 924 * The fast one is used when we have a single pattern with 925 * a string known to occur in the pattern. We can then 926 * do a BMG match on the whole buffer. 927 * This is an order of magnitude faster. 928 * Otherwise we split the buffer into lines, 929 * and check for a match on each line. 930 */ 931 static int 932 grep(int fd, const char *fn) 933 { 934 PATTERN *pp; 935 off_t data_len; /* length of the data chunk */ 936 off_t line_len; /* length of the current line */ 937 off_t line_offset; /* current line's offset from the beginning */ 938 off_t blkoffset; /* line_offset but context-compatible */ 939 long long lineno, linenum; 940 long long matches = 0; /* Number of matching lines */ 941 long long conacnt = 0, conbcnt = 0; /* context line count */ 942 int newlinep; /* 0 if the last line of file has no newline */ 943 char *ptr, *ptrend, *prntptr, *prntptrend; 944 char *nextptr = NULL, *nextend = NULL; 945 char *conptr = NULL, *conptrend = NULL; 946 char *matchptr = NULL; 947 int conaprnt = 0, conbprnt = 0, lastmatch = 0; 948 boolean_t nearmatch; /* w/in N+1 of last match */ 949 boolean_t havematch = B_FALSE; /* have a match in context */ 950 size_t prntlen; 951 952 if (patterns == NULL) 953 return (0); /* no patterns to match -- just return */ 954 955 pp = patterns; 956 957 if (use_bmg) { 958 bmgcomp(pp->pattern, strlen(pp->pattern)); 959 } 960 961 if (use_wchar && outline == NULL) { 962 outbuflen = BUFSIZE + 1; 963 outline = malloc(sizeof (wchar_t) * outbuflen); 964 if (outline == NULL) { 965 (void) fprintf(stderr, gettext("%s: out of memory\n"), 966 cmdname); 967 exit(2); 968 } 969 } 970 971 if (prntbuf == NULL) { 972 prntbuflen = BUFSIZE; 973 if ((prntbuf = malloc(prntbuflen + 1)) == NULL) { 974 (void) fprintf(stderr, gettext("%s: out of memory\n"), 975 cmdname); 976 exit(2); 977 } 978 } 979 980 if (conflag != 0 && (conbuf == NULL)) { 981 conbuflen = BUFSIZE; 982 if ((conbuf = malloc(BUFSIZE+1)) == NULL) { 983 (void) fprintf(stderr, gettext("%s: out of memory\n"), 984 cmdname); 985 exit(2); 986 } 987 } 988 989 nearmatch = (conmatches != 0); 990 blkoffset = line_offset = 0; 991 lineno = 0; 992 linenum = 1; 993 newlinep = 1; 994 data_len = 0; 995 for (; ; ) { 996 long count; 997 off_t offset = 0; 998 char separate; 999 boolean_t last_ctx = B_FALSE, eof = B_FALSE; 1000 1001 if (data_len == 0) { 1002 /* 1003 * If no data in the buffer, reset ptr 1004 */ 1005 ptr = prntbuf; 1006 if (conflag != 0 && conptr == NULL) { 1007 conptr = conbuf; 1008 conptrend = conptr - 1; 1009 } 1010 } 1011 if (ptr == prntbuf) { 1012 /* 1013 * The current data chunk starts from prntbuf. 1014 * This means either the buffer has no data 1015 * or the buffer has no newline. 1016 * So, read more data from input. 1017 */ 1018 count = read(fd, ptr + data_len, prntbuflen - data_len); 1019 if (count < 0) { 1020 /* read error */ 1021 if (cflag) { 1022 if (outfn && !rflag) { 1023 (void) fprintf(stdout, 1024 "%s:", fn); 1025 } 1026 if (!qflag && !rflag) { 1027 (void) fprintf(stdout, "%lld\n", 1028 matches); 1029 } 1030 } 1031 return (0); 1032 } else if (count == 0) { 1033 /* no new data */ 1034 eof = B_TRUE; 1035 1036 if (data_len == 0) { 1037 /* end of file already reached */ 1038 if (conflag != 0) { 1039 if (conptrend >= conptr) 1040 *conptrend = '\n'; 1041 last_ctx = B_TRUE; 1042 goto L_next_line; 1043 } else { 1044 goto out; 1045 } 1046 } 1047 /* last line of file has no newline */ 1048 ptrend = ptr + data_len; 1049 newlinep = 0; 1050 goto L_start_process; 1051 } 1052 offset = data_len; 1053 data_len += count; 1054 } 1055 1056 /* 1057 * Look for newline in the chunk 1058 * between ptr + offset and ptr + data_len - offset. 1059 */ 1060 ptrend = find_nl(ptr + offset, data_len - offset); 1061 if (ptrend == NULL) { 1062 /* no newline found in this chunk */ 1063 if (ptr > prntbuf) { 1064 /* 1065 * Move remaining data to the beginning 1066 * of the buffer. 1067 * Remaining data lie from ptr for 1068 * data_len bytes. 1069 */ 1070 (void) memmove(prntbuf, ptr, data_len); 1071 } 1072 if (data_len == prntbuflen) { 1073 /* 1074 * Not enough room in the buffer 1075 */ 1076 if (prntbuflen > SIZE_MAX - BUFSIZE) { 1077 (void) fprintf(stderr, 1078 gettext("%s: buflen would" 1079 " overflow\n"), 1080 cmdname); 1081 exit(2); 1082 } 1083 1084 prntbuflen += BUFSIZE; 1085 prntbuf = realloc(prntbuf, prntbuflen + 1); 1086 if (prntbuf == NULL) { 1087 (void) fprintf(stderr, 1088 gettext("%s: out of memory\n"), 1089 cmdname); 1090 exit(2); 1091 } 1092 } 1093 ptr = prntbuf; 1094 /* read the next input */ 1095 continue; 1096 } 1097 L_start_process: 1098 1099 /* 1100 * Beginning of the chunk: ptr 1101 * End of the chunk: ptr + data_len 1102 * Beginning of the line: ptr 1103 * End of the line: ptrend 1104 * 1105 * conptr: Beginning of the context. 1106 * conptrend: If context is empty, conptr - 1 (invalid memory). 1107 * Otherwise, Last newline in the context. 1108 */ 1109 1110 if (use_bmg) { 1111 /* 1112 * Use Boyer-Moore-Gosper algorithm to find out if 1113 * this chunk (not this line) contains the specified 1114 * pattern. If not, restart from the last line 1115 * of this chunk. 1116 */ 1117 char *bline; 1118 bline = bmgexec(ptr, ptr + data_len); 1119 if (bline == NULL) { 1120 /* 1121 * No pattern found in this chunk. 1122 * Need to find the last line 1123 * in this chunk. 1124 */ 1125 ptrend = rfind_nl(ptr, data_len); 1126 1127 /* 1128 * When this chunk does not contain newline, 1129 * ptrend becomes NULL, which should happen 1130 * when the last line of file does not end 1131 * with a newline. At such a point, 1132 * newlinep should have been set to 0. 1133 * Therefore, just after jumping to 1134 * L_skip_line, the main for-loop quits, 1135 * and the line_len value won't be 1136 * used. 1137 */ 1138 line_len = ptrend - ptr; 1139 goto L_skip_line; 1140 } 1141 if (bline > ptrend) { 1142 /* 1143 * Pattern found not in the first line 1144 * of this chunk. 1145 * Discard the first line. 1146 */ 1147 line_len = ptrend - ptr; 1148 goto L_skip_line; 1149 } 1150 /* 1151 * Pattern found in the first line of this chunk. 1152 * Using this result. 1153 */ 1154 *ptrend = '\0'; 1155 line_len = ptrend - ptr; 1156 1157 /* 1158 * before jumping to L_next_line, 1159 * need to handle xflag if specified 1160 */ 1161 if (xflag && (line_len != bmglen || 1162 strcmp(bmgpat, ptr) != 0)) { 1163 /* didn't match */ 1164 pp = NULL; 1165 } else { 1166 pp = patterns; /* to make it happen */ 1167 } 1168 goto L_next_line; 1169 } 1170 lineno++; 1171 /* 1172 * Line starts from ptr and ends at ptrend. 1173 * line_len will be the length of the line. 1174 */ 1175 *ptrend = '\0'; 1176 line_len = ptrend - ptr; 1177 1178 /* 1179 * From now, the process will be performed based 1180 * on the line from ptr to ptrend. 1181 */ 1182 if (use_wchar) { 1183 size_t len; 1184 1185 if (line_len >= outbuflen) { 1186 outbuflen = line_len + 1; 1187 outline = realloc(outline, 1188 sizeof (wchar_t) * outbuflen); 1189 if (outline == NULL) { 1190 (void) fprintf(stderr, 1191 gettext("%s: out of memory\n"), 1192 cmdname); 1193 exit(2); 1194 } 1195 } 1196 1197 len = mbstowcs(outline, ptr, line_len); 1198 if (len == (size_t)-1) { 1199 (void) fprintf(stderr, gettext( 1200 "%s: input file \"%s\": line %lld: invalid multibyte character\n"), 1201 cmdname, fn, lineno); 1202 /* never match a line with invalid sequence */ 1203 goto L_skip_line; 1204 } 1205 outline[len] = L'\0'; 1206 1207 if (iflag) { 1208 wchar_t *cp; 1209 for (cp = outline; *cp != '\0'; cp++) { 1210 *cp = towlower((wint_t)*cp); 1211 } 1212 } 1213 1214 if (xflag) { 1215 for (pp = patterns; pp; pp = pp->next) { 1216 if (outline[0] == pp->wpattern[0] && 1217 wcscmp(outline, 1218 pp->wpattern) == 0) { 1219 /* matched */ 1220 break; 1221 } 1222 } 1223 } else { 1224 for (pp = patterns; pp; pp = pp->next) { 1225 if (wcswcs(outline, pp->wpattern) 1226 != NULL) { 1227 /* matched */ 1228 break; 1229 } 1230 } 1231 } 1232 } else if (Fflag) { 1233 /* fgrep in byte-oriented handling */ 1234 char *fptr; 1235 if (iflag) { 1236 fptr = istrdup(ptr); 1237 } else { 1238 fptr = ptr; 1239 } 1240 if (xflag) { 1241 /* fgrep -x */ 1242 for (pp = patterns; pp; pp = pp->next) { 1243 if (fptr[0] == pp->pattern[0] && 1244 strcmp(fptr, pp->pattern) == 0) { 1245 /* matched */ 1246 break; 1247 } 1248 } 1249 } else { 1250 for (pp = patterns; pp; pp = pp->next) { 1251 if (strstr(fptr, pp->pattern) != NULL) { 1252 /* matched */ 1253 break; 1254 } 1255 } 1256 } 1257 } else { 1258 /* grep or egrep */ 1259 for (pp = patterns; pp; pp = pp->next) { 1260 int rv; 1261 1262 rv = regexec(&pp->re, ptr, 0, NULL, 0); 1263 if (rv == REG_OK) { 1264 /* matched */ 1265 break; 1266 } 1267 1268 switch (rv) { 1269 case REG_NOMATCH: 1270 break; 1271 case REG_ECHAR: 1272 (void) fprintf(stderr, gettext( 1273 "%s: input file \"%s\": line %lld: invalid multibyte character\n"), 1274 cmdname, fn, lineno); 1275 break; 1276 default: 1277 (void) regerror(rv, &pp->re, errstr, 1278 sizeof (errstr)); 1279 (void) fprintf(stderr, gettext( 1280 "%s: input file \"%s\": line %lld: %s\n"), 1281 cmdname, fn, lineno, errstr); 1282 exit(2); 1283 } 1284 } 1285 } 1286 1287 /* 1288 * Context is set up as follows: 1289 * For a 'Before' context, we maintain a set of pointers 1290 * containing 'N' lines of context. If the current number of 1291 * lines contained is greater than N, and N isn't a match, the 1292 * start pointer is moved forward to the next newline. 1293 * 1294 * If we ever find a match, we print out immediately. 1295 * 'nearmatch' tells us if we're within N+1 lines of the last 1296 * match ; if we are, and we find another match, we don't 1297 * separate the matches. 'nearmatch' becomes false when 1298 * a line gets rotated out of the context. 1299 * 1300 * For an 'After' context, we simply wait until we've found a 1301 * match, then create a context N+1 lines big. If we don't find 1302 * a match within the context, we print out the current context. 1303 * Otherwise, we save a reference to the new matching line, 1304 * print out the other context, and reset our context pointers 1305 * to the new matching line. 1306 * 1307 * 'nearmatch' becomes false when we find a non-matching line 1308 * that isn't a part of any context. 1309 * 1310 * A full-context is implemented as a combination of the 1311 * 'Before' and 'After' context logic. Before we find a match, 1312 * we follow the Before logic. When we find a match, we 1313 * follow the After logic. 'nearmatch' is handled by the Before 1314 * logic. 1315 */ 1316 1317 if (conflag == 0) 1318 goto L_next_line; 1319 1320 /* Do we have room to add this line to the context buffer? */ 1321 while ((line_len + 1) > (conbuflen - 1322 ((conptrend >= conptr) ? conptrend - conbuf : 0))) { 1323 char *oldconbuf = conbuf; 1324 char *oldconptr = conptr; 1325 long tmp = matchptr - conptr; 1326 1327 if (conbuflen > SIZE_MAX - BUFSIZE) { 1328 (void) fprintf(stderr, 1329 gettext("%s: buflen would overflow\n"), 1330 cmdname); 1331 exit(2); 1332 } 1333 1334 conbuflen += BUFSIZE; 1335 conbuf = realloc(conbuf, conbuflen + 1); 1336 if (conbuf == NULL) { 1337 (void) fprintf(stderr, 1338 gettext("%s: out of memory\n"), 1339 cmdname); 1340 exit(2); 1341 } 1342 1343 conptr = conbuf + (conptr - oldconbuf); 1344 conptrend = conptr + (conptrend - oldconptr); 1345 if (matchptr) 1346 matchptr = conptr + tmp; 1347 } 1348 (void) memcpy(conptrend + 1, ptr, line_len); 1349 conptrend += line_len + 1; 1350 *conptrend = '\n'; 1351 1352 if (nvflag == (pp != NULL)) { 1353 /* matched */ 1354 if (havematch) { 1355 if ((conflag & AFTER) != 0) { 1356 conaprnt = 1; 1357 nextend = conptrend; 1358 conptrend = conptr + lastmatch; 1359 nextptr = conptrend + 1; 1360 *nextend = '\n'; 1361 } 1362 } else { 1363 if (conflag == AFTER) { 1364 conptr = conptrend - (line_len); 1365 linenum = lineno; 1366 } 1367 blkoffset = line_offset - 1368 (conptrend - conptr - line_len); 1369 } 1370 1371 if (conflag == BEFORE) 1372 conbprnt = 1; 1373 1374 lastmatch = conptrend - conptr; 1375 havematch = B_TRUE; 1376 goto L_next_line; 1377 } 1378 1379 if (!havematch) { 1380 if ((conflag & BEFORE) != 0) { 1381 if (conbcnt >= conblen) { 1382 char *tmp = conptr; 1383 conptr = find_nl(conptr, 1384 conptrend - conptr) + 1; 1385 if (bflag) 1386 blkoffset += conptr - tmp; 1387 linenum++; 1388 nearmatch = B_TRUE; 1389 } else { 1390 conbcnt++; 1391 } 1392 } 1393 if (conflag == AFTER) 1394 nearmatch = B_TRUE; 1395 } else { 1396 if (++conacnt >= conalen && !conaprnt && conalen) 1397 conaprnt = 1; 1398 else 1399 lastmatch = conptrend - conptr; 1400 } 1401 1402 L_next_line: 1403 /* 1404 * Here, if pp points to non-NULL, something has been matched 1405 * to the pattern. 1406 */ 1407 if (!last_ctx && nvflag == (pp != NULL)) { 1408 matches++; 1409 if (!nextend) 1410 matchptr = (conflag != 0) ? conptrend : ptrend; 1411 } 1412 1413 /* 1414 * Set up some print context so that we can treat 1415 * single-line matches as a zero-N context. 1416 * Apply CLI flags to each line of the context. 1417 * 1418 * For context, we only print if we both have a match and are 1419 * either at the end of the data stream, or we've previously 1420 * declared that we want to print for a particular context. 1421 */ 1422 if (havematch && (eof || conaprnt || conbprnt)) { 1423 1424 /* 1425 * We'd normally do this earlier, but we had to 1426 * escape early because we reached the end of the data. 1427 */ 1428 if (eof && nextptr) 1429 conptrend = nextend; 1430 1431 prntlen = conptrend - conptr + 1; 1432 prntptr = conptr; 1433 if (conmatches++ && nearmatch && !cflag) 1434 (void) fwrite("--\n", 1, 3, stdout); 1435 } else if (conflag == 0 && nvflag == (pp != NULL)) { 1436 *ptrend = '\n'; 1437 prntlen = line_len + 1; 1438 prntptr = ptr; 1439 linenum = lineno; 1440 blkoffset = line_offset; 1441 } else if (eof) { 1442 /* No match and no more data */ 1443 goto out; 1444 } else { 1445 /* No match, or we're not done building context */ 1446 goto L_skip_line; 1447 } 1448 1449 prntptrend = prntptr - 1; 1450 while ((prntptrend = find_nl(prntptrend + 1, 1451 prntlen)) != NULL) { 1452 1453 /* 1454 * GNU grep uses '-' for context lines and ':' for 1455 * matching lines, so replicate that here. 1456 */ 1457 if (prntptrend == matchptr) { 1458 if (eof && nextptr) { 1459 matchptr = nextend; 1460 nextptr = NULL; 1461 } else { 1462 matchptr = NULL; 1463 } 1464 separate = ':'; 1465 } else { 1466 separate = '-'; 1467 } 1468 1469 /* 1470 * Handle q, l, and c flags. 1471 */ 1472 if (qflag) { 1473 /* no need to continue */ 1474 /* 1475 * End of this line is ptrend. 1476 * We have read up to ptr + data_len. 1477 */ 1478 off_t pos; 1479 pos = ptr + data_len - (ptrend + 1); 1480 (void) lseek(fd, -pos, SEEK_CUR); 1481 exit(0); 1482 } 1483 if (lflag) { 1484 (void) printf("%s\n", fn); 1485 goto out; 1486 } 1487 if (Lflag) { 1488 goto out; 1489 } 1490 if (!cflag) { 1491 if (Hflag || outfn) { 1492 (void) printf("%s%c", fn, separate); 1493 } 1494 if (bflag) { 1495 (void) printf("%lld%c", (offset_t) 1496 (blkoffset / BSIZE), separate); 1497 } 1498 if (nflag) { 1499 (void) printf("%lld%c", linenum, 1500 separate); 1501 } 1502 (void) fwrite(prntptr, 1, 1503 prntptrend - prntptr + 1, stdout); 1504 } 1505 if (ferror(stdout)) { 1506 return (0); 1507 } 1508 linenum++; 1509 prntlen -= prntptrend - prntptr + 1; 1510 blkoffset += prntptrend - prntptr + 1; 1511 prntptr = prntptrend + 1; 1512 } 1513 1514 if (eof) 1515 goto out; 1516 1517 /* 1518 * Update context buffer and variables post-print 1519 */ 1520 if (conflag != 0) { 1521 conptr = conbuf; 1522 conaprnt = conbprnt = 0; 1523 nearmatch = B_FALSE; 1524 conacnt = conbcnt = 0; 1525 1526 if (nextptr) { 1527 (void) memmove(conbuf, nextptr, 1528 nextend - nextptr + 1); 1529 blkoffset += nextptr - conptrend - 1; 1530 conptrend = conptr + (nextend - nextptr); 1531 matchptr = conptrend; 1532 linenum = lineno; 1533 lastmatch = conptrend - conptr; 1534 havematch = B_TRUE; 1535 } else { 1536 conptrend = conptr - 1; 1537 conacnt = 0; 1538 lastmatch = 0; 1539 havematch = B_FALSE; 1540 } 1541 nextptr = nextend = NULL; 1542 } 1543 1544 L_skip_line: 1545 if (!newlinep) 1546 break; 1547 1548 data_len -= line_len + 1; 1549 line_offset += line_len + 1; 1550 ptr = ptrend + 1; 1551 } 1552 1553 out: 1554 if (cflag) { 1555 if (Hflag || outfn) { 1556 (void) printf("%s:", fn); 1557 } 1558 if (!qflag) { 1559 (void) printf("%lld\n", matches); 1560 } 1561 } 1562 1563 /* 1564 * -L tells us to print the filename only when it doesn't match. So we 1565 * run through the normal operationa and then invert it. 1566 */ 1567 if (Lflag) { 1568 if (matches == 0) { 1569 (void) printf("%s\n", fn); 1570 matches = 1; 1571 } else { 1572 matches = 0; 1573 } 1574 } 1575 1576 return (matches != 0); 1577 } 1578 1579 /* 1580 * usage message for grep 1581 */ 1582 static void 1583 usage(void) 1584 { 1585 (void) fprintf(stderr, gettext("usage: %5s"), cmdname); 1586 if (!egrep && !fgrep) 1587 (void) fprintf(stderr, gettext(" [-E|-F]")); 1588 (void) fprintf(stderr, gettext(" [-bchHilLnqrRsvx] [-A num] [-B num] " 1589 "[-C num|-num]\n [--label=name] [-e pattern_list]... " 1590 "[-f pattern_file]...\n [pattern_list] [file]...\n")); 1591 exit(2); 1592 /* NOTREACHED */ 1593 } 1594 1595 /* 1596 * Compile literal pattern into BMG tables 1597 */ 1598 static void 1599 bmgcomp(char *pat, int len) 1600 { 1601 int i; 1602 int tlen; 1603 unsigned char *uc = (unsigned char *)pat; 1604 1605 bmglen = len; 1606 bmgpat = pat; 1607 1608 for (i = 0; i < M_CSETSIZE; i++) { 1609 bmgtab[i] = len; 1610 } 1611 1612 len--; 1613 for (tlen = len, i = 0; i <= len; i++, tlen--) { 1614 bmgtab[*uc++] = tlen; 1615 } 1616 } 1617 1618 /* 1619 * BMG search. 1620 */ 1621 static char * 1622 bmgexec(char *str, char *end) 1623 { 1624 int t; 1625 char *k, *s, *p; 1626 1627 k = str + bmglen - 1; 1628 if (bmglen == 1) { 1629 return (memchr(str, bmgpat[0], end - str)); 1630 } 1631 for (; ; ) { 1632 /* inner loop, should be most optimized */ 1633 while (k < end && (t = bmgtab[(unsigned char)*k]) != 0) { 1634 k += t; 1635 } 1636 if (k >= end) { 1637 return (NULL); 1638 } 1639 for (s = k, p = bmgpat + bmglen - 1; *--s == *--p; ) { 1640 if (p == bmgpat) { 1641 return (s); 1642 } 1643 } 1644 k++; 1645 } 1646 /* NOTREACHED */ 1647 } 1648