[rustc.git] / src / jemalloc / test / unit / hash.c

/*
 * This file is based on code that is part of SMHasher
 * (https://code.google.com/p/smhasher/), and is subject to the MIT license
 * (http://www.opensource.org/licenses/mit-license.php).  Both email addresses
 * associated with the source code's revision history belong to Austin Appleby,
 * and the revision history ranges from 2010 to 2012.  Therefore the copyright
 * and license are here taken to be:
 *
 * Copyright (c) 2010-2012 Austin Appleby
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include "test/jemalloc_test.h"

typedef enum {
	hash_variant_x86_32,
	hash_variant_x86_128,
	hash_variant_x64_128
} hash_variant_t;

static int
hash_variant_bits(hash_variant_t variant)
{

	switch (variant) {
	case hash_variant_x86_32: return (32);
	case hash_variant_x86_128: return (128);
	case hash_variant_x64_128: return (128);
	default: not_reached();
	}
}

static const char *
hash_variant_string(hash_variant_t variant)
{

	switch (variant) {
	case hash_variant_x86_32: return ("hash_x86_32");
	case hash_variant_x86_128: return ("hash_x86_128");
	case hash_variant_x64_128: return ("hash_x64_128");
	default: not_reached();
	}
}

#define	KEY_SIZE	256
static void
hash_variant_verify_key(hash_variant_t variant, uint8_t *key)
{
	const int hashbytes = hash_variant_bits(variant) / 8;
	const int hashes_size = hashbytes * 256;
	VARIABLE_ARRAY(uint8_t, hashes, hashes_size);
	VARIABLE_ARRAY(uint8_t, final, hashbytes);
	unsigned i;
	uint32_t computed, expected;

	memset(key, 0, KEY_SIZE);
	memset(hashes, 0, hashes_size);
	memset(final, 0, hashbytes);

	/*
	 * Hash keys of the form {0}, {0,1}, {0,1,2}, ..., {0,1,...,255} as the
	 * seed.
	 */
	for (i = 0; i < 256; i++) {
		key[i] = (uint8_t)i;
		switch (variant) {
		case hash_variant_x86_32: {
			uint32_t out;
			out = hash_x86_32(key, i, 256-i);
			memcpy(&hashes[i*hashbytes], &out, hashbytes);
			break;
		} case hash_variant_x86_128: {
			uint64_t out[2];
			hash_x86_128(key, i, 256-i, out);
			memcpy(&hashes[i*hashbytes], out, hashbytes);
			break;
		} case hash_variant_x64_128: {
			uint64_t out[2];
			hash_x64_128(key, i, 256-i, out);
			memcpy(&hashes[i*hashbytes], out, hashbytes);
			break;
		} default: not_reached();
		}
	}

	/* Hash the result array. */
	switch (variant) {
	case hash_variant_x86_32: {
		uint32_t out = hash_x86_32(hashes, hashes_size, 0);
		memcpy(final, &out, sizeof(out));
		break;
	} case hash_variant_x86_128: {
		uint64_t out[2];
		hash_x86_128(hashes, hashes_size, 0, out);
		memcpy(final, out, sizeof(out));
		break;
	} case hash_variant_x64_128: {
		uint64_t out[2];
		hash_x64_128(hashes, hashes_size, 0, out);
		memcpy(final, out, sizeof(out));
		break;
	} default: not_reached();
	}

	computed = (final[0] << 0) | (final[1] << 8) | (final[2] << 16) |
	    (final[3] << 24);

	switch (variant) {
#ifdef JEMALLOC_BIG_ENDIAN
	case hash_variant_x86_32: expected = 0x6213303eU; break;
	case hash_variant_x86_128: expected = 0x266820caU; break;
	case hash_variant_x64_128: expected = 0xcc622b6fU; break;
#else
	case hash_variant_x86_32: expected = 0xb0f57ee3U; break;
	case hash_variant_x86_128: expected = 0xb3ece62aU; break;
	case hash_variant_x64_128: expected = 0x6384ba69U; break;
#endif
	default: not_reached();
	}

	assert_u32_eq(computed, expected,
	    "Hash mismatch for %s(): expected %#x but got %#x",
	    hash_variant_string(variant), expected, computed);
}

static void
hash_variant_verify(hash_variant_t variant)
{
#define	MAX_ALIGN	16
	uint8_t key[KEY_SIZE + (MAX_ALIGN - 1)];
	unsigned i;

	for (i = 0; i < MAX_ALIGN; i++)
		hash_variant_verify_key(variant, &key[i]);
#undef MAX_ALIGN
}
#undef KEY_SIZE

TEST_BEGIN(test_hash_x86_32)
{

	hash_variant_verify(hash_variant_x86_32);
}
TEST_END

TEST_BEGIN(test_hash_x86_128)
{

	hash_variant_verify(hash_variant_x86_128);
}
TEST_END

TEST_BEGIN(test_hash_x64_128)
{

	hash_variant_verify(hash_variant_x64_128);
}
TEST_END

int
main(void)
{

	return (test(
	    test_hash_x86_32,
	    test_hash_x86_128,
	    test_hash_x64_128));
}
Commit	Line	Data
1a4d82fc JJ	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
54a0048b	38	static int
1a4d82fc JJ	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
54a0048b	62	#define KEY_SIZE 256
1a4d82fc	63	static void
54a0048b	64	hash_variant_verify_key(hash_variant_t variant, uint8_t *key)
1a4d82fc	65	{
54a0048b SL	66	const int hashbytes = hash_variant_bits(variant) / 8;
	67	const int hashes_size = hashbytes * 256;
	68	VARIABLE_ARRAY(uint8_t, hashes, hashes_size);
1a4d82fc JJ	69	VARIABLE_ARRAY(uint8_t, final, hashbytes);
	70	unsigned i;
	71	uint32_t computed, expected;
	72
54a0048b SL	73	memset(key, 0, KEY_SIZE);
	74	memset(hashes, 0, hashes_size);
	75	memset(final, 0, hashbytes);
1a4d82fc JJ	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: {
54a0048b	106	uint32_t out = hash_x86_32(hashes, hashes_size, 0);
1a4d82fc JJ	107	memcpy(final, &out, sizeof(out));
	108	break;
	109	} case hash_variant_x86_128: {
	110	uint64_t out[2];
54a0048b	111	hash_x86_128(hashes, hashes_size, 0, out);
1a4d82fc JJ	112	memcpy(final, out, sizeof(out));
	113	break;
	114	} case hash_variant_x64_128: {
	115	uint64_t out[2];
54a0048b	116	hash_x64_128(hashes, hashes_size, 0, out);
1a4d82fc JJ	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
54a0048b SL	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
1a4d82fc JJ	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	}