/*
- * Copyright (c) 2009 Nicira Networks.
+ * Copyright (c) 2009, 2012 Nicira, Inc.
*
- * Permission to use, copy, modify, and/or distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
*
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
*/
#include <config.h>
#include <stdlib.h>
#include <string.h>
#include "hash.h"
+#include "jhash.h"
#undef NDEBUG
#include <assert.h>
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)
{
}
}
-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);
+ }
+ }
+ }
+}
+
+int
+main(void)
+{
/* 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.
* 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
*
* 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);
+ check_word_hash(hash_int_cb, "hash_int", 12);
return 0;
}