Home | History | Annotate | Line # | Download | only in util 
      1 /*	$NetBSD: hash_fnv.c,v 1.5 2026/05/09 18:49:22 christos Exp $	*/
      2 
      3 /*++
      4 /* NAME
      5 /*	hash_fnv 3
      6 /* SUMMARY
      7 /*	Fowler/Noll/Vo hash function
      8 /* SYNOPSIS
      9 /*	#include <hash_fnv.h>
     10 /*
     11 /*	HASH_FNV_T hash_fnv(
     12 /*	const void *src,
     13 /*	size_t	len)
     14 /*
     15 /*	HASH_FNV_T hash_fnvz(
     16 /*	const char *src)
     17 /* DESCRIPTION
     18 /*	hash_fnv() implements a modified FNV type 1a hash function.
     19 /*
     20 /*	hash_fnvz() provides the same functionality for null-terminated
     21 /*	strings, avoiding an unnecessary strlen() call.
     22 /*
     23 /*	To thwart collision attacks, the hash function is seeded
     24 /*	once with ldseed(). To disable seeding (typically, to make
     25 /*	tests predictable), specify the NORANDOMIZE environment
     26 /*	variable; the value does not matter.
     27 /*
     28 /*	This implementation works around a "sticky state" problem
     29 /*	with FNV hash functions: when an input produces a zero hash
     30 /*	state, and the next input byte is zero, then the hash state
     31 /*	would not change. To avoid this, hash_fnv() adds 1 to each
     32 /*	input value. Compile with -DSTRICT_FNV1A to get the standard
     33 /*	behavior.
     34 /*
     35 /*	The default HASH_FNV_T result type is uint64_t. When compiled
     36 /*	with -DUSE_FNV_32BIT, the result type is uint32_t. On ancient
     37 /*	systems without <stdint.h>, define HASH_FNV_T on the compiler
     38 /*	command line as an unsigned 32-bit or 64-bit integer type,
     39 /*	and specify -DUSE_FNV_32BIT when HASH_FNV_T is a 32-bit type.
     40 /* SEE ALSO
     41 /*	http://www.isthe.com/chongo/tech/comp/fnv/index.html
     42 /*	https://softwareengineering.stackexchange.com/questions/49550/
     43 /* LICENSE
     44 /* .ad
     45 /* .fi
     46 /*	The Secure Mailer license must be distributed with this software.
     47 /* AUTHOR(S)
     48 /*	Wietse Venema
     49 /*	Google, Inc.
     50 /*	111 8th Avenue
     51 /*	New York, NY 10011, USA
     52 /*--*/
     53 
     54  /*
     55   * System library
     56   */
     57 #include <sys_defs.h>
     58 #include <stdlib.h>
     59 #include <unistd.h>
     60 
     61  /*
     62   * Utility library.
     63   */
     64 #include <msg.h>
     65 #include <ldseed.h>
     66 #include <hash_fnv.h>
     67 
     68  /*
     69   * Application-specific.
     70   */
     71 #ifdef USE_FNV_32BIT
     72 #define FNV_prime 		0x01000193UL
     73 #define FNV_offset_basis	0x811c9dc5UL
     74 #else
     75 #define FNV_prime		0x00000100000001B3ULL
     76 #define FNV_offset_basis	0xcbf29ce484222325ULL
     77 #endif
     78 
     79  /*
     80   * Workaround for the sticky all-zero hash state: when the next input byte
     81   * is zero, then the operations "hash ^= 0" and "hash *= FNV_prime" would
     82   * not change the hash state. To avoid that, add 1 to the every input value.
     83   */
     84 #ifdef STRICT_FNV1A
     85 #define HASH_FNV_NEW_BITS(new_bits) (new_bits)
     86 #else
     87 #define HASH_FNV_NEW_BITS(new_bits) (1 + (new_bits))
     88 #endif
     89 
     90 static HASH_FNV_T hash_fnv_basis = FNV_offset_basis;
     91 static int hash_fnv_must_init = 1;
     92 
     93 /* hash_fnv_init - seed the hash */
     94 
     95 static void hash_fnv_init(void)
     96 {
     97     HASH_FNV_T seed;
     98 
     99     if (!getenv("NORANDOMIZE")) {
    100 	ldseed(&seed, sizeof(seed));
    101 	hash_fnv_basis ^= seed;
    102     }
    103     hash_fnv_must_init = 0;
    104 }
    105 
    106 /* hash_fnv - modified FNV 1a hash */
    107 
    108 HASH_FNV_T hash_fnv(const void *src, size_t len)
    109 {
    110     HASH_FNV_T hash;
    111     HASH_FNV_T new_bits;
    112 
    113     if (hash_fnv_must_init)
    114 	hash_fnv_init();
    115 
    116     hash = hash_fnv_basis;
    117     while (len-- > 0) {
    118 	new_bits = *(unsigned char *) src++;
    119 	hash ^= HASH_FNV_NEW_BITS(new_bits);
    120 	hash *= FNV_prime;
    121     }
    122     return (hash);
    123 }
    124 
    125 /* hash_fnvz - modified FNV 1a hash for null-terminated strings */
    126 
    127 HASH_FNV_T hash_fnvz(const char *src)
    128 {
    129     HASH_FNV_T hash;
    130     HASH_FNV_T new_bits;
    131 
    132     if (hash_fnv_must_init)
    133 	hash_fnv_init();
    134 
    135     hash = hash_fnv_basis;
    136     while ((new_bits = *(unsigned char *) src++) != 0) {
    137 	hash ^= HASH_FNV_NEW_BITS(new_bits);
    138 	hash *= FNV_prime;
    139     }
    140     return (hash);
    141 }
    142