From 41b82fa1b8fbad44a1cc7671bd614b016b2c38b8 Mon Sep 17 00:00:00 2001
From: Florent Bruneau <florent.bruneau@polytechnique.org>
Date: Tue, 11 Nov 2008 15:21:20 +0100
Subject: [PATCH] Fix build on 64bits.

Signed-off-by: Florent Bruneau <florent.bruneau@polytechnique.org>
---
 common/trie.c        |  6 +--
 common/tst-trie.c    | 98 ++++++++++++++++++++++++++++++++++++++++++++
 postlicyd/greylist.c |  8 ++--
 3 files changed, 105 insertions(+), 7 deletions(-)

diff --git a/common/trie.c b/common/trie.c
index 6bf4cf9..f4240b4 100644
--- a/common/trie.c
+++ b/common/trie.c
@@ -138,12 +138,12 @@ static inline const trie_entry_t* trie_entry_child(const trie_t *trie,
         const char c2 = str(trie, child)[0];
 
         if (c2 == c) {
-          return child;
+            return child;
         }
         if (c < c2) {
-          end = mid;
+            end = mid;
         } else {
-          start = mid + 1;
+            start = mid + 1;
         }
     }
     return NULL;
diff --git a/common/tst-trie.c b/common/tst-trie.c
index 2b7bdee..8902277 100644
--- a/common/tst-trie.c
+++ b/common/tst-trie.c
@@ -86,6 +86,7 @@ static trie_t *create_trie_from_file(const char *file)
     return db;
 }
 
+
 __attribute__((used))
 static void check_trie_with_file(const trie_t *db, const char *file)
 {
@@ -132,8 +133,105 @@ static void check_trie_with_file(const trie_t *db, const char *file)
 }
 
 
+static bool test_linear(const uint8_t *start, uint32_t len, uint8_t data) {
+    const uint8_t *end = start + len;
+    while (start < end) {
+        const uint8_t val = *start;
+        if (val == data) {
+            return true;
+        } else if (val > data) {
+            return false;
+        }
+        ++start;
+    }
+    return false;
+}
+
+static bool test_dicho(const uint8_t *start, uint32_t len, uint8_t data) {
+    const uint8_t *end = start + len;
+
+    while (start < end) {
+        const uint8_t *mid = start + ((end - start) >> 1);
+        const uint8_t val = *mid;
+
+        if (val == data) {
+            return true;
+        } else if (data < val) {
+            end = mid;
+        } else {
+            start = mid + 1;
+        }
+    }
+    return false;
+}
+
+static void test_lookup(void) {
+    bool set[64];
+    uint8_t data[64];
+
+    printf("size,dicho,linear\n");
+    for (int i = 1 ; i < 64 ; ++i) {
+        if (i > 32) {
+            int selected = 64;
+            memset(set, 1, 64 * sizeof(bool));
+            while (selected > i) {
+                int val = rand() % 64;
+                if (set[val]) {
+                    set[val] = false;
+                    --selected;
+                }
+            }
+        } else {
+            int selected = 0;
+            memset(set, 0, 64 * sizeof(bool));
+            while (selected < i) {
+                int val = rand() % 64;
+                if (!set[val]) {
+                    set[val] = true;
+                    ++selected;
+                }
+            }
+        }
+        int pos = 0;
+        for (int j = 0 ; j < 64 ; ++j) {
+            if (set[j]) {
+                data[pos] = j;
+                ++pos;
+            }
+        }
+
+        struct timeval start, end;
+        double diff_dicho, diff_linear;
+        const int iterations = 50000000;
+
+        gettimeofday(&start, NULL);
+        for (int k = 0 ; k < iterations ; ++k) {
+            for (int j = 0 ; j < 64 ; ++j) {
+                test_dicho(data, i, j);
+            }
+        }
+        gettimeofday(&end, NULL);
+        diff_dicho = ((end.tv_sec - start.tv_sec) * 10.0)
+             + (double)(end.tv_usec - start.tv_usec) / 10e5;
+
+        gettimeofday(&start, NULL);
+        for (int k = 0 ; k < iterations ; ++k) {
+            for (int j = 0 ; j < 64 ; ++j) {
+                test_linear(data, i, j);
+            }
+        }
+        gettimeofday(&end, NULL);
+        diff_linear = ((end.tv_sec - start.tv_sec) * 10.0)
+             + (double)(end.tv_usec - start.tv_usec) / 10e5;
+        printf("%d,%d,%d\n", i, (int)diff_dicho, (int)diff_linear);
+    }
+}
+
+
 int main(int argc, char *argv[])
 {
+    test_lookup();
+
     /* Trivial tests
      */
     trie_t *trie = trie_new();
diff --git a/postlicyd/greylist.c b/postlicyd/greylist.c
index beba34d..6bc65db 100644
--- a/postlicyd/greylist.c
+++ b/postlicyd/greylist.c
@@ -372,7 +372,7 @@ static bool try_greylist(const greylist_config_t *config,
     aent.count++;                                             \
     aent.last = now;                                          \
     debug("whitelist entry for %.*s updated, count %d",       \
-          c_addr->len, c_addr->str, aent.count);                     \
+          (int)c_addr->len, c_addr->str, aent.count);         \
     tcbdbput(awl_db, c_addr->str, c_addr->len, &aent, sizeof(aent));
 
     char sbuf[BUFSIZ], cnet[64], key[BUFSIZ];
@@ -393,20 +393,20 @@ static bool try_greylist(const greylist_config_t *config,
         if (res && len == sizeof(aent)) {
             memcpy(&aent, res, len);
             debug("client %.*s has a whitelist entry, count is %d",
-                  c_addr->len, c_addr->str, aent.count);
+                  (int)c_addr->len, c_addr->str, aent.count);
         }
 
         if (!greylist_check_awlentry(config, &aent, now)) {
             aent.count = 0;
             aent.last  = 0;
             debug("client %.*s whitelist entry too old",
-                  c_addr->len, c_addr->str);
+                  (int)c_addr->len, c_addr->str);
         }
 
         /* Whitelist if count is enough.
          */
         if (aent.count >= config->client_awl) {
-            debug("client %.*s whitelisted", c_addr->len, c_addr->str);
+            debug("client %.*s whitelisted", (int)c_addr->len, c_addr->str);
             if (now < aent.last + 3600) {
                 INCR_AWL
             }
-- 
2.20.1