pintos-os.org Git - openvswitch/blob - tests/test-hash.c

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