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#include "jemalloc/internal/hash.h" 32 33typedef enum { 34 hash_variant_x86_32, 35 hash_variant_x86_128, 36 hash_variant_x64_128 37} hash_variant_t; 38 39static int 40hash_variant_bits(hash_variant_t variant) { 41 switch (variant) { 42 case hash_variant_x86_32: return 32; 43 case hash_variant_x86_128: return 128; 44 case hash_variant_x64_128: return 128; 45 default: not_reached(); 46 } 47} 48 49static const char * 50hash_variant_string(hash_variant_t variant) { 51 switch (variant) { 52 case hash_variant_x86_32: return "hash_x86_32"; 53 case hash_variant_x86_128: return "hash_x86_128"; 54 case hash_variant_x64_128: return "hash_x64_128"; 55 default: not_reached(); 56 } 57} 58 59#define KEY_SIZE 256 60static void 61hash_variant_verify_key(hash_variant_t variant, uint8_t *key) { 62 const int hashbytes = hash_variant_bits(variant) / 8; 63 const int hashes_size = hashbytes * 256; 64 VARIABLE_ARRAY(uint8_t, hashes, hashes_size); 65 VARIABLE_ARRAY(uint8_t, final, hashbytes); 66 unsigned i; 67 uint32_t computed, expected; 68 69 memset(key, 0, KEY_SIZE); 70 memset(hashes, 0, hashes_size); 71 memset(final, 0, hashbytes); 72 73 /* 74 * Hash keys of the form {0}, {0,1}, {0,1,2}, ..., {0,1,...,255} as the 75 * seed. 76 */ 77 for (i = 0; i < 256; i++) { 78 key[i] = (uint8_t)i; 79 switch (variant) { 80 case hash_variant_x86_32: { 81 uint32_t out; 82 out = hash_x86_32(key, i, 256-i); 83 memcpy(&hashes[i*hashbytes], &out, hashbytes); 84 break; 85 } case hash_variant_x86_128: { 86 uint64_t out[2]; 87 hash_x86_128(key, i, 256-i, out); 88 memcpy(&hashes[i*hashbytes], out, hashbytes); 89 break; 90 } case hash_variant_x64_128: { 91 uint64_t out[2]; 92 hash_x64_128(key, i, 256-i, out); 93 memcpy(&hashes[i*hashbytes], out, hashbytes); 94 break; 95 } default: not_reached(); 96 } 97 } 98 99 /* Hash the result array. */ 100 switch (variant) { 101 case hash_variant_x86_32: { 102 uint32_t out = hash_x86_32(hashes, hashes_size, 0); 103 memcpy(final, &out, sizeof(out)); 104 break; 105 } case hash_variant_x86_128: { 106 uint64_t out[2]; 107 hash_x86_128(hashes, hashes_size, 0, out); 108 memcpy(final, out, sizeof(out)); 109 break; 110 } case hash_variant_x64_128: { 111 uint64_t out[2]; 112 hash_x64_128(hashes, hashes_size, 0, out); 113 memcpy(final, out, sizeof(out)); 114 break; 115 } default: not_reached(); 116 } 117 118 computed = (final[0] << 0) | (final[1] << 8) | (final[2] << 16) | 119 (final[3] << 24); 120 121 switch (variant) { 122#ifdef JEMALLOC_BIG_ENDIAN 123 case hash_variant_x86_32: expected = 0x6213303eU; break; 124 case hash_variant_x86_128: expected = 0x266820caU; break; 125 case hash_variant_x64_128: expected = 0xcc622b6fU; break; 126#else 127 case hash_variant_x86_32: expected = 0xb0f57ee3U; break; 128 case hash_variant_x86_128: expected = 0xb3ece62aU; break; 129 case hash_variant_x64_128: expected = 0x6384ba69U; break; 130#endif 131 default: not_reached(); 132 } 133 134 assert_u32_eq(computed, expected, 135 "Hash mismatch for %s(): expected %#x but got %#x", 136 hash_variant_string(variant), expected, computed); 137} 138 139static void 140hash_variant_verify(hash_variant_t variant) { 141#define MAX_ALIGN 16 142 uint8_t key[KEY_SIZE + (MAX_ALIGN - 1)]; 143 unsigned i; 144 145 for (i = 0; i < MAX_ALIGN; i++) { 146 hash_variant_verify_key(variant, &key[i]); 147 } 148#undef MAX_ALIGN 149} 150#undef KEY_SIZE 151 152TEST_BEGIN(test_hash_x86_32) { 153 hash_variant_verify(hash_variant_x86_32); 154} 155TEST_END 156 157TEST_BEGIN(test_hash_x86_128) { 158 hash_variant_verify(hash_variant_x86_128); 159} 160TEST_END 161 162TEST_BEGIN(test_hash_x64_128) { 163 hash_variant_verify(hash_variant_x64_128); 164} 165TEST_END 166 167int 168main(void) { 169 return test( 170 test_hash_x86_32, 171 test_hash_x86_128, 172 test_hash_x64_128); 173} 174