tests/test-hash.c

   1 /*
   2  * Copyright (c) 2009, 2012, 2014, 2015 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 /* When bit == n_bits, the function just 0 sets the 'values'. */
  39 static void
  40 set_bit128(ovs_u128 *values, int bit, int n_bits)
  41 {
  42     assert(bit >= 0 && bit <= 2048);
  43     memset(values, 0, n_bits/8);
  44     if (bit < n_bits) {
  45         int b = bit % 128;
  46
  47         if (b < 64) {
  48             values[bit / 128].u64.lo = UINT64_C(1) << (b % 64);
  49         } else {
  50             values[bit / 128].u64.hi = UINT64_C(1) << (b % 64);
  51         }
  52     }
  53 }
  54
  55 static uint64_t
  56 get_range128(ovs_u128 *value, int ofs, uint64_t mask)
  57 {
  58     return ((ofs < 64 ? (value->u64.lo >> ofs) : 0) & mask)
  59         | ((ofs <= 64 ? (value->u64.hi << (64 - ofs)) : (value->u64.hi >> (ofs - 64)) & mask));
  60 }
  61
  62 static uint32_t
  63 hash_words_cb(uint32_t input)
  64 {
  65     return hash_words(&input, 1, 0);
  66 }
  67
  68 static uint32_t
  69 jhash_words_cb(uint32_t input)
  70 {
  71     return jhash_words(&input, 1, 0);
  72 }
  73
  74 static uint32_t
  75 hash_int_cb(uint32_t input)
  76 {
  77     return hash_int(input, 0);
  78 }
  79
  80 static void
  81 check_word_hash(uint32_t (*hash)(uint32_t), const char *name,
  82                 int min_unique)
  83 {
  84     int i, j;
  85
  86     for (i = 0; i <= 32; i++) {
  87         uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0;
  88         for (j = i + 1; j <= 32; j++) {
  89             uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0;
  90             uint32_t out1 = hash(in1);
  91             uint32_t out2 = hash(in2);
  92             const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
  93             int ofs;
  94             for (ofs = 0; ofs < 32 - min_unique; ofs++) {
  95                 uint32_t bits1 = (out1 >> ofs) & unique_mask;
  96                 uint32_t bits2 = (out2 >> ofs) & unique_mask;
  97                 if (bits1 == bits2) {
  98                     printf("Partial collision for '%s':\n", name);
  99                     printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in1, out1);
 100                     printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2);
 101                     printf("%d bits of output starting at bit %d "
 102                            "are both 0x%"PRIx32"\n", min_unique, ofs, bits1);
 103                 }
 104             }
 105         }
 106     }
 107 }
 108
 109 static void
 110 check_3word_hash(uint32_t (*hash)(const uint32_t[], size_t, uint32_t),
 111                  const char *name)
 112 {
 113     int i, j;
 114
 115     for (i = 0; i <= 96; i++) {
 116         for (j = i + 1; j <= 96; j++) {
 117             uint32_t in0[3], in1[3], in2[3];
 118             uint32_t out0,out1, out2;
 119             const int min_unique = 12;
 120             const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
 121
 122             set_bit(in0, i);
 123             set_bit(in1, i);
 124             set_bit(in2, j);
 125             out0 = hash(in0, 3, 0);
 126             out1 = hash(in1, 3, 0);
 127             out2 = hash(in2, 3, 0);
 128
 129             if (out0 != out1) {
 130                 printf("%s hash not the same for non-64 aligned data "
 131                        "%08"PRIx32" != %08"PRIx32"\n", name, out0, out1);
 132             }
 133             if ((out1 & unique_mask) == (out2 & unique_mask)) {
 134                 printf("%s has a partial collision:\n", name);
 135                 printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
 136                 printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
 137                 printf("The low-order %d bits of output are both "
 138                        "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
 139             }
 140         }
 141     }
 142 }
 143
 144 static void
 145 check_hash_bytes128(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *),
 146                     const char *name, const int min_unique)
 147 {
 148     const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1;
 149     const int n_bits = sizeof(ovs_u128) * 8;
 150     int i, j;
 151
 152     for (i = 0; i <= n_bits; i++) {
 153         OVS_PACKED(struct offset_ovs_u128 {
 154             uint32_t a;
 155             ovs_u128 b;
 156         }) in0_data;
 157         ovs_u128 *in0, in1;
 158         ovs_u128 out0, out1;
 159
 160         in0 = &in0_data.b;
 161         set_bit128(in0, i, n_bits);
 162         set_bit128(&in1, i, n_bits);
 163         hash(in0, sizeof(ovs_u128), 0, &out0);
 164         hash(&in1, sizeof(ovs_u128), 0, &out1);
 165         if (!ovs_u128_equal(&out0, &out1)) {
 166             printf("%s hash not the same for non-64 aligned data "
 167                    "%016"PRIx64"%016"PRIx64" != %016"PRIx64"%016"PRIx64"\n",
 168                    name, out0.u64.lo, out0.u64.hi, out1.u64.lo, out1.u64.hi);
 169         }
 170
 171         for (j = i + 1; j <= n_bits; j++) {
 172             ovs_u128 in2;
 173             ovs_u128 out2;
 174             int ofs;
 175
 176             set_bit128(&in2, j, n_bits);
 177             hash(&in2, sizeof(ovs_u128), 0, &out2);
 178             for (ofs = 0; ofs < 128 - min_unique; ofs++) {
 179                 uint64_t bits1 = get_range128(&out1, ofs, unique_mask);
 180                 uint64_t bits2 = get_range128(&out2, ofs, unique_mask);
 181
 182                 if (bits1 == bits2) {
 183                     printf("%s has a partial collision:\n", name);
 184                     printf("hash(1 << %d) == %016"PRIx64"%016"PRIx64"\n",
 185                            i, out1.u64.hi, out1.u64.lo);
 186                     printf("hash(1 << %d) == %016"PRIx64"%016"PRIx64"\n",
 187                            j, out2.u64.hi, out2.u64.lo);
 188                     printf("%d bits of output starting at bit %d "
 189                            "are both 0x%016"PRIx64"\n", min_unique, ofs, bits1);
 190                 }
 191             }
 192         }
 193     }
 194 }
 195
 196 static void
 197 check_256byte_hash(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *),
 198                    const char *name, const int min_unique)
 199 {
 200     const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1;
 201     const int n_bits = sizeof(ovs_u128) * 8 * 16;
 202     int i, j;
 203
 204     for (i = 0; i <= n_bits; i++) {
 205         OVS_PACKED(struct offset_ovs_u128 {
 206             uint32_t a;
 207             ovs_u128 b[16];
 208         }) in0_data;
 209         ovs_u128 *in0, in1[16];
 210         ovs_u128 out0, out1;
 211
 212         in0 = in0_data.b;
 213         set_bit128(in0, i, n_bits);
 214         set_bit128(in1, i, n_bits);
 215         hash(in0, sizeof(ovs_u128) * 16, 0, &out0);
 216         hash(in1, sizeof(ovs_u128) * 16, 0, &out1);
 217         if (!ovs_u128_equal(&out0, &out1)) {
 218             printf("%s hash not the same for non-64 aligned data "
 219                    "%016"PRIx64"%016"PRIx64" != %016"PRIx64"%016"PRIx64"\n",
 220                    name, out0.u64.lo, out0.u64.hi, out1.u64.lo, out1.u64.hi);
 221         }
 222
 223         for (j = i + 1; j <= n_bits; j++) {
 224             ovs_u128 in2[16];
 225             ovs_u128 out2;
 226
 227             set_bit128(in2, j, n_bits);
 228             hash(in2, sizeof(ovs_u128) * 16, 0, &out2);
 229             if ((out1.u64.lo & unique_mask) == (out2.u64.lo & unique_mask)) {
 230                 printf("%s has a partial collision:\n", name);
 231                 printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", i,
 232                        out1.u64.hi, out1.u64.lo);
 233                 printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", j,
 234                        out2.u64.hi, out2.u64.lo);
 235                 printf("The low-order %d bits of output are both "
 236                        "0x%"PRIx64"\n", min_unique, out1.u64.lo & unique_mask);
 237             }
 238         }
 239     }
 240 }
 241
 242 static void
 243 test_hash_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 244 {
 245     /* Check that all hashes computed with hash_words with one 1-bit (or no
 246      * 1-bits) set within a single 32-bit word have different values in all
 247      * 11-bit consecutive runs.
 248      *
 249      * Given a random distribution, the probability of at least one collision
 250      * in any set of 11 bits is approximately
 251      *
 252      *                      1 - (proportion of same_bits)
 253      *                          **(binomial_coefficient(n_bits_in_data + 1, 2))
 254      *                   == 1 - ((2**11 - 1)/2**11)**C(33,2)
 255      *                   == 1 - (2047/2048)**528
 256      *                   =~ 0.22
 257      *
 258      * There are 21 ways to pick 11 consecutive bits in a 32-bit word, so if we
 259      * assumed independence then the chance of having no collisions in any of
 260      * those 11-bit runs would be (1-0.22)**21 =~ .0044.  Obviously
 261      * independence must be a bad assumption :-)
 262      */
 263     check_word_hash(hash_words_cb, "hash_words", 11);
 264     check_word_hash(jhash_words_cb, "jhash_words", 11);
 265
 266     /* Check that all hash functions of with one 1-bit (or no 1-bits) set
 267      * within three 32-bit words have different values in their lowest 12
 268      * bits.
 269      *
 270      * Given a random distribution, the probability of at least one collision
 271      * in 12 bits is approximately
 272      *
 273      *                      1 - ((2**12 - 1)/2**12)**C(97,2)
 274      *                   == 1 - (4095/4096)**4656
 275      *                   =~ 0.68
 276      *
 277      * so we are doing pretty well to not have any collisions in 12 bits.
 278      */
 279     check_3word_hash(hash_words, "hash_words");
 280     check_3word_hash(jhash_words, "jhash_words");
 281
 282     /* Check that all hashes computed with hash_int with one 1-bit (or no
 283      * 1-bits) set within a single 32-bit word have different values in all
 284      * 12-bit consecutive runs.
 285      *
 286      * Given a random distribution, the probability of at least one collision
 287      * in any set of 12 bits is approximately
 288      *
 289      *                      1 - ((2**12 - 1)/2**12)**C(33,2)
 290      *                   == 1 - (4,095/4,096)**528
 291      *                   =~ 0.12
 292      *
 293      * There are 20 ways to pick 12 consecutive bits in a 32-bit word, so if we
 294      * assumed independence then the chance of having no collisions in any of
 295      * those 12-bit runs would be (1-0.12)**20 =~ 0.078.  This refutes our
 296      * assumption of independence, which makes it seem like a good hash
 297      * function.
 298      */
 299     check_word_hash(hash_int_cb, "hash_int", 12);
 300
 301     /* Check that all hashes computed with hash_bytes128 with one 1-bit (or no
 302      * 1-bits) set within a single 128-bit word have different values in all
 303      * 19-bit consecutive runs.
 304      *
 305      * Given a random distribution, the probability of at least one collision
 306      * in any set of 19 bits is approximately
 307      *
 308      *                      1 - ((2**19 - 1)/2**19)**C(129,2)
 309      *                   == 1 - (524,287/524,288)**8256
 310      *                   =~ 0.0156
 311      *
 312      * There are 111 ways to pick 19 consecutive bits in a 128-bit word, so if
 313      * we assumed independence then the chance of having no collisions in any of
 314      * those 19-bit runs would be (1-0.0156)**111 =~ 0.174.  This refutes our
 315      * assumption of independence, which makes it seem like a good hash
 316      * function.
 317      */
 318     check_hash_bytes128(hash_bytes128, "hash_bytes128", 19);
 319
 320     /* Check that all hashes computed with hash_bytes128 with 1-bit (or no
 321      * 1-bits) set within 16 128-bit words have different values in their
 322      * lowest 23 bits.
 323      *
 324      * Given a random distribution, the probability of at least one collision
 325      * in any set of 23 bits is approximately
 326      *
 327      *                      1 - ((2**23 - 1)/2**23)**C(2049,2)
 328      *                   == 1 - (8,388,607/8,388,608)**2,098,176
 329      *                   =~ 0.22
 330      *
 331      * so we are doing pretty well to not have any collisions in 23 bits.
 332      */
 333     check_256byte_hash(hash_bytes128, "hash_bytes128", 23);
 334 }
 335
 336 OVSTEST_REGISTER("test-hash", test_hash_main);