2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.1 1994-09-27 16:31:18 adam
8 * First version of grepper: grep with error correction.
22 static int show_line = 0;
24 typedef unsigned MatchWord;
28 int n; /* no of MatchWord needed */
29 int range; /* max no. of errors */
30 MatchWord *Sc; /* Mask Sc */
33 #define INFBUF_SIZE 16384
35 static inline void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
37 int off = state & (WORD_BITS-1);
38 int wno = state / WORD_BITS;
40 m[mc->n * ch + wno] |= 1<<off;
43 static inline void reset_bit (MatchContext *mc, MatchWord *m, int ch, int state)
45 int off = state & (WORD_BITS-1);
46 int wno = state / WORD_BITS;
48 m[mc->n * ch + wno] &= ~(1<<off);
51 static inline MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch, int state)
53 int off = state & (WORD_BITS-1);
54 int wno = state / WORD_BITS;
56 return m[mc->n * ch + wno] & (1<<off);
59 static MatchContext *mk_MatchContext (DFA_states *dfas, int range)
61 MatchContext *mc = imalloc (sizeof(*mc));
64 mc->n = (dfas->no+WORD_BITS) / WORD_BITS;
66 mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n);
68 for (i=0; i<dfas->no; i++)
71 DFA_state *state = dfas->sortarray[i];
73 for (j=0; j<state->tran_no; j++)
76 int ch0 = state->trans[j].ch[0];
77 int ch1 = state->trans[j].ch[1];
78 assert (ch0 >= 0 && ch1 >= 0);
80 for (ch = ch0; ch <= ch1; ch++)
81 set_bit (mc, mc->Sc, ch, i);
87 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
88 DFA_states *dfas, int ch)
92 for (i = 1; i<mc->n; i++)
94 for (s = 0; s<dfas->no; s++)
95 if (get_bit (mc, Rsrc, 0, s))
97 DFA_state *state = dfas->sortarray[s];
98 int i = state->tran_no;
100 if (ch >= state->trans[i].ch[0] && ch <= state->trans[i].ch[1])
101 set_bit (mc, Rdst, 0, state->trans[i].to);
105 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
109 for (i = 0; i<mc->n; i++)
111 for (s = 0; s<dfas->no; s++)
112 if (get_bit (mc, Rsrc, 0, s))
114 DFA_state *state = dfas->sortarray[s];
115 int i = state->tran_no;
117 set_bit (mc, Rdst, 0, state->trans[i].to);
121 static void or (MatchContext *mc, MatchWord *Rdst,
122 MatchWord *Rsrc1, MatchWord *Rsrc2)
125 for (i = 0; i<mc->n; i++)
126 Rdst[i] = Rsrc1[i] | Rsrc2[i];
130 static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
132 MatchWord *Rj, *Rj1, *Rj_a, *Rj_b;
139 infbuf = imalloc (INFBUF_SIZE);
141 Rj = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
142 Rj1 = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
143 Rj_a = icalloc (mc->n * sizeof(*Rj));
144 Rj_b = icalloc (mc->n * sizeof(*Rj));
146 set_bit (mc, Rj, 0, 0);
147 for (d = 1; d<=mc->range; d++)
150 memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
151 for (s = 0; s<dfas->no; s++)
153 if (get_bit (mc, Rj, d-1, s))
155 DFA_state *state = dfas->sortarray[s];
156 int i = state->tran_no;
158 set_bit (mc, Rj, d, state->trans[i].to);
162 while ((ch = getc (inf)) != EOF)
171 printf ("%5d:", lineno);
172 while (infbuf[i] != '\n')
179 if (++i == INFBUF_SIZE)
182 } while (infbuf[i] != '\n');
187 infbuf[inf_ptr++] = ch;
188 if (inf_ptr == INFBUF_SIZE)
190 mask_shift (mc, Rj1, Rj, dfas, ch);
191 for (d = 1; d <= mc->range; d++)
193 mask_shift (mc, Rj_b, Rj+d*mc->n, dfas, ch);/* 1 */
195 shift (mc, Rj_a, Rj+(d-1)*mc->n, dfas); /* 2 */
197 or (mc, Rj_a, Rj_a, Rj_b); /* 1,2 */
199 shift (mc, Rj_b, Rj1+(d-1)*mc->n, dfas); /* 3 */
201 or (mc, Rj_a, Rj_a, Rj_b); /* 1,2,3 */
203 or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n); /* 1,2,3,4 */
205 for (s = 0; s<dfas->no; s++)
207 if (dfas->sortarray[s]->rule_no)
208 if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
211 for (d = 0; d <= mc->range; d++)
212 reset_bit (mc, Rj1+d*mc->n, 0, dfas->no);
225 static int grep_file (DFA_states *dfas, const char *fname, int range)
232 inf = fopen (fname, "r");
235 log (LOG_FATAL|LOG_ERRNO, "cannot open `%s'", fname);
242 mc = mk_MatchContext (dfas, range);
251 int main (int argc, char **argv)
256 char *pattern = NULL;
257 DFA_states *dfas = NULL;
261 while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2)
268 DFA *dfa = init_dfa();
270 i = parse_dfa (dfa, &pattern, dfa_thompson_chars);
273 fprintf (stderr, "%s: illegal pattern\n", prog);
276 dfa->root = dfa->top;
277 dfas = mk_dfas (dfa, 200);
283 grep_file (dfas, arg, range);
288 log_init (atoi(arg), prog, NULL);
297 debug_dfa_followpos = 1;
310 log (LOG_FATAL, "unknown option");
316 fprintf (stderr, "usage:\n "
317 " %s [-d] [-n] [-r n] [-s] [-v n] pattern file ..\n", prog);
320 else if (no_files == 0)
322 grep_file (dfas, NULL, range);