OpenGrok

/*	$NetBSD: t_hash.c,v 1.2 2025/04/16 02:27:17 riastradh Exp $	*/

/*-
 * Copyright (c) 2023 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/cdefs.h>

#include <atf-c.h>
#include <stdint.h>

#include "hash.h"

/* known-answer tests */
struct kat {
	const char *in;
	unsigned long long out;
};

/*
 * From the SysV spec, with uint64_t instead of unsigned long to
 * illustrate the problem on all systems, not just LP64 ones.
 *
 * https://www.sco.com/developers/devspecs/gabi41.pdf#page=95
 * https://web.archive.org/web/20241216221811/https://www.sco.com/developers/devspecs/gabi41.pdf#page=95
 */
static uint64_t
sysv_broken_hash(const char *name)
{
	uint64_t h = 0, g;

	while (*name) {
		h = (h << 4) + *name++;
		if ((g = h & 0xf0000000) != 0)
			h ^= g >> 24;
		h &= ~g;
	}

	return h;
}

ATF_TC(sysv);
ATF_TC_HEAD(sysv, tc)
{
	atf_tc_set_md_var(tc, "descr", "SysV hash (32-bit)");
}
ATF_TC_BODY(sysv, tc)
{
	static const struct kat kat[] = {
		{ "", 0x00000000 },
		{ "a", 0x00000061 },
		{ "aa", 0x00000671 },
		{ "aaa", 0x00006771 },
		{ "aaaa", 0x00067771 },
		{ "aaaaa", 0x00677771 },
		{ "aaaaaa", 0x06777771 },
		{ "aaaaaaa", 0x07777711 },
		{ "aaaaaaaa", 0x07777101 },
		{ "aaaaaaaaa", 0x07771001 },
		{ "ab", 0x00000672 },
		{ "abc", 0x00006783 },
		{ "abcd", 0x00067894 },
		{ "abcde", 0x006789a5 },
		{ "abcdef", 0x06789ab6 },
		{ "abcdefg", 0x0789aba7 },
		{ "abcdefgh", 0x089abaa8 },
		{ "abcdefghi", 0x09abaa69 },
		/* https://maskray.me/blog/2023-04-12-elf-hash-function */
		{ "Z", 0x0000005a },
		{ "ZZ", 0x000005fa },
		{ "ZZZ", 0x00005ffa },
		{ "ZZZZ", 0x0005fffa },
		{ "ZZZZZ", 0x005ffffa },
		{ "ZZZZZW", 0x05fffff7 },
		{ "ZZZZZW9", 0x0ffffff9 },
		{ "ZZZZZW9p", 0x00000000 },
		{ "pneumonoultramicroscopicsilicovolcanoconiosis",
		  0x051706b3 },
	};
	unsigned i;

	for (i = 0; i < __arraycount(kat); i++) {
		unsigned long long h = _rtld_sysv_hash(kat[i].in);

		ATF_CHECK_EQ_MSG(h, kat[i].out,
		    "[%u] _rtld_hash_sysv(\"%s\") = 0x%08llx != 0x%08llx",
		    i, kat[i].in, h, kat[i].out);
	}
}

ATF_TC(sysv_broken);
ATF_TC_HEAD(sysv_broken, tc)
{
	atf_tc_set_md_var(tc, "descr",
	    "SysV hash (broken with 64-bit unsigned long)");
}
ATF_TC_BODY(sysv_broken, tc)
{
	static const struct kat kat[] = {
		{ "", 0x00000000 },
		{ "a", 0x00000061 },
		{ "aa", 0x00000671 },
		{ "aaa", 0x00006771 },
		{ "aaaa", 0x00067771 },
		{ "aaaaa", 0x00677771 },
		{ "aaaaaa", 0x06777771 },
		{ "aaaaaaa", 0x07777711 },
		{ "aaaaaaaa", 0x07777101 },
		{ "aaaaaaaaa", 0x07771001 },
		{ "ab", 0x00000672 },
		{ "abc", 0x00006783 },
		{ "abcd", 0x00067894 },
		{ "abcde", 0x006789a5 },
		{ "abcdef", 0x06789ab6 },
		{ "abcdefg", 0x0789aba7 },
		{ "abcdefgh", 0x089abaa8 },
		{ "abcdefghi", 0x09abaa69 },
		/* https://maskray.me/blog/2023-04-12-elf-hash-function */
		{ "Z", 0x0000005a },
		{ "ZZ", 0x000005fa },
		{ "ZZZ", 0x00005ffa },
		{ "ZZZZ", 0x0005fffa },
		{ "ZZZZZ", 0x005ffffa },
		{ "ZZZZZW", 0x05fffff7 },
		{ "ZZZZZW9", 0x0ffffff9 },
		{ "ZZZZZW9p", 0x100000000 },
		{ "pneumonoultramicroscopicsilicovolcanoconiosis",
		  0x051706b3 },
	};
	unsigned i;

	for (i = 0; i < __arraycount(kat); i++) {
		unsigned long long h = sysv_broken_hash(kat[i].in);

		ATF_CHECK_EQ_MSG(h, kat[i].out,
		    "[%u] sysv_broken_hash(\"%s\") = 0x%08llx != 0x%08llx",
		    i, kat[i].in, h, kat[i].out);
	}
}

ATF_TC(gnu);
ATF_TC_HEAD(gnu, tc)
{
	atf_tc_set_md_var(tc, "descr", "GNU hash (djb2)");
}
ATF_TC_BODY(gnu, tc)
{
	static const struct kat kat[] = {
		{ """", 0x00001505 },
		{ "a", 0x0002b606 },
		{ "aa", 0x00597727 },
		{ "aaa", 0x0b885c68 },
		{ "aaaa", 0x7c93e9c9 },
		{ "aaaaa", 0x0f11234a },
		{ "aaaaaa", 0xf1358ceb },
		{ "aaaaaaa", 0x17e72aac },
		{ "aaaaaaaa", 0x14cc808d },
		{ "aaaaaaaaa", 0xae5c928e },
		{ "ab", 0x00597728 },
		{ "abc", 0x0b885c8b },
		{ "abcd", 0x7c93ee4f },
		{ "abcde", 0x0f11b894 },
		{ "abcdef", 0xf148cb7a },
		{ "abcdefg", 0x1a623b21 },
		{ "abcdefgh", 0x66a99fa9 },
		{ "abcdefghi", 0x3bdd9532 },
		{ "Z", 0x0002b5ff },
		{ "ZZ", 0x00597639 },
		{ "ZZZ", 0x0b883db3 },
		{ "ZZZZ", 0x7c8ff46d },
		{ "ZZZZZ", 0x0e8e8267 },
		{ "ZZZZZW", 0xe05ecf9e },
		{ "ZZZZZW9", 0xec38c397 },
		{ "ZZZZZW9p", 0x735136e7 },
		{ "pneumonoultramicroscopicsilicovolcanoconiosis",
		  0xee6245b5 },
	};
	unsigned i;

	for (i = 0; i < __arraycount(kat); i++) {
		unsigned long long h = _rtld_gnu_hash(kat[i].in);

		ATF_CHECK_EQ_MSG(h, kat[i].out,
		    "[%u] _rtld_gnu_hash(\"%s\") = 0x%08llx != 0x%08llx",
		    i, kat[i].in, h, kat[i].out);
	}
}

ATF_TP_ADD_TCS(tp)
{

	ATF_TP_ADD_TC(tp, gnu);
	ATF_TP_ADD_TC(tp, sysv);
	ATF_TP_ADD_TC(tp, sysv_broken);

	return atf_no_error();
}