dict/lookgrep.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: lookgrep.c,v $
   7  * Revision 1.1  1994-10-03 17:23:04  adam
   8  * First version of dictionary lookup with regular expressions and errors.
   9  *
  10  */
  11
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <stdio.h>
  15 #include <assert.h>
  16
  17 #include <dfa.h>
  18 #include <dict.h>
  19
  20 typedef unsigned MatchWord;
  21 #define WORD_BITS 32
  22
  23 typedef struct {
  24     int n;           /* no of MatchWord needed */
  25     int range;       /* max no. of errors */
  26     MatchWord *Sc;   /* Mask Sc */
  27 } MatchContext;
  28
  29 #define INLINE
  30
  31 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
  32 {
  33     int off = state & (WORD_BITS-1);
  34     int wno = state / WORD_BITS;
  35
  36     m[mc->n * ch + wno] |= 1<<off;
  37 }
  38
  39 static INLINE void reset_bit (MatchContext *mc, MatchWord *m, int ch,
  40                               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 MatchWord get_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     return m[mc->n * ch + wno] & (1<<off);
  55 }
  56
  57 static MatchContext *mk_MatchContext (DFA_states *dfas, int range)
  58 {
  59     MatchContext *mc = xmalloc (sizeof(*mc));
  60     int i;
  61
  62     mc->n = (dfas->no+WORD_BITS) / WORD_BITS;
  63     mc->range = range;
  64     mc->Sc = xcalloc (sizeof(*mc->Sc) * 256 * mc->n, 1);
  65
  66     for (i=0; i<dfas->no; i++)
  67     {
  68         int j;
  69         DFA_state *state = dfas->sortarray[i];
  70
  71         for (j=0; j<state->tran_no; j++)
  72         {
  73             int ch;
  74             int ch0 = state->trans[j].ch[0];
  75             int ch1 = state->trans[j].ch[1];
  76             assert (ch0 >= 0 && ch1 >= 0);
  77
  78             for (ch = ch0; ch <= ch1; ch++)
  79                 set_bit (mc, mc->Sc, ch, i);
  80         }
  81     }
  82     return mc;
  83 }
  84
  85
  86 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
  87                    DFA_states *dfas, int ch)
  88 {
  89     int j, s = 0;
  90     MatchWord *Rsrc_p = Rsrc, mask;
  91
  92 #if 1
  93     for (j = 0; j<mc->n; j++)
  94         Rdst[j] = 0;
  95 #else
  96     Rdst[0] = 1;
  97     for (j = 1; j<mc->n; j++)
  98         Rdst[j] = 0;
  99 #endif
 100     while (1)
 101     {
 102         mask = *Rsrc_p++;
 103         for (j = 0; j<WORD_BITS/4; j++)
 104         {
 105             if (mask & 15)
 106             {
 107                 if (mask & 1)
 108                 {
 109                     DFA_state *state = dfas->sortarray[s];
 110                     int i = state->tran_no;
 111                     while (--i >= 0)
 112                         if (ch >= state->trans[i].ch[0] &&
 113                             ch <= state->trans[i].ch[1])
 114                             set_bit (mc, Rdst, 0, state->trans[i].to);
 115                 }
 116                 if (mask & 2)
 117                 {
 118                     DFA_state *state = dfas->sortarray[s+1];
 119                     int i = state->tran_no;
 120                     while (--i >= 0)
 121                         if (ch >= state->trans[i].ch[0] &&
 122                             ch <= state->trans[i].ch[1])
 123                             set_bit (mc, Rdst, 0, state->trans[i].to);
 124                 }
 125                 if (mask & 4)
 126                 {
 127                     DFA_state *state = dfas->sortarray[s+2];
 128                     int i = state->tran_no;
 129                     while (--i >= 0)
 130                         if (ch >= state->trans[i].ch[0] &&
 131                             ch <= state->trans[i].ch[1])
 132                             set_bit (mc, Rdst, 0, state->trans[i].to);
 133                 }
 134                 if (mask & 8)
 135                 {
 136                     DFA_state *state = dfas->sortarray[s+3];
 137                     int i = state->tran_no;
 138                     while (--i >= 0)
 139                         if (ch >= state->trans[i].ch[0] &&
 140                             ch <= state->trans[i].ch[1])
 141                             set_bit (mc, Rdst, 0, state->trans[i].to);
 142                 }
 143             }
 144             s += 4;
 145             if (s >= dfas->no)
 146                 return;
 147             mask >>= 4;
 148         }
 149     }
 150 }
 151
 152 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 153                    DFA_states *dfas)
 154 {
 155     int j, s = 0;
 156     MatchWord *Rsrc_p = Rsrc, mask;
 157     for (j = 0; j<mc->n; j++)
 158         Rdst[j] = 0;
 159     while (1)
 160     {
 161         mask = *Rsrc_p++;
 162         for (j = 0; j<WORD_BITS/4; j++)
 163         {
 164             if (mask & 15)
 165             {
 166                 if (mask & 1)
 167                 {
 168                     DFA_state *state = dfas->sortarray[s];
 169                     int i = state->tran_no;
 170                     while (--i >= 0)
 171                         set_bit (mc, Rdst, 0, state->trans[i].to);
 172                 }
 173                 if (mask & 2)
 174                 {
 175                     DFA_state *state = dfas->sortarray[s+1];
 176                     int i = state->tran_no;
 177                     while (--i >= 0)
 178                         set_bit (mc, Rdst, 0, state->trans[i].to);
 179                 }
 180                 if (mask & 4)
 181                 {
 182                     DFA_state *state = dfas->sortarray[s+2];
 183                     int i = state->tran_no;
 184                     while (--i >= 0)
 185                         set_bit (mc, Rdst, 0, state->trans[i].to);
 186                 }
 187                 if (mask & 8)
 188                 {
 189                     DFA_state *state = dfas->sortarray[s+3];
 190                     int i = state->tran_no;
 191                     while (--i >= 0)
 192                         set_bit (mc, Rdst, 0, state->trans[i].to);
 193                 }
 194             }
 195             s += 4;
 196             if (s >= dfas->no)
 197                 return;
 198             mask >>= 4;
 199         }
 200     }
 201 }
 202
 203 static void or (MatchContext *mc, MatchWord *Rdst,
 204                 MatchWord *Rsrc1, MatchWord *Rsrc2)
 205 {
 206     int i;
 207     for (i = 0; i<mc->n; i++)
 208         Rdst[i] = Rsrc1[i] | Rsrc2[i];
 209 }
 210
 211 static int move (MatchContext *mc, MatchWord *Rj1, MatchWord *Rj,
 212                  Dict_char ch, DFA_states *dfas, MatchWord *Rtmp)
 213 {
 214     int d;
 215     MatchWord *Rj_a = Rtmp;
 216     MatchWord *Rj_b = Rtmp +   mc->n;
 217     MatchWord *Rj_c = Rtmp + 2*mc->n;
 218
 219     mask_shift (mc, Rj1, Rj, dfas, ch);
 220     for (d = 1; d <= mc->range; d++)
 221     {
 222         mask_shift (mc, Rj_b, Rj+d*mc->n, dfas, ch);    /* 1 */
 223
 224         or (mc, Rj_a, Rj+(d-1)*mc->n, Rj1+(d-1)*mc->n); /* 2,3 */
 225
 226         shift (mc, Rj_c, Rj_a, dfas);
 227
 228         or (mc, Rj_a, Rj_b, Rj_c);                      /* 1,2,3*/
 229
 230         or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n);     /* 1,2,3,4 */
 231     }
 232     return 1;
 233
 234 }
 235
 236
 237 static int dict_grep (Dict dict, Dict_ptr ptr, MatchContext *mc,
 238                       MatchWord *Rj, int pos,
 239                       int (*userfunc)(Dict_char *name, char *info),
 240                       Dict_char *prefix, DFA_states *dfas)
 241 {
 242     int lo, hi;
 243     void *p;
 244     short *indxp;
 245     char *info;
 246
 247     dict_bf_readp (dict->dbf, ptr, &p);
 248     lo = 0;
 249     hi = DICT_nodir(p)-1;
 250     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 251     while (lo <= hi)
 252     {
 253         if (indxp[-lo] > 0)
 254         {
 255             /* string (Dict_char *) DICT_EOS terminated */
 256             /* unsigned char        length of information */
 257             /* char *               information */
 258             int j;
 259             int was_match = 0;
 260             info = (char*)p + indxp[-lo];
 261             for (j=0; ; j++)
 262             {
 263                 Dict_char ch;
 264                 int s, d;
 265                 MatchWord *Rj0 =    Rj + j    *(1+mc->range)*mc->n;
 266                 MatchWord *Rj1 =    Rj + (j+1)*(1+mc->range)*mc->n;
 267                 MatchWord *Rj_tmp = Rj + (j+2)*(1+mc->range)*mc->n;
 268
 269                 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
 270                 prefix[pos+j] = ch;
 271                 if (ch == DICT_EOS)
 272                 {
 273                     if (was_match)
 274                         (*userfunc)(prefix, info+(j+1)*sizeof(Dict_char));
 275                     break;
 276                 }
 277
 278                 was_match = 0;
 279                 move (mc, Rj1, Rj0, ch, dfas, Rj_tmp);
 280                 for (d = mc->n; --d >= 0; )
 281                     if (Rj1[mc->range*mc->n + d])
 282                         break;
 283                 if (d < 0)
 284                     break;
 285                 for (s = 0; s<dfas->no; s++)
 286                 {
 287                     if (dfas->sortarray[s]->rule_no)
 288                         if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
 289                             was_match = 1;
 290                 }
 291                 for (d = 0; d <= mc->range; d++)
 292                     reset_bit (mc, Rj1+d*mc->n, 0, dfas->no);
 293             }
 294         }
 295         else
 296         {
 297             MatchWord *Rj1 =    Rj+  (1+mc->range)*mc->n;
 298             MatchWord *Rj_tmp = Rj+2*(1+mc->range)*mc->n;
 299             Dict_char ch;
 300             int d;
 301
 302             /* Dict_ptr             subptr */
 303             /* Dict_char            sub char */
 304             /* unsigned char        length of information */
 305             /* char *               information */
 306             info = (char*)p - indxp[-lo];
 307             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
 308             prefix[pos] = ch;
 309
 310             move (mc, Rj1, Rj, ch, dfas, Rj_tmp);
 311             for (d = mc->n; --d >= 0; )
 312                 if (Rj1[mc->range*mc->n + d])
 313                     break;
 314             if (d >= 0)
 315             {
 316                 Dict_ptr subptr;
 317                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 318                 {
 319                     int s;
 320                     for (s = 0; s<dfas->no; s++)
 321                         if (dfas->sortarray[s]->rule_no)
 322                             if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
 323                             {
 324                                 prefix[pos+1] = DICT_EOS;
 325                                 (*userfunc)(prefix, info+sizeof(Dict_ptr)+
 326                                             sizeof(Dict_char));
 327                                 break;
 328                             }
 329                 }
 330                 memcpy (&subptr, info, sizeof(Dict_ptr));
 331                 if (subptr)
 332                 {
 333                     dict_grep (dict, subptr, mc, Rj1, pos+1,
 334                                   userfunc, prefix, dfas);
 335                     dict_bf_readp (dict->dbf, ptr, &p);
 336                     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 337                 }
 338             }
 339         }
 340         lo++;
 341     }
 342     return 0;
 343 }
 344
 345 int dict_lookup_grep (Dict dict, Dict_char *pattern, int range,
 346                     int (*userfunc)(Dict_char *name, char *info))
 347 {
 348     MatchWord *Rj;
 349     Dict_char prefix[2048];
 350     char *this_pattern = pattern;
 351     DFA_states *dfas;
 352     MatchContext *mc;
 353     DFA *dfa = init_dfa();
 354     int i, d;
 355
 356     i = parse_dfa (dfa, &this_pattern, dfa_thompson_chars);
 357     if (i || *this_pattern)
 358     {
 359         rm_dfa (&dfa);
 360         return -1;
 361     }
 362     dfa->root = dfa->top;
 363     dfas = mk_dfas (dfa, 200);
 364     rm_dfa (&dfa);
 365
 366     mc = mk_MatchContext (dfas, range);
 367
 368     Rj = xcalloc ((1000+dict_strlen(pattern)+range+2)*(range+1)*mc->n,
 369                   sizeof(*Rj));
 370
 371     set_bit (mc, Rj, 0, 0);
 372     for (d = 1; d<=mc->range; d++)
 373     {
 374         int s;
 375         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
 376         for (s = 0; s<dfas->no; s++)
 377         {
 378             if (get_bit (mc, Rj, d-1, s))
 379             {
 380                 DFA_state *state = dfas->sortarray[s];
 381                 int i = state->tran_no;
 382                 while (--i >= 0)
 383                     set_bit (mc, Rj, d, state->trans[i].to);
 384             }
 385         }
 386     }
 387     i = dict_grep (dict, 1, mc, Rj, 0, userfunc, prefix, dfas);
 388
 389     rm_dfas (&dfas);
 390     xfree (Rj);
 391     return i;
 392 }
 393
 394
 395