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;
 157         ovs_u128 in1;
 158         ovs_u128 out0, out1;
 159
 160         set_bit128(&in1, i, n_bits);
 161         in0.b = in1;
 162         hash(&in0.b, sizeof(ovs_u128), 0, &out0);
 163         hash(&in1, sizeof(ovs_u128), 0, &out1);
 164         if (!ovs_u128_equals(out0, out1)) {
 165             printf("%s hash not the same for non-64 aligned data "
 166                    "%016"PRIx64"%016"PRIx64" != %016"PRIx64"%016"PRIx64"\n",
 167                    name, out0.u64.lo, out0.u64.hi, out1.u64.lo, out1.u64.hi);
 168         }
 169
 170         for (j = i + 1; j <= n_bits; j++) {
 171             ovs_u128 in2;
 172             ovs_u128 out2;
 173             int ofs;
 174
 175             set_bit128(&in2, j, n_bits);
 176             hash(&in2, sizeof(ovs_u128), 0, &out2);
 177             for (ofs = 0; ofs < 128 - min_unique; ofs++) {
 178                 uint64_t bits1 = get_range128(&out1, ofs, unique_mask);
 179                 uint64_t bits2 = get_range128(&out2, ofs, unique_mask);
 180
 181                 if (bits1 == bits2) {
 182                     printf("%s has a partial collision:\n", name);
 183                     printf("hash(1 << %d) == %016"PRIx64"%016"PRIx64"\n",
 184                            i, out1.u64.hi, out1.u64.lo);
 185                     printf("hash(1 << %d) == %016"PRIx64"%016"PRIx64"\n",
 186                            j, out2.u64.hi, out2.u64.lo);
 187                     printf("%d bits of output starting at bit %d "
 188                            "are both 0x%016"PRIx64"\n", min_unique, ofs, bits1);
 189                 }
 190             }
 191         }
 192     }
 193 }
 194
 195 static void
 196 check_256byte_hash(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *),
 197                    const char *name, const int min_unique)
 198 {
 199     const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1;
 200     const int n_bits = sizeof(ovs_u128) * 8 * 16;
 201     int i, j;
 202
 203     for (i = 0; i <= n_bits; i++) {
 204         OVS_PACKED(struct offset_ovs_u128 {
 205             uint32_t a;
 206             ovs_u128 b[16];
 207         }) in0;
 208         ovs_u128 in1[16];
 209         ovs_u128 out0, out1;
 210
 211         set_bit128(in1, i, n_bits);
 212         for (j = 0; j < 16; j++) {
 213             in0.b[j] = in1[j];
 214         }
 215         hash(&in0.b, sizeof(ovs_u128) * 16, 0, &out0);
 216         hash(in1, sizeof(ovs_u128) * 16, 0, &out1);
 217         if (!ovs_u128_equals(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     /*
 246      * The following tests check that all hashes computed with hash_function
 247      * with one 1-bit (or no 1-bits) set within a X-bit word have different
 248      * values in all N-bit consecutive comparisons.
 249      *
 250      *    test_function(hash_function, test_name, N)
 251      *
 252      * Given a random distribution, the probability of at least one collision
 253      * in any set of N bits is approximately
 254      *
 255      *                      1 - (prob of no collisions)
 256      *                          **(combination of all possible comparisons)
 257      *                   == 1 - ((2**N - 1)/2**N)**C(X+1,2)
 258      *                   == p
 259      *
 260      * There are (X-N) ways to pick N consecutive bits in a X-bit word, so if we
 261      * assumed independence then the chance of having no collisions in any of
 262      * those X-bit runs would be (1-p)**(X-N) == q.  If this q is very small
 263      * and we can also find a relatively small 'magic number' N such that there
 264      * is no collision in any comparison, then it means we have a pretty good
 265      * hash function.
 266      *
 267      * The values of each parameters mentioned above for the tested hash
 268      * functions are summarized as follow:
 269      *
 270      * hash_function       X      N        p             q
 271      * -------------      ---    ---    -------       -------
 272      *
 273      * hash_words_cb       32     11     0.22          0.0044
 274      * jhash_words_cb      32     11     0.22          0.0044
 275      * hash_int_cb         32     12     0.12          0.0078
 276      * hash_bytes128      128     19     0.0156        0.174
 277      *
 278      */
 279     check_word_hash(hash_words_cb, "hash_words", 11);
 280     check_word_hash(jhash_words_cb, "jhash_words", 11);
 281     check_word_hash(hash_int_cb, "hash_int", 12);
 282     check_hash_bytes128(hash_bytes128, "hash_bytes128", 19);
 283
 284     /*
 285      * The following tests check that all hashes computed with hash_function
 286      * with one 1-bit (or no 1-bits) set within Y X-bit word have different
 287      * values in their lowest N bits.
 288      *
 289      *    test_function(hash_function, test_name, N)
 290      *
 291      * Given a random distribution, the probability of at least one collision
 292      * in any set of N bits is approximately
 293      *
 294      *                      1 - (prob of no collisions)
 295      *                          **(combination of all possible comparisons)
 296      *                   == 1 - ((2**N - 1)/2**N)**C(Y*X+1,2)
 297      *                   == p
 298      *
 299      * If this p is not very small and we can also find a relatively small
 300      * 'magic number' N such that there is no collision in any comparison,
 301      * then it means we have a pretty good hash function.
 302      *
 303      * The values of each parameters mentioned above for the tested hash
 304      * functions are summarized as follow:
 305      *
 306      * hash_function       Y      X      N        p
 307      * -------------      ---    ---    ---    -------
 308      *
 309      * hash_words          3      32     12     0.68
 310      * jhash_words         3      32     12     0.68
 311      * hash_bytes128      16     128     23     0.22
 312      *
 313      */
 314     check_3word_hash(hash_words, "hash_words");
 315     check_3word_hash(jhash_words, "jhash_words");
 316     check_256byte_hash(hash_bytes128, "hash_bytes128", 23);
 317 }
 318
 319 OVSTEST_REGISTER("test-hash", test_hash_main);