2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.4 1995-01-24 16:00:21 adam
8 * Added -ansi to CFLAGS.
9 * Some changes to the dfa module.
11 * Revision 1.3 1994/10/04 17:46:43 adam
12 * Function options now returns arg with error option.
14 * Revision 1.2 1994/10/03 17:22:18 adam
15 * Optimization of grepper.
17 * Revision 1.1 1994/09/27 16:31:18 adam
18 * First version of grepper: grep with error correction.
32 static int show_line = 0;
34 typedef unsigned MatchWord;
38 int n; /* no of MatchWord needed */
39 int range; /* max no. of errors */
40 MatchWord *Sc; /* Mask Sc */
43 #define INFBUF_SIZE 16384
47 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
49 int off = state & (WORD_BITS-1);
50 int wno = state / WORD_BITS;
52 m[mc->n * ch + wno] |= 1<<off;
55 static INLINE void reset_bit (MatchContext *mc, MatchWord *m, int ch,
58 int off = state & (WORD_BITS-1);
59 int wno = state / WORD_BITS;
61 m[mc->n * ch + wno] &= ~(1<<off);
64 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
67 int off = state & (WORD_BITS-1);
68 int wno = state / WORD_BITS;
70 return m[mc->n * ch + wno] & (1<<off);
73 static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
75 MatchContext *mc = imalloc (sizeof(*mc));
78 mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
80 mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n);
82 for (i=0; i<dfa->no_states; i++)
85 struct DFA_state *state = dfa->states[i];
87 for (j=0; j<state->tran_no; j++)
90 int ch0 = state->trans[j].ch[0];
91 int ch1 = state->trans[j].ch[1];
92 assert (ch0 >= 0 && ch1 >= 0);
94 for (ch = ch0; ch <= ch1; ch++)
95 set_bit (mc, mc->Sc, ch, i);
102 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
103 struct DFA *dfa, int ch)
106 MatchWord *Rsrc_p = Rsrc, mask;
109 for (j = 1; j<mc->n; j++)
114 for (j = 0; j<WORD_BITS/4; j++)
120 struct DFA_state *state = dfa->states[s];
121 int i = state->tran_no;
123 if (ch >= state->trans[i].ch[0] &&
124 ch <= state->trans[i].ch[1])
125 set_bit (mc, Rdst, 0, state->trans[i].to);
129 struct DFA_state *state = dfa->states[s+1];
130 int i = state->tran_no;
132 if (ch >= state->trans[i].ch[0] &&
133 ch <= state->trans[i].ch[1])
134 set_bit (mc, Rdst, 0, state->trans[i].to);
138 struct DFA_state *state = dfa->states[s+2];
139 int i = state->tran_no;
141 if (ch >= state->trans[i].ch[0] &&
142 ch <= state->trans[i].ch[1])
143 set_bit (mc, Rdst, 0, state->trans[i].to);
147 struct DFA_state *state = dfa->states[s+3];
148 int i = state->tran_no;
150 if (ch >= state->trans[i].ch[0] &&
151 ch <= state->trans[i].ch[1])
152 set_bit (mc, Rdst, 0, state->trans[i].to);
156 if (s >= dfa->no_states)
163 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
167 MatchWord *Rsrc_p = Rsrc, mask;
168 for (j = 0; j<mc->n; j++)
173 for (j = 0; j<WORD_BITS/4; j++)
179 struct DFA_state *state = dfa->states[s];
180 int i = state->tran_no;
182 set_bit (mc, Rdst, 0, state->trans[i].to);
186 struct DFA_state *state = dfa->states[s+1];
187 int i = state->tran_no;
189 set_bit (mc, Rdst, 0, state->trans[i].to);
193 struct DFA_state *state = dfa->states[s+2];
194 int i = state->tran_no;
196 set_bit (mc, Rdst, 0, state->trans[i].to);
200 struct DFA_state *state = dfa->states[s+3];
201 int i = state->tran_no;
203 set_bit (mc, Rdst, 0, state->trans[i].to);
207 if (s >= dfa->no_states)
214 static void or (MatchContext *mc, MatchWord *Rdst,
215 MatchWord *Rsrc1, MatchWord *Rsrc2)
218 for (i = 0; i<mc->n; i++)
219 Rdst[i] = Rsrc1[i] | Rsrc2[i];
223 static int go (MatchContext *mc, struct DFA *dfa, FILE *inf)
225 MatchWord *Rj, *Rj1, *Rj_a, *Rj_b, *Rj_c;
232 infbuf = imalloc (INFBUF_SIZE);
234 Rj = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
235 Rj1 = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
236 Rj_a = icalloc (mc->n * sizeof(*Rj));
237 Rj_b = icalloc (mc->n * sizeof(*Rj));
238 Rj_c = icalloc (mc->n * sizeof(*Rj));
240 set_bit (mc, Rj, 0, 0);
241 for (d = 1; d<=mc->range; d++)
244 memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
245 for (s = 0; s<dfa->no_states; s++)
247 if (get_bit (mc, Rj, d-1, s))
249 struct DFA_state *state = dfa->states[s];
250 int i = state->tran_no;
252 set_bit (mc, Rj, d, state->trans[i].to);
256 while ((ch = getc (inf)) != EOF)
260 infbuf[inf_ptr] = ch;
267 printf ("%5d:", lineno);
272 } while (infbuf[i] != '\n');
275 if (++i == INFBUF_SIZE)
278 } while (infbuf[i] != '\n');
283 if (++inf_ptr == INFBUF_SIZE)
285 mask_shift (mc, Rj1, Rj, dfa, ch);
286 for (d = 1; d <= mc->range; d++)
288 mask_shift (mc, Rj_b, Rj+d*mc->n, dfa, ch); /* 1 */
290 or (mc, Rj_a, Rj+(d-1)*mc->n, Rj1+(d-1)*mc->n); /* 2,3 */
292 shift (mc, Rj_c, Rj_a, dfa);
294 or (mc, Rj_a, Rj_b, Rj_c); /* 1,2,3*/
296 or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n); /* 1,2,3,4 */
298 for (s = 0; s<dfa->no_states; s++)
300 if (dfa->states[s]->rule_no)
301 if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
304 for (d = 0; d <= mc->range; d++)
305 reset_bit (mc, Rj1+d*mc->n, 0, dfa->no_states);
319 static int grep_file (struct DFA *dfa, const char *fname, int range)
326 inf = fopen (fname, "r");
329 log (LOG_FATAL|LOG_ERRNO, "cannot open `%s'", fname);
336 mc = mk_MatchContext (dfa, range);
345 int main (int argc, char **argv)
350 char *pattern = NULL;
352 struct DFA *dfa = dfa_init();
355 while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2)
363 i = dfa_parse (dfa, &pattern);
366 fprintf (stderr, "%s: illegal pattern\n", prog);
374 grep_file (dfa, arg, range);
379 log_init (log_mask_str(arg), prog, NULL);
388 debug_dfa_followpos = 1;
401 log (LOG_FATAL, "Unknown option '-%s'", arg);
407 fprintf (stderr, "usage:\n "
408 " %s [-d] [-n] [-r n] [-s] [-v n] pattern file ..\n", prog);
411 else if (no_files == 0)
413 grep_file (dfa, NULL, range);