dfa/grepper.c

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