bmg.c

   1 /*
   2 a quick hack to test an idea for 16 bit BMG string searches
   3
   4 Inspired by the fact that Padre is slow when lots of alternates are
   5 specified in a query
   6
   7 This method reduces the density of zero entries in the delta_table and
   8 also makes the list of candidate targets much smaller when a zero
   9 entry is hit.
  10
  11 It still needs a lot of optimisation. In particular it needs to be
  12 hard wired for 16 bit operation. Currently it can compile for ngraph
  13 based matching, although n>2 would be silly.
  14
  15 Sample usage:
  16
  17 compile it with "gcc -O2 -o bmg16 -DTAG=short bmg.c"
  18
  19 run it with "bmg16 'hello|goodbye|yellow|blue' /usr/dict/words"
  20
  21 Andrew Tridgell
  22 30/3/95
  23 */
  24
  25 #include <stdio.h>
  26 #include <sys/fcntl.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30
  31 /* this determines if the algorithm is 8 or 16 bit - it works for both */
  32 #ifndef TAG
  33 #define TAG short
  34 #endif
  35
  36 typedef unsigned TAG tag;
  37 typedef unsigned char uchar;
  38
  39
  40 #define TABLE_SIZE (1<<(sizeof(tag)*8))
  41 #define DELIMITERS "|"
  42 #define MAX_ALTERNATES 255
  43 #define AVG_ALTERNATES 4
  44 #define PUNCTUATION " \t,;:.\"'`"
  45 #define CASE_MASK (~(1<<5))
  46
  47 #ifndef MIN
  48 #define MIN(a,b) ((a)<(b)?(a):(b))
  49 #endif
  50
  51 /* this is a case insensitive character match */
  52 #define CHAR_EQUAL(c1,c2) (((c1)&CASE_MASK) == ((c2)&CASE_MASK))
  53
  54 static uchar delta_table[TABLE_SIZE];
  55 static uchar target_list[TABLE_SIZE][AVG_ALTERNATES];
  56 static uchar target_list_len[TABLE_SIZE];
  57 static uchar *targets[MAX_ALTERNATES];
  58 static int target_lengths[MAX_ALTERNATES];
  59 static int num_targets = 0;
  60 static int min_target_length = (1<<30);
  61
  62 /* extract a tag value from a buffer. Obviously if the tag size
  63    were fixed (8 or 16 bit) this would be much faster */
  64 static inline tag tag_value(uchar *buf)
  65 {
  66   int i;
  67   unsigned int ret=0;
  68   for (i=0;i<sizeof(tag);i++)
  69     ret |= (buf[i]<<(8*i));
  70   return(ret);
  71 }
  72
  73 /* check if two characters match using the rules for
  74    punctuation */
  75 static inline int uchar_match(uchar c,uchar b)
  76 {
  77   return(CHAR_EQUAL(c,b) || (b==' ' && strchr(PUNCTUATION,c)));
  78 }
  79
  80 /* check if two tags are equal. This is quite general, and slow */
  81 static inline int tag_equal(tag t,uchar *buf,int offset)
  82 {
  83   int i;
  84   if (offset>0) offset=0;
  85   for (i=-offset;i<sizeof(tag);i++)
  86     if (!uchar_match((t>>(8*i))&0xFF,buf[i])) return(0);
  87   return(1);
  88 }
  89
  90 /* compare two strings */
  91 static inline int strnequal(uchar *s1,uchar *s2,int n)
  92 {
  93   while (n--) {
  94     if (!uchar_match(*s2,*s1)) return(0);
  95     s1++; s2++;
  96   }
  97   return(1);
  98 }
  99
 100
 101 /* generate a table of what chars occur at all in the targets */
 102 static void generate_char_table(char *char_table)
 103 {
 104   int has_space=0;
 105   uchar c;
 106   int i,j;
 107   uchar *p = (uchar *)PUNCTUATION;
 108
 109   memset(char_table,0,256);
 110   for (i=0;i<num_targets;i++)
 111     for (j=0;j<target_lengths[i];j++) {
 112       c = targets[i][j];
 113       if (c == ' ')
 114         has_space = 1;
 115       else
 116         char_table[c & CASE_MASK] = char_table[c | ~CASE_MASK] = 1;
 117     }
 118   if (has_space)
 119     for (i=0;i<strlen(p);i++)
 120       char_table[p[i]] = 1;
 121 }
 122
 123
 124
 125 /* check if a tag is possible */
 126 static inline int valid_tag(char *char_table,tag t)
 127 {
 128   if (!char_table[(t>>(8*(sizeof(tag)-1)))&0xFF]) return(0);
 129   return(1);
 130 }
 131
 132
 133 /* build the tables needed for the bmg search */
 134 void bmg_build_table(uchar *target_string)
 135 {
 136   uchar *p = (uchar *)strdup(target_string);
 137   uchar *tok;
 138   int i,j;
 139   int t;
 140   char char_table[256];
 141
 142   num_targets = 0;
 143
 144   /* parse the command */
 145   for (tok=strtok(p,DELIMITERS); tok; tok = strtok(NULL,DELIMITERS)) {
 146     targets[num_targets] = strdup(tok);
 147     target_lengths[num_targets] = strlen(tok);
 148     min_target_length = MIN(min_target_length,target_lengths[num_targets]);
 149     num_targets++;
 150   }
 151   free(p);
 152
 153   if (min_target_length < sizeof(tag))
 154     printf("Error! you have a target smaller than the tag\n");
 155
 156   if (!num_targets) return;
 157
 158   generate_char_table(char_table);
 159
 160   /* built the bmg table - this is a mess */
 161   for (t=0;t<TABLE_SIZE;t++) {
 162
 163     delta_table[t] = min_target_length;
 164     target_list_len[t] = 0;
 165
 166     if (!valid_tag(char_table,t))
 167       continue;
 168
 169     for (i=0;i<num_targets;i++)
 170       {
 171         for (j=(target_lengths[i]-sizeof(tag));j+sizeof(tag)>=1;j--)
 172           if (tag_equal(t,targets[i]+j,j))
 173             {
 174               delta_table[t] = MIN(delta_table[t],
 175                                    target_lengths[i]-(j+sizeof(tag)));
 176               if (target_list_len[t] < AVG_ALTERNATES) {
 177                 target_list[t][target_list_len[t]] = i;
 178                 target_list_len[t]++;
 179               } else {
 180                 target_list_len[t] = MAX_ALTERNATES;
 181               }
 182               break;
 183             }
 184       }
 185   }
 186 }
 187
 188
 189 /* some counters to see how we did */
 190 static int stringops=0;
 191 static int comparisons=0;
 192
 193 /* check if a proposed match is valid */
 194 static inline int check_target(uchar *buf,int pos,int i)
 195 {
 196   int posi = pos-target_lengths[i];
 197   if (posi<0) return(0);
 198   stringops++;
 199   if (strnequal(targets[i],buf+posi,target_lengths[i])) {
 200     printf("Found target %d (%s) at %d\n",i,targets[i],posi);
 201     return(1);
 202   }
 203   return(0);
 204 }
 205
 206
 207 /* the search proper - it takes a buffer and finds the targets previously
 208    specified when building the bmg tables */
 209 void bmg_search(uchar *buf,int len)
 210 {
 211   int pos = 0;
 212   int found = 0;
 213   int hits=0;
 214   int i;
 215
 216   stringops=0;
 217   comparisons=0;
 218
 219   for (pos=min_target_length; pos <= len;)
 220     {
 221       tag v = tag_value(buf+pos-sizeof(tag));
 222       int skip = delta_table[v];
 223       comparisons++;
 224       if (skip) {
 225         pos += skip;
 226         continue;
 227       }
 228
 229       if (target_list_len[v] <= AVG_ALTERNATES)
 230         for (found=0,i=0;i<target_list_len[v] && !found;i++)
 231           found = check_target(buf,pos,target_list[v][i]);
 232       else
 233         for (found=0,i=0;i<num_targets && !found;i++)
 234           found = check_target(buf,pos,i);
 235
 236       if (found) hits++;
 237       pos++;
 238     }
 239
 240   printf("\nGot %d hits with %d comparisons and %d stringops\n",
 241          hits,comparisons,stringops);
 242 }
 243
 244
 245 /* a simple harness to test the above */
 246 int main(int argc,char *argv[])
 247 {
 248   uchar *target;
 249   uchar *buf;
 250   char *fname;
 251   int fd;
 252   int len;
 253
 254   if (argc < 3) {
 255     printf("Usage: bmg string|string|string... file\n");
 256     exit(1);
 257   }
 258
 259   target = (uchar *)argv[1];
 260   fname = argv[2];
 261   fd = open(fname,O_RDONLY);
 262   if (fd < 0) {
 263     printf("couldn't open %s\n",fname);
 264     exit(1);
 265   }
 266   len = lseek(fd,0,SEEK_END);
 267   lseek(fd,0,SEEK_SET);
 268   buf = (uchar *)malloc(len);
 269   if (!buf) {
 270     printf("failed to alloc buffer\n");
 271     exit(1);
 272   }
 273   len = read(fd,buf,len);
 274   close(fd);
 275   printf("Loaded %d bytes\n",len);
 276
 277   bmg_build_table(target);
 278   printf("Finished building tables\n");
 279   bmg_search(buf,len);
 280   return(0);
 281 }
 282