tests/test-hash.c

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