bmg2.c

   1 /* COPYRIGHT (C) The Australian National University 1995 */
   2 /*************************************************************************/
   3 /*                              bmg2.c                                     */
   4 /*                      Digraph Boyer-Moore-Gosper algorithm               */
   5 /*                                                                         */
   6 /***************************************************************************/
   7
   8 /* $Id: bmg2.c,v 1.1 2000/10/10 02:16:17 tridge Exp $ */
   9
  10 /*
  11 a digraph version of the bmg algorithm
  12
  13 Andrew Tridgell
  14 30/3/95
  15
  16 Last modified 5/5/95
  17
  18 This module has the following interface:
  19
  20 int bmg_build_table(uchar *target_string,uchar *char_map,int wsmode);
  21 void bmg_search(uchar *buf,int len,void (*fn)());
  22
  23 You call bmg_build_table() with the list of search terms, separated by
  24 | The char_map[] is a character array which maps characters from the
  25 data into characters in the search string. If this is null then a
  26 default mapping is performed. The default mapping maps all non
  27 alphanumeric characters to a space and other characters to themselves.
  28
  29 If wsmode is true then the search routine will only find words that begin
  30 with the target strings. If wsmode is 0 then it will accept the
  31 targets at any alignment.
  32
  33 bmg_search() is called with a pointer to the data, the length of the
  34 data and a function to call when a match is found. This function will
  35 be called with a pointer to the point at which the match was
  36 found. When this function returns the search will automatically
  37 continue from where it left off, calling fn() at each matching string.
  38
  39 Calling bmg_build_table() with a NULL target_string will free the tables
  40 that are created by bmg_build_table().
  41 */
  42
  43 #include <stdio.h>
  44 #include <ctype.h>
  45 #include <sys/fcntl.h>
  46 #include <stdlib.h>
  47 #include <string.h>
  48 #include <sys/time.h>
  49 #include <unistd.h>
  50 #if !AJT
  51 #include "const.h"
  52 #endif
  53
  54 typedef unsigned short tag;
  55
  56 #define TAB14 0
  57 #define TAB16 0
  58
  59 /* if you have targets longer than 255 chars they will be truncated */
  60 #define MAX_TARGET_LENGTH 255
  61
  62 /* this is what is used to delimit search alternates in the target
  63    string passed to the bmg_build_table() routine */
  64 #define DELIMITERS "|"
  65 #define SPACE_CHAR ' '
  66
  67 /* the following defines are optimisation constants. Leave them
  68    alone unless you know the code */
  69 #define DIGRAPH_THRESHOLD 3
  70
  71 #ifndef MIN
  72 #define MIN(a,b) ((a)<(b)?(a):(b))
  73 #endif
  74 #ifndef MAX
  75 #define MAX(a,b) ((a)>(b)?(a):(b))
  76 #endif
  77
  78
  79 struct target {
  80   int next;
  81   u_char *str;
  82   u_char length;
  83 };
  84
  85 static u_char space_char = SPACE_CHAR;
  86 static u_char char_bits = 0;
  87 static int max_char = 0;
  88 static int table_size = 0;
  89 static u_char *delta_table = NULL;
  90 #if TAB14 || TAB16
  91 static u_char *delta_table2 = NULL;
  92 #endif
  93 static tag *tag_table = NULL;
  94 static struct target *targets = NULL;
  95 static tag num_targets = 0;
  96 static int min_target_length = MAX_TARGET_LENGTH;
  97 static int max_target_length = 0;
  98 static tag char_table[256];
  99 static tag char_table_shifted[256];
 100 static int wsmode=0;
 101 static int digraph=1;
 102 static int tagsize=2;
 103
 104 #if TAB14
 105 #define TAGV2(buf) ((((tag)(((u_char *)buf)[1])&0x7F)<<7)|(((u_char *)buf)[0]&0x7f))
 106 #endif
 107 #if TAB16
 108 #define TAGV2(buf) ((((tag)(((u_char *)buf)[1]))<<8)|(((u_char *)buf)[0]))
 109 #endif
 110
 111 /* extract a digraph tag value from a buffer. This must be fast, and
 112  is a clear candidate for assembly optimisation */
 113 static inline tag tag_value16(u_char *buf)
 114 {
 115   return(char_table_shifted[buf[1]]|char_table[buf[0]]);
 116 }
 117
 118 /* this is like tag_value16 but it uses the unmapped characters */
 119 static inline tag tag_value16u(u_char *buf)
 120 {
 121   return((buf[1]<<char_bits)|buf[0]);
 122 }
 123
 124 /* check if two characters match */
 125 static inline int u_char_match(u_char c,u_char b)
 126 {
 127   return(char_table[c] == b);
 128 }
 129
 130 /* compare two strings. We unroll a bit for speed. */
 131 static inline int strnequal(u_char *s1,u_char *s2,int n)
 132 {
 133   while (n>3) {
 134     if (!(u_char_match(s2[0],s1[0]) &&
 135           u_char_match(s2[1],s1[1]) &&
 136           u_char_match(s2[2],s1[2]))) return(0);
 137     s1 += 3; s2 += 3;
 138     n -= 3;
 139   }
 140   while (n) {
 141     if (!u_char_match(s2[0],s1[0])) return(0);
 142     s1++; s2++;
 143     n--;
 144   }
 145   return(1);
 146 }
 147
 148 /* add a tag to the delta table. Possibly update the list of targets
 149    for the tag as well */
 150 static inline void add_to_table(tag t,int i,int j)
 151 {
 152   int skip = targets[i].length-(j+tagsize);
 153   int a;
 154
 155   delta_table[t] = MIN(delta_table[t],skip);
 156
 157   if (skip == 0) {
 158     targets[i].next = MAX(targets[i].next,(int)t);
 159     tag_table[t] = (tag)i;
 160   }
 161 }
 162
 163
 164 /* remap the character tables and the targets to pack them into a small
 165    area in the delta table - this helps the cacheing */
 166 static void remap_char_table(void)
 167 {
 168   int i,j;
 169   u_char target_chars[256];
 170
 171   /* work out what chars exist in the targets */
 172   memset(target_chars,0,256);
 173   for (i=0;i<num_targets;i++)
 174     for (j=0;j<targets[i].length;j++)
 175       target_chars[targets[i].str[j]] = 1;
 176
 177   /* force a space to exist */
 178   if (wsmode) target_chars[SPACE_CHAR] = 1;
 179
 180   /* map each of the chars to a number */
 181   j = 1;
 182   for (i=0;i<256;i++)
 183     if (target_chars[i]) target_chars[i] = j++;
 184   max_char = j;
 185
 186   /* remember what the space is */
 187   space_char = target_chars[SPACE_CHAR];
 188
 189   /* remap the targets */
 190   for (i=0;i<num_targets;i++)
 191     for (j=0;j<targets[i].length;j++)
 192       targets[i].str[j] = target_chars[targets[i].str[j]];
 193
 194   /* remap the char table */
 195   for (i=0;i<256;i++)
 196     char_table[i] = target_chars[char_table[i]];
 197
 198   /* find how many bits are needed for the char table */
 199   char_bits = 0;
 200   i = max_char-1;
 201   while (i) {
 202     char_bits++;
 203     i /= 2;
 204   }
 205
 206   /* create the shifted table */
 207   for (i=0;i<256;i++)
 208     char_table_shifted[i] = char_table[i]<<char_bits;
 209 }
 210
 211
 212 int compare_targets(struct target *t1,struct target *t2)
 213 {
 214   return(t1->next - t2->next);
 215 }
 216
 217 int compare_targets2(int *t1,int *t2)
 218 {
 219   return(targets[*t1].next - targets[*t2].next);
 220 }
 221
 222
 223 static void free_old_tables(void)
 224 {
 225   int i;
 226   /* free up from the last search */
 227   for (i=0;i<num_targets;i++) free(targets[i].str);
 228   if (targets) {free(targets); targets = NULL;}
 229   if (tag_table) {free(tag_table); tag_table = NULL;}
 230   if (delta_table) {free(delta_table); delta_table = NULL;}
 231 #if TAB14 || TAB16
 232   if (delta_table2) {free(delta_table2); delta_table2 = NULL;}
 233 #endif
 234   num_targets = 0;
 235 }
 236
 237 /* build the tables needed for the bmg search */
 238 int bmg_build_table(u_char *target_string,u_char *char_map,int mode)
 239 {
 240   u_char *p;
 241   u_char *tok;
 242   int i,j;
 243   int t;
 244   int dodigraph=0;
 245
 246   /* remember the wsmode */
 247   wsmode = mode;
 248
 249   /* clean up from a previous run */
 250   free_old_tables();
 251   space_char = SPACE_CHAR;
 252
 253   if (!target_string) return(-1);
 254
 255   if (char_map) {
 256     for (i=0;i<256;i++)
 257       char_table[i] = char_map[i];
 258   } else {
 259     for (i=0;i<256;i++)
 260       char_table[i] = isalnum(i)?i:SPACE_CHAR;
 261   }
 262
 263   min_target_length = MAX_TARGET_LENGTH;
 264   max_target_length = 0;
 265
 266   /* count the targets */
 267   p = (u_char *)strdup(target_string);
 268   for (tok=strtok(p,DELIMITERS); tok; tok = strtok(NULL,DELIMITERS))
 269     num_targets++;
 270   free(p);
 271
 272   /* allocate the targets */
 273   targets = (struct target *)malloc(sizeof(targets[0])*num_targets);
 274
 275   if (!targets) {
 276     free_old_tables();
 277     return(-3);
 278   }
 279
 280   /* parse the command */
 281   p = (u_char *)strdup(target_string);
 282   if (!p) {
 283     free_old_tables();
 284     return(-3);
 285   }
 286   i = 0;
 287   for (tok=strtok(p,DELIMITERS); tok; tok = strtok(NULL,DELIMITERS)) {
 288     int l = strlen(tok);
 289     targets[i].next = -1;
 290     targets[i].str = strdup(tok);
 291     if (!targets[i].str) {
 292       free_old_tables();
 293       return(-3);
 294     }
 295     l = MIN(l,MAX_TARGET_LENGTH);
 296     targets[i].length = l;
 297     min_target_length = MIN(min_target_length,targets[i].length);
 298     max_target_length = MAX(max_target_length,targets[i].length);
 299     if (targets[i].str[l-1]==' ') dodigraph=1;
 300     i++;
 301   }
 302   free(p);
 303
 304
 305   /* determine if we will do a digraph search or not */
 306   if (!dodigraph && num_targets<DIGRAPH_THRESHOLD) {
 307     digraph=0;
 308     tagsize=1;
 309   } else {
 310     digraph = 1;
 311     tagsize = 2;
 312   }
 313
 314   if (!num_targets) {
 315     free_old_tables();
 316     return(-2);
 317   }
 318
 319   remap_char_table();
 320
 321   /* build the bmg table - this is a mess */
 322   if (digraph)
 323     table_size = 1<<(char_bits*2);
 324   else
 325     table_size = 256;
 326
 327   delta_table = (u_char *)malloc(table_size*sizeof(delta_table[0]));
 328   tag_table = (tag *)malloc(table_size*sizeof(tag_table[0]));
 329
 330   if (!delta_table || !tag_table) {
 331     free_old_tables();
 332     return(-3);
 333   }
 334
 335 #if TAB14 || TAB16
 336   if (digraph) {
 337 #if TAB14
 338     int tabsize=(1<<14);
 339 #else
 340     int tabsize=(1<<16);
 341 #endif
 342     delta_table2 = (u_char *)malloc(tabsize*sizeof(delta_table[0]));
 343     if (!delta_table2) {
 344       free_old_tables();
 345       return(-3);
 346     }
 347   }
 348 #endif
 349
 350   for (t=0;t<table_size;t++) {
 351     delta_table[t] = min_target_length;
 352     tag_table[t] = num_targets;
 353   }
 354
 355   if (digraph)
 356     {
 357       for (i=0;i<num_targets;i++)
 358         {
 359           int length = targets[i].length;
 360           char *str = targets[i].str;
 361           u_char c[2];
 362           c[1] = str[0];
 363           if (length == min_target_length) {
 364             if (wsmode) {
 365               c[0] = space_char;
 366               t = tag_value16u(c);
 367               add_to_table(t,i,-1);
 368             } else {
 369               for (c[0]=0;;c[0]++)
 370                 {
 371                   /* this little loop handles the first char in each
 372                      target - our tags must match for any possible char
 373                      to the left of it */
 374                   t = tag_value16u(c);
 375                   add_to_table(t,i,-1);
 376                   if (c[0] == (max_char-1)) break;
 377                 }
 378             }
 379           }
 380           for (j=MAX(0,length-(min_target_length+1));j<=(length-2);j++)
 381             {
 382               t = tag_value16u(str+j);
 383               add_to_table(t,i,j);
 384             }
 385         }
 386     }
 387   else
 388     {
 389       for (t=0;t<256;t++)
 390         for (i=0;i<num_targets;i++)
 391           {
 392             int length = targets[i].length;
 393             char *str = targets[i].str;
 394             for (j=(length-1);j>=(length-min_target_length);j--)
 395               if (char_table[t] == str[j]) {
 396                 add_to_table(t,i,j);
 397                 break; /* go to the next target */
 398               }
 399           }
 400     }
 401
 402
 403   if (num_targets>1)
 404     {
 405       int *target_map1 = (int *)malloc(sizeof(int)*num_targets);
 406       int *target_map2 = (int *)malloc(sizeof(int)*num_targets);
 407       if (!target_map1 || !target_map2) {
 408         free_old_tables();
 409         return(-3);
 410       }
 411
 412       for (i=0;i<num_targets;i++) target_map1[i]=i;
 413
 414       /* sort the targets by the "next" value thay have in the target struct */
 415       qsort(target_map1,num_targets,sizeof(int),(int (*)())compare_targets2);
 416       qsort(targets,num_targets,sizeof(targets[0]),(int (*)())compare_targets);
 417
 418       for (i=0;i<num_targets;i++) target_map2[target_map1[i]]=i;
 419
 420       for (t=0;t<table_size;t++) {
 421         if (delta_table[t]) continue;
 422         tag_table[t] = target_map2[tag_table[t]];
 423         while (tag_table[t] &&
 424                targets[tag_table[t]-1].next == targets[tag_table[t]].next)
 425           tag_table[t]--;
 426       }
 427       free(target_map1);
 428       free(target_map2);
 429     }
 430
 431   for (i=0;i<num_targets-1;i++)
 432     if (targets[i].next == targets[i+1].next)
 433       targets[i].next = i+1;
 434     else
 435       targets[i].next = -1;
 436   targets[num_targets-1].next = -1;
 437
 438 #if TAB14
 439   if (digraph) {
 440     u_char c[2];
 441     for (c[0]=0;c[0]<(1<<7);c[0]++)
 442       for (c[1]=0;c[1]<(1<<7);c[1]++)
 443         delta_table2[TAGV2(c)] = delta_table[tag_value16(c)];
 444   }
 445 #endif
 446 #if TAB16
 447   if (digraph) {
 448     tag v;
 449     u_char *c = (u_char *)&v;
 450     for (t=0;t<(1<<16);t++) {
 451       v = t;
 452       delta_table2[TAGV2(c)] = delta_table[tag_value16(c)];
 453     }
 454   }
 455 #endif
 456
 457   return(0);
 458 }
 459
 460
 461 /* check if a single proposed match is valid */
 462 static inline int check_target(u_char *buf,int i,void (*fn)())
 463 {
 464   if (wsmode && char_table[buf[-1]]!=space_char) return(0);
 465   if (strnequal(targets[i].str,buf,targets[i].length) && fn) {
 466     fn(buf);
 467     return(1);
 468   }
 469   return(0);
 470 }
 471
 472
 473 /* check if a proposed match is valid against the list of alternates
 474    for this tag */
 475 static void check_targets(u_char *buf,tag v,void (*fn)())
 476 {
 477   int i = tag_table[v];
 478   do {
 479     u_char *buf2 = buf-targets[i].length;
 480     u_char *str = targets[i].str;
 481     if (u_char_match(*buf2,*str))
 482       check_target(buf2,i,fn);
 483     i = targets[i].next;
 484   } while (i != -1);
 485 }
 486
 487
 488 /* the search proper, 8 bit version - it takes a buffer and finds the
 489    targets previously specified when building the bmg tables */
 490 #define TAGV(buf) ((buf)[0])
 491 #define DELTAB(buf) delta_table[TAGV(buf)]
 492 #define TAGSIZE 1
 493 static void bmg_search8(u_char *buf,int len,void (*fn)())
 494 {
 495   u_char *bufend = buf + len - (TAGSIZE-1);
 496   u_char k;
 497
 498   buf += min_target_length - TAGSIZE;
 499   bufend -= 8*MAX_TARGET_LENGTH;
 500
 501   while (buf<bufend)
 502     {
 503       buf += DELTAB(buf);
 504       buf += DELTAB(buf);
 505       buf += DELTAB(buf);
 506       buf += (k = DELTAB(buf));
 507       if (!k) {
 508         if (DELTAB(buf-2) < 3 && DELTAB(buf-1) < 2)
 509           check_targets(buf+TAGSIZE,TAGV(buf),fn);
 510         buf++;
 511       }
 512     }
 513
 514   bufend += 8*MAX_TARGET_LENGTH;
 515
 516   while (buf<bufend)
 517     {
 518       buf += (k = DELTAB(buf));
 519       if (!k) {
 520         if (DELTAB(buf-2) < 3 && DELTAB(buf-1) < 2)
 521           check_targets(buf+TAGSIZE,TAGV(buf),fn);
 522         buf++;
 523       }
 524     }
 525 }
 526
 527 #undef TAGV
 528 #undef TAGSIZE
 529 #undef DELTAB
 530
 531
 532 #define TAGV(buf) tag_value16(buf)
 533 #if TAB14 || TAB16
 534 #define DELTAB(buf) delta_table2[TAGV2(buf)]
 535 #else
 536 #define DELTAB(buf) delta_table[TAGV(buf)]
 537 #endif
 538 #define TAGSIZE 2
 539 /* this code is identical to the 8 bit search, except for the above two
 540    macros  */
 541 static void bmg_search16(u_char *buf,int len,void (*fn)())
 542 {
 543   u_char *bufend = buf + len - (TAGSIZE-1);
 544   int k;
 545
 546   buf += min_target_length - TAGSIZE;
 547   bufend -= 8*MAX_TARGET_LENGTH;
 548
 549   while (buf<bufend)
 550     {
 551       buf += DELTAB(buf);
 552       buf += DELTAB(buf);
 553       buf += DELTAB(buf);
 554       buf += (k=DELTAB(buf));
 555       if (!k) {
 556         if (DELTAB(buf-2) < 3 && DELTAB(buf-1) < 2)
 557           check_targets(buf+TAGSIZE,TAGV(buf),fn);
 558         buf++;
 559       }
 560     }
 561
 562   bufend += 8*MAX_TARGET_LENGTH;
 563
 564   while (buf<bufend)
 565     {
 566       buf += (k = DELTAB(buf));
 567       if (!k) {
 568         if (DELTAB(buf-2) < 3 && DELTAB(buf-1) < 2)
 569           check_targets(buf+TAGSIZE,TAGV(buf),fn);
 570         buf++;
 571       }
 572     }
 573 }
 574
 575
 576
 577 /* choose 8 or 16 bit search */
 578 void bmg_search(u_char *buf,int len,void (*fn)())
 579 {
 580   int i,j;
 581   if (!num_targets || !buf || !fn || len<1) return;
 582
 583   /* a special case - check the start of the buffer */
 584   for (j=0;j<max_target_length;j++) {
 585     for (i=0;i<num_targets;i++)
 586       if (len >= targets[i].length && check_target(buf,i,fn)) break;
 587     buf++; len--;
 588   }
 589
 590   if (len < 1) return;
 591
 592   if (digraph)
 593     bmg_search16(buf,len,fn);
 594   else
 595     bmg_search8(buf,len,fn);
 596 }