have hex2blf print approx fp rate

Hbomba89 · Nov 4, 2015 · 0c9c9a0 · 0c9c9a0
1 parent bdcf7bd
commit 0c9c9a0
Show file tree

Hide file tree

Showing 2 changed files with 13 additions and 2 deletions.
diff --git a/Makefile b/Makefile
@@ -49,7 +49,7 @@ blfchk: blfchk.o hex.o bloom.o mmapf.o hsearchf.o
 	$(COMPILE) -static $^ $(LIBS) -o $@
 
 hex2blf: hex2blf.o hex.o bloom.o mmapf.o
-	$(COMPILE) -static $^ $(LIBS) -o $@
+	$(COMPILE) -static $^ $(LIBS) -lm -o $@
 
 ecmtabgen: ecmtabgen.o mmapf.o ec_pubkey_fast.o
 	$(COMPILE) -static $^ $(LIBS) -o $@

diff --git a/hex2blf.c b/hex2blf.c
@@ -13,20 +13,27 @@
 
 #include <arpa/inet.h> /*  for ntohl/htonl */
 
+#include <math.h> /* pow/exp */
+
 #include "hex.h"
 #include "bloom.h"
 #include "hash160.h"
 
+const double k_hashes = 20;
+const double m_bits   = 4294967296;
+
 int main(int argc, char **argv) {
   hash160_t hash;
   int i;
   double pct;
   struct stat sb;
   unsigned char *bloom, *hashfile, *bloomfile;
   FILE *f, *b;
-  size_t line_sz = 1024;
+  size_t line_sz = 1024, line_ct = 0;
   char *line;
 
+  double err_rate;
+
   if (argc != 3) {
     fprintf(stderr, "[!] Usage: %s hashfile.hex bloomfile.blf\n", argv[0]);
     exit(1);
@@ -79,6 +86,7 @@ int main(int argc, char **argv) {
   stat(hashfile, &sb);
   fprintf(stderr, "[*] Loading hash160s from '%s' \033[s  0.0%%", hashfile);
   while (getline(&line, &line_sz, f) > 0) {
+    ++line_ct;
     unhex(line, strlen(line), hash.uc, sizeof(hash.uc));
     bloom_set_hash160(bloom, hash.ul);
 
@@ -90,6 +98,9 @@ int main(int argc, char **argv) {
   }
   fprintf(stderr, "\033[u 100.0%%\n");
 
+  err_rate = pow(1 - exp(-k_hashes * line_ct / m_bits), k_hashes);
+  fprintf(stderr, "[*] Loaded %zu hashes, false positive rate: ~%.3e (1 in ~%.3e)\n", line_ct, err_rate, 1/err_rate);
+
   fprintf(stderr, "[*] Writing bloom filter to '%s'...\n", bloomfile);
   if ((fwrite(bloom, BLOOM_SIZE, 1, b)) != 1) {
     fprintf(stderr, "[!] Failed to write bloom filter file '%s'\n", bloomfile);