git://git.onelab.eu
/
sliver-openvswitch.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
new makefile target for error reporting
[sliver-openvswitch.git]
/
tests
/
test-hash.c
diff --git
a/tests/test-hash.c
b/tests/test-hash.c
index
d53ba2e
..
0b7b87a
100644
(file)
--- a/
tests/test-hash.c
+++ b/
tests/test-hash.c
@@
-20,6
+20,7
@@
#include <stdlib.h>
#include <string.h>
#include "hash.h"
#include <stdlib.h>
#include <string.h>
#include "hash.h"
+#include "jhash.h"
#undef NDEBUG
#include <assert.h>
#undef NDEBUG
#include <assert.h>
@@
-41,9
+42,9
@@
hash_words_cb(uint32_t input)
}
static uint32_t
}
static uint32_t
-
m
hash_words_cb(uint32_t input)
+
j
hash_words_cb(uint32_t input)
{
{
- return
m
hash_words(&input, 1, 0);
+ return
j
hash_words(&input, 1, 0);
}
static uint32_t
}
static uint32_t
@@
-130,7
+131,7
@@
main(void)
* independence must be a bad assumption :-)
*/
check_word_hash(hash_words_cb, "hash_words", 11);
* independence must be a bad assumption :-)
*/
check_word_hash(hash_words_cb, "hash_words", 11);
- check_word_hash(
mhash_words_cb, "m
hash_words", 11);
+ check_word_hash(
jhash_words_cb, "j
hash_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
/* 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
@@
-146,24
+147,26
@@
main(void)
* so we are doing pretty well to not have any collisions in 12 bits.
*/
check_3word_hash(hash_words, "hash_words");
* so we are doing pretty well to not have any collisions in 12 bits.
*/
check_3word_hash(hash_words, "hash_words");
- check_3word_hash(
mhash_words, "m
hash_words");
+ check_3word_hash(
jhash_words, "j
hash_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
/* 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
- * 1
4
-bit consecutive runs.
+ * 1
2
-bit consecutive runs.
*
* Given a random distribution, the probability of at least one collision
*
* Given a random distribution, the probability of at least one collision
- * in any set of 1
4
bits is approximately
+ * in any set of 1
2
bits is approximately
*
*
- * 1 - ((2**1
4 - 1)/2**14
)**C(33,2)
- * == 1 - (
16,383/16,834
)**528
- * =~ 0.
031
+ * 1 - ((2**1
2 - 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
* 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", 1
4
);
+ check_word_hash(hash_int_cb, "hash_int", 1
2
);
return 0;
}
return 0;
}