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 #include <inttypes.h>
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include "hash.h"
  23 #include "jhash.h"
  24 #include "ovstest.h"
  25
  26 #undef NDEBUG
  27 #include <assert.h>
  28
  29 static void
  30 set_bit(uint32_t array[3], int bit)
  31 {
  32     assert(bit >= 0 && bit <= 96);
  33     memset(array, 0, sizeof(uint32_t) * 3);
  34     if (bit < 96) {
  35         array[bit / 32] = UINT32_C(1) << (bit % 32);
  36     }
  37 }
  38
  39 static uint32_t
  40 hash_words_cb(uint32_t input)
  41 {
  42     return hash_words(&input, 1, 0);
  43 }
  44
  45 static uint32_t
  46 jhash_words_cb(uint32_t input)
  47 {
  48     return jhash_words(&input, 1, 0);
  49 }
  50
  51 static uint32_t
  52 hash_int_cb(uint32_t input)
  53 {
  54     return hash_int(input, 0);
  55 }
  56
  57 static void
  58 check_word_hash(uint32_t (*hash)(uint32_t), const char *name,
  59                 int min_unique)
  60 {
  61     int i, j;
  62
  63     for (i = 0; i <= 32; i++) {
  64         uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0;
  65         for (j = i + 1; j <= 32; j++) {
  66             uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0;
  67             uint32_t out1 = hash(in1);
  68             uint32_t out2 = hash(in2);
  69             const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
  70             int ofs;
  71             for (ofs = 0; ofs < 32 - min_unique; ofs++) {
  72                 uint32_t bits1 = (out1 >> ofs) & unique_mask;
  73                 uint32_t bits2 = (out2 >> ofs) & unique_mask;
  74                 if (bits1 == bits2) {
  75                     printf("Partial collision for '%s':\n", name);
  76                     printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in1, out1);
  77                     printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2);
  78                     printf("%d bits of output starting at bit %d "
  79                            "are both 0x%"PRIx32"\n", min_unique, ofs, bits1);
  80                     exit(1);
  81                 }
  82             }
  83         }
  84     }
  85 }
  86
  87 static void
  88 check_3word_hash(uint32_t (*hash)(const uint32_t[], size_t, uint32_t),
  89                  const char *name)
  90 {
  91     int i, j;
  92
  93     for (i = 0; i <= 96; i++) {
  94         for (j = i + 1; j <= 96; j++) {
  95             uint32_t in0[3], in1[3], in2[3];
  96             uint32_t out0,out1, out2;
  97             const int min_unique = 12;
  98             const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
  99
 100             set_bit(in0, i);
 101             set_bit(in1, i);
 102             set_bit(in2, j);
 103             out0 = hash(in0, 3, 0);
 104             out1 = hash(in1, 3, 0);
 105             out2 = hash(in2, 3, 0);
 106
 107             if (out0 != out1) {
 108                 printf("%s hash not the same for non-64 aligned data "
 109                        "%08"PRIx32" != %08"PRIx32"\n", name, out0, out1);
 110             }
 111             if ((out1 & unique_mask) == (out2 & unique_mask)) {
 112                 printf("%s has a partial collision:\n", name);
 113                 printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
 114                 printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
 115                 printf("The low-order %d bits of output are both "
 116                        "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
 117             }
 118         }
 119     }
 120 }
 121
 122 static void
 123 test_hash_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 124 {
 125     /* Check that all hashes computed with hash_words with one 1-bit (or no
 126      * 1-bits) set within a single 32-bit word have different values in all
 127      * 11-bit consecutive runs.
 128      *
 129      * Given a random distribution, the probability of at least one collision
 130      * in any set of 11 bits is approximately
 131      *
 132      *                      1 - ((2**11 - 1)/2**11)**C(33,2)
 133      *                   == 1 - (2047/2048)**528
 134      *                   =~ 0.22
 135      *
 136      * There are 21 ways to pick 11 consecutive bits in a 32-bit word, so if we
 137      * assumed independence then the chance of having no collisions in any of
 138      * those 11-bit runs would be (1-0.22)**21 =~ .0044.  Obviously
 139      * independence must be a bad assumption :-)
 140      */
 141     check_word_hash(hash_words_cb, "hash_words", 11);
 142     check_word_hash(jhash_words_cb, "jhash_words", 11);
 143
 144     /* Check that all hash functions of with one 1-bit (or no 1-bits) set
 145      * within three 32-bit words have different values in their lowest 12
 146      * bits.
 147      *
 148      * Given a random distribution, the probability of at least one collision
 149      * in 12 bits is approximately
 150      *
 151      *                      1 - ((2**12 - 1)/2**12)**C(97,2)
 152      *                   == 1 - (4095/4096)**4656
 153      *                   =~ 0.68
 154      *
 155      * so we are doing pretty well to not have any collisions in 12 bits.
 156      */
 157     check_3word_hash(hash_words, "hash_words");
 158     check_3word_hash(jhash_words, "jhash_words");
 159
 160     /* Check that all hashes computed with hash_int with one 1-bit (or no
 161      * 1-bits) set within a single 32-bit word have different values in all
 162      * 12-bit consecutive runs.
 163      *
 164      * Given a random distribution, the probability of at least one collision
 165      * in any set of 12 bits is approximately
 166      *
 167      *                      1 - ((2**12 - 1)/2**12)**C(33,2)
 168      *                   == 1 - (4,095/4,096)**528
 169      *                   =~ 0.12
 170      *
 171      * There are 20 ways to pick 12 consecutive bits in a 32-bit word, so if we
 172      * assumed independence then the chance of having no collisions in any of
 173      * those 12-bit runs would be (1-0.12)**20 =~ 0.078.  This refutes our
 174      * assumption of independence, which makes it seem like a good hash
 175      * function.
 176      */
 177     check_word_hash(hash_int_cb, "hash_int", 12);
 178 }
 179
 180 OVSTEST_REGISTER("test-hash", test_hash_main);