tests/test-hash.c

   1 /*
   2  * Copyright (c) 2009, 2012, 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #undef NDEBUG
  19 #include "hash.h"
  20 #include <assert.h>
  21 #include <inttypes.h>
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include "jhash.h"
  26 #include "ovstest.h"
  27
  28 static void
  29 set_bit(uint32_t array[3], int bit)
  30 {
  31     assert(bit >= 0 && bit <= 96);
  32     memset(array, 0, sizeof(uint32_t) * 3);
  33     if (bit < 96) {
  34         array[bit / 32] = UINT32_C(1) << (bit % 32);
  35     }
  36 }
  37
  38 static void
  39 set_bit128(ovs_u128 array[16], int bit)
  40 {
  41     assert(bit >= 0 && bit <= 2048);
  42     memset(array, 0, sizeof(ovs_u128) * 16);
  43     if (bit < 2048) {
  44         int b = bit % 128;
  45
  46         if (b < 64) {
  47             array[bit / 128].u64.lo = UINT64_C(1) << (b % 64);
  48         } else {
  49             array[bit / 128].u64.hi = UINT64_C(1) << (b % 64);
  50         }
  51     }
  52 }
  53
  54 static uint32_t
  55 hash_words_cb(uint32_t input)
  56 {
  57     return hash_words(&input, 1, 0);
  58 }
  59
  60 static uint32_t
  61 jhash_words_cb(uint32_t input)
  62 {
  63     return jhash_words(&input, 1, 0);
  64 }
  65
  66 static uint32_t
  67 hash_int_cb(uint32_t input)
  68 {
  69     return hash_int(input, 0);
  70 }
  71
  72 static uint32_t
  73 hash_bytes128_cb(uint32_t input)
  74 {
  75     ovs_u128 hash;
  76
  77     hash_bytes128(&input, sizeof input, 0, &hash);
  78     return hash.u64.lo;
  79 }
  80
  81 static void
  82 check_word_hash(uint32_t (*hash)(uint32_t), const char *name,
  83                 int min_unique)
  84 {
  85     int i, j;
  86
  87     for (i = 0; i <= 32; i++) {
  88         uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0;
  89         for (j = i + 1; j <= 32; j++) {
  90             uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0;
  91             uint32_t out1 = hash(in1);
  92             uint32_t out2 = hash(in2);
  93             const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
  94             int ofs;
  95             for (ofs = 0; ofs < 32 - min_unique; ofs++) {
  96                 uint32_t bits1 = (out1 >> ofs) & unique_mask;
  97                 uint32_t bits2 = (out2 >> ofs) & unique_mask;
  98                 if (bits1 == bits2) {
  99                     printf("Partial collision for '%s':\n", name);
 100                     printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in1, out1);
 101                     printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2);
 102                     printf("%d bits of output starting at bit %d "
 103                            "are both 0x%"PRIx32"\n", min_unique, ofs, bits1);
 104                     exit(1);
 105                 }
 106             }
 107         }
 108     }
 109 }
 110
 111 static void
 112 check_3word_hash(uint32_t (*hash)(const uint32_t[], size_t, uint32_t),
 113                  const char *name)
 114 {
 115     int i, j;
 116
 117     for (i = 0; i <= 96; i++) {
 118         for (j = i + 1; j <= 96; j++) {
 119             uint32_t in0[3], in1[3], in2[3];
 120             uint32_t out0,out1, out2;
 121             const int min_unique = 12;
 122             const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
 123
 124             set_bit(in0, i);
 125             set_bit(in1, i);
 126             set_bit(in2, j);
 127             out0 = hash(in0, 3, 0);
 128             out1 = hash(in1, 3, 0);
 129             out2 = hash(in2, 3, 0);
 130
 131             if (out0 != out1) {
 132                 printf("%s hash not the same for non-64 aligned data "
 133                        "%08"PRIx32" != %08"PRIx32"\n", name, out0, out1);
 134             }
 135             if ((out1 & unique_mask) == (out2 & unique_mask)) {
 136                 printf("%s has a partial collision:\n", name);
 137                 printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
 138                 printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
 139                 printf("The low-order %d bits of output are both "
 140                        "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
 141             }
 142         }
 143     }
 144 }
 145
 146 static void
 147 check_256byte_hash(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *),
 148                    const char *name, const int min_unique)
 149 {
 150     const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1;
 151     const int n_bits = 256 * 8;
 152     int i, j;
 153
 154     for (i = 0; i < n_bits; i++) {
 155         for (j = i + 1; j < n_bits; j++) {
 156             OVS_PACKED(struct offset_ovs_u128 {
 157                 uint32_t a;
 158                 ovs_u128 b[16];
 159             }) in0_data;
 160             ovs_u128 *in0, in1[16], in2[16];
 161             ovs_u128 out0, out1, out2;
 162
 163             in0 = in0_data.b;
 164             set_bit128(in0, i);
 165             set_bit128(in1, i);
 166             set_bit128(in2, j);
 167             hash(in0, sizeof(ovs_u128) * 16, 0, &out0);
 168             hash(in1, sizeof(ovs_u128) * 16, 0, &out1);
 169             hash(in2, sizeof(ovs_u128) * 16, 0, &out2);
 170             if (!ovs_u128_equal(&out0, &out1)) {
 171                 printf("%s hash not the same for non-64 aligned data "
 172                        "%016"PRIx64"%016"PRIx64" != %016"PRIx64"%016"PRIx64"\n",
 173                        name, out0.u64.lo, out0.u64.hi, out1.u64.lo, out1.u64.hi);
 174             }
 175             if ((out1.u64.lo & unique_mask) == (out2.u64.lo & unique_mask)) {
 176                 printf("%s has a partial collision:\n", name);
 177                 printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", i,
 178                        out1.u64.hi, out1.u64.lo);
 179                 printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", j,
 180                        out2.u64.hi, out2.u64.lo);
 181                 printf("The low-order %d bits of output are both "
 182                        "0x%"PRIx64"\n", min_unique, out1.u64.lo & unique_mask);
 183             }
 184         }
 185     }
 186 }
 187
 188 static void
 189 test_hash_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 190 {
 191     /* Check that all hashes computed with hash_words with one 1-bit (or no
 192      * 1-bits) set within a single 32-bit word have different values in all
 193      * 11-bit consecutive runs.
 194      *
 195      * Given a random distribution, the probability of at least one collision
 196      * in any set of 11 bits is approximately
 197      *
 198      *                      1 - (proportion of same_bits)
 199      *                          **(binomial_coefficient(n_bits_in_data + 1, 2))
 200      *                   == 1 - ((2**11 - 1)/2**11)**C(33,2)
 201      *                   == 1 - (2047/2048)**528
 202      *                   =~ 0.22
 203      *
 204      * There are 21 ways to pick 11 consecutive bits in a 32-bit word, so if we
 205      * assumed independence then the chance of having no collisions in any of
 206      * those 11-bit runs would be (1-0.22)**21 =~ .0044.  Obviously
 207      * independence must be a bad assumption :-)
 208      */
 209     check_word_hash(hash_words_cb, "hash_words", 11);
 210     check_word_hash(jhash_words_cb, "jhash_words", 11);
 211
 212     /* Check that all hash functions of with one 1-bit (or no 1-bits) set
 213      * within three 32-bit words have different values in their lowest 12
 214      * bits.
 215      *
 216      * Given a random distribution, the probability of at least one collision
 217      * in 12 bits is approximately
 218      *
 219      *                      1 - ((2**12 - 1)/2**12)**C(97,2)
 220      *                   == 1 - (4095/4096)**4656
 221      *                   =~ 0.68
 222      *
 223      * so we are doing pretty well to not have any collisions in 12 bits.
 224      */
 225     check_3word_hash(hash_words, "hash_words");
 226     check_3word_hash(jhash_words, "jhash_words");
 227
 228     /* Check that all hashes computed with hash_int with one 1-bit (or no
 229      * 1-bits) set within a single 32-bit word have different values in all
 230      * 12-bit consecutive runs.
 231      *
 232      * Given a random distribution, the probability of at least one collision
 233      * in any set of 12 bits is approximately
 234      *
 235      *                      1 - ((2**12 - 1)/2**12)**C(33,2)
 236      *                   == 1 - (4,095/4,096)**528
 237      *                   =~ 0.12
 238      *
 239      * There are 20 ways to pick 12 consecutive bits in a 32-bit word, so if we
 240      * assumed independence then the chance of having no collisions in any of
 241      * those 12-bit runs would be (1-0.12)**20 =~ 0.078.  This refutes our
 242      * assumption of independence, which makes it seem like a good hash
 243      * function.
 244      */
 245     check_word_hash(hash_int_cb, "hash_int", 12);
 246     check_word_hash(hash_bytes128_cb, "hash_bytes128", 12);
 247
 248     /* Check that all hashes computed with hash_bytes128 with 1-bit (or no
 249      * 1-bits) set within 16 128-bit words have different values in their
 250      * lowest 23 bits.
 251      *
 252      * Given a random distribution, the probability of at least one collision
 253      * in any set of 23 bits is approximately
 254      *
 255      *                      1 - ((2**23 - 1)/2**23)**C(2049,2)
 256      *                   == 1 - (8,388,607/8,388,608)**2,098,176
 257      *                   =~ 0.22
 258      *
 259      * so we are doing pretty well to not have any collisions in 23 bits.
 260      */
 261     check_256byte_hash(hash_bytes128, "hash_bytes128", 23);
 262 }
 263
 264 OVSTEST_REGISTER("test-hash", test_hash_main);