| 1 |
|
| /* |
| 2 |
|
| * wumanber_impl.c -- an efficient WuManber implementation. |
| 3 |
|
| * |
| 4 |
|
| * Copyright (C) 2010, Juergen Weigert, Novell inc. |
| 5 |
|
| * Distribute,modify under GPLv2 or GPLv3, or perl license. |
| 6 |
|
| * |
| 7 |
|
| * Loosly based on |
| 8 |
|
| * ftp://ftp.cs.arizona.edu/agrep/agrep-2.04.tar:mgrep.c |
| 9 |
|
| * which is timestamped 1992-04-11 |
| 10 |
|
| * |
| 11 |
|
| * The content of the COPYRIGHT file from the above package is included here |
| 12 |
|
| ------------------------------------------------------------------- |
| 13 |
|
| This material was developed by Sun Wu and Udi Manber |
| 14 |
|
| at the University of Arizona, Department of Computer Science. |
| 15 |
|
| Permission is granted to copy this software, to redistribute it |
| 16 |
|
| on a nonprofit basis, and to use it for any purpose, subject to |
| 17 |
|
| the following restrictions and understandings. |
| 18 |
|
| |
| 19 |
|
| 1. Any copy made of this software must include this copyright notice |
| 20 |
|
| in full. |
| 21 |
|
| |
| 22 |
|
| 2. All materials developed as a consequence of the use of this |
| 23 |
|
| software shall duly acknowledge such use, in accordance with the usual |
| 24 |
|
| standards of acknowledging credit in academic research. |
| 25 |
|
| |
| 26 |
|
| 3. The authors have made no warranty or representation that the |
| 27 |
|
| operation of this software will be error-free or suitable for any |
| 28 |
|
| application, and they are under under no obligation to provide any |
| 29 |
|
| services, by way of maintenance, update, or otherwise. The software |
| 30 |
|
| is an experimental prototype offered on an as-is basis. |
| 31 |
|
| |
| 32 |
|
| 4. Redistribution for profit requires the express, written permission |
| 33 |
|
| of the authors. |
| 34 |
|
| |
| 35 |
|
| ------------------------------------------------------------------- |
| 36 |
|
| * |
| 37 |
|
| * NOTE: modern agrep from libtre5 does not have the -f option and no |
| 38 |
|
| * comparable multi pattern search capability. Therefore I am transporting this |
| 39 |
|
| * code 18 years into the future. Are we really that old? |
| 40 |
|
| * |
| 41 |
|
| * My version of this code reworks the API and the behaviour when a match is |
| 42 |
|
| * found. |
| 43 |
|
| * - made -Wall silent |
| 44 |
|
| * - made run standalone |
| 45 |
|
| * - do not skip to end of line, when a match is found. |
| 46 |
|
| * - allow multiple matches on the same location. |
| 47 |
|
| * - memory based, no longer slurp in chunks of a file. |
| 48 |
|
| * - clean API, call prep_pat() with a list of patterns, then |
| 49 |
|
| * call search_init() and search_text() with the text string. |
| 50 |
|
| * - allow for a dynamic wm object, no more global statics. |
| 51 |
|
| * - removed most arbitrary size limits. Used calloc. |
| 52 |
|
| * |
| 53 |
|
| * 2010-01-10, jw@suse.de |
| 54 |
|
| * |
| 55 |
|
| * TODO: find out, why not all possible matches are found in wm_bs3()/wm_bs1() |
| 56 |
|
| * maybe, a loop is aborted, during hash lookup? |
| 57 |
|
| */ |
| 58 |
|
| |
| 59 |
|
| /* Copyright (c) 1991 Sun Wu and Udi Manber. All Rights Reserved. */ |
| 60 |
|
| /* multipattern matcher */ |
| 61 |
|
| #include <stdio.h> |
| 62 |
|
| #include <ctype.h> |
| 63 |
|
| #include <string.h> // strlen() and friends. |
| 64 |
|
| #include <stdlib.h> // exit() |
| 65 |
|
| #include <unistd.h> // read() |
| 66 |
|
| #include <sys/types.h> // O_RDONLY |
| 67 |
|
| #include <sys/stat.h> // O_RDONLY |
| 68 |
|
| #include <fcntl.h> // open() |
| 69 |
|
| #include <errno.h> // errno, strerror() |
| 70 |
|
| #include "wumanber_impl.h" // assert correct prototypes |
| 71 |
|
| |
| 72 |
|
| #ifndef STANDALONE |
| 73 |
|
| # define STANDALONE 1 // use own main() below. |
| 74 |
|
| #endif |
| 75 |
|
| |
| 76 |
|
| static void f_prep(struct WuManber *wm, int pat_index, unsigned char *Pattern); |
| 77 |
|
| static void wm_bs1(struct WuManber *wm, unsigned char *text, int end); |
| 78 |
|
| static void wm_bs3(struct WuManber *wm, unsigned char *text, int end); |
| 79 |
|
| |
| 80 |
|
| // search_init() must be called after prep_pat() but before search_text() |
| 81 |
1 |
| void search_init(struct WuManber *wm, char *name) |
| 82 |
|
| { |
| 83 |
|
| // match_word_boundaries, match_whole_line, nocase are initialized in prep_pat() |
| 84 |
|
| |
| 85 |
1 |
| wm->one_match_per_line = 0; |
| 86 |
1 |
| wm->one_match_per_offset = 0; |
| 87 |
1 |
| wm->cb = NULL; |
| 88 |
|
| |
| 89 |
1 |
| } |
| 90 |
|
| |
| 91 |
|
| /* |
| 92 |
|
| * pat_p[0]=NULL; pat_p[n_pat+1]=NULL recommended, |
| 93 |
|
| * pat_p[1]...pat_p[n_pat] are valid entries |
| 94 |
|
| */ |
| 95 |
1 |
| void prep_pat(struct WuManber *wm, int n_pat, unsigned char **pat_p, int nocase) |
| 96 |
|
| { |
| 97 |
|
| #if HAVE_WORDBOUND_OR_WHOLELINE |
| 98 |
|
| wm->match_word_boundaries = 0; |
| 99 |
|
| #endif |
| 100 |
1 |
| wm->nocase = nocase; |
| 101 |
1 |
| wm->patt = pat_p; |
| 102 |
1 |
| wm->n_pat = n_pat; |
| 103 |
1 |
| wm->use_bs3 = 0; |
| 104 |
1 |
| wm->use_bs1 = 0; |
| 105 |
|
| |
| 106 |
|
| # if HAVE_WORDBOUND_OR_WHOLELINE |
| 107 |
|
| i = 0; p=1; |
| 108 |
|
| while(i<length) { |
| 109 |
|
| patt[p] = pat_ptr; |
| 110 |
|
| if(wm->match_word_boundaries) *pat_ptr++ = W_DELIM; |
| 111 |
|
| if(wm->match_whole_line) *pat_ptr++ = L_DELIM; |
| 112 |
|
| while((*pat_ptr = buf[i++]) != '\n') pat_ptr++; |
| 113 |
|
| if(wm->match_word_boundaries) *pat_ptr++ = W_DELIM; |
| 114 |
|
| if(wm->match_whole_line) *pat_ptr++ = L_DELIM; /* Can't be both on */ |
| 115 |
|
| *pat_ptr++ = 0; |
| 116 |
|
| p++; |
| 117 |
|
| } |
| 118 |
|
| #endif |
| 119 |
|
| |
| 120 |
1 |
| unsigned Mask = 15; |
| 121 |
|
| int i; |
| 122 |
257 |
▶ | for(i=0; i< N_SYMB; i++) wm->tr[i] = i; |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0; i< N_SYMB; i++) wm->tr[i] = i; |
256 |
1 |
257 |
|
| 123 |
1 |
▶ | if(wm->nocase) { |
Branch: 1 branch
| Branch | True | False | Total |
| if(wm->nocase) { |
1 |
0 |
1 |
|
| 124 |
27 |
▶ | for(i='A'; i<= 'Z'; i++) wm->tr[i] = i + 'a' - 'A'; |
Branch: 1 branch
| Branch | True | False | Total |
| for(i='A'; i<= 'Z'; i++) wm->tr[i] = i + 'a' - 'A'; |
26 |
1 |
27 |
|
| 125 |
|
| } |
| 126 |
|
| #if HAVE_WORDBOUND_OR_WHOLELINE |
| 127 |
|
| if(wm->match_word_boundaries) { |
| 128 |
|
| for(i=0; i<128; i++) if(!isalnum(i)) wm->tr[i] = W_DELIM; |
| 129 |
|
| } |
| 130 |
|
| #endif |
| 131 |
257 |
▶ | for(i=0; i< N_SYMB; i++) wm->tr1[i] = wm->tr[i]&Mask; |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0; i< N_SYMB; i++) wm->tr1[i] = wm->tr[i]&Mask; |
256 |
1 |
257 |
|
| 132 |
|
| |
| 133 |
1 |
| wm->pat_len = (unsigned int *)calloc(n_pat+2, sizeof(unsigned int)); |
| 134 |
|
| |
| 135 |
1 |
| wm->p_size = 255; // max that fits in shift_min[] entries. |
| 136 |
14 |
▶ | for(i=1 ; i <= wm->n_pat; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=1 ; i <= wm->n_pat; i++) |
13 |
1 |
14 |
|
| 137 |
|
| { |
| 138 |
13 |
| int l = strlen((char *)wm->patt[i]); |
| 139 |
13 |
| wm->pat_len[i] = l; |
| 140 |
13 |
▶ | if (l!=0 && l < wm->p_size) wm->p_size = l; |
Branch: 2 branches
| Branch | True | False | Total |
| if (l!=0 && l < wm->p_size) wm->p_size = l; |
13 |
0 |
13 |
| if (l!=0 && l < wm->p_size) wm->p_size = l; |
5 |
8 |
13 |
|
| 141 |
|
| } |
| 142 |
1 |
▶ | if (wm->p_size == 0) |
Branch: 1 branch
| Branch | True | False | Total |
| if (wm->p_size == 0) |
0 |
1 |
1 |
|
| 143 |
|
| { |
| 144 |
0 |
| fprintf(stderr, "%s: the pattern file is empty\n", wm->progname); |
| 145 |
0 |
| exit(2); |
| 146 |
|
| } |
| 147 |
1 |
▶ | if (n_pat > 100 && wm->p_size > 2) wm->use_bs3 = 1; |
Branch: 2 branches
| Branch | True | False | Total |
| if (n_pat > 100 && wm->p_size > 2) wm->use_bs3 = 1; |
0 |
1 |
1 |
| if (n_pat > 100 && wm->p_size > 2) wm->use_bs3 = 1; |
0 |
0 |
0 |
|
| 148 |
1 |
▶ | if (wm->p_size == 1) wm->use_bs1 = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (wm->p_size == 1) wm->use_bs1 = 1; |
0 |
1 |
1 |
|
| 149 |
4097 |
▶ | for (i=0; i<SHIFT_SZ; i++) wm->shift_min[i] = wm->p_size - 2; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i=0; i<SHIFT_SZ; i++) wm->shift_min[i] = wm->p_size - 2; |
4096 |
1 |
4097 |
|
| 150 |
8193 |
▶ | for (i=0; i<PAT_HASH_SZ; i++) wm->pat_hash[i] = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i=0; i<PAT_HASH_SZ; i++) wm->pat_hash[i] = 0; |
8192 |
1 |
8193 |
|
| 151 |
14 |
▶ | for (i=1; i<= n_pat; i++) f_prep(wm, i, wm->patt[i]); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i=1; i<= n_pat; i++) f_prep(wm, i, wm->patt[i]); |
13 |
1 |
14 |
|
| 152 |
1 |
| } |
| 153 |
|
| |
| 154 |
|
| |
| 155 |
|
| #if 0 |
| 156 |
|
| void mgrep(struct WuManber *wm, int fd) |
| 157 |
|
| { |
| 158 |
|
| #define MAXLINE 1024 |
| 159 |
|
| #define BLOCKSIZE 8192 |
| 160 |
|
| char r_newline = '\n'; |
| 161 |
|
| unsigned char text[2*BLOCKSIZE+MAXLINE]; |
| 162 |
|
| int buf_end, num_read, start, end, residue = 0; |
| 163 |
|
| |
| 164 |
|
| text[MAXLINE-1] = '\n'; /* initial case */ |
| 165 |
|
| start = MAXLINE-1; |
| 166 |
|
| |
| 167 |
|
| while( (num_read = read(fd, text+MAXLINE, BLOCKSIZE)) > 0) |
| 168 |
|
| { |
| 169 |
|
| buf_end = end = MAXLINE + num_read -1 ; |
| 170 |
|
| while(text[end] != r_newline && end > MAXLINE) end--; |
| 171 |
|
| residue = buf_end - end + 1 ; |
| 172 |
|
| text[start-1] = r_newline; |
| 173 |
|
| if(use_bs1) wm_bs1(wm, text, start, end); |
| 174 |
|
| else wm_bs3(wm, text, start, end); |
| 175 |
|
| start = MAXLINE - residue; |
| 176 |
|
| if(start < 0) { |
| 177 |
|
| start = 1; |
| 178 |
|
| } |
| 179 |
|
| strncpy((char *)text+start, (char *)text+end, residue); |
| 180 |
|
| } /* end of while(num_read = ... */ |
| 181 |
|
| text[MAXLINE] = '\n'; |
| 182 |
|
| text[start-1] = '\n'; |
| 183 |
|
| if(residue > 1) { |
| 184 |
|
| if(use_bs1) wm_bs1(wm, text, start, end); |
| 185 |
|
| else wm_bs3(wm, text, start, end); |
| 186 |
|
| } |
| 187 |
|
| return; |
| 188 |
|
| } /* end mgrep */ |
| 189 |
|
| #endif |
| 190 |
|
| |
| 191 |
1 |
| static void wm_bs3(struct WuManber *wm, unsigned char *text, int end) |
| 192 |
|
| { |
| 193 |
1 |
| unsigned char *textstart = text; |
| 194 |
1 |
| unsigned char *textend = text + end; |
| 195 |
|
| unsigned char shift; |
| 196 |
|
| |
| 197 |
|
| unsigned int hash, i, m1, j; |
| 198 |
1 |
| int Long = wm->use_bs3; |
| 199 |
|
| int pat_index; |
| 200 |
1 |
| int m = wm->p_size; |
| 201 |
1 |
| int MATCHED = 0; |
| 202 |
1 |
| int ONE_MATCH_PER_LINE = wm->one_match_per_line; |
| 203 |
1 |
| int ONE_MATCH_PER_OFFSET = wm->one_match_per_offset; |
| 204 |
1 |
| unsigned char *tr = wm->tr; |
| 205 |
1 |
| unsigned char *tr1 = wm->tr1; |
| 206 |
|
| |
| 207 |
|
| unsigned char *qx; |
| 208 |
|
| struct pat_list *p; |
| 209 |
|
| |
| 210 |
1 |
| m1 = m - 1; |
| 211 |
1 |
| text = text + m1; |
| 212 |
400 |
▶ | while (text <= textend) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (text <= textend) { |
399 |
1 |
400 |
|
| 213 |
399 |
| hash=tr1[*text]; |
| 214 |
399 |
| hash=(hash<<4)+(tr1[*(text-1)]); |
| 215 |
399 |
▶ | if(Long) hash=(hash<<4)+(tr1[*(text-2)]); |
Branch: 1 branch
| Branch | True | False | Total |
| if(Long) hash=(hash<<4)+(tr1[*(text-2)]); |
0 |
399 |
399 |
|
| 216 |
399 |
| shift = wm->shift_min[hash]; |
| 217 |
399 |
▶ | if(shift == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if(shift == 0) { |
67 |
332 |
399 |
|
| 218 |
|
| // text points to the m'th char of a candidate pattern |
| 219 |
67 |
| hash=0; |
| 220 |
402 |
▶ | for(i=0;i<=m1;i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(i=0;i<=m1;i++) { |
335 |
67 |
402 |
|
| 221 |
335 |
| hash=(hash<<4)+(tr1[*(text-i)]); |
| 222 |
|
| } |
| 223 |
67 |
| hash=hash&(PAT_HASH_SZ-1); |
| 224 |
67 |
| p = wm->pat_hash[hash]; |
| 225 |
89 |
▶ | while(p != 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| while(p != 0) { |
22 |
67 |
89 |
|
| 226 |
22 |
| pat_index = p->index; |
| 227 |
22 |
| p = p->next; |
| 228 |
22 |
| qx = text-m1; |
| 229 |
|
| #if DANGEROUS_BEANS |
| 230 |
|
| // This code may read across array bounds. |
| 231 |
|
| // It performs 10% better in one of my test cases. |
| 232 |
|
| j = 0; |
| 233 |
|
| while(tr[wm->patt[pat_index][j]] == tr[*(qx++)]) j++; |
| 234 |
|
| if (j > m1 ) { |
| 235 |
|
| if(wm->pat_len[pat_index] <= j) { |
| 236 |
|
| if(text > textend) return; |
| 237 |
|
| #else |
| 238 |
22 |
▶ | if (text > textend) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (text > textend) return; |
0 |
22 |
22 |
|
| 239 |
22 |
| int l = wm->pat_len[pat_index]; |
| 240 |
22 |
▶ | if (qx+l <= textend) |
Branch: 1 branch
| Branch | True | False | Total |
| if (qx+l <= textend) |
22 |
0 |
22 |
|
| 241 |
|
| { |
| 242 |
22 |
| j = 0; |
| 243 |
|
| // not checking tr[] when not needed also saves 10% |
| 244 |
22 |
▶ | if (wm->nocase |
Branch: 1 branch
| Branch | True | False | Total |
| if (wm->nocase |
22 |
0 |
22 |
|
| 245 |
|
| #if HAVE_WORDBOUND_OR_WHOLELINE |
| 246 |
|
| || wm->match_word_boundaries || wm->match_whole_line |
| 247 |
|
| #endif |
| 248 |
|
| ) |
| 249 |
138 |
▶ | while ((--l>=0) && (tr[wm->patt[pat_index][l]] == tr[qx[l]])) ; |
Branch: 2 branches
| Branch | True | False | Total |
| while ((--l>=0) && (tr[wm->patt[pat_index][l]] == tr[qx[l]])) ; |
122 |
16 |
138 |
| while ((--l>=0) && (tr[wm->patt[pat_index][l]] == tr[qx[l]])) ; |
116 |
6 |
122 |
|
| 250 |
|
| else |
| 251 |
0 |
▶ | while ((--l>=0) && ( wm->patt[pat_index][l] == qx[l])) ; |
Branch: 2 branches
| Branch | True | False | Total |
| while ((--l>=0) && ( wm->patt[pat_index][l] == qx[l])) ; |
0 |
0 |
0 |
| while ((--l>=0) && ( wm->patt[pat_index][l] == qx[l])) ; |
0 |
0 |
0 |
|
| 252 |
22 |
▶ | if (l < 0) |
Branch: 1 branch
| Branch | True | False | Total |
| if (l < 0) |
16 |
6 |
22 |
|
| 253 |
|
| { |
| 254 |
|
| #endif |
| 255 |
16 |
| wm->n_matches++; |
| 256 |
16 |
| MATCHED=1; |
| 257 |
16 |
▶ | if (wm->cb) wm->cb(pat_index, text-textstart-m1, wm->cb_data); |
Branch: 1 branch
| Branch | True | False | Total |
| if (wm->cb) wm->cb(pat_index, text-textstart-m1, wm->cb_data); |
16 |
0 |
16 |
|
| 258 |
16 |
▶ | if (ONE_MATCH_PER_LINE) while (*text != '\n') text++; |
Branch: 2 branches
| Branch | True | False | Total |
| if (ONE_MATCH_PER_LINE) while (*text != '\n') text++; |
0 |
16 |
16 |
| if (ONE_MATCH_PER_LINE) while (*text != '\n') text++; |
0 |
0 |
0 |
|
| 259 |
|
| } |
| 260 |
|
| } |
| 261 |
22 |
▶ | if (ONE_MATCH_PER_OFFSET && MATCHED) break; |
Branch: 2 branches
| Branch | True | False | Total |
| if (ONE_MATCH_PER_OFFSET && MATCHED) break; |
0 |
22 |
22 |
| if (ONE_MATCH_PER_OFFSET && MATCHED) break; |
0 |
0 |
0 |
|
| 262 |
|
| } |
| 263 |
67 |
| MATCHED = 0; |
| 264 |
67 |
| shift = 1; // take care of overlapping matches |
| 265 |
|
| } |
| 266 |
399 |
| text = text + shift; |
| 267 |
|
| } |
| 268 |
|
| } |
| 269 |
|
| |
| 270 |
0 |
| static void wm_bs1(struct WuManber *wm, unsigned char *text, int end) |
| 271 |
|
| { |
| 272 |
0 |
| unsigned char *textend = text + end; |
| 273 |
0 |
| unsigned char *textstart = text; |
| 274 |
|
| int j; |
| 275 |
|
| struct pat_list *p; |
| 276 |
|
| int pat_index; |
| 277 |
0 |
| int MATCHED=0; |
| 278 |
0 |
| int ONE_MATCH_PER_LINE = wm->one_match_per_line; |
| 279 |
0 |
| int ONE_MATCH_PER_OFFSET = wm->one_match_per_offset; |
| 280 |
0 |
| unsigned char *tr = wm->tr; |
| 281 |
|
| unsigned char *qx; |
| 282 |
|
| |
| 283 |
0 |
| text = text - 1; |
| 284 |
0 |
▶ | while (++text <= textend) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (++text <= textend) { |
0 |
0 |
0 |
|
| 285 |
0 |
| p = wm->pat_hash[*text]; |
| 286 |
0 |
▶ | while(p != 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| while(p != 0) { |
0 |
0 |
0 |
|
| 287 |
0 |
| pat_index = p->index; |
| 288 |
0 |
| p = p->next; |
| 289 |
0 |
| qx = text; |
| 290 |
0 |
| j = 0; |
| 291 |
0 |
▶ | while(tr[wm->patt[pat_index][j]] == tr[*(qx++)]) j++; |
Branch: 1 branch
| Branch | True | False | Total |
| while(tr[wm->patt[pat_index][j]] == tr[*(qx++)]) j++; |
0 |
0 |
0 |
|
| 292 |
0 |
▶ | if(wm->pat_len[pat_index] <= j) { |
Branch: 1 branch
| Branch | True | False | Total |
| if(wm->pat_len[pat_index] <= j) { |
0 |
0 |
0 |
|
| 293 |
0 |
▶ | if(text >= textend) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if(text >= textend) return; |
0 |
0 |
0 |
|
| 294 |
0 |
| wm->n_matches++; |
| 295 |
0 |
▶ | if (wm->cb) wm->cb(pat_index, text-textstart, wm->cb_data); |
Branch: 1 branch
| Branch | True | False | Total |
| if (wm->cb) wm->cb(pat_index, text-textstart, wm->cb_data); |
0 |
0 |
0 |
|
| 296 |
0 |
▶ | if (ONE_MATCH_PER_LINE) while (*text != '\n') text++; |
Branch: 2 branches
| Branch | True | False | Total |
| if (ONE_MATCH_PER_LINE) while (*text != '\n') text++; |
0 |
0 |
0 |
| if (ONE_MATCH_PER_LINE) while (*text != '\n') text++; |
0 |
0 |
0 |
|
| 297 |
|
| } |
| 298 |
0 |
▶ | if (ONE_MATCH_PER_OFFSET && MATCHED) break; |
Branch: 2 branches
| Branch | True | False | Total |
| if (ONE_MATCH_PER_OFFSET && MATCHED) break; |
0 |
0 |
0 |
| if (ONE_MATCH_PER_OFFSET && MATCHED) break; |
0 |
0 |
0 |
|
| 299 |
|
| } |
| 300 |
0 |
| MATCHED = 0; |
| 301 |
|
| } /* while */ |
| 302 |
|
| } |
| 303 |
|
| |
| 304 |
|
| static void |
| 305 |
13 |
| f_prep(struct WuManber *wm, int pat_index, unsigned char *Pattern) |
| 306 |
|
| { |
| 307 |
|
| int i, m; |
| 308 |
|
| struct pat_list *pt, *qt; |
| 309 |
13 |
| unsigned hash, Mask=15; |
| 310 |
13 |
| m = wm->p_size; |
| 311 |
65 |
▶ | for (i = m-1; i>=(1+wm->use_bs3); i--) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = m-1; i>=(1+wm->use_bs3); i--) { |
52 |
13 |
65 |
|
| 312 |
52 |
| hash = (Pattern[i] & Mask); |
| 313 |
52 |
| hash = (hash << 4) + (Pattern[i-1]& Mask); |
| 314 |
52 |
▶ | if(wm->use_bs3) hash = (hash << 4) + (Pattern[i-2] & Mask); |
Branch: 1 branch
| Branch | True | False | Total |
| if(wm->use_bs3) hash = (hash << 4) + (Pattern[i-2] & Mask); |
0 |
52 |
52 |
|
| 315 |
52 |
▶ | if(wm->shift_min[hash] >= m-1-i) wm->shift_min[hash] = m-1-i; |
Branch: 1 branch
| Branch | True | False | Total |
| if(wm->shift_min[hash] >= m-1-i) wm->shift_min[hash] = m-1-i; |
47 |
5 |
52 |
|
| 316 |
|
| } |
| 317 |
13 |
▶ | if(wm->use_bs1) Mask = 255; /* 011111111 */ |
Branch: 1 branch
| Branch | True | False | Total |
| if(wm->use_bs1) Mask = 255; /* 011111111 */ |
0 |
13 |
13 |
|
| 318 |
13 |
| hash = 0; |
| 319 |
78 |
▶ | for(i = m-1; i>=0; i--) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(i = m-1; i>=0; i--) { |
65 |
13 |
78 |
|
| 320 |
65 |
| hash = (hash << 4) + (wm->tr[Pattern[i]]&Mask); |
| 321 |
|
| } |
| 322 |
13 |
| hash=hash&(PAT_HASH_SZ-1); |
| 323 |
13 |
| qt = (struct pat_list *) malloc(sizeof(struct pat_list)); |
| 324 |
13 |
| qt->index = pat_index; |
| 325 |
13 |
| pt = wm->pat_hash[hash]; |
| 326 |
13 |
| qt->next = pt; |
| 327 |
13 |
| wm->pat_hash[hash] = qt; |
| 328 |
13 |
| } |
| 329 |
|
| |
| 330 |
1 |
| unsigned int search_text(struct WuManber *wm, unsigned char *text, int end) |
| 331 |
|
| { |
| 332 |
1 |
| wm->n_matches = 0; |
| 333 |
1 |
▶ | if (wm->use_bs1) wm_bs1(wm, text, end); |
Branch: 1 branch
| Branch | True | False | Total |
| if (wm->use_bs1) wm_bs1(wm, text, end); |
0 |
1 |
1 |
|
| 334 |
1 |
| else wm_bs3(wm, text, end); |
| 335 |
|
| |
| 336 |
|
| // mgrep(wm, text, text_len); |
| 337 |
1 |
| return wm->n_matches; |
| 338 |
|
| } |
| 339 |
|
| |
| 340 |
|
| #if STANDALONE |
| 341 |
|
| static unsigned int pat_count[4*PAT_HASH_SZ]; |
| 342 |
|
| static int distinct_count; |
| 343 |
0 |
| static void count_em(unsigned int idx, unsigned long offset, void *data) |
| 344 |
|
| { |
| 345 |
0 |
▶ | if (idx < 4*PAT_HASH_SZ && !pat_count[idx]++) |
Branch: 2 branches
| Branch | True | False | Total |
| if (idx < 4*PAT_HASH_SZ && !pat_count[idx]++) |
0 |
0 |
0 |
| if (idx < 4*PAT_HASH_SZ && !pat_count[idx]++) |
0 |
0 |
0 |
|
| 346 |
0 |
| distinct_count++; |
| 347 |
0 |
| printf("offset=%ld: idx=%d, '%s'\n", offset, idx, ((unsigned char **)data)[idx]); |
| 348 |
0 |
| } |
| 349 |
|
| |
| 350 |
|
| static unsigned char * |
| 351 |
0 |
| load_file(char *filename, char *progname, int *lenp) |
| 352 |
|
| { |
| 353 |
|
| struct stat st; |
| 354 |
|
| int fp; |
| 355 |
|
| |
| 356 |
0 |
▶ | if ((fp = open(filename, O_RDONLY)) < 0) |
Branch: 1 branch
| Branch | True | False | Total |
| if ((fp = open(filename, O_RDONLY)) < 0) |
0 |
0 |
0 |
|
| 357 |
|
| { |
| 358 |
0 |
| fprintf(stderr, "%s: Cannot open file %s: %s\n", progname, filename, strerror(errno)); |
| 359 |
0 |
| exit(3); |
| 360 |
|
| } |
| 361 |
0 |
| fstat(fp, &st); |
| 362 |
0 |
| unsigned char *buf = (unsigned char *)calloc(st.st_size+2, sizeof(unsigned char)); |
| 363 |
|
| |
| 364 |
0 |
| int length = 0; |
| 365 |
|
| int num_read; |
| 366 |
0 |
▶ | while((num_read = read(fp, buf+length, 8192)) > 0) |
Branch: 1 branch
| Branch | True | False | Total |
| while((num_read = read(fp, buf+length, 8192)) > 0) |
0 |
0 |
0 |
|
| 367 |
|
| { |
| 368 |
0 |
| length = length + num_read; |
| 369 |
|
| } |
| 370 |
0 |
| close(fp); |
| 371 |
0 |
| buf[length] = '\0'; |
| 372 |
|
| |
| 373 |
0 |
▶ | if (lenp) *lenp = length; |
Branch: 1 branch
| Branch | True | False | Total |
| if (lenp) *lenp = length; |
0 |
0 |
0 |
|
| 374 |
0 |
| return buf; |
| 375 |
|
| } |
| 376 |
|
| |
| 377 |
|
| static unsigned char ** |
| 378 |
0 |
| load_pat_list(char *filename, char *progname, int *npat) |
| 379 |
|
| { |
| 380 |
0 |
| int length=0, i; |
| 381 |
0 |
| unsigned char *buf = load_file(filename, progname, &length); |
| 382 |
|
| |
| 383 |
0 |
| int n_pat = 0; |
| 384 |
0 |
▶ | for (i = 0; i <= length; i++) if (buf[i] == '\n') n_pat++; |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i <= length; i++) if (buf[i] == '\n') n_pat++; |
0 |
0 |
0 |
| for (i = 0; i <= length; i++) if (buf[i] == '\n') n_pat++; |
0 |
0 |
0 |
|
| 385 |
|
| |
| 386 |
0 |
| unsigned char **ppat = (unsigned char **)calloc(n_pat+2, sizeof(char *)); |
| 387 |
0 |
| int p = 0; |
| 388 |
0 |
| ppat[p++] = buf; |
| 389 |
0 |
▶ | for (i = 0; i <= length; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i <= length; i++) |
0 |
0 |
0 |
|
| 390 |
|
| { |
| 391 |
0 |
▶ | if (buf[i] == '\n') |
Branch: 1 branch
| Branch | True | False | Total |
| if (buf[i] == '\n') |
0 |
0 |
0 |
|
| 392 |
|
| { |
| 393 |
0 |
| buf[i] = '\0'; |
| 394 |
0 |
| ppat[p++] = buf+i+1; |
| 395 |
|
| } |
| 396 |
|
| } |
| 397 |
0 |
| ppat[p] = NULL; |
| 398 |
|
| |
| 399 |
0 |
▶ | if (p>4*PAT_HASH_SZ) |
Branch: 1 branch
| Branch | True | False | Total |
| if (p>4*PAT_HASH_SZ) |
0 |
0 |
0 |
|
| 400 |
|
| { |
| 401 |
0 |
| fprintf(stderr, "%s: suggested maximum number of patterns is %d, using %d\n", progname, 4*PAT_HASH_SZ, p); |
| 402 |
|
| } |
| 403 |
|
| |
| 404 |
0 |
▶ | if (npat) *npat = n_pat; |
Branch: 1 branch
| Branch | True | False | Total |
| if (npat) *npat = n_pat; |
0 |
0 |
0 |
|
| 405 |
0 |
| return ppat; |
| 406 |
|
| } |
| 407 |
|
| |
| 408 |
0 |
| int main(int argc, char **argv) |
| 409 |
|
| { |
| 410 |
|
| struct WuManber wm; |
| 411 |
|
| |
| 412 |
0 |
| wm.progname = argv[0]; |
| 413 |
0 |
| wm.nocase = 0; |
| 414 |
|
| |
| 415 |
0 |
▶ | if (argc > 2 && !strcmp(argv[1], "-n")) |
Branch: 2 branches
| Branch | True | False | Total |
| if (argc > 2 && !strcmp(argv[1], "-n")) |
0 |
0 |
0 |
| if (argc > 2 && !strcmp(argv[1], "-n")) |
0 |
0 |
0 |
|
| 416 |
|
| { |
| 417 |
0 |
| wm.nocase = 1; |
| 418 |
0 |
| argv++; argc--; |
| 419 |
|
| } |
| 420 |
|
| |
| 421 |
0 |
▶ | if (argc < 2) |
Branch: 1 branch
| Branch | True | False | Total |
| if (argc < 2) |
0 |
0 |
0 |
|
| 422 |
|
| { |
| 423 |
0 |
| fprintf(stderr, "Usage: %s patterns_file text_file\n", wm.progname); |
| 424 |
0 |
| fprintf(stderr, "\n patterns_file is a newline seperated file of exact patterns\n"); |
| 425 |
0 |
| exit(1); |
| 426 |
|
| } |
| 427 |
|
| |
| 428 |
0 |
| int n_pat = 0; |
| 429 |
0 |
| unsigned char **pat_list = load_pat_list(argv[1], wm.progname, &n_pat); |
| 430 |
|
| |
| 431 |
0 |
| int text_len = 0; |
| 432 |
0 |
| unsigned char *text = load_file(argv[2], wm.progname, &text_len); |
| 433 |
|
| |
| 434 |
0 |
| prep_pat(&wm, n_pat, --pat_list, wm.nocase); |
| 435 |
0 |
| search_init(&wm, wm.progname); |
| 436 |
0 |
| wm.cb = count_em; |
| 437 |
0 |
| wm.cb_data = (void *)pat_list; |
| 438 |
0 |
| search_text(&wm, text, text_len); |
| 439 |
|
| |
| 440 |
0 |
| printf("words:%d %d\n", distinct_count, wm.n_matches); |
| 441 |
0 |
| exit(wm.n_matches?0:1); |
| 442 |
|
| } |
| 443 |
|
| #endif |