libexec/ld.elf_so/t_hash.c

/*        $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();
}