xref: /freebsd/contrib/elftoolchain/libelftc/libelftc_hash.c (revision 98e0ffaefb0f241cda3a72395d3be04192ae0d47)
1*a85fe12eSEd Maste /*-
2*a85fe12eSEd Maste  * Copyright (c) 2013, Joseph Koshy
3*a85fe12eSEd Maste  * All rights reserved.
4*a85fe12eSEd Maste  *
5*a85fe12eSEd Maste  * Redistribution and use in source and binary forms, with or without
6*a85fe12eSEd Maste  * modification, are permitted provided that the following conditions
7*a85fe12eSEd Maste  * are met:
8*a85fe12eSEd Maste  * 1. Redistributions of source code must retain the above copyright
9*a85fe12eSEd Maste  *    notice, this list of conditions and the following disclaimer
10*a85fe12eSEd Maste  *    in this position and unchanged.
11*a85fe12eSEd Maste  * 2. Redistributions in binary form must reproduce the above copyright
12*a85fe12eSEd Maste  *    notice, this list of conditions and the following disclaimer in the
13*a85fe12eSEd Maste  *    documentation and/or other materials provided with the distribution.
14*a85fe12eSEd Maste  *
15*a85fe12eSEd Maste  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
16*a85fe12eSEd Maste  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17*a85fe12eSEd Maste  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18*a85fe12eSEd Maste  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
19*a85fe12eSEd Maste  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20*a85fe12eSEd Maste  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21*a85fe12eSEd Maste  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22*a85fe12eSEd Maste  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23*a85fe12eSEd Maste  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24*a85fe12eSEd Maste  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25*a85fe12eSEd Maste  */
26*a85fe12eSEd Maste 
27*a85fe12eSEd Maste /*
28*a85fe12eSEd Maste  * An implementation of the Fowler-Noll-Vo hash function.
29*a85fe12eSEd Maste  *
30*a85fe12eSEd Maste  * References:
31*a85fe12eSEd Maste  * - http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
32*a85fe12eSEd Maste  * - http://www.isthe.com/chongo/tech/comp/fnv/
33*a85fe12eSEd Maste  */
34*a85fe12eSEd Maste 
35*a85fe12eSEd Maste #include <sys/types.h>
36*a85fe12eSEd Maste 
37*a85fe12eSEd Maste #include <limits.h>
38*a85fe12eSEd Maste 
39*a85fe12eSEd Maste #include "_libelftc.h"
40*a85fe12eSEd Maste 
41*a85fe12eSEd Maste ELFTC_VCSID("$Id: libelftc_hash.c 2870 2013-01-07 10:38:43Z jkoshy $");
42*a85fe12eSEd Maste 
43*a85fe12eSEd Maste /*
44*a85fe12eSEd Maste  * Use the size of an 'int' to determine the magic numbers used by the
45*a85fe12eSEd Maste  * hash function.
46*a85fe12eSEd Maste  */
47*a85fe12eSEd Maste 
48*a85fe12eSEd Maste #if	INT_MAX == 2147483647UL
49*a85fe12eSEd Maste #define	FNV_PRIME		16777619UL
50*a85fe12eSEd Maste #define FNV_OFFSET		2166136261UL
51*a85fe12eSEd Maste #elif	INT_MAX == 18446744073709551615ULL
52*a85fe12eSEd Maste #define	FNV_PRIME		1099511628211ULL
53*a85fe12eSEd Maste #define	FNV_OFFSET		14695981039346656037ULL
54*a85fe12eSEd Maste #else
55*a85fe12eSEd Maste #error	sizeof(int) is unknown.
56*a85fe12eSEd Maste #endif
57*a85fe12eSEd Maste 
58*a85fe12eSEd Maste unsigned int
libelftc_hash_string(const char * s)59*a85fe12eSEd Maste libelftc_hash_string(const char *s)
60*a85fe12eSEd Maste {
61*a85fe12eSEd Maste 	char c;
62*a85fe12eSEd Maste 	unsigned int hash;
63*a85fe12eSEd Maste 
64*a85fe12eSEd Maste 	for (hash = FNV_OFFSET; (c = *s) != '\0'; s++) {
65*a85fe12eSEd Maste 		hash ^= c;
66*a85fe12eSEd Maste 		hash *= FNV_PRIME;
67*a85fe12eSEd Maste 	}
68*a85fe12eSEd Maste 
69*a85fe12eSEd Maste 	return (hash);
70*a85fe12eSEd Maste }
71