dfa/grepper.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: grepper.c,v $
   7  * Revision 1.2  1994-10-03 17:22:18  adam
   8  * Optimization of grepper.
   9  *
  10  * Revision 1.1  1994/09/27  16:31:18  adam
  11  * First version of grepper: grep with error correction.
  12  *
  13  */
  14 #include <stdlib.h>
  15 #include <string.h>
  16 #include <stdio.h>
  17 #include <ctype.h>
  18 #include <assert.h>
  19
  20 #include <util.h>
  21 #include <dfa.h>
  22 #include "imalloc.h"
  23
  24 char *prog;
  25 static int show_line = 0;
  26
  27 typedef unsigned MatchWord;
  28 #define WORD_BITS 32
  29
  30 typedef struct {
  31     int n;           /* no of MatchWord needed */
  32     int range;       /* max no. of errors */
  33     MatchWord *Sc;   /* Mask Sc */
  34 } MatchContext;
  35
  36 #define INFBUF_SIZE 16384
  37
  38 #define INLINE
  39
  40 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
  41 {
  42     int off = state & (WORD_BITS-1);
  43     int wno = state / WORD_BITS;
  44
  45     m[mc->n * ch + wno] |= 1<<off;
  46 }
  47
  48 static INLINE void reset_bit (MatchContext *mc, MatchWord *m, int ch,
  49                               int state)
  50 {
  51     int off = state & (WORD_BITS-1);
  52     int wno = state / WORD_BITS;
  53
  54     m[mc->n * ch + wno] &= ~(1<<off);
  55 }
  56
  57 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
  58                                  int state)
  59 {
  60     int off = state & (WORD_BITS-1);
  61     int wno = state / WORD_BITS;
  62
  63     return m[mc->n * ch + wno] & (1<<off);
  64 }
  65
  66 static MatchContext *mk_MatchContext (DFA_states *dfas, int range)
  67 {
  68     MatchContext *mc = imalloc (sizeof(*mc));
  69     int i;
  70
  71     mc->n = (dfas->no+WORD_BITS) / WORD_BITS;
  72     mc->range = range;
  73     mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n);
  74
  75     for (i=0; i<dfas->no; i++)
  76     {
  77         int j;
  78         DFA_state *state = dfas->sortarray[i];
  79
  80         for (j=0; j<state->tran_no; j++)
  81         {
  82             int ch;
  83             int ch0 = state->trans[j].ch[0];
  84             int ch1 = state->trans[j].ch[1];
  85             assert (ch0 >= 0 && ch1 >= 0);
  86
  87             for (ch = ch0; ch <= ch1; ch++)
  88                 set_bit (mc, mc->Sc, ch, i);
  89         }
  90     }
  91     return mc;
  92 }
  93
  94
  95 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
  96                    DFA_states *dfas, int ch)
  97 {
  98     int j, s = 0;
  99     MatchWord *Rsrc_p = Rsrc, mask;
 100
 101     Rdst[0] = 1;
 102     for (j = 1; j<mc->n; j++)
 103         Rdst[j] = 0;
 104     while (1)
 105     {
 106         mask = *Rsrc_p++;
 107         for (j = 0; j<WORD_BITS/4; j++)
 108         {
 109             if (mask & 15)
 110             {
 111                 if (mask & 1)
 112                 {
 113                     DFA_state *state = dfas->sortarray[s];
 114                     int i = state->tran_no;
 115                     while (--i >= 0)
 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);
 119                 }
 120                 if (mask & 2)
 121                 {
 122                     DFA_state *state = dfas->sortarray[s+1];
 123                     int i = state->tran_no;
 124                     while (--i >= 0)
 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);
 128                 }
 129                 if (mask & 4)
 130                 {
 131                     DFA_state *state = dfas->sortarray[s+2];
 132                     int i = state->tran_no;
 133                     while (--i >= 0)
 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);
 137                 }
 138                 if (mask & 8)
 139                 {
 140                     DFA_state *state = dfas->sortarray[s+3];
 141                     int i = state->tran_no;
 142                     while (--i >= 0)
 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);
 146                 }
 147             }
 148             s += 4;
 149             if (s >= dfas->no)
 150                 return;
 151             mask >>= 4;
 152         }
 153     }
 154 }
 155
 156 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 157                    DFA_states *dfas)
 158 {
 159     int j, s = 0;
 160     MatchWord *Rsrc_p = Rsrc, mask;
 161     for (j = 0; j<mc->n; j++)
 162         Rdst[j] = 0;
 163     while (1)
 164     {
 165         mask = *Rsrc_p++;
 166         for (j = 0; j<WORD_BITS/4; j++)
 167         {
 168             if (mask & 15)
 169             {
 170                 if (mask & 1)
 171                 {
 172                     DFA_state *state = dfas->sortarray[s];
 173                     int i = state->tran_no;
 174                     while (--i >= 0)
 175                         set_bit (mc, Rdst, 0, state->trans[i].to);
 176                 }
 177                 if (mask & 2)
 178                 {
 179                     DFA_state *state = dfas->sortarray[s+1];
 180                     int i = state->tran_no;
 181                     while (--i >= 0)
 182                         set_bit (mc, Rdst, 0, state->trans[i].to);
 183                 }
 184                 if (mask & 4)
 185                 {
 186                     DFA_state *state = dfas->sortarray[s+2];
 187                     int i = state->tran_no;
 188                     while (--i >= 0)
 189                         set_bit (mc, Rdst, 0, state->trans[i].to);
 190                 }
 191                 if (mask & 8)
 192                 {
 193                     DFA_state *state = dfas->sortarray[s+3];
 194                     int i = state->tran_no;
 195                     while (--i >= 0)
 196                         set_bit (mc, Rdst, 0, state->trans[i].to);
 197                 }
 198             }
 199             s += 4;
 200             if (s >= dfas->no)
 201                 return;
 202             mask >>= 4;
 203         }
 204     }
 205 }
 206
 207 static void or (MatchContext *mc, MatchWord *Rdst,
 208                 MatchWord *Rsrc1, MatchWord *Rsrc2)
 209 {
 210     int i;
 211     for (i = 0; i<mc->n; i++)
 212         Rdst[i] = Rsrc1[i] | Rsrc2[i];
 213 }
 214
 215
 216 static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
 217 {
 218     MatchWord *Rj, *Rj1, *Rj_a, *Rj_b, *Rj_c;
 219     int s, d, ch;
 220     int lineno = 1;
 221     char *infbuf;
 222     int inf_ptr = 1;
 223     int no_match = 0;
 224
 225     infbuf = imalloc (INFBUF_SIZE);
 226     infbuf[0] = '\n';
 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));
 232
 233     set_bit (mc, Rj, 0, 0);
 234     for (d = 1; d<=mc->range; d++)
 235     {
 236         int s;
 237         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
 238         for (s = 0; s<dfas->no; s++)
 239         {
 240             if (get_bit (mc, Rj, d-1, s))
 241             {
 242                 DFA_state *state = dfas->sortarray[s];
 243                 int i = state->tran_no;
 244                 while (--i >= 0)
 245                     set_bit (mc, Rj, d, state->trans[i].to);
 246             }
 247         }
 248     }
 249     while ((ch = getc (inf)) != EOF)
 250     {
 251         MatchWord *Rj_t;
 252
 253         infbuf[inf_ptr] = ch;
 254         if (ch == '\n')
 255         {
 256             if (no_match)
 257             {
 258                 int i = inf_ptr;
 259                 if (show_line)
 260                     printf ("%5d:", lineno);
 261                 do
 262                 {
 263                     if (--i < 0)
 264                         i = INFBUF_SIZE-1;
 265                 } while (infbuf[i] != '\n');
 266                 do
 267                 {
 268                     if (++i == INFBUF_SIZE)
 269                         i = 0;
 270                     putchar (infbuf[i]);
 271                 } while (infbuf[i] != '\n');
 272                 no_match = 0;
 273             }
 274             lineno++;
 275         }
 276         if (++inf_ptr == INFBUF_SIZE)
 277             inf_ptr = 0;
 278         mask_shift (mc, Rj1, Rj, dfas, ch);
 279         for (d = 1; d <= mc->range; d++)
 280         {
 281             mask_shift (mc, Rj_b, Rj+d*mc->n, dfas, ch);    /* 1 */
 282
 283             or (mc, Rj_a, Rj+(d-1)*mc->n, Rj1+(d-1)*mc->n); /* 2,3 */
 284
 285             shift (mc, Rj_c, Rj_a, dfas);
 286
 287             or (mc, Rj_a, Rj_b, Rj_c);                      /* 1,2,3*/
 288
 289             or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n);     /* 1,2,3,4 */
 290         }
 291         for (s = 0; s<dfas->no; s++)
 292         {
 293             if (dfas->sortarray[s]->rule_no)
 294                 if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
 295                     no_match++;
 296         }
 297         for (d = 0; d <= mc->range; d++)
 298             reset_bit (mc, Rj1+d*mc->n, 0, dfas->no);
 299         Rj_t = Rj1;
 300         Rj1 = Rj;
 301         Rj = Rj_t;
 302     }
 303     ifree (Rj);
 304     ifree (Rj1);
 305     ifree (Rj_a);
 306     ifree (Rj_b);
 307     ifree (Rj_c);
 308     ifree (infbuf);
 309     return 0;
 310 }
 311
 312 static int grep_file (DFA_states *dfas, const char *fname, int range)
 313 {
 314     FILE *inf;
 315     MatchContext *mc;
 316
 317     if (fname)
 318     {
 319         inf = fopen (fname, "r");
 320         if (!inf)
 321         {
 322             log (LOG_FATAL|LOG_ERRNO, "cannot open `%s'", fname);
 323             exit (1);
 324         }
 325     }
 326     else
 327         inf = stdin;
 328
 329     mc = mk_MatchContext (dfas, range);
 330
 331     go (mc, dfas, inf);
 332
 333     if (fname)
 334         fclose (inf);
 335     return 0;
 336 }
 337
 338 int main (int argc, char **argv)
 339 {
 340     int ret;
 341     int range = 0;
 342     char *arg;
 343     char *pattern = NULL;
 344     DFA_states *dfas = NULL;
 345     int no_files = 0;
 346
 347     prog = argv[0];
 348     while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2)
 349     {
 350         if (ret == 0)
 351         {
 352             if (!pattern)
 353             {
 354                 int i;
 355                 DFA *dfa = init_dfa();
 356                 pattern = arg;
 357                 i = parse_dfa (dfa, &pattern, dfa_thompson_chars);
 358                 if (i || *pattern)
 359                 {
 360                     fprintf (stderr, "%s: illegal pattern\n", prog);
 361                     return 1;
 362                 }
 363                 dfa->root = dfa->top;
 364                 dfas = mk_dfas (dfa, 200);
 365                 rm_dfa (&dfa);
 366             }
 367             else
 368             {
 369                 no_files++;
 370                 grep_file (dfas, arg, range);
 371             }
 372         }
 373         else if (ret == 'v')
 374         {
 375             log_init (log_mask_str(arg), prog, NULL);
 376         }
 377         else if (ret == 's')
 378         {
 379             dfa_verbose = 1;
 380         }
 381         else if (ret == 'd')
 382         {
 383             debug_dfa_tran = 1;
 384             debug_dfa_followpos = 1;
 385             debug_dfa_trav = 1;
 386         }
 387         else if (ret == 'r')
 388         {
 389             range = atoi (arg);
 390         }
 391         else if (ret == 'n')
 392         {
 393             show_line = 1;
 394         }
 395         else
 396         {
 397             log (LOG_FATAL, "unknown option");
 398             exit (1);
 399         }
 400     }
 401     if (!pattern)
 402     {
 403         fprintf (stderr, "usage:\n "
 404                  " %s [-d] [-n] [-r n] [-s] [-v n] pattern file ..\n", prog);
 405         exit (1);
 406     }
 407     else if (no_files == 0)
 408     {
 409         grep_file (dfas, NULL, range);
 410     }
 411     return 0;
 412 }