X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=tests%2Ftest-hash.c;h=081e72383c2089c73c1c680b7d6ab45ab2d4b063;hb=0ef165ecb57943e17a8ee8270df68ffb8d032e29;hp=55a544fc0244832841bdc169f117dc271377f81d;hpb=064af42167bf4fc9aaea2702d80ce08074b889c0;p=sliver-openvswitch.git diff --git a/tests/test-hash.c b/tests/test-hash.c index 55a544fc0..081e72383 100644 --- a/tests/test-hash.c +++ b/tests/test-hash.c @@ -1,17 +1,17 @@ /* - * Copyright (c) 2009 Nicira Networks. + * Copyright (c) 2009, 2012, 2014 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 @@ -20,6 +20,8 @@ #include #include #include "hash.h" +#include "jhash.h" +#include "ovstest.h" #undef NDEBUG #include @@ -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);