Prepare for post-2.2.0 (2.2.90).

[sliver-openvswitch.git] / tests / test-hash.c

diff --git a/tests/test-hash.c b/tests/test-hash.c
index bdf1435..081e723 100644 (file)
--- a/tests/test-hash.c
+++ b/tests/test-hash.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009 Nicira, Inc.
+ * Copyright (c) 2009, 2012, 2014 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -20,6 +20,8 @@
 #include <stdlib.h>
 #include <string.h>
 #include "hash.h"
+#include "jhash.h"
+#include "ovstest.h"
 
 #undef NDEBUG
 #include <assert.h>
@@ -40,6 +42,12 @@ hash_words_cb(uint32_t input)
     return hash_words(&input, 1, 0);
 }
 
+static uint32_t
+jhash_words_cb(uint32_t input)
+{
+    return jhash_words(&input, 1, 0);
+}
+
 static uint32_t
 hash_int_cb(uint32_t input)
 {
@@ -76,11 +84,37 @@ check_word_hash(uint32_t (*hash)(uint32_t), const char *name,
     }
 }
 
-int
-main(void)
+static void
+check_3word_hash(uint32_t (*hash)(const uint32_t[], size_t, uint32_t),
+                 const char *name)
 {
     int i, j;
 
+    for (i = 0; i <= 96; i++) {
+        for (j = i + 1; j <= 96; j++) {
+            uint32_t in1[3], in2[3];
+            uint32_t out1, out2;
+            const int min_unique = 12;
+            const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
+
+            set_bit(in1, i);
+            set_bit(in2, j);
+            out1 = hash(in1, 3, 0);
+            out2 = hash(in2, 3, 0);
+            if ((out1 & unique_mask) == (out2 & unique_mask)) {
+                printf("%s has a partial collision:\n", name);
+                printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
+                printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
+                printf("The low-order %d bits of output are both "
+                       "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
+            }
+        }
+    }
+}
+
+static void
+test_hash_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
+{
     /* Check that all hashes computed with hash_words with one 1-bit (or no
      * 1-bits) set within a single 32-bit word have different values in all
      * 11-bit consecutive runs.
@@ -98,6 +132,7 @@ main(void)
      * independence must be a bad assumption :-)
      */
     check_word_hash(hash_words_cb, "hash_words", 11);
+    check_word_hash(jhash_words_cb, "jhash_words", 11);
 
     /* Check that all hash functions of with one 1-bit (or no 1-bits) set
      * within three 32-bit words have different values in their lowest 12
@@ -112,44 +147,27 @@ main(void)
      *
      * so we are doing pretty well to not have any collisions in 12 bits.
      */
-    for (i = 0; i <= 96; i++) {
-        for (j = i + 1; j <= 96; j++) {
-            uint32_t in1[3], in2[3];
-            uint32_t out1, out2;
-            const int min_unique = 12;
-            const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
-
-            set_bit(in1, i);
-            set_bit(in2, j);
-            out1 = hash_words(in1, 3, 0);
-            out2 = hash_words(in2, 3, 0);
-            if ((out1 & unique_mask) == (out2 & unique_mask)) {
-                printf("Partial collision:\n");
-                printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
-                printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
-                printf("The low-order %d bits of output are both "
-                       "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
-                exit(1);
-            }
-        }
-    }
+    check_3word_hash(hash_words, "hash_words");
+    check_3word_hash(jhash_words, "jhash_words");
 
     /* Check that all hashes computed with hash_int with one 1-bit (or no
      * 1-bits) set within a single 32-bit word have different values in all
-     * 14-bit consecutive runs.
+     * 12-bit consecutive runs.
      *
      * Given a random distribution, the probability of at least one collision
-     * in any set of 14 bits is approximately
+     * in any set of 12 bits is approximately
      *
-     *                      1 - ((2**14 - 1)/2**14)**C(33,2)
-     *                   == 1 - (16,383/16,834)**528
-     *                   =~ 0.031
+     *                      1 - ((2**12 - 1)/2**12)**C(33,2)
+     *                   == 1 - (4,095/4,096)**528
+     *                   =~ 0.12
      *
-     * There are 18 ways to pick 14 consecutive bits in a 32-bit word, so if we
+     * There are 20 ways to pick 12 consecutive bits in a 32-bit word, so if we
      * assumed independence then the chance of having no collisions in any of
-     * those 14-bit runs would be (1-0.03)**18 =~ 0.56.  This seems reasonable.
+     * those 12-bit runs would be (1-0.12)**20 =~ 0.078.  This refutes our
+     * assumption of independence, which makes it seem like a good hash
+     * function.
      */
-    check_word_hash(hash_int_cb, "hash_int", 14);
-
-    return 0;
+    check_word_hash(hash_int_cb, "hash_int", 12);
 }
+
+OVSTEST_REGISTER("test-hash", test_hash_main);