Home | History | Annotate | Line # | Download | only in ld.elf_so
t_hash.c revision 1.1.6.2 
      1 /*	$NetBSD: t_hash.c,v 1.1.6.2 2023/08/11 12:13:10 sborrill Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2023 The NetBSD Foundation, Inc.
      5  * All rights reserved.
      6  *
      7  * Redistribution and use in source and binary forms, with or without
      8  * modification, are permitted provided that the following conditions
      9  * are met:
     10  * 1. Redistributions of source code must retain the above copyright
     11  *    notice, this list of conditions and the following disclaimer.
     12  * 2. Redistributions in binary form must reproduce the above copyright
     13  *    notice, this list of conditions and the following disclaimer in the
     14  *    documentation and/or other materials provided with the distribution.
     15  *
     16  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     18  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     19  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     20  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     26  * POSSIBILITY OF SUCH DAMAGE.
     27  */
     28 
     29 #include <sys/cdefs.h>
     30 
     31 #include <atf-c.h>
     32 #include <stdint.h>
     33 
     34 #include "hash.h"
     35 
     36 /* known-answer tests */
     37 struct kat {
     38 	const char *in;
     39 	unsigned long long out;
     40 };
     41 
     42 /*
     43  * From the SysV spec, with uint64_t instead of unsigned long to
     44  * illustrate the problem on all systems, not just LP64 ones.
     45  *
     46  * https://www.sco.com/developers/devspecs/gabi41.pdf#page=95
     47  */
     48 static uint64_t
     49 sysv_broken_hash(const char *name)
     50 {
     51 	uint64_t h = 0, g;
     52 
     53 	while (*name) {
     54 		h = (h << 4) + *name++;
     55 		if ((g = h & 0xf0000000) != 0)
     56 			h ^= g >> 24;
     57 		h &= ~g;
     58 	}
     59 
     60 	return h;
     61 }
     62 
     63 ATF_TC(sysv);
     64 ATF_TC_HEAD(sysv, tc)
     65 {
     66 	atf_tc_set_md_var(tc, "descr", "SysV hash (32-bit)");
     67 }
     68 ATF_TC_BODY(sysv, tc)
     69 {
     70 	static const struct kat kat[] = {
     71 		{ "", 0x00000000 },
     72 		{ "a", 0x00000061 },
     73 		{ "aa", 0x00000671 },
     74 		{ "aaa", 0x00006771 },
     75 		{ "aaaa", 0x00067771 },
     76 		{ "aaaaa", 0x00677771 },
     77 		{ "aaaaaa", 0x06777771 },
     78 		{ "aaaaaaa", 0x07777711 },
     79 		{ "aaaaaaaa", 0x07777101 },
     80 		{ "aaaaaaaaa", 0x07771001 },
     81 		{ "ab", 0x00000672 },
     82 		{ "abc", 0x00006783 },
     83 		{ "abcd", 0x00067894 },
     84 		{ "abcde", 0x006789a5 },
     85 		{ "abcdef", 0x06789ab6 },
     86 		{ "abcdefg", 0x0789aba7 },
     87 		{ "abcdefgh", 0x089abaa8 },
     88 		{ "abcdefghi", 0x09abaa69 },
     89 		/* https://maskray.me/blog/2023-04-12-elf-hash-function */
     90 		{ "Z", 0x0000005a },
     91 		{ "ZZ", 0x000005fa },
     92 		{ "ZZZ", 0x00005ffa },
     93 		{ "ZZZZ", 0x0005fffa },
     94 		{ "ZZZZZ", 0x005ffffa },
     95 		{ "ZZZZZW", 0x05fffff7 },
     96 		{ "ZZZZZW9", 0x0ffffff9 },
     97 		{ "ZZZZZW9p", 0x00000000 },
     98 		{ "pneumonoultramicroscopicsilicovolcanoconiosis",
     99 		  0x051706b3 },
    100 	};
    101 	unsigned i;
    102 
    103 	for (i = 0; i < __arraycount(kat); i++) {
    104 		unsigned long long h = _rtld_elf_hash(kat[i].in);
    105 
    106 		ATF_CHECK_EQ_MSG(h, kat[i].out,
    107 		    "[%u] _rtld_elf_hash(\"%s\") = 0x%08llx != 0x%08llx",
    108 		    i, kat[i].in, h, kat[i].out);
    109 	}
    110 }
    111 
    112 ATF_TC(sysv_broken);
    113 ATF_TC_HEAD(sysv_broken, tc)
    114 {
    115 	atf_tc_set_md_var(tc, "descr",
    116 	    "SysV hash (broken with 64-bit unsigned long)");
    117 }
    118 ATF_TC_BODY(sysv_broken, tc)
    119 {
    120 	static const struct kat kat[] = {
    121 		{ "", 0x00000000 },
    122 		{ "a", 0x00000061 },
    123 		{ "aa", 0x00000671 },
    124 		{ "aaa", 0x00006771 },
    125 		{ "aaaa", 0x00067771 },
    126 		{ "aaaaa", 0x00677771 },
    127 		{ "aaaaaa", 0x06777771 },
    128 		{ "aaaaaaa", 0x07777711 },
    129 		{ "aaaaaaaa", 0x07777101 },
    130 		{ "aaaaaaaaa", 0x07771001 },
    131 		{ "ab", 0x00000672 },
    132 		{ "abc", 0x00006783 },
    133 		{ "abcd", 0x00067894 },
    134 		{ "abcde", 0x006789a5 },
    135 		{ "abcdef", 0x06789ab6 },
    136 		{ "abcdefg", 0x0789aba7 },
    137 		{ "abcdefgh", 0x089abaa8 },
    138 		{ "abcdefghi", 0x09abaa69 },
    139 		/* https://maskray.me/blog/2023-04-12-elf-hash-function */
    140 		{ "Z", 0x0000005a },
    141 		{ "ZZ", 0x000005fa },
    142 		{ "ZZZ", 0x00005ffa },
    143 		{ "ZZZZ", 0x0005fffa },
    144 		{ "ZZZZZ", 0x005ffffa },
    145 		{ "ZZZZZW", 0x05fffff7 },
    146 		{ "ZZZZZW9", 0x0ffffff9 },
    147 		{ "ZZZZZW9p", 0x100000000 }, /* XXX */
    148 		{ "pneumonoultramicroscopicsilicovolcanoconiosis",
    149 		  0x051706b3 },
    150 	};
    151 	unsigned i;
    152 
    153 	for (i = 0; i < __arraycount(kat); i++) {
    154 		unsigned long long h = sysv_broken_hash(kat[i].in);
    155 
    156 		ATF_CHECK_EQ_MSG(h, kat[i].out,
    157 		    "[%u] sysv_broken_hash(\"%s\") = 0x%08llx != 0x%08llx",
    158 		    i, kat[i].in, h, kat[i].out);
    159 	}
    160 }
    161 
    162 ATF_TP_ADD_TCS(tp)
    163 {
    164 
    165 	ATF_TP_ADD_TC(tp, sysv);
    166 	ATF_TP_ADD_TC(tp, sysv_broken);
    167 
    168 	return atf_no_error();
    169 }
    170