1 /** \file bogogrep.c
2 *
3 * This file emulates GNU grep -ab with a plain text pattern anchored to
4 * the left. The Horspool search was taken from a publicly available
5 * version on the Internet.
6 *
7 * The rest of the program was written by Matthias Andree and is public
8 * domain.
9 */
10
11 #include <string.h>
12 #include <stdio.h>
13 #include <stdlib.h>
14
15 #include <sys/types.h>
16 #include <sys/mman.h>
17 #include <sys/stat.h>
18 #include <unistd.h>
19 #include <fcntl.h>
20
21 #ifndef MAP_FAILED
22 #define MAP_FAILED ((void *) -1)
23 #endif
24
25 #if !defined(__GNUC__)
26 #define __attribute__(a)
27 #endif
28
29 #define ALPHABET 256
30
31 /* vanilla Boyer-Moore-Horspool */
search(const unsigned char * text,const unsigned char * pat,long n)32 static const unsigned char *search(const unsigned char *text,
33 const unsigned char *pat, long n)
34 {
35 long i, j, k, m, skip[ALPHABET];
36
37 m = strlen((const char *)pat);
38 if (m == 0)
39 return (text);
40 for (k = 0; k < ALPHABET; k++)
41 skip[k] = m;
42 for (k = 0; k < m - 1; k++)
43 skip[pat[k]] = m - k - 1;
44
45 for (k = m - 1; k < n; k += skip[text[k] & (ALPHABET - 1)]) {
46 for (j = m - 1, i = k; j >= 0 && text[i] == pat[j]; j--)
47 i--;
48 if (j == (-1))
49 return (text + i + 1);
50 }
51 return (NULL);
52 }
53
54 static void usage(int rc, const char *tag) __attribute__((noreturn)) ;
usage(int rc,const char * tag)55 static void usage(int rc, const char *tag) {
56 fprintf(stderr, "Usage: %s searchstring regular_file [...]\n"
57 "This program searches all lines in regular_file that start with searchstring.\n"
58 "For each match, it prints the byte offset (starting with 0), a colon and the\n"
59 "the matching line.\n", tag);
60 exit(rc);
61 }
62
main(int argc,char ** argv)63 int main(int argc, char **argv) {
64 int fd;
65 unsigned char *base;
66 const unsigned char *i;
67 struct stat st;
68 int argindex; /* file name in argv[] vector */
69 int rc = 0;
70
71 if (argc < 3) usage(1, argv[0]);
72
73 for(argindex = 2; argindex < argc; argindex++) {
74 if ((fd = open(argv[argindex], O_RDONLY)) < 0) {
75 perror(argv[argindex]);
76 rc = 1;
77 continue;
78 }
79
80 if (fstat(fd, &st)) {
81 perror(argv[argindex]);
82 close(fd);
83 rc = 1;
84 continue;
85 }
86
87 if (MAP_FAILED == (base = (unsigned char *)mmap(NULL, st.st_size,
88 PROT_READ, MAP_SHARED, fd, 0))) {
89 perror("mmap");
90 close(fd);
91 rc = 1;
92 continue;
93 }
94
95 i = base;
96 while(NULL != (i = search((const unsigned char *)i,
97 (unsigned char *)argv[1],
98 base - i + st.st_size))) {
99 if (i == base || *(i-1) == '\n') {
100 /** \bug FIXME: dead assignments here */
101 int l = strcspn((const char *)i, "\n");
102
103 if (l > base - i + st.st_size) l = base - i + st.st_size;
104 printf("%ld:", (long)(i - base));
105 (void) fwrite(i, 1, strcspn((const char *)i, "\n"), stdout);
106 if (EOF == puts("")) {
107 perror("stdout");
108 exit(2);
109 }
110 }
111 i += strlen(argv[1]);
112 }
113
114 if (munmap((char *)base, st.st_size)) {
115 perror("munmap");
116 rc = 1;
117 }
118 if (close(fd)) {
119 perror("close");
120 rc = 1;
121 }
122 }
123 if (fflush(stdout)) {
124 perror("stdout");
125 rc = 2;
126 }
127 exit(rc);
128 }
129