src/jemalloc/test/unit/hash.c

   1 /*
   2  * This file is based on code that is part of SMHasher
   3  * (https://code.google.com/p/smhasher/), and is subject to the MIT license
   4  * (http://www.opensource.org/licenses/mit-license.php).  Both email addresses
   5  * associated with the source code's revision history belong to Austin Appleby,
   6  * and the revision history ranges from 2010 to 2012.  Therefore the copyright
   7  * and license are here taken to be:
   8  *
   9  * Copyright (c) 2010-2012 Austin Appleby
  10  *
  11  * Permission is hereby granted, free of charge, to any person obtaining a copy
  12  * of this software and associated documentation files (the "Software"), to deal
  13  * in the Software without restriction, including without limitation the rights
  14  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  15  * copies of the Software, and to permit persons to whom the Software is
  16  * furnished to do so, subject to the following conditions:
  17  *
  18  * The above copyright notice and this permission notice shall be included in
  19  * all copies or substantial portions of the Software.
  20  *
  21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  22  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  23  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  24  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  25  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  26  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  27  * THE SOFTWARE.
  28  */
  29
  30 #include "test/jemalloc_test.h"
  31
  32 typedef enum {
  33         hash_variant_x86_32,
  34         hash_variant_x86_128,
  35         hash_variant_x64_128
  36 } hash_variant_t;
  37
  38 static int
  39 hash_variant_bits(hash_variant_t variant)
  40 {
  41
  42         switch (variant) {
  43         case hash_variant_x86_32: return (32);
  44         case hash_variant_x86_128: return (128);
  45         case hash_variant_x64_128: return (128);
  46         default: not_reached();
  47         }
  48 }
  49
  50 static const char *
  51 hash_variant_string(hash_variant_t variant)
  52 {
  53
  54         switch (variant) {
  55         case hash_variant_x86_32: return ("hash_x86_32");
  56         case hash_variant_x86_128: return ("hash_x86_128");
  57         case hash_variant_x64_128: return ("hash_x64_128");
  58         default: not_reached();
  59         }
  60 }
  61
  62 #define KEY_SIZE        256
  63 static void
  64 hash_variant_verify_key(hash_variant_t variant, uint8_t *key)
  65 {
  66         const int hashbytes = hash_variant_bits(variant) / 8;
  67         const int hashes_size = hashbytes * 256;
  68         VARIABLE_ARRAY(uint8_t, hashes, hashes_size);
  69         VARIABLE_ARRAY(uint8_t, final, hashbytes);
  70         unsigned i;
  71         uint32_t computed, expected;
  72
  73         memset(key, 0, KEY_SIZE);
  74         memset(hashes, 0, hashes_size);
  75         memset(final, 0, hashbytes);
  76
  77         /*
  78          * Hash keys of the form {0}, {0,1}, {0,1,2}, ..., {0,1,...,255} as the
  79          * seed.
  80          */
  81         for (i = 0; i < 256; i++) {
  82                 key[i] = (uint8_t)i;
  83                 switch (variant) {
  84                 case hash_variant_x86_32: {
  85                         uint32_t out;
  86                         out = hash_x86_32(key, i, 256-i);
  87                         memcpy(&hashes[i*hashbytes], &out, hashbytes);
  88                         break;
  89                 } case hash_variant_x86_128: {
  90                         uint64_t out[2];
  91                         hash_x86_128(key, i, 256-i, out);
  92                         memcpy(&hashes[i*hashbytes], out, hashbytes);
  93                         break;
  94                 } case hash_variant_x64_128: {
  95                         uint64_t out[2];
  96                         hash_x64_128(key, i, 256-i, out);
  97                         memcpy(&hashes[i*hashbytes], out, hashbytes);
  98                         break;
  99                 } default: not_reached();
 100                 }
 101         }
 102
 103         /* Hash the result array. */
 104         switch (variant) {
 105         case hash_variant_x86_32: {
 106                 uint32_t out = hash_x86_32(hashes, hashes_size, 0);
 107                 memcpy(final, &out, sizeof(out));
 108                 break;
 109         } case hash_variant_x86_128: {
 110                 uint64_t out[2];
 111                 hash_x86_128(hashes, hashes_size, 0, out);
 112                 memcpy(final, out, sizeof(out));
 113                 break;
 114         } case hash_variant_x64_128: {
 115                 uint64_t out[2];
 116                 hash_x64_128(hashes, hashes_size, 0, out);
 117                 memcpy(final, out, sizeof(out));
 118                 break;
 119         } default: not_reached();
 120         }
 121
 122         computed = (final[0] << 0) | (final[1] << 8) | (final[2] << 16) |
 123             (final[3] << 24);
 124
 125         switch (variant) {
 126 #ifdef JEMALLOC_BIG_ENDIAN
 127         case hash_variant_x86_32: expected = 0x6213303eU; break;
 128         case hash_variant_x86_128: expected = 0x266820caU; break;
 129         case hash_variant_x64_128: expected = 0xcc622b6fU; break;
 130 #else
 131         case hash_variant_x86_32: expected = 0xb0f57ee3U; break;
 132         case hash_variant_x86_128: expected = 0xb3ece62aU; break;
 133         case hash_variant_x64_128: expected = 0x6384ba69U; break;
 134 #endif
 135         default: not_reached();
 136         }
 137
 138         assert_u32_eq(computed, expected,
 139             "Hash mismatch for %s(): expected %#x but got %#x",
 140             hash_variant_string(variant), expected, computed);
 141 }
 142
 143 static void
 144 hash_variant_verify(hash_variant_t variant)
 145 {
 146 #define MAX_ALIGN       16
 147         uint8_t key[KEY_SIZE + (MAX_ALIGN - 1)];
 148         unsigned i;
 149
 150         for (i = 0; i < MAX_ALIGN; i++)
 151                 hash_variant_verify_key(variant, &key[i]);
 152 #undef MAX_ALIGN
 153 }
 154 #undef KEY_SIZE
 155
 156 TEST_BEGIN(test_hash_x86_32)
 157 {
 158
 159         hash_variant_verify(hash_variant_x86_32);
 160 }
 161 TEST_END
 162
 163 TEST_BEGIN(test_hash_x86_128)
 164 {
 165
 166         hash_variant_verify(hash_variant_x86_128);
 167 }
 168 TEST_END
 169
 170 TEST_BEGIN(test_hash_x64_128)
 171 {
 172
 173         hash_variant_verify(hash_variant_x64_128);
 174 }
 175 TEST_END
 176
 177 int
 178 main(void)
 179 {
 180
 181         return (test(
 182             test_hash_x86_32,
 183             test_hash_x86_128,
 184             test_hash_x64_128));
 185 }