< draft-eastlake-fnv-10.txt   draft-eastlake-fnv-11.txt >
Network Working Group Glenn Fowler Network Working Group Glenn Fowler
INTERNET-DRAFT Google INTERNET-DRAFT Google
Intended Status: Informational Landon Curt Noll Intended Status: Informational Landon Curt Noll
Cisco Systems Cisco Systems
Kiem-Phong Vo Kiem-Phong Vo
Google Google
Donald Eastlake Donald Eastlake
Huawei Technologies Huawei Technologies
Expires: April 5, 2016 October 6, 2015 Tony Hansen
AT&T Laboratories
Expires: December 15, 2016 June 16, 2016
The FNV Non-Cryptographic Hash Algorithm The FNV Non-Cryptographic Hash Algorithm
<draft-eastlake-fnv-10.txt> <draft-eastlake-fnv-11.txt>
Abstract Abstract
FNV (Fowler/Noll/Vo) is a fast, non-cryptographic hash algorithm with FNV (Fowler/Noll/Vo) is a fast, non-cryptographic hash algorithm with
good dispersion. The purpose of this document is to make information good dispersion. The purpose of this document is to make information
on FNV and open source code performing FNV conveniently available to on FNV and open source code performing FNV conveniently available to
the Internet community. the Internet community.
Status of This Memo Status of This Memo
skipping to change at page 2, line 14 skipping to change at page 2, line 14
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Table of Contents Table of Contents
1. Introduction............................................3 1. Introduction............................................3
2. FNV Basics..............................................4 2. FNV Basics..............................................4
2.1 FNV Primes.............................................4 2.1 FNV Primes.............................................4
2.2 FNV offset_basis.......................................5 2.2 FNV offset_basis.......................................5
2.3 FNV Endianism..........................................5 2.3 FNV Endianism..........................................6
3. Other Hash Sizes and XOR Folding........................7 3. Other Hash Sizes and XOR Folding........................7
4. Hashing Multiple Values Together........................8 4. Hashing Multiple Values Together........................8
5. FNV Constants...........................................9 5. FNV Constants...........................................9
6. The Source Code........................................11 6. The Source Code........................................11
6.1 FNV-1a C Code.........................................11 6.1 FNV-1a C Code.........................................11
6.1.1 FNV32 Code..........................................13 6.1.1 FNV32 Code..........................................15
6.1.2 FNV64 C Code........................................19 6.1.2 FNV64 C Code........................................21
6.1.3 FNV128 C Code.......................................30 6.1.3 FNV128 C Code.......................................32
6.1.4 FNV256 C Code.......................................42 6.1.4 FNV256 C Code.......................................44
6.1.5 FNV512 C Code.......................................54 6.1.5 FNV512 C Code.......................................55
6.1.6 FNV1024 C Code......................................65 6.1.6 FNV1024 C Code......................................67
6.2 FNV Test Code.........................................68 6.2 FNV Test Code.........................................79
7. Security Considerations................................79
7.1 Why is FNV Non-Cryptographic?.........................79
8. IANA Considerations....................................80 7. Security Considerations................................93
7.1 Why is FNV Non-Cryptographic?.........................93
7.2 Inducing Collisions...................................94
Normative References......................................80 8. IANA Considerations....................................95
Informative References....................................80
Acknowledgements..........................................81
Appendix A: Work Comparison with SHA-1....................82 Normative References......................................95
Appendix B: Previous IETF Reference to FNV................83 Informative References....................................95
Acknowledgements..........................................96
Appendix Z: Change Summary................................84 Appendix A: Work Comparison with SHA-1....................97
From -00 to -01...........................................84 Appendix B: Previous IETF Reference to FNV................98
From -01 to -02...........................................84 Appendix C: A Few Test Vectors............................99
From -02 to -03...........................................84 Appendix Z: Change Summary...............................100
From -03 to -04...........................................84 From -00 to -01..........................................100
From -04 to -05...........................................85 From -01 to -02..........................................100
From -05 to -06...........................................85 From -02 to -03..........................................100
From -06 to -07 to -08....................................85 From -03 to -04..........................................100
From -08 to -09...........................................85 From -04 to -05..........................................101
From -09 to -10...........................................85 From -05 to -06..........................................101
From -06 to -07 to -08...................................101
From -08 to -09..........................................101
From -09 to -10..........................................101
From -10 to -11..........................................102
Author's Address..........................................86 Author's Address.........................................103
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
1. Introduction 1. Introduction
The FNV hash algorithm is based on an idea sent as reviewer comments The FNV hash algorithm is based on an idea sent as reviewer comments
to the [IEEE] POSIX P1003.2 committee by Glenn Fowler and Phong Vo in to the [IEEE] POSIX P1003.2 committee by Glenn Fowler and Phong Vo in
1991. In a subsequent ballot round Landon Curt Noll suggested an 1991. In a subsequent ballot round Landon Curt Noll suggested an
improvement on their algorithm. Some people tried this hash and found improvement on their algorithm. Some people tried this hash and found
that it worked rather well. In an EMail message to Landon, they named that it worked rather well. In an EMail message to Landon, they named
skipping to change at page 4, line 34 skipping to change at page 4, line 34
and multiply operations are reversed. Operational experience and multiply operations are reversed. Operational experience
indicates better hash dispersion for small amounts of data with indicates better hash dispersion for small amounts of data with
FNV-1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero. FNV-1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero.
FNV-1a is suggested for general use. FNV-1a is suggested for general use.
2.1 FNV Primes 2.1 FNV Primes
The theory behind FNV_Prime's is beyond the scope of this document The theory behind FNV_Prime's is beyond the scope of this document
but the basic property to look for is how an FNV_Prime would impact but the basic property to look for is how an FNV_Prime would impact
dispersion. Now, consider any n-bit FNV hash where n is >= 32 and dispersion. Now, consider any n-bit FNV hash where n is >= 32 and
also a power of 2. For each such n-bit FNV hash, an FNV_Prime p is also a power of 2, in particular n = 2**s. For each such n-bit FNV
defined as: hash, an FNV_Prime p is defined as:
When s is an integer and 4 < s < 11, then FNV_Prime is the When s is an integer and 4 < s < 11, then FNV_Prime is the
smallest prime p of the form: smallest prime p of the form:
256**int((5 + 2^s)/12) + 2**8 + b 256**int((5 + 2**s)/12) + 2**8 + b
where b is an integer such that: where b is an integer such that:
0 < b < 2**8 0 < b < 2**8
The number of one-bits in b is 4 or 5 The number of one-bits in b is 4 or 5
and where p mod (2**40 - 2**24 - 1) > (2**24 + 2**8 + 2**7). and where ( p mod (2**40 - 2**24 - 1) ) > (2**24 + 2**8 + 2**7).
Experimentally, FNV_Primes matching the above constraints tend to Experimentally, FNV_Primes matching the above constraints tend to
have better dispersion properties. They improve the polynomial have better dispersion properties. They improve the polynomial
feedback characteristic when an FNV_Prime multiplies an intermediate feedback characteristic when an FNV_Prime multiplies an intermediate
hash value. As such, the hash values produced are more scattered hash value. As such, the hash values produced are more scattered
throughout the n-bit hash space. throughout the n-bit hash space.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
The case where s < 5 is not considered because the resulting hash The case where s < 5 is not considered because the resulting hash
skipping to change at page 5, line 44 skipping to change at page 5, line 44
"chongo <Landon Curt Noll> /\\../\\" "chongo <Landon Curt Noll> /\\../\\"
That string was used because the person testing FNV with non-zero That string was used because the person testing FNV with non-zero
offset_basis values was looking at an email message from Landon and offset_basis values was looking at an email message from Landon and
was copying his standard email signature line; however, they couldn't was copying his standard email signature line; however, they couldn't
see very well and copied it incorrectly. In fact, he uses see very well and copied it incorrectly. In fact, he uses
chongo (Landon Curt Noll) /\oo/\ chongo (Landon Curt Noll) /\oo/\
but, since it doesn't matter, no effort has been made to correct but, since it doesn't matter, no effort has been made to correct
this. In the general case, almost any offset_basis will serve so this.
long as it is non-zero.
In the general case, almost any offset_basis will serve so long as it
is non-zero. The choice of a non-standard offset_basis may be
beneficial in defending against some attacks that try to induce hash
collisions.
INTERNET-DRAFT FNV
2.3 FNV Endianism 2.3 FNV Endianism
For persistent storage or interoperability between different hardware For persistent storage or interoperability between different hardware
platforms, an FNV hash shall be represented in the little endian platforms, an FNV hash shall be represented in the little endian
format. That is, the FNV hash will be stored in an array hash[N] with format. That is, the FNV hash will be stored in an array hash[N] with
INTERNET-DRAFT FNV
N bytes such that its integer value can be retrieved as follows: N bytes such that its integer value can be retrieved as follows:
unsigned char hash[N]; unsigned char hash[N];
for ( i = N-1, value = 0; i >= 0; --i ) for ( i = N-1, value = 0; i >= 0; --i )
value = value << 8 + hash[i]; value = value << 8 + hash[i];
Of course, when FNV hashes are used in a single process or a group of Of course, when FNV hashes are used in a single process or a group of
processes sharing memory on processors with compatible endian-ness, processes sharing memory on processors with compatible endian-ness,
the natural endianness of those processors can be used regardless of the natural endian-ness of those processors can be used regardless of
its type, little, big, or some other exotic form. its type, little, big, or some other exotic form.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
3. Other Hash Sizes and XOR Folding 3. Other Hash Sizes and XOR Folding
Many hash uses require a hash that is not one of the FNV sizes for Many hash uses require a hash that is not one of the FNV sizes for
which constants are provided in Section 5. If a larger hash size is which constants are provided in Section 5. If a larger hash size is
needed, please contact the authors of this document. needed, please contact the authors of this document.
Most hash applications make use of a hash that is a fixed size binary Most hash applications make use of a hash that is a fixed size binary
field. Assume that k bits of hash are desired and k is less than 1024 field. Assume that k bits of hash are desired and k is less than 1024
but not one of the sizes for which constants are provided in Section but not one of the sizes for which constants are provided in Section
5. The recommended technique is to take the smallest FNV hash of size 5. The recommended technique is to take the smallest FNV hash of size
S, where S is larger than k, and calculate the desired hash using xor S, where S is larger than k, and calculate the desired k-bit-hash
folding as shown below. The final bit masking operation is logically using xor folding as shown below. The final bit masking operation is
unnecessarily if the size of hash is exactly the number of desired logically unnecessary if the size of the variable k-bit-hash is
bits. exactly k bits.
temp = FNV_S ( data-to-be-hashed ) temp = FNV_S ( data-to-be-hashed )
hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 ) k-bit-hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 )
Hash functions are a trade-off between speed and strength. For Hash functions are a trade-off between speed and strength. For
example, a somewhat stronger hash may be obtained for exact FNV sizes example, a somewhat stronger hash may be obtained for exact FNV sizes
by calculating an FNV twice as long as the desired output ( S = 2*k ) by calculating an FNV twice as long as the desired output ( S = 2*k )
and performing such data folding using a k equal to the size of the and performing such data folding using a k equal to the size of the
desired output. However, if a much stronger hash, for example one desired output. However, if a much stronger hash, for example one
suitable for cryptographic applications, is wanted, algorithms suitable for cryptographic applications, is wanted, algorithms
designed for that purpose, such as those in [RFC6234], should be designed for that purpose, such as those in [RFC6234], should be
used. used.
If it is desired to obtain a hash result that is a value between 0 If it is desired to obtain a hash result that is a value between 0
and max, where max is a not a power of two, simply choose an FNV hash and max, where max+1 is a not a power of two, simply choose an FNV
size S such that 2**S > max. Then calculate the following: hash size S such that 2**S > max. Then calculate the following:
FNV_S mod ( max+1 ) FNV_S mod ( max+1 )
The resulting remainder will be in the range desired but will suffer The resulting remainder will be in the range desired but will suffer
from a bias against large values with the bias being larger if 2**S from a bias against large values with the bias being larger if 2**S
is only a little bigger than max. If this bias is acceptable, no is only a little bigger than max. If this bias is acceptable, no
further processing is needed. If this bias is unacceptable, it can be further processing is needed. If this bias is unacceptable, it can be
avoided by retrying for certain high values of hash, as follows, avoided by retrying for certain high values of hash, as follows,
before applying the mod operation above: before applying the mod operation above:
skipping to change at page 8, line 34 skipping to change at page 8, line 34
calculated and then fnvxy = FNVoffset_basis ( fnvx, Y ), and finally calculated and then fnvxy = FNVoffset_basis ( fnvx, Y ), and finally
fnvxyz = FNVoffset_basis ( fnvxy, Z). The resulting fnvxyz would be fnvxyz = FNVoffset_basis ( fnvxy, Z). The resulting fnvxyz would be
the same as FNV ( X | Y | Z ); the same as FNV ( X | Y | Z );
Cases are also common where such a hash needs to be repeatedly Cases are also common where such a hash needs to be repeatedly
calculated where the component values vary but some vary more calculated where the component values vary but some vary more
frequently than others. For example, assume some sort of computer frequently than others. For example, assume some sort of computer
network traffic flow ID, such as the IPv6 flow ID [RFC6437], is to be network traffic flow ID, such as the IPv6 flow ID [RFC6437], is to be
calculated for network packets based on the source and destination calculated for network packets based on the source and destination
IPv6 address and the Traffic Class [RFC2460]. If the Flow ID is IPv6 address and the Traffic Class [RFC2460]. If the Flow ID is
calculate in the originating host, the source IPv6 address would calculated in the originating host, the source IPv6 address would
likely always be the same or perhaps assume one of a very small likely always be the same or perhaps assume one of a very small
number of values. By placing this quasi-constant IPv6 source address number of values. By placing this quasi-constant IPv6 source address
first in the string being FNV hashed, FNV ( IPv6source ) could be first in the string being FNV hashed, FNV ( IPv6source ) could be
calculated and used as the offset_basis for calculating FNV of the calculated and used as the offset_basis for calculating FNV of the
IPv6 destination address and Traffic Class for each packet. As a IPv6 destination address and Traffic Class for each packet. As a
result, the per packet hash would be over 17 bytes rather than over result, the per packet hash would be over 17 bytes rather than over
33 bytes saving computational resources. The code in this document 33 bytes saving computational resources. The code in this document
includes functions facilitating the use of a non-standard includes functions facilitating the use of a non-standard
offset_basis. offset_basis.
skipping to change at page 11, line 31 skipping to change at page 11, line 31
This section provides the direct FNV-1a function for each of the This section provides the direct FNV-1a function for each of the
lengths for which it is specified in this document. The following lengths for which it is specified in this document. The following
functions are provided, where XXX is "32", "64", "128", "256", "512", functions are provided, where XXX is "32", "64", "128", "256", "512",
or "1024": or "1024":
FNVXXXstring, FNVXXXblock: These are simple functions for directly FNVXXXstring, FNVXXXblock: These are simple functions for directly
returning the FNV hash of a zero terminated byte string not returning the FNV hash of a zero terminated byte string not
including the zero and the FNV hash of a counted block of including the zero and the FNV hash of a counted block of
bytes. Note that for applications of FNV-32 where 32-bit bytes. Note that for applications of FNV-32 where 32-bit
integers are supported and FNV-64 where 64-bit integers are integers are supported and FNV-64 where 64-bit integers are
supported, the code is sufficiently simple that use of open supported, the code is sufficiently simple that, to maximize
coding or macros may be more appropriate to maximize performance, use of open coding or macros may be more
performance. appropriate than calling a subroutine.
FNVXXXinit, FNVXXXinitBasis: These function and the next two sets of FNVXXXinit, FNVXXXinitBasis: These functions and the next two sets of
functions below provide facilities for incrementally functions below provide facilities for incrementally
calculating FNV hashes. They all assume a data structure of calculating FNV hashes. They all assume a data structure of
type FNVXXXcontext that holds the current state of the hash. type FNVXXXcontext that holds the current state of the hash.
FNVXXXinit initializes that context to the standard FNVXXXinit initializes that context to the standard
offset_basis. FNVXXXinitBasis takes an offset_basis value as a offset_basis. FNVXXXinitBasis takes an offset_basis value as a
parameter and may be useful for hashing concatenations, as parameter and may be useful for hashing concatenations, as
described in Section 4, as well as for simply using a non- described in Section 4, as well as for simply using a non-
standard offset_basis. standard offset_basis.
FNXXXVblockin, FNVXXXstringin: These functions hash a sequence of FNXXXVblockin, FNVXXXstringin: These functions hash a sequence of
skipping to change at page 12, line 13 skipping to change at page 12, line 13
The following code is a private header file used by all the FNV The following code is a private header file used by all the FNV
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
functions further below and which states the terms for use and functions further below and which states the terms for use and
redistribution of all of this code. redistribution of all of this code.
<CODE BEGINS> <CODE BEGINS>
/************************ fnv-private.h ************************/ /************************ fnv-private.h ************************/
/****************** See RFC NNNN for details *******************/ /****************** See RFC NNNN for details *******************/
/* Copyright (c) 2015 IETF Trust and the persons identified as /* Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* *
* Redistribution and use in source and binary forms, with or without * Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions * modification, are permitted provided that the following conditions
* are met: * are met:
* *
* * Redistributions of source code must retain the above copyright * * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer. * notice, this list of conditions and the following disclaimer.
* *
* * Redistributions in binary form must reproduce the above copyright * * Redistributions in binary form must reproduce the above copyright
skipping to change at page 12, line 52 skipping to change at page 12, line 52
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE. * POSSIBILITY OF SUCH DAMAGE.
*/ */
#ifndef _FNV_PRIVATE_H_ #ifndef _FNV_PRIVATE_H_
#define _FNV_PRIVATE_H_ #define _FNV_PRIVATE_H_
/* /*
* Six FNV-1a hashes are defined with these sizes: * Six FNV-1a hashes are defined with these sizes:
* FNV32 32 bit, 4 byte * FNV32 32 bits, 4 bytes
* FNV64 64 bit, 8 byte * FNV64 64 bits, 8 bytes
* FNV128 128 bit, 16 byte * FNV128 128 bits, 16 bytes
* FNV256 256 bit, 32 byte * FNV256 256 bits, 32 bytes
* FNV512 512 bit, 64 byte * FNV512 512 bits, 64 bytes
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
* FNV1024 1024 bit, 128 bytes * FNV1024 1024 bits, 128 bytes
*/ */
/* Private stuff used by this implementation of the FNV /* Private stuff used by this implementation of the FNV
* (Fowler, Noll, Vo) non-cryptographic hash function FNV-1a. * (Fowler, Noll, Vo) non-cryptographic hash function FNV-1a.
* External callers don't need to know any of this. */ * External callers don't need to know any of this. */
enum { /* State value bases for context->Computed */ enum { /* State value bases for context->Computed */
FNVinited = 22, FNVinited = 22,
FNVcomputed = 76, FNVcomputed = 76,
FNVemptied = 220, FNVemptied = 220,
FNVclobber = 122 /* know bad value for testing */ FNVclobber = 122 /* known bad value for testing */
}; };
/* Deltas to assure distinct state values for different lengths */ /* Deltas to assure distinct state values for different lengths */
enum { enum {
FNV32state = 1, FNV32state = 1,
FNV64state = 3, FNV64state = 3,
FNV128state = 5, FNV128state = 5,
FNV256state = 7, FNV256state = 7,
FNV512state = 11, FNV512state = 11,
FNV1024state = 13 FNV1024state = 13
}; };
#endif #endif
<CODE ENDS> <CODE ENDS>
6.1.1 FNV32 Code The following code is a simple header file to include all the
specific length FNV header files.
The header and C source for 32-bit FNV-1a. <CODE BEGINS>
/****************************** FNV.h *******************************/
/******************* See RFC NNNN for details. **********************/
/*
* Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution.
*/
#ifndef _FNV_H_
#define _FNV_H_
#include "FNV32.h"
#include "FNV64.h"
#include "FNV128.h"
#include "FNV256.h"
#include "FNV512.h"
#include "FNV1024.h"
#endif /* _FNV_H_ */
INTERNET-DRAFT FNV
<CODE ENDS>
The following code is a simple header file to control configuration
related to big integer and big endian support.
<CODE BEGINS> <CODE BEGINS>
/***************************** FNV32.h ******************************/ /*************************** FNVconfig.h ****************************/
/******************** See RFC NNNN for details **********************/ /******************* See RFC NNNN for details. **********************/
/* /*
* Copyright (c) 2015 IETF Trust and the persons identified as * Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
#ifndef _FNV32_H_ #ifndef _FNVconfig_H_
#define _FNV32_H_ #define _FNVconfig_H_
/* /*
* Description: * Description:
* This file provides headers for the 32-bit version of the FNV-1a * This file provides configuration ifdefs for the
* non-cryptographic hash algorithm. * FNV-1a non-cryptographic hash algorithms.
* *
* >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */
INTERNET-DRAFT FNV /* FNV_64bitIntegers - Define this if your system supports 64-bit
* arithmetic including 32-bit x 32-bit multiplication
* producing a 64-bit product. If undefined, it will be
* assumed that 32-bit arithmetic is supported including
* 16-bit x 16-bit multiplication producing a 32-bit result.
*/
// #define FNV_64bitIntegers
* >>>>>>>> IMPORTANT CONFIGURATION ifdef: <<<<<<<<<< /*
* *
* FNV_BigEndian - Define this ONLY if your system uses big * FNV_BigEndian - Define this ONLY if your system uses big
* endian representation AND your FNV hashes need to * endian representation AND your FNV hashes need to
* interoperate with little endian systems. If you #define * interoperate with little endian systems. If you #define
* this symbol when not needed, it will unnecessarily slow * this symbol when not needed, it will unnecessarily slow
* execution and increase the code size of FNV functions. * down and increase the code size of the FNV functions.
*
* It is assumed that your system supports 32-bit arithemetic
* including 6-bit x 16-bit multiplication producing a
* 32-bit result.
*/ */
// #define FNV_BigEndian
/*
* The following allow the FNV test program to override the
* above configuration settings.
*/
#ifdef FNV_TEST_PROGRAM
# ifdef TEST_FNV_64bitIntegers
INTERNET-DRAFT FNV
# ifndef FNV_64bitIntegers
# define FNV_64bitIntegers
# endif
# else
# undef FNV_64bitIntegers
# endif
# ifndef FNV_64bitIntegers /* causes an error if uint64_t is used */
# define uint64_t foobar
# endif
# ifdef TEST_FNV_BigEndian
# ifndef FNV_BigEndian
# define FNV_BigEndian
# endif
# else
# undef FNV_BigEndian
# endif
#endif
#endif /* _FNVconfig_H_ */
<CODE ENDS>
6.1.1 FNV32 Code
The header and C source for 32-bit FNV-1a.
<CODE BEGINS>
/***************************** FNV32.h ******************************/
/******************** See RFC NNNN for details **********************/
/*
* Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution.
*/
#ifndef _FNV32_H_
#define _FNV32_H_
#include "FNVconfig.h"
#include <stdint.h> #include <stdint.h>
/* #define FNV32size (32/8) not used */ /* #define FNV32size (32/8) not used */
/* If you do not have the ISO standard stdint.h header file, then you /* If you do not have the ISO standard stdint.h header file, then you
* must typedef the following types: * must typedef the following types:
* *
* type meaning * type meaning
* uint32_t unsigned 32 bit integer * uint32_t unsigned 32 bit integer
* uint8_t unsigned 8 bit integer (i.e., unsigned char) * uint8_t unsigned 8 bit integer (i.e., unsigned char)
INTERNET-DRAFT FNV
*/ */
#ifndef _FNV_ErrCodes_ #ifndef _FNV_ErrCodes_
#define _FNV_ErrCodes_ #define _FNV_ErrCodes_
/******************************************************************** /********************************************************************
* All FNV functions provided return as integer as follows: * All FNV functions provided return as integer as follows:
* 0 -> success * 0 -> success
* >0 -> error as listed below * >0 -> error as listed below
*/ */
enum { /* success and errors */ enum { /* success and errors */
skipping to change at page 15, line 4 skipping to change at page 16, line 35
* This structure holds context information for an FNV32 hash * This structure holds context information for an FNV32 hash
*/ */
typedef struct FNV32context_s { typedef struct FNV32context_s {
int Computed; /* state */ int Computed; /* state */
uint32_t Hash; uint32_t Hash;
} FNV32context; } FNV32context;
/* /*
* Function Prototypes * Function Prototypes
* FNV32string: hash a zero terminated string not including * FNV32string: hash a zero terminated string not including
INTERNET-DRAFT FNV
* the terminating zero * the terminating zero
* FNV32block: hash a specified length byte vector * FNV32block: hash a specified length byte vector
* FNV32init: initializes an FNV32 context * FNV32init: initializes an FNV32 context
* FNV32initBasis: initializes an FNV32 context with a * FNV32initBasis: initializes an FNV32 context with a
* provided basis * provided basis
* FNV32blockin: hash in a specified length byte vector * FNV32blockin: hash in a specified length byte vector
* FNV32stringin: hash in a zero terminated string not * FNV32stringin: hash in a zero terminated string not
* including the zero * including the zero
* FNV32result: returns the hash value * FNV32result: returns the hash value
* *
* Hash is returned as a 32-bit integer * Hash is returned as a 32-bit integer
*/ */
#ifdef __cplusplus
extern "C" {
#endif
/* FNV32 */ /* FNV32 */
extern int FNV32string ( const char *in, extern int FNV32string ( const char *in,
uint32_t * const out ); uint32_t * const out );
extern int FNV32block ( const uint8_t *in, extern int FNV32block ( const void *in,
long int inlength, long int inlength,
INTERNET-DRAFT FNV
uint32_t * const out ); uint32_t * const out );
extern int FNV32init ( FNV32context * const ); extern int FNV32init ( FNV32context * const );
extern int FNV32initBasis ( FNV32context * const, extern int FNV32initBasis ( FNV32context * const,
uint32_t basis ); uint32_t basis );
extern int FNV32blockin ( FNV32context * const, extern int FNV32blockin ( FNV32context * const,
const uint8_t *in, const void *in,
long int inlength ); long int inlength );
extern int FNV32stringin ( FNV32context * const, extern int FNV32stringin ( FNV32context * const,
const char *in ); const char *in );
extern int FNV32result ( FNV32context * const, extern int FNV32result ( FNV32context * const,
uint32_t * const out ); uint32_t * const out );
#ifdef __cplusplus
}
#endif
#endif /* _FNV32_H_ */ #endif /* _FNV32_H_ */
<CODE ENDS> <CODE ENDS>
<CODE BEGINS> <CODE BEGINS>
/**************************** FNV32.c ****************************/ /**************************** FNV32.c ****************************/
/****************** See RFC NNNN for details. ********************/ /****************** See RFC NNNN for details. ********************/
/* Copyright (c) 2015 IETF Trust and the persons identified as /* Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
/* This code implements the FNV (Fowler, Noll, Vo) non-cryptographic /* This code implements the FNV (Fowler, Noll, Vo) non-cryptographic
* hash function FNV-1a for 32-bit hashes. * hash function FNV-1a for 32-bit hashes.
*/ */
#ifndef _FNV32_C_ #ifndef _FNV32_C_
#define _FNV32_C_ #define _FNV32_C_
#include "fnv-private.h" #include "fnv-private.h"
#include "FNV32.h" #include "FNV32.h"
INTERNET-DRAFT FNV
/* 32 bit FNV_prime = 2^24 + 2^8 + 0x93 */
#define FNV32prime 0x01000193 #define FNV32prime 0x01000193
#define FNV32basis 0x811C9DC5 #define FNV32basis 0x811C9DC5
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
/* Local prototype */ /* Local prototype */
void FNV32reverse ( uint32_t const *out, uint32_t hash ); static void FNV32reverse ( uint32_t *out, uint32_t hash );
#endif #endif
/* FNV32 hash a zero terminated string not including the zero /* FNV32 hash a zero terminated string not including the zero
*********************************************************************/ *********************************************************************/
int FNV32string ( const char *in, uint32_t * const out ) int FNV32string ( const char *in, uint32_t * const out )
{ {
INTERNET-DRAFT FNV
uint32_t temp; uint32_t temp;
uint8_t ch; uint8_t ch;
if ( in && out ) if ( in && out )
{ {
temp = FNV32basis; temp = FNV32basis;
while ( (ch = *in++) ) while ( (ch = *in++) )
temp = FNV32prime * ( temp ^ ch ); temp = FNV32prime * ( temp ^ ch );
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
FNV32reverse ( out, temp ); FNV32reverse ( out, temp );
#else #else
*out = temp; *out = temp;
#endif #endif
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; /* Null input pointer */ return fnvNull; /* Null input pointer */
} /* end FNV32string */ } /* end FNV32string */
/* FNV32 hash a counted block /* FNV32 hash a counted block
***************************************************************/ ***************************************************************/
int FNV32block ( const uint8_t *in, int FNV32block ( const void *vin,
long int length, long int length,
uint32_t * const out ) uint32_t * const out )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint32_t temp; uint32_t temp;
if ( in && out ) if ( in && out )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
for ( temp = FNV32basis; length > 0; length-- ) for ( temp = FNV32basis; length > 0; length-- )
temp = FNV32prime * ( temp ^ *in++ ); temp = FNV32prime * ( temp ^ *in++ );
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
FNV32reverse ( out, temp ); FNV32reverse ( out, temp );
#else #else
*out = temp; *out = temp;
#endif #endif
return fnvSuccess; return fnvSuccess;
INTERNET-DRAFT FNV
} }
return fnvNull; /* Null input pointer */ return fnvNull; /* Null input pointer */
} /* end FNV32block */ } /* end FNV32block */
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
/* Store a Big Endian result back as Little Endian /* Store a Big Endian result back as Little Endian
***************************************************************/ ***************************************************************/
static void FNV32reverse ( uint32_t const *out, uint32_t hash ) static void FNV32reverse ( uint32_t *out, uint32_t hash )
{ {
uint32_t temp; uint32_t temp;
INTERNET-DRAFT FNV
temp = hash & 0xFF; temp = hash & 0xFF;
hash >>= 8; hash >>= 8;
temp = ( temp << 8 ) + ( hash & 0xFF ); temp = ( temp << 8 ) + ( hash & 0xFF );
hash >>= 8; hash >>= 8;
temp = ( temp << 8 ) + ( hash & 0xFF ); temp = ( temp << 8 ) + ( hash & 0xFF );
hash >>= 8; hash >>= 8;
*out = ( temp << 8 ) + ( hash & 0xFF ); *out = ( temp << 8 ) + ( hash & 0xFF );
} /* end FNV32reverse */ } /* end FNV32reverse */
skipping to change at page 18, line 4 skipping to change at page 19, line 43
if ( ctx ) if ( ctx )
{ {
ctx->Hash = basis; ctx->Hash = basis;
ctx->Computed = FNVinited+FNV32state; ctx->Computed = FNVinited+FNV32state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV32initBasis */ } /* end FNV32initBasis */
/* hash in a counted block /* hash in a counted block
INTERNET-DRAFT FNV
***************************************************************/ ***************************************************************/
int FNV32blockin ( FNV32context * const ctx, int FNV32blockin ( FNV32context * const ctx,
const uint8_t *in, const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint32_t temp; uint32_t temp;
if ( ctx && in ) if ( ctx && in )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
INTERNET-DRAFT FNV
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV32state: case FNVinited+FNV32state:
ctx->Computed = FNVcomputed+FNV32state; ctx->Computed = FNVcomputed+FNV32state;
case FNVcomputed+FNV32state: case FNVcomputed+FNV32state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( temp = ctx->Hash; length > 0; length-- ) for ( temp = ctx->Hash; length > 0; length-- )
skipping to change at page 19, line 4 skipping to change at page 20, line 46
case FNVinited+FNV32state: case FNVinited+FNV32state:
ctx->Computed = FNVcomputed+FNV32state; ctx->Computed = FNVcomputed+FNV32state;
case FNVcomputed+FNV32state: case FNVcomputed+FNV32state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
temp = ctx->Hash; temp = ctx->Hash;
while ( (ch = (uint8_t)*in++) ) while ( (ch = (uint8_t)*in++) )
temp = FNV32prime * ( temp ^ ch ); temp = FNV32prime * ( temp ^ ch );
INTERNET-DRAFT FNV
ctx->Hash = temp; ctx->Hash = temp;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV32stringin */ } /* end FNV32stringin */
/* return hash /* return hash
***************************************************************/ ***************************************************************/
int FNV32result ( FNV32context * const ctx, int FNV32result ( FNV32context * const ctx,
uint32_t * const out ) uint32_t * const out )
{ {
INTERNET-DRAFT FNV
if ( ctx && out ) if ( ctx && out )
{ {
if ( ctx->Computed != FNVcomputed+FNV32state ) if ( ctx->Computed != FNVcomputed+FNV32state )
return fnvStateError; return fnvStateError;
ctx->Computed = FNVemptied+FNV32state; ctx->Computed = FNVemptied+FNV32state;
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
FNV32reverse ( out, ctx->Hash ); FNV32reverse ( out, ctx->Hash );
#else #else
*out = ctx->Hash; *out = ctx->Hash;
#endif #endif
skipping to change at page 19, line 45 skipping to change at page 21, line 33
<CODE ENDS> <CODE ENDS>
6.1.2 FNV64 C Code 6.1.2 FNV64 C Code
The header and C source for 64-bit FNV-1a. The header and C source for 64-bit FNV-1a.
<CODE BEGINS> <CODE BEGINS>
/***************************** FNV64.h ******************************/ /***************************** FNV64.h ******************************/
/******************* See RFC NNNN for details. **********************/ /******************* See RFC NNNN for details. **********************/
/* /*
* Copyright (c) 2015 IETF Trust and the persons identified as * Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
#ifndef _FNV64_H_ #ifndef _FNV64_H_
#define _FNV64_H_ #define _FNV64_H_
/* /*
* Description: * Description:
INTERNET-DRAFT FNV
* This file provides headers for the 64-bit version of the FNV-1a * This file provides headers for the 64-bit version of the FNV-1a
* non-cryptographic hash algorithm. * non-cryptographic hash algorithm.
*
* >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */
#define FNV_64bitIntegers
/* FNV_64bitIntegers - Define this if your system supports 64-bit
* arithmetic including 32-bit x 32-bit multiplication
* producing a 64-bit product. If undefined, it will be
* assumed that 32-bit arithmetic is supported including
* 16-bit x 16-bit multiplication producing a 32-bit result.
*
* FNV_BigEndian - Define this ONLY if your system uses big
* endian representation AND your FNV hashes need to
* interoperate with little endian systems. If you #define
* this symbol when not needed, it will unnecessarily slow
* down and increase the code size of the FNV functions.
*/ */
#include "FNVconfig.h"
#include <stdint.h> #include <stdint.h>
#define FNV64size (64/8) #define FNV64size (64/8)
/* If you do not have the ISO standard stdint.h header file, then you /* If you do not have the ISO standard stdint.h header file, then you
* must typedef the following types: * must typedef the following types:
INTERNET-DRAFT FNV
* *
* type meaning * type meaning
* uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers)
* uint32_t unsigned 32 bit integer * uint32_t unsigned 32 bit integer
* uint16_t unsigned 16 bit integer * uint16_t unsigned 16 bit integer
* uint8_t unsigned 8 bit integer (i.e., unsigned char) * uint8_t unsigned 8 bit integer (i.e., unsigned char)
*/ */
#ifndef _FNV_ErrCodes_ #ifndef _FNV_ErrCodes_
#define _FNV_ErrCodes_ #define _FNV_ErrCodes_
skipping to change at page 21, line 4 skipping to change at page 22, line 32
enum { /* success and errors */ enum { /* success and errors */
fnvSuccess = 0, fnvSuccess = 0,
fnvNull, /* Null pointer parameter */ fnvNull, /* Null pointer parameter */
fnvStateError, /* called Input after Result, etc. */ fnvStateError, /* called Input after Result, etc. */
fnvBadParam /* passed a bad parameter */ fnvBadParam /* passed a bad parameter */
}; };
#endif /* _FNV_ErrCodes_ */ #endif /* _FNV_ErrCodes_ */
/* /*
* This structure holds context information for an FNV64 hash * This structure holds context information for an FNV64 hash
INTERNET-DRAFT FNV
*/ */
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
/* version if 64 bit integers supported */ /* version if 64 bit integers supported */
typedef struct FNV64context_s { typedef struct FNV64context_s {
int Computed; /* state */ int Computed; /* state */
uint64_t Hash; uint64_t Hash;
} FNV64context; } FNV64context;
#else #else
skipping to change at page 21, line 32 skipping to change at page 23, line 4
} FNV64context; } FNV64context;
#endif /* FNV_64bitIntegers */ #endif /* FNV_64bitIntegers */
/* /*
* Function Prototypes * Function Prototypes
* FNV64string: hash a zero terminated string not including * FNV64string: hash a zero terminated string not including
* the terminating zero * the terminating zero
* FNV64block: FNV64 hash a specified length byte vector * FNV64block: FNV64 hash a specified length byte vector
* FNV64init: initializes an FNV64 context * FNV64init: initializes an FNV64 context
INTERNET-DRAFT FNV
* FNV64initBasis: initializes an FNV64 context with a * FNV64initBasis: initializes an FNV64 context with a
* provided basis * provided basis
* FNV64blockin: hash in a specified length byte vector * FNV64blockin: hash in a specified length byte vector
* FNV64stringin: hash in a zero terminated string not * FNV64stringin: hash in a zero terminated string not
* incluing the zero * incluing the zero
* FNV64result: returns the hash value * FNV64result: returns the hash value
* *
* Hash is returned as a 64-bit integer if supported, otherwise * Hash is returned as a 64-bit integer if supported, otherwise
* as a vector of 8-bit integers * as a vector of 8-bit integers
*/ */
#ifdef __cplusplus
extern "C" {
#endif
/* FNV64 */ /* FNV64 */
extern int FNV64init ( FNV64context * const ); extern int FNV64init ( FNV64context * const );
extern int FNV64blockin ( FNV64context * const, extern int FNV64blockin ( FNV64context * const,
const uint8_t * in, const void * in,
long int length ); long int length );
extern int FNV64stringin ( FNV64context * const, extern int FNV64stringin ( FNV64context * const,
const char * in ); const char * in );
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
extern int FNV64string ( const char *in, extern int FNV64string ( const char *in,
uint64_t * const out ); uint64_t * const out );
extern int FNV64block ( const uint8_t *in, extern int FNV64block ( const void *in,
long int length, long int length,
uint64_t * const out ); uint64_t * const out );
INTERNET-DRAFT FNV
extern int FNV64initBasis ( FNV64context * const, extern int FNV64initBasis ( FNV64context * const,
uint64_t basis ); uint64_t basis );
extern int FNV64result ( FNV64context * const, extern int FNV64result ( FNV64context * const,
uint64_t * const out ); uint64_t * const out );
#else #else
extern int FNV64string ( const char *in, extern int FNV64string ( const char *in,
uint8_t out[FNV64size] ); uint8_t out[FNV64size] );
extern int FNV64block ( const unsigned char *in, extern int FNV64block ( const void *in,
long int length, long int length,
uint8_t out[FNV64size] ); uint8_t out[FNV64size] );
extern int FNV32initBasis ( FNV64context * const, extern int FNV64initBasis ( FNV64context * const,
const uint8_t basis[FNV64size] ); const uint8_t basis[FNV64size] );
extern int FNV64result ( FNV64context * const, extern int FNV64result ( FNV64context * const,
uint8_t out[FNV64size] ); uint8_t out[FNV64size] );
#endif /* FNV_64bitIntegers */ #endif /* FNV_64bitIntegers */
#ifdef __cplusplus
}
#endif
#endif /* _FNV64_H_ */ #endif /* _FNV64_H_ */
INTERNET-DRAFT FNV
<CODE ENDS> <CODE ENDS>
<CODE BEGINS> <CODE BEGINS>
/***************************** FNV64.c ******************************/ /***************************** FNV64.c ******************************/
/******************** See RFC NNNN for details **********************/ /******************** See RFC NNNN for details **********************/
/* Copyright (c) 2015 IETF Trust and the persons identified as /* Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
/* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic
* hash function FNV-1a for 64-bit hashes. * hash function FNV-1a for 64-bit hashes.
*/ */
#ifndef _FNV64_C_ #ifndef _FNV64_C_
#define _FNV64_C_ #define _FNV64_C_
skipping to change at page 22, line 51 skipping to change at page 24, line 33
#include "fnv-private.h" #include "fnv-private.h"
#include "FNV64.h" #include "FNV64.h"
/******************************************************************** /********************************************************************
* START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
********************************************************************/ ********************************************************************/
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
/* Local prototype */ /* Local prototype */
void FNV64reverse ( uint64_t * const out, uint64_t hash ); static void FNV64reverse ( uint64_t * out, uint64_t hash );
#endif /* FNV_BigEndian */ #endif /* FNV_BigEndian */
/* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */
#define FNV64prime 0x00000100000001B3 #define FNV64prime 0x00000100000001B3
#define FNV64basis 0xCBF29CE484222325 #define FNV64basis 0xCBF29CE484222325
INTERNET-DRAFT FNV
/* FNV64 hash a null terminated string (64 bit) /* FNV64 hash a null terminated string (64 bit)
********************************************************************/ ********************************************************************/
int FNV64string ( const char *in, uint64_t * const out ) int FNV64string ( const char *in, uint64_t * const out )
{ {
uint64_t temp; uint64_t temp;
uint8_t ch; uint8_t ch;
if ( in && out ) if ( in && out )
{ {
temp = FNV64basis; temp = FNV64basis;
while ( (ch = *in++) ) while ( (ch = *in++) )
temp = FNV64prime * ( temp ^ ch ); temp = FNV64prime * ( temp ^ ch );
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
FNV64reverse ( out, temp ); FNV64reverse ( out, temp );
#else #else
*out = temp; *out = temp;
INTERNET-DRAFT FNV
#endif #endif
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; /* Null input pointer */ return fnvNull; /* Null input pointer */
} /* end FNV64string */ } /* end FNV64string */
/* FNV64 hash a counted block (64 bit) /* FNV64 hash a counted block (64 bit)
********************************************************************/ ********************************************************************/
int FNV64block ( const uint8_t *in, int FNV64block ( const void *vin,
long int length, long int length,
uint64_t * const out ) uint64_t * const out )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint64_t temp; uint64_t temp;
if ( in && out ) if ( in && out )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
for ( temp = FNV64basis; length > 0; length-- ) for ( temp = FNV64basis; length > 0; length-- )
temp = FNV64prime * ( temp ^ *in++ ); temp = FNV64prime * ( temp ^ *in++ );
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
FNV64reverse ( out, temp ); FNV64reverse ( out, temp );
skipping to change at page 24, line 4 skipping to change at page 25, line 42
#endif #endif
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; /* Null input pointer */ return fnvNull; /* Null input pointer */
} /* end FNV64block */ } /* end FNV64block */
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
/* Store a Big Endian result back as Little Endian /* Store a Big Endian result back as Little Endian
***************************************************************/ ***************************************************************/
static void FNV64reverse ( uint64_t *out, uint64_t hash )
INTERNET-DRAFT FNV
static void FNV64reverse ( uint64_t const *out, uint64_t hash )
{ {
uint64_t temp; uint64_t temp;
int i; int i;
temp = hash & 0xFF; temp = hash & 0xFF;
for ( i = FNV64size - 1; i > 0; i-- ) for ( i = FNV64size - 1; i > 0; i-- )
{ {
hash >>= 8; hash >>= 8;
temp = ( temp << 8 ) + ( hash & 0xFF ); temp = ( temp << 8 ) + ( hash & 0xFF );
} }
*out = temp; *out = temp;
} /* end FNV64reverse */ } /* end FNV64reverse */
#endif /* FNV_BigEndian */ #endif /* FNV_BigEndian */
INTERNET-DRAFT FNV
/******************************************************************** /********************************************************************
* Set of init, input, and output functions below * * Set of init, input, and output functions below *
* to incrementally compute FNV64 * * to incrementally compute FNV64 *
********************************************************************/ ********************************************************************/
/* initialize context (64 bit) /* initialize context (64 bit)
********************************************************************/ ********************************************************************/
int FNV64init ( FNV64context * const ctx ) int FNV64init ( FNV64context * const ctx )
{ {
skipping to change at page 24, line 51 skipping to change at page 26, line 34
ctx->Hash = basis; ctx->Hash = basis;
ctx->Computed = FNVinited+FNV64state; ctx->Computed = FNVinited+FNV64state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV64initBasis */ } /* end FNV64initBasis */
/* hash in a counted block (64 bit) /* hash in a counted block (64 bit)
********************************************************************/ ********************************************************************/
int FNV64blockin ( FNV64context * const ctx, int FNV64blockin ( FNV64context * const ctx,
const uint8_t *in, const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint64_t temp; uint64_t temp;
INTERNET-DRAFT FNV
if ( ctx && in ) if ( ctx && in )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV64state: case FNVinited+FNV64state:
ctx->Computed = FNVcomputed+FNV64state; ctx->Computed = FNVcomputed+FNV64state;
case FNVcomputed+FNV64state: case FNVcomputed+FNV64state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( temp = ctx->Hash; length > 0; length-- ) for ( temp = ctx->Hash; length > 0; length-- )
temp = FNV64prime * ( temp ^ *in++ ); temp = FNV64prime * ( temp ^ *in++ );
ctx->Hash = temp; ctx->Hash = temp;
INTERNET-DRAFT FNV
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV64input */ } /* end FNV64input */
/* hash in a zero terminated string not including the zero (64 bit) /* hash in a zero terminated string not including the zero (64 bit)
********************************************************************/ ********************************************************************/
int FNV64stringin ( FNV64context * const ctx, int FNV64stringin ( FNV64context * const ctx,
const char *in ) const char *in )
{ {
skipping to change at page 26, line 4 skipping to change at page 27, line 41
temp = ctx->Hash; temp = ctx->Hash;
while ( (ch = *in++) ) while ( (ch = *in++) )
temp = FNV64prime * ( temp ^ ch ); temp = FNV64prime * ( temp ^ ch );
ctx->Hash = temp; ctx->Hash = temp;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV64stringin */ } /* end FNV64stringin */
/* return hash (64 bit) /* return hash (64 bit)
INTERNET-DRAFT FNV
********************************************************************/ ********************************************************************/
int FNV64result ( FNV64context * const ctx, int FNV64result ( FNV64context * const ctx,
uint64_t * const out ) uint64_t * const out )
{ {
if ( ctx && out ) if ( ctx && out )
{ {
if ( ctx->Computed != FNVcomputed+FNV64state ) if ( ctx->Computed != FNVcomputed+FNV64state )
return fnvStateError; return fnvStateError;
ctx->Computed = FNVemptied+FNV64state; ctx->Computed = FNVemptied+FNV64state;
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
FNV64reverse ( out, ctx->Hash ); FNV64reverse ( out, ctx->Hash );
#else #else
*out = ctx->Hash; *out = ctx->Hash;
#endif #endif
ctx->Hash = 0; ctx->Hash = 0;
return fnvSuccess; return fnvSuccess;
INTERNET-DRAFT FNV
} }
return fnvNull; return fnvNull;
} /* end FNV64result */ } /* end FNV64result */
/****************************************************************** /******************************************************************
* END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
******************************************************************/ ******************************************************************/
#else /* FNV_64bitIntegers */ #else /* FNV_64bitIntegers */
/****************************************************************** /******************************************************************
* START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
******************************************************************/ ******************************************************************/
/* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */
/* #define FNV64prime 0x00000100000001B3 */ /* #define FNV64prime 0x00000100000001B3 */
#define FNV64primeX 0x01B3 #define FNV64primeX 0x01B3
#define FNV64shift 8 #define FNV64shift 8
/* #define FNV64basis 0xCBF29CE484222325 */ /* #define FNV64basis 0xCBF29CE484222325 */
#define FNV64basis0 0xCBF2 #define FNV64basis0 0xCBF2
#define FNV64basis1 0x9CE4 #define FNV64basis1 0x9CE4
#define FNV64basis2 0x8422 #define FNV64basis2 0x8422
#define FN64Vbasis3 0x2325 #define FNV64basis3 0x2325
/* FNV64 hash a null terminated string (32 bit) /* FNV64 hash a null terminated string (32 bit)
********************************************************************/ ********************************************************************/
int FNV64string ( const char *in, uint8_t out[FNV64size] ) int FNV64string ( const char *in, uint8_t out[FNV64size] )
{ {
FNV64context ctx; FNV64context ctx;
int err; int err;
if (err = FNV64init (&ctx)) if ( ( err = FNV64init (&ctx) ) != fnvSuccess )
return err; return err;
if (err = FNV64stringin (&ctx, in)) if ( ( err = FNV64stringin (&ctx, in) ) != fnvSuccess )
return err; return err;
return FNV64result (&ctx, out); return FNV64result (&ctx, out);
INTERNET-DRAFT FNV
} /* end FNV64string */ } /* end FNV64string */
/* FNV64 hash a counted block (32 bit) /* FNV64 hash a counted block (32 bit)
********************************************************************/ ********************************************************************/
int FNV64block ( const char *in, int FNV64block ( const void *in,
long int length, long int length,
uint8_t out[FNV64size] ) uint8_t out[FNV64size] )
{ {
FNV64context ctx; FNV64context ctx;
int err; int err;
if (err = FNV64init (&ctx)) if ( ( err = FNV64init (&ctx) ) != fnvSuccess )
return err; return err;
if (err = FNV64blockin (&ctx, in, length)) if ( ( err = FNV64blockin (&ctx, in, length) ) != fnvSuccess )
return err; return err;
return FNV64result (&ctx, out));
INTERNET-DRAFT FNV
return FNV64result (&ctx, out);
} /* end FNV64block */ } /* end FNV64block */
/******************************************************************** /********************************************************************
* Set of init, input, and output functions below * * Set of init, input, and output functions below *
* to incrementally compute FNV64 * * to incrementally compute FNV64 *
********************************************************************/ ********************************************************************/
/* initialize context (32 bit) /* initialize context (32 bit)
********************************************************************/ ********************************************************************/
int FNV64init ( FNV64context * const ctx ) int FNV64init ( FNV64context * const ctx )
skipping to change at page 27, line 53 skipping to change at page 29, line 39
} /* end FNV64init */ } /* end FNV64init */
/* initialize context (32 bit) /* initialize context (32 bit)
********************************************************************/ ********************************************************************/
int FNV64initBasis ( FNV64context * const ctx, int FNV64initBasis ( FNV64context * const ctx,
const uint8_t basis[FNV64size] ) const uint8_t basis[FNV64size] )
{ {
if ( ctx ) if ( ctx )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
ctx->Hash[0] = basis[1] + basis[0]<<8; ctx->Hash[0] = basis[1] + ( basis[0]<<8 );
ctx->Hash[1] = basis[3] + basis[2]<<8; ctx->Hash[1] = basis[3] + ( basis[2]<<8 );
ctx->Hash[2] = basis[5] + ( basis[4]<<8 );
INTERNET-DRAFT FNV ctx->Hash[3] = basis[7] + ( basis[6]<<8 );
ctx->Hash[2] = basis[5] + basis[4]<<8;
ctx->Hash[3] = basis[7] + basis[6]<<8;
#else #else
ctx->Hash[0] = basis[0] + basis[1]<<8; ctx->Hash[0] = basis[0] + ( basis[1]<<8 );
ctx->Hash[1] = basis[2] + basis[3]<<8; ctx->Hash[1] = basis[2] + ( basis[3]<<8 );
ctx->Hash[2] = basis[4] + basis[5]<<8; ctx->Hash[2] = basis[4] + ( basis[5]<<8 );
ctx->Hash[3] = basis[6] + basis[7]<<8; ctx->Hash[3] = basis[6] + ( basis[7]<<8 );
#endif #endif
ctx->Computed = FNVinited+FNV64state; ctx->Computed = FNVinited+FNV64state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV64initBasis */ } /* end FNV64initBasis */
/* hash in a counted block (32 bit) /* hash in a counted block (32 bit)
INTERNET-DRAFT FNV
********************************************************************/ ********************************************************************/
int FNV64blockin ( FNV64context * const ctx, int FNV64blockin ( FNV64context * const ctx,
const unsigned char *in, const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint32_t temp[FNV64size/2]; uint32_t temp[FNV64size/2];
uint32_t temp2[2]; uint32_t temp2[2];
int i; int i;
if ( ctx && in ) if ( ctx && in )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
skipping to change at page 29, line 4 skipping to change at page 30, line 42
{ {
/* temp = FNV64prime * ( temp ^ *in++ ); */ /* temp = FNV64prime * ( temp ^ *in++ ); */
temp2[1] = temp[3] << FNV64shift; temp2[1] = temp[3] << FNV64shift;
temp2[0] = temp[2] << FNV64shift; temp2[0] = temp[2] << FNV64shift;
temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); temp[3] = FNV64primeX * ( temp[3] ^ *in++ );
temp[2] *= FNV64primeX; temp[2] *= FNV64primeX;
temp[1] = temp[1] * FNV64primeX + temp2[1]; temp[1] = temp[1] * FNV64primeX + temp2[1];
temp[0] = temp[0] * FNV64primeX + temp2[0]; temp[0] = temp[0] * FNV64primeX + temp2[0];
temp[2] += temp[3] >> 16; temp[2] += temp[3] >> 16;
temp[3] &= 0xFFFF; temp[3] &= 0xFFFF;
INTERNET-DRAFT FNV
temp[1] += temp[2] >> 16; temp[1] += temp[2] >> 16;
temp[2] &= 0xFFFF; temp[2] &= 0xFFFF;
temp[0] += temp[1] >> 16; temp[0] += temp[1] >> 16;
temp[1] &= 0xFFFF; temp[1] &= 0xFFFF;
} }
for ( i=0; i<FNV64size/2; ++i ) for ( i=0; i<FNV64size/2; ++i )
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV64blockin */ } /* end FNV64blockin */
/* hash in a string (32 bit) /* hash in a string (32 bit)
********************************************************************/ ********************************************************************/
INTERNET-DRAFT FNV
int FNV64stringin ( FNV64context * const ctx, int FNV64stringin ( FNV64context * const ctx,
const char *in ) const char *in )
{ {
uint32_t temp[FNV64size/2]; uint32_t temp[FNV64size/2];
uint32_t temp2[2]; uint32_t temp2[2];
int i; int i;
uint8_t ch; uint8_t ch;
if ( ctx && in ) if ( ctx && in )
{ {
skipping to change at page 29, line 42 skipping to change at page 31, line 28
{ {
case FNVinited+FNV64state: case FNVinited+FNV64state:
ctx->Computed = FNVcomputed+FNV64state; ctx->Computed = FNVcomputed+FNV64state;
case FNVcomputed+FNV64state: case FNVcomputed+FNV64state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( i=0; i<FNV64size/2; ++i ) for ( i=0; i<FNV64size/2; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
while ( ch = (uint8_t)*in++ ) while ( ( ch = (uint8_t)*in++ ) != 0)
{ {
/* temp = FNV64prime * ( temp ^ ch ); */ /* temp = FNV64prime * ( temp ^ ch ); */
temp2[1] = temp[3] << FNV64shift; temp2[1] = temp[3] << FNV64shift;
temp2[0] = temp[2] << FNV64shift; temp2[0] = temp[2] << FNV64shift;
temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); temp[3] = FNV64primeX * ( temp[3] ^ *in++ );
temp[2] *= FNV64primeX; temp[2] *= FNV64primeX;
temp[1] = temp[1] * FNV64primeX + temp2[1]; temp[1] = temp[1] * FNV64primeX + temp2[1];
temp[0] = temp[0] * FNV64primeX + temp2[0]; temp[0] = temp[0] * FNV64primeX + temp2[0];
temp[2] += temp[3] >> 16; temp[2] += temp[3] >> 16;
temp[3] &= 0xFFFF; temp[3] &= 0xFFFF;
temp[1] += temp[2] >> 16; temp[1] += temp[2] >> 16;
temp[2] &= 0xFFFF; temp[2] &= 0xFFFF;
temp[0] += temp[1] >> 16; temp[0] += temp[1] >> 16;
temp[1] &= 0xFFFF; temp[1] &= 0xFFFF;
INTERNET-DRAFT FNV
} }
for ( i=0; i<FNV64size/2; ++i ) for ( i=0; i<FNV64size/2; ++i )
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV64stringin */ } /* end FNV64stringin */
/* return hash (32 bit) /* return hash (32 bit)
********************************************************************/ ********************************************************************/
int FNV64result ( FNV64context * const ctx, int FNV64result ( FNV64context * const ctx,
uint8_t out[FNV64size] ) uint8_t out[FNV64size] )
{ {
int i; int i;
INTERNET-DRAFT FNV
if ( ctx && out ) if ( ctx && out )
{ {
if ( ctx->Computed != FNVcomputed+FNV64state ) if ( ctx->Computed != FNVcomputed+FNV64state )
return fnvStateError; return fnvStateError;
for ( i=0; i<FNV64size/2; ++i ) for ( i=0; i<FNV64size/2; ++i )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
out[7-2*i] = ctx->Hash[i]; out[7-2*i] = ctx->Hash[i];
out[6-2*i] = ctx->Hash[i] >> 8; out[6-2*i] = ctx->Hash[i] >> 8;
skipping to change at page 31, line 5 skipping to change at page 32, line 39
* END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
********************************************************************/ ********************************************************************/
#endif /* _FNV64_C_ */ #endif /* _FNV64_C_ */
<CODE ENDS> <CODE ENDS>
6.1.3 FNV128 C Code 6.1.3 FNV128 C Code
The header and C source for 128-bit FNV-1a. The header and C source for 128-bit FNV-1a.
INTERNET-DRAFT FNV
<CODE BEGINS> <CODE BEGINS>
/**************************** FNV128.h **************************/ /**************************** FNV128.h **************************/
/***************** See RFC NNNN for details. ********************/ /***************** See RFC NNNN for details. ********************/
/* /*
* Copyright (c) 2015 IETF Trust and the persons identified as * Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
#ifndef _FNV128_H_ #ifndef _FNV128_H_
#define _FNV128_H_ #define _FNV128_H_
/* /*
* Description: * Description:
* This file provides headers for the 128-bit version of the * This file provides headers for the 128-bit version of the
* FNV-1a non-cryptographic hash algorithm.
*
* >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */
#define FNV_64bitIntegers INTERNET-DRAFT FNV
/* FNV_64bitIntegers - Define this if your system supports 64-bit * FNV-1a non-cryptographic hash algorithm.
* arithmetic including 32-bit x 32-bit multiplication
* producing a 64-bit product. If undefined, it will be
* assumed that 32-bit arithmetic is supported including
* 16-bit x 16-bit multiplication producing a 32-bit result.
*
* FNV_BigEndian - Define this ONLY if your system uses big
* endian representation AND your FNV hashes need to
* interoperate with little endian systems. If you #define
* this symbol when not needed, it will unnecessarily slow
* down and increase the code size of the FNV functions.
*/ */
#include "FNVconfig.h"
#include <stdint.h> #include <stdint.h>
#define FNV128size (128/8) #define FNV128size (128/8)
/* If you do not have the ISO standard stdint.h header file, then you /* If you do not have the ISO standard stdint.h header file, then you
* must typedef the following types: * must typedef the following types:
* *
* type meaning * type meaning
* uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers)
* uint32_t unsigned 32 bit integer * uint32_t unsigned 32 bit integer
* uint16_t unsigned 16 bit integer * uint16_t unsigned 16 bit integer
* uint8_t unsigned 8 bit integer (i.e., unsigned char) * uint8_t unsigned 8 bit integer (i.e., unsigned char)
*/ */
#ifndef _FNV_ErrCodes_ #ifndef _FNV_ErrCodes_
#define _FNV_ErrCodes_ #define _FNV_ErrCodes_
/********************************************************************* /*********************************************************************
INTERNET-DRAFT FNV
* All FNV functions provided return as integer as follows: * All FNV functions provided return as integer as follows:
* 0 -> success * 0 -> success
* >0 -> error as listed below * >0 -> error as listed below
*/ */
enum { /* success and errors */ enum { /* success and errors */
fnvSuccess = 0, fnvSuccess = 0,
fnvNull, /* Null pointer parameter */ fnvNull, /* Null pointer parameter */
fnvStateError, /* called Input after Result or before Init */ fnvStateError, /* called Input after Result or before Init */
fnvBadParam /* passed a bad parameter */ fnvBadParam /* passed a bad parameter */
}; };
skipping to change at page 32, line 35 skipping to change at page 34, line 4
uint32_t Hash[FNV128size/4]; uint32_t Hash[FNV128size/4];
} FNV128context; } FNV128context;
#else #else
/* version if 64 bit integers NOT supported */ /* version if 64 bit integers NOT supported */
typedef struct FNV128context_s { typedef struct FNV128context_s {
int Computed; /* state */ int Computed; /* state */
uint16_t Hash[FNV128size/2]; uint16_t Hash[FNV128size/2];
} FNV128context; } FNV128context;
INTERNET-DRAFT FNV
#endif /* FNV_64bitIntegers */ #endif /* FNV_64bitIntegers */
/* /*
* Function Prototypes * Function Prototypes
* FNV128string: hash a zero terminated string not including * FNV128string: hash a zero terminated string not including
* the terminating zero * the terminating zero
* FNV128block: FNV128 hash a specified length byte vector * FNV128block: FNV128 hash a specified length byte vector
* FNV128init: initializes an FNV128 context * FNV128init: initializes an FNV128 context
* FNV128initBasis: initializes an FNV128 context with a * FNV128initBasis: initializes an FNV128 context with a
* provided basis * provided basis
* FNV128blockin: hash in a specified length byte vector * FNV128blockin: hash in a specified length byte vector
* FNV128stringin: hash in a zero terminated string not * FNV128stringin: hash in a zero terminated string not
* including the zero * including the zero
* FNV128result: returns the hash value * FNV128result: returns the hash value
* *
* Hash is returned as an array of 8-bit integers * Hash is returned as an array of 8-bit integers
*/ */
#ifdef __cplusplus
extern "C" {
#endif
/* FNV128 */ /* FNV128 */
extern int FNV128string ( const char *in, extern int FNV128string ( const char *in,
INTERNET-DRAFT FNV
uint8_t out[FNV128size] ); uint8_t out[FNV128size] );
extern int FNV128block ( const unsigned char *in, extern int FNV128block ( const void *in,
long int length, long int length,
uint8_t out[FNV128size] ); uint8_t out[FNV128size] );
extern int FNV128init ( FNV128context * const ); extern int FNV128init ( FNV128context * const );
extern int FNV128initBasis ( FNV128context * const, extern int FNV128initBasis ( FNV128context * const,
const uint8_t basis[FNV128size] ); const uint8_t basis[FNV128size] );
extern int FNV128blockin ( FNV128context * const, extern int FNV128blockin ( FNV128context * const,
const unsigned char *in, const void *in,
long int length ); long int length );
extern int FNV128stringin ( FNV128context * const, extern int FNV128stringin ( FNV128context * const,
const char *in ); const char *in );
extern int FNV128result ( FNV128context * const, extern int FNV128result ( FNV128context * const,
uint8_t out[FNV128size] ); uint8_t out[FNV128size] );
#ifdef __cplusplus
}
#endif
#endif /* _FNV128_H_ */ #endif /* _FNV128_H_ */
<CODE ENDS> <CODE ENDS>
<CODE BEGINS> <CODE BEGINS>
/***************************** FNV128.c ****************************/ /***************************** FNV128.c ****************************/
/******************** See RFC NNNN for details *********************/ /******************** See RFC NNNN for details *********************/
/* Copyright (c) 2015 IETF Trust and the persons identified as /* Copyright (c) 2016 IETF Trust and the persons identified as
INTERNET-DRAFT FNV
* authors of the code. All rights * authors of the code. All rights
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
/* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic
* hash function FNV-1a for 128-bit hashes. * hash function FNV-1a for 128-bit hashes.
*/ */
#ifndef _FNV128_C_ #ifndef _FNV128_C_
#define _FNV128_C_ #define _FNV128_C_
skipping to change at page 33, line 52 skipping to change at page 35, line 30
/* common code for 64 and 32 bit modes */ /* common code for 64 and 32 bit modes */
/* FNV128 hash a null terminated string (64/32 bit) /* FNV128 hash a null terminated string (64/32 bit)
********************************************************************/ ********************************************************************/
int FNV128string ( const char *in, uint8_t out[FNV128size] ) int FNV128string ( const char *in, uint8_t out[FNV128size] )
{ {
FNV128context ctx; FNV128context ctx;
int err; int err;
err = FNV128init ( &ctx ); err = FNV128init ( &ctx );
if ( err ) return err; if ( err != fnvSuccess ) return err;
err = FNV128stringin ( &ctx, in ); err = FNV128stringin ( &ctx, in );
if ( err ) return err; if ( err != fnvSuccess ) return err;
return FNV128result (&ctx, out); return FNV128result (&ctx, out);
INTERNET-DRAFT FNV
} /* end FNV128string */ } /* end FNV128string */
/* FNV128 hash a counted block (64/32 bit) /* FNV128 hash a counted block (64/32 bit)
********************************************************************/ ********************************************************************/
int FNV128block ( const unsigned char *in, int FNV128block ( const void *in,
long int length, long int length,
uint8_t out[FNV128size] ) uint8_t out[FNV128size] )
{ {
FNV128context ctx; FNV128context ctx;
int err; int err;
err = FNV128init ( &ctx ); err = FNV128init ( &ctx );
if ( err ) return err; if ( err != fnvSuccess ) return err;
err = FNV128blockin ( &ctx, in, length ); err = FNV128blockin ( &ctx, in, length );
if ( err ) return err; if ( err != fnvSuccess ) return err;
return FNV128result ( &ctx, out ); return FNV128result ( &ctx, out );
} /* end FNV128block */ } /* end FNV128block */
/******************************************************************** /********************************************************************
* START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
********************************************************************/ ********************************************************************/
INTERNET-DRAFT FNV
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
/* 128 bit FNV_prime = 2^88 + 2^8 + 0x3b */
/* 0x00000000 01000000 00000000 0000013B */ /* 0x00000000 01000000 00000000 0000013B */
#define FNV128primeX 0x013B #define FNV128primeX 0x013B
#define FNV128shift 24 #define FNV128shift 24
/* 0x6C62272E 07BB0142 62B82175 6295C58D */ /* 0x6C62272E 07BB0142 62B82175 6295C58D */
#define FNV128basis0 0x6C62272E #define FNV128basis0 0x6C62272E
#define FNV128basis1 0x07BB0142 #define FNV128basis1 0x07BB0142
#define FNV128basis2 0x62B82175 #define FNV128basis2 0x62B82175
#define FNV128basis3 0x6295C58D #define FNV128basis3 0x6295C58D
skipping to change at page 35, line 4 skipping to change at page 36, line 36
********************************************************************/ ********************************************************************/
int FNV128init ( FNV128context * const ctx ) int FNV128init ( FNV128context * const ctx )
{ {
if ( ctx ) if ( ctx )
{ {
ctx->Hash[0] = FNV128basis0; ctx->Hash[0] = FNV128basis0;
ctx->Hash[1] = FNV128basis1; ctx->Hash[1] = FNV128basis1;
ctx->Hash[2] = FNV128basis2; ctx->Hash[2] = FNV128basis2;
ctx->Hash[3] = FNV128basis3; ctx->Hash[3] = FNV128basis3;
ctx->Computed = FNVinited+FNV128state; ctx->Computed = FNVinited+FNV128state;
INTERNET-DRAFT FNV
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV128init */ } /* end FNV128init */
/* initialize context with a provided basis (64 bit) /* initialize context with a provided basis (64 bit)
********************************************************************/ ********************************************************************/
int FNV128initBasis ( FNV128context * const ctx, int FNV128initBasis ( FNV128context * const ctx,
const uint8_t basis[FNV128size] ) const uint8_t basis[FNV128size] )
{ {
int i; int i;
uint8_t *ui8p; const uint8_t *ui8p;
uint32_t temp; uint32_t temp;
if ( ctx ) if ( ctx )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
ui8p = basis; ui8p = basis;
for ( i=0; i < FNV128size/4; ++i ) for ( i=0; i < FNV128size/4; ++i )
{ {
temp = (*ui8p++)<<8; temp = (*ui8p++)<<8;
INTERNET-DRAFT FNV
temp = (temp + *ui8p++)<<8; temp = (temp + *ui8p++)<<8;
temp = (temp + *ui8p++)<<8; temp = (temp + *ui8p++)<<8;
ctx->Hash[i] = temp + *ui8p; ctx->Hash[i] = temp + *ui8p;
} }
#else #else
ui8p = basis + ( FNV128size/4 - 1 ); ui8p = basis + ( FNV128size/4 - 1 );
for ( i=0; i < FNV128size/4; ++i ) for ( i=0; i < FNV128size/4; ++i )
{ {
temp = (*ui8p--)<<8; temp = (*ui8p--)<<8;
temp = (temp + *ui8p--)<<8; temp = (temp + *ui8p--)<<8;
skipping to change at page 35, line 51 skipping to change at page 37, line 30
#endif #endif
ctx->Computed = FNVinited+FNV128state; ctx->Computed = FNVinited+FNV128state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV128initBasis */ } /* end FNV128initBasis */
/* hash in a counted block (64 bit) /* hash in a counted block (64 bit)
********************************************************************/ ********************************************************************/
int FNV128blockin ( FNV128context * const ctx, int FNV128blockin ( FNV128context * const ctx,
const unsigned char *in, const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint64_t temp[FNV128size/4]; uint64_t temp[FNV128size/4];
uint64_t temp2[2]; uint64_t temp2[2];
int i; int i;
INTERNET-DRAFT FNV
if ( ctx && in ) if ( ctx && in )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV128state: case FNVinited+FNV128state:
ctx->Computed = FNVcomputed+FNV128state; ctx->Computed = FNVcomputed+FNV128state;
case FNVcomputed+FNV128state: case FNVcomputed+FNV128state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( i=0; i<FNV128size/4; ++i ) for ( i=0; i<FNV128size/4; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
for ( ; length > 0; length-- ) for ( ; length > 0; length-- )
{ {
/* temp = FNV128prime * ( temp ^ *in++ ); */ /* temp = FNV128prime * ( temp ^ *in++ ); */
temp2[1] = temp[3] << FNV128shift; temp2[1] = temp[3] << FNV128shift;
INTERNET-DRAFT FNV
temp2[0] = temp[2] << FNV128shift; temp2[0] = temp[2] << FNV128shift;
temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); temp[3] = FNV128primeX * ( temp[3] ^ *in++ );
temp[2] *= FNV128primeX; temp[2] *= FNV128primeX;
temp[1] = temp[1] * FNV128primeX + temp2[1]; temp[1] = temp[1] * FNV128primeX + temp2[1];
temp[0] = temp[0] * FNV128primeX + temp2[0]; temp[0] = temp[0] * FNV128primeX + temp2[0];
temp[2] += temp[3] >> 32; temp[2] += temp[3] >> 32;
temp[3] &= 0xFFFFFFFF; temp[3] &= 0xFFFFFFFF;
temp[1] += temp[2] >> 32; temp[1] += temp[2] >> 32;
temp[2] &= 0xFFFFFFFF; temp[2] &= 0xFFFFFFFF;
temp[0] += temp[1] >> 32; temp[0] += temp[1] >> 32;
skipping to change at page 37, line 4 skipping to change at page 38, line 38
int FNV128stringin ( FNV128context * const ctx, const char *in ) int FNV128stringin ( FNV128context * const ctx, const char *in )
{ {
uint64_t temp[FNV128size/4]; uint64_t temp[FNV128size/4];
uint64_t temp2[2]; uint64_t temp2[2];
int i; int i;
uint8_t ch; uint8_t ch;
if ( ctx && in ) if ( ctx && in )
{ {
switch ( ctx->Computed ) switch ( ctx->Computed )
INTERNET-DRAFT FNV
{ {
case FNVinited+FNV128state: case FNVinited+FNV128state:
ctx->Computed = FNVcomputed+FNV128state; ctx->Computed = FNVcomputed+FNV128state;
case FNVcomputed+FNV128state: case FNVcomputed+FNV128state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( i=0; i<FNV128size/4; ++i ) for ( i=0; i<FNV128size/4; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
while ( (ch = (uint8_t)*in++) ) while ( (ch = (uint8_t)*in++) )
{ {
/* temp = FNV128prime * ( temp ^ ch ); */ /* temp = FNV128prime * ( temp ^ ch ); */
temp2[1] = temp[3] << FNV128shift; temp2[1] = temp[3] << FNV128shift;
temp2[0] = temp[2] << FNV128shift; temp2[0] = temp[2] << FNV128shift;
temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); temp[3] = FNV128primeX * ( temp[3] ^ *in++ );
temp[2] *= FNV128primeX; temp[2] *= FNV128primeX;
temp[1] = temp[1] * FNV128primeX + temp2[1]; temp[1] = temp[1] * FNV128primeX + temp2[1];
temp[0] = temp[0] * FNV128primeX + temp2[0]; temp[0] = temp[0] * FNV128primeX + temp2[0];
INTERNET-DRAFT FNV
temp[2] += temp[3] >> 32; temp[2] += temp[3] >> 32;
temp[3] &= 0xFFFFFFFF; temp[3] &= 0xFFFFFFFF;
temp[1] += temp[2] >> 32; temp[1] += temp[2] >> 32;
temp[2] &= 0xFFFFFFFF; temp[2] &= 0xFFFFFFFF;
temp[0] += temp[1] >> 32; temp[0] += temp[1] >> 32;
temp[1] &= 0xFFFFFFFF; temp[1] &= 0xFFFFFFFF;
} }
for ( i=0; i<FNV128size/4; ++i ) for ( i=0; i<FNV128size/4; ++i )
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
return fnvSuccess; return fnvSuccess;
skipping to change at page 38, line 4 skipping to change at page 39, line 38
{ {
if ( ctx->Computed != FNVcomputed+FNV128state ) if ( ctx->Computed != FNVcomputed+FNV128state )
return fnvStateError; return fnvStateError;
for ( i=0; i<FNV128size/4; ++i ) for ( i=0; i<FNV128size/4; ++i )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
out[15-4*i] = ctx->Hash[i]; out[15-4*i] = ctx->Hash[i];
out[14-4*i] = ctx->Hash[i] >> 8; out[14-4*i] = ctx->Hash[i] >> 8;
out[13-4*i] = ctx->Hash[i] >> 16; out[13-4*i] = ctx->Hash[i] >> 16;
out[12-4*i] = ctx->Hash[i] >> 24; out[12-4*i] = ctx->Hash[i] >> 24;
INTERNET-DRAFT FNV
#else #else
out[4*i] = ctx->Hash[i]; out[4*i] = ctx->Hash[i];
out[4*i+1] = ctx->Hash[i] >> 8; out[4*i+1] = ctx->Hash[i] >> 8;
out[4*i+2] = ctx->Hash[i] >> 16; out[4*i+2] = ctx->Hash[i] >> 16;
out[4*i+3] = ctx->Hash[i] >> 24; out[4*i+3] = ctx->Hash[i] >> 24;
#endif #endif
ctx -> Hash[i] = 0; ctx -> Hash[i] = 0;
} }
ctx->Computed = FNVemptied+FNV128state; ctx->Computed = FNVemptied+FNV128state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV128result */ } /* end FNV128result */
/****************************************************************** /******************************************************************
* END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
******************************************************************/ ******************************************************************/
#else /* FNV_64bitIntegers */ #else /* FNV_64bitIntegers */
/****************************************************************** /******************************************************************
INTERNET-DRAFT FNV
* START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
******************************************************************/ ******************************************************************/
/* 128 bit FNV_prime = 2^88 + 2^8 + 0x3b */
/* 0x00000000 01000000 00000000 0000013B */ /* 0x00000000 01000000 00000000 0000013B */
#define FNV128primeX 0x013B #define FNV128primeX 0x013B
#define FNV128shift 8 #define FNV128shift 8
/* 0x6C62272E 07BB0142 62B82175 6295C58D */ /* 0x6C62272E 07BB0142 62B82175 6295C58D */
uint16_t FNV128basis[FNV128size/2] = uint16_t FNV128basis[FNV128size/2] =
{ 0x6C62, 0x272E, 0x07BB, 0x0142, { 0x6C62, 0x272E, 0x07BB, 0x0142,
0x62B8, 0x2175, 0x6295, 0xC58D }; 0x62B8, 0x2175, 0x6295, 0xC58D };
/******************************************************************** /********************************************************************
skipping to change at page 39, line 4 skipping to change at page 40, line 38
int i; int i;
if ( ctx ) if ( ctx )
{ {
for ( i=0; i<FNV128size/2; ++i ) for ( i=0; i<FNV128size/2; ++i )
ctx->Hash[i] = FNV128basis[i]; ctx->Hash[i] = FNV128basis[i];
ctx->Computed = FNVinited+FNV128state; ctx->Computed = FNVinited+FNV128state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
INTERNET-DRAFT FNV
} /* end FNV128init */ } /* end FNV128init */
/* initialize context with a provided basis (32 bit) /* initialize context with a provided basis (32 bit)
********************************************************************/ ********************************************************************/
int FNV128initBasis ( FNV128context *ctx, int FNV128initBasis ( FNV128context *ctx,
const uint8_t basis[FNV128size] ) const uint8_t basis[FNV128size] )
{ {
int i; int i;
uint8_t *ui8p; const uint8_t *ui8p;
uint32_t temp; uint32_t temp;
if ( ctx ) if ( ctx )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
ui8p = basis; ui8p = basis;
for ( i=0; i < FNV128size/2; ++i ) for ( i=0; i < FNV128size/2; ++i )
{ {
temp = *ui8p++; temp = *ui8p++;
ctx->Hash[i] = temp<<8 + (*ui8p++);
INTERNET-DRAFT FNV
ctx->Hash[i] = ( temp<<8 ) + (*ui8p++);
} }
#else #else
ui8p = basis + (FNV128size/2 - 1); ui8p = basis + (FNV128size/2 - 1);
for ( i=0; i < FNV128size/2; ++i ) for ( i=0; i < FNV128size/2; ++i )
{ {
temp = *ui8p--; temp = *ui8p--;
ctx->Hash[i] = (temp<<8) + (*ui8p--); ctx->Hash[i] = ( temp<<8 ) + (*ui8p--);
} }
#endif #endif
ctx->Computed = FNVinited+FNV128state; ctx->Computed = FNVinited+FNV128state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV128initBasis */ } /* end FNV128initBasis */
/* hash in a counted block (32 bit) /* hash in a counted block (32 bit)
*******************************************************************/ *******************************************************************/
int FNV128blockin ( FNV128context *ctx, int FNV128blockin ( FNV128context *ctx,
const unsigned char *in, const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint32_t temp[FNV128size/2]; uint32_t temp[FNV128size/2];
uint32_t temp2[3]; uint32_t temp2[3];
int i; int i;
if ( ctx && in ) if ( ctx && in )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
INTERNET-DRAFT FNV
case FNVinited+FNV128state: case FNVinited+FNV128state:
ctx->Computed = FNVcomputed+FNV128state; ctx->Computed = FNVcomputed+FNV128state;
case FNVcomputed+FNV128state: case FNVcomputed+FNV128state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( i=0; i<FNV128size/2; ++i ) for ( i=0; i<FNV128size/2; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
for ( ; length > 0; length-- ) for ( ; length > 0; length-- )
{ {
/* temp = FNV128prime * ( temp ^ *in++ ); */ /* temp = FNV128prime * ( temp ^ *in++ ); */
temp[7] ^= *in++; temp[7] ^= *in++;
temp2[2] = temp[7] << FNV128shift; temp2[2] = temp[7] << FNV128shift;
temp2[1] = temp[6] << FNV128shift; temp2[1] = temp[6] << FNV128shift;
temp2[0] = temp[5] << FNV128shift; temp2[0] = temp[5] << FNV128shift;
for ( i=0; i<8; ++i ) for ( i=0; i<8; ++i )
INTERNET-DRAFT FNV
temp[i] *= FNV128primeX; temp[i] *= FNV128primeX;
temp[2] += temp2[2]; temp[2] += temp2[2];
temp[1] += temp2[1]; temp[1] += temp2[1];
temp[0] += temp2[0]; temp[0] += temp2[0];
for ( i=7; i>0; --i ) for ( i=7; i>0; --i )
{ {
temp[i-1] += temp[i] >> 16; temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF; temp[i] &= 0xFFFF;
} }
} }
skipping to change at page 41, line 4 skipping to change at page 42, line 40
uint32_t temp2[3]; uint32_t temp2[3];
int i; int i;
uint8_t ch; uint8_t ch;
if ( ctx && in ) if ( ctx && in )
{ {
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV128state: case FNVinited+FNV128state:
ctx->Computed = FNVcomputed+FNV128state; ctx->Computed = FNVcomputed+FNV128state;
INTERNET-DRAFT FNV
case FNVcomputed+FNV128state: case FNVcomputed+FNV128state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( i=0; i<FNV128size/2; ++i ) for ( i=0; i<FNV128size/2; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
while ( (ch = (uint8_t)*in++) ) while ( (ch = (uint8_t)*in++) )
{ {
/* temp = FNV128prime * ( temp ^ *in++ ); */ /* temp = FNV128prime * ( temp ^ *in++ ); */
temp[7] ^= ch; temp[7] ^= ch;
temp2[2] = temp[7] << FNV128shift; temp2[2] = temp[7] << FNV128shift;
temp2[1] = temp[6] << FNV128shift; temp2[1] = temp[6] << FNV128shift;
temp2[0] = temp[5] << FNV128shift; temp2[0] = temp[5] << FNV128shift;
for ( i=0; i<8; ++i ) for ( i=0; i<8; ++i )
temp[i] *= FNV128primeX; temp[i] *= FNV128primeX;
temp[2] += temp2[2]; temp[2] += temp2[2];
INTERNET-DRAFT FNV
temp[1] += temp2[1]; temp[1] += temp2[1];
temp[0] += temp2[0]; temp[0] += temp2[0];
for ( i=7; i>0; --i ) for ( i=7; i>0; --i )
{ {
temp[i-1] += temp[i] >> 16; temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF; temp[i] &= 0xFFFF;
} }
} }
for ( i=0; i<FNV128size/2; ++i ) for ( i=0; i<FNV128size/2; ++i )
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
skipping to change at page 42, line 4 skipping to change at page 43, line 40
{ {
if ( ctx->Computed != FNVcomputed+FNV128state ) if ( ctx->Computed != FNVcomputed+FNV128state )
return fnvStateError; return fnvStateError;
for ( i=0; i<FNV128size/2; ++i ) for ( i=0; i<FNV128size/2; ++i )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
out[15-2*i] = ctx->Hash[i]; out[15-2*i] = ctx->Hash[i];
out[14-2*i] = ctx->Hash[i] >> 8; out[14-2*i] = ctx->Hash[i] >> 8;
#else #else
out[2*i] = ctx->Hash[i]; out[2*i] = ctx->Hash[i];
INTERNET-DRAFT FNV
out[2*i+1] = ctx->Hash[i] >> 8; out[2*i+1] = ctx->Hash[i] >> 8;
#endif #endif
ctx -> Hash[i] = 0; ctx -> Hash[i] = 0;
} }
ctx->Computed = FNVemptied+FNV128state; ctx->Computed = FNVemptied+FNV128state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV128result */ } /* end FNV128result */
#endif /* Have64bitIntegers */ #endif /* Have64bitIntegers */
/******************************************************************** /********************************************************************
* END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
********************************************************************/ ********************************************************************/
#endif /* _FNV128_C_ */ #endif /* _FNV128_C_ */
<CODE ENDS> <CODE ENDS>
INTERNET-DRAFT FNV
6.1.4 FNV256 C Code 6.1.4 FNV256 C Code
The header and C source for 256-bit FNV-1a. The header and C source for 256-bit FNV-1a.
<CODE BEGINS> <CODE BEGINS>
/**************************** FNV256.h **************************/ /**************************** FNV256.h **************************/
/***************** See RFC NNNN for details. ********************/ /***************** See RFC NNNN for details. ********************/
/* /*
* Copyright (c) 2015 IETF Trust and the persons identified as * Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
#ifndef _FNV256_H_ #ifndef _FNV256_H_
#define _FNV256_H_ #define _FNV256_H_
/* /*
* Description: * Description:
* This file provides headers for the 256-bit version of the * This file provides headers for the 256-bit version of the
* FNV-1a non-cryptographic hash algorithm. * FNV-1a non-cryptographic hash algorithm.
*
* >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */
#define FNV_64bitIntegers
/* FNV_64bitIntegers - Define this if your system supports 64-bit
* arithmetic including 32-bit x 32-bit multiplication
* producing a 64-bit product. If undefined, it will be
* assumed that 32-bit arithmetic is supported including
* 16-bit x 16-bit multiplication producing a 32-bit result.
INTERNET-DRAFT FNV
*
* FNV_BigEndian - Define this ONLY if your system uses big
* endian representation AND your FNV hashes need to
* interoperate with little endian systems. If you #define
* this symbol when not needed, it will unnecessarily slow
* down and increase the code size of the FNV functions.
*/ */
#include "FNVconfig.h"
#include <stdint.h> #include <stdint.h>
#define FNV256size (256/8) #define FNV256size (256/8)
/* If you do not have the ISO standard stdint.h header file, then you /* If you do not have the ISO standard stdint.h header file, then you
* must typedef the following types: * must typedef the following types:
* *
* type meaning * type meaning
* uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers)
* uint32_t unsigned 32 bit integer * uint32_t unsigned 32 bit integer
* uint16_t unsigned 16 bit integer * uint16_t unsigned 16 bit integer
skipping to change at page 43, line 41 skipping to change at page 45, line 4
* All FNV functions provided return as integer as follows: * All FNV functions provided return as integer as follows:
* 0 -> success * 0 -> success
* >0 -> error as listed below * >0 -> error as listed below
*/ */
enum { /* success and errors */ enum { /* success and errors */
fnvSuccess = 0, fnvSuccess = 0,
fnvNull, /* Null pointer parameter */ fnvNull, /* Null pointer parameter */
fnvStateError, /* called Input after Result or before Init */ fnvStateError, /* called Input after Result or before Init */
fnvBadParam /* passed a bad parameter */ fnvBadParam /* passed a bad parameter */
}; };
INTERNET-DRAFT FNV
#endif /* _FNV_ErrCodes_ */ #endif /* _FNV_ErrCodes_ */
/* /*
* This structure holds context information for an FNV256 hash * This structure holds context information for an FNV256 hash
*/ */
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
/* version if 64 bit integers supported */ /* version if 64 bit integers supported */
typedef struct FNV256context_s { typedef struct FNV256context_s {
int Computed; /* state */ int Computed; /* state */
uint32_t Hash[FNV256size/4]; uint32_t Hash[FNV256size/4];
} FNV256context; } FNV256context;
#else #else
/* version if 64 bit integers NOT supported */ /* version if 64 bit integers NOT supported */
typedef struct FNV256context_s { typedef struct FNV256context_s {
INTERNET-DRAFT FNV
int Computed; /* state */ int Computed; /* state */
uint16_t Hash[FNV256size/2]; uint16_t Hash[FNV256size/2];
} FNV256context; } FNV256context;
#endif /* FNV_64bitIntegers */ #endif /* FNV_64bitIntegers */
/* /*
* Function Prototypes * Function Prototypes
* FNV256string: hash a zero terminated string not including * FNV256string: hash a zero terminated string not including
* the zero * the zero
skipping to change at page 44, line 28 skipping to change at page 45, line 44
* FNV256initBasis: initializes an FNV256 context with a provided * FNV256initBasis: initializes an FNV256 context with a provided
* basis * basis
* FNV256blockin: hash in a specified length byte vector * FNV256blockin: hash in a specified length byte vector
* FNV256stringin: hash in a zero terminated string not * FNV256stringin: hash in a zero terminated string not
* including the zero * including the zero
* FNV256result: returns the hash value * FNV256result: returns the hash value
* *
* Hash is returned as an array of 8-bit integers * Hash is returned as an array of 8-bit integers
*/ */
#ifdef __cplusplus
extern "C" {
#endif
/* FNV256 */ /* FNV256 */
extern int FNV256string ( const char *in, extern int FNV256string ( const char *in,
uint8_t out[FNV256size] ); uint8_t out[FNV256size] );
extern int FNV256block ( const unsigned char *in, extern int FNV256block ( const void *in,
long int length, long int length,
uint8_t out[FNV256size] ); uint8_t out[FNV256size] );
extern int FNV256init ( FNV256context *); extern int FNV256init ( FNV256context *);
extern int FNV256initBasis ( FNV256context * const, extern int FNV256initBasis ( FNV256context * const,
INTERNET-DRAFT FNV
const uint8_t basis[FNV256size] ); const uint8_t basis[FNV256size] );
extern int FNV256blockin ( FNV256context * const, extern int FNV256blockin ( FNV256context * const,
const unsigned char *in, const void *in,
long int length ); long int length );
extern int FNV256stringin ( FNV256context * const, extern int FNV256stringin ( FNV256context * const,
const char *in ); const char *in );
extern int FNV256result ( FNV256context * const, extern int FNV256result ( FNV256context * const,
uint8_t out[FNV256size] ); uint8_t out[FNV256size] );
#ifdef __cplusplus
}
#endif
#endif /* _FNV256_H_ */ #endif /* _FNV256_H_ */
<CODE ENDS> <CODE ENDS>
<CODE BEGINS> <CODE BEGINS>
/***************************** FNV256.c ****************************/ /***************************** FNV256.c ****************************/
/******************** See RFC NNNN for details *********************/ /******************** See RFC NNNN for details *********************/
/* Copyright (c) 2015 IETF Trust and the persons identified as /* Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights * authors of the code. All rights
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
INTERNET-DRAFT FNV
/* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic
* hash function FNV-1a for 256-bit hashes. * hash function FNV-1a for 256-bit hashes.
*/ */
#ifndef _FNV256_C_ #ifndef _FNV256_C_
#define _FNV256_C_ #define _FNV256_C_
#include "fnv-private.h" #include "fnv-private.h"
#include "FNV256.h" #include "FNV256.h"
/* common code for 64 and 32 bit modes */ /* common code for 64 and 32 bit modes */
/* FNV256 hash a null terminated string (64/32 bit) /* FNV256 hash a null terminated string (64/32 bit)
********************************************************************/ ********************************************************************/
int FNV256string ( const char *in, uint8_t out[FNV256size] ) int FNV256string ( const char *in, uint8_t out[FNV256size] )
{ {
FNV256context ctx; FNV256context ctx;
int err; int err;
if ( (err = FNV256init ( &ctx )) ) if ( (err = FNV256init ( &ctx )) != fnvSuccess )
return err; return err;
if ( (err = FNV256stringin ( &ctx, in )) ) if ( (err = FNV256stringin ( &ctx, in )) != fnvSuccess )
return err; return err;
return FNV256result ( &ctx, out ); return FNV256result ( &ctx, out );
} /* end FNV256string */ } /* end FNV256string */
INTERNET-DRAFT FNV
/* FNV256 hash a counted block (64/32 bit) /* FNV256 hash a counted block (64/32 bit)
********************************************************************/ ********************************************************************/
int FNV256block ( const unsigned char *in, int FNV256block ( const void *in,
long int length, long int length,
uint8_t out[FNV256size] ) uint8_t out[FNV256size] )
{ {
FNV256context ctx; FNV256context ctx;
int err; int err;
if ( (err = FNV256init ( &ctx )) ) if ( (err = FNV256init ( &ctx )) != fnvSuccess )
return err; return err;
if ( (err = FNV256blockin ( &ctx, in, length)) ) if ( (err = FNV256blockin ( &ctx, in, length)) != fnvSuccess )
return err; return err;
return FNV256result ( &ctx, out ); return FNV256result ( &ctx, out );
} /* end FNV256block */ } /* end FNV256block */
/******************************************************************** /********************************************************************
* START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
********************************************************************/ ********************************************************************/
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
/* 256 bit FNV_prime = 2^168 + 2^8 + 0x63 */
/* 0x0000000000000000 0000010000000000 /* 0x0000000000000000 0000010000000000
0000000000000000 0000000000000163 */ 0000000000000000 0000000000000163 */
INTERNET-DRAFT FNV
#define FNV256primeX 0x0163 #define FNV256primeX 0x0163
#define FNV256shift 8 #define FNV256shift 8
/* 0xDD268DBCAAC55036 2D98C384C4E576CC /* 0xDD268DBCAAC55036 2D98C384C4E576CC
C8B1536847B6BBB3 1023B4C8CAEE0535 */ C8B1536847B6BBB3 1023B4C8CAEE0535 */
uint32_t FNV256basis[FNV256size/4] = { uint32_t FNV256basis[FNV256size/4] = {
0xDD268DBC, 0xAAC55036, 0x2D98C384, 0xC4E576CC, 0xDD268DBC, 0xAAC55036, 0x2D98C384, 0xC4E576CC,
0xC8B15368, 0x47B6BBB3, 0x1023B4C8, 0xCAEE0535 }; 0xC8B15368, 0x47B6BBB3, 0x1023B4C8, 0xCAEE0535 };
/******************************************************************** /********************************************************************
skipping to change at page 46, line 32 skipping to change at page 48, line 4
********************************************************************/ ********************************************************************/
int FNV256init ( FNV256context *ctx ) int FNV256init ( FNV256context *ctx )
{ {
int i; int i;
if ( ctx ) if ( ctx )
{ {
for ( i=0; i<FNV256size/4; ++i ) for ( i=0; i<FNV256size/4; ++i )
ctx->Hash[i] = FNV256basis[i]; ctx->Hash[i] = FNV256basis[i];
ctx->Computed = FNVinited+FNV256state; ctx->Computed = FNVinited+FNV256state;
INTERNET-DRAFT FNV
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV256init */ } /* end FNV256init */
/* initialize context with a provided basis (64 bit) /* initialize context with a provided basis (64 bit)
********************************************************************/ ********************************************************************/
int FNV256initBasis ( FNV256context* const ctx, int FNV256initBasis ( FNV256context* const ctx,
const uint8_t basis[FNV256size] ) const uint8_t basis[FNV256size] )
{ {
int i; int i;
uint8_t *ui8p; const uint8_t *ui8p;
uint32_t temp; uint32_t temp;
if ( ctx ) if ( ctx )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
ui8p = basis; ui8p = basis;
for ( i=0; i < FNV256size/4; ++i ) for ( i=0; i < FNV256size/4; ++i )
{ {
temp = (*ui8p++)<<8; temp = (*ui8p++)<<8;
temp = (temp + *ui8p++)<<8; temp = (temp + *ui8p++)<<8;
temp = (temp + *ui8p++)<<8; temp = (temp + *ui8p++)<<8;
ctx->Hash[i] = temp + *ui8p; ctx->Hash[i] = temp + *ui8p;
} }
INTERNET-DRAFT FNV
#else #else
ui8p = basis + (FNV256size/4 - 1); ui8p = basis + (FNV256size/4 - 1);
for ( i=0; i < FNV256size/4; ++i ) for ( i=0; i < FNV256size/4; ++i )
{ {
temp = (*ui8p--)<<8; temp = (*ui8p--)<<8;
temp = (temp + *ui8p--)<<8; temp = (temp + *ui8p--)<<8;
temp = (temp + *ui8p--)<<8; temp = (temp + *ui8p--)<<8;
ctx->Hash[i] = temp + *ui8p; ctx->Hash[i] = temp + *ui8p;
} }
#endif #endif
ctx->Computed = FNVinited+FNV256state; ctx->Computed = FNVinited+FNV256state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV256initBasis */ } /* end FNV256initBasis */
/* hash in a counted block (64 bit) /* hash in a counted block (64 bit)
********************************************************************/ ********************************************************************/
int FNV256blockin ( FNV256context *ctx, int FNV256blockin ( FNV256context *ctx,
const unsigned char *in, const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint64_t temp[FNV256size/4]; uint64_t temp[FNV256size/4];
uint64_t temp2[3]; uint64_t temp2[3];
INTERNET-DRAFT FNV
int i; int i;
if ( ctx && in ) if ( ctx && in )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV256state: case FNVinited+FNV256state:
ctx->Computed = FNVcomputed+FNV256state; ctx->Computed = FNVcomputed+FNV256state;
skipping to change at page 48, line 4 skipping to change at page 49, line 32
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
for ( ; length > 0; length-- ) for ( ; length > 0; length-- )
{ {
/* temp = FNV256prime * ( temp ^ *in++ ); */ /* temp = FNV256prime * ( temp ^ *in++ ); */
temp[7] ^= *in++; temp[7] ^= *in++;
temp2[2] = temp[7] << FNV256shift; temp2[2] = temp[7] << FNV256shift;
temp2[1] = temp[6] << FNV256shift; temp2[1] = temp[6] << FNV256shift;
temp2[0] = temp[5] << FNV256shift; temp2[0] = temp[5] << FNV256shift;
for ( i=0; i<FNV256size/4; ++i ) for ( i=0; i<FNV256size/4; ++i )
temp[i] *= FNV256primeX; temp[i] *= FNV256primeX;
INTERNET-DRAFT FNV
temp[2] += temp2[2]; temp[2] += temp2[2];
temp[1] += temp2[1]; temp[1] += temp2[1];
temp[0] += temp2[0]; temp[0] += temp2[0];
for ( i=FNV256size/4-1; i>0; --i ) for ( i=FNV256size/4-1; i>0; --i )
{ {
temp[i-1] += temp[i] >> 16; temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF; temp[i] &= 0xFFFF;
} }
} }
for ( i=0; i<FNV256size/4; ++i ) for ( i=0; i<FNV256size/4; ++i )
skipping to change at page 48, line 31 skipping to change at page 50, line 4
} /* end FNV256input */ } /* end FNV256input */
/* hash in a string (64 bit) /* hash in a string (64 bit)
********************************************************************/ ********************************************************************/
int FNV256stringin ( FNV256context *ctx, const char *in ) int FNV256stringin ( FNV256context *ctx, const char *in )
{ {
uint64_t temp[FNV256size/4]; uint64_t temp[FNV256size/4];
uint64_t temp2[3]; uint64_t temp2[3];
int i; int i;
uint8_t ch; uint8_t ch;
INTERNET-DRAFT FNV
if ( ctx && in ) if ( ctx && in )
{ {
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV256state: case FNVinited+FNV256state:
ctx->Computed = FNVcomputed+FNV256state; ctx->Computed = FNVcomputed+FNV256state;
case FNVcomputed+FNV256state: case FNVcomputed+FNV256state:
break; break;
default: default:
skipping to change at page 49, line 4 skipping to change at page 50, line 31
/* temp = FNV256prime * ( temp ^ ch ); */ /* temp = FNV256prime * ( temp ^ ch ); */
temp[7] ^= ch; temp[7] ^= ch;
temp2[2] = temp[7] << FNV256shift; temp2[2] = temp[7] << FNV256shift;
temp2[1] = temp[6] << FNV256shift; temp2[1] = temp[6] << FNV256shift;
temp2[0] = temp[5] << FNV256shift; temp2[0] = temp[5] << FNV256shift;
for ( i=0; i<FNV256size/4; ++i ) for ( i=0; i<FNV256size/4; ++i )
temp[i] *= FNV256primeX; temp[i] *= FNV256primeX;
temp[2] += temp2[2]; temp[2] += temp2[2];
temp[1] += temp2[1]; temp[1] += temp2[1];
temp[0] += temp2[0]; temp[0] += temp2[0];
INTERNET-DRAFT FNV
for ( i=FNV256size/4-1; i>0; --i ) for ( i=FNV256size/4-1; i>0; --i )
{ {
temp[i-1] += temp[i] >> 16; temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF; temp[i] &= 0xFFFF;
} }
} }
for ( i=0; i<FNV256size/4; ++i ) for ( i=0; i<FNV256size/4; ++i )
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
return fnvSuccess; return fnvSuccess;
} }
skipping to change at page 49, line 32 skipping to change at page 51, line 4
int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] ) int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] )
{ {
int i; int i;
if ( ctx && out ) if ( ctx && out )
{ {
if ( ctx->Computed != FNVcomputed+FNV256state ) if ( ctx->Computed != FNVcomputed+FNV256state )
return fnvStateError; return fnvStateError;
for ( i=0; i<FNV256size/4; ++i ) for ( i=0; i<FNV256size/4; ++i )
{ {
INTERNET-DRAFT FNV
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
out[31-4*i] = ctx->Hash[i]; out[31-4*i] = ctx->Hash[i];
out[31-4*i] = ctx->Hash[i] >> 8; out[31-4*i] = ctx->Hash[i] >> 8;
out[31-4*i] = ctx->Hash[i] >> 16; out[31-4*i] = ctx->Hash[i] >> 16;
out[31-4*i] = ctx->Hash[i] >> 24; out[31-4*i] = ctx->Hash[i] >> 24;
#else #else
out[4*i] = ctx->Hash[i]; out[4*i] = ctx->Hash[i];
out[4*i+1] = ctx->Hash[i] >> 8; out[4*i+1] = ctx->Hash[i] >> 8;
out[4*i+2] = ctx->Hash[i] >> 16; out[4*i+2] = ctx->Hash[i] >> 16;
out[4*i+3] = ctx->Hash[i] >> 24; out[4*i+3] = ctx->Hash[i] >> 24;
skipping to change at page 50, line 4 skipping to change at page 51, line 32
} }
return fnvNull; return fnvNull;
} /* end FNV256result */ } /* end FNV256result */
/****************************************************************** /******************************************************************
* END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
******************************************************************/ ******************************************************************/
#else /* FNV_64bitIntegers */ #else /* FNV_64bitIntegers */
/****************************************************************** /******************************************************************
* START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
INTERNET-DRAFT FNV
******************************************************************/ ******************************************************************/
/* version for when you only have 32-bit arithmetic /* version for when you only have 32-bit arithmetic
********************************************************************/ ********************************************************************/
/* 256 bit FNV_prime = 2^168 + 2^8 + 0x63 */
/* 0x00000000 00000000 00000100 00000000 /* 0x00000000 00000000 00000100 00000000
00000000 00000000 00000000 00000163 */ 00000000 00000000 00000000 00000163 */
#define FNV256primeX 0x0163 #define FNV256primeX 0x0163
#define FNV256shift 8 #define FNV256shift 8
/* 0xDD268DBCAAC55036 2D98C384C4E576CC /* 0xDD268DBCAAC55036 2D98C384C4E576CC
C8B1536847B6BBB3 1023B4C8CAEE0535 */ C8B1536847B6BBB3 1023B4C8CAEE0535 */
uint16_t FNV256basis[FNV256size/2] = { uint16_t FNV256basis[FNV256size/2] = {
0xDD26, 0x8DBC, 0xAAC5, 0x5036, 0xDD26, 0x8DBC, 0xAAC5, 0x5036,
0x2D98, 0xC384, 0xC4E5, 0x76CC, 0x2D98, 0xC384, 0xC4E5, 0x76CC,
0xC8B1, 0x5368, 0x47B6, 0xBBB3, 0xC8B1, 0x5368, 0x47B6, 0xBBB3,
0x1023, 0xB4C8, 0xCAEE, 0x0535 }; 0x1023, 0xB4C8, 0xCAEE, 0x0535 };
/******************************************************************** /********************************************************************
* Set of init, input, and output functions bel ow * * Set of init, input, and output functions below *
* to incrementally compute FNV256 * * to incrementally compute FNV256 *
********************************************************************/ ********************************************************************/
/* initialize context (32 bit) /* initialize context (32 bit)
INTERNET-DRAFT FNV
********************************************************************/ ********************************************************************/
int FNV256init ( FNV256context *ctx ) int FNV256init ( FNV256context *ctx )
{ {
int i; int i;
if ( ctx ) if ( ctx )
{ {
for ( i=0; i<FNV256size/2; ++i ) for ( i=0; i<FNV256size/2; ++i )
ctx->Hash[i] = FNV256basis[i]; ctx->Hash[i] = FNV256basis[i];
ctx->Computed = FNVinited+FNV256state; ctx->Computed = FNVinited+FNV256state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV256init */ } /* end FNV256init */
/* initialize context with a provided basis (32 bit) /* initialize context with a provided basis (32 bit)
********************************************************************/ ********************************************************************/
int FNV256initBasis ( FNV128context *ctx, int FNV256initBasis ( FNV256context *ctx,
const unint8_t basis[FNV256size) ) const uint8_t basis[FNV256size] )
{ {
int i; int i;
unit8_t *ui8p; const uint8_t *ui8p;
uint32_t temp; uint32_t temp;
if ( ctx ) if ( ctx )
{ {
INTERNET-DRAFT FNV
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
ui8p = basis; ui8p = basis;
for ( i=0; i < FNV256size/2; ++i ) for ( i=0; i < FNV256size/2; ++i )
{ {
temp = *ui8p++; temp = *ui8p++;
ctx->Hash[i] = temp<<8 + (*ui8p++); ctx->Hash[i] = ( temp<<8 ) + (*ui8p++);
} }
#else #else
ui8p = basis + FNV256size/2 -1; ui8p = basis + FNV256size/2 -1;
for ( i=0; i < FNV256size/2; ++i ) for ( i=0; i < FNV256size/2; ++i )
{ {
temp = *ui8p--; temp = *ui8p--;
ctx->Hash[i] = temp<<8 + (*ui8p--); ctx->Hash[i] = ( temp<<8 ) + (*ui8p--);
} }
#endif #endif
ctx->Computed = FNVinited+FNV256state; ctx->Computed = FNVinited+FNV256state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV256initBasis */ } /* end FNV256initBasis */
/* hash in a counted block (32 bit) /* hash in a counted block (32 bit)
*******************************************************************/ *******************************************************************/
int FNV256blockin ( FNV256context *ctx, int FNV256blockin ( FNV256context *ctx,
const unsigned char *in, INTERNET-DRAFT FNV
const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint32_t temp[FNV256size/2]; uint32_t temp[FNV256size/2];
uint32_t temp2[6]; uint32_t temp2[6];
int i; int i;
if ( ctx && in ) if ( ctx && in )
{ {
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
skipping to change at page 52, line 4 skipping to change at page 53, line 33
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( i=0; i<FNV256size/2; ++i ) for ( i=0; i<FNV256size/2; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
for ( ; length > 0; length-- ) for ( ; length > 0; length-- )
{ {
/* temp = FNV256prime * ( temp ^ *in++ ); */ /* temp = FNV256prime * ( temp ^ *in++ ); */
temp[15] ^= *in++; temp[15] ^= *in++;
INTERNET-DRAFT FNV
for ( i=0; i<6; ++i ) for ( i=0; i<6; ++i )
temp2[i] = temp[10+i] << FNV256shift; temp2[i] = temp[10+i] << FNV256shift;
for ( i=0; i<FNV256size/2; ++i ) for ( i=0; i<FNV256size/2; ++i )
temp[i] *= FNV256primeX; temp[i] *= FNV256primeX;
for ( i=0; i<6; ++i ) for ( i=0; i<6; ++i )
temp[10+i] += temp2[i]; temp[10+i] += temp2[i];
for ( i=15; i>0; --i ) for ( i=15; i>0; --i )
{ {
temp[i-1] += temp[i] >> 16; temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF; temp[i] &= 0xFFFF;
skipping to change at page 52, line 30 skipping to change at page 54, line 4
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV256blockin */ } /* end FNV256blockin */
/* hash in a string (32 bit) /* hash in a string (32 bit)
*******************************************************************/ *******************************************************************/
int FNV256stringin ( FNV256context *ctx, const char *in ) int FNV256stringin ( FNV256context *ctx, const char *in )
{ {
INTERNET-DRAFT FNV
uint32_t temp[FNV256size/2]; uint32_t temp[FNV256size/2];
uint32_t temp2[6]; uint32_t temp2[6];
int i; int i;
uint8_t ch; uint8_t ch;
if ( ctx && in ) if ( ctx && in )
{ {
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV256state: case FNVinited+FNV256state:
ctx->Computed = FNVcomputed+FNV256state; ctx->Computed = FNVcomputed+FNV256state;
case FNVcomputed+FNV256state: case FNVcomputed+FNV256state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( i=0; i<FNV256size/2; ++i ) for ( i=0; i<FNV256size/2; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
while ( ch = (uint8_t)*in++ ) while ( ( ch = (uint8_t)*in++ ) != 0)
{ {
/* temp = FNV256prime * ( temp ^ *in++ ); */ /* temp = FNV256prime * ( temp ^ *in++ ); */
temp[15] ^= ch; temp[15] ^= ch;
for ( i=0; i<6; ++i ) for ( i=0; i<6; ++i )
temp2[i] = temp[10+i] << FNV256shift; temp2[i] = temp[10+i] << FNV256shift;
for ( i=0; i<FNV256size/2; ++i ) for ( i=0; i<FNV256size/2; ++i )
temp[i] *= FNV256primeX; temp[i] *= FNV256primeX;
for ( i=0; i<6; ++i ) for ( i=0; i<6; ++i )
INTERNET-DRAFT FNV
temp[10+i] += temp2[i]; temp[10+i] += temp2[i];
for ( i=15; i>0; --i ) for ( i=15; i>0; --i )
{ {
temp[i-1] += temp[i] >> 16; temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF; temp[i] &= 0xFFFF;
} }
} }
for ( i=0; i<FNV256size/2; ++i ) for ( i=0; i<FNV256size/2; ++i )
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV256stringin */ } /* end FNV256stringin */
/* return hash (32 bit) /* return hash (32 bit)
********************************************************************/ ********************************************************************/
int FNV256result ( FNV256context *ctx, unit8_t out[FNV256size] ) int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] )
{ {
int i; int i;
if ( ctx && out ) if ( ctx && out )
{ {
if ( ctx->Computed != FNVcomputed+FNV256state ) if ( ctx->Computed != FNVcomputed+FNV256state )
INTERNET-DRAFT FNV
return fnvStateError; return fnvStateError;
for ( i=0; i<FNV256size/2; ++i ) for ( i=0; i<FNV256size/2; ++i )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
out[31-2*i] = ctx->Hash[i]; out[31-2*i] = ctx->Hash[i];
out[30-2*i] = ctx->Hash[i] >> 8; out[30-2*i] = ctx->Hash[i] >> 8;
#else #else
out[2*i] = ctx->Hash[i]; out[2*i] = ctx->Hash[i];
out[2*i+1] = ctx->Hash[i] >> 8; out[2*i+1] = ctx->Hash[i] >> 8;
#endif #endif
skipping to change at page 54, line 5 skipping to change at page 55, line 33
} /* end FNV256result */ } /* end FNV256result */
#endif /* Have64bitIntegers */ #endif /* Have64bitIntegers */
/******************************************************************** /********************************************************************
* END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
********************************************************************/ ********************************************************************/
#endif /* _FNV256_C_ */ #endif /* _FNV256_C_ */
<CODE ENDS> <CODE ENDS>
INTERNET-DRAFT FNV
6.1.5 FNV512 C Code 6.1.5 FNV512 C Code
The header and C source for 512-bit FNV-1a. The header and C source for 512-bit FNV-1a.
<CODE BEGINS> <CODE BEGINS>
/**************************** FNV512.h **************************/ /**************************** FNV512.h **************************/
/***************** See RFC NNNN for details. ********************/ /***************** See RFC NNNN for details. ********************/
/* /*
* Copyright (c) 2015 IETF Trust and the persons identified as * Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
#ifndef _FNV512_H_ #ifndef _FNV512_H_
#define _FNV512_H_ #define _FNV512_H_
/* /*
* Description: * Description:
* This file provides headers for the 512-bit version of the * This file provides headers for the 512-bit version of the
* FNV-1a non-cryptographic hash algorithm. * FNV-1a non-cryptographic hash algorithm.
* */
* >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */
#define FNV_64bitIntegers INTERNET-DRAFT FNV
/* FNV_64bitIntegers - Define this if your system supports 64-bit #include "FNVconfig.h"
* arithmetic including 32-bit x 32-bit multiplication
* producing a 64-bit product. If undefined, it will be
* assumed that 32-bit arithmetic is supported including
* 16-bit x 16-bit multiplication producing a 32-bit result.
*
* FNV_BigEndian - Define this ONLY if your system uses big
* endian representation AND your FNV hashes need to
* interoperate with little endian systems. If you #define
* this symbol when not needed, it will unnecessarily slow
* down and increase the code size of the FNV functions.
*/
#include <stdint.h> #include <stdint.h>
#define FNV512size (512/8) #define FNV512size (512/8)
/* If you do not have the ISO standard stdint.h header file, then you /* If you do not have the ISO standard stdint.h header file, then you
* must typedef the following types: * must typedef the following types:
* *
* type meaning * type meaning
* uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers)
* uint32_t unsigned 32 bit integer * uint32_t unsigned 32 bit integer
* uint16_t unsigned 16 bit integer * uint16_t unsigned 16 bit integer
* uint8_t unsigned 8 bit integer (i.e., unsigned char) * uint8_t unsigned 8 bit integer (i.e., unsigned char)
*/ */
INTERNET-DRAFT FNV
#ifndef _FNV_ErrCodes_ #ifndef _FNV_ErrCodes_
#define _FNV_ErrCodes_ #define _FNV_ErrCodes_
/********************************************************************* /*********************************************************************
* All FNV functions provided return as integer as follows: * All FNV functions provided return as integer as follows:
* 0 -> success * 0 -> success
* >0 -> error as listed below * >0 -> error as listed below
*/ */
enum { /* success and errors */ enum { /* success and errors */
fnvSuccess = 0, fnvSuccess = 0,
fnvNull, /* Null pointer parameter */ fnvNull, /* Null pointer parameter */
skipping to change at page 55, line 41 skipping to change at page 57, line 4
#else #else
/* version if 64 bit integers NOT supported */ /* version if 64 bit integers NOT supported */
typedef struct FNV512context_s { typedef struct FNV512context_s {
int Computed; /* state */ int Computed; /* state */
uint16_t Hash[FNV512size/2]; uint16_t Hash[FNV512size/2];
} FNV512context; } FNV512context;
#endif /* FNV_64bitIntegers */ #endif /* FNV_64bitIntegers */
INTERNET-DRAFT FNV
/* /*
* Function Prototypes * Function Prototypes
* FNV512string: hash a zero terminated string not including * FNV512string: hash a zero terminated string not including
* the terminating zero * the terminating zero
* FNV512block: FNV512 hash a specified length byte vector * FNV512block: FNV512 hash a specified length byte vector
* FNV512init: initializes an FNV512 context * FNV512init: initializes an FNV512 context
* FNV512initBasis: initializes an FNV512 context with a * FNV512initBasis: initializes an FNV512 context with a
* provided basis * provided basis
* FNV512blockin: hash in a specified length byte vector * FNV512blockin: hash in a specified length byte vector
* FNV512stringin: hash in a zero terminated string not * FNV512stringin: hash in a zero terminated string not
* including the zero * including the zero
* FNV512result: returns the hash value * FNV512result: returns the hash value
* *
* Hash is returned as an array of 8-bit integers * Hash is returned as an array of 8-bit integers
*/ */
INTERNET-DRAFT FNV #ifdef __cplusplus
extern "C" {
#endif
/* FNV512 */ /* FNV512 */
extern int FNV512string ( const char *in, extern int FNV512string ( const char *in,
uint8_t out[FNV512size] ); uint8_t out[FNV512size] );
extern int FNV512block ( const unsigned char *in, extern int FNV512block ( const void *in,
long int length, long int length,
uint8_t out[FNV512size] ); uint8_t out[FNV512size] );
extern int FNV512init ( FNV512context *); extern int FNV512init ( FNV512context *);
extern int FNV512initBasis ( FNV512context * const, extern int FNV512initBasis ( FNV512context * const,
const uint8_t basis[FNV512size] ); const uint8_t basis[FNV512size] );
extern int FNV512blockin ( FNV512context *, extern int FNV512blockin ( FNV512context *,
const unsigned char *in, const void *in,
long int length ); long int length );
extern int FNV512stringin ( FNV512context *, extern int FNV512stringin ( FNV512context *,
const char *in ); const char *in );
extern int FNV512result ( FNV512context *, extern int FNV512result ( FNV512context *,
uint8_t out[FNV512size] ); uint8_t out[FNV512size] );
#ifdef __cplusplus
}
#endif
#endif /* _FNV512_H_ */ #endif /* _FNV512_H_ */
<CODE ENDS> <CODE ENDS>
<CODE BEGINS> <CODE BEGINS>
/***************************** FNV512.c ****************************/ /***************************** FNV512.c ****************************/
/******************** See RFC NNNN for details *********************/ /******************** See RFC NNNN for details *********************/
/* Copyright (c) 2015 IETF Trust and the persons identified as /* Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights * authors of the code. All rights
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
INTERNET-DRAFT FNV
*/ */
/* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic
* hash function FNV-1a for 512-bit hashes. * hash function FNV-1a for 512-bit hashes.
*/ */
#ifndef _FNV512_C_ #ifndef _FNV512_C_
#define _FNV512_C_ #define _FNV512_C_
#include "fnv-private.h" #include "fnv-private.h"
skipping to change at page 56, line 54 skipping to change at page 58, line 28
/* common code for 64 and 32 bit modes */ /* common code for 64 and 32 bit modes */
/* FNV512 hash a null terminated string (64/32 bit) /* FNV512 hash a null terminated string (64/32 bit)
********************************************************************/ ********************************************************************/
int FNV512string ( const char *in, uint8_t out[FNV512size] ) int FNV512string ( const char *in, uint8_t out[FNV512size] )
{ {
FNV512context ctx; FNV512context ctx;
int err; int err;
if ( (err = FNV512init ( &ctx )) ) if ( (err = FNV512init ( &ctx )) != fnvSuccess )
return err; return err;
if ( (err = FNV512stringin ( &ctx, in )) ) if ( (err = FNV512stringin ( &ctx, in )) != fnvSuccess )
INTERNET-DRAFT FNV
return err; return err;
return FNV512result ( &ctx, out ); return FNV512result ( &ctx, out );
} /* end FNV512string */ } /* end FNV512string */
/* FNV512 hash a counted block (64/32 bit) /* FNV512 hash a counted block (64/32 bit)
********************************************************************/ ********************************************************************/
int FNV512block ( const unsigned char *in, int FNV512block ( const void *in,
long int length, long int length,
uint8_t out[FNV512size] ) uint8_t out[FNV512size] )
{ {
FNV512context ctx; FNV512context ctx;
int err; int err;
if ( (err = FNV512init ( &ctx )) ) if ( (err = FNV512init ( &ctx )) != fnvSuccess )
return err; return err;
if ( (err = FNV512blockin ( &ctx, in, length)) ) if ( (err = FNV512blockin ( &ctx, in, length)) != fnvSuccess )
return err; return err;
return FNV512result ( &ctx, out ); return FNV512result ( &ctx, out );
} /* end FNV512block */ } /* end FNV512block */
/******************************************************************** /********************************************************************
* START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
********************************************************************/ ********************************************************************/
#ifdef Have64bitIntegers #ifdef Have64bitIntegers
INTERNET-DRAFT FNV
/* 0x0000000000000000 0000000000000000 /*
512 bit FNV_prime = 2^344 + 2^8 + 0x57 =
0x0000000000000000 0000000000000000
0000000001000000 0000000000000000 0000000001000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000157 */ 0000000000000000 0000000000000157 */
#define FNV512primeX 0x0157 #define FNV512primeX 0x0157
#define FNV512shift 24 #define FNV512shift 24
/* 0xB86DB0B1171F4416 DCA1E50F309990AC /* 0xB86DB0B1171F4416 DCA1E50F309990AC
AC87D059C9000000 0000000000000D21 AC87D059C9000000 0000000000000D21
E948F68A34C192F6 2EA79BC942DBE7CE E948F68A34C192F6 2EA79BC942DBE7CE
182036415F56E34B AC982AAC4AFE9FD9 */ 182036415F56E34B AC982AAC4AFE9FD9 */
skipping to change at page 57, line 42 skipping to change at page 59, line 19
0000000001000000 0000000000000000 0000000001000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000157 */ 0000000000000000 0000000000000157 */
#define FNV512primeX 0x0157 #define FNV512primeX 0x0157
#define FNV512shift 24 #define FNV512shift 24
/* 0xB86DB0B1171F4416 DCA1E50F309990AC /* 0xB86DB0B1171F4416 DCA1E50F309990AC
AC87D059C9000000 0000000000000D21 AC87D059C9000000 0000000000000D21
E948F68A34C192F6 2EA79BC942DBE7CE E948F68A34C192F6 2EA79BC942DBE7CE
182036415F56E34B AC982AAC4AFE9FD9 */ 182036415F56E34B AC982AAC4AFE9FD9 */
uint32_t FNV512basis[FNV512size/4] = { uint32_t FNV512basis[FNV512size/4] = {
0xB86DB0B1, 0x171F4416, 0xDCA1E50F, 0x209990AC, 0xB86DB0B1, 0x171F4416, 0xDCA1E50F, 0x209990AC,
0xAC87D059, 0x9C000000, 0x00000000, 0x00000D21, 0xAC87D059, 0x9C000000, 0x00000000, 0x00000D21,
0xE948F68A, 0x34C192F6, 0x2EA79BC9, 0x42DBE7CE, 0xE948F68A, 0x34C192F6, 0x2EA79BC9, 0x42DBE7CE,
0x18203641, 0x5F56E34B, 0xAC982AAC, 0x4AFE9FD9 }; 0x18203641, 0x5F56E34B, 0xAC982AAC, 0x4AFE9FD9 };
/******************************************************************** /********************************************************************
* Set of init, input, and output functions below * * Set of init, input, and output functions below *
* to incrementally compute FNV512 * * to incrementally compute FNV512 *
********************************************************************/ ********************************************************************/
/* initialize context (64 bit) /* initialize context (64 bit)
********************************************************************/ ********************************************************************/
INTERNET-DRAFT FNV
int FNV512init ( FNV512context *ctx ) int FNV512init ( FNV512context *ctx )
{ {
if ( ctx ) if ( ctx )
{ {
for ( i=0; i<FNV512size/4; ++i ) for ( i=0; i<FNV512size/4; ++i )
ctx->Hash[i] = FNV512basis[i]; ctx->Hash[i] = FNV512basis[i];
ctx->Computed = FNVinited+FNV512state; ctx->Computed = FNVinited+FNV512state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV512init */ } /* end FNV512init */
/* initialize context with a provided basis (64 bit) /* initialize context with a provided basis (64 bit)
********************************************************************/ ********************************************************************/
int FNV512initBasis ( FNV512context* const ctx, int FNV512initBasis ( FNV512context* const ctx,
const uint8_t basis[FNV512size] ) const uint8_t basis[FNV512size] )
{ {
int i; int i;
uint8_t *ui8p; const uint8_t *ui8p;
uint32_t temp; uint32_t temp;
if ( ctx ) if ( ctx )
{ {
INTERNET-DRAFT FNV
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
ui8p = basis; ui8p = basis;
for ( i=0; i < FNV512size/4; ++i ) for ( i=0; i < FNV512size/4; ++i )
{ {
temp = (*ui8p++)<<8; temp = (*ui8p++)<<8;
temp = (temp + *ui8p++)<<8; temp = (temp + *ui8p++)<<8;
temp = (temp + *ui8p++)<<8; temp = (temp + *ui8p++)<<8;
ctx->Hash[i] = temp + *ui8p; ctx->Hash[i] = temp + *ui8p;
} }
#else #else
skipping to change at page 59, line 4 skipping to change at page 60, line 34
} }
#endif #endif
ctx->Computed = FNVinited+FNV512state; ctx->Computed = FNVinited+FNV512state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV512initBasis */ } /* end FNV512initBasis */
/* hash in a counted block (64 bit) /* hash in a counted block (64 bit)
********************************************************************/ ********************************************************************/
INTERNET-DRAFT FNV
int FNV512blockin ( FNV512context *ctx, int FNV512blockin ( FNV512context *ctx,
const unsigned char *in, const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint64_t temp[FNV512size/4]; uint64_t temp[FNV512size/4];
uint64_t temp2[3]; uint64_t temp2[3];
if ( ctx && in ) if ( ctx && in )
{ {
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV512state: case FNVinited+FNV512state:
ctx->Computed = FNVcomputed+FNV128state; ctx->Computed = FNVcomputed+FNV128state;
case FNVcomputed+FNV512state: case FNVcomputed+FNV512state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
for ( i=0; i<FNV512size/4; ++i ) for ( i=0; i<FNV512size/4; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
INTERNET-DRAFT FNV
for ( ; length > 0; length-- ) for ( ; length > 0; length-- )
{ {
/* temp = FNV512prime * ( temp ^ *in++ ); */ /* temp = FNV512prime * ( temp ^ *in++ ); */
temp[7] ^= *in++; temp[7] ^= *in++;
temp2[2] = temp[7] << FNV512shift; temp2[2] = temp[7] << FNV512shift;
temp2[1] = temp[6] << FNV512shift; temp2[1] = temp[6] << FNV512shift;
temp2[0] = temp[5] << FNV512shift; temp2[0] = temp[5] << FNV512shift;
for ( i=0; i<FNV512size/4; ++i ) for ( i=0; i<FNV512size/4; ++i )
temp[i] *= FNV512primeX; temp[i] *= FNV512primeX;
temp[2] += temp2[2]; temp[2] += temp2[2];
skipping to change at page 60, line 4 skipping to change at page 61, line 35
for ( i=0; i<FNV512size/4; ++i ) for ( i=0; i<FNV512size/4; ++i )
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV512input */ } /* end FNV512input */
/* hash in a string (64 bit) /* hash in a string (64 bit)
********************************************************************/ ********************************************************************/
inf FNV512stringin ( FNV512context *ctx, const char *in ) inf FNV512stringin ( FNV512context *ctx, const char *in )
INTERNET-DRAFT FNV
{ {
uint64_t temp[FNV512size/4]; uint64_t temp[FNV512size/4];
uint64_t temp2[2]; uint64_t temp2[2];
int i; int i;
uint8_t ch; uint8_t ch;
if ( ctx && in ) if ( ctx && in )
{ {
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
skipping to change at page 60, line 28 skipping to change at page 62, line 4
case FNVcomputed+FNV512state: case FNVcomputed+FNV512state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
for ( i=0; i<FNV512size/4; ++i ) for ( i=0; i<FNV512size/4; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
while ( ch = (uint8_t)*in++ ) while ( ch = (uint8_t)*in++ )
{ {
/* temp = FNV512prime * ( temp ^ ch ); */ /* temp = FNV512prime * ( temp ^ ch ); */
INTERNET-DRAFT FNV
temp[7] ^= ch; temp[7] ^= ch;
temp2[2] = temp[7] << FNV128shift; temp2[2] = temp[7] << FNV128shift;
temp2[1] = temp[6] << FNV128shift; temp2[1] = temp[6] << FNV128shift;
temp2[0] = temp[5] << FNV128shift; temp2[0] = temp[5] << FNV128shift;
for ( i=0; i<FNV512size/4; ++i ) for ( i=0; i<FNV512size/4; ++i )
temp[i] *= FNV512prime; temp[i] *= FNV512prime;
temp[2] += temp2[2]; temp[2] += temp2[2];
temp[1] += temp2[1]; temp[1] += temp2[1];
temp[0] += temp2[0]; temp[0] += temp2[0];
for ( i=FNVsize512/4-1; i>0; --i ) for ( i=FNVsize512/4-1; i>0; --i )
skipping to change at page 61, line 4 skipping to change at page 62, line 35
} }
return fnvNull; return fnvNull;
} /* end FNV512stringin */ } /* end FNV512stringin */
/* return hash (64 bit) /* return hash (64 bit)
********************************************************************/ ********************************************************************/
int FNV512result ( FNV512context *ctx, uint8_t out[FNV512size] ) int FNV512result ( FNV512context *ctx, uint8_t out[FNV512size] )
{ {
if ( ctx && out ) if ( ctx && out )
{ {
INTERNET-DRAFT FNV
if ( ctx->Computed != FNVcomputed+FNV512state ) if ( ctx->Computed != FNVcomputed+FNV512state )
return fnvStateError; return fnvStateError;
for ( i=0; i<FNV512size/4; ++i ) for ( i=0; i<FNV512size/4; ++i )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
out[15-2*i] = ctx->Hash[i]; out[15-2*i] = ctx->Hash[i];
out[14-2*i] = ctx->Hash[i] >> 8; out[14-2*i] = ctx->Hash[i] >> 8;
#else #else
out[2*i] = ctx->Hash[i]; out[2*i] = ctx->Hash[i];
out[2*i+1] = ctx->Hash[i] >> 8; out[2*i+1] = ctx->Hash[i] >> 8;
skipping to change at page 61, line 29 skipping to change at page 63, line 4
} }
ctx->Computed = FNVemptied+FNV512state; ctx->Computed = FNVemptied+FNV512state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV512result */ } /* end FNV512result */
/****************************************************************** /******************************************************************
* END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
******************************************************************/ ******************************************************************/
INTERNET-DRAFT FNV
#else /* FNV_64bitIntegers */ #else /* FNV_64bitIntegers */
/****************************************************************** /******************************************************************
* START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
******************************************************************/ ******************************************************************/
/* version for when you only have 32-bit arithmetic /* version for when you only have 32-bit arithmetic
********************************************************************/ ********************************************************************/
/* 0x0000000000000000 0000000000000000 /*
512 bit FNV_prime = 2^344 + 2^8 + 0x57 =
0x0000000000000000 0000000000000000
0000000001000000 0000000000000000 0000000001000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000157 */ 0000000000000000 0000000000000157 */
#define FNV512primeX 0x0157 #define FNV512primeX 0x0157
#define FNV512shift 8 #define FNV512shift 8
/* 0xB86DB0B1171F4416 DCA1E50F309990AC /* 0xB86DB0B1171F4416 DCA1E50F309990AC
AC87D059C9000000 0000000000000D21 AC87D059C9000000 0000000000000D21
E948F68A34C192F6 2EA79BC942DBE7CE E948F68A34C192F6 2EA79BC942DBE7CE
182036415F56E34B AC982AAC4AFE9FD9 */ 182036415F56E34B AC982AAC4AFE9FD9 */
skipping to change at page 61, line 48 skipping to change at page 63, line 28
0000000001000000 0000000000000000 0000000001000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000157 */ 0000000000000000 0000000000000157 */
#define FNV512primeX 0x0157 #define FNV512primeX 0x0157
#define FNV512shift 8 #define FNV512shift 8
/* 0xB86DB0B1171F4416 DCA1E50F309990AC /* 0xB86DB0B1171F4416 DCA1E50F309990AC
AC87D059C9000000 0000000000000D21 AC87D059C9000000 0000000000000D21
E948F68A34C192F6 2EA79BC942DBE7CE E948F68A34C192F6 2EA79BC942DBE7CE
182036415F56E34B AC982AAC4AFE9FD9 */ 182036415F56E34B AC982AAC4AFE9FD9 */
uint16_t FNV512basis[FNV512size/2] = { uint16_t FNV512basis[FNV512size/2] = {
0xB86D, 0xB0B1, 0x171F, 0x4416, 0xDCA1, 0xE50F, 0x3099, 0x90AC, 0xB86D, 0xB0B1, 0x171F, 0x4416, 0xDCA1, 0xE50F, 0x3099, 0x90AC,
0xAC87, 0xD059, 0xC900, 0x0000, 0x0000, 0x0000, 0x0000, 0x0D21, 0xAC87, 0xD059, 0xC900, 0x0000, 0x0000, 0x0000, 0x0000, 0x0D21,
0xE948, 0xF68A, 0x34C1, 0x92F6, 0x2EA7, 0x9BC9, 0x42DB, 0xE7CE, 0xE948, 0xF68A, 0x34C1, 0x92F6, 0x2EA7, 0x9BC9, 0x42DB, 0xE7CE,
0x1820, 0x3641, 0x5F56, 0xE34B, 0xAC98, 0x2AAC, 0x4AFE, 0x9FD9 }; 0x1820, 0x3641, 0x5F56, 0xE34B, 0xAC98, 0x2AAC, 0x4AFE, 0x9FD9 };
/******************************************************************** /********************************************************************
* Set of init, input, and output functions bel ow * * Set of init, input, and output functions below *
INTERNET-DRAFT FNV
* to incrementally compute FNV512 * * to incrementally compute FNV512 *
********************************************************************/ ********************************************************************/
/* initialize context (32 bit) /* initialize context (32 bit)
********************************************************************/ ********************************************************************/
int FNV512init ( FNV512context *ctx ) int FNV512init ( FNV512context *ctx )
{ {
int i; int i;
if ( ctx ) if ( ctx )
{ {
for ( i=0; i<FNV512size/2; ++i ) for ( i=0; i<FNV512size/2; ++i )
ctx->Hash[i] = FNV512basis[i]; ctx->Hash[i] = FNV512basis[i];
ctx->Computed = FNVinited+FNV512state; ctx->Computed = FNVinited+FNV512state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV512init */ } /* end FNV512init */
INTERNET-DRAFT FNV
/* initialize context with a provided basis (32 bit) /* initialize context with a provided basis (32 bit)
********************************************************************/ ********************************************************************/
int FNV512initBasis ( FNV512context *ctx, int FNV512initBasis ( FNV512context *ctx,
const uint8_t basis[FNV512size] ) const uint8_t basis[FNV512size] )
{ {
int i; int i;
uint8_t *ui8p; const uint8_t *ui8p;
uint32_t temp; uint32_t temp;
if ( ctx ) if ( ctx )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
ui8p = basis; ui8p = basis;
for ( i=0; i < FNV512size/2; ++i ) for ( i=0; i < FNV512size/2; ++i )
{ {
temp = *ui8p++; temp = *ui8p++;
ctx->Hash[i] = temp<<8 + (*ui8p++); ctx->Hash[i] = ( temp<<8 ) + (*ui8p++);
} }
#else #else
ui8p = basis + ( FNV512size/2 - 1 ); ui8p = basis + ( FNV512size/2 - 1 );
for ( i=0; i < FNV512size/2; ++i ) for ( i=0; i < FNV512size/2; ++i )
{ {
temp = *ui8p--; temp = *ui8p--;
ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); ctx->Hash[i] = ( temp<<8 ) + (*ui8p--);
} }
#endif #endif
ctx->Computed = FNVinited+FNV512state; ctx->Computed = FNVinited+FNV512state;
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV512initBasis */ } /* end FNV512initBasis */
INTERNET-DRAFT FNV
/* hash in a counted block (32 bit) /* hash in a counted block (32 bit)
*******************************************************************/ *******************************************************************/
int FNV512blockin ( FNV512context *ctx, int FNV512blockin ( FNV512context *ctx,
const unsigned char *in, const void *vin,
long int length ) long int length )
{ {
const uint8_t *in = (const uint8_t*)vin;
uint32_t temp[FNV512size/2]; uint32_t temp[FNV512size/2];
uint32_t temp2[6]; uint32_t temp2[6];
int i; int i;
if ( ctx && in ) if ( ctx && in )
{ {
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV512state: case FNVinited+FNV512state:
ctx->Computed = FNVcomputed+FNV512state; ctx->Computed = FNVcomputed+FNV512state;
case FNVcomputed+FNV512state: case FNVcomputed+FNV512state:
INTERNET-DRAFT FNV
break; break;
default: default:
return fnvStateError; return fnvStateError;
} }
if ( length < 0 ) if ( length < 0 )
return fnvBadParam; return fnvBadParam;
for ( i=0; i<FNV512size/2; ++i ) for ( i=0; i<FNV512size/2; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
for ( ; length > 0; length-- ) for ( ; length > 0; length-- )
{ {
skipping to change at page 64, line 4 skipping to change at page 65, line 40
} }
for ( i=0; i<FNV512size/2; ++i ) for ( i=0; i<FNV512size/2; ++i )
ctx->Hash[i] = temp[i]; ctx->Hash[i] = temp[i];
return fnvSuccess; return fnvSuccess;
} }
return fnvNull; return fnvNull;
} /* end FNV512blockin */ } /* end FNV512blockin */
/* hash in a string (32 bit) /* hash in a string (32 bit)
*******************************************************************/ *******************************************************************/
INTERNET-DRAFT FNV
int FNV512stringin ( FNV512context *ctx, const char *in ) int FNV512stringin ( FNV512context *ctx, const char *in )
{ {
uint32_t temp[FNV512size/2]; uint32_t temp[FNV512size/2];
uint32_t temp2[6]; uint32_t temp2[6];
int i; int i;
uint8_t ch; uint8_t ch;
if ( ctx && in ) if ( ctx && in )
{ {
switch ( ctx->Computed ) switch ( ctx->Computed )
{ {
case FNVinited+FNV512state: case FNVinited+FNV512state:
ctx->Computed = FNVcomputed+FNV512state; ctx->Computed = FNVcomputed+FNV512state;
case FNVcomputed+FNV512state: case FNVcomputed+FNV512state:
break; break;
default: default:
return fnvStateError; return fnvStateError;
INTERNET-DRAFT FNV
} }
for ( i=0; i<FNV512size/2; ++i ) for ( i=0; i<FNV512size/2; ++i )
temp[i] = ctx->Hash[i]; temp[i] = ctx->Hash[i];
while ( (ch = (uint8_t)*in++) ) while ( (ch = (uint8_t)*in++) )
{ {
/* temp = FNV512prime * ( temp ^ *in++ ); */ /* temp = FNV512prime * ( temp ^ *in++ ); */
temp[15] ^= ch; temp[15] ^= ch;
for ( i=0; i<6; ++i ) for ( i=0; i<6; ++i )
temp2[i] = temp[10+i] << FNV512shift; temp2[i] = temp[10+i] << FNV512shift;
for ( i=0; i<FNV512size/2; ++i ) for ( i=0; i<FNV512size/2; ++i )
skipping to change at page 65, line 4 skipping to change at page 66, line 40
return fnvNull; return fnvNull;
} /* end FNV512stringin */ } /* end FNV512stringin */
/* return hash (32 bit) /* return hash (32 bit)
********************************************************************/ ********************************************************************/
int FNV512result ( FNV512context *ctx, unsigned char out[16] ) int FNV512result ( FNV512context *ctx, unsigned char out[16] )
{ {
int i; int i;
if ( ctx && out ) if ( ctx && out )
INTERNET-DRAFT FNV
{ {
if ( ctx->Computed != FNVcomputed+FNV512state ) if ( ctx->Computed != FNVcomputed+FNV512state )
return fnvStateError; return fnvStateError;
for ( i=0; i<FNV512size/2; ++i ) for ( i=0; i<FNV512size/2; ++i )
{ {
#ifdef FNV_BigEndian #ifdef FNV_BigEndian
out[31-2*i] = ctx->Hash[i]; out[31-2*i] = ctx->Hash[i];
out[30-2*i] = ctx->Hash[i] >> 8; out[30-2*i] = ctx->Hash[i] >> 8;
#else #else
out[2*i] = ctx->Hash[i]; out[2*i] = ctx->Hash[i];
out[2*i+1] = ctx->Hash[i] >> 8; out[2*i+1] = ctx->Hash[i] >> 8;
#endif #endif
ctx->Hash[i] = 0; ctx->Hash[i] = 0;
} }
ctx->Computed = FNVemptied+FNV512state; ctx->Computed = FNVemptied+FNV512state;
return fnvSuccess; return fnvSuccess;
} }
INTERNET-DRAFT FNV
return fnvNull; return fnvNull;
} /* end FNV512result */ } /* end FNV512result */
#endif /* Have64bitIntegers */ #endif /* Have64bitIntegers */
/******************************************************************** /********************************************************************
* END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
********************************************************************/ ********************************************************************/
#endif /* _FNV512_C_ */ #endif /* _FNV512_C_ */
<CODE ENDS> <CODE ENDS>
6.1.6 FNV1024 C Code 6.1.6 FNV1024 C Code
The header and C source for 1024-bit FNV-1a. The header and C source for 1024-bit FNV-1a.
<CODE BEGINS> <CODE BEGINS>
/*************************** FNV1024.h **************************/ /*************************** FNV1024.h **************************/
/***************** See RFC NNNN for details. ********************/ /***************** See RFC NNNN for details. ********************/
/* /*
* Copyright (c) 2015 IETF Trust and the persons identified as * Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
#ifndef _FNV1024_H_ #ifndef _FNV1024_H_
#define _FNV1024_H_ #define _FNV1024_H_
/* /*
* Description: * Description:
* This file provides headers for the 1024-bit version of the * This file provides headers for the 1024-bit version of the
* FNV-1a non-cryptographic hash algorithm. * FNV-1a non-cryptographic hash algorithm.
INTERNET-DRAFT FNV
*
* >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */
#define FNV_64bitIntegers
/* FNV_64bitIntegers - Define this if your system supports 64-bit
* arithmetic including 32-bit x 32-bit multiplication
* producing a 64-bit product. If undefined, it will be
* assumed that 32-bit arithmetic is supported including
* 16-bit x 16-bit multiplication producing a 32-bit result.
*
* FNV_BigEndian - Define this ONLY if your system uses big
* endian representation AND your FNV hashes need to
* interoperate with little endian systems. If you #define
* this symbol when not needed, it will unnecessarily slow
* down and increase the code size of the FNV functions.
*/ */
#include "FNVconfig.h"
#include <stdint.h> #include <stdint.h>
#define FNV1024size (1024/8) #define FNV1024size (1024/8)
/* If you do not have the ISO standard stdint.h header file, then you /* If you do not have the ISO standard stdint.h header file, then you
* must typedef the following types: * must typedef the following types:
* *
* type meaning * type meaning
* uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers)
* uint32_t unsigned 32 bit integer * uint32_t unsigned 32 bit integer
* uint16_t unsigned 16 bit integer * uint16_t unsigned 16 bit integer
* uint8_t unsigned 8 bit integer (i.e., unsigned char) * uint8_t unsigned 8 bit integer (i.e., unsigned char)
*/ */
INTERNET-DRAFT FNV
#ifndef _FNV_ErrCodes_ #ifndef _FNV_ErrCodes_
#define _FNV_ErrCodes_ #define _FNV_ErrCodes_
/********************************************************************* /*********************************************************************
* All FNV functions provided return as integer as follows: * All FNV functions provided return as integer as follows:
* 0 -> success * 0 -> success
* >0 -> error as listed below * >0 -> error as listed below
*/ */
enum { /* success and errors */ enum { /* success and errors */
fnvSuccess = 0, fnvSuccess = 0,
fnvNull, /* Null pointer parameter */ fnvNull, /* Null pointer parameter */
fnvStateError, /* called Input after Result or before Init */ fnvStateError, /* called Input after Result or before Init */
fnvBadParam /* passed a bad parameter */ fnvBadParam /* passed a bad parameter */
}; };
#endif /* _FNV_ErrCodes_ */ #endif /* _FNV_ErrCodes_ */
/* /*
* This structure holds context information for an FNV1024 hash * This structure holds context information for an FNV1024 hash
*/ */
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
INTERNET-DRAFT FNV
/* version if 64 bit integers supported */ /* version if 64 bit integers supported */
typedef struct FNV1024context_s { typedef struct FNV1024context_s {
int Computed; /* state */ int Computed; /* state */
uint32_t Hash[FNV1024size/4]; uint32_t Hash[FNV1024size/4];
} FNV1024context; } FNV1024context;
#else #else
/* version if 64 bit integers NOT supported */ /* version if 64 bit integers NOT supported */
typedef struct FNV1024context_s { typedef struct FNV1024context_s {
skipping to change at page 67, line 38 skipping to change at page 69, line 5
* FNV1024initBasis: initializes an FNV1024 context with a * FNV1024initBasis: initializes an FNV1024 context with a
* provided basis * provided basis
* FNV1024blockin: hash in a specified length byte vector * FNV1024blockin: hash in a specified length byte vector
* FNV1024stringin: hash in a zero terminated string not * FNV1024stringin: hash in a zero terminated string not
* including the zero * including the zero
* FNV1024result: returns the hash value * FNV1024result: returns the hash value
* *
* Hash is returned as an array of 8-bit integers * Hash is returned as an array of 8-bit integers
*/ */
INTERNET-DRAFT FNV
#ifdef __cplusplus
extern "C" {
#endif
/* FNV1024 */ /* FNV1024 */
extern int FNV1024string ( const char *in, extern int FNV1024string ( const char *in,
unsigned char out[FNV1024size] ); unsigned char out[FNV1024size] );
extern int FNV1024block ( const unsigned char *in, extern int FNV1024block ( const void *in,
unsigned long int length, long int length,
unsigned char out[FNV1024size] ); unsigned char out[FNV1024size] );
extern int FNV1024init ( FNV1024context *); extern int FNV1024init ( FNV1024context *);
extern int FNV1024initBasis ( FNV128context * const, extern int FNV1024initBasis ( FNV1024context * const,
const uint8_t basis[FNV1024size] ); const uint8_t basis[FNV1024size] );
extern int FNV1024blockin ( FNV1024context *, extern int FNV1024blockin ( FNV1024context *,
const unsigned char *in, const void *in,
long int length ); long int length );
extern int FNV1024stringin ( FNV1024context *, extern int FNV1024stringin ( FNV1024context *,
const char *in ); const char *in );
extern int FNV1024result ( FNV1024context *, extern int FNV1024result ( FNV1024context *,
unsigned char out[FNV1024size] ); unsigned char out[FNV1024size] );
#endif /* _FNV1024_H_ */ #ifdef __cplusplus
INTERNET-DRAFT FNV }
#endif
#endif /* _FNV1024_H_ */
<CODE ENDS> <CODE ENDS>
<CODE BEGINS> <CODE BEGINS>
TBD /***************************** FNV1024.c ****************************/
/******************** See RFC NNNN for details *********************/
/* Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights
* See fnv-private.h for terms of use and redistribution.
*/
/* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic
* hash function FNV-1a for 1024-bit hashes.
*/
#ifndef _FNV1024_C_
#define _FNV1024_C_
#include "fnv-private.h"
#include "FNV1024.h"
/* common code for 64 and 32 bit modes */
/* FNV1024 hash a null terminated string (64/32 bit)
********************************************************************/
INTERNET-DRAFT FNV
int FNV1024string ( const char *in, uint8_t out[FNV1024size] )
{
FNV1024context ctx;
int err;
if ( (err = FNV1024init ( &ctx )) != fnvSuccess)
return err;
if ( (err = FNV1024stringin ( &ctx, in )) != fnvSuccess)
return err;
return FNV1024result ( &ctx, out );
} /* end FNV1024string */
/* FNV1024 hash a counted block (64/32 bit)
********************************************************************/
int FNV1024block ( const void *in,
long int length,
uint8_t out[FNV1024size] )
{
FNV1024context ctx;
int err;
if ( (err = FNV1024init ( &ctx )) != fnvSuccess)
return err;
if ( (err = FNV1024blockin ( &ctx, in, length)) != fnvSuccess)
return err;
return FNV1024result ( &ctx, out );
} /* end FNV1024block */
/********************************************************************
* START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
********************************************************************/
#ifdef Have64bitIntegers
/*
1024 bit FNV_prime = 2^680 + 2^8 + 0x8d =
0x0000000000000000 0000010000000000
0000000000000000 0000000000000000
0000000000000000 0000000000000000
0000000000000000 0000000000000000
0000000000000000 0000000000000000
0000000000000000 000000000000018D
#define FNV1024primeX 0x018D
#define FNV1024shift 24
/* 0x0000000000000000 005F7A76758ECC4D
32E56D5A591028B7 4B29FC4223FDADA1
6C3BF34EDA3674DA 9A21D90000000000
0000000000000000 0000000000000000
0000000000000000 0000000000000000
INTERNET-DRAFT FNV
0000000000000000 000000000004C6D7
EB6E73802734510A 555F256CC005AE55
6BDE8CC9C6A93B21 AFF4B16C71EE90B3 */
uint32_t FNV1024basis[FNV1024size/4] = {
0x00000000, 0x00000000, 0x005F7A76, 0x758ECC4D,
0x32E56D5A, 0x591028B7, 0x4B29FC42, 0x23FDADA1,
0x6C3BF34E, 0xDA3674DA, 0x9A21D900, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x0004C6D7,
0xEB6E7380, 0x2734510A, 0x555F256C, 0xC005AE55,
0x6BDE8CC9, 0xC6A93B21, 0xAFF4B16C, 0x71EE90B3
};
/********************************************************************
* Set of init, input, and output functions below *
* to incrementally compute FNV1024 *
********************************************************************/
/* initialize context (64 bit)
********************************************************************/
int FNV1024init ( FNV1024context *ctx )
{
if ( ctx )
{
for ( i=0; i<FNV1024size/4; ++i )
ctx->Hash[i] = FNV1024basis[i];
ctx->Computed = FNVinited+FNV1024state;
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024init */
/* initialize context with a provided basis (64 bit)
********************************************************************/
int FNV1024initBasis ( FNV1024context* const ctx,
const uint8_t basis[FNV1024size] )
{
int i;
uint8_t *ui8p;
uint32_t temp;
if ( ctx )
{
#ifdef FNV_BigEndian
ui8p = basis;
for ( i=0; i < FNV1024size/4; ++i )
{
temp = (*ui8p++)<<8;
INTERNET-DRAFT FNV
temp = (temp + *ui8p++)<<8;
temp = (temp + *ui8p++)<<8;
ctx->Hash[i] = temp + *ui8p;
}
#else
ui8p = basis + (FNV1024size/4 - 1);
for ( i=0; i < FNV1024size/4; ++i )
{
temp = (*ui8p--)<<8;
temp = (temp + *ui8p--)<<8;
temp = (temp + *ui8p--)<<8;
ctx->Hash[i] = temp + *ui8p;
}
#endif
ctx->Computed = FNVinited+FNV1024state;
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024initBasis */
/* hash in a counted block (64 bit)
********************************************************************/
int FNV1024blockin ( FNV1024context *ctx,
const void *vin,
long int length )
{
const uint8_t *in = (const uint8_t*)vin;
uint64_t temp[FNV1024size/4];
uint64_t temp2[3];
if ( ctx && in )
{
switch ( ctx->Computed )
{
case FNVinited+FNV1024state:
ctx->Computed = FNVcomputed+FNV128state;
case FNVcomputed+FNV1024state:
break;
default:
return fnvStateError;
}
if ( length < 0 )
return fnvBadParam;
for ( i=0; i<FNV1024size/4; ++i )
temp[i] = ctx->Hash[i];
for ( ; length > 0; length-- )
{
/* temp = FNV1024prime * ( temp ^ *in++ ); */
temp[7] ^= *in++;
temp2[2] = temp[7] << FNV1024shift;
INTERNET-DRAFT FNV
temp2[1] = temp[6] << FNV1024shift;
temp2[0] = temp[5] << FNV1024shift;
for ( i=0; i<FNV1024size/4; ++i )
temp[i] *= FNV1024primeX;
temp[2] += temp2[2];
temp[1] += temp2[1];
temp[0] += temp2[0];
for ( i=FNV1024size/4-1; i>0; --i )
{
temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF;
}
}
for ( i=0; i<FNV1024size/4; ++i )
ctx->Hash[i] = temp[i];
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024input */
/* hash in a string (64 bit)
********************************************************************/
inf FNV1024stringin ( FNV1024context *ctx, const char *in )
{
uint64_t temp[FNV1024size/4];
uint64_t temp2[2];
int i;
uint8_t ch;
if ( ctx && in )
{
switch ( ctx->Computed )
{
case FNVinited+FNV1024state:
ctx->Computed = FNVcomputed+FNV1024state;
case FNVcomputed+FNV1024state:
break;
default:
return fnvStateError;
}
for ( i=0; i<FNV1024size/4; ++i )
temp[i] = ctx->Hash[i];
while ( ch = (uint8_t)*in++ )
{
/* temp = FNV1024prime * ( temp ^ ch ); */
temp[7] ^= ch;
temp2[2] = temp[7] << FNV128shift;
temp2[1] = temp[6] << FNV128shift;
temp2[0] = temp[5] << FNV128shift;
for ( i=0; i<FNV1024size/4; ++i )
INTERNET-DRAFT FNV
temp[i] *= FNV1024prime;
temp[2] += temp2[2];
temp[1] += temp2[1];
temp[0] += temp2[0];
for ( i=FNVsize1024/4-1; i>0; --i )
{
temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF;
}
}
for ( i=0; i<FNV1024size/4; ++i )
ctx->Hash[i] = temp[i];
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024stringin */
/* return hash (64 bit)
********************************************************************/
int FNV1024result ( FNV1024context *ctx, uint8_t out[FNV1024size] )
{
if ( ctx && out )
{
if ( ctx->Computed != FNVcomputed+FNV1024state )
return fnvStateError;
for ( i=0; i<FNV1024size/4; ++i )
{
#ifdef FNV_BigEndian
out[15-2*i] = ctx->Hash[i];
out[14-2*i] = ctx->Hash[i] >> 8;
#else
out[2*i] = ctx->Hash[i];
out[2*i+1] = ctx->Hash[i] >> 8;
#endif
ctx -> Hash[i] = 0;
}
ctx->Computed = FNVemptied+FNV1024state;
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024result */
/******************************************************************
* END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC *
******************************************************************/
#else /* FNV_64bitIntegers */
/******************************************************************
* START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
******************************************************************/
INTERNET-DRAFT FNV
/* version for when you only have 32-bit arithmetic
********************************************************************/
/*
1024 bit FNV_prime = 2^680 + 2^8 + 0x8d =
0x0000000000000000 0000010000000000
0000000000000000 0000000000000000
0000000000000000 0000000000000000
0000000000000000 0000000000000000
0000000000000000 0000000000000000
0000000000000000 000000000000018D */
#define FNV1024primeX 0x018D
#define FNV1024shift 8
/* 0x0000000000000000 005F7A76758ECC4D
32E56D5A591028B7 4B29FC4223FDADA1
6C3BF34EDA3674DA 9A21D90000000000
0000000000000000 0000000000000000
0000000000000000 0000000000000000
0000000000000000 000000000004C6D7
EB6E73802734510A 555F256CC005AE55
6BDE8CC9C6A93B21 AFF4B16C71EE90B3 */
uint16_t FNV1024basis[FNV1024size/2] = {
0x0000, 0x0000, 0x0000, 0x0000, 0x005F, 0x7A76, 0x758E, 0xCC4D,
0x32E5, 0x6D5A, 0x5910, 0x28B7, 0x4B29, 0xFC42, 0x23FD, 0xADA1,
0x6C3B, 0xF34E, 0xDA36, 0x74DA, 0x9A21, 0xD900, 0x0000, 0x0000,
0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0004, 0xC6D7,
0xEB6E, 0x7380, 0x2734, 0x510A, 0x555F, 0x256C, 0xC005, 0xAE55,
0x6BDE, 0x8CC9, 0xC6A9, 0x3B21, 0xAFF4, 0xB16C, 0x71EE, 0x90B3
};
/********************************************************************
* Set of init, input, and output functions below *
* to incrementally compute FNV1024 *
********************************************************************/
/* initialize context (32 bit)
********************************************************************/
int FNV1024init ( FNV1024context *ctx )
{
int i;
if ( ctx )
{
for ( i=0; i<FNV1024size/2; ++i )
ctx->Hash[i] = FNV1024basis[i];
INTERNET-DRAFT FNV
ctx->Computed = FNVinited+FNV1024state;
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024init */
/* initialize context with a provided basis (32 bit)
********************************************************************/
int FNV1024initBasis ( FNV1024context *ctx,
const uint8_t basis[FNV1024size] )
{
int i;
const uint8_t *ui8p;
uint32_t temp;
if ( ctx )
{
#ifdef FNV_BigEndian
ui8p = basis;
for ( i=0; i < FNV1024size/2; ++i )
{
temp = *ui8p++;
ctx->Hash[i] = ( temp<<8 ) + (*ui8p++);
}
#else
ui8p = basis + ( FNV1024size/2 - 1 );
for ( i=0; i < FNV1024size/2; ++i )
{
temp = *ui8p--;
ctx->Hash[i] = ( temp<<8 ) + (*ui8p--);
}
#endif
ctx->Computed = FNVinited+FNV1024state;
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024initBasis */
/* hash in a counted block (32 bit)
*******************************************************************/
int FNV1024blockin ( FNV1024context *ctx,
const void *vin,
long int length )
{
const uint8_t *in = (const uint8_t*)vin;
uint32_t temp[FNV1024size/2];
uint32_t temp2[6];
int i;
if ( ctx && in )
INTERNET-DRAFT FNV
{
switch ( ctx->Computed )
{
case FNVinited+FNV1024state:
ctx->Computed = FNVcomputed+FNV1024state;
case FNVcomputed+FNV1024state:
break;
default:
return fnvStateError;
}
if ( length < 0 )
return fnvBadParam;
for ( i=0; i<FNV1024size/2; ++i )
temp[i] = ctx->Hash[i];
for ( ; length > 0; length-- )
{
/* temp = FNV1024prime * ( temp ^ *in++ ); */
temp[15] ^= *in++;
for ( i=0; i<6; ++i )
temp2[i] = temp[10+i] << FNV1024shift;
for ( i=0; i<FNV1024size/2; ++i )
temp[i] *= FNV1024primeX;
for ( i=0; i<6; ++i )
temp[10+i] += temp2[i];
for ( i=15; i>0; --i )
{
temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF;
}
}
for ( i=0; i<FNV1024size/2; ++i )
ctx->Hash[i] = temp[i];
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024blockin */
/* hash in a string (32 bit)
*******************************************************************/
int FNV1024stringin ( FNV1024context *ctx, const char *in )
{
uint32_t temp[FNV1024size/2];
uint32_t temp2[6];
int i;
uint8_t ch;
if ( ctx && in )
{
switch ( ctx->Computed )
{
INTERNET-DRAFT FNV
case FNVinited+FNV1024state:
ctx->Computed = FNVcomputed+FNV1024state;
case FNVcomputed+FNV1024state:
break;
default:
return fnvStateError;
}
for ( i=0; i<FNV1024size/2; ++i )
temp[i] = ctx->Hash[i];
while ( (ch = (uint8_t)*in++) )
{
/* temp = FNV1024prime * ( temp ^ *in++ ); */
temp[15] ^= ch;
for ( i=0; i<6; ++i )
temp2[i] = temp[10+i] << FNV1024shift;
for ( i=0; i<FNV1024size/2; ++i )
temp[i] *= FNV1024primeX;
for ( i=0; i<6; ++i )
temp[10+i] += temp2[i];
for ( i=15; i>0; --i )
{
temp[i-1] += temp[i] >> 16;
temp[i] &= 0xFFFF;
}
}
for ( i=0; i<FNV1024size/2; ++i )
ctx->Hash[i] = temp[i];
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024stringin */
/* return hash (32 bit)
********************************************************************/
int FNV1024result ( FNV1024context *ctx, unsigned char out[16] )
{
int i;
if ( ctx && out )
{
if ( ctx->Computed != FNVcomputed+FNV1024state )
return fnvStateError;
for ( i=0; i<FNV1024size/2; ++i )
{
#ifdef FNV_BigEndian
out[31-2*i] = ctx->Hash[i];
out[30-2*i] = ctx->Hash[i] >> 8;
#else
out[2*i] = ctx->Hash[i];
out[2*i+1] = ctx->Hash[i] >> 8;
INTERNET-DRAFT FNV
#endif
ctx->Hash[i] = 0;
}
ctx->Computed = FNVemptied+FNV1024state;
return fnvSuccess;
}
return fnvNull;
} /* end FNV1024result */
#endif /* Have64bitIntegers */
/********************************************************************
* END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC *
********************************************************************/
#endif /* _FNV1024_C_ */
<CODE ENDS> <CODE ENDS>
6.2 FNV Test Code 6.2 FNV Test Code
Here is a test driver: Here is a test driver:
<CODE BEGINS> <CODE BEGINS>
/**************************** MAIN.c ****************************/ /**************************** MAIN.c ****************************/
/****************** See RFC NNNN for details. *******************/ /****************** See RFC NNNN for details. *******************/
/* /*
* Copyright (c) 2015 IETF Trust and the persons identified as * Copyright (c) 2016 IETF Trust and the persons identified as
* authors of the code. All rights reserved. * authors of the code. All rights reserved.
* See fnv-private.h for terms of use and redistribution. * See fnv-private.h for terms of use and redistribution.
*/ */
/* to do a thorough test you need to run will all four /* to do a thorough test you need to run will all four
combinations of the following defined/undefined */ combinations of the following defined/undefined */
#define FNV_64bitIntegers // #define FNV_64bitIntegers
// #define FNV_BigEndian // #define FNV_BigEndian
#include <stdio.h> #include <stdio.h>
#include <string.h> #include <string.h>
#include "fnv-private.h" #include "fnv-private.h"
#include "FNV32.h" #include "FNV.h"
#include "FNV64.h"
#include "FNV128.h"
#include "FNV256.h"
#include "FNV512.h"
#include "FNV1024.h"
/* global variables */ /* global variables */
char *funcName; char *funcName;
char *errteststring = "foo"; char *errteststring = "foo";
int Terr; /* Total errors */ int Terr; /* Total errors */
#define NTestBytes 3 #define NTestBytes 3
uint8_t errtestbytes[NTestBytes] = { (uint8_t)1, uint8_t errtestbytes[NTestBytes] = { (uint8_t)1,
(uint8_t)2, (uint8_t)3 }; (uint8_t)2, (uint8_t)3 };
INTERNET-DRAFT FNV
#define NTstrings 3 #define NTstrings 3
char *teststring[NTstrings] = { "", "a", "foobar" }; char *teststring[NTstrings] = { "", "a", "foobar" };
/***************************************************************** /*****************************************************************
* local prototypes * local prototypes
INTERNET-DRAFT FNV
*****************************************************************/ *****************************************************************/
int TestR ( char *, int should, int was ); int TestR ( char *, int should, int was );
void TestNValue ( char *subfunc, void TestNValue ( char *subfunc,
char *string, char *string,
int N, int N,
uint8_t *should, uint8_t *should,
uint8_t *was ); uint8_t *was );
void HexPrint ( int i, unsigned char *p ); void HexPrint ( int i, unsigned char *p );
void Test32 (); void Test32 ();
void Test32Value ( char *subfunc, char *string, void Test32Value ( char *subfunc, char *string,
uint32_t was, uint32_t should ); uint32_t was, uint32_t should );
void Test64 (); void Test64 ();
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
void Test64Value ( char *subfunc, char *string, void Test64Value ( char *subfunc, char *string,
uint64_t should, uint64_t was ); uint64_t should, uint64_t was );
#else
#define uint64_t foobar
#endif /* FNB_64bitIntegers */ #endif /* FNB_64bitIntegers */
void Test128 (); void Test128 ();
void Test256 (); void Test256 ();
void Test512 (); void Test512 ();
void Test1024 (); void Test1024 ();
void TestNValue ( char *subfunc, void TestNValue ( char *subfunc,
char *string, char *string,
int N, int N,
uint8_t was[N], uint8_t was[N],
skipping to change at page 69, line 44 skipping to change at page 80, line 51
/***************************************************************** /*****************************************************************
* main * main
*****************************************************************/ *****************************************************************/
int main (int argc, const char * argv[]) int main (int argc, const char * argv[])
{ {
#ifdef FNV_64bitIntegers #ifdef FNV_64bitIntegers
printf ("Have 64-bit Integers. "); printf ("Have 64-bit Integers. ");
#else #else
printf ("Do not have 64-bit integers. "); printf ("Do not have 64-bit integers. ");
#endif #endif
#ifdef FNV_BidgEndian #ifdef FNV_BigEndian
printf ("Calculating for Big Endian.0); printf ("Calculating for Big Endian.0);
#else #else
printf ("Not calculating for Big Endian.0); printf ("Not calculating for Big Endian.0);
#endif #endif
funcName = "Testing TestR "; funcName = "Testing TestR ";
INTERNET-DRAFT FNV
/* test the Test Return function */ /* test the Test Return function */
TestR ( "should fail", 1, 2 ); TestR ( "should fail", 1, 2 );
TestR ( "should not have failed", 0, 0 ); TestR ( "should not have failed", 0, 0 );
Test32(); Test32();
Test64(); Test64();
Test128(); Test128();
INTERNET-DRAFT FNV
Test256(); Test256();
Test512();
Test1024();
printf ("Type return to exit.0); printf ("Type return to exit.0);
(void)getchar(); (void)getchar();
printf ("Goodbye!0); printf ("Goodbye!0);
return 0; return 0;
} /* end main */ } /* end main */
/* Test status returns /* Test status returns
*****************************************************************/ *****************************************************************/
skipping to change at page 70, line 29 skipping to change at page 81, line 38
{ {
if ( expect != actual ) if ( expect != actual )
{ {
printf ( "%s%s returned %i instead of %i.0, printf ( "%s%s returned %i instead of %i.0,
funcName, name, actual, expect ); funcName, name, actual, expect );
++Terr; ++Terr;
} }
return actual; return actual;
} /* end TestR */ } /* end TestR */
/* Return true if the bytes are in reverse order from each other */
int revcmp(uint8_t *buf1, uint8_t *buf2, int N) {
int i;
uint8_t *bufc = buf2 + N;
for ( i = 0; i < N / 2; i++ )
if (*buf1++ != *--bufc)
return 0;
return 1;
}
/* General byte vector return error test /* General byte vector return error test
*****************************************************************/ *****************************************************************/
void TestNValue ( char *subfunc, void TestNValue ( char *subfunc,
char *string, char *string,
int N, int N,
uint8_t *was, uint8_t *was,
uint8_t *should ) uint8_t *should )
{ {
if ( !memcmp ( was, should, N) ) #ifdef FNV_BigEndian
INTERNET-DRAFT FNV
if ( revcmp ( was, should, N) == 0)
#else
if ( memcmp ( was, should, N) != 0)
#endif
{ {
printf ( "%s %s of '%s' computed ", funcName, subfunc, string ); printf ( "%s %s of '%s' computed ", funcName, subfunc, string );
HexPrint ( N, was ); HexPrint ( N, was );
printf ( ", should have been " ); printf ( ", should have been " );
HexPrint ( N, should ); HexPrint ( N, should );
printf ( ".0 ); printf ( ".0 );
++Terr; ++Terr;
} }
} /* end TestNValue */ } /* end TestNValue */
/* print some hex /* print some hex
*****************************************************************/ *****************************************************************/
void HexPrint ( int count, unsigned char *ptr ) void HexPrint ( int count, unsigned char *ptr )
{ {
int i; int i;
for ( i = 0; i < count; ++i ) for ( i = 0; i < count; ++i )
printf ( "%02X", ptr[i] ); printf ( "%02X", ptr[i] );
} /* end HexPrint */ } /* end HexPrint */
INTERNET-DRAFT FNV
/***************************************************************** /*****************************************************************
* FNV32 test * FNV32 test
*****************************************************************/ *****************************************************************/
void Test32 () void Test32 ()
{ {
int i, err; int i, err;
long int iLen; long int iLen;
uint32_t eUint32; uint32_t eUint32;
FNV32context eContext; FNV32context eContext;
skipping to change at page 71, line 31 skipping to change at page 83, line 4
funcName = "Test32Value"; funcName = "Test32Value";
Test32Value ( "should fail", "test", FNV32svalues[1], FNV32svalues[2] ); Test32Value ( "should fail", "test", FNV32svalues[1], FNV32svalues[2] );
funcName = "FNV32"; funcName = "FNV32";
/* test error checks */ /* test error checks */
Terr = 0; Terr = 0;
TestR ( "init", fnvSuccess, FNV32init (&eContext) ); TestR ( "init", fnvSuccess, FNV32init (&eContext) );
TestR ( "string", fnvNull, TestR ( "string", fnvNull,
FNV32string ( (char *)0, &eUint32 ) ); FNV32string ( (char *)0, &eUint32 ) );
INTERNET-DRAFT FNV
TestR ( "string", fnvNull, TestR ( "string", fnvNull,
FNV32string ( errteststring, (uint32_t *)0 ) ); FNV32string ( errteststring, (uint32_t *)0 ) );
TestR ( "block", fnvNull, TestR ( "block", fnvNull,
FNV32block ( (uint8_t *)0, 1, &eUint32 ) ); FNV32block ( (uint8_t *)0, 1, &eUint32 ) );
TestR ( "block", fnvBadParam, TestR ( "block", fnvBadParam,
FNV32block ( errtestbytes, -1, &eUint32 ) ); FNV32block ( errtestbytes, -1, &eUint32 ) );
TestR ( "block", fnvNull, TestR ( "block", fnvNull,
FNV32block ( errtestbytes, 1, (uint32_t *)0 ) ); FNV32block ( errtestbytes, 1, (uint32_t *)0 ) );
TestR ( "init", fnvNull, TestR ( "init", fnvNull,
FNV32init ( (FNV32context *)0 ) ); FNV32init ( (FNV32context *)0 ) );
skipping to change at page 72, line 4 skipping to change at page 83, line 32
TestR ( "blockin", fnvNull, TestR ( "blockin", fnvNull,
FNV32blockin ( &eContext, (uint8_t *)0, FNV32blockin ( &eContext, (uint8_t *)0,
NTestBytes ) ); NTestBytes ) );
TestR ( "blockin", fnvBadParam, TestR ( "blockin", fnvBadParam,
FNV32blockin ( &eContext, errtestbytes, -1 ) ); FNV32blockin ( &eContext, errtestbytes, -1 ) );
eContext.Computed = FNVclobber+FNV32state; eContext.Computed = FNVclobber+FNV32state;
TestR ( "blockin", fnvStateError, TestR ( "blockin", fnvStateError,
FNV32blockin ( &eContext, errtestbytes, FNV32blockin ( &eContext, errtestbytes,
NTestBytes ) ); NTestBytes ) );
TestR ( "stringin", fnvNull, TestR ( "stringin", fnvNull,
INTERNET-DRAFT FNV
FNV32stringin ( (FNV32context *)0, errteststring ) ); FNV32stringin ( (FNV32context *)0, errteststring ) );
TestR ( "stringin", fnvNull, TestR ( "stringin", fnvNull,
FNV32stringin ( &eContext, (char *)0 ) ); FNV32stringin ( &eContext, (char *)0 ) );
TestR ( "stringin", fnvStateError, TestR ( "stringin", fnvStateError,
FNV32stringin ( &eContext, errteststring ) ); FNV32stringin ( &eContext, errteststring ) );
TestR ( "result", fnvNull, TestR ( "result", fnvNull,
FNV32result ( (FNV32context *)0, &eUint32 ) ); FNV32result ( (FNV32context *)0, &eUint32 ) );
TestR ( "result", fnvNull, TestR ( "result", fnvNull,
FNV32result ( &eContext, (uint32_t *)0 ) ); FNV32result ( &eContext, (uint32_t *)0 ) );
TestR ( "result", fnvStateError, TestR ( "result", fnvStateError,
skipping to change at page 72, line 32 skipping to change at page 84, line 4
printf ( "%s test of error checks passed0, funcName ); printf ( "%s test of error checks passed0, funcName );
/* test actual results */ /* test actual results */
Terr = 0; Terr = 0;
for ( i = 0; i < NTstrings; ++i ) for ( i = 0; i < NTstrings; ++i )
{ {
err = TestR ( "string", fnvSuccess, err = TestR ( "string", fnvSuccess,
FNV32string ( teststring[i], &eUint32 ) ); FNV32string ( teststring[i], &eUint32 ) );
if ( err == fnvSuccess ) if ( err == fnvSuccess )
Test32Value ( "string", teststring[i], eUint32, Test32Value ( "string", teststring[i], eUint32,
INTERNET-DRAFT FNV
FNV32svalues[i] ); FNV32svalues[i] );
err = TestR ( "block", fnvSuccess, err = TestR ( "block", fnvSuccess,
FNV32block ( (uint8_t *)teststring[i], FNV32block ( (uint8_t *)teststring[i],
(unsigned long)(strlen(teststring[i])+1), (unsigned long)(strlen(teststring[i])+1),
&eUint32 ) ); &eUint32 ) );
if ( err == fnvSuccess ) if ( err == fnvSuccess )
Test32Value ( "block", teststring[i], eUint32, Test32Value ( "block", teststring[i], eUint32,
FNV32bvalues[i] ); FNV32bvalues[i] );
/* now try testing the incremental stuff */ /* now try testing the incremental stuff */
err = TestR ( "init", fnvSuccess, FNV32init ( &eContext ) ); err = TestR ( "init", fnvSuccess, FNV32init ( &eContext ) );
skipping to change at page 73, line 4 skipping to change at page 84, line 32
iLen/2 ) ); iLen/2 ) );
if ( err ) break; if ( err ) break;
err = TestR ( "stringin", fnvSuccess, err = TestR ( "stringin", fnvSuccess,
FNV32stringin ( &eContext, FNV32stringin ( &eContext,
teststring[i] + iLen/2 ) ); teststring[i] + iLen/2 ) );
err = TestR ( "result", fnvSuccess, err = TestR ( "result", fnvSuccess,
FNV32result ( &eContext, &eUint32 ) ); FNV32result ( &eContext, &eUint32 ) );
if ( err ) break; if ( err ) break;
Test32Value ( " incremental", teststring[i], eUint32, Test32Value ( " incremental", teststring[i], eUint32,
FNV32svalues[i] ); FNV32svalues[i] );
INTERNET-DRAFT FNV
} }
if ( Terr ) if ( Terr )
printf ( "%s test of return values failed %i times.0, printf ( "%s test of return values failed %i times.0,
funcName, Terr ); funcName, Terr );
else else
printf ( "%s test of return values passed.0, funcName ); printf ( "%s test of return values passed.0, funcName );
} /* end Test32 */ } /* end Test32 */
/* start Test32Value /* start Test32Value
*****************************************************************/ *****************************************************************/
void Test32Value ( char *subfunc, void Test32Value ( char *subfunc,
char *string, char *string,
uint32_t should, uint32_t was,
uint32_t was ) uint32_t should )
{ {
if ( was != should) TestNValue(subfunc, string, sizeof(uint32_t), (uint8_t*)&was,
{ (uint8_t*)&should);
printf ( "%s %s of '%s' computed 0x",
funcName, subfunc, string );
HexPrint ( 4, (unsigned char *)&was );
printf ( " (%i), should have been 0x", was );
HexPrint ( 4, (unsigned char *)&should );
printf ( " (%i).0, should );
++Terr;
}
} /* end Test32Value */ } /* end Test32Value */
#ifdef FNV_64bitIntegers
/***************************************************************** /*****************************************************************
* Code for FNV64 using 64-bit integers * Code for FNV64 using 64-bit integers
*****************************************************************/ *****************************************************************/
INTERNET-DRAFT FNV
void Test64 () void Test64 ()
{ {
int i, err; int i, err;
uint64_t eUint64 = 42; uint64_t eUint64 = 42;
FNV64context eContext; FNV64context eContext;
uint64_t FNV64svalues[NTstrings] = { uint64_t FNV64svalues[NTstrings] = {
0xcbf29ce484222325, 0xaf63dc4c8601ec8c, 0x85944171f73967e8 }; 0xcbf29ce484222325, 0xaf63dc4c8601ec8c, 0x85944171f73967e8 };
uint64_t FNV64bvalues[NTstrings] = { uint64_t FNV64bvalues[NTstrings] = {
0xaf63bd4c8601b7df, 0x089be207b544f1e4, 0x34531ca7168b8f38 }; 0xaf63bd4c8601b7df, 0x089be207b544f1e4, 0x34531ca7168b8f38 };
funcName = "FNV64"; funcName = "FNV64";
/* test error checks */ /* test error checks */
Terr = 0; Terr = 0;
TestR ( "init", fnvSuccess, FNV64init (&eContext) ); TestR ( "init", fnvSuccess, FNV64init (&eContext) );
TestR ( "string", fnvNull, TestR ( "string", fnvNull,
FNV64string ( (char *)0, &eUint64 ) ); FNV64string ( (char *)0, &eUint64 ) );
TestR ( "string", fnvNull, TestR ( "string", fnvNull,
INTERNET-DRAFT FNV
FNV64string ( errteststring, (uint64_t *)0 ) ); FNV64string ( errteststring, (uint64_t *)0 ) );
TestR ( "block", fnvNull, TestR ( "block", fnvNull,
FNV64block ( (uint8_t *)0, 1, &eUint64 ) ); FNV64block ( (uint8_t *)0, 1, &eUint64 ) );
TestR ( "block", fnvBadParam, TestR ( "block", fnvBadParam,
FNV64block ( errtestbytes, -1, &eUint64 ) ); FNV64block ( errtestbytes, -1, &eUint64 ) );
TestR ( "block", fnvNull, TestR ( "block", fnvNull,
FNV64block ( errtestbytes, 1, (uint64_t *)0 ) ); FNV64block ( errtestbytes, 1, (uint64_t *)0 ) );
TestR ( "init", fnvNull, TestR ( "init", fnvNull,
FNV64init ( (FNV64context *)0 ) ); FNV64init ( (FNV64context *)0 ) );
TestR ( "initBasis", fnvNull, TestR ( "initBasis", fnvNull,
skipping to change at page 74, line 39 skipping to change at page 86, line 4
NTestBytes ) ); NTestBytes ) );
TestR ( "stringin", fnvNull, TestR ( "stringin", fnvNull,
FNV64stringin ( (FNV64context *)0, errteststring ) ); FNV64stringin ( (FNV64context *)0, errteststring ) );
TestR ( "stringin", fnvNull, TestR ( "stringin", fnvNull,
FNV64stringin ( &eContext, (char *)0 ) ); FNV64stringin ( &eContext, (char *)0 ) );
TestR ( "stringin", fnvStateError, TestR ( "stringin", fnvStateError,
FNV64stringin ( &eContext, errteststring ) ); FNV64stringin ( &eContext, errteststring ) );
TestR ( "result", fnvNull, TestR ( "result", fnvNull,
FNV64result ( (FNV64context *)0, &eUint64 ) ); FNV64result ( (FNV64context *)0, &eUint64 ) );
TestR ( "result", fnvNull, TestR ( "result", fnvNull,
INTERNET-DRAFT FNV
FNV64result ( &eContext, (uint64_t *)0 ) ); FNV64result ( &eContext, (uint64_t *)0 ) );
TestR ( "result", fnvStateError, TestR ( "result", fnvStateError,
FNV64result ( &eContext, &eUint64 ) ); FNV64result ( &eContext, &eUint64 ) );
if ( Terr ) if ( Terr )
printf ( "%s test of error checks failed %i times.0, printf ( "%s test of error checks failed %i times.0,
funcName, Terr ); funcName, Terr );
else else
printf ( "%s test of error checks passed0, funcName ); printf ( "%s test of error checks passed0, funcName );
/* test actual results */ /* test actual results */
Terr = 0; Terr = 0;
for ( i = 0; i < NTstrings; ++i ) for ( i = 0; i < NTstrings; ++i )
{ {
err = TestR ( "string", fnvSuccess, err = TestR ( "string", fnvSuccess,
FNV64string ( teststring[i], &eUint64 ) ); FNV64string ( teststring[i], &eUint64 ) );
if ( err == fnvSuccess ) if ( err == fnvSuccess )
Test64Value ( "string", teststring[i], eUint64, Test64Value ( "string", teststring[i], eUint64,
FNV64svalues[i] ); FNV64svalues[i] );
INTERNET-DRAFT FNV
err = TestR ( "block", fnvSuccess, err = TestR ( "block", fnvSuccess,
FNV64block ( (uint8_t *)teststring[i], FNV64block ( (uint8_t *)teststring[i],
(unsigned long)(strlen(teststring[i])+1), (unsigned long)(strlen(teststring[i])+1),
&eUint64 ) ); &eUint64 ) );
if ( err == fnvSuccess ) if ( err == fnvSuccess )
Test64Value ( "block", teststring[i], eUint64, Test64Value ( "block", teststring[i], eUint64,
FNV64bvalues[i] ); FNV64bvalues[i] );
/* now try testing the incremental stuff */ /* now try testing the incremental stuff */
err = TestR ( "init", fnvSuccess, FNV64init ( &eContext ) ); err = TestR ( "init", fnvSuccess, FNV64init ( &eContext ) );
skipping to change at page 75, line 32 skipping to change at page 86, line 50
printf ( "%s test of return values passed.0, funcName ); printf ( "%s test of return values passed.0, funcName );
} /* end Test64 */ } /* end Test64 */
/* start Test64Value /* start Test64Value
*****************************************************************/ *****************************************************************/
void Test64Value ( char *subfunc, void Test64Value ( char *subfunc,
char *string, char *string,
uint64_t should, uint64_t should,
uint64_t was ) uint64_t was )
{ {
if ( was != should) TestNValue(subfunc, string, sizeof(uint64_t), (uint8_t*)&was,
{ . (uint8_t*)&should);
printf ( "%s%s of '%s' computed %llu, should have been %llu.0,
funcName, subfunc, string, was, should );
++Terr;
}
} /* end Test64Value */ } /* end Test64Value */
#else
void Test64 ()
{
/* TBD */
INTERNET-DRAFT FNV
}
#endif /* FNV_64bitIntegers */
/***************************************************************** /*****************************************************************
* Code for FNV128 using 64-bit integers * Code for FNV128 using 64-bit integers
*****************************************************************/ *****************************************************************/
void Test128 () void Test128 ()
{ {
//int i, err; //int i, err;
uint8_t eUint128[FNV128size]; uint8_t eUint128[FNV128size];
FNV128context eContext; FNV128context eContext;
funcName = "FNV128"; funcName = "FNV128";
/* test error checks */ /* test error checks */
Terr = 0; Terr = 0;
TestR ( "init", fnvSuccess, FNV128init (&eContext) ); TestR ( "init", fnvSuccess, FNV128init (&eContext) );
TestR ( "string", fnvNull, TestR ( "string", fnvNull,
INTERNET-DRAFT FNV
FNV128string ( (char *)0, eUint128 ) ); FNV128string ( (char *)0, eUint128 ) );
TestR ( "string", fnvNull, TestR ( "string", fnvNull,
FNV128string ( errteststring, (uint8_t *)0 ) ); FNV128string ( errteststring, (uint8_t *)0 ) );
TestR ( "block", fnvNull, TestR ( "block", fnvNull,
FNV128block ( (uint8_t *)0, 1, eUint128 ) ); FNV128block ( (uint8_t *)0, 1, eUint128 ) );
TestR ( "block", fnvBadParam, TestR ( "block", fnvBadParam,
FNV128block ( errtestbytes, -1, eUint128 ) ); FNV128block ( errtestbytes, -1, eUint128 ) );
TestR ( "block", fnvNull, TestR ( "block", fnvNull,
FNV128block ( errtestbytes, 1, (uint8_t *)0 ) ); FNV128block ( errtestbytes, 1, (uint8_t *)0 ) );
TestR ( "init", fnvNull, TestR ( "init", fnvNull,
skipping to change at page 76, line 37 skipping to change at page 88, line 4
FNV128blockin ( &eContext, errtestbytes, -1 ) ); FNV128blockin ( &eContext, errtestbytes, -1 ) );
eContext.Computed = FNVclobber+FNV128state; eContext.Computed = FNVclobber+FNV128state;
TestR ( "blockin", fnvStateError, TestR ( "blockin", fnvStateError,
FNV128blockin ( &eContext, errtestbytes, FNV128blockin ( &eContext, errtestbytes,
NTestBytes ) ); NTestBytes ) );
TestR ( "stringin", fnvNull, TestR ( "stringin", fnvNull,
FNV128stringin ( (FNV128context *)0, errteststring ) ); FNV128stringin ( (FNV128context *)0, errteststring ) );
TestR ( "stringin", fnvNull, TestR ( "stringin", fnvNull,
FNV128stringin ( &eContext, (char *)0 ) ); FNV128stringin ( &eContext, (char *)0 ) );
TestR ( "stringin", fnvStateError, TestR ( "stringin", fnvStateError,
INTERNET-DRAFT FNV
FNV128stringin ( &eContext, errteststring ) ); FNV128stringin ( &eContext, errteststring ) );
TestR ( "result", fnvNull, TestR ( "result", fnvNull,
FNV128result ( (FNV128context *)0, eUint128 ) ); FNV128result ( (FNV128context *)0, eUint128 ) );
TestR ( "result", fnvNull, TestR ( "result", fnvNull,
FNV128result ( &eContext, (uint8_t *)0 ) ); FNV128result ( &eContext, (uint8_t *)0 ) );
TestR ( "result", fnvStateError, TestR ( "result", fnvStateError,
FNV128result ( &eContext, eUint128 ) ); FNV128result ( &eContext, eUint128 ) );
if ( Terr ) if ( Terr )
printf ( "%s test of error checks failed %i times.0, printf ( "%s test of error checks failed %i times.0,
funcName, Terr ); funcName, Terr );
else else
printf ( "%s test of error checks passed0, funcName ); printf ( "%s test of error checks passed0, funcName );
/* test actual results */ /* test actual results */
Terr = 0; Terr = 0;
/* tbd */ /* tbd */
} /* end Test128 */ } /* end Test128 */
/***************************************************************** /*****************************************************************
INTERNET-DRAFT FNV
* Code for FNV256 using 64-bit integers * Code for FNV256 using 64-bit integers
*****************************************************************/ *****************************************************************/
void Test256 () void Test256 ()
{ {
//int i, err; //int i, err;
uint8_t eUint256[FNV256size]; uint8_t eUint256[FNV256size];
FNV256context eContext; FNV256context eContext;
funcName = "FNV256"; funcName = "FNV256";
skipping to change at page 77, line 36 skipping to change at page 89, line 4
TestR ( "block", fnvBadParam, TestR ( "block", fnvBadParam,
FNV256block ( errtestbytes, -1, eUint256 ) ); FNV256block ( errtestbytes, -1, eUint256 ) );
TestR ( "block", fnvNull, TestR ( "block", fnvNull,
FNV256block ( errtestbytes, 1, (uint8_t *)0 ) ); FNV256block ( errtestbytes, 1, (uint8_t *)0 ) );
TestR ( "init", fnvNull, TestR ( "init", fnvNull,
FNV256init ( (FNV256context *)0 ) ); FNV256init ( (FNV256context *)0 ) );
TestR ( "initBasis", fnvNull, TestR ( "initBasis", fnvNull,
FNV256initBasis ( (FNV256context *)0, eUint256 ) ); FNV256initBasis ( (FNV256context *)0, eUint256 ) );
TestR ( "blockin", fnvNull, TestR ( "blockin", fnvNull,
FNV256blockin ( (FNV256context *)0, FNV256blockin ( (FNV256context *)0,
INTERNET-DRAFT FNV
errtestbytes, NTestBytes ) ); errtestbytes, NTestBytes ) );
TestR ( "blockin", fnvNull, TestR ( "blockin", fnvNull,
FNV256blockin ( &eContext, (uint8_t *)0, FNV256blockin ( &eContext, (uint8_t *)0,
NTestBytes ) ); NTestBytes ) );
TestR ( "blockin", fnvBadParam, TestR ( "blockin", fnvBadParam,
FNV256blockin ( &eContext, errtestbytes, -1 ) ); FNV256blockin ( &eContext, errtestbytes, -1 ) );
eContext.Computed = FNVclobber+FNV256state; eContext.Computed = FNVclobber+FNV256state;
TestR ( "blockin", fnvStateError, TestR ( "blockin", fnvStateError,
FNV256blockin ( &eContext, errtestbytes, FNV256blockin ( &eContext, errtestbytes,
NTestBytes ) ); NTestBytes ) );
TestR ( "stringin", fnvNull, TestR ( "stringin", fnvNull,
FNV256stringin ( (FNV256context *)0, errteststring ) ); FNV256stringin ( (FNV256context *)0, errteststring ) );
TestR ( "stringin", fnvNull, TestR ( "stringin", fnvNull,
FNV256stringin ( &eContext, (char *)0 ) ); FNV256stringin ( &eContext, (char *)0 ) );
TestR ( "stringin", fnvStateError, TestR ( "stringin", fnvStateError,
FNV256stringin ( &eContext, errteststring ) ); FNV256stringin ( &eContext, errteststring ) );
TestR ( "result", fnvNull, TestR ( "result", fnvNull,
FNV256result ( (FNV256context *)0, eUint256 ) ); FNV256result ( (FNV256context *)0, eUint256 ) );
TestR ( "result", fnvNull, TestR ( "result", fnvNull,
FNV256result ( &eContext, (uint8_t *)0 ) ); FNV256result ( &eContext, (uint8_t *)0 ) );
TestR ( "result", fnvStateError,
FNV256result ( &eContext, eUint256 ) );
if ( Terr )
printf ( "%s test of error checks failed %i times.0,
funcName, Terr );
else
printf ( "%s test of error checks passed0, funcName );
/* test actual results */
Terr = 0;
/* tbd */
} /* end Test256 */
/*****************************************************************
* Code for FNV512 using 64-bit integers
*****************************************************************/
void Test512 ()
{
//int i, err;
uint8_t eUint512[FNV512size];
FNV512context eContext;
funcName = "FNV512";
/* test error checks */
Terr = 0;
TestR ( "init", fnvSuccess, FNV512init (&eContext) );
TestR ( "string", fnvNull,
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
FNV512string ( (char *)0, eUint512 ) );
TestR ( "string", fnvNull,
FNV512string ( errteststring, (uint8_t *)0 ) );
TestR ( "block", fnvNull,
FNV512block ( (uint8_t *)0, 1, eUint512 ) );
TestR ( "block", fnvBadParam,
FNV512block ( errtestbytes, -1, eUint512 ) );
TestR ( "block", fnvNull,
FNV512block ( errtestbytes, 1, (uint8_t *)0 ) );
TestR ( "init", fnvNull,
FNV512init ( (FNV512context *)0 ) );
TestR ( "initBasis", fnvNull,
FNV512initBasis ( (FNV512context *)0, eUint512 ) );
TestR ( "blockin", fnvNull,
FNV512blockin ( (FNV512context *)0,
errtestbytes, NTestBytes ) );
TestR ( "blockin", fnvNull,
FNV512blockin ( &eContext, (uint8_t *)0,
NTestBytes ) );
TestR ( "blockin", fnvBadParam,
FNV512blockin ( &eContext, errtestbytes, -1 ) );
eContext.Computed = FNVclobber+FNV512state;
TestR ( "blockin", fnvStateError,
FNV512blockin ( &eContext, errtestbytes,
NTestBytes ) );
TestR ( "stringin", fnvNull,
FNV512stringin ( (FNV512context *)0, errteststring ) );
TestR ( "stringin", fnvNull,
FNV512stringin ( &eContext, (char *)0 ) );
TestR ( "stringin", fnvStateError,
FNV512stringin ( &eContext, errteststring ) );
TestR ( "result", fnvNull,
FNV512result ( (FNV512context *)0, eUint512 ) );
TestR ( "result", fnvNull,
FNV512result ( &eContext, (uint8_t *)0 ) );
TestR ( "result", fnvStateError, TestR ( "result", fnvStateError,
FNV256result ( &eContext, eUint256 ) ); FNV512result ( &eContext, eUint512 ) );
if ( Terr ) if ( Terr )
printf ( "%s test of error checks failed %i times.0, printf ( "%s test of error checks failed %i times.0,
funcName, Terr ); funcName, Terr );
else else
printf ( "%s test of error checks passed0, funcName ); printf ( "%s test of error checks passed0, funcName );
/* test actual results */ /* test actual results */
Terr = 0; Terr = 0;
/* tbd */ /* tbd */
} /* end Test256 */ } /* end Test512 */
/*****************************************************************
INTERNET-DRAFT FNV
* Code for FNV1024 using 64-bit integers
*****************************************************************/
void Test1024 ()
{
//int i, err;
uint8_t eUint1024[FNV1024size];
FNV1024context eContext;
funcName = "FNV1024";
/* test error checks */
Terr = 0;
TestR ( "init", fnvSuccess, FNV1024init (&eContext) );
TestR ( "string", fnvNull,
FNV1024string ( (char *)0, eUint1024 ) );
TestR ( "string", fnvNull,
FNV1024string ( errteststring, (uint8_t *)0 ) );
TestR ( "block", fnvNull,
FNV1024block ( (uint8_t *)0, 1, eUint1024 ) );
TestR ( "block", fnvBadParam,
FNV1024block ( errtestbytes, -1, eUint1024 ) );
TestR ( "block", fnvNull,
FNV1024block ( errtestbytes, 1, (uint8_t *)0 ) );
TestR ( "init", fnvNull,
FNV1024init ( (FNV1024context *)0 ) );
TestR ( "initBasis", fnvNull,
FNV1024initBasis ( (FNV1024context *)0, eUint1024 ) );
TestR ( "blockin", fnvNull,
FNV1024blockin ( (FNV1024context *)0,
errtestbytes, NTestBytes ) );
TestR ( "blockin", fnvNull,
FNV1024blockin ( &eContext, (uint8_t *)0,
NTestBytes ) );
TestR ( "blockin", fnvBadParam,
FNV1024blockin ( &eContext, errtestbytes, -1 ) );
eContext.Computed = FNVclobber+FNV1024state;
TestR ( "blockin", fnvStateError,
FNV1024blockin ( &eContext, errtestbytes,
NTestBytes ) );
TestR ( "stringin", fnvNull,
FNV1024stringin ( (FNV1024context *)0, errteststring ) );
TestR ( "stringin", fnvNull,
FNV1024stringin ( &eContext, (char *)0 ) );
TestR ( "stringin", fnvStateError,
FNV1024stringin ( &eContext, errteststring ) );
TestR ( "result", fnvNull,
FNV1024result ( (FNV1024context *)0, eUint1024 ) );
TestR ( "result", fnvNull,
FNV1024result ( &eContext, (uint8_t *)0 ) );
INTERNET-DRAFT FNV
TestR ( "result", fnvStateError,
FNV1024result ( &eContext, eUint1024 ) );
if ( Terr )
printf ( "%s test of error checks failed %i times.0,
funcName, Terr );
else
printf ( "%s test of error checks passed0, funcName );
/* test actual results */
Terr = 0;
/* tbd */
} /* end Test1024 */
<CODE ENDS> <CODE ENDS>
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
7. Security Considerations 7. Security Considerations
This document is intended to provide convenient open source access by This document is intended to provide convenient open source access by
the Internet community to the FNV non-cryptographic hash. No the Internet community to the FNV non-cryptographic hash. No
assertion of suitability for cryptographic applications is made for assertion of suitability for cryptographic applications is made for
the FNV hash algorithms. the FNV hash algorithms.
skipping to change at page 80, line 7 skipping to change at page 94, line 7
profusely available through elastic cloud services or botnets. profusely available through elastic cloud services or botnets.
This is to slow down testing of possible inputs if the output is This is to slow down testing of possible inputs if the output is
known. But FNV is designed to be very inexpensive on a general- known. But FNV is designed to be very inexpensive on a general-
purpose processor. (See Appendix A.) purpose processor. (See Appendix A.)
Nevertheless, none of the above have proven to be a problem in actual Nevertheless, none of the above have proven to be a problem in actual
practice for the many applications of FNV. practice for the many applications of FNV.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
7.2 Inducing Collisions
While use of a cryptographic hash should be considered when active
adversaries are a factor, the following attack can be made much more
difficult with very minor changes in the use of FNV.
If FNV is being used in a known way for hash tables in a network
server or the like, for example some part of a web server, an
adversary could send requests calculated to cause hash table
collisions and induce substantial processing delays. As mentioned in
Section 2.2, use of an offset_basis not knownable by the adversary
will substantially eliminate this problem.
INTERNET-DRAFT FNV
8. IANA Considerations 8. IANA Considerations
This document requires no IANA Actions. This document requires no IANA Actions. RFC Ediotor: Please delete
this section before publication.
Normative References Normative References
[RFC20] - Cerf, V., "ASCII format for network interchange", STD 80, [RFC20] - Cerf, V., "ASCII format for network interchange", STD 80,
RFC 20, October 1969, <http://www.rfc-editor.org/info/rfc20>. RFC 20, October 1969, <http://www.rfc-editor.org/info/rfc20>.
Informative References Informative References
[FNV] - FNV web site: [FNV] - FNV web site:
http://www.isthe.com/chongo/tech/comp/fnv/index.html http://www.isthe.com/chongo/tech/comp/fnv/index.html
skipping to change at page 81, line 11 skipping to change at page 96, line 11
[RFC6437] - Amante, S., Carpenter, B., Jiang, S., and J. Rajahalme, [RFC6437] - Amante, S., Carpenter, B., Jiang, S., and J. Rajahalme,
"IPv6 Flow Label Specification", RFC 6437, November 2011, "IPv6 Flow Label Specification", RFC 6437, November 2011,
<http://www.rfc-editor.org/info/rfc6437>. <http://www.rfc-editor.org/info/rfc6437>.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Acknowledgements Acknowledgements
The contributions of the following are gratefully acknowledged: The contributions of the following are gratefully acknowledged:
Frank Ellermann, Tony Finch, Bob Moskowitz, Gayle Noble, and Roman Donchenko, Frank Ellermann, Tony Finch, Bob Moskowitz,
Stefan Santesson. Gayle Noble, Stefan Santesson, and Mukund Sivaraman.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Appendix A: Work Comparison with SHA-1 Appendix A: Work Comparison with SHA-1
This section provides a simplistic rough comparison of the level of This section provides a simplistic rough comparison of the level of
effort required per input byte to compute FNV-1a and SHA-1 [RFC3174]. effort required per input byte to compute FNV-1a and SHA-1 [RFC3174].
Ignoring transfer of control and conditional tests and equating all Ignoring transfer of control and conditional tests and equating all
logical and arithmetic operations, FNV requires 2 operations per logical and arithmetic operations, FNV requires 2 operations per
byte, an XOR and a multiply. byte, an XOR and a multiply.
SHA-1 is a relatively weak cryptographic hash producing a 160-bit SHA-1 is a relatively weak cryptographic hash producing a 160-bit
hash. It that has been partially broken [RFC6194]. It is actually hash. It has been partially broken [RFC6194]. It is actually designed
designed to accept a bit vector input although almost all computer to accept a bit vector input although almost all computer uses apply
uses apply it to an integer number of bytes. It processes blocks of it to an integer number of bytes. It processes blocks of 512 bits (64
512 bits (64 bytes) and we estimate the effort involved in SHA-1 bytes) and we estimate the effort involved in SHA-1 processing a full
processing a full block. Ignoring SHA-1 initial set up, transfer of block. Ignoring SHA-1 initial set up, transfer of control, and
control, and conditional tests, but counting all logical and conditional tests, but counting all logical and arithmetic
arithmetic operations, including counting indexing as an addition, operations, including counting indexing as an addition, SHA-1
SHA-1 requires 1,744 operations per 64 bytes block or 27.25 requires 1,744 operations per 64 bytes block or 27.25 operations per
operations per byte. So by this rough measure, it is a little over 13 byte. So by this rough measure, it is a little over 13 times the
times the effort of FNV for large amounts of data. However, FNV is effort of FNV for large amounts of data. However, FNV is commonly
commonly used for small inputs. Using the above method, for inputs of used for small inputs. Using the above method, for inputs of N bytes,
N bytes, where N is <= 55 so SHA-1 will take one block (SHA-1 where N is <= 55 so SHA-1 will take one block (SHA-1 includes padding
includes padding and an 8-byte length at the end of the data in the and an 8-byte length at the end of the data in the last block), the
last block), the ratio of the effort for SHA-1 to the effort for FNV ratio of the effort for SHA-1 to the effort for FNV will be 872/N.
will be 872/N. For example, with an 8 byte input, SHA-1 will take 109 For example, with an 8 byte input, SHA-1 will take 109 times as much
times as much effort as FNV. effort as FNV.
Stronger cryptographic functions than SHA-1 generally have an even Stronger cryptographic functions than SHA-1 generally have an even
high work factor. higher work factor.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Appendix B: Previous IETF Reference to FNV Appendix B: Previous IETF Reference to FNV
FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has
since expired. It was later decided that it would be better to use a since expired. It was later decided that it would be better to use a
cryptographic hash for that application. cryptographic hash for that application.
Below is the Java code for FNV64 from that TLS draft include by the Below is the Java code for FNV64 from that TLS draft included by the
kind permission of the author: kind permission of the author:
<CODE BEGINS> <CODE BEGINS>
/** /**
* Java code sample, implementing 64 bit FNV-1a * Java code sample, implementing 64 bit FNV-1a
* By Stefan Santesson * By Stefan Santesson
*/ */
import java.math.BigInteger; import java.math.BigInteger;
skipping to change at page 84, line 7 skipping to change at page 99, line 7
digest = digest.multiply(fnvPrime).mod(m); digest = digest.multiply(fnvPrime).mod(m);
} }
return digest; return digest;
} }
} }
<CODE ENDS> <CODE ENDS>
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Appendix C: A Few Test Vectors
Below are a few test vectors in the form of ASCII strings and their
FNV32 and FNV64 hashes using the FNV-1a algorithm.
Strings without null (zero byte) termination:
String FNV32 FNV64
"" 0x811c9dc5 0xcbf29ce484222325
"a" 0xe40c292c 0xaf63dc4c8601ec8c
"foobar" 0xbf9cf968 0x85944171f73967e8
Strings including null (zero byte) termination:
String FNV32 FNV64
"" 0x050c5d1f 0xaf63bd4c8601b7df
"a" 0x2b24d044 0x089be207b544f1e4
"foobar" 0x0c1c9eb8 0x34531ca7168b8f38
INTERNET-DRAFT FNV
Appendix Z: Change Summary Appendix Z: Change Summary
RFC Editor Note: Please delete this appendix on publication. RFC Editor Note: Please delete this appendix on publication.
From -00 to -01 From -00 to -01
1. Add Security Considerations section on why FNV is non- 1. Add Security Considerations section on why FNV is non-
cryptographic. cryptographic.
2. Add Appendix A on a work factor comparison with SHA-1. 2. Add Appendix A on a work factor comparison with SHA-1.
skipping to change at page 86, line 7 skipping to change at page 102, line 7
From -09 to -10 From -09 to -10
1. Inclusion of initial partial version of code and some 1. Inclusion of initial partial version of code and some
documentation about the code, Section 6. documentation about the code, Section 6.
2. Insertion of new Section 4 on hashing values. 2. Insertion of new Section 4 on hashing values.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
From -10 to -11
Changes based on code improvements primarily from Tony Hansen who has
been added as an author. Changes based on comments from Mukund
Sivaraman and Roman Donchenko.
INTERNET-DRAFT FNV
Author's Address Author's Address
Glenn Fowler Glenn Fowler
Google Google
Email: glenn.s.fowler@gmail.com Email: glenn.s.fowler@gmail.com
Landon Curt Noll Landon Curt Noll
Cisco Systems Cisco Systems
170 West Tasman Drive 170 West Tasman Drive
skipping to change at page 87, line 5 skipping to change at page 103, line 36
Email: phongvo@gmail.com Email: phongvo@gmail.com
Donald Eastlake Donald Eastlake
Huawei Technologies Huawei Technologies
155 Beaver Street 155 Beaver Street
Milford, MA 01757 USA Milford, MA 01757 USA
Telephone: +1-508-333-2270 Telephone: +1-508-333-2270
EMail: d3e3e3@gmail.com EMail: d3e3e3@gmail.com
Tony Hansen
AT&T Laboratories
200 Laurel Ave. South
Middletown, NJ 07748
USA
Email: tony@att.com
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Copyright, Disclaimer, and Additional IPR Provisions Copyright, Disclaimer, and Additional IPR Provisions
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2016 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
 End of changes. 305 change blocks. 
456 lines changed or deleted 1244 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/