dfa/grepper.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 1994-2010 Index Data
   3
   4 Zebra is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free
   6 Software Foundation; either version 2, or (at your option) any later
   7 version.
   8
   9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12 for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <stdio.h>
  24 #include <ctype.h>
  25 #include <assert.h>
  26
  27 #include <idzebra/util.h>
  28 #include <yaz/yaz-util.h>
  29 #include <dfa.h>
  30 #include "imalloc.h"
  31
  32 char *prog;
  33 static int show_line = 0;
  34
  35 typedef unsigned MatchWord;
  36 #define WORD_BITS 32
  37
  38 typedef struct {
  39     int n;           /* no of MatchWord needed */
  40     int range;       /* max no. of errors */
  41     MatchWord *Sc;   /* Mask Sc */
  42 } MatchContext;
  43
  44 #define INFBUF_SIZE 16384
  45
  46 #define INLINE
  47
  48 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
  49 {
  50     int off = state & (WORD_BITS-1);
  51     int wno = state / WORD_BITS;
  52
  53     m[mc->n * ch + wno] |= 1<<off;
  54 }
  55
  56 static INLINE void reset_bit (MatchContext *mc, MatchWord *m, int ch,
  57                               int state)
  58 {
  59     int off = state & (WORD_BITS-1);
  60     int wno = state / WORD_BITS;
  61
  62     m[mc->n * ch + wno] &= ~(1<<off);
  63 }
  64
  65 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
  66                                  int state)
  67 {
  68     int off = state & (WORD_BITS-1);
  69     int wno = state / WORD_BITS;
  70
  71     return m[mc->n * ch + wno] & (1<<off);
  72 }
  73
  74 static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
  75 {
  76     MatchContext *mc = imalloc (sizeof(*mc));
  77     int i;
  78
  79     mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
  80     mc->range = range;
  81     mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n);
  82
  83     for (i=0; i<dfa->no_states; i++)
  84     {
  85         int j;
  86         struct DFA_state *state = dfa->states[i];
  87
  88         for (j=0; j<state->tran_no; j++)
  89         {
  90             int ch;
  91             int ch0 = state->trans[j].ch[0];
  92             int ch1 = state->trans[j].ch[1];
  93             assert (ch0 >= 0 && ch1 >= 0);
  94
  95             for (ch = ch0; ch <= ch1; ch++)
  96                 set_bit (mc, mc->Sc, ch, i);
  97         }
  98     }
  99     return mc;
 100 }
 101
 102
 103 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 104                         struct DFA *dfa, int ch)
 105 {
 106     int j, s = 0;
 107     MatchWord *Rsrc_p = Rsrc, mask;
 108
 109     Rdst[0] = 1;
 110     for (j = 1; j<mc->n; j++)
 111         Rdst[j] = 0;
 112     while (1)
 113     {
 114         mask = *Rsrc_p++;
 115         for (j = 0; j<WORD_BITS/4; j++)
 116         {
 117             if (mask & 15)
 118             {
 119                 if (mask & 1)
 120                 {
 121                     struct DFA_state *state = dfa->states[s];
 122                     int i = state->tran_no;
 123                     while (--i >= 0)
 124                         if (ch >= state->trans[i].ch[0] &&
 125                             ch <= state->trans[i].ch[1])
 126                             set_bit (mc, Rdst, 0, state->trans[i].to);
 127                 }
 128                 if (mask & 2)
 129                 {
 130                     struct DFA_state *state = dfa->states[s+1];
 131                     int i = state->tran_no;
 132                     while (--i >= 0)
 133                         if (ch >= state->trans[i].ch[0] &&
 134                             ch <= state->trans[i].ch[1])
 135                             set_bit (mc, Rdst, 0, state->trans[i].to);
 136                 }
 137                 if (mask & 4)
 138                 {
 139                     struct DFA_state *state = dfa->states[s+2];
 140                     int i = state->tran_no;
 141                     while (--i >= 0)
 142                         if (ch >= state->trans[i].ch[0] &&
 143                             ch <= state->trans[i].ch[1])
 144                             set_bit (mc, Rdst, 0, state->trans[i].to);
 145                 }
 146                 if (mask & 8)
 147                 {
 148                     struct DFA_state *state = dfa->states[s+3];
 149                     int i = state->tran_no;
 150                     while (--i >= 0)
 151                         if (ch >= state->trans[i].ch[0] &&
 152                             ch <= state->trans[i].ch[1])
 153                             set_bit (mc, Rdst, 0, state->trans[i].to);
 154                 }
 155             }
 156             s += 4;
 157             if (s >= dfa->no_states)
 158                 return;
 159             mask >>= 4;
 160         }
 161     }
 162 }
 163
 164 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 165                    struct DFA *dfa)
 166 {
 167     int j, s = 0;
 168     MatchWord *Rsrc_p = Rsrc, mask;
 169     for (j = 0; j<mc->n; j++)
 170         Rdst[j] = 0;
 171     while (1)
 172     {
 173         mask = *Rsrc_p++;
 174         for (j = 0; j<WORD_BITS/4; j++)
 175         {
 176             if (mask & 15)
 177             {
 178                 if (mask & 1)
 179                 {
 180                     struct DFA_state *state = dfa->states[s];
 181                     int i = state->tran_no;
 182                     while (--i >= 0)
 183                         set_bit (mc, Rdst, 0, state->trans[i].to);
 184                 }
 185                 if (mask & 2)
 186                 {
 187                     struct DFA_state *state = dfa->states[s+1];
 188                     int i = state->tran_no;
 189                     while (--i >= 0)
 190                         set_bit (mc, Rdst, 0, state->trans[i].to);
 191                 }
 192                 if (mask & 4)
 193                 {
 194                     struct DFA_state *state = dfa->states[s+2];
 195                     int i = state->tran_no;
 196                     while (--i >= 0)
 197                         set_bit (mc, Rdst, 0, state->trans[i].to);
 198                 }
 199                 if (mask & 8)
 200                 {
 201                     struct DFA_state *state = dfa->states[s+3];
 202                     int i = state->tran_no;
 203                     while (--i >= 0)
 204                         set_bit (mc, Rdst, 0, state->trans[i].to);
 205                 }
 206             }
 207             s += 4;
 208             if (s >= dfa->no_states)
 209                 return;
 210             mask >>= 4;
 211         }
 212     }
 213 }
 214
 215 static void or (MatchContext *mc, MatchWord *Rdst,
 216                 MatchWord *Rsrc1, MatchWord *Rsrc2)
 217 {
 218     int i;
 219     for (i = 0; i<mc->n; i++)
 220         Rdst[i] = Rsrc1[i] | Rsrc2[i];
 221 }
 222
 223
 224 static int go (MatchContext *mc, struct DFA *dfa, FILE *inf)
 225 {
 226     MatchWord *Rj, *Rj1, *Rj_a, *Rj_b, *Rj_c;
 227     int s, d, ch;
 228     int lineno = 1;
 229     char *infbuf;
 230     int inf_ptr = 1;
 231     int no_match = 0;
 232
 233     infbuf = imalloc (INFBUF_SIZE);
 234     infbuf[0] = '\n';
 235     Rj = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
 236     Rj1 = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
 237     Rj_a = icalloc (mc->n * sizeof(*Rj));
 238     Rj_b = icalloc (mc->n * sizeof(*Rj));
 239     Rj_c = icalloc (mc->n * sizeof(*Rj));
 240
 241     set_bit (mc, Rj, 0, 0);
 242     for (d = 1; d<=mc->range; d++)
 243     {
 244         int s;
 245         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
 246         for (s = 0; s<dfa->no_states; s++)
 247         {
 248             if (get_bit (mc, Rj, d-1, s))
 249             {
 250                 struct DFA_state *state = dfa->states[s];
 251                 int i = state->tran_no;
 252                 while (--i >= 0)
 253                     set_bit (mc, Rj, d, state->trans[i].to);
 254             }
 255         }
 256     }
 257     while ((ch = getc (inf)) != EOF)
 258     {
 259         MatchWord *Rj_t;
 260
 261         infbuf[inf_ptr] = ch;
 262         if (ch == '\n')
 263         {
 264             if (no_match)
 265             {
 266                 int i = inf_ptr;
 267                 if (show_line)
 268                     printf ("%5d:", lineno);
 269                 do
 270                 {
 271                     if (--i < 0)
 272                         i = INFBUF_SIZE-1;
 273                 } while (infbuf[i] != '\n');
 274                 do
 275                 {
 276                     if (++i == INFBUF_SIZE)
 277                         i = 0;
 278                     putchar (infbuf[i]);
 279                 } while (infbuf[i] != '\n');
 280                 no_match = 0;
 281             }
 282             lineno++;
 283         }
 284         if (++inf_ptr == INFBUF_SIZE)
 285             inf_ptr = 0;
 286         mask_shift (mc, Rj1, Rj, dfa, ch);
 287         for (d = 1; d <= mc->range; d++)
 288         {
 289             mask_shift (mc, Rj_b, Rj+d*mc->n, dfa, ch);    /* 1 */
 290
 291             or (mc, Rj_a, Rj+(d-1)*mc->n, Rj1+(d-1)*mc->n); /* 2,3 */
 292
 293             shift (mc, Rj_c, Rj_a, dfa);
 294
 295             or (mc, Rj_a, Rj_b, Rj_c);                      /* 1,2,3*/
 296
 297             or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n);     /* 1,2,3,4 */
 298         }
 299         for (s = 0; s<dfa->no_states; s++)
 300         {
 301             if (dfa->states[s]->rule_no)
 302                 if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
 303                     no_match++;
 304         }
 305         for (d = 0; d <= mc->range; d++)
 306             reset_bit (mc, Rj1+d*mc->n, 0, dfa->no_states);
 307         Rj_t = Rj1;
 308         Rj1 = Rj;
 309         Rj = Rj_t;
 310     }
 311     ifree (Rj);
 312     ifree (Rj1);
 313     ifree (Rj_a);
 314     ifree (Rj_b);
 315     ifree (Rj_c);
 316     ifree (infbuf);
 317     return 0;
 318 }
 319
 320 static int grep_file (struct DFA *dfa, const char *fname, int range)
 321 {
 322     FILE *inf;
 323     MatchContext *mc;
 324
 325     if (fname)
 326     {
 327         inf = fopen (fname, "r");
 328         if (!inf)
 329         {
 330             yaz_log (YLOG_FATAL|YLOG_ERRNO, "cannot open `%s'", fname);
 331             exit (1);
 332         }
 333     }
 334     else
 335         inf = stdin;
 336
 337     mc = mk_MatchContext (dfa, range);
 338
 339     go (mc, dfa, inf);
 340
 341     if (fname)
 342         fclose (inf);
 343     return 0;
 344 }
 345
 346 int main (int argc, char **argv)
 347 {
 348     int ret;
 349     int range = 0;
 350     char *arg;
 351     const char *pattern = NULL;
 352     int no_files = 0;
 353     struct DFA *dfa = dfa_init();
 354
 355     prog = argv[0];
 356     while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2)
 357     {
 358         if (ret == 0)
 359         {
 360             if (!pattern)
 361             {
 362                 int i;
 363                 pattern = arg;
 364                 i = dfa_parse (dfa, &pattern);
 365                 if (i || *pattern)
 366                 {
 367                     fprintf (stderr, "%s: illegal pattern\n", prog);
 368                     return 1;
 369                 }
 370                 dfa_mkstate (dfa);
 371             }
 372             else
 373             {
 374                 no_files++;
 375                 grep_file (dfa, arg, range);
 376             }
 377         }
 378         else if (ret == 'v')
 379         {
 380             yaz_log_init (yaz_log_mask_str(arg), prog, NULL);
 381         }
 382         else if (ret == 's')
 383         {
 384             dfa_verbose = 1;
 385         }
 386         else if (ret == 'd')
 387         {
 388             debug_dfa_tran = 1;
 389             debug_dfa_followpos = 1;
 390             debug_dfa_trav = 1;
 391         }
 392         else if (ret == 'r')
 393         {
 394             range = atoi (arg);
 395         }
 396         else if (ret == 'n')
 397         {
 398             show_line = 1;
 399         }
 400         else
 401         {
 402             yaz_log (YLOG_FATAL, "Unknown option '-%s'", arg);
 403             exit (1);
 404         }
 405     }
 406     if (!pattern)
 407     {
 408         fprintf (stderr, "usage:\n "
 409                  " %s [-d] [-n] [-r n] [-s] [-v n] pattern file ..\n", prog);
 410         exit (1);
 411     }
 412     else if (no_files == 0)
 413     {
 414         grep_file (dfa, NULL, range);
 415     }
 416     dfa_delete (&dfa);
 417     return 0;
 418 }
 419 /*
 420  * Local variables:
 421  * c-basic-offset: 4
 422  * c-file-style: "Stroustrup"
 423  * indent-tabs-mode: nil
 424  * End:
 425  * vim: shiftwidth=4 tabstop=8 expandtab
 426  */
 427