idnits 2.17.1 draft-eastlake-fnv-13.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 236 has weird spacing: '...ed char hash...' == Line 1679 has weird spacing: '...int i;...' == Line 2219 has weird spacing: '...int i;...' == Line 2390 has weird spacing: '...context ctx...' == Line 2405 has weird spacing: '...context ctx...' == (18 more instances...) -- The document date (June 7, 2017) is 2514 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'N' is mentioned on line 236, but not defined == Missing Reference: 'FNV128size' is mentioned on line 4966, but not defined == Missing Reference: 'FNV256size' is mentioned on line 5029, but not defined == Missing Reference: 'FNV512size' is mentioned on line 5093, but not defined == Missing Reference: 'FNV1024size' is mentioned on line 5158, but not defined -- Obsolete informational reference (is this intentional?): RFC 2460 (Obsoleted by RFC 8200) Summary: 0 errors (**), 0 flaws (~~), 12 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group Glenn Fowler 2 INTERNET-DRAFT Google 3 Intended Status: Informational Landon Curt Noll 4 Cisco Systems 5 Kiem-Phong Vo 6 Google 7 Donald Eastlake 8 Huawei Technologies 9 Tony Hansen 10 AT&T Laboratories 11 Expires: December 6, 2017 June 7, 2017 13 The FNV Non-Cryptographic Hash Algorithm 14 16 Abstract 18 FNV (Fowler/Noll/Vo) is a fast, non-cryptographic hash algorithm with 19 good dispersion. The purpose of this document is to make information 20 on FNV and open source code performing FNV conveniently available to 21 the Internet community. 23 Status of This Memo 25 This Internet-Draft is submitted to IETF in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Distribution of this document is unlimited. Comments should be sent 29 to the authors. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF), its areas, and its working groups. Note that 33 other groups may also distribute working documents as Internet- 34 Drafts. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 The list of current Internet-Drafts can be accessed at 42 http://www.ietf.org/1id-abstracts.html. The list of Internet-Draft 43 Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html. 46 Table of Contents 48 1. Introduction............................................3 50 2. FNV Basics..............................................4 51 2.1 FNV Primes.............................................4 52 2.2 FNV offset_basis.......................................5 53 2.3 FNV Endianism..........................................6 55 3. Other Hash Sizes and XOR Folding........................7 56 4. Hashing Multiple Values Together........................8 57 5. FNV Constants...........................................9 59 6. The Source Code........................................11 60 6.1 FNV-1a C Code.........................................11 61 6.1.1 FNV32 Code..........................................15 62 6.1.2 FNV64 C Code........................................26 63 6.1.3 FNV128 C Code.......................................48 64 6.1.4 FNV256 C Code.......................................59 65 6.1.5 FNV512 C Code.......................................71 66 6.1.6 FNV1024 C Code......................................82 67 6.2 FNV Test Code.........................................95 69 7. Security Considerations...............................108 70 7.1 Why is FNV Non-Cryptographic?........................108 71 7.2 Inducing Collisions..................................109 73 8. IANA Considerations...................................110 74 Normative References.....................................110 75 Informative References...................................110 77 Acknowledgements.........................................111 78 Appendix A: Work Comparison with SHA-1...................112 79 Appendix B: Previous IETF Reference to FNV...............113 80 Appendix C: A Few Test Vectors...........................114 82 Appendix Z: Change Summary...............................115 83 From -00 to -01..........................................115 84 From -01 to -02..........................................115 85 From -02 to -03..........................................115 86 From -03 to -04..........................................115 87 From -04 to -05..........................................116 88 From -05 to -06..........................................116 89 From -06 to -07 to -08...................................116 90 From -08 to -09..........................................116 91 From -09 to -10..........................................116 92 From -10 to -11..........................................117 93 From -11 to -12..........................................117 94 From -12 to -13..........................................117 96 1. Introduction 98 The FNV hash algorithm is based on an idea sent as reviewer comments 99 to the [IEEE] POSIX P1003.2 committee by Glenn Fowler and Phong Vo in 100 1991. In a subsequent ballot round Landon Curt Noll suggested an 101 improvement on their algorithm. Some people tried this hash and found 102 that it worked rather well. In an EMail message to Landon, they named 103 it the "Fowler/Noll/Vo" or FNV hash. [FNV] 105 FNV hashes are designed to be fast while maintaining a low collision 106 rate. The high dispersion of the FNV hashes makes them well suited 107 for hashing nearly identical strings such as URLs, hostnames, 108 filenames, text, IP addresses, etc. Their speed allows one to quickly 109 hash lots of data while maintaining a reasonably low collision rate. 110 However, they are generally not suitable for cryptographic use. (See 111 Section 7.1.) 113 The FNV hash is widely used, for example in DNS servers, the Twitter 114 service, database indexing hashes, major web search / indexing 115 engines, netnews history file Message-ID lookup functions, anti-spam 116 filters, a spellchecker programmed in Ada 95, flatassembler's open 117 source x86 assembler - user-defined symbol hashtree, non- 118 cryptographic file fingerprints, computing Unique IDs in DASM (DTN 119 (Delay Tolerant Networking) Applications for Symbian Mobile-phones), 120 Microsoft's hash_map implementation for VC++ 2005, the realpath cache 121 in PHP 5.x (php-5.2.3/TSRM/tsrm_virtual_cwd.c), and many other uses. 123 A study has recommended FNV in connection with the IPv6 Flow Label 124 field [IPv6flow]. 126 FNV hash algorithms and source code have been released into the 127 public domain. The authors of the FNV algorithm took deliberate steps 128 to disclose the algorithm in a public forum soon after it was 129 invented. More than a year passed after this public disclosure and 130 the authors deliberately took no steps to patent the FNV algorithm. 131 Therefore, it is safe to say that the FNV authors have no patent 132 claims on the FNV algorithm as published. 134 If you use an FNV function in an application, you are kindly 135 requested to send an EMail about it to: fnv-mail@asthe.com 137 2. FNV Basics 139 This document focuses on the FNV-1a function whose pseudo-code is as 140 follows: 142 hash = offset_basis 143 for each octet_of_data to be hashed 144 hash = hash xor octet_of_data 145 hash = hash * FNV_Prime 146 return hash 148 In the pseudo-code above, hash is a power-of-two number of bits (32, 149 64, ... 1024) and offset_basis and FNV_Prime depend on the size of 150 hash. 152 The FNV-1 algorithm is the same, including the values of offset_basis 153 and FNV_Prime, except that the order of the two lines with the "xor" 154 and multiply operations are reversed. Operational experience 155 indicates better hash dispersion for small amounts of data with 156 FNV-1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero. 157 FNV-1a is suggested for general use. 159 2.1 FNV Primes 161 The theory behind FNV_Prime's is beyond the scope of this document 162 but the basic property to look for is how an FNV_Prime would impact 163 dispersion. Now, consider any n-bit FNV hash where n is >= 32 and 164 also a power of 2, in particular n = 2**s. For each such n-bit FNV 165 hash, an FNV_Prime p is defined as: 167 When s is an integer and 4 < s < 11, then FNV_Prime is the 168 smallest prime p of the form: 170 256**int((5 + 2**s)/12) + 2**8 + b 172 where b is an integer such that: 174 0 < b < 2**8 175 The number of one-bits in b is 4 or 5 177 and where ( p mod (2**40 - 2**24 - 1) ) > (2**24 + 2**8 + 2**7). 179 Experimentally, FNV_Primes matching the above constraints tend to 180 have better dispersion properties. They improve the polynomial 181 feedback characteristic when an FNV_Prime multiplies an intermediate 182 hash value. As such, the hash values produced are more scattered 183 throughout the n-bit hash space. 185 The case where s < 5 is not considered because the resulting hash 186 quality is too low. Such small hashes can, if desired, be derived 187 from a 32 bit FNV hash by XOR folding (see Section 3). The case where 188 s > 10 is not considered because of the doubtful utility of such 189 large FNV hashes and because the criteria for such large FNV_Primes 190 is more complex, due to the sparsity of such large primes, and would 191 needlessly clutter the criteria given above. 193 Per the above constraints, an FNV_Prime should have only 6 or 7 one- 194 bits in it. Therefore, some compilers may seek to improve the 195 performance of a multiplication with an FNV_Prime by replacing the 196 multiplication with shifts and adds. However, note that the 197 performance of this substitution is highly hardware-dependent and 198 should be done with care. FNV_Primes were selected primarily for the 199 quality of resulting hash function, not for compiler optimization. 201 2.2 FNV offset_basis 203 The offset_basis values for the n-bit FNV-1a algorithms are computed 204 by applying the n-bit FNV-0 algorithm to the 32 octets representing 205 the following character string in [RFC20]: 207 chongo /\../\ 209 The \'s in the above string are not C-style escape characters. In C- 210 string notation, these 32 octets are: 212 "chongo /\\../\\" 214 That string was used because the person testing FNV with non-zero 215 offset_basis values was looking at an email message from Landon and 216 was copying his standard email signature line; however, they couldn't 217 see very well and copied it incorrectly. In fact, he uses 219 chongo (Landon Curt Noll) /\oo/\ 221 but, since it doesn't matter, no effort has been made to correct 222 this. 224 In the general case, almost any offset_basis will serve so long as it 225 is non-zero. The choice of a non-standard offset_basis may be 226 beneficial in defending against some attacks that try to induce hash 227 collisions. 229 2.3 FNV Endianism 231 For persistent storage or interoperability between different hardware 232 platforms, an FNV hash shall be represented in the little endian 233 format. That is, the FNV hash will be stored in an array hash[N] with 234 N bytes such that its integer value can be retrieved as follows: 236 unsigned char hash[N]; 237 for ( i = N-1, value = 0; i >= 0; --i ) 238 value = ( value << 8 ) + hash[i]; 240 Of course, when FNV hashes are used in a single process or a group of 241 processes sharing memory on processors with compatible endian-ness, 242 the natural endian-ness of those processors can be used regardless of 243 its type, little, big, or some other exotic form. 245 The code provided in Section 6 has FNV hash functions that return a 246 little endian byte vector. Because they are slightly more efficient, 247 code returning FNV hashes of 32-bit or 64-bit size as integers, on 248 computers supporting integers of those sides, are also provided. Such 249 integers are compatible with the same size byte vectors on little 250 endian computers but use of the functions returning integers on big 251 endian or other non-little-endian machines will be byte-reversed or 252 otherwise incompatible with the byte vectors. 254 3. Other Hash Sizes and XOR Folding 256 Many hash uses require a hash that is not one of the FNV sizes for 257 which constants are provided in Section 5. If a larger hash size is 258 needed, please contact the authors of this document. 260 Most hash applications make use of a hash that is a fixed size binary 261 field. Assume that k bits of hash are desired and k is less than 1024 262 but not one of the sizes for which constants are provided in Section 263 5. The recommended technique is to take the smallest FNV hash of size 264 S, where S is larger than k, and calculate the desired k-bit-hash 265 using xor folding as shown below. The final bit masking operation is 266 logically unnecessary if the size of the variable k-bit-hash is 267 exactly k bits. 269 temp = FNV_S ( data-to-be-hashed ) 270 k-bit-hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 ) 272 Hash functions are a trade-off between speed and strength. For 273 example, a somewhat stronger hash may be obtained for exact FNV sizes 274 by calculating an FNV twice as long as the desired output ( S = 2*k ) 275 and performing such data folding using a k equal to the size of the 276 desired output. However, if a much stronger hash, for example one 277 suitable for cryptographic applications, is wanted, algorithms 278 designed for that purpose, such as those in [RFC6234], should be 279 used. 281 If it is desired to obtain a hash result that is a value between 0 282 and max, where max+1 is a not a power of two, simply choose an FNV 283 hash size S such that 2**S > max. Then calculate the following: 285 FNV_S mod ( max+1 ) 287 The resulting remainder will be in the range desired but will suffer 288 from a bias against large values with the bias being larger if 2**S 289 is only a little bigger than max. If this bias is acceptable, no 290 further processing is needed. If this bias is unacceptable, it can be 291 avoided by retrying for certain high values of hash, as follows, 292 before applying the mod operation above: 294 X = ( int( ( 2**S - 1 ) / ( max+1 ) ) ) * ( max+1 ) 295 while ( hash >= X ) 296 hash = ( hash * FNV_Prime ) + offset_basis 298 4. Hashing Multiple Values Together 300 It is common for there to be a few different component values, say 301 three strings X, Y, and Z, where a hash over all of them is desired. 302 The simplest thing to do is to concatenate them and compute the hash 303 of that concatenation, as in 305 hash ( X | Y | Z ) 307 where the vertical bar character ("|") represents string 308 concatenation. Note that, for FNV, the same hash results if X, Y, 309 and Z are actually concatenated and the FNV hash applied to the 310 resulting string or if FNV is calculated on an initial substring and 311 the result used as the offset_basis when calculating the FNV hash of 312 the remainder of the string. This can be done several times. 313 Assuming FNVoffset_basis ( v, w ) is FNV of w using v as the 314 offset_basis, then in the example above, fnvx = FNV ( X ) could be 315 calculated and then fnvxy = FNVoffset_basis ( fnvx, Y ), and finally 316 fnvxyz = FNVoffset_basis ( fnvxy, Z). The resulting fnvxyz would be 317 the same as FNV ( X | Y | Z ); 319 Cases are also common where such a hash needs to be repeatedly 320 calculated where the component values vary but some vary more 321 frequently than others. For example, assume some sort of computer 322 network traffic flow ID, such as the IPv6 flow ID [RFC6437], is to be 323 calculated for network packets based on the source and destination 324 IPv6 address and the Traffic Class [RFC2460]. If the Flow ID is 325 calculated in the originating host, the source IPv6 address would 326 likely always be the same or perhaps assume one of a very small 327 number of values. By placing this quasi-constant IPv6 source address 328 first in the string being FNV hashed, FNV ( IPv6source ) could be 329 calculated and used as the offset_basis for calculating FNV of the 330 IPv6 destination address and Traffic Class for each packet. As a 331 result, the per packet hash would be over 17 bytes rather than over 332 33 bytes saving computational resources. The code in this document 333 includes functions facilitating the use of a non-standard 334 offset_basis. 336 5. FNV Constants 338 The FNV Primes are as follows: 340 32 bit FNV_Prime = 2**24 + 2**8 + 0x93 = 16,777,619 341 = 0x01000193 343 64 bit FNV_Prime = 2**40 + 2**8 + 0xB3 = 1,099,511,628,211 344 = 0x00000100 000001B3 346 128 bit FNV_Prime = 2**88 + 2**8 + 0x3B = 347 309,485,009,821,345,068,724,781,371 348 = 0x00000000 01000000 00000000 0000013B 350 256 bit FNV_Prime = 2**168 + 2**8 + 0x63 = 351 374,144,419,156,711,147,060,143,317,175,368,453,031,918,731,002,211 = 352 0x0000000000000000 0000010000000000 0000000000000000 0000000000000163 354 512 bit FNV_Prime = 2**344 + 2**8 + 0x57 = 35, 355 835,915,874,844,867,368,919,076,489,095,108,449,946,327,955,754,392, 356 558,399,825,615,420,669,938,882,575,126,094,039,892,345,713,852,759 = 357 0x0000000000000000 0000000000000000 0000000001000000 0000000000000000 358 0000000000000000 0000000000000000 0000000000000000 0000000000000157 360 1024 bit FNV_Prime = 2**680 + 2**8 + 0x8D = 5, 361 016,456,510,113,118,655,434,598,811,035,278,955,030,765,345,404,790, 362 744,303,017,523,831,112,055,108,147,451,509,157,692,220,295,382,716, 363 162,651,878,526,895,249,385,292,291,816,524,375,083,746,691,371,804, 364 094,271,873,160,484,737,966,720,260,389,217,684,476,157,468,082,573 = 365 0x0000000000000000 0000000000000000 0000000000000000 0000000000000000 366 0000000000000000 0000010000000000 0000000000000000 0000000000000000 367 0000000000000000 0000000000000000 0000000000000000 0000000000000000 368 0000000000000000 0000000000000000 0000000000000000 000000000000018D 370 The FNV offset_basis values are as follows: 372 32 bit offset_basis = 2,166,136,261 = 0x811C9DC5 374 64 bit offset_basis = 14695981039346656037 = 0xCBF29CE4 84222325 376 128 bit offset_basis = 144066263297769815596495629667062367629 = 377 0x6C62272E 07BB0142 62B82175 6295C58D 379 256 bit offset_basis = 100,029,257,958,052,580,907,070,968, 380 620,625,704,837,092,796,014,241,193,945,225,284,501,741,471,925,557 = 381 0xDD268DBCAAC55036 2D98C384C4E576CC C8B1536847B6BBB3 1023B4C8CAEE0535 382 512 bit offset_basis = 9, 383 659,303,129,496,669,498,009,435,400,716,310,466,090,418,745,672,637, 384 896,108,374,329,434,462,657,994,582,932,197,716,438,449,813,051,892, 385 206,539,805,784,495,328,239,340,083,876,191,928,701,583,869,517,785 = 386 0xB86DB0B1171F4416 DCA1E50F309990AC AC87D059C9000000 0000000000000D21 387 E948F68A34C192F6 2EA79BC942DBE7CE 182036415F56E34B AC982AAC4AFE9FD9 389 1024 bit offset_basis = 14,197,795,064,947,621,068,722,070,641,403, 390 218,320,880,622,795,441,933,960,878,474,914,617,582,723,252,296,732, 391 303,717,722,150,864,096,521,202,355,549,365,628,174,669,108,571,814, 392 760,471,015,076,148,029,755,969,804,077,320,157,692,458,563,003,215, 393 304,957,150,157,403,644,460,363,550,505,412,711,285,966,361,610,267, 394 868,082,893,823,963,790,439,336,411,086,884,584,107,735,010,676,915 = 395 0x0000000000000000 005F7A76758ECC4D 32E56D5A591028B7 4B29FC4223FDADA1 396 6C3BF34EDA3674DA 9A21D90000000000 0000000000000000 0000000000000000 397 0000000000000000 0000000000000000 0000000000000000 000000000004C6D7 398 EB6E73802734510A 555F256CC005AE55 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 400 6. The Source Code 402 [THIS CODE IS BEING WORKING AND IS INCONSISTENT AS BELOW.] 404 The following sub-sections provide reference C source code and a test 405 driver for FNV-1a. 407 Alternative source code, including 32 and 64 bit FNV-1 and FNV-1a in 408 x86 assembler, is currently available at [FNV]. 410 Section 6.2 provides a test driver. 412 6.1 FNV-1a C Code 414 This section provides the direct FNV-1a function for each of the 415 lengths for which it is specified in this document. The functions 416 provided are listed below. Those whose name is of the form FNVxxxB* 417 output a byte vector that will be compatible between systems of 418 different endian-ness, where xxx is "32", "64", "128", "256", "512", 419 or "1024". Those whose name is of the form FNVxxx* (with no "B" after 420 the xxx) return an integer and are NOT compatible between systems of 421 different endian-ness. These integer based functions exist only for 422 xxx of "32" and, on systems supporting 64-bit integers, "64". 424 FNVxxxstring, FNVxxxblock: 425 FNVxxxBstring, FNVxxxBblock: These are simple functions for directly 426 returning the FNV hash of a zero terminated byte string not 427 including the zero and the FNV hash of a counted block of 428 bytes. Note that for applications of FNV-32 where 32-bit 429 integers are supported and FNV-64 where 64-bit integers are 430 supported and an integer data type output is acceptable, the 431 code is sufficiently simple that, to maximize performance, use 432 of open coding or macros may be more appropriate than calling a 433 subroutine. 435 FNVxxxinit, FNVxxxinitBasis: 436 FNVxxxBinit, FNVxxxBinitBasis: These functions and the next two sets 437 of functions below provide facilities for incrementally 438 calculating FNV hashes. They all assume a data structure of 439 type FNVxxx(B)context that holds the current state of the hash. 440 FNVxxx(B)init initializes that context to the standard 441 offset_basis. FNVxxx(B)initBasis takes an offset_basis value as 442 a parameter and may be useful for hashing concatenations, as 443 described in Section 4, as well as for simply using a non- 444 standard offset_basis. 446 FNVxxxblockin, FNVxxxstringin: 447 FNVxxxBblockin, FNVxxxBstringin: These functions hash a sequence of 448 bytes into an FNVxxx(B)context that was originally initialized 449 by FNVxxx(B)init or FNVxxx(B)initBasis. FNVxxx(B)blockin hashes 450 in a counted block of bytes. FNVxxx(B)stringin hashes in a zero 451 terminated byte string not incuding the final zero. 453 FNVxxxresult: 454 FNVxxxBresult: This function extracts the final FNV hash result from 455 an FNVxxx(B)context. 457 The following code is a private header file used by all the FNV 458 functions further below and which states the terms for use and 459 redistribution of all of this code. 461 462 /************************ fnv-private.h ************************/ 463 /****************** See RFC NNNN for details *******************/ 464 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 465 * authors of the code. All rights reserved. 466 * 467 * Redistribution and use in source and binary forms, with or without 468 * modification, are permitted provided that the following conditions 469 * are met: 470 * 471 * * Redistributions of source code must retain the above copyright 472 * notice, this list of conditions and the following disclaimer. 473 * 474 * * Redistributions in binary form must reproduce the above copyright 475 * notice, this list of conditions and the following disclaimer in 476 * the documentation and/or other materials provided with the 477 * distribution. 478 * 479 * * Neither the name of Internet Society, IETF or IETF Trust, nor the 480 * names of specific contributors, may be used to endorse or promote 481 * products derived from this software without specific prior 482 * written permission. 483 * 484 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 485 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 486 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 487 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 488 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 489 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 490 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 491 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 492 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 493 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 494 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 495 * POSSIBILITY OF SUCH DAMAGE. 497 */ 499 #ifndef _FNV_PRIVATE_H_ 500 #define _FNV_PRIVATE_H_ 502 /* 503 * Six FNV-1a hashes are defined with these sizes: 504 * FNV32 32 bits, 4 bytes 505 * FNV64 64 bits, 8 bytes 506 * FNV128 128 bits, 16 bytes 507 * FNV256 256 bits, 32 bytes 508 * FNV512 512 bits, 64 bytes 509 * FNV1024 1024 bits, 128 bytes 510 */ 512 /* Private stuff used by this implementation of the FNV 513 * (Fowler, Noll, Vo) non-cryptographic hash function FNV-1a. 514 * External callers don't need to know any of this. */ 516 enum { /* State value bases for context->Computed */ 517 FNVinited = 22, 518 FNVcomputed = 76, 519 FNVemptied = 220, 520 FNVclobber = 122 /* known bad value for testing */ 521 }; 523 /* Deltas to assure distinct state values for different lengths */ 524 enum { 525 FNV32state = 1, 526 FNV32Bstate = 17, 527 FNV64state = 3, 528 FNV64Bstate = 19, 529 FNV128state = 5, 530 FNV256state = 7, 531 FNV512state = 11, 532 FNV1024state = 13 533 }; 535 #endif 536 538 The following code is a simple header file to include all the 539 specific length FNV header files. 541 542 /****************************** FNV.h *******************************/ 543 /******************* See RFC NNNN for details. **********************/ 544 /* 545 * Copyright (c) 2016, 2017 IETF Trust and the persons identified as 546 * authors of the code. All rights reserved. 548 * See fnv-private.h for terms of use and redistribution. 549 */ 551 #ifndef _FNV_H_ 552 #define _FNV_H_ 554 #include "FNV32.h" 555 #include "FNV32B.h" 556 #ifdef FNV_64bitIntegers 557 # include "FNV64.h" 558 #endif /* FNV_64bitIntegers */ 559 #include "FNV64B.h" 560 #include "FNV128.h" 561 #include "FNV256.h" 562 #include "FNV512.h" 563 #include "FNV1024.h" 565 #endif /* _FNV_H_ */ 566 568 The following code is a simple header file to control configuration 569 related to big integer and big endian support. 571 572 /*************************** FNVconfig.h ****************************/ 573 /******************* See RFC NNNN for details. **********************/ 574 /* 575 * Copyright (c) 2016, 2017 IETF Trust and the persons identified as 576 * authors of the code. All rights reserved. 577 * See fnv-private.h for terms of use and redistribution. 578 */ 580 #ifndef _FNVconfig_H_ 581 #define _FNVconfig_H_ 583 /* 584 * Description: 585 * This file provides configuration ifdefs for the 586 * FNV-1a non-cryptographic hash algorithms. 587 * 588 * >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */ 590 /* FNV_64bitIntegers - Define this if your system supports 64-bit 591 * arithmetic including 32-bit x 32-bit multiplication 592 * producing a 64-bit product. If undefined, it will be 593 * assumed that 32-bit arithmetic is supported including 594 * 16-bit x 16-bit multiplication producing a 32-bit result. 595 */ 596 // #define FNV_64bitIntegers 597 /* 598 * The following allow the FNV test program to override the 599 * above configuration settings. 600 */ 602 #ifdef FNV_TEST_PROGRAM 603 # ifdef TEST_FNV_64bitIntegers 604 # ifndef FNV_64bitIntegers 605 # define FNV_64bitIntegers 606 # endif 607 # else 608 # undef FNV_64bitIntegers 609 # endif 610 # ifndef FNV_64bitIntegers /* causes an error if uint64_t is used */ 611 # define uint64_t foobar /* RFC 3092 */ 612 # endif 613 #endif 615 #endif /* _FNVconfig_H_ */ 616 618 6.1.1 FNV32 Code 620 The header and C source for 32-bit FNV-1a returning a 32-bit integer. 622 623 /***************************** FNV32.h ******************************/ 624 /******************** See RFC NNNN for details **********************/ 625 /* 626 * Copyright (c) 2016 IETF Trust and the persons identified as 627 * authors of the code. All rights reserved. 628 * See fnv-private.h for terms of use and redistribution. 629 */ 631 #ifndef _FNV32_H_ 632 #define _FNV32_H_ 634 #include "FNVconfig.h" 636 #include 637 /* #define FNV32size (32/8) not used */ 639 /* If you do not have the ISO standard stdint.h header file, then you 640 * must typedef the following types: 641 * 642 * type meaning 643 * uint32_t unsigned 32 bit integer 644 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 645 */ 647 #ifndef _FNV_ErrCodes_ 648 #define _FNV_ErrCodes_ 649 /******************************************************************** 650 * All FNV functions provided return as integer as follows: 651 * 0 -> success 652 * >0 -> error as listed below 653 */ 654 enum { /* success and errors */ 655 fnvSuccess = 0, 656 fnvNull, /* Null pointer parameter */ 657 fnvStateError, /* called Input after Result, etc. */ 658 fnvBadParam /* passed a bad parameter */ 659 }; 660 #endif /* _FNV_ErrCodes_ */ 662 /* 663 * This structure holds context information for an FNV32 hash 664 */ 665 typedef struct FNV32context_s { 666 int Computed; /* state */ 667 uint32_t Hash; 668 } FNV32context; 670 /* 671 * Function Prototypes 672 * FNV32string: hash a zero terminated string not including 673 * the terminating zero 674 * FNV32block: hash a specified length byte vector 675 * FNV32init: initializes an FNV32 context 676 * FNV32initBasis: initializes an FNV32 context with a 677 * provided basis 678 * FNV32blockin: hash in a specified length byte vector 679 * FNV32stringin: hash in a zero terminated string not 680 * including the zero 681 * FNV32result: returns the hash value 682 * 683 * Hash is returned as a 32-bit integer 684 */ 686 #ifdef __cplusplus 687 extern "C" { 688 #endif 690 /* FNV32 */ 691 extern int FNV32string ( const char *in, 692 uint32_t * const out ); 693 extern int FNV32block ( const void *in, 694 long int inlength, 695 uint32_t * const out ); 696 extern int FNV32init ( FNV32context * const ); 697 extern int FNV32initBasis ( FNV32context * const, 698 uint32_t basis ); 699 extern int FNV32blockin ( FNV32context * const, 700 const void *in, 701 long int inlength ); 702 extern int FNV32stringin ( FNV32context * const, 703 const char *in ); 704 extern int FNV32result ( FNV32context * const, 705 uint32_t * const out ); 707 #ifdef __cplusplus 708 } 709 #endif 711 #endif /* _FNV32_H_ */ 712 714 715 /**************************** FNV32.c ****************************/ 716 /****************** See RFC NNNN for details. ********************/ 717 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified 718 * as authors of the code. All rights reserved. 719 * See fnv-private.h for terms of use and redistribution. 720 */ 722 /* This code implements the FNV (Fowler, Noll, Vo) non-cryptographic 723 * hash function FNV-1a for 32-bit hashes returning a 32-bit 724 * integer. 725 */ 727 #ifndef _FNV32_C_ 728 #define _FNV32_C_ 730 #include "fnv-private.h" 731 #include "FNV32.h" 733 /* 32 bit FNV_prime = 2^24 + 2^8 + 0x93 */ 734 #define FNV32prime 0x01000193 735 #define FNV32basis 0x811C9DC5 737 /* FNV32 hash a zero terminated string not including the zero 738 *********************************************************************/ 739 int FNV32string ( const char *in, uint32_t * const out ) 740 { 741 uint32_t temp; 742 uint8_t ch; 744 if ( in && out ) 745 { 746 temp = FNV32basis; 747 while ( (ch = *in++) ) 748 temp = FNV32prime * ( temp ^ ch ); 749 *out = temp; 750 return fnvSuccess; 751 } 752 return fnvNull; /* Null input pointer */ 753 } /* end FNV32string */ 755 /* FNV32 hash a counted block 756 ***************************************************************/ 757 int FNV32block ( const void *vin, 758 long int length, 759 uint32_t * const out ) 760 { 761 const uint8_t *in = (const uint8_t*)vin; 762 uint32_t temp; 764 if ( in && out ) 765 { 766 if ( length < 0 ) 767 return fnvBadParam; 768 for ( temp = FNV32basis; length > 0; length-- ) 769 temp = FNV32prime * ( temp ^ *in++ ); 770 *out = temp; 771 return fnvSuccess; 772 } 773 return fnvNull; /* Null input pointer */ 774 } /* end FNV32block */ 776 /*************************************************************** 777 * Set of init, input, and output functions below * 778 * to incrementally compute FNV32 * 779 ***************************************************************/ 781 /* initialize context 782 ***************************************************************/ 783 int FNV32init ( FNV32context * const ctx ) 784 { 785 return FNV32initBasis ( ctx, FNV32basis ); 786 } /* end FNV32init */ 788 /* initialize context with a provided basis 789 ***************************************************************/ 790 int FNV32initBasis ( FNV32context * const ctx, uint32_t basis ) 791 { 792 if ( ctx ) 793 { 794 ctx->Hash = basis; 795 ctx->Computed = FNVinited+FNV32state; 796 return fnvSuccess; 797 } 798 return fnvNull; 799 } /* end FNV32initBasis */ 801 /* hash in a counted block 802 ***************************************************************/ 803 int FNV32blockin ( FNV32context * const ctx, 804 const void *vin, 805 long int length ) 806 { 807 const uint8_t *in = (const uint8_t*)vin; 808 uint32_t temp; 810 if ( ctx && in ) 811 { 812 if ( length < 0 ) 813 return fnvBadParam; 814 switch ( ctx->Computed ) 815 { 816 case FNVinited+FNV32state: 817 ctx->Computed = FNVcomputed+FNV32state; 818 case FNVcomputed+FNV32state: 819 break; 820 default: 821 return fnvStateError; 822 } 823 for ( temp = ctx->Hash; length > 0; length-- ) 824 temp = FNV32prime * ( temp ^ *in++ ); 825 ctx->Hash = temp; 826 return fnvSuccess; 827 } 828 return fnvNull; 829 } /* end FNV32blockin */ 831 /* hash in a zero terminated string not including the zero 832 ***************************************************************/ 833 int FNV32stringin ( FNV32context * const ctx, 834 const char *in ) 835 { 836 uint32_t temp; 837 uint8_t ch; 839 if ( ctx && in ) 840 { 841 switch ( ctx->Computed ) 842 { 843 case FNVinited+FNV32state: 845 ctx->Computed = FNVcomputed+FNV32state; 846 case FNVcomputed+FNV32state: 847 break; 848 default: 849 return fnvStateError; 850 } 851 temp = ctx->Hash; 852 while ( (ch = (uint8_t)*in++) ) 853 temp = FNV32prime * ( temp ^ ch ); 854 ctx->Hash = temp; 855 return fnvSuccess; 856 } 857 return fnvNull; 858 } /* end FNV32stringin */ 860 /* return hash 861 ***************************************************************/ 862 int FNV32result ( FNV32context * const ctx, 863 uint32_t * const out ) 864 { 865 if ( ctx && out ) 866 { 867 if ( ctx->Computed != FNVcomputed+FNV32state ) 868 return fnvStateError; 869 ctx->Computed = FNVemptied+FNV32state; 870 *out = ctx->Hash; 871 ctx->Hash = 0; 872 return fnvSuccess; 873 } 874 return fnvNull; 875 } /* end FNV32result */ 877 #endif /* _FNV32_C_ */ 878 880 The header and C source for 32-bit FNV-1a returning a byte vector. 882 883 /***************************** FNV32B.h *****************************/ 884 /******************** See RFC NNNN for details **********************/ 885 /* 886 * Copyright (c) 2016, 2017 IETF Trust and the persons identified as 887 * authors of the code. All rights reserved. 888 * See fnv-private.h for terms of use and redistribution. 889 */ 891 #ifndef _FNV32_H_ 892 #define _FNV32_H_ 894 #include "FNVconfig.h" 895 #include 896 #define FNV32size (32/8) 898 /* If you do not have the ISO standard stdint.h header file, then you 899 * must typedef the following types: 900 * 901 * type meaning 902 * uint32_t unsigned 32 bit integer 903 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 904 */ 906 #ifndef _FNV_ErrCodes_ 907 #define _FNV_ErrCodes_ 908 /******************************************************************** 909 * All FNV functions provided return as integer as follows: 910 * 0 -> success 911 * >0 -> error as listed below 912 */ 913 enum { /* success and errors */ 914 fnvSuccess = 0, 915 fnvNull, /* Null pointer parameter */ 916 fnvStateError, /* called Input after Result, etc. */ 917 fnvBadParam /* passed a bad parameter */ 918 }; 919 #endif /* _FNV_ErrCodes_ */ 921 /* 922 * This structure holds context information for an FNV32 hash 923 */ 924 typedef struct FNV32Bcontext_s { 925 int Computed; /* state */ 926 uint32_t Hash; 927 } FNV32Bcontext; 929 /* 930 * Function Prototypes 931 * FNV32Bstring: hash a zero terminated string not including 932 * the terminating zero 933 * FNV32Bblock: hash a specified length byte vector 934 * FNV32Binit: initializes an FNV32 context 935 * FNV32BinitBasis: initializes an FNV32 context with a 936 * provided basis 937 * FNV32Bblockin: hash in a specified length byte vector 938 * FNV32Bstringin: hash in a zero terminated string not 939 * including the zero 940 * FNV32Bresult: returns the hash value 941 * 942 * Hash is returned as a 32-bit integer 943 */ 945 #ifdef __cplusplus 946 extern "C" { 947 #endif 949 /* FNV32 */ 950 extern int FNV32Bstring ( const char *in, 951 uint8_t * const out[FNV32size] ); 952 extern int FNV32Bblock ( const void *in, 953 long int inlength, 954 uint8_t * const out[FNV32size] ); 955 extern int FNV32Binit ( FNV32Bcontext * const ); 956 extern int FNV32BinitBasis ( FNV32Bcontext * const, 957 uint32_t basis ); 958 extern int FNV32Bblockin ( FNV32Bcontext * const, 959 const void *in, 960 long int inlength ); 961 extern int FNV32Bstringin ( FNV32Bcontext * const, 962 const char *in ); 963 extern int FNV32Bresult ( FNV32Bcontext * const, 964 int8_t * const out[FNV32size] ); 966 #ifdef __cplusplus 967 } 968 #endif 970 #endif /* _FNV32_H_ */ 971 973 974 /**************************** FNV32B.c ***************************/ 975 /****************** See RFC NNNN for details. ********************/ 976 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 977 * authors of the code. All rights reserved. 978 * See fnv-private.h for terms of use and redistribution. 979 */ 981 /* This code implements the FNV (Fowler, Noll, Vo) non-cryptographic 982 * hash function FNV-1a for 32-bit hashes returning a byte vector. 983 */ 985 #ifndef _FNV32_C_ 986 #define _FNV32_C_ 988 #include "fnv-private.h" 989 #include "FNV32B.h" 991 /* 32 bit FNV_prime = 2^24 + 2^8 + 0x93 */ 992 #define FNV32prime 0x01000193 993 #define FNV32basis 0x811C9DC5 994 /* FNV32 hash a zero terminated string not including the zero 995 *******************************************************************/ 996 int FNV32Bstring ( const char *in, uint8_t * const out[FNV32size] ) 997 { 998 uint32_t temp; 999 uint8_t ch; 1001 if ( in && out ) 1002 { 1003 temp = FNV32basis; 1004 while ( (ch = *in++) ) 1005 temp = FNV32prime * ( temp ^ ch ); 1006 *out[0] = temp & 0xFF; 1007 temp =>> 8; 1008 *out[1] = temp & 0xFF; 1009 temp =>> 8; 1010 *out[2] = temp & 0xFF; 1011 temp =>> 8; 1012 *out[3] = temp & 0xFF; 1013 return fnvSuccess; 1014 } 1015 return fnvNull; /* Null input pointer */ 1016 } /* end FNV32Bstring */ 1018 /* FNV32 hash a counted block 1019 ***************************************************************/ 1020 int FNV32Bblock ( const void *vin, 1021 long int length, 1022 uint8_t * const out[FNV32size] ) 1023 { 1024 const uint8_t *in = (const uint8_t*)vin; 1025 uint32_t temp; 1027 if ( in && out ) 1028 { 1029 if ( length < 0 ) 1030 return fnvBadParam; 1031 for ( temp = FNV32basis; length > 0; length-- ) 1032 temp = FNV32prime * ( temp ^ *in++ ); 1033 *out[0] = temp & 0xFF; 1034 temp =>> 8; 1035 *out[1] = temp & 0xFF; 1036 temp =>> 8; 1037 *out[2] = temp & 0xFF; 1038 temp =>> 8; 1039 *out[3] = temp & 0xFF; 1040 *out = temp; 1041 return fnvSuccess; 1042 } 1043 return fnvNull; /* Null input pointer */ 1044 } /* end FNV32Bblock */ 1046 /*************************************************************** 1047 * Set of init, input, and output functions below * 1048 * to incrementally compute FNV32 * 1049 ***************************************************************/ 1051 /* initialize context 1052 ***************************************************************/ 1053 int FNV32Binit ( FNV32Bcontext * const ctx ) 1054 { 1055 return FNV32BinitBasis ( ctx, FNV32basis ); 1056 } /* end FNV32Binit */ 1058 /* initialize context with a provided basis 1059 ***************************************************************/ 1060 int FNV32BinitBasis ( FNV32Bcontext * const ctx, uint32_t basis ) 1061 { 1062 if ( ctx ) 1063 { 1064 ctx->Hash = basis; 1065 ctx->Computed = FNVinited+FNV32Bstate; 1066 return fnvSuccess; 1067 } 1068 return fnvNull; 1069 } /* end FNV32BinitBasis */ 1071 /* hash in a counted block 1072 ***************************************************************/ 1073 int FNV32Bblockin ( FNV32Bcontext * const ctx, 1074 const void *vin, 1075 long int length ) 1076 { 1077 const uint8_t *in = (const uint8_t*)vin; 1078 uint32_t temp; 1080 if ( ctx && in ) 1081 { 1082 if ( length < 0 ) 1083 return fnvBadParam; 1084 switch ( ctx->Computed ) 1085 { 1086 case FNVinited+FNV32Bstate: 1087 ctx->Computed = FNVcomputed+FNV32Bstate; 1088 case FNVcomputed+FNV32Bstate: 1089 break; 1090 default: 1091 return fnvStateError; 1092 } 1094 for ( temp = ctx->Hash; length > 0; length-- ) 1095 temp = FNV32prime * ( temp ^ *in++ ); 1096 ctx->Hash = temp; 1097 return fnvSuccess; 1098 } 1099 return fnvNull; 1100 } /* end FNV32Bblockin */ 1102 /* hash in a zero terminated string not including the zero 1103 ***************************************************************/ 1104 int FNV32Bstringin ( FNV32Bcontext * const ctx, 1105 const char *in ) 1106 { 1107 uint32_t temp; 1108 uint8_t ch; 1110 if ( ctx && in ) 1111 { 1112 switch ( ctx->Computed ) 1113 { 1114 case FNVinited+FNV32Bstate: 1115 ctx->Computed = FNVcomputed+FNV32Bstate; 1116 case FNVcomputed+FNV32Bstate: 1117 break; 1118 default: 1119 return fnvStateError; 1120 } 1121 temp = ctx->Hash; 1122 while ( (ch = (uint8_t)*in++) ) 1123 temp = FNV32prime * ( temp ^ ch ); 1124 ctx->Hash = temp; 1125 return fnvSuccess; 1126 } 1127 return fnvNull; 1128 } /* end FNV32Bstringin */ 1130 /* return hash 1131 ***************************************************************/ 1132 int FNV32Bresult ( FNV32Bcontext * const ctx, 1133 uint8_t * const out[FNV32size] ) 1134 { 1135 if ( ctx && out ) 1136 { 1137 if ( ctx->Computed != FNVcomputed+FNV32Bstate ) 1138 return fnvStateError; 1139 ctx->Computed = FNVemptied+FNV32Bstate; 1140 *out[0] = ctx->Hash & 0xFF; 1141 ctx->Hash =>> 8; 1142 *out[1] = ctx->Hash & 0xFF; 1143 ctx->Hash =>> 8; 1144 *out[2] = ctx->Hash & 0xFF; 1145 ctx->Hash =>> 8; 1146 *out[3] = ctx->Hash & 0xFF; 1147 ctx->Hash = 0; 1148 return fnvSuccess; 1149 } 1150 return fnvNull; 1151 } /* end FNV32Bresult */ 1153 #endif /* _FNV32_C_ */ 1154 1156 6.1.2 FNV64 C Code 1158 The header and C source for 64-bit FNV-1a returning a 64-bit integer. 1160 1161 /***************************** FNV64.h ******************************/ 1162 /******************* See RFC NNNN for details. **********************/ 1163 /* 1164 * Copyright (c) 2016 IETF Trust and the persons identified as 1165 * authors of the code. All rights reserved. 1166 * See fnv-private.h for terms of use and redistribution. 1167 */ 1169 #ifndef _FNV64_H_ 1170 #define _FNV64_H_ 1172 /* 1173 * Description: 1174 * This file provides headers for the 64-bit version of the FNV-1a 1175 * non-cryptographic hash algorithm. 1176 */ 1178 #include "FNVconfig.h" 1180 #include 1181 #define FNV64size (64/8) 1183 /* If you do not have the ISO standard stdint.h header file, then you 1184 * must typedef the following types: 1185 * 1186 * type meaning 1187 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 1188 * uint32_t unsigned 32 bit integer 1189 * uint16_t unsigned 16 bit integer 1190 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 1191 */ 1193 #ifndef _FNV_ErrCodes_ 1194 #define _FNV_ErrCodes_ 1195 /********************************************************************* 1196 * All FNV functions provided return as integer as follows: 1197 * 0 -> success 1198 * >0 -> error as listed below 1199 */ 1200 enum { /* success and errors */ 1201 fnvSuccess = 0, 1202 fnvNull, /* Null pointer parameter */ 1203 fnvStateError, /* called Input after Result, etc. */ 1204 fnvBadParam /* passed a bad parameter */ 1205 }; 1206 #endif /* _FNV_ErrCodes_ */ 1208 /* 1209 * This structure holds context information for an FNV64 hash 1210 */ 1211 #ifdef FNV_64bitIntegers 1212 /* version if 64 bit integers supported */ 1214 typedef struct FNV64context_s { 1215 int Computed; /* state */ 1216 uint64_t Hash; 1217 } FNV64context; 1219 #else 1220 /* version if 64 bit integers NOT supported */ 1222 typedef struct FNV64context_s { 1223 int Computed; /* state */ 1224 uint16_t Hash[FNV64size/2]; 1225 } FNV64context; 1227 #endif /* FNV_64bitIntegers */ 1229 /* 1230 * Function Prototypes 1231 * FNV64string: hash a zero terminated string not including 1232 * the terminating zero 1233 * FNV64block: FNV64 hash a specified length byte vector 1234 * FNV64init: initializes an FNV64 context 1235 * FNV64initBasis: initializes an FNV64 context with a 1236 * provided basis 1237 * FNV64blockin: hash in a specified length byte vector 1238 * FNV64stringin: hash in a zero terminated string not 1239 * incluing the zero 1240 * FNV64result: returns the hash value 1241 * 1242 * Hash is returned as a 64-bit integer if supported, otherwise 1243 * as a vector of 8-bit integers 1244 */ 1246 #ifdef __cplusplus 1247 extern "C" { 1248 #endif 1250 /* FNV64 */ 1251 extern int FNV64init ( FNV64context * const ); 1252 extern int FNV64blockin ( FNV64context * const, 1253 const void * in, 1254 long int length ); 1255 extern int FNV64stringin ( FNV64context * const, 1256 const char * in ); 1258 #ifdef FNV_64bitIntegers 1259 extern int FNV64string ( const char *in, 1260 uint64_t * const out ); 1261 extern int FNV64block ( const void *in, 1262 long int length, 1263 uint64_t * const out ); 1264 extern int FNV64initBasis ( FNV64context * const, 1265 uint64_t basis ); 1266 extern int FNV64result ( FNV64context * const, 1267 uint64_t * const out ); 1268 #else 1269 extern int FNV64string ( const char *in, 1270 uint8_t out[FNV64size] ); 1271 extern int FNV64block ( const void *in, 1272 long int length, 1273 uint8_t out[FNV64size] ); 1274 extern int FNV64initBasis ( FNV64context * const, 1275 const uint8_t basis[FNV64size] ); 1276 extern int FNV64result ( FNV64context * const, 1277 uint8_t out[FNV64size] ); 1278 #endif /* FNV_64bitIntegers */ 1280 #ifdef __cplusplus 1281 } 1282 #endif 1284 #endif /* _FNV64_H_ */ 1285 1287 1288 /***************************** FNV64.c ******************************/ 1289 /******************** See RFC NNNN for details **********************/ 1290 /* Copyright (c) 2016 IETF Trust and the persons identified as 1291 * authors of the code. All rights reserved. 1292 * See fnv-private.h for terms of use and redistribution. 1294 */ 1296 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 1297 * hash function FNV-1a for 64-bit hashes. 1298 */ 1300 #ifndef _FNV64_C_ 1301 #define _FNV64_C_ 1303 #include "fnv-private.h" 1304 #include "FNV64.h" 1306 /******************************************************************** 1307 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1308 ********************************************************************/ 1309 #ifdef FNV_64bitIntegers 1311 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 1312 #define FNV64prime 0x00000100000001B3 1313 #define FNV64basis 0xCBF29CE484222325 1315 /* FNV64 hash a null terminated string (64 bit) 1316 ********************************************************************/ 1317 int FNV64string ( const char *in, uint64_t * const out ) 1318 { 1319 uint64_t temp; 1320 uint8_t ch; 1322 if ( in && out ) 1323 { 1324 temp = FNV64basis; 1325 while ( (ch = *in++) ) 1326 temp = FNV64prime * ( temp ^ ch ); 1327 #ifdef FNV_BigEndian 1328 FNV64reverse ( out, temp ); 1329 #else 1330 *out = temp; 1331 #endif 1332 return fnvSuccess; 1333 } 1334 return fnvNull; /* Null input pointer */ 1335 } /* end FNV64string */ 1337 /* FNV64 hash a counted block (64 bit) 1338 ********************************************************************/ 1339 int FNV64block ( const void *vin, 1340 long int length, 1341 uint64_t * const out ) 1342 { 1343 const uint8_t *in = (const uint8_t*)vin; 1344 uint64_t temp; 1346 if ( in && out ) 1347 { 1348 if ( length < 0 ) 1349 return fnvBadParam; 1350 for ( temp = FNV64basis; length > 0; length-- ) 1351 temp = FNV64prime * ( temp ^ *in++ ); 1352 #ifdef FNV_BigEndian 1353 FNV64reverse ( out, temp ); 1354 #else 1355 *out = temp; 1356 #endif 1357 return fnvSuccess; 1358 } 1359 return fnvNull; /* Null input pointer */ 1360 } /* end FNV64block */ 1362 #ifdef FNV_BigEndian 1364 /* Store a Big Endian result back as Little Endian 1365 ***************************************************************/ 1366 static void FNV64reverse ( uint64_t *out, uint64_t hash ) 1367 { 1368 uint64_t temp; 1369 int i; 1371 temp = hash & 0xFF; 1372 for ( i = FNV64size - 1; i > 0; i-- ) 1373 { 1374 hash >>= 8; 1375 temp = ( temp << 8 ) + ( hash & 0xFF ); 1376 } 1377 *out = temp; 1378 } /* end FNV64reverse */ 1380 #endif /* FNV_BigEndian */ 1382 /******************************************************************** 1383 * Set of init, input, and output functions below * 1384 * to incrementally compute FNV64 * 1385 ********************************************************************/ 1387 /* initialize context (64 bit) 1388 ********************************************************************/ 1389 int FNV64init ( FNV64context * const ctx ) 1390 { 1391 return FNV64initBasis ( ctx, FNV64basis ); 1392 } /* end FNV64init */ 1393 /* initialize context with a provided basis (64 bit) 1394 ********************************************************************/ 1395 int FNV64initBasis ( FNV64context * const ctx, uint64_t basis ) 1396 { 1397 if ( ctx ) 1398 { 1399 ctx->Hash = basis; 1400 ctx->Computed = FNVinited+FNV64state; 1401 return fnvSuccess; 1402 } 1403 return fnvNull; 1404 } /* end FNV64initBasis */ 1406 /* hash in a counted block (64 bit) 1407 ********************************************************************/ 1408 int FNV64blockin ( FNV64context * const ctx, 1409 const void *vin, 1410 long int length ) 1411 { 1412 const uint8_t *in = (const uint8_t*)vin; 1413 uint64_t temp; 1415 if ( ctx && in ) 1416 { 1417 if ( length < 0 ) 1418 return fnvBadParam; 1419 switch ( ctx->Computed ) 1420 { 1421 case FNVinited+FNV64state: 1422 ctx->Computed = FNVcomputed+FNV64state; 1423 case FNVcomputed+FNV64state: 1424 break; 1425 default: 1426 return fnvStateError; 1427 } 1428 for ( temp = ctx->Hash; length > 0; length-- ) 1429 temp = FNV64prime * ( temp ^ *in++ ); 1430 ctx->Hash = temp; 1431 return fnvSuccess; 1432 } 1433 return fnvNull; 1434 } /* end FNV64input */ 1436 /* hash in a zero terminated string not including the zero (64 bit) 1437 ********************************************************************/ 1438 int FNV64stringin ( FNV64context * const ctx, 1439 const char *in ) 1440 { 1441 uint64_t temp; 1442 uint8_t ch; 1443 if ( ctx && in ) 1444 { 1445 switch ( ctx->Computed ) 1446 { 1447 case FNVinited+FNV64state: 1448 ctx->Computed = FNVcomputed+FNV64state; 1449 case FNVcomputed+FNV64state: 1450 break; 1451 default: 1452 return fnvStateError; 1453 } 1454 temp = ctx->Hash; 1455 while ( (ch = *in++) ) 1456 temp = FNV64prime * ( temp ^ ch ); 1457 ctx->Hash = temp; 1458 return fnvSuccess; 1459 } 1460 return fnvNull; 1461 } /* end FNV64stringin */ 1463 /* return hash (64 bit) 1464 ********************************************************************/ 1465 int FNV64result ( FNV64context * const ctx, 1466 uint64_t * const out ) 1467 { 1468 if ( ctx && out ) 1469 { 1470 if ( ctx->Computed != FNVcomputed+FNV64state ) 1471 return fnvStateError; 1472 ctx->Computed = FNVemptied+FNV64state; 1473 #ifdef FNV_BigEndian 1474 FNV64reverse ( out, ctx->Hash ); 1475 #else 1476 *out = ctx->Hash; 1477 #endif 1478 ctx->Hash = 0; 1479 return fnvSuccess; 1480 } 1481 return fnvNull; 1482 } /* end FNV64result */ 1484 /****************************************************************** 1485 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1486 ******************************************************************/ 1487 #else /* FNV_64bitIntegers */ 1488 /****************************************************************** 1489 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1490 ******************************************************************/ 1492 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 1493 /* #define FNV64prime 0x00000100000001B3 */ 1494 #define FNV64primeX 0x01B3 1495 #define FNV64shift 8 1497 /* #define FNV64basis 0xCBF29CE484222325 */ 1498 #define FNV64basis0 0xCBF2 1499 #define FNV64basis1 0x9CE4 1500 #define FNV64basis2 0x8422 1501 #define FNV64basis3 0x2325 1503 /* FNV64 hash a null terminated string (32 bit) 1504 ********************************************************************/ 1505 int FNV64string ( const char *in, uint8_t out[FNV64size] ) 1506 { 1507 FNV64context ctx; 1508 int err; 1510 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 1511 return err; 1512 if ( ( err = FNV64stringin (&ctx, in) ) != fnvSuccess ) 1513 return err; 1514 return FNV64result (&ctx, out); 1515 } /* end FNV64string */ 1517 /* FNV64 hash a counted block (32 bit) 1518 ********************************************************************/ 1519 int FNV64block ( const void *in, 1520 long int length, 1521 uint8_t out[FNV64size] ) 1522 { 1523 FNV64context ctx; 1524 int err; 1526 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 1527 return err; 1528 if ( ( err = FNV64blockin (&ctx, in, length) ) != fnvSuccess ) 1529 return err; 1530 return FNV64result (&ctx, out); 1531 } /* end FNV64block */ 1533 /******************************************************************** 1534 * Set of init, input, and output functions below * 1535 * to incrementally compute FNV64 * 1536 ********************************************************************/ 1538 /* initialize context (32 bit) 1539 ********************************************************************/ 1540 int FNV64init ( FNV64context * const ctx ) 1541 { 1542 if ( ctx ) 1543 { 1544 ctx->Hash[0] = FNV64basis0; 1545 ctx->Hash[1] = FNV64basis1; 1546 ctx->Hash[2] = FNV64basis2; 1547 ctx->Hash[3] = FNV64basis3; 1548 ctx->Computed = FNVinited+FNV64state; 1549 return fnvSuccess; 1550 } 1551 return fnvNull; 1552 } /* end FNV64init */ 1554 /* initialize context (32 bit) 1555 ********************************************************************/ 1556 int FNV64initBasis ( FNV64context * const ctx, 1557 const uint8_t basis[FNV64size] ) 1558 { 1559 if ( ctx ) 1560 { 1561 #ifdef FNV_BigEndian 1562 ctx->Hash[0] = basis[1] + ( basis[0]<<8 ); 1563 ctx->Hash[1] = basis[3] + ( basis[2]<<8 ); 1564 ctx->Hash[2] = basis[5] + ( basis[4]<<8 ); 1565 ctx->Hash[3] = basis[7] + ( basis[6]<<8 ); 1566 #else 1567 ctx->Hash[0] = basis[0] + ( basis[1]<<8 ); 1568 ctx->Hash[1] = basis[2] + ( basis[3]<<8 ); 1569 ctx->Hash[2] = basis[4] + ( basis[5]<<8 ); 1570 ctx->Hash[3] = basis[6] + ( basis[7]<<8 ); 1571 #endif 1572 ctx->Computed = FNVinited+FNV64state; 1573 return fnvSuccess; 1574 } 1575 return fnvNull; 1576 } /* end FNV64initBasis */ 1578 /* hash in a counted block (32 bit) 1579 ********************************************************************/ 1580 int FNV64blockin ( FNV64context * const ctx, 1581 const void *vin, 1582 long int length ) 1583 { 1584 const uint8_t *in = (const uint8_t*)vin; 1585 uint32_t temp[FNV64size/2]; 1586 uint32_t temp2[2]; 1587 int i; 1589 if ( ctx && in ) 1590 { 1591 if ( length < 0 ) 1592 return fnvBadParam; 1593 switch ( ctx->Computed ) 1594 { 1595 case FNVinited+FNV64state: 1596 ctx->Computed = FNVcomputed+FNV64state; 1597 case FNVcomputed+FNV64state: 1598 break; 1599 default: 1600 return fnvStateError; 1601 } 1602 for ( i=0; iHash[i]; 1604 for ( ; length > 0; length-- ) 1605 { 1606 /* temp = FNV64prime * ( temp ^ *in++ ); */ 1607 temp2[1] = temp[3] << FNV64shift; 1608 temp2[0] = temp[2] << FNV64shift; 1609 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 1610 temp[2] *= FNV64primeX; 1611 temp[1] = temp[1] * FNV64primeX + temp2[1]; 1612 temp[0] = temp[0] * FNV64primeX + temp2[0]; 1613 temp[2] += temp[3] >> 16; 1614 temp[3] &= 0xFFFF; 1615 temp[1] += temp[2] >> 16; 1616 temp[2] &= 0xFFFF; 1617 temp[0] += temp[1] >> 16; 1618 temp[1] &= 0xFFFF; 1619 } 1620 for ( i=0; iHash[i] = temp[i]; 1622 return fnvSuccess; 1623 } 1624 return fnvNull; 1625 } /* end FNV64blockin */ 1627 /* hash in a string (32 bit) 1628 ********************************************************************/ 1629 int FNV64stringin ( FNV64context * const ctx, 1630 const char *in ) 1631 { 1632 uint32_t temp[FNV64size/2]; 1633 uint32_t temp2[2]; 1634 int i; 1635 uint8_t ch; 1637 if ( ctx && in ) 1638 { 1639 switch ( ctx->Computed ) 1640 { 1641 case FNVinited+FNV64state: 1643 ctx->Computed = FNVcomputed+FNV64state; 1644 case FNVcomputed+FNV64state: 1645 break; 1646 default: 1647 return fnvStateError; 1648 } 1649 for ( i=0; iHash[i]; 1651 while ( ( ch = (uint8_t)*in++ ) != 0) 1652 { 1653 /* temp = FNV64prime * ( temp ^ ch ); */ 1654 temp2[1] = temp[3] << FNV64shift; 1655 temp2[0] = temp[2] << FNV64shift; 1656 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 1657 temp[2] *= FNV64primeX; 1658 temp[1] = temp[1] * FNV64primeX + temp2[1]; 1659 temp[0] = temp[0] * FNV64primeX + temp2[0]; 1660 temp[2] += temp[3] >> 16; 1661 temp[3] &= 0xFFFF; 1662 temp[1] += temp[2] >> 16; 1663 temp[2] &= 0xFFFF; 1664 temp[0] += temp[1] >> 16; 1665 temp[1] &= 0xFFFF; 1666 } 1667 for ( i=0; iHash[i] = temp[i]; 1669 return fnvSuccess; 1670 } 1671 return fnvNull; 1672 } /* end FNV64stringin */ 1674 /* return hash (32 bit) 1675 ********************************************************************/ 1676 int FNV64result ( FNV64context * const ctx, 1677 uint8_t out[FNV64size] ) 1678 { 1679 int i; 1681 if ( ctx && out ) 1682 { 1683 if ( ctx->Computed != FNVcomputed+FNV64state ) 1684 return fnvStateError; 1685 for ( i=0; iHash[i]; 1689 out[6-2*i] = ctx->Hash[i] >> 8; 1690 #else 1691 out[2*i] = ctx->Hash[i]; 1692 out[2*i+1] = ctx->Hash[i] >> 8; 1694 #endif 1695 ctx -> Hash[i] = 0; 1696 } 1697 ctx->Computed = FNVemptied+FNV64state; 1698 return fnvSuccess; 1699 } 1700 return fnvNull; 1701 } /* end FNV64result */ 1703 #endif /* FNV_64bitIntegers */ 1704 /******************************************************************** 1705 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1706 ********************************************************************/ 1708 #endif /* _FNV64_C_ */ 1709 1711 The header and C source for 64-bit FNV-1a returning a byte vector. 1713 1714 /***************************** FNV64B.h *****************************/ 1715 /******************* See RFC NNNN for details. **********************/ 1716 /* 1717 * Copyright (c) 2016, 2017 IETF Trust and the persons identified as 1718 * authors of the code. All rights reserved. 1719 * See fnv-private.h for terms of use and redistribution. 1720 */ 1722 #ifndef _FNV64_H_ 1723 #define _FNV64_H_ 1725 /* 1726 * Description: 1727 * This file provides headers for the 64-bit version of the FNV-1a 1728 * non-cryptographic hash algorithm. 1729 */ 1731 #include "FNVconfig.h" 1733 #include 1734 #define FNV64size (64/8) 1736 /* If you do not have the ISO standard stdint.h header file, then you 1737 * must typedef the following types: 1738 * 1739 * type meaning 1740 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 1741 * uint32_t unsigned 32 bit integer 1742 * uint16_t unsigned 16 bit integer 1743 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 1744 */ 1746 #ifndef _FNV_ErrCodes_ 1747 #define _FNV_ErrCodes_ 1748 /********************************************************************* 1749 * All FNV functions provided return as integer as follows: 1750 * 0 -> success 1751 * >0 -> error as listed below 1752 */ 1753 enum { /* success and errors */ 1754 fnvSuccess = 0, 1755 fnvNull, /* Null pointer parameter */ 1756 fnvStateError, /* called Input after Result, etc. */ 1757 fnvBadParam /* passed a bad parameter */ 1758 }; 1759 #endif /* _FNV_ErrCodes_ */ 1761 /* 1762 * This structure holds context information for an FNV64 hash 1763 */ 1764 #ifdef FNV_64bitIntegers 1765 /* version if 64 bit integers supported */ 1767 typedef struct FNV64Bcontext_s { 1768 int Computed; /* state */ 1769 uint64_t Hash; 1770 } FNV64Bcontext; 1772 #else 1773 /* version if 64 bit integers NOT supported */ 1775 typedef struct FNV64Bcontext_s { 1776 int Computed; /* state */ 1777 uint16_t Hash[FNV64size/2]; 1778 } FNV64Bcontext; 1780 #endif /* FNV_64bitIntegers */ 1782 /* 1783 * Function Prototypes 1784 * FNV64Bstring: hash a zero terminated string not including 1785 * the terminating zero 1786 * FNV64Bblock: FNV64 hash a specified length byte vector 1787 * FNV64Binit: initializes an FNV64 context 1788 * FNV64BinitBasis: initializes an FNV64 context with a 1789 * provided basis 1790 * FNV64Bblockin: hash in a specified length byte vector 1791 * FNV64Bstringin: hash in a zero terminated string not 1792 * incluing the zero 1793 * FNV64Bresult: returns the hash value 1794 * 1795 * Hash is returned as a vector of 8-bit integers 1796 */ 1798 #ifdef __cplusplus 1799 extern "C" { 1800 #endif 1802 /* FNV64 */ 1803 extern int FNV64Bstring ( const char *in, 1804 uint8_t out[FNV64size] ); 1805 extern int FNV64Bblock ( const void *in, 1806 long int length, 1807 uint8_t out[FNV64size] ); 1808 extern int FNV64Binit ( FNV64Bcontext * const ); 1809 extern int FNV64BinitBasis ( FNV64Bcontext * const, 1810 const uint8_t basis[FNV64size] ); 1811 extern int FNV64Bblockin ( FNV64Bcontext * const, 1812 const void * in, 1813 long int length ); 1814 extern int FNV64Bstringin ( FNV64Bcontext * const, 1815 const char * in ); 1816 extern int FNV64Bresult ( FNV64Bcontext * const, 1817 uint8_t out[FNV64size] ); 1819 #ifdef __cplusplus 1820 } 1821 #endif 1823 #endif /* _FNV64_H_ */ 1824 1826 1827 /***************************** FNV64B.c *****************************/ 1828 /******************** See RFC NNNN for details **********************/ 1829 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 1830 * authors of the code. All rights reserved. 1831 * See fnv-private.h for terms of use and redistribution. 1832 */ 1834 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 1835 * hash function FNV-1a for 64-bit hashes. 1836 */ 1838 #ifndef _FNV64_C_ 1839 #define _FNV64_C_ 1841 #include "fnv-private.h" 1842 #include "FNV64.h" 1843 /******************************************************************** 1844 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1845 ********************************************************************/ 1846 #ifdef FNV_64bitIntegers 1848 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 1849 #define FNV64prime 0x00000100000001B3 1850 #define FNV64basis 0xCBF29CE484222325 1852 /* FNV64 hash a null terminated string (64 bit) 1853 ********************************************************************/ 1854 int FNV64Bstring ( const char *in, uint64_t * const out ) 1855 { 1856 uint64_t temp; 1857 uint8_t ch; 1859 if ( in && out ) 1860 { 1861 temp = FNV64basis; 1862 while ( (ch = *in++) ) 1863 temp = FNV64prime * ( temp ^ ch ); 1864 #ifdef FNV_BigEndian 1865 FNV64reverse ( out, temp ); 1866 #else 1867 *out = temp; 1868 #endif 1869 return fnvSuccess; 1870 } 1871 return fnvNull; /* Null input pointer */ 1872 } /* end FNV64string */ 1874 /* FNV64 hash a counted block (64 bit) 1875 ********************************************************************/ 1876 int FNV64Bblock ( const void *vin, 1877 long int length, 1878 uint64_t * const out ) 1879 { 1880 const uint8_t *in = (const uint8_t*)vin; 1881 uint64_t temp; 1883 if ( in && out ) 1884 { 1885 if ( length < 0 ) 1886 return fnvBadParam; 1887 for ( temp = FNV64basis; length > 0; length-- ) 1888 temp = FNV64prime * ( temp ^ *in++ ); 1889 #ifdef FNV_BigEndian 1890 FNV64reverse ( out, temp ); 1891 #else 1892 *out = temp; 1894 #endif 1895 return fnvSuccess; 1896 } 1897 return fnvNull; /* Null input pointer */ 1898 } /* end FNV64block */ 1900 #ifdef FNV_BigEndian 1902 /* Store a Big Endian result back as Little Endian 1903 ***************************************************************/ 1904 static void FNV64Breverse ( uint64_t *out, uint64_t hash ) 1905 { 1906 uint64_t temp; 1907 int i; 1909 temp = hash & 0xFF; 1910 for ( i = FNV64size - 1; i > 0; i-- ) 1911 { 1912 hash >>= 8; 1913 temp = ( temp << 8 ) + ( hash & 0xFF ); 1914 } 1915 *out = temp; 1916 } /* end FNV64reverse */ 1918 #endif /* FNV_BigEndian */ 1920 /******************************************************************** 1921 * Set of init, input, and output functions below * 1922 * to incrementally compute FNV64 * 1923 ********************************************************************/ 1925 /* initialize context (64 bit) 1926 ********************************************************************/ 1927 int FNV64Binit ( FNV64Bcontext * const ctx ) 1928 { 1929 return FNV64initBasis ( ctx, FNV64basis ); 1930 } /* end FNV64Binit */ 1932 /* initialize context with a provided basis (64 bit) 1933 ********************************************************************/ 1934 int FNV64BinitBasis ( FNV64Bcontext * const ctx, uint64_t basis ) 1935 { 1936 if ( ctx ) 1937 { 1938 ctx->Hash = basis; 1939 ctx->Computed = FNVinited+FNV64state; 1940 return fnvSuccess; 1941 } 1942 return fnvNull; 1943 } /* end FNV64BinitBasis */ 1945 /* hash in a counted block (64 bit) 1946 ********************************************************************/ 1947 int FNV64Bblockin ( FNV64Bcontext * const ctx, 1948 const void *vin, 1949 long int length ) 1950 { 1951 const uint8_t *in = (const uint8_t*)vin; 1952 uint64_t temp; 1954 if ( ctx && in ) 1955 { 1956 if ( length < 0 ) 1957 return fnvBadParam; 1958 switch ( ctx->Computed ) 1959 { 1960 case FNVinited+FNV64state: 1961 ctx->Computed = FNVcomputed+FNV64state; 1962 case FNVcomputed+FNV64state: 1963 break; 1964 default: 1965 return fnvStateError; 1966 } 1967 for ( temp = ctx->Hash; length > 0; length-- ) 1968 temp = FNV64prime * ( temp ^ *in++ ); 1969 ctx->Hash = temp; 1970 return fnvSuccess; 1971 } 1972 return fnvNull; 1973 } /* end FNV64Binput */ 1975 /* hash in a zero terminated string not including the zero (64 bit) 1976 ********************************************************************/ 1977 int FNV64Bstringin ( FNV64Bcontext * const ctx, 1978 const char *in ) 1979 { 1980 uint64_t temp; 1981 uint8_t ch; 1983 if ( ctx && in ) 1984 { 1985 switch ( ctx->Computed ) 1986 { 1987 case FNVinited+FNV64state: 1988 ctx->Computed = FNVcomputed+FNV64state; 1989 case FNVcomputed+FNV64state: 1990 break; 1991 default: 1992 return fnvStateError; 1994 } 1995 temp = ctx->Hash; 1996 while ( (ch = *in++) ) 1997 temp = FNV64prime * ( temp ^ ch ); 1998 ctx->Hash = temp; 1999 return fnvSuccess; 2000 } 2001 return fnvNull; 2002 } /* end FNV64Bstringin */ 2004 /* return hash (64 bit) 2005 ********************************************************************/ 2006 int FNV64Bresult ( FNV64Bcontext * const ctx, 2007 uint64_t * const out ) 2008 { 2009 if ( ctx && out ) 2010 { 2011 if ( ctx->Computed != FNVcomputed+FNV64state ) 2012 return fnvStateError; 2013 ctx->Computed = FNVemptied+FNV64state; 2014 #ifdef FNV_BigEndian 2015 FNV64reverse ( out, ctx->Hash ); 2016 #else 2017 *out = ctx->Hash; 2018 #endif 2019 ctx->Hash = 0; 2020 return fnvSuccess; 2021 } 2022 return fnvNull; 2023 } /* end FNV64Bresult */ 2025 /****************************************************************** 2026 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2027 ******************************************************************/ 2028 #else /* FNV_64bitIntegers */ 2029 /****************************************************************** 2030 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2031 ******************************************************************/ 2033 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 2034 /* #define FNV64prime 0x00000100000001B3 */ 2035 #define FNV64primeX 0x01B3 2036 #define FNV64shift 8 2038 /* #define FNV64basis 0xCBF29CE484222325 */ 2039 #define FNV64basis0 0xCBF2 2040 #define FNV64basis1 0x9CE4 2041 #define FNV64basis2 0x8422 2042 #define FNV64basis3 0x2325 2043 /* FNV64 hash a null terminated string (32 bit) 2044 ********************************************************************/ 2045 int FNV64Bstring ( const char *in, uint8_t out[FNV64size] ) 2046 { 2047 FNV64Bcontext ctx; 2048 int err; 2050 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 2051 return err; 2052 if ( ( err = FNV64stringin (&ctx, in) ) != fnvSuccess ) 2053 return err; 2054 return FNV64result (&ctx, out); 2055 } /* end FNV64Bstring */ 2057 /* FNV64 hash a counted block (32 bit) 2058 ********************************************************************/ 2059 int FNV64Bblock ( const void *in, 2060 long int length, 2061 uint8_t out[FNV64size] ) 2062 { 2063 FNV64Bcontext ctx; 2064 int err; 2066 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 2067 return err; 2068 if ( ( err = FNV64blockin (&ctx, in, length) ) != fnvSuccess ) 2069 return err; 2070 return FNV64result (&ctx, out); 2071 } /* end FNV64Bblock */ 2073 /******************************************************************** 2074 * Set of init, input, and output functions below * 2075 * to incrementally compute FNV64 * 2076 ********************************************************************/ 2078 /* initialize context (32 bit) 2079 ********************************************************************/ 2080 int FNV64Binit ( FNV64Bcontext * const ctx ) 2081 { 2082 if ( ctx ) 2083 { 2084 ctx->Hash[0] = FNV64basis0; 2085 ctx->Hash[1] = FNV64basis1; 2086 ctx->Hash[2] = FNV64basis2; 2087 ctx->Hash[3] = FNV64basis3; 2088 ctx->Computed = FNVinited+FNV64state; 2089 return fnvSuccess; 2090 } 2091 return fnvNull; 2092 } /* end FNV64Binit */ 2094 /* initialize context (32 bit) 2095 ********************************************************************/ 2096 int FNV64BinitBasis ( FNV64Bcontext * const ctx, 2097 const uint8_t basis[FNV64size] ) 2098 { 2099 if ( ctx ) 2100 { 2101 #ifdef FNV_BigEndian 2102 ctx->Hash[0] = basis[1] + ( basis[0]<<8 ); 2103 ctx->Hash[1] = basis[3] + ( basis[2]<<8 ); 2104 ctx->Hash[2] = basis[5] + ( basis[4]<<8 ); 2105 ctx->Hash[3] = basis[7] + ( basis[6]<<8 ); 2106 #else 2107 ctx->Hash[0] = basis[0] + ( basis[1]<<8 ); 2108 ctx->Hash[1] = basis[2] + ( basis[3]<<8 ); 2109 ctx->Hash[2] = basis[4] + ( basis[5]<<8 ); 2110 ctx->Hash[3] = basis[6] + ( basis[7]<<8 ); 2111 #endif 2112 ctx->Computed = FNVinited+FNV64state; 2113 return fnvSuccess; 2114 } 2115 return fnvNull; 2116 } /* end FNV64BinitBasis */ 2118 /* hash in a counted block (32 bit) 2119 ********************************************************************/ 2120 int FNV64Bblockin ( FNV64Bcontext * const ctx, 2121 const void *vin, 2122 long int length ) 2123 { 2124 const uint8_t *in = (const uint8_t*)vin; 2125 uint32_t temp[FNV64size/2]; 2126 uint32_t temp2[2]; 2127 int i; 2129 if ( ctx && in ) 2130 { 2131 if ( length < 0 ) 2132 return fnvBadParam; 2133 switch ( ctx->Computed ) 2134 { 2135 case FNVinited+FNV64state: 2136 ctx->Computed = FNVcomputed+FNV64state; 2137 case FNVcomputed+FNV64state: 2138 break; 2139 default: 2140 return fnvStateError; 2141 } 2143 for ( i=0; iHash[i]; 2145 for ( ; length > 0; length-- ) 2146 { 2147 /* temp = FNV64prime * ( temp ^ *in++ ); */ 2148 temp2[1] = temp[3] << FNV64shift; 2149 temp2[0] = temp[2] << FNV64shift; 2150 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 2151 temp[2] *= FNV64primeX; 2152 temp[1] = temp[1] * FNV64primeX + temp2[1]; 2153 temp[0] = temp[0] * FNV64primeX + temp2[0]; 2154 temp[2] += temp[3] >> 16; 2155 temp[3] &= 0xFFFF; 2156 temp[1] += temp[2] >> 16; 2157 temp[2] &= 0xFFFF; 2158 temp[0] += temp[1] >> 16; 2159 temp[1] &= 0xFFFF; 2160 } 2161 for ( i=0; iHash[i] = temp[i]; 2163 return fnvSuccess; 2164 } 2165 return fnvNull; 2166 } /* end FNV64Bblockin */ 2168 /* hash in a string (32 bit) 2169 ********************************************************************/ 2170 int FNV64Bstringin ( FNV64Bcontext * const ctx, 2171 const char *in ) 2172 { 2173 uint32_t temp[FNV64size/2]; 2174 uint32_t temp2[2]; 2175 int i; 2176 uint8_t ch; 2178 if ( ctx && in ) 2179 { 2180 switch ( ctx->Computed ) 2181 { 2182 case FNVinited+FNV64state: 2183 ctx->Computed = FNVcomputed+FNV64state; 2184 case FNVcomputed+FNV64state: 2185 break; 2186 default: 2187 return fnvStateError; 2188 } 2189 for ( i=0; iHash[i]; 2191 while ( ( ch = (uint8_t)*in++ ) != 0) 2192 { 2193 /* temp = FNV64prime * ( temp ^ ch ); */ 2194 temp2[1] = temp[3] << FNV64shift; 2195 temp2[0] = temp[2] << FNV64shift; 2196 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 2197 temp[2] *= FNV64primeX; 2198 temp[1] = temp[1] * FNV64primeX + temp2[1]; 2199 temp[0] = temp[0] * FNV64primeX + temp2[0]; 2200 temp[2] += temp[3] >> 16; 2201 temp[3] &= 0xFFFF; 2202 temp[1] += temp[2] >> 16; 2203 temp[2] &= 0xFFFF; 2204 temp[0] += temp[1] >> 16; 2205 temp[1] &= 0xFFFF; 2206 } 2207 for ( i=0; iHash[i] = temp[i]; 2209 return fnvSuccess; 2210 } 2211 return fnvNull; 2212 } /* end FNV64Bstringin */ 2214 /* return hash (32 bit) 2215 ********************************************************************/ 2216 int FNV64Bresult ( FNV64Bcontext * const ctx, 2217 uint8_t out[FNV64size] ) 2218 { 2219 int i; 2221 if ( ctx && out ) 2222 { 2223 if ( ctx->Computed != FNVcomputed+FNV64state ) 2224 return fnvStateError; 2225 for ( i=0; iHash[i]; 2229 out[6-2*i] = ctx->Hash[i] >> 8; 2230 #else 2231 out[2*i] = ctx->Hash[i]; 2232 out[2*i+1] = ctx->Hash[i] >> 8; 2233 #endif 2234 ctx -> Hash[i] = 0; 2235 } 2236 ctx->Computed = FNVemptied+FNV64state; 2237 return fnvSuccess; 2238 } 2239 return fnvNull; 2240 } /* end FNV64Bresult */ 2242 #endif /* FNV_64bitIntegers */ 2243 /******************************************************************** 2244 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2245 ********************************************************************/ 2247 #endif /* _FNV64_C_ */ 2248 2250 6.1.3 FNV128 C Code 2252 The header and C source for 128-bit FNV-1a returning a byte vector. 2254 2255 /**************************** FNV128.h **************************/ 2256 /***************** See RFC NNNN for details. ********************/ 2257 /* 2258 * Copyright (c) 2016 IETF Trust and the persons identified as 2259 * authors of the code. All rights reserved. 2260 * See fnv-private.h for terms of use and redistribution. 2261 */ 2263 #ifndef _FNV128_H_ 2264 #define _FNV128_H_ 2266 /* 2267 * Description: 2268 * This file provides headers for the 128-bit version of the 2269 * FNV-1a non-cryptographic hash algorithm. 2270 */ 2272 #include "FNVconfig.h" 2274 #include 2275 #define FNV128size (128/8) 2277 /* If you do not have the ISO standard stdint.h header file, then you 2278 * must typedef the following types: 2279 * 2280 * type meaning 2281 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 2282 * uint32_t unsigned 32 bit integer 2283 * uint16_t unsigned 16 bit integer 2284 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 2285 */ 2287 #ifndef _FNV_ErrCodes_ 2288 #define _FNV_ErrCodes_ 2289 /********************************************************************* 2290 * All FNV functions provided return as integer as follows: 2292 * 0 -> success 2293 * >0 -> error as listed below 2294 */ 2295 enum { /* success and errors */ 2296 fnvSuccess = 0, 2297 fnvNull, /* Null pointer parameter */ 2298 fnvStateError, /* called Input after Result or before Init */ 2299 fnvBadParam /* passed a bad parameter */ 2300 }; 2301 #endif /* _FNV_ErrCodes_ */ 2303 /* 2304 * This structure holds context information for an FNV128 hash 2305 */ 2306 #ifdef FNV_64bitIntegers 2307 /* version if 64 bit integers supported */ 2308 typedef struct FNV128context_s { 2309 int Computed; /* state */ 2310 uint32_t Hash[FNV128size/4]; 2311 } FNV128context; 2313 #else 2314 /* version if 64 bit integers NOT supported */ 2316 typedef struct FNV128context_s { 2317 int Computed; /* state */ 2318 uint16_t Hash[FNV128size/2]; 2319 } FNV128context; 2321 #endif /* FNV_64bitIntegers */ 2323 /* 2324 * Function Prototypes 2325 * FNV128string: hash a zero terminated string not including 2326 * the terminating zero 2327 * FNV128block: FNV128 hash a specified length byte vector 2328 * FNV128init: initializes an FNV128 context 2329 * FNV128initBasis: initializes an FNV128 context with a 2330 * provided basis 2331 * FNV128blockin: hash in a specified length byte vector 2332 * FNV128stringin: hash in a zero terminated string not 2333 * including the zero 2334 * FNV128result: returns the hash value 2335 * 2336 * Hash is returned as an array of 8-bit integers 2337 */ 2339 #ifdef __cplusplus 2340 extern "C" { 2341 #endif 2342 /* FNV128 */ 2343 extern int FNV128string ( const char *in, 2344 uint8_t out[FNV128size] ); 2345 extern int FNV128block ( const void *in, 2346 long int length, 2347 uint8_t out[FNV128size] ); 2348 extern int FNV128init ( FNV128context * const ); 2349 extern int FNV128initBasis ( FNV128context * const, 2350 const uint8_t basis[FNV128size] ); 2351 extern int FNV128blockin ( FNV128context * const, 2352 const void *in, 2353 long int length ); 2354 extern int FNV128stringin ( FNV128context * const, 2355 const char *in ); 2356 extern int FNV128result ( FNV128context * const, 2357 uint8_t out[FNV128size] ); 2359 #ifdef __cplusplus 2360 } 2361 #endif 2363 #endif /* _FNV128_H_ */ 2364 2366 2367 /***************************** FNV128.c ****************************/ 2368 /******************** See RFC NNNN for details *********************/ 2369 /* Copyright (c) 2016 IETF Trust and the persons identified as 2370 * authors of the code. All rights 2371 * See fnv-private.h for terms of use and redistribution. 2372 */ 2374 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 2375 * hash function FNV-1a for 128-bit hashes. 2376 */ 2378 #ifndef _FNV128_C_ 2379 #define _FNV128_C_ 2381 #include "fnv-private.h" 2382 #include "FNV128.h" 2384 /* common code for 64 and 32 bit modes */ 2386 /* FNV128 hash a null terminated string (64/32 bit) 2387 ********************************************************************/ 2388 int FNV128string ( const char *in, uint8_t out[FNV128size] ) 2389 { 2390 FNV128context ctx; 2391 int err; 2392 err = FNV128init ( &ctx ); 2393 if ( err != fnvSuccess ) return err; 2394 err = FNV128stringin ( &ctx, in ); 2395 if ( err != fnvSuccess ) return err; 2396 return FNV128result (&ctx, out); 2397 } /* end FNV128string */ 2399 /* FNV128 hash a counted block (64/32 bit) 2400 ********************************************************************/ 2401 int FNV128block ( const void *in, 2402 long int length, 2403 uint8_t out[FNV128size] ) 2404 { 2405 FNV128context ctx; 2406 int err; 2408 err = FNV128init ( &ctx ); 2409 if ( err != fnvSuccess ) return err; 2410 err = FNV128blockin ( &ctx, in, length ); 2411 if ( err != fnvSuccess ) return err; 2412 return FNV128result ( &ctx, out ); 2413 } /* end FNV128block */ 2415 /******************************************************************** 2416 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2417 ********************************************************************/ 2418 #ifdef FNV_64bitIntegers 2420 /* 128 bit FNV_prime = 2^88 + 2^8 + 0x3b */ 2421 /* 0x00000000 01000000 00000000 0000013B */ 2422 #define FNV128primeX 0x013B 2423 #define FNV128shift 24 2425 /* 0x6C62272E 07BB0142 62B82175 6295C58D */ 2426 #define FNV128basis0 0x6C62272E 2427 #define FNV128basis1 0x07BB0142 2428 #define FNV128basis2 0x62B82175 2429 #define FNV128basis3 0x6295C58D 2431 /******************************************************************** 2432 * Set of init, input, and output functions below * 2433 * to incrementally compute FNV128 * 2434 ********************************************************************/ 2436 /* initialize context (64 bit) 2437 ********************************************************************/ 2438 int FNV128init ( FNV128context * const ctx ) 2439 { 2440 if ( ctx ) 2441 { 2442 ctx->Hash[0] = FNV128basis0; 2443 ctx->Hash[1] = FNV128basis1; 2444 ctx->Hash[2] = FNV128basis2; 2445 ctx->Hash[3] = FNV128basis3; 2446 ctx->Computed = FNVinited+FNV128state; 2447 return fnvSuccess; 2448 } 2449 return fnvNull; 2450 } /* end FNV128init */ 2452 /* initialize context with a provided basis (64 bit) 2453 ********************************************************************/ 2454 int FNV128initBasis ( FNV128context * const ctx, 2455 const uint8_t basis[FNV128size] ) 2456 { 2457 int i; 2458 const uint8_t *ui8p; 2459 uint32_t temp; 2461 if ( ctx ) 2462 { 2463 #ifdef FNV_BigEndian 2464 ui8p = basis; 2465 for ( i=0; i < FNV128size/4; ++i ) 2466 { 2467 temp = (*ui8p++)<<8; 2468 temp = (temp + *ui8p++)<<8; 2469 temp = (temp + *ui8p++)<<8; 2470 ctx->Hash[i] = temp + *ui8p; 2471 } 2472 #else 2473 ui8p = basis + ( FNV128size/4 - 1 ); 2474 for ( i=0; i < FNV128size/4; ++i ) 2475 { 2476 temp = (*ui8p--)<<8; 2477 temp = (temp + *ui8p--)<<8; 2478 temp = (temp + *ui8p--)<<8; 2479 ctx->Hash[i] = temp + *ui8p; 2480 } 2481 #endif 2482 ctx->Computed = FNVinited+FNV128state; 2483 return fnvSuccess; 2484 } 2485 return fnvNull; 2486 } /* end FNV128initBasis */ 2488 /* hash in a counted block (64 bit) 2489 ********************************************************************/ 2490 int FNV128blockin ( FNV128context * const ctx, 2491 const void *vin, 2492 long int length ) 2493 { 2494 const uint8_t *in = (const uint8_t*)vin; 2495 uint64_t temp[FNV128size/4]; 2496 uint64_t temp2[2]; 2497 int i; 2499 if ( ctx && in ) 2500 { 2501 if ( length < 0 ) 2502 return fnvBadParam; 2503 switch ( ctx->Computed ) 2504 { 2505 case FNVinited+FNV128state: 2506 ctx->Computed = FNVcomputed+FNV128state; 2507 case FNVcomputed+FNV128state: 2508 break; 2509 default: 2510 return fnvStateError; 2511 } 2512 for ( i=0; iHash[i]; 2514 for ( ; length > 0; length-- ) 2515 { 2516 /* temp = FNV128prime * ( temp ^ *in++ ); */ 2517 temp2[1] = temp[3] << FNV128shift; 2518 temp2[0] = temp[2] << FNV128shift; 2519 temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); 2520 temp[2] *= FNV128primeX; 2521 temp[1] = temp[1] * FNV128primeX + temp2[1]; 2522 temp[0] = temp[0] * FNV128primeX + temp2[0]; 2523 temp[2] += temp[3] >> 32; 2524 temp[3] &= 0xFFFFFFFF; 2525 temp[1] += temp[2] >> 32; 2526 temp[2] &= 0xFFFFFFFF; 2527 temp[0] += temp[1] >> 32; 2528 temp[1] &= 0xFFFFFFFF; 2529 } 2530 for ( i=0; iHash[i] = temp[i]; 2532 return fnvSuccess; 2533 } 2534 return fnvNull; 2535 } /* end FNV128input */ 2537 /* hash in a string (64 bit) 2538 ********************************************************************/ 2539 int FNV128stringin ( FNV128context * const ctx, const char *in ) 2540 { 2541 uint64_t temp[FNV128size/4]; 2542 uint64_t temp2[2]; 2543 int i; 2544 uint8_t ch; 2546 if ( ctx && in ) 2547 { 2548 switch ( ctx->Computed ) 2549 { 2550 case FNVinited+FNV128state: 2551 ctx->Computed = FNVcomputed+FNV128state; 2552 case FNVcomputed+FNV128state: 2553 break; 2554 default: 2555 return fnvStateError; 2556 } 2557 for ( i=0; iHash[i]; 2559 while ( (ch = (uint8_t)*in++) ) 2560 { 2561 /* temp = FNV128prime * ( temp ^ ch ); */ 2562 temp2[1] = temp[3] << FNV128shift; 2563 temp2[0] = temp[2] << FNV128shift; 2564 temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); 2565 temp[2] *= FNV128primeX; 2566 temp[1] = temp[1] * FNV128primeX + temp2[1]; 2567 temp[0] = temp[0] * FNV128primeX + temp2[0]; 2568 temp[2] += temp[3] >> 32; 2569 temp[3] &= 0xFFFFFFFF; 2570 temp[1] += temp[2] >> 32; 2571 temp[2] &= 0xFFFFFFFF; 2572 temp[0] += temp[1] >> 32; 2573 temp[1] &= 0xFFFFFFFF; 2574 } 2575 for ( i=0; iHash[i] = temp[i]; 2577 return fnvSuccess; 2578 } 2579 return fnvNull; 2580 } /* end FNV128stringin */ 2582 /* return hash (64 bit) 2583 ********************************************************************/ 2584 int FNV128result ( FNV128context * const ctx, uint8_t out[FNV128size] ) 2585 { 2586 int i; 2588 if ( ctx && out ) 2589 { 2590 if ( ctx->Computed != FNVcomputed+FNV128state ) 2591 return fnvStateError; 2592 for ( i=0; iHash[i]; 2596 out[14-4*i] = ctx->Hash[i] >> 8; 2597 out[13-4*i] = ctx->Hash[i] >> 16; 2598 out[12-4*i] = ctx->Hash[i] >> 24; 2599 #else 2600 out[4*i] = ctx->Hash[i]; 2601 out[4*i+1] = ctx->Hash[i] >> 8; 2602 out[4*i+2] = ctx->Hash[i] >> 16; 2603 out[4*i+3] = ctx->Hash[i] >> 24; 2604 #endif 2605 ctx -> Hash[i] = 0; 2606 } 2607 ctx->Computed = FNVemptied+FNV128state; 2608 return fnvSuccess; 2609 } 2610 return fnvNull; 2611 } /* end FNV128result */ 2613 /****************************************************************** 2614 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2615 ******************************************************************/ 2616 #else /* FNV_64bitIntegers */ 2617 /****************************************************************** 2618 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2619 ******************************************************************/ 2621 /* 128 bit FNV_prime = 2^88 + 2^8 + 0x3b */ 2622 /* 0x00000000 01000000 00000000 0000013B */ 2623 #define FNV128primeX 0x013B 2624 #define FNV128shift 8 2626 /* 0x6C62272E 07BB0142 62B82175 6295C58D */ 2627 uint16_t FNV128basis[FNV128size/2] = 2628 { 0x6C62, 0x272E, 0x07BB, 0x0142, 2629 0x62B8, 0x2175, 0x6295, 0xC58D }; 2631 /******************************************************************** 2632 * Set of init, input, and output functions below * 2633 * to incrementally compute FNV128 * 2634 ********************************************************************/ 2636 /* initialize context (32 bit) 2637 ********************************************************************/ 2638 int FNV128init ( FNV128context *ctx ) 2639 { 2640 int i; 2641 if ( ctx ) 2642 { 2643 for ( i=0; iHash[i] = FNV128basis[i]; 2645 ctx->Computed = FNVinited+FNV128state; 2646 return fnvSuccess; 2647 } 2648 return fnvNull; 2649 } /* end FNV128init */ 2651 /* initialize context with a provided basis (32 bit) 2652 ********************************************************************/ 2653 int FNV128initBasis ( FNV128context *ctx, 2654 const uint8_t basis[FNV128size] ) 2655 { 2656 int i; 2657 const uint8_t *ui8p; 2658 uint32_t temp; 2660 if ( ctx ) 2661 { 2662 #ifdef FNV_BigEndian 2663 ui8p = basis; 2664 for ( i=0; i < FNV128size/2; ++i ) 2665 { 2666 temp = *ui8p++; 2667 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 2668 } 2669 #else 2670 ui8p = basis + (FNV128size/2 - 1); 2671 for ( i=0; i < FNV128size/2; ++i ) 2672 { 2673 temp = *ui8p--; 2674 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 2675 } 2676 #endif 2677 ctx->Computed = FNVinited+FNV128state; 2678 return fnvSuccess; 2679 } 2680 return fnvNull; 2681 } /* end FNV128initBasis */ 2683 /* hash in a counted block (32 bit) 2684 *******************************************************************/ 2685 int FNV128blockin ( FNV128context *ctx, 2686 const void *vin, 2687 long int length ) 2688 { 2689 const uint8_t *in = (const uint8_t*)vin; 2690 uint32_t temp[FNV128size/2]; 2691 uint32_t temp2[3]; 2692 int i; 2694 if ( ctx && in ) 2695 { 2696 if ( length < 0 ) 2697 return fnvBadParam; 2698 switch ( ctx->Computed ) 2699 { 2700 case FNVinited+FNV128state: 2701 ctx->Computed = FNVcomputed+FNV128state; 2702 case FNVcomputed+FNV128state: 2703 break; 2704 default: 2705 return fnvStateError; 2706 } 2707 for ( i=0; iHash[i]; 2709 for ( ; length > 0; length-- ) 2710 { 2711 /* temp = FNV128prime * ( temp ^ *in++ ); */ 2712 temp[7] ^= *in++; 2713 temp2[2] = temp[7] << FNV128shift; 2714 temp2[1] = temp[6] << FNV128shift; 2715 temp2[0] = temp[5] << FNV128shift; 2716 for ( i=0; i<8; ++i ) 2717 temp[i] *= FNV128primeX; 2718 temp[2] += temp2[2]; 2719 temp[1] += temp2[1]; 2720 temp[0] += temp2[0]; 2721 for ( i=7; i>0; --i ) 2722 { 2723 temp[i-1] += temp[i] >> 16; 2724 temp[i] &= 0xFFFF; 2725 } 2726 } 2727 for ( i=0; iHash[i] = temp[i]; 2729 return fnvSuccess; 2730 } 2731 return fnvNull; 2732 } /* end FNV128blockin */ 2734 /* hash in a string (32 bit) 2735 *******************************************************************/ 2736 int FNV128stringin ( FNV128context *ctx, 2737 const char *in ) 2738 { 2739 uint32_t temp[FNV128size/2]; 2740 uint32_t temp2[3]; 2741 int i; 2742 uint8_t ch; 2744 if ( ctx && in ) 2745 { 2746 switch ( ctx->Computed ) 2747 { 2748 case FNVinited+FNV128state: 2749 ctx->Computed = FNVcomputed+FNV128state; 2750 case FNVcomputed+FNV128state: 2751 break; 2752 default: 2753 return fnvStateError; 2754 } 2755 for ( i=0; iHash[i]; 2757 while ( (ch = (uint8_t)*in++) ) 2758 { 2759 /* temp = FNV128prime * ( temp ^ *in++ ); */ 2760 temp[7] ^= ch; 2761 temp2[2] = temp[7] << FNV128shift; 2762 temp2[1] = temp[6] << FNV128shift; 2763 temp2[0] = temp[5] << FNV128shift; 2764 for ( i=0; i<8; ++i ) 2765 temp[i] *= FNV128primeX; 2766 temp[2] += temp2[2]; 2767 temp[1] += temp2[1]; 2768 temp[0] += temp2[0]; 2769 for ( i=7; i>0; --i ) 2770 { 2771 temp[i-1] += temp[i] >> 16; 2772 temp[i] &= 0xFFFF; 2773 } 2774 } 2775 for ( i=0; iHash[i] = temp[i]; 2777 return fnvSuccess; 2778 } 2779 return fnvNull; 2780 } /* end FNV128stringin */ 2782 /* return hash (32 bit) 2783 ********************************************************************/ 2784 int FNV128result ( FNV128context *ctx, 2785 uint8_t out[FNV128size] ) 2786 { 2787 int i; 2789 if ( ctx && out ) 2790 { 2791 if ( ctx->Computed != FNVcomputed+FNV128state ) 2792 return fnvStateError; 2793 for ( i=0; iHash[i]; 2797 out[14-2*i] = ctx->Hash[i] >> 8; 2798 #else 2799 out[2*i] = ctx->Hash[i]; 2800 out[2*i+1] = ctx->Hash[i] >> 8; 2801 #endif 2802 ctx -> Hash[i] = 0; 2803 } 2804 ctx->Computed = FNVemptied+FNV128state; 2805 return fnvSuccess; 2806 } 2807 return fnvNull; 2808 } /* end FNV128result */ 2810 #endif /* Have64bitIntegers */ 2811 /******************************************************************** 2812 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2813 ********************************************************************/ 2815 #endif /* _FNV128_C_ */ 2816 2818 6.1.4 FNV256 C Code 2820 The header and C source for 256-bit FNV-1a returning a byte vector. 2822 2823 /**************************** FNV256.h **************************/ 2824 /***************** See RFC NNNN for details. ********************/ 2825 /* 2826 * Copyright (c) 2016 IETF Trust and the persons identified as 2827 * authors of the code. All rights reserved. 2828 * See fnv-private.h for terms of use and redistribution. 2829 */ 2831 #ifndef _FNV256_H_ 2832 #define _FNV256_H_ 2834 /* 2835 * Description: 2836 * This file provides headers for the 256-bit version of the 2837 * FNV-1a non-cryptographic hash algorithm. 2838 */ 2840 #include "FNVconfig.h" 2842 #include 2843 #define FNV256size (256/8) 2845 /* If you do not have the ISO standard stdint.h header file, then you 2846 * must typedef the following types: 2847 * 2848 * type meaning 2849 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 2850 * uint32_t unsigned 32 bit integer 2851 * uint16_t unsigned 16 bit integer 2852 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 2853 */ 2855 #ifndef _FNV_ErrCodes_ 2856 #define _FNV_ErrCodes_ 2857 /********************************************************************* 2858 * All FNV functions provided return as integer as follows: 2859 * 0 -> success 2860 * >0 -> error as listed below 2861 */ 2862 enum { /* success and errors */ 2863 fnvSuccess = 0, 2864 fnvNull, /* Null pointer parameter */ 2865 fnvStateError, /* called Input after Result or before Init */ 2866 fnvBadParam /* passed a bad parameter */ 2867 }; 2868 #endif /* _FNV_ErrCodes_ */ 2870 /* 2871 * This structure holds context information for an FNV256 hash 2872 */ 2873 #ifdef FNV_64bitIntegers 2874 /* version if 64 bit integers supported */ 2875 typedef struct FNV256context_s { 2876 int Computed; /* state */ 2877 uint32_t Hash[FNV256size/4]; 2878 } FNV256context; 2880 #else 2881 /* version if 64 bit integers NOT supported */ 2883 typedef struct FNV256context_s { 2884 int Computed; /* state */ 2885 uint16_t Hash[FNV256size/2]; 2886 } FNV256context; 2888 #endif /* FNV_64bitIntegers */ 2889 /* 2890 * Function Prototypes 2891 * FNV256string: hash a zero terminated string not including 2892 * the zero 2893 * FNV256block: FNV256 hash a specified length byte vector 2894 * FNV256init: initializes an FNV256 context 2895 * FNV256initBasis: initializes an FNV256 context with a provided 2896 * basis 2897 * FNV256blockin: hash in a specified length byte vector 2898 * FNV256stringin: hash in a zero terminated string not 2899 * including the zero 2900 * FNV256result: returns the hash value 2901 * 2902 * Hash is returned as an array of 8-bit integers 2903 */ 2905 #ifdef __cplusplus 2906 extern "C" { 2907 #endif 2909 /* FNV256 */ 2910 extern int FNV256string ( const char *in, 2911 uint8_t out[FNV256size] ); 2912 extern int FNV256block ( const void *in, 2913 long int length, 2914 uint8_t out[FNV256size] ); 2915 extern int FNV256init ( FNV256context *); 2916 extern int FNV256initBasis ( FNV256context * const, 2917 const uint8_t basis[FNV256size] ); 2918 extern int FNV256blockin ( FNV256context * const, 2919 const void *in, 2920 long int length ); 2921 extern int FNV256stringin ( FNV256context * const, 2922 const char *in ); 2923 extern int FNV256result ( FNV256context * const, 2924 uint8_t out[FNV256size] ); 2926 #ifdef __cplusplus 2927 } 2928 #endif 2930 #endif /* _FNV256_H_ */ 2931 2933 2934 /***************************** FNV256.c ****************************/ 2935 /******************** See RFC NNNN for details *********************/ 2936 /* Copyright (c) 2016 IETF Trust and the persons identified as 2937 * authors of the code. All rights 2938 * See fnv-private.h for terms of use and redistribution. 2940 */ 2942 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 2943 * hash function FNV-1a for 256-bit hashes. 2944 */ 2946 #ifndef _FNV256_C_ 2947 #define _FNV256_C_ 2949 #include "fnv-private.h" 2950 #include "FNV256.h" 2952 /* common code for 64 and 32 bit modes */ 2954 /* FNV256 hash a null terminated string (64/32 bit) 2955 ********************************************************************/ 2956 int FNV256string ( const char *in, uint8_t out[FNV256size] ) 2957 { 2958 FNV256context ctx; 2959 int err; 2961 if ( (err = FNV256init ( &ctx )) != fnvSuccess ) 2962 return err; 2963 if ( (err = FNV256stringin ( &ctx, in )) != fnvSuccess ) 2964 return err; 2965 return FNV256result ( &ctx, out ); 2966 } /* end FNV256string */ 2968 /* FNV256 hash a counted block (64/32 bit) 2969 ********************************************************************/ 2970 int FNV256block ( const void *in, 2971 long int length, 2972 uint8_t out[FNV256size] ) 2973 { 2974 FNV256context ctx; 2975 int err; 2977 if ( (err = FNV256init ( &ctx )) != fnvSuccess ) 2978 return err; 2979 if ( (err = FNV256blockin ( &ctx, in, length)) != fnvSuccess ) 2980 return err; 2981 return FNV256result ( &ctx, out ); 2982 } /* end FNV256block */ 2984 /******************************************************************** 2985 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2986 ********************************************************************/ 2987 #ifdef FNV_64bitIntegers 2988 /* 256 bit FNV_prime = 2^168 + 2^8 + 0x63 */ 2989 /* 0x0000000000000000 0000010000000000 2990 0000000000000000 0000000000000163 */ 2991 #define FNV256primeX 0x0163 2992 #define FNV256shift 8 2994 /* 0xDD268DBCAAC55036 2D98C384C4E576CC 2995 C8B1536847B6BBB3 1023B4C8CAEE0535 */ 2996 uint32_t FNV256basis[FNV256size/4] = { 2997 0xDD268DBC, 0xAAC55036, 0x2D98C384, 0xC4E576CC, 2998 0xC8B15368, 0x47B6BBB3, 0x1023B4C8, 0xCAEE0535 }; 3000 /******************************************************************** 3001 * Set of init, input, and output functions below * 3002 * to incrementally compute FNV256 * 3003 ********************************************************************/ 3005 /* initialize context (64 bit) 3006 ********************************************************************/ 3007 int FNV256init ( FNV256context *ctx ) 3008 { 3009 int i; 3011 if ( ctx ) 3012 { 3013 for ( i=0; iHash[i] = FNV256basis[i]; 3015 ctx->Computed = FNVinited+FNV256state; 3016 return fnvSuccess; 3017 } 3018 return fnvNull; 3019 } /* end FNV256init */ 3021 /* initialize context with a provided basis (64 bit) 3022 ********************************************************************/ 3023 int FNV256initBasis ( FNV256context* const ctx, 3024 const uint8_t basis[FNV256size] ) 3025 { 3026 int i; 3027 const uint8_t *ui8p; 3028 uint32_t temp; 3030 if ( ctx ) 3031 { 3032 #ifdef FNV_BigEndian 3033 ui8p = basis; 3034 for ( i=0; i < FNV256size/4; ++i ) 3035 { 3036 temp = (*ui8p++)<<8; 3037 temp = (temp + *ui8p++)<<8; 3038 temp = (temp + *ui8p++)<<8; 3039 ctx->Hash[i] = temp + *ui8p; 3040 } 3041 #else 3042 ui8p = basis + (FNV256size/4 - 1); 3043 for ( i=0; i < FNV256size/4; ++i ) 3044 { 3045 temp = (*ui8p--)<<8; 3046 temp = (temp + *ui8p--)<<8; 3047 temp = (temp + *ui8p--)<<8; 3048 ctx->Hash[i] = temp + *ui8p; 3049 } 3050 #endif 3051 ctx->Computed = FNVinited+FNV256state; 3052 return fnvSuccess; 3053 } 3054 return fnvNull; 3055 } /* end FNV256initBasis */ 3057 /* hash in a counted block (64 bit) 3058 ********************************************************************/ 3059 int FNV256blockin ( FNV256context *ctx, 3060 const void *vin, 3061 long int length ) 3062 { 3063 const uint8_t *in = (const uint8_t*)vin; 3064 uint64_t temp[FNV256size/4]; 3065 uint64_t temp2[3]; 3066 int i; 3068 if ( ctx && in ) 3069 { 3070 if ( length < 0 ) 3071 return fnvBadParam; 3072 switch ( ctx->Computed ) 3073 { 3074 case FNVinited+FNV256state: 3075 ctx->Computed = FNVcomputed+FNV256state; 3076 case FNVcomputed+FNV256state: 3077 break; 3078 default: 3079 return fnvStateError; 3080 } 3081 for ( i=0; iHash[i]; 3083 for ( ; length > 0; length-- ) 3084 { 3085 /* temp = FNV256prime * ( temp ^ *in++ ); */ 3086 temp[7] ^= *in++; 3087 temp2[2] = temp[7] << FNV256shift; 3088 temp2[1] = temp[6] << FNV256shift; 3089 temp2[0] = temp[5] << FNV256shift; 3090 for ( i=0; i0; --i ) 3096 { 3097 temp[i-1] += temp[i] >> 16; 3098 temp[i] &= 0xFFFF; 3099 } 3100 } 3101 for ( i=0; iHash[i] = temp[i]; 3103 return fnvSuccess; 3104 } 3105 return fnvNull; 3106 } /* end FNV256input */ 3108 /* hash in a string (64 bit) 3109 ********************************************************************/ 3110 int FNV256stringin ( FNV256context *ctx, const char *in ) 3111 { 3112 uint64_t temp[FNV256size/4]; 3113 uint64_t temp2[3]; 3114 int i; 3115 uint8_t ch; 3117 if ( ctx && in ) 3118 { 3119 switch ( ctx->Computed ) 3120 { 3121 case FNVinited+FNV256state: 3122 ctx->Computed = FNVcomputed+FNV256state; 3123 case FNVcomputed+FNV256state: 3124 break; 3125 default: 3126 return fnvStateError; 3127 } 3128 for ( i=0; iHash[i]; 3130 while ( (ch = (uint8_t)*in++) ) 3131 { 3132 /* temp = FNV256prime * ( temp ^ ch ); */ 3133 temp[7] ^= ch; 3134 temp2[2] = temp[7] << FNV256shift; 3135 temp2[1] = temp[6] << FNV256shift; 3136 temp2[0] = temp[5] << FNV256shift; 3137 for ( i=0; i0; --i ) 3143 { 3144 temp[i-1] += temp[i] >> 16; 3145 temp[i] &= 0xFFFF; 3146 } 3147 } 3148 for ( i=0; iHash[i] = temp[i]; 3150 return fnvSuccess; 3151 } 3152 return fnvNull; 3153 } /* end FNV256stringin */ 3155 /* return hash (64 bit) 3156 ********************************************************************/ 3157 int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] ) 3158 { 3159 int i; 3161 if ( ctx && out ) 3162 { 3163 if ( ctx->Computed != FNVcomputed+FNV256state ) 3164 return fnvStateError; 3165 for ( i=0; iHash[i]; 3169 out[31-4*i] = ctx->Hash[i] >> 8; 3170 out[31-4*i] = ctx->Hash[i] >> 16; 3171 out[31-4*i] = ctx->Hash[i] >> 24; 3172 #else 3173 out[4*i] = ctx->Hash[i]; 3174 out[4*i+1] = ctx->Hash[i] >> 8; 3175 out[4*i+2] = ctx->Hash[i] >> 16; 3176 out[4*i+3] = ctx->Hash[i] >> 24; 3177 #endif 3178 ctx -> Hash[i] = 0; 3179 } 3180 ctx->Computed = FNVemptied+FNV256state; 3181 return fnvSuccess; 3182 } 3183 return fnvNull; 3184 } /* end FNV256result */ 3186 /****************************************************************** 3187 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 3188 ******************************************************************/ 3189 #else /* FNV_64bitIntegers */ 3190 /****************************************************************** 3191 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3192 ******************************************************************/ 3194 /* version for when you only have 32-bit arithmetic 3195 ********************************************************************/ 3197 /* 256 bit FNV_prime = 2^168 + 2^8 + 0x63 */ 3198 /* 0x00000000 00000000 00000100 00000000 3199 00000000 00000000 00000000 00000163 */ 3200 #define FNV256primeX 0x0163 3201 #define FNV256shift 8 3203 /* 0xDD268DBCAAC55036 2D98C384C4E576CC 3204 C8B1536847B6BBB3 1023B4C8CAEE0535 */ 3205 uint16_t FNV256basis[FNV256size/2] = { 3206 0xDD26, 0x8DBC, 0xAAC5, 0x5036, 3207 0x2D98, 0xC384, 0xC4E5, 0x76CC, 3208 0xC8B1, 0x5368, 0x47B6, 0xBBB3, 3209 0x1023, 0xB4C8, 0xCAEE, 0x0535 }; 3211 /******************************************************************** 3212 * Set of init, input, and output functions below * 3213 * to incrementally compute FNV256 * 3214 ********************************************************************/ 3216 /* initialize context (32 bit) 3217 ********************************************************************/ 3218 int FNV256init ( FNV256context *ctx ) 3219 { 3220 int i; 3222 if ( ctx ) 3223 { 3224 for ( i=0; iHash[i] = FNV256basis[i]; 3226 ctx->Computed = FNVinited+FNV256state; 3227 return fnvSuccess; 3228 } 3229 return fnvNull; 3230 } /* end FNV256init */ 3232 /* initialize context with a provided basis (32 bit) 3233 ********************************************************************/ 3234 int FNV256initBasis ( FNV256context *ctx, 3235 const uint8_t basis[FNV256size] ) 3236 { 3237 int i; 3238 const uint8_t *ui8p; 3239 uint32_t temp; 3241 if ( ctx ) 3242 { 3243 #ifdef FNV_BigEndian 3244 ui8p = basis; 3245 for ( i=0; i < FNV256size/2; ++i ) 3246 { 3247 temp = *ui8p++; 3248 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 3249 } 3250 #else 3251 ui8p = basis + FNV256size/2 -1; 3252 for ( i=0; i < FNV256size/2; ++i ) 3253 { 3254 temp = *ui8p--; 3255 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 3256 } 3257 #endif 3258 ctx->Computed = FNVinited+FNV256state; 3259 return fnvSuccess; 3260 } 3261 return fnvNull; 3262 } /* end FNV256initBasis */ 3264 /* hash in a counted block (32 bit) 3265 *******************************************************************/ 3266 int FNV256blockin ( FNV256context *ctx, 3267 const void *vin, 3268 long int length ) 3269 { 3270 const uint8_t *in = (const uint8_t*)vin; 3271 uint32_t temp[FNV256size/2]; 3272 uint32_t temp2[6]; 3273 int i; 3275 if ( ctx && in ) 3276 { 3277 if ( length < 0 ) 3278 return fnvBadParam; 3279 switch ( ctx->Computed ) 3280 { 3281 case FNVinited+FNV256state: 3282 ctx->Computed = FNVcomputed+FNV256state; 3283 case FNVcomputed+FNV256state: 3284 break; 3285 default: 3286 return fnvStateError; 3287 } 3289 for ( i=0; iHash[i]; 3291 for ( ; length > 0; length-- ) 3292 { 3293 /* temp = FNV256prime * ( temp ^ *in++ ); */ 3294 temp[15] ^= *in++; 3295 for ( i=0; i<6; ++i ) 3296 temp2[i] = temp[10+i] << FNV256shift; 3297 for ( i=0; i0; --i ) 3302 { 3303 temp[i-1] += temp[i] >> 16; 3304 temp[i] &= 0xFFFF; 3305 } 3306 } 3307 for ( i=0; iHash[i] = temp[i]; 3309 return fnvSuccess; 3310 } 3311 return fnvNull; 3312 } /* end FNV256blockin */ 3314 /* hash in a string (32 bit) 3315 *******************************************************************/ 3316 int FNV256stringin ( FNV256context *ctx, const char *in ) 3317 { 3318 uint32_t temp[FNV256size/2]; 3319 uint32_t temp2[6]; 3320 int i; 3321 uint8_t ch; 3323 if ( ctx && in ) 3324 { 3325 switch ( ctx->Computed ) 3326 { 3327 case FNVinited+FNV256state: 3328 ctx->Computed = FNVcomputed+FNV256state; 3329 case FNVcomputed+FNV256state: 3330 break; 3331 default: 3332 return fnvStateError; 3333 } 3334 for ( i=0; iHash[i]; 3336 while ( ( ch = (uint8_t)*in++ ) != 0) 3337 { 3338 /* temp = FNV256prime * ( temp ^ *in++ ); */ 3339 temp[15] ^= ch; 3340 for ( i=0; i<6; ++i ) 3341 temp2[i] = temp[10+i] << FNV256shift; 3342 for ( i=0; i0; --i ) 3347 { 3348 temp[i-1] += temp[i] >> 16; 3349 temp[i] &= 0xFFFF; 3350 } 3351 } 3352 for ( i=0; iHash[i] = temp[i]; 3354 return fnvSuccess; 3355 } 3356 return fnvNull; 3357 } /* end FNV256stringin */ 3359 /* return hash (32 bit) 3360 ********************************************************************/ 3361 int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] ) 3362 { 3363 int i; 3365 if ( ctx && out ) 3366 { 3367 if ( ctx->Computed != FNVcomputed+FNV256state ) 3368 return fnvStateError; 3369 for ( i=0; iHash[i]; 3373 out[30-2*i] = ctx->Hash[i] >> 8; 3374 #else 3375 out[2*i] = ctx->Hash[i]; 3376 out[2*i+1] = ctx->Hash[i] >> 8; 3377 #endif 3378 ctx->Hash[i] = 0; 3379 } 3380 ctx->Computed = FNVemptied+FNV256state; 3381 return fnvSuccess; 3382 } 3383 return fnvNull; 3384 } /* end FNV256result */ 3386 #endif /* Have64bitIntegers */ 3387 /******************************************************************** 3388 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3389 ********************************************************************/ 3391 #endif /* _FNV256_C_ */ 3392 3394 6.1.5 FNV512 C Code 3396 The header and C source for 512-bit FNV-1a returning a byte vector. 3398 3399 /**************************** FNV512.h **************************/ 3400 /***************** See RFC NNNN for details. ********************/ 3401 /* 3402 * Copyright (c) 2016 IETF Trust and the persons identified as 3403 * authors of the code. All rights reserved. 3404 * See fnv-private.h for terms of use and redistribution. 3405 */ 3407 #ifndef _FNV512_H_ 3408 #define _FNV512_H_ 3410 /* 3411 * Description: 3412 * This file provides headers for the 512-bit version of the 3413 * FNV-1a non-cryptographic hash algorithm. 3414 */ 3416 #include "FNVconfig.h" 3418 #include 3419 #define FNV512size (512/8) 3421 /* If you do not have the ISO standard stdint.h header file, then you 3422 * must typedef the following types: 3423 * 3424 * type meaning 3425 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 3426 * uint32_t unsigned 32 bit integer 3427 * uint16_t unsigned 16 bit integer 3428 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 3429 */ 3431 #ifndef _FNV_ErrCodes_ 3432 #define _FNV_ErrCodes_ 3433 /********************************************************************* 3434 * All FNV functions provided return as integer as follows: 3435 * 0 -> success 3436 * >0 -> error as listed below 3437 */ 3438 enum { /* success and errors */ 3439 fnvSuccess = 0, 3440 fnvNull, /* Null pointer parameter */ 3441 fnvStateError, /* called Input after Result or before Init */ 3442 fnvBadParam /* passed a bad parameter */ 3443 }; 3444 #endif /* _FNV_ErrCodes_ */ 3446 /* 3447 * This structure holds context information for an FNV512 hash 3448 */ 3449 #ifdef FNV_64bitIntegers 3450 /* version if 64 bit integers supported */ 3451 typedef struct FNV512context_s { 3452 int Computed; /* state */ 3453 uint32_t Hash[FNV512size/4]; 3454 } FNV512context; 3456 #else 3457 /* version if 64 bit integers NOT supported */ 3459 typedef struct FNV512context_s { 3460 int Computed; /* state */ 3461 uint16_t Hash[FNV512size/2]; 3462 } FNV512context; 3464 #endif /* FNV_64bitIntegers */ 3466 /* 3467 * Function Prototypes 3468 * FNV512string: hash a zero terminated string not including 3469 * the terminating zero 3470 * FNV512block: FNV512 hash a specified length byte vector 3471 * FNV512init: initializes an FNV512 context 3472 * FNV512initBasis: initializes an FNV512 context with a 3473 * provided basis 3474 * FNV512blockin: hash in a specified length byte vector 3475 * FNV512stringin: hash in a zero terminated string not 3476 * including the zero 3477 * FNV512result: returns the hash value 3478 * 3479 * Hash is returned as an array of 8-bit integers 3480 */ 3482 #ifdef __cplusplus 3483 extern "C" { 3484 #endif 3486 /* FNV512 */ 3487 extern int FNV512string ( const char *in, 3488 uint8_t out[FNV512size] ); 3489 extern int FNV512block ( const void *in, 3490 long int length, 3491 uint8_t out[FNV512size] ); 3492 extern int FNV512init ( FNV512context *); 3493 extern int FNV512initBasis ( FNV512context * const, 3494 const uint8_t basis[FNV512size] ); 3495 extern int FNV512blockin ( FNV512context *, 3496 const void *in, 3497 long int length ); 3498 extern int FNV512stringin ( FNV512context *, 3499 const char *in ); 3500 extern int FNV512result ( FNV512context *, 3501 uint8_t out[FNV512size] ); 3503 #ifdef __cplusplus 3504 } 3505 #endif 3507 #endif /* _FNV512_H_ */ 3508 3510 3511 /***************************** FNV512.c ****************************/ 3512 /******************** See RFC NNNN for details *********************/ 3513 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 3514 * authors of the code. All rights 3515 * See fnv-private.h for terms of use and redistribution. 3516 */ 3518 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 3519 * hash function FNV-1a for 512-bit hashes. 3520 */ 3522 #ifndef _FNV512_C_ 3523 #define _FNV512_C_ 3525 #include "fnv-private.h" 3526 #include "FNV512.h" 3528 /* common code for 64 and 32 bit modes */ 3530 /* FNV512 hash a null terminated string (64/32 bit) 3531 ********************************************************************/ 3532 int FNV512string ( const char *in, uint8_t out[FNV512size] ) 3533 { 3534 FNV512context ctx; 3535 int err; 3536 if ( (err = FNV512init ( &ctx )) != fnvSuccess ) 3537 return err; 3538 if ( (err = FNV512stringin ( &ctx, in )) != fnvSuccess ) 3539 return err; 3540 return FNV512result ( &ctx, out ); 3541 } /* end FNV512string */ 3543 /* FNV512 hash a counted block (64/32 bit) 3544 ********************************************************************/ 3545 int FNV512block ( const void *in, 3546 long int length, 3547 uint8_t out[FNV512size] ) 3548 { 3549 FNV512context ctx; 3550 int err; 3552 if ( (err = FNV512init ( &ctx )) != fnvSuccess ) 3553 return err; 3554 if ( (err = FNV512blockin ( &ctx, in, length)) != fnvSuccess ) 3555 return err; 3556 return FNV512result ( &ctx, out ); 3557 } /* end FNV512block */ 3559 /******************************************************************** 3560 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 3561 ********************************************************************/ 3562 #ifdef FNV_64bitIntegers 3564 /* 3565 512 bit FNV_prime = 2^344 + 2^8 + 0x57 = 3566 0x0000000000000000 0000000000000000 3567 0000000001000000 0000000000000000 3568 0000000000000000 0000000000000000 3569 0000000000000000 0000000000000157 */ 3570 #define FNV512primeX 0x0157 3571 #define FNV512shift 24 3573 /* 0xB86DB0B1171F4416 DCA1E50F309990AC 3574 AC87D059C9000000 0000000000000D21 3575 E948F68A34C192F6 2EA79BC942DBE7CE 3576 182036415F56E34B AC982AAC4AFE9FD9 */ 3578 uint32_t FNV512basis[FNV512size/4] = { 3579 0xB86DB0B1, 0x171F4416, 0xDCA1E50F, 0x209990AC, 3580 0xAC87D059, 0x9C000000, 0x00000000, 0x00000D21, 3581 0xE948F68A, 0x34C192F6, 0x2EA79BC9, 0x42DBE7CE, 3582 0x18203641, 0x5F56E34B, 0xAC982AAC, 0x4AFE9FD9 }; 3584 /******************************************************************** 3585 * Set of init, input, and output functions below * 3586 * to incrementally compute FNV512 * 3587 ********************************************************************/ 3589 /* initialize context (64 bit) 3590 ********************************************************************/ 3591 int FNV512init ( FNV512context *ctx ) 3592 { 3593 if ( ctx ) 3594 { 3595 for ( i=0; iHash[i] = FNV512basis[i]; 3597 ctx->Computed = FNVinited+FNV512state; 3598 return fnvSuccess; 3599 } 3600 return fnvNull; 3601 } /* end FNV512init */ 3603 /* initialize context with a provided basis (64 bit) 3604 ********************************************************************/ 3605 int FNV512initBasis ( FNV512context* const ctx, 3606 const uint8_t basis[FNV512size] ) 3607 { 3608 int i; 3609 const uint8_t *ui8p; 3610 uint32_t temp; 3612 if ( ctx ) 3613 { 3614 #ifdef FNV_BigEndian 3615 ui8p = basis; 3616 for ( i=0; i < FNV512size/4; ++i ) 3617 { 3618 temp = (*ui8p++)<<8; 3619 temp = (temp + *ui8p++)<<8; 3620 temp = (temp + *ui8p++)<<8; 3621 ctx->Hash[i] = temp + *ui8p; 3622 } 3623 #else 3624 ui8p = basis + (FNV512size/4 - 1); 3625 for ( i=0; i < FNV512size/4; ++i ) 3626 { 3627 temp = (*ui8p--)<<8; 3628 temp = (temp + *ui8p--)<<8; 3629 temp = (temp + *ui8p--)<<8; 3630 ctx->Hash[i] = temp + *ui8p; 3631 } 3632 #endif 3633 ctx->Computed = FNVinited+FNV512state; 3634 return fnvSuccess; 3635 } 3636 return fnvNull; 3637 } /* end FNV512initBasis */ 3639 /* hash in a counted block (64 bit) 3640 ********************************************************************/ 3641 int FNV512blockin ( FNV512context *ctx, 3642 const void *vin, 3643 long int length ) 3644 { 3645 const uint8_t *in = (const uint8_t*)vin; 3646 uint64_t temp[FNV512size/4]; 3647 uint64_t temp2[3]; 3649 if ( ctx && in ) 3650 { 3651 switch ( ctx->Computed ) 3652 { 3653 case FNVinited+FNV512state: 3654 ctx->Computed = FNVcomputed+FNV128state; 3655 case FNVcomputed+FNV512state: 3656 break; 3657 default: 3658 return fnvStateError; 3659 } 3660 if ( length < 0 ) 3661 return fnvBadParam; 3662 for ( i=0; iHash[i]; 3664 for ( ; length > 0; length-- ) 3665 { 3666 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3667 temp[7] ^= *in++; 3668 temp2[2] = temp[7] << FNV512shift; 3669 temp2[1] = temp[6] << FNV512shift; 3670 temp2[0] = temp[5] << FNV512shift; 3671 for ( i=0; i0; --i ) 3677 { 3678 temp[i-1] += temp[i] >> 16; 3679 temp[i] &= 0xFFFF; 3680 } 3681 } 3682 for ( i=0; iHash[i] = temp[i]; 3684 return fnvSuccess; 3685 } 3686 return fnvNull; 3687 } /* end FNV512input */ 3689 /* hash in a string (64 bit) 3690 ********************************************************************/ 3691 inf FNV512stringin ( FNV512context *ctx, const char *in ) 3692 { 3693 uint64_t temp[FNV512size/4]; 3694 uint64_t temp2[2]; 3695 int i; 3696 uint8_t ch; 3698 if ( ctx && in ) 3699 { 3700 switch ( ctx->Computed ) 3701 { 3702 case FNVinited+FNV512state: 3703 ctx->Computed = FNVcomputed+FNV512state; 3704 case FNVcomputed+FNV512state: 3705 break; 3706 default: 3707 return fnvStateError; 3708 } 3709 for ( i=0; iHash[i]; 3711 while ( ch = (uint8_t)*in++ ) 3712 { 3713 /* temp = FNV512prime * ( temp ^ ch ); */ 3714 temp[7] ^= ch; 3715 temp2[2] = temp[7] << FNV128shift; 3716 temp2[1] = temp[6] << FNV128shift; 3717 temp2[0] = temp[5] << FNV128shift; 3718 for ( i=0; i0; --i ) 3724 { 3725 temp[i-1] += temp[i] >> 16; 3726 temp[i] &= 0xFFFF; 3727 } 3728 } 3729 for ( i=0; iHash[i] = temp[i]; 3731 return fnvSuccess; 3732 } 3733 return fnvNull; 3734 } /* end FNV512stringin */ 3735 /* return hash (64 bit) 3736 ********************************************************************/ 3737 int FNV512result ( FNV512context *ctx, uint8_t out[FNV512size] ) 3738 { 3739 if ( ctx && out ) 3740 { 3741 if ( ctx->Computed != FNVcomputed+FNV512state ) 3742 return fnvStateError; 3743 for ( i=0; iHash[i]; 3747 out[14-2*i] = ctx->Hash[i] >> 8; 3748 #else 3749 out[2*i] = ctx->Hash[i]; 3750 out[2*i+1] = ctx->Hash[i] >> 8; 3751 #endif 3752 ctx -> Hash[i] = 0; 3753 } 3754 ctx->Computed = FNVemptied+FNV512state; 3755 return fnvSuccess; 3756 } 3757 return fnvNull; 3758 } /* end FNV512result */ 3760 /****************************************************************** 3761 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 3762 ******************************************************************/ 3763 #else /* FNV_64bitIntegers */ 3764 /****************************************************************** 3765 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3766 ******************************************************************/ 3768 /* version for when you only have 32-bit arithmetic 3769 ********************************************************************/ 3771 /* 3772 512 bit FNV_prime = 2^344 + 2^8 + 0x57 = 3773 0x0000000000000000 0000000000000000 3774 0000000001000000 0000000000000000 3775 0000000000000000 0000000000000000 3776 0000000000000000 0000000000000157 */ 3777 #define FNV512primeX 0x0157 3778 #define FNV512shift 8 3780 /* 0xB86DB0B1171F4416 DCA1E50F309990AC 3781 AC87D059C9000000 0000000000000D21 3782 E948F68A34C192F6 2EA79BC942DBE7CE 3783 182036415F56E34B AC982AAC4AFE9FD9 */ 3785 uint16_t FNV512basis[FNV512size/2] = { 3786 0xB86D, 0xB0B1, 0x171F, 0x4416, 0xDCA1, 0xE50F, 0x3099, 0x90AC, 3787 0xAC87, 0xD059, 0xC900, 0x0000, 0x0000, 0x0000, 0x0000, 0x0D21, 3788 0xE948, 0xF68A, 0x34C1, 0x92F6, 0x2EA7, 0x9BC9, 0x42DB, 0xE7CE, 3789 0x1820, 0x3641, 0x5F56, 0xE34B, 0xAC98, 0x2AAC, 0x4AFE, 0x9FD9 }; 3791 /******************************************************************** 3792 * Set of init, input, and output functions below * 3793 * to incrementally compute FNV512 * 3794 ********************************************************************/ 3796 /* initialize context (32 bit) 3797 ********************************************************************/ 3798 int FNV512init ( FNV512context *ctx ) 3799 { 3800 int i; 3802 if ( ctx ) 3803 { 3804 for ( i=0; iHash[i] = FNV512basis[i]; 3806 ctx->Computed = FNVinited+FNV512state; 3807 return fnvSuccess; 3808 } 3809 return fnvNull; 3810 } /* end FNV512init */ 3812 /* initialize context with a provided basis (32 bit) 3813 ********************************************************************/ 3814 int FNV512initBasis ( FNV512context *ctx, 3815 const uint8_t basis[FNV512size] ) 3816 { 3817 int i; 3818 const uint8_t *ui8p; 3819 uint32_t temp; 3821 if ( ctx ) 3822 { 3823 #ifdef FNV_BigEndian 3824 ui8p = basis; 3825 for ( i=0; i < FNV512size/2; ++i ) 3826 { 3827 temp = *ui8p++; 3828 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 3829 } 3830 #else 3831 ui8p = basis + ( FNV512size/2 - 1 ); 3832 for ( i=0; i < FNV512size/2; ++i ) 3833 { 3834 temp = *ui8p--; 3835 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 3836 } 3837 #endif 3838 ctx->Computed = FNVinited+FNV512state; 3839 return fnvSuccess; 3840 } 3841 return fnvNull; 3842 } /* end FNV512initBasis */ 3844 /* hash in a counted block (32 bit) 3845 *******************************************************************/ 3846 int FNV512blockin ( FNV512context *ctx, 3847 const void *vin, 3848 long int length ) 3849 { 3850 const uint8_t *in = (const uint8_t*)vin; 3851 uint32_t temp[FNV512size/2]; 3852 uint32_t temp2[6]; 3853 int i; 3855 if ( ctx && in ) 3856 { 3857 switch ( ctx->Computed ) 3858 { 3859 case FNVinited+FNV512state: 3860 ctx->Computed = FNVcomputed+FNV512state; 3861 case FNVcomputed+FNV512state: 3862 break; 3863 default: 3864 return fnvStateError; 3865 } 3866 if ( length < 0 ) 3867 return fnvBadParam; 3868 for ( i=0; iHash[i]; 3870 for ( ; length > 0; length-- ) 3871 { 3872 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3873 temp[15] ^= *in++; 3874 for ( i=0; i<6; ++i ) 3875 temp2[i] = temp[10+i] << FNV512shift; 3876 for ( i=0; i0; --i ) 3881 { 3882 temp[i-1] += temp[i] >> 16; 3883 temp[i] &= 0xFFFF; 3884 } 3885 } 3886 for ( i=0; iHash[i] = temp[i]; 3888 return fnvSuccess; 3889 } 3890 return fnvNull; 3891 } /* end FNV512blockin */ 3893 /* hash in a string (32 bit) 3894 *******************************************************************/ 3895 int FNV512stringin ( FNV512context *ctx, const char *in ) 3896 { 3897 uint32_t temp[FNV512size/2]; 3898 uint32_t temp2[6]; 3899 int i; 3900 uint8_t ch; 3902 if ( ctx && in ) 3903 { 3904 switch ( ctx->Computed ) 3905 { 3906 case FNVinited+FNV512state: 3907 ctx->Computed = FNVcomputed+FNV512state; 3908 case FNVcomputed+FNV512state: 3909 break; 3910 default: 3911 return fnvStateError; 3912 } 3913 for ( i=0; iHash[i]; 3915 while ( (ch = (uint8_t)*in++) ) 3916 { 3917 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3918 temp[15] ^= ch; 3919 for ( i=0; i<6; ++i ) 3920 temp2[i] = temp[10+i] << FNV512shift; 3921 for ( i=0; i0; --i ) 3926 { 3927 temp[i-1] += temp[i] >> 16; 3928 temp[i] &= 0xFFFF; 3929 } 3930 } 3931 for ( i=0; iHash[i] = temp[i]; 3933 return fnvSuccess; 3934 } 3935 return fnvNull; 3936 } /* end FNV512stringin */ 3938 /* return hash (32 bit) 3939 ********************************************************************/ 3940 int FNV512result ( FNV512context *ctx, unsigned char out[16] ) 3941 { 3942 int i; 3944 if ( ctx && out ) 3945 { 3946 if ( ctx->Computed != FNVcomputed+FNV512state ) 3947 return fnvStateError; 3948 for ( i=0; iHash[i]; 3952 out[30-2*i] = ctx->Hash[i] >> 8; 3953 #else 3954 out[2*i] = ctx->Hash[i]; 3955 out[2*i+1] = ctx->Hash[i] >> 8; 3956 #endif 3957 ctx->Hash[i] = 0; 3958 } 3959 ctx->Computed = FNVemptied+FNV512state; 3960 return fnvSuccess; 3961 } 3962 return fnvNull; 3963 } /* end FNV512result */ 3965 #endif /* FNV_64bitIntegers */ 3966 /******************************************************************** 3967 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3968 ********************************************************************/ 3970 #endif /* _FNV512_C_ */ 3971 3973 6.1.6 FNV1024 C Code 3975 The header and C source for 1024-bit FNV-1a returning a byte vector. 3977 3978 /*************************** FNV1024.h **************************/ 3979 /***************** See RFC NNNN for details. ********************/ 3980 /* 3981 * Copyright (c) 2016 IETF Trust and the persons identified as 3982 * authors of the code. All rights reserved. 3983 * See fnv-private.h for terms of use and redistribution. 3984 */ 3986 #ifndef _FNV1024_H_ 3987 #define _FNV1024_H_ 3989 /* 3990 * Description: 3991 * This file provides headers for the 1024-bit version of the 3992 * FNV-1a non-cryptographic hash algorithm. 3993 */ 3995 #include "FNVconfig.h" 3997 #include 3998 #define FNV1024size (1024/8) 4000 /* If you do not have the ISO standard stdint.h header file, then you 4001 * must typedef the following types: 4002 * 4003 * type meaning 4004 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 4005 * uint32_t unsigned 32 bit integer 4006 * uint16_t unsigned 16 bit integer 4007 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 4008 */ 4010 #ifndef _FNV_ErrCodes_ 4011 #define _FNV_ErrCodes_ 4012 /********************************************************************* 4013 * All FNV functions provided return as integer as follows: 4014 * 0 -> success 4015 * >0 -> error as listed below 4016 */ 4017 enum { /* success and errors */ 4018 fnvSuccess = 0, 4019 fnvNull, /* Null pointer parameter */ 4020 fnvStateError, /* called Input after Result or before Init */ 4021 fnvBadParam /* passed a bad parameter */ 4022 }; 4023 #endif /* _FNV_ErrCodes_ */ 4025 /* 4026 * This structure holds context information for an FNV1024 hash 4027 */ 4028 #ifdef FNV_64bitIntegers 4029 /* version if 64 bit integers supported */ 4030 typedef struct FNV1024context_s { 4031 int Computed; /* state */ 4032 uint32_t Hash[FNV1024size/4]; 4033 } FNV1024context; 4035 #else 4036 /* version if 64 bit integers NOT supported */ 4038 typedef struct FNV1024context_s { 4039 int Computed; /* state */ 4040 uint16_t Hash[FNV1024size/2]; 4041 } FNV1024context; 4043 #endif /* FNV_64bitIntegers */ 4045 /* 4046 * Function Prototypes 4047 * FNV1024string: hash a zero terminated string not including 4048 * the terminating zero 4049 * FNV1024block: FNV1024 hash a specified length byte vector 4050 * FNV1024init: initializes an FNV1024 context 4051 * FNV1024initBasis: initializes an FNV1024 context with a 4052 * provided basis 4053 * FNV1024blockin: hash in a specified length byte vector 4054 * FNV1024stringin: hash in a zero terminated string not 4055 * including the zero 4056 * FNV1024result: returns the hash value 4057 * 4058 * Hash is returned as an array of 8-bit integers 4059 */ 4061 #ifdef __cplusplus 4062 extern "C" { 4063 #endif 4065 /* FNV1024 */ 4066 extern int FNV1024string ( const char *in, 4067 unsigned char out[FNV1024size] ); 4068 extern int FNV1024block ( const void *in, 4069 long int length, 4070 unsigned char out[FNV1024size] ); 4071 extern int FNV1024init ( FNV1024context *); 4072 extern int FNV1024initBasis ( FNV1024context * const, 4073 const uint8_t basis[FNV1024size] ); 4074 extern int FNV1024blockin ( FNV1024context *, 4075 const void *in, 4076 long int length ); 4077 extern int FNV1024stringin ( FNV1024context *, 4078 const char *in ); 4079 extern int FNV1024result ( FNV1024context *, 4080 unsigned char out[FNV1024size] ); 4082 #ifdef __cplusplus 4083 } 4084 #endif 4086 #endif /* _FNV1024_H_ */ 4087 4089 4090 /***************************** FNV1024.c ****************************/ 4091 /******************** See RFC NNNN for details *********************/ 4092 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 4093 * authors of the code. All rights 4094 * See fnv-private.h for terms of use and redistribution. 4095 */ 4097 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 4098 * hash function FNV-1a for 1024-bit hashes. 4099 */ 4101 #ifndef _FNV1024_C_ 4102 #define _FNV1024_C_ 4104 #include "fnv-private.h" 4105 #include "FNV1024.h" 4107 /* common code for 64 and 32 bit modes */ 4109 /* FNV1024 hash a null terminated string (64/32 bit) 4110 ********************************************************************/ 4111 int FNV1024string ( const char *in, uint8_t out[FNV1024size] ) 4112 { 4113 FNV1024context ctx; 4114 int err; 4116 if ( (err = FNV1024init ( &ctx )) != fnvSuccess) 4117 return err; 4118 if ( (err = FNV1024stringin ( &ctx, in )) != fnvSuccess) 4119 return err; 4120 return FNV1024result ( &ctx, out ); 4121 } /* end FNV1024string */ 4123 /* FNV1024 hash a counted block (64/32 bit) 4124 ********************************************************************/ 4125 int FNV1024block ( const void *in, 4126 long int length, 4127 uint8_t out[FNV1024size] ) 4128 { 4129 FNV1024context ctx; 4130 int err; 4131 if ( (err = FNV1024init ( &ctx )) != fnvSuccess) 4132 return err; 4133 if ( (err = FNV1024blockin ( &ctx, in, length)) != fnvSuccess) 4134 return err; 4135 return FNV1024result ( &ctx, out ); 4136 } /* end FNV1024block */ 4138 /******************************************************************** 4139 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 4140 ********************************************************************/ 4141 #ifdef FNV_64bitIntegers 4143 /* 4144 1024 bit FNV_prime = 2^680 + 2^8 + 0x8d = 4145 0x0000000000000000 0000010000000000 4146 0000000000000000 0000000000000000 4147 0000000000000000 0000000000000000 4148 0000000000000000 0000000000000000 4149 0000000000000000 0000000000000000 4150 0000000000000000 000000000000018D 4151 #define FNV1024primeX 0x018D 4152 #define FNV1024shift 24 4154 /* 0x0000000000000000 005F7A76758ECC4D 4155 32E56D5A591028B7 4B29FC4223FDADA1 4156 6C3BF34EDA3674DA 9A21D90000000000 4157 0000000000000000 0000000000000000 4158 0000000000000000 0000000000000000 4159 0000000000000000 000000000004C6D7 4160 EB6E73802734510A 555F256CC005AE55 4161 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 */ 4163 uint32_t FNV1024basis[FNV1024size/4] = { 4164 0x00000000, 0x00000000, 0x005F7A76, 0x758ECC4D, 4165 0x32E56D5A, 0x591028B7, 0x4B29FC42, 0x23FDADA1, 4166 0x6C3BF34E, 0xDA3674DA, 0x9A21D900, 0x00000000, 4167 0x00000000, 0x00000000, 0x00000000, 0x00000000, 4168 0x00000000, 0x00000000, 0x00000000, 0x00000000, 4169 0x00000000, 0x00000000, 0x00000000, 0x0004C6D7, 4170 0xEB6E7380, 0x2734510A, 0x555F256C, 0xC005AE55, 4171 0x6BDE8CC9, 0xC6A93B21, 0xAFF4B16C, 0x71EE90B3 4172 }; 4174 /******************************************************************** 4175 * Set of init, input, and output functions below * 4176 * to incrementally compute FNV1024 * 4177 ********************************************************************/ 4179 /* initialize context (64 bit) 4180 ********************************************************************/ 4181 int FNV1024init ( FNV1024context *ctx ) 4182 { 4183 if ( ctx ) 4184 { 4185 for ( i=0; iHash[i] = FNV1024basis[i]; 4187 ctx->Computed = FNVinited+FNV1024state; 4188 return fnvSuccess; 4189 } 4190 return fnvNull; 4191 } /* end FNV1024init */ 4193 /* initialize context with a provided basis (64 bit) 4194 ********************************************************************/ 4195 int FNV1024initBasis ( FNV1024context* const ctx, 4196 const uint8_t basis[FNV1024size] ) 4197 { 4198 int i; 4199 uint8_t *ui8p; 4200 uint32_t temp; 4202 if ( ctx ) 4203 { 4204 #ifdef FNV_BigEndian 4205 ui8p = basis; 4206 for ( i=0; i < FNV1024size/4; ++i ) 4207 { 4208 temp = (*ui8p++)<<8; 4209 temp = (temp + *ui8p++)<<8; 4210 temp = (temp + *ui8p++)<<8; 4211 ctx->Hash[i] = temp + *ui8p; 4212 } 4213 #else 4214 ui8p = basis + (FNV1024size/4 - 1); 4215 for ( i=0; i < FNV1024size/4; ++i ) 4216 { 4217 temp = (*ui8p--)<<8; 4218 temp = (temp + *ui8p--)<<8; 4219 temp = (temp + *ui8p--)<<8; 4220 ctx->Hash[i] = temp + *ui8p; 4221 } 4222 #endif 4223 ctx->Computed = FNVinited+FNV1024state; 4224 return fnvSuccess; 4225 } 4226 return fnvNull; 4227 } /* end FNV1024initBasis */ 4229 /* hash in a counted block (64 bit) 4230 ********************************************************************/ 4231 int FNV1024blockin ( FNV1024context *ctx, 4232 const void *vin, 4233 long int length ) 4234 { 4235 const uint8_t *in = (const uint8_t*)vin; 4236 uint64_t temp[FNV1024size/4]; 4237 uint64_t temp2[3]; 4239 if ( ctx && in ) 4240 { 4241 switch ( ctx->Computed ) 4242 { 4243 case FNVinited+FNV1024state: 4244 ctx->Computed = FNVcomputed+FNV128state; 4245 case FNVcomputed+FNV1024state: 4246 break; 4247 default: 4248 return fnvStateError; 4249 } 4250 if ( length < 0 ) 4251 return fnvBadParam; 4252 for ( i=0; iHash[i]; 4254 for ( ; length > 0; length-- ) 4255 { 4256 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 4257 temp[7] ^= *in++; 4258 temp2[2] = temp[7] << FNV1024shift; 4259 temp2[1] = temp[6] << FNV1024shift; 4260 temp2[0] = temp[5] << FNV1024shift; 4261 for ( i=0; i0; --i ) 4267 { 4268 temp[i-1] += temp[i] >> 16; 4269 temp[i] &= 0xFFFF; 4270 } 4271 } 4272 for ( i=0; iHash[i] = temp[i]; 4274 return fnvSuccess; 4275 } 4276 return fnvNull; 4277 } /* end FNV1024input */ 4279 /* hash in a string (64 bit) 4280 ********************************************************************/ 4281 inf FNV1024stringin ( FNV1024context *ctx, const char *in ) 4282 { 4283 uint64_t temp[FNV1024size/4]; 4284 uint64_t temp2[2]; 4285 int i; 4286 uint8_t ch; 4288 if ( ctx && in ) 4289 { 4290 switch ( ctx->Computed ) 4291 { 4292 case FNVinited+FNV1024state: 4293 ctx->Computed = FNVcomputed+FNV1024state; 4294 case FNVcomputed+FNV1024state: 4295 break; 4296 default: 4297 return fnvStateError; 4298 } 4299 for ( i=0; iHash[i]; 4301 while ( ch = (uint8_t)*in++ ) 4302 { 4303 /* temp = FNV1024prime * ( temp ^ ch ); */ 4304 temp[7] ^= ch; 4305 temp2[2] = temp[7] << FNV128shift; 4306 temp2[1] = temp[6] << FNV128shift; 4307 temp2[0] = temp[5] << FNV128shift; 4308 for ( i=0; i0; --i ) 4314 { 4315 temp[i-1] += temp[i] >> 16; 4316 temp[i] &= 0xFFFF; 4317 } 4318 } 4319 for ( i=0; iHash[i] = temp[i]; 4321 return fnvSuccess; 4322 } 4323 return fnvNull; 4324 } /* end FNV1024stringin */ 4326 /* return hash (64 bit) 4327 ********************************************************************/ 4328 int FNV1024result ( FNV1024context *ctx, uint8_t out[FNV1024size] ) 4329 { 4330 if ( ctx && out ) 4331 { 4332 if ( ctx->Computed != FNVcomputed+FNV1024state ) 4333 return fnvStateError; 4334 for ( i=0; iHash[i]; 4338 out[14-2*i] = ctx->Hash[i] >> 8; 4339 #else 4340 out[2*i] = ctx->Hash[i]; 4341 out[2*i+1] = ctx->Hash[i] >> 8; 4342 #endif 4343 ctx -> Hash[i] = 0; 4344 } 4345 ctx->Computed = FNVemptied+FNV1024state; 4346 return fnvSuccess; 4347 } 4348 return fnvNull; 4349 } /* end FNV1024result */ 4351 /****************************************************************** 4352 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 4353 ******************************************************************/ 4354 #else /* FNV_64bitIntegers */ 4355 /****************************************************************** 4356 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 4357 ******************************************************************/ 4359 /* version for when you only have 32-bit arithmetic 4360 ********************************************************************/ 4362 /* 4363 1024 bit FNV_prime = 2^680 + 2^8 + 0x8d = 4364 0x0000000000000000 0000010000000000 4365 0000000000000000 0000000000000000 4366 0000000000000000 0000000000000000 4367 0000000000000000 0000000000000000 4368 0000000000000000 0000000000000000 4369 0000000000000000 000000000000018D */ 4370 #define FNV1024primeX 0x018D 4371 #define FNV1024shift 8 4373 /* 0x0000000000000000 005F7A76758ECC4D 4374 32E56D5A591028B7 4B29FC4223FDADA1 4375 6C3BF34EDA3674DA 9A21D90000000000 4376 0000000000000000 0000000000000000 4377 0000000000000000 0000000000000000 4378 0000000000000000 000000000004C6D7 4379 EB6E73802734510A 555F256CC005AE55 4380 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 */ 4382 uint16_t FNV1024basis[FNV1024size/2] = { 4383 0x0000, 0x0000, 0x0000, 0x0000, 0x005F, 0x7A76, 0x758E, 0xCC4D, 4384 0x32E5, 0x6D5A, 0x5910, 0x28B7, 0x4B29, 0xFC42, 0x23FD, 0xADA1, 4385 0x6C3B, 0xF34E, 0xDA36, 0x74DA, 0x9A21, 0xD900, 0x0000, 0x0000, 4386 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 4387 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 4388 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0004, 0xC6D7, 4389 0xEB6E, 0x7380, 0x2734, 0x510A, 0x555F, 0x256C, 0xC005, 0xAE55, 4390 0x6BDE, 0x8CC9, 0xC6A9, 0x3B21, 0xAFF4, 0xB16C, 0x71EE, 0x90B3 4391 }; 4393 /******************************************************************** 4394 * Set of init, input, and output functions below * 4395 * to incrementally compute FNV1024 * 4396 ********************************************************************/ 4398 /* initialize context (32 bit) 4399 ********************************************************************/ 4400 int FNV1024init ( FNV1024context *ctx ) 4401 { 4402 int i; 4404 if ( ctx ) 4405 { 4406 for ( i=0; iHash[i] = FNV1024basis[i]; 4408 ctx->Computed = FNVinited+FNV1024state; 4409 return fnvSuccess; 4410 } 4411 return fnvNull; 4412 } /* end FNV1024init */ 4414 /* initialize context with a provided basis (32 bit) 4415 ********************************************************************/ 4416 int FNV1024initBasis ( FNV1024context *ctx, 4417 const uint8_t basis[FNV1024size] ) 4418 { 4419 int i; 4420 const uint8_t *ui8p; 4421 uint32_t temp; 4423 if ( ctx ) 4424 { 4425 #ifdef FNV_BigEndian 4426 ui8p = basis; 4427 for ( i=0; i < FNV1024size/2; ++i ) 4428 { 4429 temp = *ui8p++; 4430 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 4431 } 4432 #else 4433 ui8p = basis + ( FNV1024size/2 - 1 ); 4434 for ( i=0; i < FNV1024size/2; ++i ) 4435 { 4436 temp = *ui8p--; 4437 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 4438 } 4439 #endif 4440 ctx->Computed = FNVinited+FNV1024state; 4441 return fnvSuccess; 4442 } 4443 return fnvNull; 4444 } /* end FNV1024initBasis */ 4446 /* hash in a counted block (32 bit) 4447 *******************************************************************/ 4448 int FNV1024blockin ( FNV1024context *ctx, 4449 const void *vin, 4450 long int length ) 4451 { 4452 const uint8_t *in = (const uint8_t*)vin; 4453 uint32_t temp[FNV1024size/2]; 4454 uint32_t temp2[6]; 4455 int i; 4457 if ( ctx && in ) 4458 { 4459 switch ( ctx->Computed ) 4460 { 4461 case FNVinited+FNV1024state: 4462 ctx->Computed = FNVcomputed+FNV1024state; 4463 case FNVcomputed+FNV1024state: 4464 break; 4465 default: 4466 return fnvStateError; 4467 } 4468 if ( length < 0 ) 4469 return fnvBadParam; 4470 for ( i=0; iHash[i]; 4472 for ( ; length > 0; length-- ) 4473 { 4474 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 4475 temp[15] ^= *in++; 4476 for ( i=0; i<6; ++i ) 4477 temp2[i] = temp[10+i] << FNV1024shift; 4478 for ( i=0; i0; --i ) 4483 { 4484 temp[i-1] += temp[i] >> 16; 4485 temp[i] &= 0xFFFF; 4486 } 4487 } 4488 for ( i=0; iHash[i] = temp[i]; 4490 return fnvSuccess; 4491 } 4492 return fnvNull; 4493 } /* end FNV1024blockin */ 4495 /* hash in a string (32 bit) 4496 *******************************************************************/ 4497 int FNV1024stringin ( FNV1024context *ctx, const char *in ) 4498 { 4499 uint32_t temp[FNV1024size/2]; 4500 uint32_t temp2[6]; 4501 int i; 4502 uint8_t ch; 4504 if ( ctx && in ) 4505 { 4506 switch ( ctx->Computed ) 4507 { 4508 case FNVinited+FNV1024state: 4509 ctx->Computed = FNVcomputed+FNV1024state; 4510 case FNVcomputed+FNV1024state: 4511 break; 4512 default: 4513 return fnvStateError; 4514 } 4515 for ( i=0; iHash[i]; 4517 while ( (ch = (uint8_t)*in++) ) 4518 { 4519 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 4520 temp[15] ^= ch; 4521 for ( i=0; i<6; ++i ) 4522 temp2[i] = temp[10+i] << FNV1024shift; 4523 for ( i=0; i0; --i ) 4528 { 4529 temp[i-1] += temp[i] >> 16; 4530 temp[i] &= 0xFFFF; 4531 } 4532 } 4533 for ( i=0; iHash[i] = temp[i]; 4535 return fnvSuccess; 4536 } 4537 return fnvNull; 4538 } /* end FNV1024stringin */ 4540 /* return hash (32 bit) 4541 ********************************************************************/ 4542 int FNV1024result ( FNV1024context *ctx, unsigned char out[16] ) 4543 { 4544 int i; 4546 if ( ctx && out ) 4547 { 4548 if ( ctx->Computed != FNVcomputed+FNV1024state ) 4549 return fnvStateError; 4550 for ( i=0; iHash[i]; 4554 out[30-2*i] = ctx->Hash[i] >> 8; 4555 #else 4556 out[2*i] = ctx->Hash[i]; 4557 out[2*i+1] = ctx->Hash[i] >> 8; 4558 #endif 4559 ctx->Hash[i] = 0; 4560 } 4561 ctx->Computed = FNVemptied+FNV1024state; 4562 return fnvSuccess; 4563 } 4564 return fnvNull; 4565 } /* end FNV1024result */ 4567 #endif /* FNV_64bitIntegers */ 4568 /******************************************************************** 4569 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 4570 ********************************************************************/ 4572 #endif /* _FNV1024_C_ */ 4573 4575 6.2 FNV Test Code 4577 Here is a test driver: 4579 4580 /**************************** MAIN.c ****************************/ 4581 /****************** See RFC NNNN for details. *******************/ 4582 /* 4583 * Copyright (c) 2016 IETF Trust and the persons identified as 4584 * authors of the code. All rights reserved. 4585 * See fnv-private.h for terms of use and redistribution. 4586 */ 4587 /* to do a thorough test you need to run will all four 4588 combinations of the following defined/undefined */ 4590 // #define FNV_64bitIntegers 4591 // #define FNV_BigEndian 4593 #include 4594 #include 4596 #include "fnv-private.h" 4597 #include "FNV.h" 4599 /* global variables */ 4600 char *funcName; 4601 char *errteststring = "foo"; 4602 int Terr; /* Total errors */ 4603 #define NTestBytes 3 4604 uint8_t errtestbytes[NTestBytes] = { (uint8_t)1, 4605 (uint8_t)2, (uint8_t)3 }; 4607 #define NTstrings 3 4608 char *teststring[NTstrings] = { "", "a", "foobar" }; 4610 /***************************************************************** 4611 * local prototypes 4612 *****************************************************************/ 4613 int TestR ( char *, int should, int was ); 4614 void TestNValue ( char *subfunc, 4615 char *string, 4616 int N, 4617 uint8_t *should, 4618 uint8_t *was ); 4619 void HexPrint ( int i, unsigned char *p ); 4620 void Test32 (); 4621 void Test32Value ( char *subfunc, char *string, 4622 uint32_t was, uint32_t should ); 4623 void Test64 (); 4624 #ifdef FNV_64bitIntegers 4625 void Test64Value ( char *subfunc, char *string, 4626 uint64_t should, uint64_t was ); 4627 #else 4628 #define uint64_t foobar 4629 #endif /* FNB_64bitIntegers */ 4630 void Test128 (); 4631 void Test256 (); 4632 void Test512 (); 4633 void Test1024 (); 4635 void TestNValue ( char *subfunc, 4636 char *string, 4637 int N, 4638 uint8_t was[N], 4639 uint8_t should[N] ); 4641 /***************************************************************** 4642 * main 4643 *****************************************************************/ 4644 int main (int argc, const char * argv[]) 4645 { 4646 #ifdef FNV_64bitIntegers 4647 printf ("Have 64-bit Integers. "); 4648 #else 4649 printf ("Do not have 64-bit integers. "); 4650 #endif 4651 #ifdef FNV_BigEndian 4652 printf ("Calculating for Big Endian.0); 4653 #else 4654 printf ("Not calculating for Big Endian.0); 4655 #endif 4656 funcName = "Testing TestR "; 4657 /* test the Test Return function */ 4658 TestR ( "should fail", 1, 2 ); 4659 TestR ( "should not have failed", 0, 0 ); 4661 Test32(); 4662 Test64(); 4663 Test128(); 4664 Test256(); 4665 Test512(); 4666 Test1024(); 4668 printf ("Type return to exit.0); 4669 (void)getchar(); 4670 printf ("Goodbye!0); 4672 return 0; 4673 } /* end main */ 4674 /* Test status returns 4675 *****************************************************************/ 4676 int TestR ( char *name, int expect, int actual ) 4677 { 4678 if ( expect != actual ) 4679 { 4680 printf ( "%s%s returned %i instead of %i.0, 4681 funcName, name, actual, expect ); 4682 ++Terr; 4683 } 4684 return actual; 4685 } /* end TestR */ 4687 /* Return true if the bytes are in reverse order from each other */ 4688 int revcmp(uint8_t *buf1, uint8_t *buf2, int N) { 4689 int i; 4690 uint8_t *bufc = buf2 + N; 4691 for ( i = 0; i < N / 2; i++ ) 4692 if (*buf1++ != *--bufc) 4693 return 0; 4694 return 1; 4695 } 4697 /* General byte vector return error test 4698 *****************************************************************/ 4699 void TestNValue ( char *subfunc, 4700 char *string, 4701 int N, 4702 uint8_t *was, 4703 uint8_t *should ) 4704 { 4705 #ifdef FNV_BigEndian 4706 if ( revcmp ( was, should, N) == 0) 4707 #else 4708 if ( memcmp ( was, should, N) != 0) 4709 #endif 4710 { 4711 printf ( "%s %s of '%s' computed ", funcName, subfunc, string ); 4712 HexPrint ( N, was ); 4713 printf ( ", should have been " ); 4714 HexPrint ( N, should ); 4715 printf ( ".0 ); 4716 ++Terr; 4717 } 4718 } /* end TestNValue */ 4720 /* print some hex 4721 *****************************************************************/ 4722 void HexPrint ( int count, unsigned char *ptr ) 4723 { 4724 int i; 4726 for ( i = 0; i < count; ++i ) 4727 printf ( "%02X", ptr[i] ); 4728 } /* end HexPrint */ 4730 /***************************************************************** 4731 * FNV32 test 4732 *****************************************************************/ 4733 void Test32 () 4734 { 4735 int i, err; 4736 long int iLen; 4737 uint32_t eUint32; 4738 FNV32context eContext; 4739 uint32_t FNV32svalues[NTstrings] = { 4740 0x811c9dc5, 0xe40c292c, 0xbf9cf968 }; 4741 uint32_t FNV32bvalues[NTstrings] = { 4742 0x050c5d1f, 0x2b24d044, 0x0c1c9eb8 }; 4744 /* test Test32Value */ 4745 funcName = "Test32Value"; 4746 Test32Value ( "should fail", "test", FNV32svalues[1], FNV32svalues[2] ); 4748 funcName = "FNV32"; 4750 /* test error checks */ 4751 Terr = 0; 4752 TestR ( "init", fnvSuccess, FNV32init (&eContext) ); 4753 TestR ( "string", fnvNull, 4754 FNV32string ( (char *)0, &eUint32 ) ); 4755 TestR ( "string", fnvNull, 4756 FNV32string ( errteststring, (uint32_t *)0 ) ); 4757 TestR ( "block", fnvNull, 4758 FNV32block ( (uint8_t *)0, 1, &eUint32 ) ); 4759 TestR ( "block", fnvBadParam, 4760 FNV32block ( errtestbytes, -1, &eUint32 ) ); 4761 TestR ( "block", fnvNull, 4762 FNV32block ( errtestbytes, 1, (uint32_t *)0 ) ); 4763 TestR ( "init", fnvNull, 4764 FNV32init ( (FNV32context *)0 ) ); 4765 TestR ( "initBasis", fnvNull, 4766 FNV32initBasis ( (FNV32context *)0, 42 ) ); 4767 TestR ( "blockin", fnvNull, 4768 FNV32blockin ( (FNV32context *)0, 4769 errtestbytes, NTestBytes ) ); 4770 TestR ( "blockin", fnvNull, 4771 FNV32blockin ( &eContext, (uint8_t *)0, 4772 NTestBytes ) ); 4774 TestR ( "blockin", fnvBadParam, 4775 FNV32blockin ( &eContext, errtestbytes, -1 ) ); 4776 eContext.Computed = FNVclobber+FNV32state; 4777 TestR ( "blockin", fnvStateError, 4778 FNV32blockin ( &eContext, errtestbytes, 4779 NTestBytes ) ); 4780 TestR ( "stringin", fnvNull, 4781 FNV32stringin ( (FNV32context *)0, errteststring ) ); 4782 TestR ( "stringin", fnvNull, 4783 FNV32stringin ( &eContext, (char *)0 ) ); 4784 TestR ( "stringin", fnvStateError, 4785 FNV32stringin ( &eContext, errteststring ) ); 4786 TestR ( "result", fnvNull, 4787 FNV32result ( (FNV32context *)0, &eUint32 ) ); 4788 TestR ( "result", fnvNull, 4789 FNV32result ( &eContext, (uint32_t *)0 ) ); 4790 TestR ( "result", fnvStateError, 4791 FNV32result ( &eContext, &eUint32 ) ); 4792 if ( Terr ) 4793 printf ( "%s test of error checks failed %i times.0, 4794 funcName, Terr ); 4795 else 4796 printf ( "%s test of error checks passed0, funcName ); 4798 /* test actual results */ 4799 Terr = 0; 4800 for ( i = 0; i < NTstrings; ++i ) 4801 { 4802 err = TestR ( "string", fnvSuccess, 4803 FNV32string ( teststring[i], &eUint32 ) ); 4804 if ( err == fnvSuccess ) 4805 Test32Value ( "string", teststring[i], eUint32, 4806 FNV32svalues[i] ); 4807 err = TestR ( "block", fnvSuccess, 4808 FNV32block ( (uint8_t *)teststring[i], 4809 (unsigned long)(strlen(teststring[i])+1), 4810 &eUint32 ) ); 4811 if ( err == fnvSuccess ) 4812 Test32Value ( "block", teststring[i], eUint32, 4813 FNV32bvalues[i] ); 4814 /* now try testing the incremental stuff */ 4815 err = TestR ( "init", fnvSuccess, FNV32init ( &eContext ) ); 4816 if ( err ) break; 4817 iLen = strlen ( teststring[i] ); 4818 err = TestR ( "blockin", fnvSuccess, 4819 FNV32blockin ( &eContext, 4820 (uint8_t *)teststring[i], 4821 iLen/2 ) ); 4822 if ( err ) break; 4823 err = TestR ( "stringin", fnvSuccess, 4824 FNV32stringin ( &eContext, 4825 teststring[i] + iLen/2 ) ); 4826 err = TestR ( "result", fnvSuccess, 4827 FNV32result ( &eContext, &eUint32 ) ); 4828 if ( err ) break; 4829 Test32Value ( " incremental", teststring[i], eUint32, 4830 FNV32svalues[i] ); 4831 } 4832 if ( Terr ) 4833 printf ( "%s test of return values failed %i times.0, 4834 funcName, Terr ); 4835 else 4836 printf ( "%s test of return values passed.0, funcName ); 4837 } /* end Test32 */ 4839 /* start Test32Value 4840 *****************************************************************/ 4841 void Test32Value ( char *subfunc, 4842 char *string, 4843 uint32_t was, 4844 uint32_t should ) 4845 { 4846 TestNValue(subfunc, string, sizeof(uint32_t), (uint8_t*)&was, 4847 (uint8_t*)&should); 4848 } /* end Test32Value */ 4850 #ifdef FNV_64bitIntegers 4851 /***************************************************************** 4852 * Code for FNV64 using 64-bit integers 4853 *****************************************************************/ 4855 void Test64 () 4856 { 4857 int i, err; 4858 uint64_t eUint64 = 42; 4859 FNV64context eContext; 4860 uint64_t FNV64svalues[NTstrings] = { 4861 0xcbf29ce484222325, 0xaf63dc4c8601ec8c, 0x85944171f73967e8 }; 4862 uint64_t FNV64bvalues[NTstrings] = { 4863 0xaf63bd4c8601b7df, 0x089be207b544f1e4, 0x34531ca7168b8f38 }; 4865 funcName = "FNV64"; 4867 /* test error checks */ 4868 Terr = 0; 4869 TestR ( "init", fnvSuccess, FNV64init (&eContext) ); 4870 TestR ( "string", fnvNull, 4871 FNV64string ( (char *)0, &eUint64 ) ); 4872 TestR ( "string", fnvNull, 4873 FNV64string ( errteststring, (uint64_t *)0 ) ); 4874 TestR ( "block", fnvNull, 4875 FNV64block ( (uint8_t *)0, 1, &eUint64 ) ); 4876 TestR ( "block", fnvBadParam, 4877 FNV64block ( errtestbytes, -1, &eUint64 ) ); 4878 TestR ( "block", fnvNull, 4879 FNV64block ( errtestbytes, 1, (uint64_t *)0 ) ); 4880 TestR ( "init", fnvNull, 4881 FNV64init ( (FNV64context *)0 ) ); 4882 TestR ( "initBasis", fnvNull, 4883 FNV64initBasis ( (FNV64context *)0, 42 ) ); 4884 TestR ( "blockin", fnvNull, 4885 FNV64blockin ( (FNV64context *)0, 4886 errtestbytes, NTestBytes ) ); 4887 TestR ( "blockin", fnvNull, 4888 FNV64blockin ( &eContext, (uint8_t *)0, 4889 NTestBytes ) ); 4890 TestR ( "blockin", fnvBadParam, 4891 FNV64blockin ( &eContext, errtestbytes, -1 ) ); 4892 eContext.Computed = FNVclobber+FNV64state; 4893 TestR ( "blockin", fnvStateError, 4894 FNV64blockin ( &eContext, errtestbytes, 4895 NTestBytes ) ); 4896 TestR ( "stringin", fnvNull, 4897 FNV64stringin ( (FNV64context *)0, errteststring ) ); 4898 TestR ( "stringin", fnvNull, 4899 FNV64stringin ( &eContext, (char *)0 ) ); 4900 TestR ( "stringin", fnvStateError, 4901 FNV64stringin ( &eContext, errteststring ) ); 4902 TestR ( "result", fnvNull, 4903 FNV64result ( (FNV64context *)0, &eUint64 ) ); 4904 TestR ( "result", fnvNull, 4905 FNV64result ( &eContext, (uint64_t *)0 ) ); 4906 TestR ( "result", fnvStateError, 4907 FNV64result ( &eContext, &eUint64 ) ); 4908 if ( Terr ) 4909 printf ( "%s test of error checks failed %i times.0, 4910 funcName, Terr ); 4911 else 4912 printf ( "%s test of error checks passed0, funcName ); 4914 /* test actual results */ 4915 Terr = 0; 4916 for ( i = 0; i < NTstrings; ++i ) 4917 { 4918 err = TestR ( "string", fnvSuccess, 4919 FNV64string ( teststring[i], &eUint64 ) ); 4920 if ( err == fnvSuccess ) 4921 Test64Value ( "string", teststring[i], eUint64, 4922 FNV64svalues[i] ); 4924 err = TestR ( "block", fnvSuccess, 4925 FNV64block ( (uint8_t *)teststring[i], 4926 (unsigned long)(strlen(teststring[i])+1), 4927 &eUint64 ) ); 4928 if ( err == fnvSuccess ) 4929 Test64Value ( "block", teststring[i], eUint64, 4930 FNV64bvalues[i] ); 4931 /* now try testing the incremental stuff */ 4932 err = TestR ( "init", fnvSuccess, FNV64init ( &eContext ) ); 4934 } 4935 if ( Terr ) 4936 printf ( "%s test of return values failed %i times.0, 4937 funcName, Terr ); 4938 else 4939 printf ( "%s test of return values passed.0, funcName ); 4940 } /* end Test64 */ 4942 /* start Test64Value 4943 *****************************************************************/ 4944 void Test64Value ( char *subfunc, 4945 char *string, 4946 uint64_t should, 4947 uint64_t was ) 4948 { 4949 TestNValue(subfunc, string, sizeof(uint64_t), (uint8_t*)&was, 4950 . (uint8_t*)&should); 4951 } /* end Test64Value */ 4952 #else 4953 void Test64 () 4954 { 4955 /* TBD */ 4956 } 4957 #endif /* FNV_64bitIntegers */ 4959 /***************************************************************** 4960 * Code for FNV128 using 64-bit integers 4961 *****************************************************************/ 4963 void Test128 () 4964 { 4965 //int i, err; 4966 uint8_t eUint128[FNV128size]; 4967 FNV128context eContext; 4969 funcName = "FNV128"; 4971 /* test error checks */ 4972 Terr = 0; 4973 TestR ( "init", fnvSuccess, FNV128init (&eContext) ); 4974 TestR ( "string", fnvNull, 4975 FNV128string ( (char *)0, eUint128 ) ); 4976 TestR ( "string", fnvNull, 4977 FNV128string ( errteststring, (uint8_t *)0 ) ); 4978 TestR ( "block", fnvNull, 4979 FNV128block ( (uint8_t *)0, 1, eUint128 ) ); 4980 TestR ( "block", fnvBadParam, 4981 FNV128block ( errtestbytes, -1, eUint128 ) ); 4982 TestR ( "block", fnvNull, 4983 FNV128block ( errtestbytes, 1, (uint8_t *)0 ) ); 4984 TestR ( "init", fnvNull, 4985 FNV128init ( (FNV128context *)0 ) ); 4986 TestR ( "initBasis", fnvNull, 4987 FNV128initBasis ( (FNV128context *)0, eUint128 ) ); 4988 TestR ( "blockin", fnvNull, 4989 FNV128blockin ( (FNV128context *)0, 4990 errtestbytes, NTestBytes ) ); 4991 TestR ( "blockin", fnvNull, 4992 FNV128blockin ( &eContext, (uint8_t *)0, 4993 NTestBytes ) ); 4994 TestR ( "blockin", fnvBadParam, 4995 FNV128blockin ( &eContext, errtestbytes, -1 ) ); 4996 eContext.Computed = FNVclobber+FNV128state; 4997 TestR ( "blockin", fnvStateError, 4998 FNV128blockin ( &eContext, errtestbytes, 4999 NTestBytes ) ); 5000 TestR ( "stringin", fnvNull, 5001 FNV128stringin ( (FNV128context *)0, errteststring ) ); 5002 TestR ( "stringin", fnvNull, 5003 FNV128stringin ( &eContext, (char *)0 ) ); 5004 TestR ( "stringin", fnvStateError, 5005 FNV128stringin ( &eContext, errteststring ) ); 5006 TestR ( "result", fnvNull, 5007 FNV128result ( (FNV128context *)0, eUint128 ) ); 5008 TestR ( "result", fnvNull, 5009 FNV128result ( &eContext, (uint8_t *)0 ) ); 5010 TestR ( "result", fnvStateError, 5011 FNV128result ( &eContext, eUint128 ) ); 5012 if ( Terr ) 5013 printf ( "%s test of error checks failed %i times.0, 5014 funcName, Terr ); 5015 else 5016 printf ( "%s test of error checks passed0, funcName ); 5018 /* test actual results */ 5019 Terr = 0; 5020 /* tbd */ 5021 } /* end Test128 */ 5022 /***************************************************************** 5023 * Code for FNV256 using 64-bit integers 5024 *****************************************************************/ 5026 void Test256 () 5027 { 5028 //int i, err; 5029 uint8_t eUint256[FNV256size]; 5030 FNV256context eContext; 5032 funcName = "FNV256"; 5034 /* test error checks */ 5035 Terr = 0; 5036 TestR ( "init", fnvSuccess, FNV256init (&eContext) ); 5037 TestR ( "string", fnvNull, 5038 FNV256string ( (char *)0, eUint256 ) ); 5039 TestR ( "string", fnvNull, 5040 FNV256string ( errteststring, (uint8_t *)0 ) ); 5041 TestR ( "block", fnvNull, 5042 FNV256block ( (uint8_t *)0, 1, eUint256 ) ); 5043 TestR ( "block", fnvBadParam, 5044 FNV256block ( errtestbytes, -1, eUint256 ) ); 5045 TestR ( "block", fnvNull, 5046 FNV256block ( errtestbytes, 1, (uint8_t *)0 ) ); 5047 TestR ( "init", fnvNull, 5048 FNV256init ( (FNV256context *)0 ) ); 5049 TestR ( "initBasis", fnvNull, 5050 FNV256initBasis ( (FNV256context *)0, eUint256 ) ); 5051 TestR ( "blockin", fnvNull, 5052 FNV256blockin ( (FNV256context *)0, 5053 errtestbytes, NTestBytes ) ); 5054 TestR ( "blockin", fnvNull, 5055 FNV256blockin ( &eContext, (uint8_t *)0, 5056 NTestBytes ) ); 5057 TestR ( "blockin", fnvBadParam, 5058 FNV256blockin ( &eContext, errtestbytes, -1 ) ); 5059 eContext.Computed = FNVclobber+FNV256state; 5060 TestR ( "blockin", fnvStateError, 5061 FNV256blockin ( &eContext, errtestbytes, 5062 NTestBytes ) ); 5063 TestR ( "stringin", fnvNull, 5064 FNV256stringin ( (FNV256context *)0, errteststring ) ); 5065 TestR ( "stringin", fnvNull, 5066 FNV256stringin ( &eContext, (char *)0 ) ); 5067 TestR ( "stringin", fnvStateError, 5068 FNV256stringin ( &eContext, errteststring ) ); 5069 TestR ( "result", fnvNull, 5070 FNV256result ( (FNV256context *)0, eUint256 ) ); 5071 TestR ( "result", fnvNull, 5072 FNV256result ( &eContext, (uint8_t *)0 ) ); 5073 TestR ( "result", fnvStateError, 5074 FNV256result ( &eContext, eUint256 ) ); 5075 if ( Terr ) 5076 printf ( "%s test of error checks failed %i times.0, 5077 funcName, Terr ); 5078 else 5079 printf ( "%s test of error checks passed0, funcName ); 5081 /* test actual results */ 5082 Terr = 0; 5083 /* tbd */ 5084 } /* end Test256 */ 5086 /***************************************************************** 5087 * Code for FNV512 using 64-bit integers 5088 *****************************************************************/ 5090 void Test512 () 5091 { 5092 //int i, err; 5093 uint8_t eUint512[FNV512size]; 5094 FNV512context eContext; 5096 funcName = "FNV512"; 5098 /* test error checks */ 5099 Terr = 0; 5100 TestR ( "init", fnvSuccess, FNV512init (&eContext) ); 5101 TestR ( "string", fnvNull, 5102 FNV512string ( (char *)0, eUint512 ) ); 5103 TestR ( "string", fnvNull, 5104 FNV512string ( errteststring, (uint8_t *)0 ) ); 5105 TestR ( "block", fnvNull, 5106 FNV512block ( (uint8_t *)0, 1, eUint512 ) ); 5107 TestR ( "block", fnvBadParam, 5108 FNV512block ( errtestbytes, -1, eUint512 ) ); 5109 TestR ( "block", fnvNull, 5110 FNV512block ( errtestbytes, 1, (uint8_t *)0 ) ); 5111 TestR ( "init", fnvNull, 5112 FNV512init ( (FNV512context *)0 ) ); 5113 TestR ( "initBasis", fnvNull, 5114 FNV512initBasis ( (FNV512context *)0, eUint512 ) ); 5115 TestR ( "blockin", fnvNull, 5116 FNV512blockin ( (FNV512context *)0, 5117 errtestbytes, NTestBytes ) ); 5118 TestR ( "blockin", fnvNull, 5119 FNV512blockin ( &eContext, (uint8_t *)0, 5120 NTestBytes ) ); 5122 TestR ( "blockin", fnvBadParam, 5123 FNV512blockin ( &eContext, errtestbytes, -1 ) ); 5124 eContext.Computed = FNVclobber+FNV512state; 5125 TestR ( "blockin", fnvStateError, 5126 FNV512blockin ( &eContext, errtestbytes, 5127 NTestBytes ) ); 5128 TestR ( "stringin", fnvNull, 5129 FNV512stringin ( (FNV512context *)0, errteststring ) ); 5130 TestR ( "stringin", fnvNull, 5131 FNV512stringin ( &eContext, (char *)0 ) ); 5132 TestR ( "stringin", fnvStateError, 5133 FNV512stringin ( &eContext, errteststring ) ); 5134 TestR ( "result", fnvNull, 5135 FNV512result ( (FNV512context *)0, eUint512 ) ); 5136 TestR ( "result", fnvNull, 5137 FNV512result ( &eContext, (uint8_t *)0 ) ); 5138 TestR ( "result", fnvStateError, 5139 FNV512result ( &eContext, eUint512 ) ); 5140 if ( Terr ) 5141 printf ( "%s test of error checks failed %i times.0, 5142 funcName, Terr ); 5143 else 5144 printf ( "%s test of error checks passed0, funcName ); 5146 /* test actual results */ 5147 Terr = 0; 5148 /* tbd */ 5149 } /* end Test512 */ 5151 /***************************************************************** 5152 * Code for FNV1024 using 64-bit integers 5153 *****************************************************************/ 5155 void Test1024 () 5156 { 5157 //int i, err; 5158 uint8_t eUint1024[FNV1024size]; 5159 FNV1024context eContext; 5161 funcName = "FNV1024"; 5163 /* test error checks */ 5164 Terr = 0; 5165 TestR ( "init", fnvSuccess, FNV1024init (&eContext) ); 5166 TestR ( "string", fnvNull, 5167 FNV1024string ( (char *)0, eUint1024 ) ); 5168 TestR ( "string", fnvNull, 5169 FNV1024string ( errteststring, (uint8_t *)0 ) ); 5170 TestR ( "block", fnvNull, 5171 FNV1024block ( (uint8_t *)0, 1, eUint1024 ) ); 5172 TestR ( "block", fnvBadParam, 5173 FNV1024block ( errtestbytes, -1, eUint1024 ) ); 5174 TestR ( "block", fnvNull, 5175 FNV1024block ( errtestbytes, 1, (uint8_t *)0 ) ); 5176 TestR ( "init", fnvNull, 5177 FNV1024init ( (FNV1024context *)0 ) ); 5178 TestR ( "initBasis", fnvNull, 5179 FNV1024initBasis ( (FNV1024context *)0, eUint1024 ) ); 5180 TestR ( "blockin", fnvNull, 5181 FNV1024blockin ( (FNV1024context *)0, 5182 errtestbytes, NTestBytes ) ); 5183 TestR ( "blockin", fnvNull, 5184 FNV1024blockin ( &eContext, (uint8_t *)0, 5185 NTestBytes ) ); 5186 TestR ( "blockin", fnvBadParam, 5187 FNV1024blockin ( &eContext, errtestbytes, -1 ) ); 5188 eContext.Computed = FNVclobber+FNV1024state; 5189 TestR ( "blockin", fnvStateError, 5190 FNV1024blockin ( &eContext, errtestbytes, 5191 NTestBytes ) ); 5192 TestR ( "stringin", fnvNull, 5193 FNV1024stringin ( (FNV1024context *)0, errteststring ) ); 5194 TestR ( "stringin", fnvNull, 5195 FNV1024stringin ( &eContext, (char *)0 ) ); 5196 TestR ( "stringin", fnvStateError, 5197 FNV1024stringin ( &eContext, errteststring ) ); 5198 TestR ( "result", fnvNull, 5199 FNV1024result ( (FNV1024context *)0, eUint1024 ) ); 5200 TestR ( "result", fnvNull, 5201 FNV1024result ( &eContext, (uint8_t *)0 ) ); 5202 TestR ( "result", fnvStateError, 5203 FNV1024result ( &eContext, eUint1024 ) ); 5204 if ( Terr ) 5205 printf ( "%s test of error checks failed %i times.0, 5206 funcName, Terr ); 5207 else 5208 printf ( "%s test of error checks passed0, funcName ); 5210 /* test actual results */ 5211 Terr = 0; 5212 /* tbd */ 5213 } /* end Test1024 */ 5214 5216 7. Security Considerations 5218 This document is intended to provide convenient open source access by 5219 the Internet community to the FNV non-cryptographic hash. No 5220 assertion of suitability for cryptographic applications is made for 5221 the FNV hash algorithms. 5223 7.1 Why is FNV Non-Cryptographic? 5225 A full discussion of cryptographic hash requirements and strength is 5226 beyond the scope of this document. However, here are three 5227 characteristics of FNV that would generally be considered to make it 5228 non-cryptographic: 5230 1. Sticky State - A cryptographic hash should not have a state in 5231 which it can stick for a plausible input pattern. But, in the very 5232 unlikely event that the FNV hash variable becomes zero and the 5233 input is a sequence of zeros, the hash variable will remain at 5234 zero until there is a non-zero input byte and the final hash value 5235 will be unaffected by the length of that sequence of zero input 5236 bytes. Of course, for the common case of fixed length input, this 5237 would usually not be significant because the number of non-zero 5238 bytes would vary inversely with the number of zero bytes and for 5239 some types of input, runs of zeros do not occur. Furthermore, the 5240 inclusion of even a little unpredictable input may be sufficient 5241 to stop an adversary from inducing a zero hash variable. 5243 2. Diffusion - Every output bit of a cryptographic hash should be an 5244 equally complex function of every input bit. But it is easy to see 5245 that the least significant bit of a direct FNV hash is the XOR of 5246 the least significant bits of every input byte and does not depend 5247 on any other input bit. While more complex, the second through 5248 seventh least significant bits of an FNV hash have a similar 5249 weakness; only the top bit of the bottom byte of output, and 5250 higher order bits, depend on all input bits. If these properties 5251 are considered a problem, they can be easily fixed by XOR folding 5252 (see Section 3). 5254 3. Work Factor - Depending on intended use, it is frequently 5255 desirable that a hash function should be computationally expensive 5256 for general purpose and graphics processors since these may be 5257 profusely available through elastic cloud services or botnets. 5258 This is to slow down testing of possible inputs if the output is 5259 known. But FNV is designed to be very inexpensive on a general- 5260 purpose processor. (See Appendix A.) 5262 Nevertheless, none of the above have proven to be a problem in actual 5263 practice for the many applications of FNV. 5265 7.2 Inducing Collisions 5267 While use of a cryptographic hash should be considered when active 5268 adversaries are a factor, the following attack can be made much more 5269 difficult with very minor changes in the use of FNV. 5271 If FNV is being used in a known way for hash tables in a network 5272 server or the like, for example some part of a web server, an 5273 adversary could send requests calculated to cause hash table 5274 collisions and induce substantial processing delays. As mentioned in 5275 Section 2.2, use of an offset_basis not knownable by the adversary 5276 will substantially eliminate this problem. 5278 8. IANA Considerations 5280 This document requires no IANA Actions. RFC Ediotor: Please delete 5281 this section before publication. 5283 Normative References 5285 [RFC20] - Cerf, V., "ASCII format for network interchange", STD 80, 5286 RFC 20, October 1969, . 5288 Informative References 5290 [FNV] - FNV web site: 5291 http://www.isthe.com/chongo/tech/comp/fnv/index.html 5293 [IEEE] - http://www.ieee.org 5295 [IPv6flow] - https://researchspace.auckland.ac.nz/bitstream/handle/ 5296 2292/13240/flowhashRep.pdf 5298 [RFC2460] - Deering, S. and R. Hinden, "Internet Protocol, Version 6 5299 (IPv6) Specification", RFC 2460, December 1998, 5300 . 5302 [RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm 5303 1 (SHA1)", RFC 3174, September 2001. 5305 [RFC6194] - Polk, T., Chen, L., Turner, S., and P. Hoffman, "Security 5306 Considerations for the SHA-0 and SHA-1 Message-Digest 5307 Algorithms", RFC 6194, March 2011. 5309 [RFC6234] - Eastlake 3rd, D. and T. Hansen, "US Secure Hash 5310 Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 5311 2011. 5313 [RFC6437] - Amante, S., Carpenter, B., Jiang, S., and J. Rajahalme, 5314 "IPv6 Flow Label Specification", RFC 6437, November 2011, 5315 . 5317 Acknowledgements 5319 The contributions of the following are gratefully acknowledged: 5321 Roman Donchenko, Frank Ellermann, Tony Finch, Bob Moskowitz, 5322 Gayle Noble, Stefan Santesson, and Mukund Sivaraman. 5324 Appendix A: Work Comparison with SHA-1 5326 This section provides a simplistic rough comparison of the level of 5327 effort required per input byte to compute FNV-1a and SHA-1 [RFC3174]. 5329 Ignoring transfer of control and conditional tests and equating all 5330 logical and arithmetic operations, FNV requires 2 operations per 5331 byte, an XOR and a multiply. 5333 SHA-1 is a relatively weak cryptographic hash producing a 160-bit 5334 hash. It has been partially broken [RFC6194]. It is actually designed 5335 to accept a bit vector input although almost all computer uses apply 5336 it to an integer number of bytes. It processes blocks of 512 bits (64 5337 bytes) and we estimate the effort involved in SHA-1 processing a full 5338 block. Ignoring SHA-1 initial set up, transfer of control, and 5339 conditional tests, but counting all logical and arithmetic 5340 operations, including counting indexing as an addition, SHA-1 5341 requires 1,744 operations per 64 bytes block or 27.25 operations per 5342 byte. So by this rough measure, it is a little over 13 times the 5343 effort of FNV for large amounts of data. However, FNV is commonly 5344 used for small inputs. Using the above method, for inputs of N bytes, 5345 where N is <= 55 so SHA-1 will take one block (SHA-1 includes padding 5346 and an 8-byte length at the end of the data in the last block), the 5347 ratio of the effort for SHA-1 to the effort for FNV will be 872/N. 5348 For example, with an 8 byte input, SHA-1 will take 109 times as much 5349 effort as FNV. 5351 Stronger cryptographic functions than SHA-1 generally have an even 5352 higher work factor. 5354 Appendix B: Previous IETF Reference to FNV 5356 FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has 5357 since expired. It was later decided that it would be better to use a 5358 cryptographic hash for that application. 5360 Below is the Java code for FNV64 from that TLS draft included by the 5361 kind permission of the author: 5363 5364 /** 5365 * Java code sample, implementing 64 bit FNV-1a 5366 * By Stefan Santesson 5367 */ 5369 import java.math.BigInteger; 5371 public class FNV { 5373 static public BigInteger getFNV1aToByte(byte[] inp) { 5375 BigInteger m = new BigInteger("2").pow(64); 5376 BigInteger fnvPrime = new BigInteger("1099511628211"); 5377 BigInteger fnvOffsetBasis = 5378 new BigInteger("14695981039346656037"); 5380 BigInteger digest = fnvOffsetBasis; 5382 for (byte b : inp) { 5383 digest = digest.xor(BigInteger.valueOf((int) b & 255)); 5384 digest = digest.multiply(fnvPrime).mod(m); 5385 } 5386 return digest; 5388 } 5389 } 5390 5392 Appendix C: A Few Test Vectors 5394 Below are a few test vectors in the form of ASCII strings and their 5395 FNV32 and FNV64 hashes using the FNV-1a algorithm. 5397 Strings without null (zero byte) termination: 5399 String FNV32 FNV64 5400 "" 0x811c9dc5 0xcbf29ce484222325 5401 "a" 0xe40c292c 0xaf63dc4c8601ec8c 5402 "foobar" 0xbf9cf968 0x85944171f73967e8 5404 Strings including null (zero byte) termination: 5406 String FNV32 FNV64 5407 "" 0x050c5d1f 0xaf63bd4c8601b7df 5408 "a" 0x2b24d044 0x089be207b544f1e4 5409 "foobar" 0x0c1c9eb8 0x34531ca7168b8f38 5411 Appendix Z: Change Summary 5413 RFC Editor Note: Please delete this appendix on publication. 5415 From -00 to -01 5417 1. Add Security Considerations section on why FNV is non- 5418 cryptographic. 5420 2. Add Appendix A on a work factor comparison with SHA-1. 5422 3. Add Appendix B concerning previous IETF draft referenced to FNV. 5424 4. Minor editorial changes. 5426 From -01 to -02 5428 1. Correct FNV_Prime determination criteria and add note as to why s 5429 < 5 and s > 10 are not considered. 5431 2. Add acknowledgements list. 5433 3. Add a couple of references. 5435 4. Minor editorial changes. 5437 From -02 to -03 5439 1. Replace direct reference to US-ASCII standard with reference to 5440 RFC 20. 5442 2. Update dates and version number. 5444 3. Minor editing changes. 5446 From -03 to -04 5448 1. Change reference to RFC 20 back to a reference to the ANSI 1968 5449 ASCII standard. 5451 2. Minor addition to Section 6, point 3. 5453 3. Update dates and version number. 5455 4. Minor editing changes. 5457 From -04 to -05 5459 1. Add Twitter as a use example and IPv6 flow hash study reference. 5461 2. Update dates and version number. 5463 From -05 to -06 5465 1. Add code subsections. 5467 2. Update dates and version number. 5469 From -06 to -07 to -08 5471 1. Update Author info. 5473 2. Minor edits. 5475 From -08 to -09 5477 1. Change reference for ASCII to [RFC20]. 5479 2. Add more details on history of the string used to compute 5480 offset_basis. 5482 3. Re-write "Work Factor" part of Section 6 to be more precise. 5484 4. Minor editorial changes. 5486 From -09 to -10 5488 1. Inclusion of initial partial version of code and some 5489 documentation about the code, Section 6. 5491 2. Insertion of new Section 4 on hashing values. 5493 From -10 to -11 5495 Changes based on code improvements primarily from Tony Hansen who has 5496 been added as an author. Changes based on comments from Mukund 5497 Sivaraman and Roman Donchenko. 5499 From -11 to -12 5501 Keep alive update. 5503 From -12 to -13 5505 Fixed bug in pseudocode in Section 2.3. 5507 Change code to eliminate the BigEndian flag and so there are separate 5508 byte vector output routines for FNV32 and FNV64, equivalent to the 5509 other routines, and integer output routines for cases where 5510 Endianness consistency is not required. 5512 Author's Address 5514 Glenn Fowler 5515 Google 5517 Email: glenn.s.fowler@gmail.com 5519 Landon Curt Noll 5520 Cisco Systems 5521 170 West Tasman Drive 5522 San Jose, CA 95134 USA 5524 Telephone: +1-408-424-1102 5525 Email: fnv-ietf3-mail@asthe.com 5526 URL: http://www.isthe.com/chongo/index.html 5528 Kiem-Phong Vo 5529 Google 5531 Email: phongvo@gmail.com 5533 Donald Eastlake 5534 Huawei Technologies 5535 155 Beaver Street 5536 Milford, MA 01757 USA 5538 Telephone: +1-508-333-2270 5539 EMail: d3e3e3@gmail.com 5541 Tony Hansen 5542 AT&T Laboratories 5543 200 Laurel Ave. South 5544 Middletown, NJ 07748 5545 USA 5547 Email: tony@att.com 5549 Copyright, Disclaimer, and Additional IPR Provisions 5551 Copyright (c) 2017 IETF Trust and the persons identified as the 5552 document authors. All rights reserved. 5554 This document is subject to BCP 78 and the IETF Trust's Legal 5555 Provisions Relating to IETF Documents 5556 (http://trustee.ietf.org/license-info) in effect on the date of 5557 publication of this document. Please review these documents 5558 carefully, as they describe your rights and restrictions with respect 5559 to this document. Code Components extracted from this document must 5560 include Simplified BSD License text as described in Section 4.e of 5561 the Trust Legal Provisions and are provided without warranty as 5562 described in the Simplified BSD License. This Internet-Draft is 5563 submitted to IETF in full conformance with the provisions of BCP 78 5564 and BCP 79.