• R/O
  • SSH
  • HTTPS

tsukurimashou: Commit


Commit MetaInfo

Revision449 (tree)
Time2013-07-30 11:11:50
Authormskala

Log Message

more fixing and tightening of bit vectors

Change Summary

Incremental Difference

--- trunk/idsgrep/idsgrep.h (revision 448)
+++ trunk/idsgrep/idsgrep.h (revision 449)
@@ -24,8 +24,28 @@
2424 #include "config.h"
2525 #include "_stdint.h"
2626
27+#ifdef HAVE_INTTYPES_H
28+# include <inttypes.h>
29+#else
30+# if ULONG_MAX==4294967295UL
31+# ifndef PRIu64
32+# define PRIu64 "llu"
33+# endif
34+# ifndef PRIX64
35+# define PRIX64 "llx"
36+# endif
37+# else
38+# ifndef PRIu64
39+# define PRIu64 "lu"
40+# endif
41+# ifndef PRIX64
42+# define PRIX64 "lx"
43+# endif
44+# endif
45+#endif
46+
2747 #ifdef HAVE_PCRE
28-#include <pcre.h>
48+# include <pcre.h>
2949 #endif
3050
3151 /**********************************************************************/
@@ -129,10 +149,33 @@
129149 #define MSEED_SIZE 13
130150
131151 extern uint32_t magic_seed[MSEED_SIZE];
152+extern int bitvec_debug;
132153
133-void default_needle_bits_fn(NODE *,BIT_FILTER *);
134154 void haystack_bits_fn(NODE *,uint64_t bits[2]);
135155
156+void needle_fn_wrapper(NODE *,BIT_FILTER *);
157+void default_needle_fn(NODE *,BIT_FILTER *);
158+
159+void anything_needle_fn(NODE *,BIT_FILTER *);
160+void anywhere_needle_fn(NODE *,BIT_FILTER *);
161+void and_needle_fn(NODE *,BIT_FILTER *);
162+void or_needle_fn(NODE *,BIT_FILTER *);
163+void not_needle_fn(NODE *,BIT_FILTER *);
164+void unord_needle_fn(NODE *,BIT_FILTER *);
165+
166+/*
167+idsgrep.h:NODE *assoc_match_fn(NODE *);
168+idsgrep.h:NODE *default_match_fn(NODE *);
169+idsgrep.h:NODE *and_or_match_fn(NODE *);
170+idsgrep.h:NODE *anything_match_fn(NODE *);
171+idsgrep.h:NODE *anywhere_match_fn(NODE *);
172+idsgrep.h:NODE *equal_match_fn(NODE *);
173+idsgrep.h:NODE *not_match_fn(NODE *);
174+idsgrep.h:NODE *unord_match_fn(NODE *);
175+idsgrep.h:NODE *regex_match_fn(NODE *);
176+idsgrep.h:NODE *user_match_fn(NODE *);
177+*/
178+
136179 /* This should be:
137180 * - faster than GCC's builtin (which isn't great) when that doesn't
138181 * translate into a native instruction
@@ -153,7 +196,7 @@
153196 x&=UINT64_C(0x0F0F0F0F0F0F0F0F);
154197
155198 y=b[1]-((b[1]>>1)&UINT64_C(0x5555555555555555));
156- y=(x&UINT64_C(0x3333333333333333))+((y>>2)&UINT64_C(0x3333333333333333));
199+ y=(y&UINT64_C(0x3333333333333333))+((y>>2)&UINT64_C(0x3333333333333333));
157200 y+=(y>>4);
158201 y&=UINT64_C(0x0F0F0F0F0F0F0F0F);
159202
@@ -167,8 +210,8 @@
167210 extern int cook_output,canonicalize_input;
168211
169212 void set_output_recipe(char *);
170-void write_bracketed_string(HASHED_STRING *,HASHED_STRING *);
171-void write_cooked_tree(NODE *);
213+void write_bracketed_string(HASHED_STRING *,HASHED_STRING *,FILE *f);
214+void write_cooked_tree(NODE *,FILE *f);
172215
173216 /**********************************************************************/
174217
--- trunk/idsgrep/parse.c (revision 448)
+++ trunk/idsgrep/parse.c (revision 449)
@@ -578,7 +578,7 @@
578578 hashed_bracket[idx]=oph;
579579 }
580580
581-void register_special_functor(char *fctr,int arity,MATCH_FN mf) {
581+void register_special_functor(char *fctr,int arity,MATCH_FN mf,BITVEC_FN bf) {
582582 HASHED_STRING *hs;
583583
584584 hs=new_string(strlen(fctr),fctr);
@@ -590,6 +590,7 @@
590590
591591 hs->arity=arity;
592592 hs->match_fn=mf;
593+ hs->needle_bits_fn=bf;
593594 }
594595
595596 void register_alias(char *fctr,char *canon) {
@@ -631,73 +632,85 @@
631632 register_brackets("\xE3\x80\x94","\xE3\x80\x95",3,13); /* b tortoise */
632633 register_brackets("\xE3\x80\x98","\xE3\x80\x99",3,14); /* w tortoise */
633634
634- register_special_functor(";",0,default_match_fn);
635+ register_special_functor(";",0,default_match_fn,default_needle_fn);
635636
636- register_special_functor(",",2,default_match_fn);
637+ register_special_functor(",",2,default_match_fn,default_needle_fn);
637638
638- register_special_functor("?",0,anything_match_fn);
639+ register_special_functor("?",0,anything_match_fn,anything_needle_fn);
639640 register_alias("anything","?");
640641
641- register_special_functor(".",1,anywhere_match_fn);
642+ register_special_functor(".",1,anywhere_match_fn,anywhere_needle_fn);
642643 register_alias("anywhere",".");
643644
644- register_special_functor("&",2,and_or_match_fn);
645+ register_special_functor("&",2,and_or_match_fn,and_needle_fn);
645646 register_alias("and","&");
646647
647- register_special_functor("|",2,and_or_match_fn);
648+ register_special_functor("|",2,and_or_match_fn,or_needle_fn);
648649 register_alias("or","|");
649650
650- register_special_functor("!",1,not_match_fn);
651+ register_special_functor("!",1,not_match_fn,not_needle_fn);
651652 register_alias("not","!");
652653
653- register_special_functor("*",1,unord_match_fn);
654+ register_special_functor("*",1,unord_match_fn,unord_needle_fn);
654655 register_alias("unord","*");
655656
656- register_special_functor("=",1,equal_match_fn);
657+ register_special_functor("=",1,equal_match_fn,anything_needle_fn);
657658 register_alias("equal","=");
658659
659- register_special_functor("@",1,assoc_match_fn);
660+ register_special_functor("@",1,assoc_match_fn,anything_needle_fn);
660661 register_alias("assoc","@");
661662
662- register_special_functor("/",1,regex_match_fn);
663+ register_special_functor("/",1,regex_match_fn,anything_needle_fn);
663664 register_alias("regex","/");
664665
665- register_special_functor("#",1,user_match_fn);
666+ register_special_functor("#",1,user_match_fn,anything_needle_fn);
666667 register_alias("user","#");
667668
668- register_special_functor("\xE2\xBF\xB0",2,default_match_fn);
669+ register_special_functor("\xE2\xBF\xB0",2,
670+ default_match_fn,default_needle_fn);
669671 register_alias("lr","\xE2\xBF\xB0");
670672
671- register_special_functor("\xE2\xBF\xB1",2,default_match_fn);
673+ register_special_functor("\xE2\xBF\xB1",2,
674+ default_match_fn,default_needle_fn);
672675 register_alias("tb","\xE2\xBF\xB1");
673676
674- register_special_functor("\xE2\xBF\xB2",3,default_match_fn);
677+ register_special_functor("\xE2\xBF\xB2",3,
678+ default_match_fn,default_needle_fn);
675679 register_alias("lcr","\xE2\xBF\xB2");
676680
677- register_special_functor("\xE2\xBF\xB3",3,default_match_fn);
681+ register_special_functor("\xE2\xBF\xB3",3,
682+ default_match_fn,default_needle_fn);
678683 register_alias("tcb","\xE2\xBF\xB3");
679684
680- register_special_functor("\xE2\xBF\xB4",2,default_match_fn);
685+ register_special_functor("\xE2\xBF\xB4",2,
686+ default_match_fn,default_needle_fn);
681687 register_alias("enclose","\xE2\xBF\xB4");
682688
683- register_special_functor("\xE2\xBF\xB5",2,default_match_fn);
689+ register_special_functor("\xE2\xBF\xB5",2,
690+ default_match_fn,default_needle_fn);
684691 register_alias("wrapu","\xE2\xBF\xB5");
685692
686- register_special_functor("\xE2\xBF\xB6",2,default_match_fn);
693+ register_special_functor("\xE2\xBF\xB6",2,
694+ default_match_fn,default_needle_fn);
687695 register_alias("wrapd","\xE2\xBF\xB6");
688696
689- register_special_functor("\xE2\xBF\xB7",2,default_match_fn);
697+ register_special_functor("\xE2\xBF\xB7",2,
698+ default_match_fn,default_needle_fn);
690699 register_alias("wrapl","\xE2\xBF\xB7");
691700
692- register_special_functor("\xE2\xBF\xB8",2,default_match_fn);
701+ register_special_functor("\xE2\xBF\xB8",2,
702+ default_match_fn,default_needle_fn);
693703 register_alias("wrapul","\xE2\xBF\xB8");
694704
695- register_special_functor("\xE2\xBF\xB9",2,default_match_fn);
705+ register_special_functor("\xE2\xBF\xB9",2,
706+ default_match_fn,default_needle_fn);
696707 register_alias("wrapur","\xE2\xBF\xB9");
697708
698- register_special_functor("\xE2\xBF\xBA",2,default_match_fn);
709+ register_special_functor("\xE2\xBF\xBA",2,
710+ default_match_fn,default_needle_fn);
699711 register_alias("wrapll","\xE2\xBF\xBA");
700712
701- register_special_functor("\xE2\xBF\xBB",2,default_match_fn);
713+ register_special_functor("\xE2\xBF\xBB",2,
714+ default_match_fn,default_needle_fn);
702715 register_alias("overlap","\xE2\xBF\xBB");
703716 }
--- trunk/idsgrep/bitvec.c (revision 448)
+++ trunk/idsgrep/bitvec.c (revision 449)
@@ -45,37 +45,63 @@
4545 UINT32_C(0xe381abe9),UINT32_C(0xa0ade382),UINT32_C(0x92e381b6),
4646 UINT32_C(0xe381a4e3),UINT32_C(0x8191e381),UINT32_C(0xa6e6adbb),
4747 UINT32_C(0xe381ad21),
48- (uint32_t)LAMBDA,
48+ (uint32_t)(LAMBDA+128),
4949 (uint32_t)sizeof(INDEX_HEADER),(uint32_t)sizeof(INDEX_RECORD),
5050 };
5151
52+int bitvec_debug=0;
53+static int bvd_indent=0;
54+
5255 /**********************************************************************/
5356
57+/* choose a combination of k out of n bits, depending on h.
58+ * Max n allowed is 32 (and that's the expected case); this uses
59+ * simple modulo on h, which does not guarantee truly uniform choices.
60+ * Should be close enough when n choose k is small in comparison to
61+ * 2**32, and that is the intended use.
62+ */
63+static uint32_t bit_combo(int n,int k,uint32_t h) {
64+ int i,j,a[32];
65+ uint32_t rval;
66+
67+ for (i=0;i<n;i++) a[i]=i;
68+
69+ rval=UINT32_C(0);
70+ for (i=0;i<k;i++) {
71+ j=h%(n-i);
72+ h/=(n-i);
73+
74+ if (j>0) {
75+ j+=i;
76+ a[i]^=a[j];
77+ a[j]^=a[i];
78+ a[i]^=a[j];
79+ }
80+
81+ rval|=UINT32_C(1)<<a[i];
82+ }
83+
84+ return rval;
85+}
86+
87+/**********************************************************************/
88+
5489 void haystack_bits_fn(NODE *n,uint64_t bits[2]) {
5590 int i;
5691 uint32_t hval;
5792 uint64_t cbits[2];
5893
59- bits[0]=UINT64_C(0);
60- bits[1]=UINT64_C(0);
61-
62- /* head */
63- if (n->head!=NULL) {
64- hval=fnv_hash(n->head->length,n->head->data,0);
65- for (i=0;i<=LAMBDA;i++) {
66- bits[0]|=(UINT64_C(1)<<(hval&31));
67- hval>>=5;
68- }
69- }
70-
71- /* functor */
94+ /* head and functor */
7295 hval=fnv_hash(n->functor->length,n->functor->data,1)+
7396 UINT32_C(1108378657)*n->arity;
74- for (i=0;i<=LAMBDA;i++) {
75- bits[0]|=(UINT64_C(1)<<(hval&31));
76- hval>>=5;
77- }
78-
97+ bits[0]=(uint64_t)bit_combo(32,LAMBDA+1,hval);
98+ if (n->head==NULL)
99+ hval=fnv_hash(0,"",0);
100+ else
101+ hval=fnv_hash(n->head->length,n->head->data,0);
102+ bits[0]|=(uint64_t)bit_combo(32,LAMBDA+1,hval);
103+ bits[1]=UINT64_C(0);
104+
79105 /* children */
80106 switch (n->arity) {
81107 case 0:
@@ -93,7 +119,7 @@
93119 case 2:
94120 haystack_bits_fn(n->child[0],cbits);
95121 bits[0]|=(cbits[0]<<32);
96- bits[0]|=(cbits[0]&UINT64_C(0xFFFFFFFF00000000));
122+ bits[1]|=(cbits[0]&UINT64_C(0xFFFFFFFF00000000));
97123 bits[1]|=
98124 ((cbits[1]|(cbits[1]<<32))&UINT64_C(0xFFFFFFFF00000000));
99125
@@ -166,12 +192,40 @@
166192
167193 /* match if x matches or y matches */
168194 static BIT_FILTER *bf_or(BIT_FILTER *z,BIT_FILTER *x,BIT_FILTER *y) {
195+ uint64_t xybits[2];
196+ int i,hi_lambda;
197+
198+ /* find places where they differ */
199+ xybits[0]=x->bits[0]^y->bits[0];
200+ xybits[1]=x->bits[1]^y->bits[1];
201+
202+ /* compute basic OR */
169203 z->bits[0]=x->bits[0]|y->bits[0];
170204 z->bits[1]=x->bits[1]|y->bits[1];
171- if (x->lambda<y->lambda)
172- z->lambda=z->lambda;
173- else
174- z->lambda=y->lambda;
205+ if (x->lambda<y->lambda) {
206+ hi_lambda=y->lambda;
207+ z->lambda=x->lambda;
208+ } else {
209+ hi_lambda=x->lambda;
210+ z->lambda=y->lambda;
211+ }
212+
213+ /* peel off bits as far as possible */
214+ /* speed is not critical here (unlike where we do population count)
215+ * and given that we have to loop anyway when hi_lambda is significantly
216+ * more than z->lambda, it's not clear we'd save much by trying to
217+ * do a super-fast "find highest set bit" operation */
218+ for (i=63;(hi_lambda>z->lambda) && (i>=0);i--)
219+ if (xybits[1]&(UINT64_C(1)<<i)) {
220+ z->bits[1]^=UINT64_C(1)<<i;
221+ hi_lambda--;
222+ }
223+ for (i=63;(hi_lambda>z->lambda) && (i>=0);i--)
224+ if (xybits[0]&(UINT64_C(1)<<i)) {
225+ z->bits[0]^=UINT64_C(1)<<i;
226+ hi_lambda--;
227+ }
228+
175229 return z;
176230 }
177231
@@ -178,8 +232,8 @@
178232 /* match if x matches and y matches */
179233 static BIT_FILTER *bf_and(BIT_FILTER *z,BIT_FILTER *x,BIT_FILTER *y) {
180234 uint64_t xybits[2];
181- int a_max,a_min,b_max,b_min,c_max,c_min,best_filter;
182- int_fast32_t ratio,best_ratio;
235+ int a_max,a_min,b_max,b_min,c_max,c_min;
236+ int ab_min,bc_min,ac_min,abc_min,best_filter;
183237
184238 /* find the bits in common */
185239 xybits[0]=x->bits[0]&y->bits[0];
@@ -194,7 +248,7 @@
194248 if (a_max+b_max+c_max==0)
195249 return ((x->lambda<0) && (y->lambda<0))?bf_true(z):bf_false(z);
196250
197- /* lower bounds */
251+ /* lower bounds, singletons */
198252 a_min=x->lambda+1-b_max;
199253 b_min=x->lambda+1-a_max;
200254 if (y->lambda+1-c_max>b_min)
@@ -204,64 +258,44 @@
204258 if (b_min<0) b_min=0;
205259 if (c_min<0) c_min=0;
206260
261+ /* lower bounds, unions */
262+ ab_min=a_min+b_min;
263+ if (x->lambda+1>ab_min)
264+ ab_min=x->lambda+1;
265+ bc_min=b_min+c_min;
266+ if (y->lambda+1>bc_min)
267+ bc_min=y->lambda+1;
268+ abc_min=a_min+b_min+c_min;
269+ if (x->lambda+y->lambda+2-b_max>abc_min)
270+ abc_min=x->lambda+y->lambda+2-b_max;
271+ ac_min=a_min+c_min;
272+ if (abc_min-b_max>ac_min)
273+ ac_min=abc_min-b_max;
274+
207275 /* find the best filter */
208- best_filter=0;
209- best_ratio=(INT32_C(1000000)*(a_min+b_min+c_min-1))/(a_max+b_max+c_max);
210- if (a_max>0) {
211- ratio=(INT32_C(1000000)*(a_min+b_min-1))/(a_max+b_max);
212- if (ratio>best_ratio) {
213- best_ratio=ratio;
214- best_filter=1;
215- }
216- ratio=(INT32_C(1000000)*(a_min+c_min-1))/(a_max+c_max);
217- if (ratio>best_ratio) {
218- best_ratio=ratio;
219- best_filter=2;
220- }
221- ratio=(INT32_C(1000000)*(a_min-1))/a_max;
222- if (ratio>best_ratio) {
223- best_ratio=ratio;
224- best_filter=3;
225- }
226- }
227- if (b_max>0) {
228- ratio=(INT32_C(1000000)*(b_min+c_min-1))/(b_max+c_max);
229- if (ratio>best_ratio) {
230- best_ratio=ratio;
231- best_filter=4;
232- }
233- ratio=(INT32_C(1000000)*(b_min-1))/b_max;
234- if (ratio>best_ratio) {
235- best_ratio=ratio;
236- best_filter=5;
237- }
238- }
239- if (c_max>0) {
240- ratio=(INT32_C(1000000)*(c_min-1))/c_max;
241- if (ratio>best_ratio) {
242- best_ratio=ratio;
243- best_filter=6;
244- }
245- }
246-
276+ best_filter=((a_min>=a_max/3)?0:4)
277+ +((b_min>=b_max/3)?0:2)
278+ +((c_min>=c_max/3)?0:1);
279+
247280 /* set up the return value */
248281 switch(best_filter) {
249282 case 0: /* ABC */
283+ case 7: /* ABC, last ditch when none of the subsets look good */
250284 z->bits[0]=x->bits[0]|y->bits[0];
251285 z->bits[1]=x->bits[1]|y->bits[1];
252- z->lambda=a_min+b_min+c_min-1;
286+ z->lambda=abc_min-1;
253287 break;
254288
255289 case 1: /* AB */
256290 z->bits[0]=x->bits[0];
257291 z->bits[1]=x->bits[1];
258- z->lambda=a_min+b_min-1;
292+ z->lambda=ab_min-1;
259293 break;
260294
261295 case 2: /* AC */
262296 z->bits[0]=x->bits[0]^y->bits[0];
263297 z->bits[1]=x->bits[1]^y->bits[1];
264- z->lambda=a_min+c_min-1;
298+ z->lambda=ac_min-1;
265299 break;
266300
267301 case 3: /* A */
@@ -296,29 +330,28 @@
296330
297331 /* match if first child of x matches */
298332 static BIT_FILTER *bf_first_child(BIT_FILTER *z,BIT_FILTER *x) {
299- uint64_t collisions[2];
300333 int mylambda;
301-
334+ uint64_t c[2];
335+
302336 /* abort in case of the match-everything filter */
303337 if (x->lambda<0)
304338 return bf_true(z);
305339
306- /* count the collisions introduced by rearrangement */
307- collisions[0]=x->bits[0]&x->bits[1]&UINT64_C(0xFFFFFFFF00000000);
308- collisions[1]=x->bits[1]&((x->bits[1]<<32)
309- |(x->bits[0]&UINT64_C(0xFFFFFFFF00000000)));
310- collisions[0]&=~collisions[1];
340+ /* count collisions */
341+ c[0]=(x->bits[1]|(x->bits[1]<<32))&UINT64_C(0xFFFFFFFF00000000);
342+ c[1]=(x->bits[0]&UINT64_C(0xFFFFFFFF00000000))|(x->bits[0]>>32)
343+ |(x->bits[1]>>32)|(x->bits[1]<<32);
344+ c[0]&=x->bits[0];
345+ c[1]&=x->bits[1];
346+ mylambda=x->lambda-(uint64_2_pop(c)/2);
347+ if (mylambda<x->lambda/3)
348+ mylambda=x->lambda/3;
311349
312- /* find the new lambda, make sure we haven't ruined everything */
313- mylambda=x->lambda-uint64_2_pop(collisions);
314- if (mylambda<0)
315- return bf_true(z);
316-
317350 /* find the new bits */
318351 z->bits[1]=(x->bits[1]|(x->bits[1]<<32)|(x->bits[0]))
319352 &UINT64_C(0xFFFFFFFF00000000);
320353 z->bits[0]=x->bits[0]<<32;
321- x->lambda=mylambda;
354+ z->lambda=mylambda;
322355
323356 return z;
324357 }
@@ -325,42 +358,247 @@
325358
326359 /* match if last child of x matches */
327360 static BIT_FILTER *bf_last_child(BIT_FILTER *z,BIT_FILTER *x) {
328- uint64_t collisions[2];
329361 int mylambda;
330-
362+ uint64_t c[2];
363+
331364 /* abort in case of the match-everything filter */
332365 if (x->lambda<0)
333366 return bf_true(z);
334367
335- /* count the collisions introduced by rearrangement */
336- collisions[0]=x->bits[0]&x->bits[1]&UINT64_C(0xFFFFFFFF00000000);
337- collisions[1]=x->bits[1]&((x->bits[1]<<32)
338- |(x->bits[0]&UINT64_C(0xFFFFFFFF00000000)));
339- collisions[0]&=~collisions[1];
368+ /* count collisions */
369+ c[0]=(x->bits[1]|(x->bits[1]<<32))&UINT64_C(0xFFFFFFFF00000000);
370+ c[1]=(x->bits[0]&UINT64_C(0xFFFFFFFF00000000))|(x->bits[0]>>32)
371+ |(x->bits[1]>>32)|(x->bits[1]<<32);
372+ c[0]&=x->bits[0];
373+ c[1]&=x->bits[1];
374+ mylambda=x->lambda-(uint64_2_pop(c)/2);
375+ if (mylambda<x->lambda/3)
376+ mylambda=x->lambda/3;
340377
341- /* find the new lambda, make sure we haven't ruined everything */
342- mylambda=x->lambda-uint64_2_pop(collisions);
343- if (mylambda<0)
344- return bf_true(z);
345-
346378 /* find the new bits */
347- z->bits[0]=UINT64_C(0);
348379 z->bits[1]=x->bits[0]|(x->bits[1]<<32)|
349380 (x->bits[1]&UINT64_C(0xFFFFFFFF00000000));
350- x->lambda=mylambda;
351-
381+ z->bits[0]=UINT64_C(0);
382+ z->lambda=mylambda;
383+
352384 return z;
353385 }
354386
355387 /* match if middle child of x matches */
356-/* this is a little inefficient, but much easier than trying to do four-way
357- * inclusion-exclusion just for this one relatively rare case. */
358388 static BIT_FILTER *bf_middle_child(BIT_FILTER *z,BIT_FILTER *x) {
359- return bf_last_child(z,bf_last_child(z,x));
389+ int mylambda;
390+ uint64_t c[2];
391+
392+ /* abort in case of the match-everything filter */
393+ if (x->lambda<0)
394+ return bf_true(z);
395+
396+ /* count collisions */
397+ c[0]=(x->bits[0]<<32)|(x->bits[0]>>32)
398+ |x->bits[1]|(x->bits[1]<<32)|(x->bits[1]>>32);
399+ c[1]=(x->bits[0]<<32)|(x->bits[0]>>32)|x->bits[0]
400+ |(x->bits[1]<<32)|(x->bits[1]>>32);
401+ c[0]&=x->bits[0];
402+ c[1]&=x->bits[1];
403+ mylambda=x->lambda-(uint64_2_pop(c)/2);
404+ if (mylambda<x->lambda/4)
405+ mylambda=x->lambda/4;
406+
407+ /* find the new bits */
408+ z->bits[1]=x->bits[0]|x->bits[1];
409+ z->bits[1]=(z->bits[1]|(z->bits[1]>>32))<<32;
410+ z->bits[0]=UINT64_C(0);
411+ z->lambda=x->lambda/4;
412+
413+ return z;
360414 }
361415
362416 /**********************************************************************/
363417
364-void default_needle_bits_fn(NODE *n,BIT_FILTER *f) {
418+void needle_fn_wrapper(NODE *n,BIT_FILTER *f) {
419+ BIT_FILTER fa;
420+ uint32_t hval;
421+ int i;
422+
423+ /* show what we're about to crunch */
424+ if (bitvec_debug) {
425+ for (i=0;i<bvd_indent;i++) fputc(' ',stderr);
426+ write_cooked_tree(n,stderr);
427+ bvd_indent+=3;
428+ }
429+
430+ /* call the node's own needle function */
431+ n->functor->needle_bits_fn(n,f);
432+
433+ /* but if there's a head, then we could match that; else must match
434+ * the absence of head*/
435+ if (n->head!=NULL) {
436+ hval=fnv_hash(0,"",0);
437+ fa.bits[0]=(uint64_t)bit_combo(32,LAMBDA+1,hval);
438+ fa.bits[1]=UINT64_C(0);
439+ fa.lambda=LAMBDA;
440+ bf_and(f,f,&fa);
441+
442+ hval=fnv_hash(n->head->length,n->head->data,0);
443+ fa.bits[0]=(uint64_t)bit_combo(32,LAMBDA+1,hval);
444+ fa.bits[1]=UINT64_C(0);
445+ fa.lambda=LAMBDA;
446+ bf_or(f,f,&fa);
447+ }
448+
449+ /* show the result of crunching it */
450+ if (bitvec_debug) {
451+ bvd_indent-=3;
452+ for (i=0;i<bvd_indent;i++) fputc(' ',stderr);
453+ fprintf(stderr,"%016" PRIX64 "%016" PRIX64 " %d/%d\n",
454+ f->bits[1],f->bits[0],f->lambda+1,uint64_2_pop(f->bits));
455+ }
456+}
457+
458+void default_needle_fn(NODE *n,BIT_FILTER *f) {
459+ BIT_FILTER fa,fb,fc;
460+ int i;
461+ uint32_t hval;
462+
463+ /* functor */
464+ hval=fnv_hash(n->functor->length,n->functor->data,1)+
465+ UINT32_C(1108378657)*n->arity;
466+ f->bits[0]=(uint64_t)bit_combo(32,LAMBDA+1,hval);
467+ f->bits[1]=UINT64_C(0);
468+ f->lambda=LAMBDA;
469+
470+ /* first child */
471+ if (n->arity==0)
472+ bf_true(&fa);
473+ else {
474+ needle_fn_wrapper(n->child[0],&fa);
475+ bf_first_child(&fa,&fa);
476+ }
477+
478+ /* last child */
479+ if (n->arity==0)
480+ bf_true(&fb);
481+ else {
482+ needle_fn_wrapper(n->child[n->arity-1],&fb);
483+ bf_last_child(&fb,&fb);
484+ }
485+
486+ /* middle child */
487+ if (n->arity<3)
488+ bf_true(&fc);
489+ else {
490+ needle_fn_wrapper(n->child[1],&fc);
491+ bf_middle_child(&fc,&fc);
492+ }
493+
494+ /* must match all parts, if we're going that route */
495+ bf_and(f,
496+ bf_and(f,f,&fa),
497+ bf_and(&fb,&fb,&fc));
498+}
499+
500+/**********************************************************************/
501+
502+void anything_needle_fn(NODE *n,BIT_FILTER *f) {
365503 bf_true(f);
366504 }
505+
506+void anywhere_needle_fn(NODE *n,BIT_FILTER *f) {
507+ BIT_FILTER fa,fb;
508+
509+ /* if we are not unary, then it doesn't count */
510+ if (n->arity!=1) {
511+ default_needle_fn(n,f);
512+ return;
513+ }
514+
515+ /* get a filter for the child */
516+ needle_fn_wrapper(n->child[0],f);
517+
518+ /* match if it matches anywhere */
519+ bf_first_child(&fa,f);
520+ fa.bits[1]|=fa.bits[0]>>32;
521+ bf_or(f,bf_or(f,&fa,&fa),bf_middle_child(&fb,f));
522+
523+ /* FIXME make this tighter */
524+}
525+
526+void and_needle_fn(NODE *n,BIT_FILTER *f) {
527+ BIT_FILTER fa;
528+
529+ /* if we are not binary, then it doesn't count */
530+ if (n->arity!=2) {
531+ default_needle_fn(n,f);
532+ return;
533+ }
534+
535+ /* get filters for the children */
536+ needle_fn_wrapper(n->child[0],f);
537+ needle_fn_wrapper(n->child[1],&fa);
538+
539+ /* match if both match */
540+ bf_and(f,f,&fa);
541+}
542+
543+void or_needle_fn(NODE *n,BIT_FILTER *f) {
544+ BIT_FILTER fa;
545+
546+ /* if we are not binary, then it doesn't count */
547+ if (n->arity!=2) {
548+ default_needle_fn(n,f);
549+ return;
550+ }
551+
552+ /* get filters for the children */
553+ needle_fn_wrapper(n->child[0],f);
554+ needle_fn_wrapper(n->child[1],&fa);
555+
556+ /* match if either matches */
557+ bf_or(f,f,&fa);
558+}
559+
560+void not_needle_fn(NODE *n,BIT_FILTER *f) {
561+ /* if we are not unary, then it doesn't count */
562+ if (n->arity!=1) {
563+ default_needle_fn(n,f);
564+ return;
565+ }
566+
567+ /* get filter for the child */
568+ needle_fn_wrapper(n->child[0],f);
569+
570+ /* match if input doesn't match */
571+ bf_not(f,f);
572+}
573+
574+void unord_needle_fn(NODE *n,BIT_FILTER *f) {
575+ BIT_FILTER fa;
576+
577+ /* if we are not unary, then it doesn't count */
578+ if (n->arity!=1) {
579+ default_needle_fn(n,f);
580+ return;
581+ }
582+
583+ /* get filter for the child */
584+ needle_fn_wrapper(n->child[0],f);
585+
586+ /* binary: merge the two children */
587+ if (n->child[0]->arity==2) {
588+ f->bits[1]|=f->bits[0]>>32;
589+ f->bits[0]|=f->bits[1]<<32;
590+
591+ /* ternary: merge all the way around */
592+ } else if (n->child[0]->arity==3) {
593+ f->bits[1]|=f->bits[0]>>32;
594+ f->bits[1]|=f->bits[1]<<32;
595+ f->bits[0]|=f->bits[1]&UINT64_C(0xFFFFFFFF00000000);
596+ f->bits[1]|=f->bits[0]>>32;
597+ }
598+
599+ /* this is a no-op for nullary and unary trees */
600+
601+ /* FIXME figure out a better bound on new lambda */
602+ f->lambda/=3;
603+}
604+
--- trunk/idsgrep/hash.c (revision 448)
+++ trunk/idsgrep/hash.c (revision 449)
@@ -62,7 +62,7 @@
6262 rval->length=len;
6363 rval->arity=-2;
6464 rval->match_fn=default_match_fn;
65- rval->needle_bits_fn=default_needle_bits_fn;
65+ rval->needle_bits_fn=default_needle_fn;
6666 #ifdef HAVE_PCRE
6767 rval->pcre_compiled=NULL;
6868 rval->pcre_studied=NULL;
--- trunk/idsgrep/unilist.c (revision 448)
+++ trunk/idsgrep/unilist.c (revision 449)
@@ -343,7 +343,7 @@
343343 stack_ptr=0;
344344 if (tree_match(match_pattern,to_match)) {
345345 if (cook_output)
346- write_cooked_tree(to_match);
346+ write_cooked_tree(to_match,stdout);
347347 else {
348348 fwrite(ebuf,1,elen-1,stdout);
349349 echoing_whitespace=1;
--- trunk/idsgrep/cook.c (revision 448)
+++ trunk/idsgrep/cook.c (revision 449)
@@ -100,7 +100,7 @@
100100
101101 /**********************************************************************/
102102
103-void write_maybe_escaped_char(char *cp,HASHED_STRING *br) {
103+void write_maybe_escaped_char(char *cp,HASHED_STRING *br,FILE *f) {
104104 int c,do_esc;
105105
106106 switch (char_length(cp)) {
@@ -152,7 +152,7 @@
152152 case '3':
153153 if (((output_recipe[OS_ESCAPE_HOW]=='3') || (c>=0x7F)) &&
154154 (c<=0xFF)) {
155- printf("\\x%02X",c);
155+ fprintf(f,"\\x%02X",c);
156156 break;
157157 }
158158 /* FALL THROUGH */
@@ -160,7 +160,7 @@
160160 case '4':
161161 if (((output_recipe[OS_ESCAPE_HOW]=='4') || (c>0xFF)) &&
162162 (c<=0xFFFF)) {
163- printf("\\X%04X",c);
163+ fprintf(f,"\\X%04X",c);
164164 break;
165165 }
166166 /* FALL THROUGH */
@@ -167,7 +167,7 @@
167167
168168 case '2':
169169 if ((output_recipe[OS_ESCAPE_HOW]=='2') || (c>0xFFFF)) {
170- printf("\\x{%X}",c);
170+ fprintf(f,"\\x{%X}",c);
171171 break;
172172 }
173173 /* FALL THROUGH */
@@ -174,32 +174,32 @@
174174
175175 case '1':
176176 if ((c>=1) && (c<=27)) {
177- fputc('\\',stdout);
177+ fputc('\\',f);
178178 switch (c) {
179179 case 7:
180- fputc('a',stdout);
180+ fputc('a',f);
181181 break;
182182 case 8:
183- fputc('b',stdout);
183+ fputc('b',f);
184184 break;
185185 case 27:
186- fputc('e',stdout);
186+ fputc('e',f);
187187 break;
188188 case 12:
189- fputc('f',stdout);
189+ fputc('f',f);
190190 break;
191191 case 9:
192- fputc('t',stdout);
192+ fputc('t',f);
193193 break;
194194 case 10:
195- fputc('n',stdout);
195+ fputc('n',f);
196196 break;
197197 case 13:
198- fputc('r',stdout);
198+ fputc('r',f);
199199 break;
200200 default:
201- fputc('c',stdout);
202- fputc(c+'A'-1,stdout);
201+ fputc('c',f);
202+ fputc(c+'A'-1,f);
203203 break;
204204 }
205205 break;
@@ -210,34 +210,34 @@
210210 default:
211211 if ((output_recipe[OS_ESCAPE_HOW]=='5') &&
212212 ((c<=0x1F) || (c==0x7F))) {
213- printf("\\x%02X",c);
213+ fprintf(f,"\\x%02X",c);
214214 } else {
215215 if (((c|0x20)<'a') || ((c|0x20)>'z'))
216- fputc('\\',stdout);
217- fwrite(cp,1,char_length(cp),stdout);
216+ fputc('\\',f);
217+ fwrite(cp,1,char_length(cp),f);
218218 }
219219 break;
220220 }
221221 } else
222- fwrite(cp,1,char_length(cp),stdout);
222+ fwrite(cp,1,char_length(cp),f);
223223 }
224224
225-void write_bracketed_string(HASHED_STRING *hs,HASHED_STRING *br) {
225+void write_bracketed_string(HASHED_STRING *hs,HASHED_STRING *br,FILE *f) {
226226 int i;
227227
228- fwrite(br->data,1,br->length,stdout);
228+ fwrite(br->data,1,br->length,f);
229229 for (i=0;i<hs->length;i+=char_length(hs->data+i)) {
230230 if ((i==0) && (output_recipe[OS_ESCAPE_WHAT]<'6'))
231- write_maybe_escaped_char(hs->data+i,NULL);
231+ write_maybe_escaped_char(hs->data+i,NULL,f);
232232 else
233- write_maybe_escaped_char(hs->data+i,br->mate);
233+ write_maybe_escaped_char(hs->data+i,br->mate,f);
234234 }
235- fwrite(br->mate->data,1,br->mate->length,stdout);
235+ fwrite(br->mate->data,1,br->mate->length,f);
236236 }
237237
238238 /**********************************************************************/
239239
240-void write_cooked_tree(NODE *ms) {
240+void write_cooked_tree(NODE *ms,FILE *f) {
241241 NODE *tail;
242242 HASHED_STRING *semicolon,*mf;
243243 int i;
@@ -255,13 +255,13 @@
255255 }
256256
257257 if ((output_recipe[OS_INDENTATION]!='0') && (ms->complete>0))
258- putchar('\n');
258+ fputc('\n',f);
259259 if (output_recipe[OS_INDENTATION]=='8')
260260 for (i=0;i<ms->complete;i++)
261- putchar('\t');
261+ fputc('\t',f);
262262 else
263263 for (i=0;i<(ms->complete*(output_recipe[OS_INDENTATION]-'0'));i++)
264- putchar(' ');
264+ fputc(' ',f);
265265
266266 if (((output_recipe[OS_SUGAR]&2) || (ms->complete==0)) &&
267267 ((output_recipe[OS_SUGAR]&4) || (ms->complete>0)) &&
@@ -271,7 +271,7 @@
271271 (ms->head->arity==-2) &&
272272 (ms->arity==0) &&
273273 (ms->functor==semicolon)) {
274- write_maybe_escaped_char(ms->head->data,NULL);
274+ write_maybe_escaped_char(ms->head->data,NULL,f);
275275
276276 } else {
277277
@@ -280,16 +280,18 @@
280280 if (output_recipe[OS_TOP_HEAD_BRACKET_TYPE]<'2')
281281 write_bracketed_string(ms->head,hashed_bracket
282282 [output_recipe
283- [OS_TOP_HEAD_BRACKET_TYPE]-'0']);
283+ [OS_TOP_HEAD_BRACKET_TYPE]-'0'],
284+ f);
284285 else
285- write_bracketed_string(ms->head,hashed_bracket[2]);
286+ write_bracketed_string(ms->head,hashed_bracket[2],f);
286287 } else {
287288 if (output_recipe[OS_INNER_HEAD_BRACKET_TYPE]<'2')
288289 write_bracketed_string(ms->head,hashed_bracket
289290 [output_recipe
290- [OS_INNER_HEAD_BRACKET_TYPE]-'0']);
291+ [OS_INNER_HEAD_BRACKET_TYPE]-'0'],
292+ f);
291293 else
292- write_bracketed_string(ms->head,hashed_bracket[2]);
294+ write_bracketed_string(ms->head,hashed_bracket[2],f);
293295 }
294296 }
295297
@@ -305,12 +307,12 @@
305307 (mf->arity==ms->arity) &&
306308 (mf->mate==NULL) &&
307309 (char_length(mf->data)==mf->length)) {
308- fwrite(mf->data,mf->length,1,stdout);
310+ fwrite(mf->data,mf->length,1,f);
309311
310312 } else {
311313 i=output_recipe[OS_NULLARY_BRACKET_TYPE+ms->arity]-'0';
312314 if (i>2) i=2;
313- write_bracketed_string(mf,hashed_bracket[3*(ms->arity+1)+i]);
315+ write_bracketed_string(mf,hashed_bracket[3*(ms->arity+1)+i],f);
314316 }
315317 }
316318
@@ -320,18 +322,18 @@
320322
321323 switch (output_recipe[OS_SEPARATOR]) {
322324 case '0':
323- putchar('\0');
325+ fputc('\0',f);
324326 break;
325327 /* 1 is default newline */
326328 case '2':
327- putchar('\n');
328- putchar('\n');
329+ fputc('\n',f);
330+ fputc('\n',f);
329331 break;
330332 case '3':
331333 /* 3 is nothing */
332334 break;
333335 default:
334- putchar('\n');
336+ fputc('\n',f);
335337 break;
336338 }
337339
--- trunk/idsgrep/idsgrep.c (revision 448)
+++ trunk/idsgrep/idsgrep.c (revision 449)
@@ -34,7 +34,6 @@
3434 /**********************************************************************/
3535
3636 static int generate_index=0,ignore_indices=0;
37-
3837 /* basic search and index generation */
3938 void process_file(NODE *match_pattern,char *fn,int fn_flag) {
4039 int read_amt,flag,i;
@@ -119,13 +118,19 @@
119118 haystack_bits_fn(to_match,ir.bits);
120119 fwrite(&ir,sizeof(INDEX_RECORD),1,stdout);
121120 offset+=(parse_ptr-i);
121+ if (bitvec_debug) {
122+ fprintf(stderr,"%016" PRIX64 "%016" PRIX64 "(%3d) ",
123+ ir.bits[1],ir.bits[0],uint64_2_pop(ir.bits));
124+ fwrite(input_buffer+i,1,parse_ptr-i,stderr);
125+ fputc('\n',stderr);
126+ }
122127
123128 } else if (tree_match(match_pattern,to_match)) {
124129 for (i=0;((unsigned char)input_buffer[i])<=0x20;i++);
125130 if (fn_flag>=0)
126- write_bracketed_string(hfn,colon);
131+ write_bracketed_string(hfn,colon,stdout);
127132 if (cook_output)
128- write_cooked_tree(to_match);
133+ write_cooked_tree(to_match,stdout);
129134 else {
130135 fwrite(input_buffer+i,1,parse_ptr-i,stdout);
131136 echoing_whitespace=1;
@@ -164,6 +169,9 @@
164169
165170 #define IDX_REC_BLK 2001
166171
172+static uint64_t bv_checks=UINT64_C(0),bv_hits=UINT64_C(0);
173+static uint64_t tree_hits=UINT64_C(0);
174+
167175 void process_file_indexed(NODE *match_pattern,char *fn,int fn_flag) {
168176 int i,ir_avail,ir_done;
169177 NODE *to_match;
@@ -179,9 +187,9 @@
179187 size_t dict_buff_size=0,entry_size,parsed;
180188
181189 /* bail, if we can't use an index or have been told to ignore it */
182- if ((ignore_indices==1) || generate_index || (strcmp(fn,"-")==0)) {
183- if (ignore_indices==2) {
184- puts("can't use index while generating index, nor on stdin");
190+ if (ignore_indices || generate_index || (strcmp(fn,"-")==0)) {
191+ if (bitvec_debug && !generate_index) {
192+ puts("can't use index on stdin, nor both ignore and debug it");
185193 exit(1);
186194 } else {
187195 process_file(match_pattern,fn,fn_flag);
@@ -195,7 +203,7 @@
195203 if ((i<5) || (strcmp(fn+i-5,".eids")!=0)
196204 || (stat(fn,&stat_buff)!=0)) {
197205 free(ir);
198- if (ignore_indices==2) {
206+ if (bitvec_debug) {
199207 puts("filename doesn't end in .eids, or can't stat");
200208 exit(1);
201209 } else {
@@ -209,7 +217,7 @@
209217 || ((idxfile=fopen(fn,"rb"))==NULL)) {
210218 strcpy(fn+i-4,"eids");
211219 free(ir);
212- if (ignore_indices==2) {
220+ if (bitvec_debug) {
213221 puts("bit vector file too old, or can't stat or open it");
214222 exit(1);
215223 } else {
@@ -228,7 +236,7 @@
228236 || (fread(ir,sizeof(INDEX_RECORD),1,idxfile)!=1)) {
229237 fclose(idxfile);
230238 free(ir);
231- if (ignore_indices==2) {
239+ if (bitvec_debug) {
232240 puts("can't read desired header from bit vector file");
233241 exit(1);
234242 } else {
@@ -240,7 +248,7 @@
240248 /* Now we are committed to index mode. */
241249
242250 /* analyse the query */
243- match_pattern->functor->needle_bits_fn(match_pattern,&bf);
251+ needle_fn_wrapper(match_pattern,&bf);
244252
245253 /* wrap the filename in a string so we can escape-print it */
246254 if (fn_flag>=0)
@@ -271,7 +279,10 @@
271279 for (ir_done=0;ir_done<ir_avail;ir_done++) {
272280 ir[ir_done].bits[0]&=bf.bits[0];
273281 ir[ir_done].bits[1]&=bf.bits[1];
282+ bv_checks++;
283+
274284 if (uint64_2_pop(ir[ir_done].bits)>bf.lambda) {
285+ bv_hits++;
275286
276287 /* go to appropriate place in the file */
277288 if ((offset!=ir[ir_done].offset)
@@ -322,10 +333,11 @@
322333 stack_ptr=0;
323334
324335 if (tree_match(match_pattern,to_match)) {
336+ tree_hits++;
325337 if (fn_flag>=0)
326- write_bracketed_string(hfn,colon);
338+ write_bracketed_string(hfn,colon,stdout);
327339 if (cook_output)
328- write_cooked_tree(to_match);
340+ write_cooked_tree(to_match,stdout);
329341 else
330342 fwrite(dict_buff,1,entry_size,stdout);
331343 }
@@ -352,12 +364,13 @@
352364 /**********************************************************************/
353365
354366 static struct option long_opts[] = {
367+ {"bitvec-debug",no_argument,NULL,'D'|128},
355368 {"cooking",required_argument,NULL,'c'},
356369 {"dictionary",optional_argument,NULL,'d'},
357370 {"font-chars",required_argument,NULL,'f'},
358371 {"help",no_argument,NULL,'h'},
359372 {"generate-index",no_argument,NULL,'G'},
360- {"ignore-indices",optional_argument,NULL,'I'},
373+ {"ignore-indices",no_argument,NULL,'I'},
361374 {"unicode-list",optional_argument,NULL,'U'},
362375 {"version",no_argument,NULL,'V'},
363376 {0,0,0,0},
@@ -376,7 +389,7 @@
376389 char *dictdir,*dictname=NULL,*dictglob,*unilist_cfg=NULL;
377390 glob_t globres;
378391 int show_version=0,show_help=0,generate_list=0;
379-
392+
380393 /* quick usage message */
381394 if (argc<2)
382395 usage_message();
@@ -385,7 +398,7 @@
385398 register_syntax();
386399
387400 /* loop on command-line options */
388- while ((c=getopt_long(argc,argv,"GI::U::Vc:d::f:h",long_opts,NULL))!=-1) {
401+ while ((c=getopt_long(argc,argv,"GIU::Vc:d::f:h",long_opts,NULL))!=-1) {
389402 switch (c) {
390403
391404 case 'G':
@@ -393,14 +406,7 @@
393406 break;
394407
395408 case 'I':
396- if (optarg==NULL)
397- ignore_indices=1;
398- else if (optarg[0]=='I')
399- ignore_indices=2;
400- else {
401- puts("bad argument for -I");
402- exit(1);
403- }
409+ ignore_indices=1;
404410 break;
405411
406412 case 'U':
@@ -431,6 +437,9 @@
431437 show_help=1;
432438 break;
433439
440+ case 'D'|128:
441+ bitvec_debug=1;
442+
434443 default:
435444 break;
436445 }
@@ -449,7 +458,7 @@
449458 "PATTERN should be an Extended Ideographic Description Sequence\n\n"
450459 "Options:\n"
451460 " -G, --generate-index generate bit vector index\n"
452- " -I[I], --ignore-indices[=I] ignore [insist on] bit vectors\n"
461+ " -I, --ignore-indices ignore bit vector indices\n"
453462 " -U, --unicode-list=CFG generate Unicode list\n"
454463 " -V, --version display version and license\n"
455464 " -c, --cooking=FMT set input/output cooking\n"
@@ -456,13 +465,18 @@
456465 " -d, --dictionary=NAME search standard dictionary\n"
457466 " -f, --font-chars=FONT use chars in FONT as a user-defined"
458467 " predicate\n"
468+ " --bitvec-debug verbose bit vector debugging messages"
459469 " -h, --help display this help");
460470
461471 if (show_version || show_help)
462472 exit(0);
463473
464- /* parse matching pattern */
465- if (optind<argc) {
474+ /* parse matching pattern (automatic wildcard in generate mode) */
475+ if (generate_index) {
476+ parse(1,"?");
477+ match_pattern=parse_stack[0];
478+ stack_ptr=0;
479+ } else if (optind<argc) {
466480 if ((parse(strlen(argv[optind]),argv[optind])<strlen(argv[optind]))
467481 || (parse_state!=PS_COMPLETE_TREE)) {
468482 puts("can't parse matching pattern");
@@ -509,6 +523,24 @@
509523 else
510524 puts("(no dictionaries were searched)");
511525 }
526+
527+ /* print statistics */
528+ if (bitvec_debug && !generate_index) {
529+ fprintf(stderr,"%20" PRIu64 " bitvec checks\n",bv_checks);
530+ if (bv_checks>UINT64_C(0)) {
531+ fprintf(stderr,"%20" PRIu64 " bitvec hits (%d.%d%%)\n",
532+ bv_hits,(int)((100*bv_hits)/bv_checks),
533+ ((int)((1000*bv_hits)/bv_checks))%10);
534+ if (bv_hits>UINT64_C(0)) {
535+ fprintf(stderr,"%20" PRIu64 " tree hits (%d.%d%% of bitvec hits, "
536+ "%d.%d%% of all)\n",
537+ tree_hits,(int)((100*tree_hits)/bv_hits),
538+ ((int)((1000*tree_hits)/bv_hits))%10,
539+ (int)((100*tree_hits)/bv_checks),
540+ ((int)((1000*tree_hits)/bv_checks))%10);
541+ }
542+ }
543+ }
512544
513545 exit(0);
514546 }
Show on old repository browser