FNV-1a

This repository contains some Fowler-Noll-Vo hash functions. It implements 32-, 64-, 128-, 256-, 512-, and 1024-bit variants.

128-bit variants and higher come in three implementations:

1. implementation based on _BitInt numbers if the compiler supports them (FNV1A_BITINT must be #defined).
2. implementation based on __int128_t numbers to simulate 128- to 1024-bit multiplications if the compiler supports them (FNV1A_BIT128 must be #defined).
3. implementation using a custom integer type to simulate 128- to 1024-bit multiplications for older compilers.

Usage

Just add sources to your projects.

They provide a set of functions for each hash size (XXX being 32, 64, 128, 256, 512 or 1024):

/* Hash type */

typedef ... t_fnv1a_XXX;

/* Hexadecimal digest type */

typedef char t_fnv1a_XXX_digest[sizeof(t_fnv1a_XXX)*2 + 1];

/* Hash initialisation
 * Initializes `hash` with the hash initial value.
 */

void fnv1a_XXX_init(t_fnv1a_XXX *hash);

/* Hash update
 * Update `hash` with `size` bytes stored at `data`.
 */

void fnv1a_XXX_update(t_fnv1a_XXX *hash, const void *data, size_t size);

/* Hexadecimal digest
 * Stores the hexadecimal digest of `hash` to `digest`.
 */

void fnv1a_XXX_digest(const t_fnv1a_XXX *hash, t_fnv1a_XXX_digest digest);

/* Hash comparison
 * Compares `hash1` and `hash2` with `memcmp` and returns `0`, `1` or `-1`.
 */

int fnv1a_XXX_cmp(const t_fnv1a_XXX *hash1, const t_fnv1a_XXX *hash2);

The test file contains some examples.

Tests

To build and run the tests you need to install Ninja and Bang.

Then run bang to generate the Ninja build file and ninja to compile and execute the tests.

fnv1a is tested with gcc, clang and zig cc.

Performances

The current implementation is pretty fast. My custom implementation of big numbers is a bit faster than _BitInt:

Processor        : Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
Operating System : Fedora Linux version 42

gcc-fnv1a                   gcc-fnv1a-128               gcc-fnv1a-bitint
------------------------    ------------------------    ------------------------
fnv1a_32   : 1073.0 MB/s    fnv1a_32   : 1073.0 MB/s    fnv1a_32   : 1073.0 MB/s
fnv1a_64   : 1075.3 MB/s    fnv1a_64   : 1079.9 MB/s    fnv1a_64   : 1073.0 MB/s
fnv1a_128  :  566.3 MB/s    fnv1a_128  :  692.0 MB/s    fnv1a_128  :  693.0 MB/s
fnv1a_256  :  356.0 MB/s    fnv1a_256  :  435.4 MB/s    fnv1a_256  :   42.9 MB/s
fnv1a_512  :  139.9 MB/s    fnv1a_512  :  207.8 MB/s    fnv1a_512  :   21.1 MB/s
fnv1a_1024 :   62.5 MB/s    fnv1a_1024 :   90.2 MB/s    fnv1a_1024 :    8.6 MB/s

clang-fnv1a                 clang-fnv1a-128             clang-fnv1a-bitint
------------------------    ------------------------    ------------------------
fnv1a_32   : 1073.0 MB/s    fnv1a_32   : 1073.0 MB/s    fnv1a_32   : 1096.5 MB/s
fnv1a_64   : 1073.0 MB/s    fnv1a_64   : 1073.0 MB/s    fnv1a_64   : 1073.0 MB/s
fnv1a_128  :  694.9 MB/s    fnv1a_128  :  983.3 MB/s    fnv1a_128  : 1005.0 MB/s
fnv1a_256  :  352.6 MB/s    fnv1a_256  :  521.6 MB/s    fnv1a_256  :  513.3 MB/s
fnv1a_512  :  132.7 MB/s    fnv1a_512  :  233.2 MB/s    fnv1a_512  :  212.9 MB/s
fnv1a_1024 :   72.8 MB/s    fnv1a_1024 :   97.6 MB/s    fnv1a_1024 :   83.2 MB/s

zigcc-fnv1a                 zigcc-fnv1a-128             zigcc-fnv1a-bitint
------------------------    ------------------------    ------------------------
fnv1a_32   : 1073.0 MB/s    fnv1a_32   : 1073.0 MB/s    fnv1a_32   : 1073.0 MB/s
fnv1a_64   : 1073.0 MB/s    fnv1a_64   : 1073.0 MB/s    fnv1a_64   : 1073.0 MB/s
fnv1a_128  :  693.0 MB/s    fnv1a_128  :  968.1 MB/s    fnv1a_128  : 1009.1 MB/s
fnv1a_256  :  334.8 MB/s    fnv1a_256  :  590.3 MB/s    fnv1a_256  :  591.0 MB/s
fnv1a_512  :  138.0 MB/s    fnv1a_512  :  273.7 MB/s    fnv1a_512  :  258.7 MB/s
fnv1a_1024 :   72.7 MB/s    fnv1a_1024 :  120.8 MB/s    fnv1a_1024 :   98.0 MB/s

Note that gcc implementation of _BitInt seems very inefficient with hashes greater than 128 bits (10 times slower than other implementations).

License

This file is part of fnv1a.

fnv1a is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

fnv1a is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with fnv1a.  If not, see <https://www.gnu.org/licenses/>.

For further information about fnv1a you can visit
https://codeberg.org/cdsoft/fnv1a