added writesize
[tridge/junkcode.git] / 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