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