< draft-eastlake-fnv-02.txt		draft-eastlake-fnv-03.txt >
	Network Working Group Glenn Fowler		Network Working Group Glenn Fowler
	INTERNET-DRAFT AT&T Labs Research		INTERNET-DRAFT AT&T Labs Research
	Intended Status: Informational Landon Curt Noll		Intended Status: Informational Landon Curt Noll
	Cisco Systems		Cisco Systems
	Kiem-Phong Vo		Kiem-Phong Vo
	AT&T Labs Research		AT&T Labs Research
	Donald Eastlake		Donald Eastlake
	Huawei Technologies		Huawei Technologies
	Expires: March 23, 2011 September 24, 2011		Expires: September 25, 2012 March 26, 2012
	The FNV Non-Cryptographic Hash Algorithm		The FNV Non-Cryptographic Hash Algorithm
	<draft-eastlake-fnv-02.txt>		<draft-eastlake-fnv-03.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 26 ¶		skipping to change at page 2, line 26 ¶
	3. Other Hash Sizes and XOR Folding........................6		3. Other Hash Sizes and XOR Folding........................6
	4. FNV Constants...........................................7		4. FNV Constants...........................................7
	5. The Source Code.........................................9		5. The Source Code.........................................9
	5.1 FNV C Header...........................................9		5.1 FNV C Header...........................................9
	5.2 FNV C Code.............................................9		5.2 FNV C Code.............................................9
	5.3 FNV Test Code..........................................9		5.3 FNV Test Code..........................................9
	6. Security Considerations................................10		6. Security Considerations................................10
	6.1 Why is FNV Non-Cryptographic?.........................10		6.1 Why is FNV Non-Cryptographic?.........................10
	7. IANA Considerations....................................11		7. IANA Considerations....................................11
	8. Acknowledgements.......................................11		8. Acknowledgements.......................................11
	9. References.............................................12		9. References.............................................12
	9.1 Normative References..................................12		9.1 Normative References..................................12
	9.2 Informative References................................12		9.2 Informative References................................12
	Appendix A: Work Comparison with SHA-1....................13		Appendix A: Work Comparison with SHA-1....................13
	Appendix B: Previous IETF Reference to FNV................14		Appendix B: Previous IETF Reference to FNV................14
	Appendix C: A Few Test Vectors............................15		Appendix C: A Few Test Vectors............................15
	Appendix Z: Change Summary................................16		Appendix Z: Change Summary................................16
	From -00 to -01...........................................16		From -00 to -01...........................................16
	From -01 to -02...........................................16		From -01 to -02...........................................16
			From -02 to -03...........................................16
	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
	it the "Fowler/Noll/Vo" or FNV hash. [FNV]		it the "Fowler/Noll/Vo" or FNV hash. [FNV]
	FNV hashes are designed to be fast while maintaining a low collision		FNV hashes are designed to be fast while maintaining a low collision
	rate. Their speed allows one to quickly hash lots of data while		rate. The high dispersion of the FNV hashes makes them well suited
	maintaining a reasonably low collision rate. The high dispersion of		for hashing nearly identical strings such as URLs, hostnames,
	the FNV hashes makes them well suited for hashing nearly identical		filenames, text, IP addresses, etc. Their speed allows one to quickly
	strings such as URLs, hostnames, filenames, text, IP addresses, etc.		hash lots of data while maintaining a reasonably low collision rate.
	However, they are generally not suitable for cryptographic use. (See		However, they are generally not suitable for cryptographic use. (See
	Section 6.1.)		Section 6.1.)
	The FNV hash is widely used, for example in DNS servers, database		The FNV hash is widely used, for example in DNS servers, database
	indexing hashes, major web search / indexing engines, netnews history		indexing hashes, major web search / indexing engines, netnews history
	file Message-ID lookup functions, anti-spam filters, a spellchecker		file Message-ID lookup functions, anti-spam filters, a spellchecker
	programmed in Ada 95, flatassembler's open source x86 assembler -		programmed in Ada 95, flatassembler's open source x86 assembler -
	user-defined symbol hashtree, non-cryptographic file fingerprints,		user-defined symbol hashtree, non-cryptographic file fingerprints,
	computing Unique IDs in DASM (DTN Applications for Symbian Mobile-		computing Unique IDs in DASM (DTN Applications for Symbian Mobile-
	phones), Microsoft's hash_map implementation for VC++ 2005, the		phones), Microsoft's hash_map implementation for VC++ 2005, the
	skipping to change at page 5, line 27 ¶		skipping to change at page 5, line 27 ¶
	performance of a multiplication with an FNV_Prime by replacing the		performance of a multiplication with an FNV_Prime by replacing the
	multiplication with shifts and adds. However, note that the		multiplication with shifts and adds. However, note that the
	performance of this substitution is highly hardware-dependent and		performance of this substitution is highly hardware-dependent and
	should be done with care. FNV_Primes were selected primarily for the		should be done with care. FNV_Primes were selected primarily for the
	quality of resulting hash function, not for compiler optimization.		quality of resulting hash function, not for compiler optimization.
	2.2 FNV offset_basis		2.2 FNV offset_basis
	The offset_basis values for the n-bit FNV-1a algorithms are computed		The offset_basis values for the n-bit FNV-1a algorithms are computed
	by applying the n-bit FNV-0 algorithm to the 32 octets representing		by applying the n-bit FNV-0 algorithm to the 32 octets representing
	the following character string in [US-ASCII]:		the following character string in [RFC20]:
	chongo <Landon Curt Noll> /\../\		chongo <Landon Curt Noll> /\../\
	The \'s in the above string are not C-style escape characters. In C-		The \'s in the above string are not C-style escape characters. In C-
	string notation, these 32 octets are:		string notation, these 32 octets are:
	"chongo <Landon Curt Noll> /\\../\\"		"chongo <Landon Curt Noll> /\\../\\"
	2.3 FNV Endianism		2.3 FNV Endianism
	skipping to change at page 12, line 13 ¶		skipping to change at page 12, line 13 ¶
	Frank Ellermann, Bob Moskowitz, and Stefan Santesson.		Frank Ellermann, Bob Moskowitz, and Stefan Santesson.
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	9. References		9. References
	Below are the normative and informative references for this document.		Below are the normative and informative references for this document.
	9.1 Normative References		9.1 Normative References
	[US-ASCII] - ANSI, "USA Standard Code for Information Interchange",		[RFC20] - Cerf, V., "ASCII format for network interchange", RFC 20,
	X3.4, American National Standards Institute: New York, 1968.		October 1969.
	9.2 Informative References		9.2 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
	[IEEE] - http://www.ieee.org		[IEEE] - http://www.ieee.org
	[RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm		[RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm
	1 (SHA1)", RFC 3174, September 2001.		1 (SHA1)", RFC 3174, September 2001.
	skipping to change at page 17, line 5 ¶		skipping to change at page 16, line 33 ¶
	1. Correct FNV_Prime determination criteria and add note as to why s		1. Correct FNV_Prime determination criteria and add note as to why s
	< 5 and s > 10 are not considered.		< 5 and s > 10 are not considered.
	2. Add acknowledgements list.		2. Add acknowledgements list.
	3. Add a couple of references.		3. Add a couple of references.
	4. Minor editorial changes.		4. Minor editorial changes.
			From -02 to -03
			1. Replace direct reference to US-ASCII standard with reference to
			RFC 20.
			2. Update dates and verion number.
			3. Minor editing change.
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	Author's Address		Author's Address
	Glenn Fowler		Glenn Fowler
	AT&T Labs Research		AT&T Labs Research
	180 Park Avenue		180 Park Avenue
	Florham Park, NJ 07932 USA		Florham Park, NJ 07932 USA
	Email: gsf@research.att.com		Email: gsf@research.att.com
	skipping to change at page 18, line 9 ¶		skipping to change at page 18, line 9 ¶
	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
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	Copyright, Disclaimer, and Additional IPR Provisions		Copyright, Disclaimer, and Additional IPR Provisions
	Copyright (c) 2011 IETF Trust and the persons identified as the		Copyright (c) 2012 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. 11 change blocks.
	10 lines changed or deleted		23 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/