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