2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.2 1994-10-03 17:22:18 adam
8 * Optimization of grepper.
10 * Revision 1.1 1994/09/27 16:31:18 adam
11 * First version of grepper: grep with error correction.
25 static int show_line = 0;
27 typedef unsigned MatchWord;
31 int n; /* no of MatchWord needed */
32 int range; /* max no. of errors */
33 MatchWord *Sc; /* Mask Sc */
36 #define INFBUF_SIZE 16384
40 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
42 int off = state & (WORD_BITS-1);
43 int wno = state / WORD_BITS;
45 m[mc->n * ch + wno] |= 1<<off;
48 static INLINE void reset_bit (MatchContext *mc, MatchWord *m, int ch,
51 int off = state & (WORD_BITS-1);
52 int wno = state / WORD_BITS;
54 m[mc->n * ch + wno] &= ~(1<<off);
57 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
60 int off = state & (WORD_BITS-1);
61 int wno = state / WORD_BITS;
63 return m[mc->n * ch + wno] & (1<<off);
66 static MatchContext *mk_MatchContext (DFA_states *dfas, int range)
68 MatchContext *mc = imalloc (sizeof(*mc));
71 mc->n = (dfas->no+WORD_BITS) / WORD_BITS;
73 mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n);
75 for (i=0; i<dfas->no; i++)
78 DFA_state *state = dfas->sortarray[i];
80 for (j=0; j<state->tran_no; j++)
83 int ch0 = state->trans[j].ch[0];
84 int ch1 = state->trans[j].ch[1];
85 assert (ch0 >= 0 && ch1 >= 0);
87 for (ch = ch0; ch <= ch1; ch++)
88 set_bit (mc, mc->Sc, ch, i);
95 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
96 DFA_states *dfas, int ch)
99 MatchWord *Rsrc_p = Rsrc, mask;
102 for (j = 1; j<mc->n; j++)
107 for (j = 0; j<WORD_BITS/4; j++)
113 DFA_state *state = dfas->sortarray[s];
114 int i = state->tran_no;
116 if (ch >= state->trans[i].ch[0] &&
117 ch <= state->trans[i].ch[1])
118 set_bit (mc, Rdst, 0, state->trans[i].to);
122 DFA_state *state = dfas->sortarray[s+1];
123 int i = state->tran_no;
125 if (ch >= state->trans[i].ch[0] &&
126 ch <= state->trans[i].ch[1])
127 set_bit (mc, Rdst, 0, state->trans[i].to);
131 DFA_state *state = dfas->sortarray[s+2];
132 int i = state->tran_no;
134 if (ch >= state->trans[i].ch[0] &&
135 ch <= state->trans[i].ch[1])
136 set_bit (mc, Rdst, 0, state->trans[i].to);
140 DFA_state *state = dfas->sortarray[s+3];
141 int i = state->tran_no;
143 if (ch >= state->trans[i].ch[0] &&
144 ch <= state->trans[i].ch[1])
145 set_bit (mc, Rdst, 0, state->trans[i].to);
156 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
160 MatchWord *Rsrc_p = Rsrc, mask;
161 for (j = 0; j<mc->n; j++)
166 for (j = 0; j<WORD_BITS/4; j++)
172 DFA_state *state = dfas->sortarray[s];
173 int i = state->tran_no;
175 set_bit (mc, Rdst, 0, state->trans[i].to);
179 DFA_state *state = dfas->sortarray[s+1];
180 int i = state->tran_no;
182 set_bit (mc, Rdst, 0, state->trans[i].to);
186 DFA_state *state = dfas->sortarray[s+2];
187 int i = state->tran_no;
189 set_bit (mc, Rdst, 0, state->trans[i].to);
193 DFA_state *state = dfas->sortarray[s+3];
194 int i = state->tran_no;
196 set_bit (mc, Rdst, 0, state->trans[i].to);
207 static void or (MatchContext *mc, MatchWord *Rdst,
208 MatchWord *Rsrc1, MatchWord *Rsrc2)
211 for (i = 0; i<mc->n; i++)
212 Rdst[i] = Rsrc1[i] | Rsrc2[i];
216 static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
218 MatchWord *Rj, *Rj1, *Rj_a, *Rj_b, *Rj_c;
225 infbuf = imalloc (INFBUF_SIZE);
227 Rj = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
228 Rj1 = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
229 Rj_a = icalloc (mc->n * sizeof(*Rj));
230 Rj_b = icalloc (mc->n * sizeof(*Rj));
231 Rj_c = icalloc (mc->n * sizeof(*Rj));
233 set_bit (mc, Rj, 0, 0);
234 for (d = 1; d<=mc->range; d++)
237 memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
238 for (s = 0; s<dfas->no; s++)
240 if (get_bit (mc, Rj, d-1, s))
242 DFA_state *state = dfas->sortarray[s];
243 int i = state->tran_no;
245 set_bit (mc, Rj, d, state->trans[i].to);
249 while ((ch = getc (inf)) != EOF)
253 infbuf[inf_ptr] = ch;
260 printf ("%5d:", lineno);
265 } while (infbuf[i] != '\n');
268 if (++i == INFBUF_SIZE)
271 } while (infbuf[i] != '\n');
276 if (++inf_ptr == INFBUF_SIZE)
278 mask_shift (mc, Rj1, Rj, dfas, ch);
279 for (d = 1; d <= mc->range; d++)
281 mask_shift (mc, Rj_b, Rj+d*mc->n, dfas, ch); /* 1 */
283 or (mc, Rj_a, Rj+(d-1)*mc->n, Rj1+(d-1)*mc->n); /* 2,3 */
285 shift (mc, Rj_c, Rj_a, dfas);
287 or (mc, Rj_a, Rj_b, Rj_c); /* 1,2,3*/
289 or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n); /* 1,2,3,4 */
291 for (s = 0; s<dfas->no; s++)
293 if (dfas->sortarray[s]->rule_no)
294 if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
297 for (d = 0; d <= mc->range; d++)
298 reset_bit (mc, Rj1+d*mc->n, 0, dfas->no);
312 static int grep_file (DFA_states *dfas, const char *fname, int range)
319 inf = fopen (fname, "r");
322 log (LOG_FATAL|LOG_ERRNO, "cannot open `%s'", fname);
329 mc = mk_MatchContext (dfas, range);
338 int main (int argc, char **argv)
343 char *pattern = NULL;
344 DFA_states *dfas = NULL;
348 while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2)
355 DFA *dfa = init_dfa();
357 i = parse_dfa (dfa, &pattern, dfa_thompson_chars);
360 fprintf (stderr, "%s: illegal pattern\n", prog);
363 dfa->root = dfa->top;
364 dfas = mk_dfas (dfa, 200);
370 grep_file (dfas, arg, range);
375 log_init (log_mask_str(arg), prog, NULL);
384 debug_dfa_followpos = 1;
397 log (LOG_FATAL, "unknown option");
403 fprintf (stderr, "usage:\n "
404 " %s [-d] [-n] [-r n] [-s] [-v n] pattern file ..\n", prog);
407 else if (no_files == 0)
409 grep_file (dfas, NULL, range);