idnits 2.17.1 draft-eastlake-fnv-16.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 237 has weird spacing: '...ed char hash...' == Line 1680 has weird spacing: '...int i;...' == Line 2220 has weird spacing: '...int i;...' == Line 2391 has weird spacing: '...context ctx...' == Line 2406 has weird spacing: '...context ctx...' == (18 more instances...) -- The document date (December 7, 2018) is 1966 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 237, but not defined == Missing Reference: 'FNV128size' is mentioned on line 4967, but not defined == Missing Reference: 'FNV256size' is mentioned on line 5030, but not defined == Missing Reference: 'FNV512size' is mentioned on line 5094, but not defined == Missing Reference: 'FNV1024size' is mentioned on line 5159, 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: June 6, 2019 December 7, 2018 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 76 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 95 From -13 to -14 to -15 to -16............................117 97 1. Introduction 99 The FNV hash algorithm is based on an idea sent as reviewer comments 100 to the [IEEE] POSIX P1003.2 committee by Glenn Fowler and Phong Vo in 101 1991. In a subsequent ballot round Landon Curt Noll suggested an 102 improvement on their algorithm. Some people tried this hash and found 103 that it worked rather well. In an EMail message to Landon, they named 104 it the "Fowler/Noll/Vo" or FNV hash. [FNV] 106 FNV hashes are designed to be fast while maintaining a low collision 107 rate. The high dispersion of the FNV hashes makes them well suited 108 for hashing nearly identical strings such as URLs, hostnames, 109 filenames, text, IP addresses, etc. Their speed allows one to quickly 110 hash lots of data while maintaining a reasonably low collision rate. 111 However, they are generally not suitable for cryptographic use. (See 112 Section 7.1.) 114 The FNV hash is widely used, for example in DNS servers, the Twitter 115 service, database indexing hashes, major web search / indexing 116 engines, netnews history file Message-ID lookup functions, anti-spam 117 filters, a spellchecker programmed in Ada 95, flatassembler's open 118 source x86 assembler - user-defined symbol hashtree, non- 119 cryptographic file fingerprints, computing Unique IDs in DASM (DTN 120 (Delay Tolerant Networking) Applications for Symbian Mobile-phones), 121 Microsoft's hash_map implementation for VC++ 2005, the realpath cache 122 in PHP 5.x (php-5.2.3/TSRM/tsrm_virtual_cwd.c), and many other uses. 124 A study has recommended FNV in connection with the IPv6 Flow Label 125 field [IPv6flow]. 127 FNV hash algorithms and source code have been released into the 128 public domain. The authors of the FNV algorithm took deliberate steps 129 to disclose the algorithm in a public forum soon after it was 130 invented. More than a year passed after this public disclosure and 131 the authors deliberately took no steps to patent the FNV algorithm. 132 Therefore, it is safe to say that the FNV authors have no patent 133 claims on the FNV algorithm as published. 135 If you use an FNV function in an application, you are kindly 136 requested to send an EMail about it to: fnv-mail@asthe.com 138 2. FNV Basics 140 This document focuses on the FNV-1a function whose pseudo-code is as 141 follows: 143 hash = offset_basis 144 for each octet_of_data to be hashed 145 hash = hash xor octet_of_data 146 hash = hash * FNV_Prime 147 return hash 149 In the pseudo-code above, hash is a power-of-two number of bits (32, 150 64, ... 1024) and offset_basis and FNV_Prime depend on the size of 151 hash. 153 The FNV-1 algorithm is the same, including the values of offset_basis 154 and FNV_Prime, except that the order of the two lines with the "xor" 155 and multiply operations are reversed. Operational experience 156 indicates better hash dispersion for small amounts of data with 157 FNV-1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero. 158 FNV-1a is suggested for general use. 160 2.1 FNV Primes 162 The theory behind FNV_Prime's is beyond the scope of this document 163 but the basic property to look for is how an FNV_Prime would impact 164 dispersion. Now, consider any n-bit FNV hash where n is >= 32 and 165 also a power of 2, in particular n = 2**s. For each such n-bit FNV 166 hash, an FNV_Prime p is defined as: 168 When s is an integer and 4 < s < 11, then FNV_Prime is the 169 smallest prime p of the form: 171 256**int((5 + 2**s)/12) + 2**8 + b 173 where b is an integer such that: 175 0 < b < 2**8 176 The number of one-bits in b is 4 or 5 178 and where ( p mod (2**40 - 2**24 - 1) ) > (2**24 + 2**8 + 2**7). 180 Experimentally, FNV_Primes matching the above constraints tend to 181 have better dispersion properties. They improve the polynomial 182 feedback characteristic when an FNV_Prime multiplies an intermediate 183 hash value. As such, the hash values produced are more scattered 184 throughout the n-bit hash space. 186 The case where s < 5 is not considered because the resulting hash 187 quality is too low. Such small hashes can, if desired, be derived 188 from a 32 bit FNV hash by XOR folding (see Section 3). The case where 189 s > 10 is not considered because of the doubtful utility of such 190 large FNV hashes and because the criteria for such large FNV_Primes 191 is more complex, due to the sparsity of such large primes, and would 192 needlessly clutter the criteria given above. 194 Per the above constraints, an FNV_Prime should have only 6 or 7 one- 195 bits in it. Therefore, some compilers may seek to improve the 196 performance of a multiplication with an FNV_Prime by replacing the 197 multiplication with shifts and adds. However, note that the 198 performance of this substitution is highly hardware-dependent and 199 should be done with care. FNV_Primes were selected primarily for the 200 quality of resulting hash function, not for compiler optimization. 202 2.2 FNV offset_basis 204 The offset_basis values for the n-bit FNV-1a algorithms are computed 205 by applying the n-bit FNV-0 algorithm to the 32 octets representing 206 the following character string in [RFC20]: 208 chongo /\../\ 210 The \'s in the above string are not C-style escape characters. In C- 211 string notation, these 32 octets are: 213 "chongo /\\../\\" 215 That string was used because the person testing FNV with non-zero 216 offset_basis values was looking at an email message from Landon and 217 was copying his standard email signature line; however, they couldn't 218 see very well and copied it incorrectly. In fact, he uses 220 chongo (Landon Curt Noll) /\oo/\ 222 but, since it doesn't matter, no effort has been made to correct 223 this. 225 In the general case, almost any offset_basis will serve so long as it 226 is non-zero. The choice of a non-standard offset_basis may be 227 beneficial in defending against some attacks that try to induce hash 228 collisions. 230 2.3 FNV Endianism 232 For persistent storage or interoperability between different hardware 233 platforms, an FNV hash shall be represented in the little endian 234 format. That is, the FNV hash will be stored in an array hash[N] with 235 N bytes such that its integer value can be retrieved as follows: 237 unsigned char hash[N]; 238 for ( i = N-1, value = 0; i >= 0; --i ) 239 value = ( value << 8 ) + hash[i]; 241 Of course, when FNV hashes are used in a single process or a group of 242 processes sharing memory on processors with compatible endian-ness, 243 the natural endian-ness of those processors can be used regardless of 244 its type, little, big, or some other exotic form. 246 The code provided in Section 6 has FNV hash functions that return a 247 little endian byte vector. Because they are slightly more efficient, 248 code returning FNV hashes of 32-bit or 64-bit size as integers, on 249 computers supporting integers of those sides, are also provided. Such 250 integers are compatible with the same size byte vectors on little 251 endian computers but use of the functions returning integers on big 252 endian or other non-little-endian machines will be byte-reversed or 253 otherwise incompatible with the byte vectors. 255 3. Other Hash Sizes and XOR Folding 257 Many hash uses require a hash that is not one of the FNV sizes for 258 which constants are provided in Section 5. If a larger hash size is 259 needed, please contact the authors of this document. 261 Most hash applications make use of a hash that is a fixed size binary 262 field. Assume that k bits of hash are desired and k is less than 1024 263 but not one of the sizes for which constants are provided in Section 264 5. The recommended technique is to take the smallest FNV hash of size 265 S, where S is larger than k, and calculate the desired k-bit-hash 266 using xor folding as shown below. The final bit masking operation is 267 logically unnecessary if the size of the variable k-bit-hash is 268 exactly k bits. 270 temp = FNV_S ( data-to-be-hashed ) 271 k-bit-hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 ) 273 Hash functions are a trade-off between speed and strength. For 274 example, a somewhat stronger hash may be obtained for exact FNV sizes 275 by calculating an FNV twice as long as the desired output ( S = 2*k ) 276 and performing such data folding using a k equal to the size of the 277 desired output. However, if a much stronger hash, for example one 278 suitable for cryptographic applications, is wanted, algorithms 279 designed for that purpose, such as those in [RFC6234], should be 280 used. 282 If it is desired to obtain a hash result that is a value between 0 283 and max, where max+1 is a not a power of two, simply choose an FNV 284 hash size S such that 2**S > max. Then calculate the following: 286 FNV_S mod ( max+1 ) 288 The resulting remainder will be in the range desired but will suffer 289 from a bias against large values with the bias being larger if 2**S 290 is only a little bigger than max. If this bias is acceptable, no 291 further processing is needed. If this bias is unacceptable, it can be 292 avoided by retrying for certain high values of hash, as follows, 293 before applying the mod operation above: 295 X = ( int( ( 2**S - 1 ) / ( max+1 ) ) ) * ( max+1 ) 296 while ( hash >= X ) 297 hash = ( hash * FNV_Prime ) + offset_basis 299 4. Hashing Multiple Values Together 301 It is common for there to be a few different component values, say 302 three strings X, Y, and Z, where a hash over all of them is desired. 303 The simplest thing to do is to concatenate them and compute the hash 304 of that concatenation, as in 306 hash ( X | Y | Z ) 308 where the vertical bar character ("|") represents string 309 concatenation. Note that, for FNV, the same hash results if X, Y, 310 and Z are actually concatenated and the FNV hash applied to the 311 resulting string or if FNV is calculated on an initial substring and 312 the result used as the offset_basis when calculating the FNV hash of 313 the remainder of the string. This can be done several times. 314 Assuming FNVoffset_basis ( v, w ) is FNV of w using v as the 315 offset_basis, then in the example above, fnvx = FNV ( X ) could be 316 calculated and then fnvxy = FNVoffset_basis ( fnvx, Y ), and finally 317 fnvxyz = FNVoffset_basis ( fnvxy, Z). The resulting fnvxyz would be 318 the same as FNV ( X | Y | Z ); 320 Cases are also common where such a hash needs to be repeatedly 321 calculated where the component values vary but some vary more 322 frequently than others. For example, assume some sort of computer 323 network traffic flow ID, such as the IPv6 flow ID [RFC6437], is to be 324 calculated for network packets based on the source and destination 325 IPv6 address and the Traffic Class [RFC2460]. If the Flow ID is 326 calculated in the originating host, the source IPv6 address would 327 likely always be the same or perhaps assume one of a very small 328 number of values. By placing this quasi-constant IPv6 source address 329 first in the string being FNV hashed, FNV ( IPv6source ) could be 330 calculated and used as the offset_basis for calculating FNV of the 331 IPv6 destination address and Traffic Class for each packet. As a 332 result, the per packet hash would be over 17 bytes rather than over 333 33 bytes saving computational resources. The code in this document 334 includes functions facilitating the use of a non-standard 335 offset_basis. 337 5. FNV Constants 339 The FNV Primes are as follows: 341 32 bit FNV_Prime = 2**24 + 2**8 + 0x93 = 16,777,619 342 = 0x01000193 344 64 bit FNV_Prime = 2**40 + 2**8 + 0xB3 = 1,099,511,628,211 345 = 0x00000100 000001B3 347 128 bit FNV_Prime = 2**88 + 2**8 + 0x3B = 348 309,485,009,821,345,068,724,781,371 349 = 0x00000000 01000000 00000000 0000013B 351 256 bit FNV_Prime = 2**168 + 2**8 + 0x63 = 352 374,144,419,156,711,147,060,143,317,175,368,453,031,918,731,002,211 = 353 0x0000000000000000 0000010000000000 0000000000000000 0000000000000163 355 512 bit FNV_Prime = 2**344 + 2**8 + 0x57 = 35, 356 835,915,874,844,867,368,919,076,489,095,108,449,946,327,955,754,392, 357 558,399,825,615,420,669,938,882,575,126,094,039,892,345,713,852,759 = 358 0x0000000000000000 0000000000000000 0000000001000000 0000000000000000 359 0000000000000000 0000000000000000 0000000000000000 0000000000000157 361 1024 bit FNV_Prime = 2**680 + 2**8 + 0x8D = 5, 362 016,456,510,113,118,655,434,598,811,035,278,955,030,765,345,404,790, 363 744,303,017,523,831,112,055,108,147,451,509,157,692,220,295,382,716, 364 162,651,878,526,895,249,385,292,291,816,524,375,083,746,691,371,804, 365 094,271,873,160,484,737,966,720,260,389,217,684,476,157,468,082,573 = 366 0x0000000000000000 0000000000000000 0000000000000000 0000000000000000 367 0000000000000000 0000010000000000 0000000000000000 0000000000000000 368 0000000000000000 0000000000000000 0000000000000000 0000000000000000 369 0000000000000000 0000000000000000 0000000000000000 000000000000018D 371 The FNV offset_basis values are as follows: 373 32 bit offset_basis = 2,166,136,261 = 0x811C9DC5 375 64 bit offset_basis = 14695981039346656037 = 0xCBF29CE4 84222325 377 128 bit offset_basis = 144066263297769815596495629667062367629 = 378 0x6C62272E 07BB0142 62B82175 6295C58D 380 256 bit offset_basis = 100,029,257,958,052,580,907,070,968, 381 620,625,704,837,092,796,014,241,193,945,225,284,501,741,471,925,557 = 382 0xDD268DBCAAC55036 2D98C384C4E576CC C8B1536847B6BBB3 1023B4C8CAEE0535 383 512 bit offset_basis = 9, 384 659,303,129,496,669,498,009,435,400,716,310,466,090,418,745,672,637, 385 896,108,374,329,434,462,657,994,582,932,197,716,438,449,813,051,892, 386 206,539,805,784,495,328,239,340,083,876,191,928,701,583,869,517,785 = 387 0xB86DB0B1171F4416 DCA1E50F309990AC AC87D059C9000000 0000000000000D21 388 E948F68A34C192F6 2EA79BC942DBE7CE 182036415F56E34B AC982AAC4AFE9FD9 390 1024 bit offset_basis = 14,197,795,064,947,621,068,722,070,641,403, 391 218,320,880,622,795,441,933,960,878,474,914,617,582,723,252,296,732, 392 303,717,722,150,864,096,521,202,355,549,365,628,174,669,108,571,814, 393 760,471,015,076,148,029,755,969,804,077,320,157,692,458,563,003,215, 394 304,957,150,157,403,644,460,363,550,505,412,711,285,966,361,610,267, 395 868,082,893,823,963,790,439,336,411,086,884,584,107,735,010,676,915 = 396 0x0000000000000000 005F7A76758ECC4D 32E56D5A591028B7 4B29FC4223FDADA1 397 6C3BF34EDA3674DA 9A21D90000000000 0000000000000000 0000000000000000 398 0000000000000000 0000000000000000 0000000000000000 000000000004C6D7 399 EB6E73802734510A 555F256CC005AE55 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 401 6. The Source Code 403 [THIS CODE IS BEING WORKING AND IS INCONSISTENT AS BELOW.] 405 The following sub-sections provide reference C source code and a test 406 driver for FNV-1a. 408 Alternative source code, including 32 and 64 bit FNV-1 and FNV-1a in 409 x86 assembler, is currently available at [FNV]. 411 Section 6.2 provides a test driver. 413 6.1 FNV-1a C Code 415 This section provides the direct FNV-1a function for each of the 416 lengths for which it is specified in this document. The functions 417 provided are listed below. Those whose name is of the form FNVxxxB* 418 output a byte vector that will be compatible between systems of 419 different endian-ness, where xxx is "32", "64", "128", "256", "512", 420 or "1024". Those whose name is of the form FNVxxx* (with no "B" after 421 the xxx) return an integer and are NOT compatible between systems of 422 different endian-ness. These integer based functions exist only for 423 xxx of "32" and, on systems supporting 64-bit integers, "64". 425 FNVxxxstring, FNVxxxblock: 426 FNVxxxBstring, FNVxxxBblock: These are simple functions for directly 427 returning the FNV hash of a zero terminated byte string not 428 including the zero and the FNV hash of a counted block of 429 bytes. Note that for applications of FNV-32 where 32-bit 430 integers are supported and FNV-64 where 64-bit integers are 431 supported and an integer data type output is acceptable, the 432 code is sufficiently simple that, to maximize performance, use 433 of open coding or macros may be more appropriate than calling a 434 subroutine. 436 FNVxxxinit, FNVxxxinitBasis: 437 FNVxxxBinit, FNVxxxBinitBasis: These functions and the next two sets 438 of functions below provide facilities for incrementally 439 calculating FNV hashes. They all assume a data structure of 440 type FNVxxx(B)context that holds the current state of the hash. 441 FNVxxx(B)init initializes that context to the standard 442 offset_basis. FNVxxx(B)initBasis takes an offset_basis value as 443 a parameter and may be useful for hashing concatenations, as 444 described in Section 4, as well as for simply using a non- 445 standard offset_basis. 447 FNVxxxblockin, FNVxxxstringin: 448 FNVxxxBblockin, FNVxxxBstringin: These functions hash a sequence of 449 bytes into an FNVxxx(B)context that was originally initialized 450 by FNVxxx(B)init or FNVxxx(B)initBasis. FNVxxx(B)blockin hashes 451 in a counted block of bytes. FNVxxx(B)stringin hashes in a zero 452 terminated byte string not incuding the final zero. 454 FNVxxxresult: 455 FNVxxxBresult: This function extracts the final FNV hash result from 456 an FNVxxx(B)context. 458 The following code is a private header file used by all the FNV 459 functions further below and which states the terms for use and 460 redistribution of all of this code. 462 463 /************************ fnv-private.h ************************/ 464 /****************** See RFC NNNN for details *******************/ 465 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 466 * authors of the code. All rights reserved. 467 * 468 * Redistribution and use in source and binary forms, with or without 469 * modification, are permitted provided that the following conditions 470 * are met: 471 * 472 * * Redistributions of source code must retain the above copyright 473 * notice, this list of conditions and the following disclaimer. 474 * 475 * * Redistributions in binary form must reproduce the above copyright 476 * notice, this list of conditions and the following disclaimer in 477 * the documentation and/or other materials provided with the 478 * distribution. 479 * 480 * * Neither the name of Internet Society, IETF or IETF Trust, nor the 481 * names of specific contributors, may be used to endorse or promote 482 * products derived from this software without specific prior 483 * written permission. 484 * 485 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 486 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 487 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 488 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 489 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 490 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 491 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 492 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 493 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 494 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 495 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 496 * POSSIBILITY OF SUCH DAMAGE. 498 */ 500 #ifndef _FNV_PRIVATE_H_ 501 #define _FNV_PRIVATE_H_ 503 /* 504 * Six FNV-1a hashes are defined with these sizes: 505 * FNV32 32 bits, 4 bytes 506 * FNV64 64 bits, 8 bytes 507 * FNV128 128 bits, 16 bytes 508 * FNV256 256 bits, 32 bytes 509 * FNV512 512 bits, 64 bytes 510 * FNV1024 1024 bits, 128 bytes 511 */ 513 /* Private stuff used by this implementation of the FNV 514 * (Fowler, Noll, Vo) non-cryptographic hash function FNV-1a. 515 * External callers don't need to know any of this. */ 517 enum { /* State value bases for context->Computed */ 518 FNVinited = 22, 519 FNVcomputed = 76, 520 FNVemptied = 220, 521 FNVclobber = 122 /* known bad value for testing */ 522 }; 524 /* Deltas to assure distinct state values for different lengths */ 525 enum { 526 FNV32state = 1, 527 FNV32Bstate = 17, 528 FNV64state = 3, 529 FNV64Bstate = 19, 530 FNV128state = 5, 531 FNV256state = 7, 532 FNV512state = 11, 533 FNV1024state = 13 534 }; 536 #endif 537 539 The following code is a simple header file to include all the 540 specific length FNV header files. 542 543 /****************************** FNV.h *******************************/ 544 /******************* See RFC NNNN for details. **********************/ 545 /* 546 * Copyright (c) 2016, 2017 IETF Trust and the persons identified as 547 * authors of the code. All rights reserved. 549 * See fnv-private.h for terms of use and redistribution. 550 */ 552 #ifndef _FNV_H_ 553 #define _FNV_H_ 555 #include "FNV32.h" 556 #include "FNV32B.h" 557 #ifdef FNV_64bitIntegers 558 # include "FNV64.h" 559 #endif /* FNV_64bitIntegers */ 560 #include "FNV64B.h" 561 #include "FNV128.h" 562 #include "FNV256.h" 563 #include "FNV512.h" 564 #include "FNV1024.h" 566 #endif /* _FNV_H_ */ 567 569 The following code is a simple header file to control configuration 570 related to big integer and big endian support. 572 573 /*************************** FNVconfig.h ****************************/ 574 /******************* See RFC NNNN for details. **********************/ 575 /* 576 * Copyright (c) 2016, 2017 IETF Trust and the persons identified as 577 * authors of the code. All rights reserved. 578 * See fnv-private.h for terms of use and redistribution. 579 */ 581 #ifndef _FNVconfig_H_ 582 #define _FNVconfig_H_ 584 /* 585 * Description: 586 * This file provides configuration ifdefs for the 587 * FNV-1a non-cryptographic hash algorithms. 588 * 589 * >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */ 591 /* FNV_64bitIntegers - Define this if your system supports 64-bit 592 * arithmetic including 32-bit x 32-bit multiplication 593 * producing a 64-bit product. If undefined, it will be 594 * assumed that 32-bit arithmetic is supported including 595 * 16-bit x 16-bit multiplication producing a 32-bit result. 596 */ 597 // #define FNV_64bitIntegers 598 /* 599 * The following allow the FNV test program to override the 600 * above configuration settings. 601 */ 603 #ifdef FNV_TEST_PROGRAM 604 # ifdef TEST_FNV_64bitIntegers 605 # ifndef FNV_64bitIntegers 606 # define FNV_64bitIntegers 607 # endif 608 # else 609 # undef FNV_64bitIntegers 610 # endif 611 # ifndef FNV_64bitIntegers /* causes an error if uint64_t is used */ 612 # define uint64_t foobar /* RFC 3092 */ 613 # endif 614 #endif 616 #endif /* _FNVconfig_H_ */ 617 619 6.1.1 FNV32 Code 621 The header and C source for 32-bit FNV-1a returning a 32-bit integer. 623 624 /***************************** FNV32.h ******************************/ 625 /******************** See RFC NNNN for details **********************/ 626 /* 627 * Copyright (c) 2016 IETF Trust and the persons identified as 628 * authors of the code. All rights reserved. 629 * See fnv-private.h for terms of use and redistribution. 630 */ 632 #ifndef _FNV32_H_ 633 #define _FNV32_H_ 635 #include "FNVconfig.h" 637 #include 638 /* #define FNV32size (32/8) not used */ 640 /* If you do not have the ISO standard stdint.h header file, then you 641 * must typedef the following types: 642 * 643 * type meaning 644 * uint32_t unsigned 32 bit integer 645 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 646 */ 648 #ifndef _FNV_ErrCodes_ 649 #define _FNV_ErrCodes_ 650 /******************************************************************** 651 * All FNV functions provided return as integer as follows: 652 * 0 -> success 653 * >0 -> error as listed below 654 */ 655 enum { /* success and errors */ 656 fnvSuccess = 0, 657 fnvNull, /* Null pointer parameter */ 658 fnvStateError, /* called Input after Result, etc. */ 659 fnvBadParam /* passed a bad parameter */ 660 }; 661 #endif /* _FNV_ErrCodes_ */ 663 /* 664 * This structure holds context information for an FNV32 hash 665 */ 666 typedef struct FNV32context_s { 667 int Computed; /* state */ 668 uint32_t Hash; 669 } FNV32context; 671 /* 672 * Function Prototypes 673 * FNV32string: hash a zero terminated string not including 674 * the terminating zero 675 * FNV32block: hash a specified length byte vector 676 * FNV32init: initializes an FNV32 context 677 * FNV32initBasis: initializes an FNV32 context with a 678 * provided basis 679 * FNV32blockin: hash in a specified length byte vector 680 * FNV32stringin: hash in a zero terminated string not 681 * including the zero 682 * FNV32result: returns the hash value 683 * 684 * Hash is returned as a 32-bit integer 685 */ 687 #ifdef __cplusplus 688 extern "C" { 689 #endif 691 /* FNV32 */ 692 extern int FNV32string ( const char *in, 693 uint32_t * const out ); 694 extern int FNV32block ( const void *in, 695 long int inlength, 696 uint32_t * const out ); 697 extern int FNV32init ( FNV32context * const ); 698 extern int FNV32initBasis ( FNV32context * const, 699 uint32_t basis ); 700 extern int FNV32blockin ( FNV32context * const, 701 const void *in, 702 long int inlength ); 703 extern int FNV32stringin ( FNV32context * const, 704 const char *in ); 705 extern int FNV32result ( FNV32context * const, 706 uint32_t * const out ); 708 #ifdef __cplusplus 709 } 710 #endif 712 #endif /* _FNV32_H_ */ 713 715 716 /**************************** FNV32.c ****************************/ 717 /****************** See RFC NNNN for details. ********************/ 718 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified 719 * as authors of the code. All rights reserved. 720 * See fnv-private.h for terms of use and redistribution. 721 */ 723 /* This code implements the FNV (Fowler, Noll, Vo) non-cryptographic 724 * hash function FNV-1a for 32-bit hashes returning a 32-bit 725 * integer. 726 */ 728 #ifndef _FNV32_C_ 729 #define _FNV32_C_ 731 #include "fnv-private.h" 732 #include "FNV32.h" 734 /* 32 bit FNV_prime = 2^24 + 2^8 + 0x93 */ 735 #define FNV32prime 0x01000193 736 #define FNV32basis 0x811C9DC5 738 /* FNV32 hash a zero terminated string not including the zero 739 *********************************************************************/ 740 int FNV32string ( const char *in, uint32_t * const out ) 741 { 742 uint32_t temp; 743 uint8_t ch; 745 if ( in && out ) 746 { 747 temp = FNV32basis; 748 while ( (ch = *in++) ) 749 temp = FNV32prime * ( temp ^ ch ); 750 *out = temp; 751 return fnvSuccess; 752 } 753 return fnvNull; /* Null input pointer */ 754 } /* end FNV32string */ 756 /* FNV32 hash a counted block 757 ***************************************************************/ 758 int FNV32block ( const void *vin, 759 long int length, 760 uint32_t * const out ) 761 { 762 const uint8_t *in = (const uint8_t*)vin; 763 uint32_t temp; 765 if ( in && out ) 766 { 767 if ( length < 0 ) 768 return fnvBadParam; 769 for ( temp = FNV32basis; length > 0; length-- ) 770 temp = FNV32prime * ( temp ^ *in++ ); 771 *out = temp; 772 return fnvSuccess; 773 } 774 return fnvNull; /* Null input pointer */ 775 } /* end FNV32block */ 777 /*************************************************************** 778 * Set of init, input, and output functions below * 779 * to incrementally compute FNV32 * 780 ***************************************************************/ 782 /* initialize context 783 ***************************************************************/ 784 int FNV32init ( FNV32context * const ctx ) 785 { 786 return FNV32initBasis ( ctx, FNV32basis ); 787 } /* end FNV32init */ 789 /* initialize context with a provided basis 790 ***************************************************************/ 791 int FNV32initBasis ( FNV32context * const ctx, uint32_t basis ) 792 { 793 if ( ctx ) 794 { 795 ctx->Hash = basis; 796 ctx->Computed = FNVinited+FNV32state; 797 return fnvSuccess; 798 } 799 return fnvNull; 800 } /* end FNV32initBasis */ 802 /* hash in a counted block 803 ***************************************************************/ 804 int FNV32blockin ( FNV32context * const ctx, 805 const void *vin, 806 long int length ) 807 { 808 const uint8_t *in = (const uint8_t*)vin; 809 uint32_t temp; 811 if ( ctx && in ) 812 { 813 if ( length < 0 ) 814 return fnvBadParam; 815 switch ( ctx->Computed ) 816 { 817 case FNVinited+FNV32state: 818 ctx->Computed = FNVcomputed+FNV32state; 819 case FNVcomputed+FNV32state: 820 break; 821 default: 822 return fnvStateError; 823 } 824 for ( temp = ctx->Hash; length > 0; length-- ) 825 temp = FNV32prime * ( temp ^ *in++ ); 826 ctx->Hash = temp; 827 return fnvSuccess; 828 } 829 return fnvNull; 830 } /* end FNV32blockin */ 832 /* hash in a zero terminated string not including the zero 833 ***************************************************************/ 834 int FNV32stringin ( FNV32context * const ctx, 835 const char *in ) 836 { 837 uint32_t temp; 838 uint8_t ch; 840 if ( ctx && in ) 841 { 842 switch ( ctx->Computed ) 843 { 844 case FNVinited+FNV32state: 846 ctx->Computed = FNVcomputed+FNV32state; 847 case FNVcomputed+FNV32state: 848 break; 849 default: 850 return fnvStateError; 851 } 852 temp = ctx->Hash; 853 while ( (ch = (uint8_t)*in++) ) 854 temp = FNV32prime * ( temp ^ ch ); 855 ctx->Hash = temp; 856 return fnvSuccess; 857 } 858 return fnvNull; 859 } /* end FNV32stringin */ 861 /* return hash 862 ***************************************************************/ 863 int FNV32result ( FNV32context * const ctx, 864 uint32_t * const out ) 865 { 866 if ( ctx && out ) 867 { 868 if ( ctx->Computed != FNVcomputed+FNV32state ) 869 return fnvStateError; 870 ctx->Computed = FNVemptied+FNV32state; 871 *out = ctx->Hash; 872 ctx->Hash = 0; 873 return fnvSuccess; 874 } 875 return fnvNull; 876 } /* end FNV32result */ 878 #endif /* _FNV32_C_ */ 879 881 The header and C source for 32-bit FNV-1a returning a byte vector. 883 884 /***************************** FNV32B.h *****************************/ 885 /******************** See RFC NNNN for details **********************/ 886 /* 887 * Copyright (c) 2016, 2017 IETF Trust and the persons identified as 888 * authors of the code. All rights reserved. 889 * See fnv-private.h for terms of use and redistribution. 890 */ 892 #ifndef _FNV32_H_ 893 #define _FNV32_H_ 895 #include "FNVconfig.h" 896 #include 897 #define FNV32size (32/8) 899 /* If you do not have the ISO standard stdint.h header file, then you 900 * must typedef the following types: 901 * 902 * type meaning 903 * uint32_t unsigned 32 bit integer 904 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 905 */ 907 #ifndef _FNV_ErrCodes_ 908 #define _FNV_ErrCodes_ 909 /******************************************************************** 910 * All FNV functions provided return as integer as follows: 911 * 0 -> success 912 * >0 -> error as listed below 913 */ 914 enum { /* success and errors */ 915 fnvSuccess = 0, 916 fnvNull, /* Null pointer parameter */ 917 fnvStateError, /* called Input after Result, etc. */ 918 fnvBadParam /* passed a bad parameter */ 919 }; 920 #endif /* _FNV_ErrCodes_ */ 922 /* 923 * This structure holds context information for an FNV32 hash 924 */ 925 typedef struct FNV32Bcontext_s { 926 int Computed; /* state */ 927 uint32_t Hash; 928 } FNV32Bcontext; 930 /* 931 * Function Prototypes 932 * FNV32Bstring: hash a zero terminated string not including 933 * the terminating zero 934 * FNV32Bblock: hash a specified length byte vector 935 * FNV32Binit: initializes an FNV32 context 936 * FNV32BinitBasis: initializes an FNV32 context with a 937 * provided basis 938 * FNV32Bblockin: hash in a specified length byte vector 939 * FNV32Bstringin: hash in a zero terminated string not 940 * including the zero 941 * FNV32Bresult: returns the hash value 942 * 943 * Hash is returned as a 32-bit integer 944 */ 946 #ifdef __cplusplus 947 extern "C" { 948 #endif 950 /* FNV32 */ 951 extern int FNV32Bstring ( const char *in, 952 uint8_t * const out[FNV32size] ); 953 extern int FNV32Bblock ( const void *in, 954 long int inlength, 955 uint8_t * const out[FNV32size] ); 956 extern int FNV32Binit ( FNV32Bcontext * const ); 957 extern int FNV32BinitBasis ( FNV32Bcontext * const, 958 uint32_t basis ); 959 extern int FNV32Bblockin ( FNV32Bcontext * const, 960 const void *in, 961 long int inlength ); 962 extern int FNV32Bstringin ( FNV32Bcontext * const, 963 const char *in ); 964 extern int FNV32Bresult ( FNV32Bcontext * const, 965 int8_t * const out[FNV32size] ); 967 #ifdef __cplusplus 968 } 969 #endif 971 #endif /* _FNV32_H_ */ 972 974 975 /**************************** FNV32B.c ***************************/ 976 /****************** See RFC NNNN for details. ********************/ 977 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 978 * authors of the code. All rights reserved. 979 * See fnv-private.h for terms of use and redistribution. 980 */ 982 /* This code implements the FNV (Fowler, Noll, Vo) non-cryptographic 983 * hash function FNV-1a for 32-bit hashes returning a byte vector. 984 */ 986 #ifndef _FNV32_C_ 987 #define _FNV32_C_ 989 #include "fnv-private.h" 990 #include "FNV32B.h" 992 /* 32 bit FNV_prime = 2^24 + 2^8 + 0x93 */ 993 #define FNV32prime 0x01000193 994 #define FNV32basis 0x811C9DC5 995 /* FNV32 hash a zero terminated string not including the zero 996 *******************************************************************/ 997 int FNV32Bstring ( const char *in, uint8_t * const out[FNV32size] ) 998 { 999 uint32_t temp; 1000 uint8_t ch; 1002 if ( in && out ) 1003 { 1004 temp = FNV32basis; 1005 while ( (ch = *in++) ) 1006 temp = FNV32prime * ( temp ^ ch ); 1007 *out[0] = temp & 0xFF; 1008 temp =>> 8; 1009 *out[1] = temp & 0xFF; 1010 temp =>> 8; 1011 *out[2] = temp & 0xFF; 1012 temp =>> 8; 1013 *out[3] = temp & 0xFF; 1014 return fnvSuccess; 1015 } 1016 return fnvNull; /* Null input pointer */ 1017 } /* end FNV32Bstring */ 1019 /* FNV32 hash a counted block 1020 ***************************************************************/ 1021 int FNV32Bblock ( const void *vin, 1022 long int length, 1023 uint8_t * const out[FNV32size] ) 1024 { 1025 const uint8_t *in = (const uint8_t*)vin; 1026 uint32_t temp; 1028 if ( in && out ) 1029 { 1030 if ( length < 0 ) 1031 return fnvBadParam; 1032 for ( temp = FNV32basis; length > 0; length-- ) 1033 temp = FNV32prime * ( temp ^ *in++ ); 1034 *out[0] = temp & 0xFF; 1035 temp =>> 8; 1036 *out[1] = temp & 0xFF; 1037 temp =>> 8; 1038 *out[2] = temp & 0xFF; 1039 temp =>> 8; 1040 *out[3] = temp & 0xFF; 1041 *out = temp; 1042 return fnvSuccess; 1043 } 1044 return fnvNull; /* Null input pointer */ 1045 } /* end FNV32Bblock */ 1047 /*************************************************************** 1048 * Set of init, input, and output functions below * 1049 * to incrementally compute FNV32 * 1050 ***************************************************************/ 1052 /* initialize context 1053 ***************************************************************/ 1054 int FNV32Binit ( FNV32Bcontext * const ctx ) 1055 { 1056 return FNV32BinitBasis ( ctx, FNV32basis ); 1057 } /* end FNV32Binit */ 1059 /* initialize context with a provided basis 1060 ***************************************************************/ 1061 int FNV32BinitBasis ( FNV32Bcontext * const ctx, uint32_t basis ) 1062 { 1063 if ( ctx ) 1064 { 1065 ctx->Hash = basis; 1066 ctx->Computed = FNVinited+FNV32Bstate; 1067 return fnvSuccess; 1068 } 1069 return fnvNull; 1070 } /* end FNV32BinitBasis */ 1072 /* hash in a counted block 1073 ***************************************************************/ 1074 int FNV32Bblockin ( FNV32Bcontext * const ctx, 1075 const void *vin, 1076 long int length ) 1077 { 1078 const uint8_t *in = (const uint8_t*)vin; 1079 uint32_t temp; 1081 if ( ctx && in ) 1082 { 1083 if ( length < 0 ) 1084 return fnvBadParam; 1085 switch ( ctx->Computed ) 1086 { 1087 case FNVinited+FNV32Bstate: 1088 ctx->Computed = FNVcomputed+FNV32Bstate; 1089 case FNVcomputed+FNV32Bstate: 1090 break; 1091 default: 1092 return fnvStateError; 1093 } 1095 for ( temp = ctx->Hash; length > 0; length-- ) 1096 temp = FNV32prime * ( temp ^ *in++ ); 1097 ctx->Hash = temp; 1098 return fnvSuccess; 1099 } 1100 return fnvNull; 1101 } /* end FNV32Bblockin */ 1103 /* hash in a zero terminated string not including the zero 1104 ***************************************************************/ 1105 int FNV32Bstringin ( FNV32Bcontext * const ctx, 1106 const char *in ) 1107 { 1108 uint32_t temp; 1109 uint8_t ch; 1111 if ( ctx && in ) 1112 { 1113 switch ( ctx->Computed ) 1114 { 1115 case FNVinited+FNV32Bstate: 1116 ctx->Computed = FNVcomputed+FNV32Bstate; 1117 case FNVcomputed+FNV32Bstate: 1118 break; 1119 default: 1120 return fnvStateError; 1121 } 1122 temp = ctx->Hash; 1123 while ( (ch = (uint8_t)*in++) ) 1124 temp = FNV32prime * ( temp ^ ch ); 1125 ctx->Hash = temp; 1126 return fnvSuccess; 1127 } 1128 return fnvNull; 1129 } /* end FNV32Bstringin */ 1131 /* return hash 1132 ***************************************************************/ 1133 int FNV32Bresult ( FNV32Bcontext * const ctx, 1134 uint8_t * const out[FNV32size] ) 1135 { 1136 if ( ctx && out ) 1137 { 1138 if ( ctx->Computed != FNVcomputed+FNV32Bstate ) 1139 return fnvStateError; 1140 ctx->Computed = FNVemptied+FNV32Bstate; 1141 *out[0] = ctx->Hash & 0xFF; 1142 ctx->Hash =>> 8; 1143 *out[1] = ctx->Hash & 0xFF; 1144 ctx->Hash =>> 8; 1145 *out[2] = ctx->Hash & 0xFF; 1146 ctx->Hash =>> 8; 1147 *out[3] = ctx->Hash & 0xFF; 1148 ctx->Hash = 0; 1149 return fnvSuccess; 1150 } 1151 return fnvNull; 1152 } /* end FNV32Bresult */ 1154 #endif /* _FNV32_C_ */ 1155 1157 6.1.2 FNV64 C Code 1159 The header and C source for 64-bit FNV-1a returning a 64-bit integer. 1161 1162 /***************************** FNV64.h ******************************/ 1163 /******************* See RFC NNNN for details. **********************/ 1164 /* 1165 * Copyright (c) 2016 IETF Trust and the persons identified as 1166 * authors of the code. All rights reserved. 1167 * See fnv-private.h for terms of use and redistribution. 1168 */ 1170 #ifndef _FNV64_H_ 1171 #define _FNV64_H_ 1173 /* 1174 * Description: 1175 * This file provides headers for the 64-bit version of the FNV-1a 1176 * non-cryptographic hash algorithm. 1177 */ 1179 #include "FNVconfig.h" 1181 #include 1182 #define FNV64size (64/8) 1184 /* If you do not have the ISO standard stdint.h header file, then you 1185 * must typedef the following types: 1186 * 1187 * type meaning 1188 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 1189 * uint32_t unsigned 32 bit integer 1190 * uint16_t unsigned 16 bit integer 1191 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 1192 */ 1194 #ifndef _FNV_ErrCodes_ 1195 #define _FNV_ErrCodes_ 1196 /********************************************************************* 1197 * All FNV functions provided return as integer as follows: 1198 * 0 -> success 1199 * >0 -> error as listed below 1200 */ 1201 enum { /* success and errors */ 1202 fnvSuccess = 0, 1203 fnvNull, /* Null pointer parameter */ 1204 fnvStateError, /* called Input after Result, etc. */ 1205 fnvBadParam /* passed a bad parameter */ 1206 }; 1207 #endif /* _FNV_ErrCodes_ */ 1209 /* 1210 * This structure holds context information for an FNV64 hash 1211 */ 1212 #ifdef FNV_64bitIntegers 1213 /* version if 64 bit integers supported */ 1215 typedef struct FNV64context_s { 1216 int Computed; /* state */ 1217 uint64_t Hash; 1218 } FNV64context; 1220 #else 1221 /* version if 64 bit integers NOT supported */ 1223 typedef struct FNV64context_s { 1224 int Computed; /* state */ 1225 uint16_t Hash[FNV64size/2]; 1226 } FNV64context; 1228 #endif /* FNV_64bitIntegers */ 1230 /* 1231 * Function Prototypes 1232 * FNV64string: hash a zero terminated string not including 1233 * the terminating zero 1234 * FNV64block: FNV64 hash a specified length byte vector 1235 * FNV64init: initializes an FNV64 context 1236 * FNV64initBasis: initializes an FNV64 context with a 1237 * provided basis 1238 * FNV64blockin: hash in a specified length byte vector 1239 * FNV64stringin: hash in a zero terminated string not 1240 * incluing the zero 1241 * FNV64result: returns the hash value 1242 * 1243 * Hash is returned as a 64-bit integer if supported, otherwise 1244 * as a vector of 8-bit integers 1245 */ 1247 #ifdef __cplusplus 1248 extern "C" { 1249 #endif 1251 /* FNV64 */ 1252 extern int FNV64init ( FNV64context * const ); 1253 extern int FNV64blockin ( FNV64context * const, 1254 const void * in, 1255 long int length ); 1256 extern int FNV64stringin ( FNV64context * const, 1257 const char * in ); 1259 #ifdef FNV_64bitIntegers 1260 extern int FNV64string ( const char *in, 1261 uint64_t * const out ); 1262 extern int FNV64block ( const void *in, 1263 long int length, 1264 uint64_t * const out ); 1265 extern int FNV64initBasis ( FNV64context * const, 1266 uint64_t basis ); 1267 extern int FNV64result ( FNV64context * const, 1268 uint64_t * const out ); 1269 #else 1270 extern int FNV64string ( const char *in, 1271 uint8_t out[FNV64size] ); 1272 extern int FNV64block ( const void *in, 1273 long int length, 1274 uint8_t out[FNV64size] ); 1275 extern int FNV64initBasis ( FNV64context * const, 1276 const uint8_t basis[FNV64size] ); 1277 extern int FNV64result ( FNV64context * const, 1278 uint8_t out[FNV64size] ); 1279 #endif /* FNV_64bitIntegers */ 1281 #ifdef __cplusplus 1282 } 1283 #endif 1285 #endif /* _FNV64_H_ */ 1286 1288 1289 /***************************** FNV64.c ******************************/ 1290 /******************** See RFC NNNN for details **********************/ 1291 /* Copyright (c) 2016 IETF Trust and the persons identified as 1292 * authors of the code. All rights reserved. 1293 * See fnv-private.h for terms of use and redistribution. 1295 */ 1297 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 1298 * hash function FNV-1a for 64-bit hashes. 1299 */ 1301 #ifndef _FNV64_C_ 1302 #define _FNV64_C_ 1304 #include "fnv-private.h" 1305 #include "FNV64.h" 1307 /******************************************************************** 1308 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1309 ********************************************************************/ 1310 #ifdef FNV_64bitIntegers 1312 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 1313 #define FNV64prime 0x00000100000001B3 1314 #define FNV64basis 0xCBF29CE484222325 1316 /* FNV64 hash a null terminated string (64 bit) 1317 ********************************************************************/ 1318 int FNV64string ( const char *in, uint64_t * const out ) 1319 { 1320 uint64_t temp; 1321 uint8_t ch; 1323 if ( in && out ) 1324 { 1325 temp = FNV64basis; 1326 while ( (ch = *in++) ) 1327 temp = FNV64prime * ( temp ^ ch ); 1328 #ifdef FNV_BigEndian 1329 FNV64reverse ( out, temp ); 1330 #else 1331 *out = temp; 1332 #endif 1333 return fnvSuccess; 1334 } 1335 return fnvNull; /* Null input pointer */ 1336 } /* end FNV64string */ 1338 /* FNV64 hash a counted block (64 bit) 1339 ********************************************************************/ 1340 int FNV64block ( const void *vin, 1341 long int length, 1342 uint64_t * const out ) 1343 { 1344 const uint8_t *in = (const uint8_t*)vin; 1345 uint64_t temp; 1347 if ( in && out ) 1348 { 1349 if ( length < 0 ) 1350 return fnvBadParam; 1351 for ( temp = FNV64basis; length > 0; length-- ) 1352 temp = FNV64prime * ( temp ^ *in++ ); 1353 #ifdef FNV_BigEndian 1354 FNV64reverse ( out, temp ); 1355 #else 1356 *out = temp; 1357 #endif 1358 return fnvSuccess; 1359 } 1360 return fnvNull; /* Null input pointer */ 1361 } /* end FNV64block */ 1363 #ifdef FNV_BigEndian 1365 /* Store a Big Endian result back as Little Endian 1366 ***************************************************************/ 1367 static void FNV64reverse ( uint64_t *out, uint64_t hash ) 1368 { 1369 uint64_t temp; 1370 int i; 1372 temp = hash & 0xFF; 1373 for ( i = FNV64size - 1; i > 0; i-- ) 1374 { 1375 hash >>= 8; 1376 temp = ( temp << 8 ) + ( hash & 0xFF ); 1377 } 1378 *out = temp; 1379 } /* end FNV64reverse */ 1381 #endif /* FNV_BigEndian */ 1383 /******************************************************************** 1384 * Set of init, input, and output functions below * 1385 * to incrementally compute FNV64 * 1386 ********************************************************************/ 1388 /* initialize context (64 bit) 1389 ********************************************************************/ 1390 int FNV64init ( FNV64context * const ctx ) 1391 { 1392 return FNV64initBasis ( ctx, FNV64basis ); 1393 } /* end FNV64init */ 1394 /* initialize context with a provided basis (64 bit) 1395 ********************************************************************/ 1396 int FNV64initBasis ( FNV64context * const ctx, uint64_t basis ) 1397 { 1398 if ( ctx ) 1399 { 1400 ctx->Hash = basis; 1401 ctx->Computed = FNVinited+FNV64state; 1402 return fnvSuccess; 1403 } 1404 return fnvNull; 1405 } /* end FNV64initBasis */ 1407 /* hash in a counted block (64 bit) 1408 ********************************************************************/ 1409 int FNV64blockin ( FNV64context * const ctx, 1410 const void *vin, 1411 long int length ) 1412 { 1413 const uint8_t *in = (const uint8_t*)vin; 1414 uint64_t temp; 1416 if ( ctx && in ) 1417 { 1418 if ( length < 0 ) 1419 return fnvBadParam; 1420 switch ( ctx->Computed ) 1421 { 1422 case FNVinited+FNV64state: 1423 ctx->Computed = FNVcomputed+FNV64state; 1424 case FNVcomputed+FNV64state: 1425 break; 1426 default: 1427 return fnvStateError; 1428 } 1429 for ( temp = ctx->Hash; length > 0; length-- ) 1430 temp = FNV64prime * ( temp ^ *in++ ); 1431 ctx->Hash = temp; 1432 return fnvSuccess; 1433 } 1434 return fnvNull; 1435 } /* end FNV64input */ 1437 /* hash in a zero terminated string not including the zero (64 bit) 1438 ********************************************************************/ 1439 int FNV64stringin ( FNV64context * const ctx, 1440 const char *in ) 1441 { 1442 uint64_t temp; 1443 uint8_t ch; 1444 if ( ctx && in ) 1445 { 1446 switch ( ctx->Computed ) 1447 { 1448 case FNVinited+FNV64state: 1449 ctx->Computed = FNVcomputed+FNV64state; 1450 case FNVcomputed+FNV64state: 1451 break; 1452 default: 1453 return fnvStateError; 1454 } 1455 temp = ctx->Hash; 1456 while ( (ch = *in++) ) 1457 temp = FNV64prime * ( temp ^ ch ); 1458 ctx->Hash = temp; 1459 return fnvSuccess; 1460 } 1461 return fnvNull; 1462 } /* end FNV64stringin */ 1464 /* return hash (64 bit) 1465 ********************************************************************/ 1466 int FNV64result ( FNV64context * const ctx, 1467 uint64_t * const out ) 1468 { 1469 if ( ctx && out ) 1470 { 1471 if ( ctx->Computed != FNVcomputed+FNV64state ) 1472 return fnvStateError; 1473 ctx->Computed = FNVemptied+FNV64state; 1474 #ifdef FNV_BigEndian 1475 FNV64reverse ( out, ctx->Hash ); 1476 #else 1477 *out = ctx->Hash; 1478 #endif 1479 ctx->Hash = 0; 1480 return fnvSuccess; 1481 } 1482 return fnvNull; 1483 } /* end FNV64result */ 1485 /****************************************************************** 1486 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1487 ******************************************************************/ 1488 #else /* FNV_64bitIntegers */ 1489 /****************************************************************** 1490 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1491 ******************************************************************/ 1493 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 1494 /* #define FNV64prime 0x00000100000001B3 */ 1495 #define FNV64primeX 0x01B3 1496 #define FNV64shift 8 1498 /* #define FNV64basis 0xCBF29CE484222325 */ 1499 #define FNV64basis0 0xCBF2 1500 #define FNV64basis1 0x9CE4 1501 #define FNV64basis2 0x8422 1502 #define FNV64basis3 0x2325 1504 /* FNV64 hash a null terminated string (32 bit) 1505 ********************************************************************/ 1506 int FNV64string ( const char *in, uint8_t out[FNV64size] ) 1507 { 1508 FNV64context ctx; 1509 int err; 1511 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 1512 return err; 1513 if ( ( err = FNV64stringin (&ctx, in) ) != fnvSuccess ) 1514 return err; 1515 return FNV64result (&ctx, out); 1516 } /* end FNV64string */ 1518 /* FNV64 hash a counted block (32 bit) 1519 ********************************************************************/ 1520 int FNV64block ( const void *in, 1521 long int length, 1522 uint8_t out[FNV64size] ) 1523 { 1524 FNV64context ctx; 1525 int err; 1527 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 1528 return err; 1529 if ( ( err = FNV64blockin (&ctx, in, length) ) != fnvSuccess ) 1530 return err; 1531 return FNV64result (&ctx, out); 1532 } /* end FNV64block */ 1534 /******************************************************************** 1535 * Set of init, input, and output functions below * 1536 * to incrementally compute FNV64 * 1537 ********************************************************************/ 1539 /* initialize context (32 bit) 1540 ********************************************************************/ 1541 int FNV64init ( FNV64context * const ctx ) 1542 { 1543 if ( ctx ) 1544 { 1545 ctx->Hash[0] = FNV64basis0; 1546 ctx->Hash[1] = FNV64basis1; 1547 ctx->Hash[2] = FNV64basis2; 1548 ctx->Hash[3] = FNV64basis3; 1549 ctx->Computed = FNVinited+FNV64state; 1550 return fnvSuccess; 1551 } 1552 return fnvNull; 1553 } /* end FNV64init */ 1555 /* initialize context (32 bit) 1556 ********************************************************************/ 1557 int FNV64initBasis ( FNV64context * const ctx, 1558 const uint8_t basis[FNV64size] ) 1559 { 1560 if ( ctx ) 1561 { 1562 #ifdef FNV_BigEndian 1563 ctx->Hash[0] = basis[1] + ( basis[0]<<8 ); 1564 ctx->Hash[1] = basis[3] + ( basis[2]<<8 ); 1565 ctx->Hash[2] = basis[5] + ( basis[4]<<8 ); 1566 ctx->Hash[3] = basis[7] + ( basis[6]<<8 ); 1567 #else 1568 ctx->Hash[0] = basis[0] + ( basis[1]<<8 ); 1569 ctx->Hash[1] = basis[2] + ( basis[3]<<8 ); 1570 ctx->Hash[2] = basis[4] + ( basis[5]<<8 ); 1571 ctx->Hash[3] = basis[6] + ( basis[7]<<8 ); 1572 #endif 1573 ctx->Computed = FNVinited+FNV64state; 1574 return fnvSuccess; 1575 } 1576 return fnvNull; 1577 } /* end FNV64initBasis */ 1579 /* hash in a counted block (32 bit) 1580 ********************************************************************/ 1581 int FNV64blockin ( FNV64context * const ctx, 1582 const void *vin, 1583 long int length ) 1584 { 1585 const uint8_t *in = (const uint8_t*)vin; 1586 uint32_t temp[FNV64size/2]; 1587 uint32_t temp2[2]; 1588 int i; 1590 if ( ctx && in ) 1591 { 1592 if ( length < 0 ) 1593 return fnvBadParam; 1594 switch ( ctx->Computed ) 1595 { 1596 case FNVinited+FNV64state: 1597 ctx->Computed = FNVcomputed+FNV64state; 1598 case FNVcomputed+FNV64state: 1599 break; 1600 default: 1601 return fnvStateError; 1602 } 1603 for ( i=0; iHash[i]; 1605 for ( ; length > 0; length-- ) 1606 { 1607 /* temp = FNV64prime * ( temp ^ *in++ ); */ 1608 temp2[1] = temp[3] << FNV64shift; 1609 temp2[0] = temp[2] << FNV64shift; 1610 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 1611 temp[2] *= FNV64primeX; 1612 temp[1] = temp[1] * FNV64primeX + temp2[1]; 1613 temp[0] = temp[0] * FNV64primeX + temp2[0]; 1614 temp[2] += temp[3] >> 16; 1615 temp[3] &= 0xFFFF; 1616 temp[1] += temp[2] >> 16; 1617 temp[2] &= 0xFFFF; 1618 temp[0] += temp[1] >> 16; 1619 temp[1] &= 0xFFFF; 1620 } 1621 for ( i=0; iHash[i] = temp[i]; 1623 return fnvSuccess; 1624 } 1625 return fnvNull; 1626 } /* end FNV64blockin */ 1628 /* hash in a string (32 bit) 1629 ********************************************************************/ 1630 int FNV64stringin ( FNV64context * const ctx, 1631 const char *in ) 1632 { 1633 uint32_t temp[FNV64size/2]; 1634 uint32_t temp2[2]; 1635 int i; 1636 uint8_t ch; 1638 if ( ctx && in ) 1639 { 1640 switch ( ctx->Computed ) 1641 { 1642 case FNVinited+FNV64state: 1644 ctx->Computed = FNVcomputed+FNV64state; 1645 case FNVcomputed+FNV64state: 1646 break; 1647 default: 1648 return fnvStateError; 1649 } 1650 for ( i=0; iHash[i]; 1652 while ( ( ch = (uint8_t)*in++ ) != 0) 1653 { 1654 /* temp = FNV64prime * ( temp ^ ch ); */ 1655 temp2[1] = temp[3] << FNV64shift; 1656 temp2[0] = temp[2] << FNV64shift; 1657 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 1658 temp[2] *= FNV64primeX; 1659 temp[1] = temp[1] * FNV64primeX + temp2[1]; 1660 temp[0] = temp[0] * FNV64primeX + temp2[0]; 1661 temp[2] += temp[3] >> 16; 1662 temp[3] &= 0xFFFF; 1663 temp[1] += temp[2] >> 16; 1664 temp[2] &= 0xFFFF; 1665 temp[0] += temp[1] >> 16; 1666 temp[1] &= 0xFFFF; 1667 } 1668 for ( i=0; iHash[i] = temp[i]; 1670 return fnvSuccess; 1671 } 1672 return fnvNull; 1673 } /* end FNV64stringin */ 1675 /* return hash (32 bit) 1676 ********************************************************************/ 1677 int FNV64result ( FNV64context * const ctx, 1678 uint8_t out[FNV64size] ) 1679 { 1680 int i; 1682 if ( ctx && out ) 1683 { 1684 if ( ctx->Computed != FNVcomputed+FNV64state ) 1685 return fnvStateError; 1686 for ( i=0; iHash[i]; 1690 out[6-2*i] = ctx->Hash[i] >> 8; 1691 #else 1692 out[2*i] = ctx->Hash[i]; 1693 out[2*i+1] = ctx->Hash[i] >> 8; 1695 #endif 1696 ctx -> Hash[i] = 0; 1697 } 1698 ctx->Computed = FNVemptied+FNV64state; 1699 return fnvSuccess; 1700 } 1701 return fnvNull; 1702 } /* end FNV64result */ 1704 #endif /* FNV_64bitIntegers */ 1705 /******************************************************************** 1706 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1707 ********************************************************************/ 1709 #endif /* _FNV64_C_ */ 1710 1712 The header and C source for 64-bit FNV-1a returning a byte vector. 1714 1715 /***************************** FNV64B.h *****************************/ 1716 /******************* See RFC NNNN for details. **********************/ 1717 /* 1718 * Copyright (c) 2016, 2017 IETF Trust and the persons identified as 1719 * authors of the code. All rights reserved. 1720 * See fnv-private.h for terms of use and redistribution. 1721 */ 1723 #ifndef _FNV64_H_ 1724 #define _FNV64_H_ 1726 /* 1727 * Description: 1728 * This file provides headers for the 64-bit version of the FNV-1a 1729 * non-cryptographic hash algorithm. 1730 */ 1732 #include "FNVconfig.h" 1734 #include 1735 #define FNV64size (64/8) 1737 /* If you do not have the ISO standard stdint.h header file, then you 1738 * must typedef the following types: 1739 * 1740 * type meaning 1741 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 1742 * uint32_t unsigned 32 bit integer 1743 * uint16_t unsigned 16 bit integer 1744 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 1745 */ 1747 #ifndef _FNV_ErrCodes_ 1748 #define _FNV_ErrCodes_ 1749 /********************************************************************* 1750 * All FNV functions provided return as integer as follows: 1751 * 0 -> success 1752 * >0 -> error as listed below 1753 */ 1754 enum { /* success and errors */ 1755 fnvSuccess = 0, 1756 fnvNull, /* Null pointer parameter */ 1757 fnvStateError, /* called Input after Result, etc. */ 1758 fnvBadParam /* passed a bad parameter */ 1759 }; 1760 #endif /* _FNV_ErrCodes_ */ 1762 /* 1763 * This structure holds context information for an FNV64 hash 1764 */ 1765 #ifdef FNV_64bitIntegers 1766 /* version if 64 bit integers supported */ 1768 typedef struct FNV64Bcontext_s { 1769 int Computed; /* state */ 1770 uint64_t Hash; 1771 } FNV64Bcontext; 1773 #else 1774 /* version if 64 bit integers NOT supported */ 1776 typedef struct FNV64Bcontext_s { 1777 int Computed; /* state */ 1778 uint16_t Hash[FNV64size/2]; 1779 } FNV64Bcontext; 1781 #endif /* FNV_64bitIntegers */ 1783 /* 1784 * Function Prototypes 1785 * FNV64Bstring: hash a zero terminated string not including 1786 * the terminating zero 1787 * FNV64Bblock: FNV64 hash a specified length byte vector 1788 * FNV64Binit: initializes an FNV64 context 1789 * FNV64BinitBasis: initializes an FNV64 context with a 1790 * provided basis 1791 * FNV64Bblockin: hash in a specified length byte vector 1792 * FNV64Bstringin: hash in a zero terminated string not 1793 * incluing the zero 1794 * FNV64Bresult: returns the hash value 1795 * 1796 * Hash is returned as a vector of 8-bit integers 1797 */ 1799 #ifdef __cplusplus 1800 extern "C" { 1801 #endif 1803 /* FNV64 */ 1804 extern int FNV64Bstring ( const char *in, 1805 uint8_t out[FNV64size] ); 1806 extern int FNV64Bblock ( const void *in, 1807 long int length, 1808 uint8_t out[FNV64size] ); 1809 extern int FNV64Binit ( FNV64Bcontext * const ); 1810 extern int FNV64BinitBasis ( FNV64Bcontext * const, 1811 const uint8_t basis[FNV64size] ); 1812 extern int FNV64Bblockin ( FNV64Bcontext * const, 1813 const void * in, 1814 long int length ); 1815 extern int FNV64Bstringin ( FNV64Bcontext * const, 1816 const char * in ); 1817 extern int FNV64Bresult ( FNV64Bcontext * const, 1818 uint8_t out[FNV64size] ); 1820 #ifdef __cplusplus 1821 } 1822 #endif 1824 #endif /* _FNV64_H_ */ 1825 1827 1828 /***************************** FNV64B.c *****************************/ 1829 /******************** See RFC NNNN for details **********************/ 1830 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 1831 * authors of the code. All rights reserved. 1832 * See fnv-private.h for terms of use and redistribution. 1833 */ 1835 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 1836 * hash function FNV-1a for 64-bit hashes. 1837 */ 1839 #ifndef _FNV64_C_ 1840 #define _FNV64_C_ 1842 #include "fnv-private.h" 1843 #include "FNV64.h" 1844 /******************************************************************** 1845 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1846 ********************************************************************/ 1847 #ifdef FNV_64bitIntegers 1849 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 1850 #define FNV64prime 0x00000100000001B3 1851 #define FNV64basis 0xCBF29CE484222325 1853 /* FNV64 hash a null terminated string (64 bit) 1854 ********************************************************************/ 1855 int FNV64Bstring ( const char *in, uint64_t * const out ) 1856 { 1857 uint64_t temp; 1858 uint8_t ch; 1860 if ( in && out ) 1861 { 1862 temp = FNV64basis; 1863 while ( (ch = *in++) ) 1864 temp = FNV64prime * ( temp ^ ch ); 1865 #ifdef FNV_BigEndian 1866 FNV64reverse ( out, temp ); 1867 #else 1868 *out = temp; 1869 #endif 1870 return fnvSuccess; 1871 } 1872 return fnvNull; /* Null input pointer */ 1873 } /* end FNV64string */ 1875 /* FNV64 hash a counted block (64 bit) 1876 ********************************************************************/ 1877 int FNV64Bblock ( const void *vin, 1878 long int length, 1879 uint64_t * const out ) 1880 { 1881 const uint8_t *in = (const uint8_t*)vin; 1882 uint64_t temp; 1884 if ( in && out ) 1885 { 1886 if ( length < 0 ) 1887 return fnvBadParam; 1888 for ( temp = FNV64basis; length > 0; length-- ) 1889 temp = FNV64prime * ( temp ^ *in++ ); 1890 #ifdef FNV_BigEndian 1891 FNV64reverse ( out, temp ); 1892 #else 1893 *out = temp; 1895 #endif 1896 return fnvSuccess; 1897 } 1898 return fnvNull; /* Null input pointer */ 1899 } /* end FNV64block */ 1901 #ifdef FNV_BigEndian 1903 /* Store a Big Endian result back as Little Endian 1904 ***************************************************************/ 1905 static void FNV64Breverse ( uint64_t *out, uint64_t hash ) 1906 { 1907 uint64_t temp; 1908 int i; 1910 temp = hash & 0xFF; 1911 for ( i = FNV64size - 1; i > 0; i-- ) 1912 { 1913 hash >>= 8; 1914 temp = ( temp << 8 ) + ( hash & 0xFF ); 1915 } 1916 *out = temp; 1917 } /* end FNV64reverse */ 1919 #endif /* FNV_BigEndian */ 1921 /******************************************************************** 1922 * Set of init, input, and output functions below * 1923 * to incrementally compute FNV64 * 1924 ********************************************************************/ 1926 /* initialize context (64 bit) 1927 ********************************************************************/ 1928 int FNV64Binit ( FNV64Bcontext * const ctx ) 1929 { 1930 return FNV64initBasis ( ctx, FNV64basis ); 1931 } /* end FNV64Binit */ 1933 /* initialize context with a provided basis (64 bit) 1934 ********************************************************************/ 1935 int FNV64BinitBasis ( FNV64Bcontext * const ctx, uint64_t basis ) 1936 { 1937 if ( ctx ) 1938 { 1939 ctx->Hash = basis; 1940 ctx->Computed = FNVinited+FNV64state; 1941 return fnvSuccess; 1942 } 1943 return fnvNull; 1944 } /* end FNV64BinitBasis */ 1946 /* hash in a counted block (64 bit) 1947 ********************************************************************/ 1948 int FNV64Bblockin ( FNV64Bcontext * const ctx, 1949 const void *vin, 1950 long int length ) 1951 { 1952 const uint8_t *in = (const uint8_t*)vin; 1953 uint64_t temp; 1955 if ( ctx && in ) 1956 { 1957 if ( length < 0 ) 1958 return fnvBadParam; 1959 switch ( ctx->Computed ) 1960 { 1961 case FNVinited+FNV64state: 1962 ctx->Computed = FNVcomputed+FNV64state; 1963 case FNVcomputed+FNV64state: 1964 break; 1965 default: 1966 return fnvStateError; 1967 } 1968 for ( temp = ctx->Hash; length > 0; length-- ) 1969 temp = FNV64prime * ( temp ^ *in++ ); 1970 ctx->Hash = temp; 1971 return fnvSuccess; 1972 } 1973 return fnvNull; 1974 } /* end FNV64Binput */ 1976 /* hash in a zero terminated string not including the zero (64 bit) 1977 ********************************************************************/ 1978 int FNV64Bstringin ( FNV64Bcontext * const ctx, 1979 const char *in ) 1980 { 1981 uint64_t temp; 1982 uint8_t ch; 1984 if ( ctx && in ) 1985 { 1986 switch ( ctx->Computed ) 1987 { 1988 case FNVinited+FNV64state: 1989 ctx->Computed = FNVcomputed+FNV64state; 1990 case FNVcomputed+FNV64state: 1991 break; 1992 default: 1993 return fnvStateError; 1995 } 1996 temp = ctx->Hash; 1997 while ( (ch = *in++) ) 1998 temp = FNV64prime * ( temp ^ ch ); 1999 ctx->Hash = temp; 2000 return fnvSuccess; 2001 } 2002 return fnvNull; 2003 } /* end FNV64Bstringin */ 2005 /* return hash (64 bit) 2006 ********************************************************************/ 2007 int FNV64Bresult ( FNV64Bcontext * const ctx, 2008 uint64_t * const out ) 2009 { 2010 if ( ctx && out ) 2011 { 2012 if ( ctx->Computed != FNVcomputed+FNV64state ) 2013 return fnvStateError; 2014 ctx->Computed = FNVemptied+FNV64state; 2015 #ifdef FNV_BigEndian 2016 FNV64reverse ( out, ctx->Hash ); 2017 #else 2018 *out = ctx->Hash; 2019 #endif 2020 ctx->Hash = 0; 2021 return fnvSuccess; 2022 } 2023 return fnvNull; 2024 } /* end FNV64Bresult */ 2026 /****************************************************************** 2027 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2028 ******************************************************************/ 2029 #else /* FNV_64bitIntegers */ 2030 /****************************************************************** 2031 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2032 ******************************************************************/ 2034 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 2035 /* #define FNV64prime 0x00000100000001B3 */ 2036 #define FNV64primeX 0x01B3 2037 #define FNV64shift 8 2039 /* #define FNV64basis 0xCBF29CE484222325 */ 2040 #define FNV64basis0 0xCBF2 2041 #define FNV64basis1 0x9CE4 2042 #define FNV64basis2 0x8422 2043 #define FNV64basis3 0x2325 2044 /* FNV64 hash a null terminated string (32 bit) 2045 ********************************************************************/ 2046 int FNV64Bstring ( const char *in, uint8_t out[FNV64size] ) 2047 { 2048 FNV64Bcontext ctx; 2049 int err; 2051 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 2052 return err; 2053 if ( ( err = FNV64stringin (&ctx, in) ) != fnvSuccess ) 2054 return err; 2055 return FNV64result (&ctx, out); 2056 } /* end FNV64Bstring */ 2058 /* FNV64 hash a counted block (32 bit) 2059 ********************************************************************/ 2060 int FNV64Bblock ( const void *in, 2061 long int length, 2062 uint8_t out[FNV64size] ) 2063 { 2064 FNV64Bcontext ctx; 2065 int err; 2067 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 2068 return err; 2069 if ( ( err = FNV64blockin (&ctx, in, length) ) != fnvSuccess ) 2070 return err; 2071 return FNV64result (&ctx, out); 2072 } /* end FNV64Bblock */ 2074 /******************************************************************** 2075 * Set of init, input, and output functions below * 2076 * to incrementally compute FNV64 * 2077 ********************************************************************/ 2079 /* initialize context (32 bit) 2080 ********************************************************************/ 2081 int FNV64Binit ( FNV64Bcontext * const ctx ) 2082 { 2083 if ( ctx ) 2084 { 2085 ctx->Hash[0] = FNV64basis0; 2086 ctx->Hash[1] = FNV64basis1; 2087 ctx->Hash[2] = FNV64basis2; 2088 ctx->Hash[3] = FNV64basis3; 2089 ctx->Computed = FNVinited+FNV64state; 2090 return fnvSuccess; 2091 } 2092 return fnvNull; 2093 } /* end FNV64Binit */ 2095 /* initialize context (32 bit) 2096 ********************************************************************/ 2097 int FNV64BinitBasis ( FNV64Bcontext * const ctx, 2098 const uint8_t basis[FNV64size] ) 2099 { 2100 if ( ctx ) 2101 { 2102 #ifdef FNV_BigEndian 2103 ctx->Hash[0] = basis[1] + ( basis[0]<<8 ); 2104 ctx->Hash[1] = basis[3] + ( basis[2]<<8 ); 2105 ctx->Hash[2] = basis[5] + ( basis[4]<<8 ); 2106 ctx->Hash[3] = basis[7] + ( basis[6]<<8 ); 2107 #else 2108 ctx->Hash[0] = basis[0] + ( basis[1]<<8 ); 2109 ctx->Hash[1] = basis[2] + ( basis[3]<<8 ); 2110 ctx->Hash[2] = basis[4] + ( basis[5]<<8 ); 2111 ctx->Hash[3] = basis[6] + ( basis[7]<<8 ); 2112 #endif 2113 ctx->Computed = FNVinited+FNV64state; 2114 return fnvSuccess; 2115 } 2116 return fnvNull; 2117 } /* end FNV64BinitBasis */ 2119 /* hash in a counted block (32 bit) 2120 ********************************************************************/ 2121 int FNV64Bblockin ( FNV64Bcontext * const ctx, 2122 const void *vin, 2123 long int length ) 2124 { 2125 const uint8_t *in = (const uint8_t*)vin; 2126 uint32_t temp[FNV64size/2]; 2127 uint32_t temp2[2]; 2128 int i; 2130 if ( ctx && in ) 2131 { 2132 if ( length < 0 ) 2133 return fnvBadParam; 2134 switch ( ctx->Computed ) 2135 { 2136 case FNVinited+FNV64state: 2137 ctx->Computed = FNVcomputed+FNV64state; 2138 case FNVcomputed+FNV64state: 2139 break; 2140 default: 2141 return fnvStateError; 2142 } 2144 for ( i=0; iHash[i]; 2146 for ( ; length > 0; length-- ) 2147 { 2148 /* temp = FNV64prime * ( temp ^ *in++ ); */ 2149 temp2[1] = temp[3] << FNV64shift; 2150 temp2[0] = temp[2] << FNV64shift; 2151 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 2152 temp[2] *= FNV64primeX; 2153 temp[1] = temp[1] * FNV64primeX + temp2[1]; 2154 temp[0] = temp[0] * FNV64primeX + temp2[0]; 2155 temp[2] += temp[3] >> 16; 2156 temp[3] &= 0xFFFF; 2157 temp[1] += temp[2] >> 16; 2158 temp[2] &= 0xFFFF; 2159 temp[0] += temp[1] >> 16; 2160 temp[1] &= 0xFFFF; 2161 } 2162 for ( i=0; iHash[i] = temp[i]; 2164 return fnvSuccess; 2165 } 2166 return fnvNull; 2167 } /* end FNV64Bblockin */ 2169 /* hash in a string (32 bit) 2170 ********************************************************************/ 2171 int FNV64Bstringin ( FNV64Bcontext * const ctx, 2172 const char *in ) 2173 { 2174 uint32_t temp[FNV64size/2]; 2175 uint32_t temp2[2]; 2176 int i; 2177 uint8_t ch; 2179 if ( ctx && in ) 2180 { 2181 switch ( ctx->Computed ) 2182 { 2183 case FNVinited+FNV64state: 2184 ctx->Computed = FNVcomputed+FNV64state; 2185 case FNVcomputed+FNV64state: 2186 break; 2187 default: 2188 return fnvStateError; 2189 } 2190 for ( i=0; iHash[i]; 2192 while ( ( ch = (uint8_t)*in++ ) != 0) 2193 { 2194 /* temp = FNV64prime * ( temp ^ ch ); */ 2195 temp2[1] = temp[3] << FNV64shift; 2196 temp2[0] = temp[2] << FNV64shift; 2197 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 2198 temp[2] *= FNV64primeX; 2199 temp[1] = temp[1] * FNV64primeX + temp2[1]; 2200 temp[0] = temp[0] * FNV64primeX + temp2[0]; 2201 temp[2] += temp[3] >> 16; 2202 temp[3] &= 0xFFFF; 2203 temp[1] += temp[2] >> 16; 2204 temp[2] &= 0xFFFF; 2205 temp[0] += temp[1] >> 16; 2206 temp[1] &= 0xFFFF; 2207 } 2208 for ( i=0; iHash[i] = temp[i]; 2210 return fnvSuccess; 2211 } 2212 return fnvNull; 2213 } /* end FNV64Bstringin */ 2215 /* return hash (32 bit) 2216 ********************************************************************/ 2217 int FNV64Bresult ( FNV64Bcontext * const ctx, 2218 uint8_t out[FNV64size] ) 2219 { 2220 int i; 2222 if ( ctx && out ) 2223 { 2224 if ( ctx->Computed != FNVcomputed+FNV64state ) 2225 return fnvStateError; 2226 for ( i=0; iHash[i]; 2230 out[6-2*i] = ctx->Hash[i] >> 8; 2231 #else 2232 out[2*i] = ctx->Hash[i]; 2233 out[2*i+1] = ctx->Hash[i] >> 8; 2234 #endif 2235 ctx -> Hash[i] = 0; 2236 } 2237 ctx->Computed = FNVemptied+FNV64state; 2238 return fnvSuccess; 2239 } 2240 return fnvNull; 2241 } /* end FNV64Bresult */ 2243 #endif /* FNV_64bitIntegers */ 2244 /******************************************************************** 2245 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2246 ********************************************************************/ 2248 #endif /* _FNV64_C_ */ 2249 2251 6.1.3 FNV128 C Code 2253 The header and C source for 128-bit FNV-1a returning a byte vector. 2255 2256 /**************************** FNV128.h **************************/ 2257 /***************** See RFC NNNN for details. ********************/ 2258 /* 2259 * Copyright (c) 2016 IETF Trust and the persons identified as 2260 * authors of the code. All rights reserved. 2261 * See fnv-private.h for terms of use and redistribution. 2262 */ 2264 #ifndef _FNV128_H_ 2265 #define _FNV128_H_ 2267 /* 2268 * Description: 2269 * This file provides headers for the 128-bit version of the 2270 * FNV-1a non-cryptographic hash algorithm. 2271 */ 2273 #include "FNVconfig.h" 2275 #include 2276 #define FNV128size (128/8) 2278 /* If you do not have the ISO standard stdint.h header file, then you 2279 * must typedef the following types: 2280 * 2281 * type meaning 2282 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 2283 * uint32_t unsigned 32 bit integer 2284 * uint16_t unsigned 16 bit integer 2285 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 2286 */ 2288 #ifndef _FNV_ErrCodes_ 2289 #define _FNV_ErrCodes_ 2290 /********************************************************************* 2291 * All FNV functions provided return as integer as follows: 2293 * 0 -> success 2294 * >0 -> error as listed below 2295 */ 2296 enum { /* success and errors */ 2297 fnvSuccess = 0, 2298 fnvNull, /* Null pointer parameter */ 2299 fnvStateError, /* called Input after Result or before Init */ 2300 fnvBadParam /* passed a bad parameter */ 2301 }; 2302 #endif /* _FNV_ErrCodes_ */ 2304 /* 2305 * This structure holds context information for an FNV128 hash 2306 */ 2307 #ifdef FNV_64bitIntegers 2308 /* version if 64 bit integers supported */ 2309 typedef struct FNV128context_s { 2310 int Computed; /* state */ 2311 uint32_t Hash[FNV128size/4]; 2312 } FNV128context; 2314 #else 2315 /* version if 64 bit integers NOT supported */ 2317 typedef struct FNV128context_s { 2318 int Computed; /* state */ 2319 uint16_t Hash[FNV128size/2]; 2320 } FNV128context; 2322 #endif /* FNV_64bitIntegers */ 2324 /* 2325 * Function Prototypes 2326 * FNV128string: hash a zero terminated string not including 2327 * the terminating zero 2328 * FNV128block: FNV128 hash a specified length byte vector 2329 * FNV128init: initializes an FNV128 context 2330 * FNV128initBasis: initializes an FNV128 context with a 2331 * provided basis 2332 * FNV128blockin: hash in a specified length byte vector 2333 * FNV128stringin: hash in a zero terminated string not 2334 * including the zero 2335 * FNV128result: returns the hash value 2336 * 2337 * Hash is returned as an array of 8-bit integers 2338 */ 2340 #ifdef __cplusplus 2341 extern "C" { 2342 #endif 2343 /* FNV128 */ 2344 extern int FNV128string ( const char *in, 2345 uint8_t out[FNV128size] ); 2346 extern int FNV128block ( const void *in, 2347 long int length, 2348 uint8_t out[FNV128size] ); 2349 extern int FNV128init ( FNV128context * const ); 2350 extern int FNV128initBasis ( FNV128context * const, 2351 const uint8_t basis[FNV128size] ); 2352 extern int FNV128blockin ( FNV128context * const, 2353 const void *in, 2354 long int length ); 2355 extern int FNV128stringin ( FNV128context * const, 2356 const char *in ); 2357 extern int FNV128result ( FNV128context * const, 2358 uint8_t out[FNV128size] ); 2360 #ifdef __cplusplus 2361 } 2362 #endif 2364 #endif /* _FNV128_H_ */ 2365 2367 2368 /***************************** FNV128.c ****************************/ 2369 /******************** See RFC NNNN for details *********************/ 2370 /* Copyright (c) 2016 IETF Trust and the persons identified as 2371 * authors of the code. All rights 2372 * See fnv-private.h for terms of use and redistribution. 2373 */ 2375 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 2376 * hash function FNV-1a for 128-bit hashes. 2377 */ 2379 #ifndef _FNV128_C_ 2380 #define _FNV128_C_ 2382 #include "fnv-private.h" 2383 #include "FNV128.h" 2385 /* common code for 64 and 32 bit modes */ 2387 /* FNV128 hash a null terminated string (64/32 bit) 2388 ********************************************************************/ 2389 int FNV128string ( const char *in, uint8_t out[FNV128size] ) 2390 { 2391 FNV128context ctx; 2392 int err; 2393 err = FNV128init ( &ctx ); 2394 if ( err != fnvSuccess ) return err; 2395 err = FNV128stringin ( &ctx, in ); 2396 if ( err != fnvSuccess ) return err; 2397 return FNV128result (&ctx, out); 2398 } /* end FNV128string */ 2400 /* FNV128 hash a counted block (64/32 bit) 2401 ********************************************************************/ 2402 int FNV128block ( const void *in, 2403 long int length, 2404 uint8_t out[FNV128size] ) 2405 { 2406 FNV128context ctx; 2407 int err; 2409 err = FNV128init ( &ctx ); 2410 if ( err != fnvSuccess ) return err; 2411 err = FNV128blockin ( &ctx, in, length ); 2412 if ( err != fnvSuccess ) return err; 2413 return FNV128result ( &ctx, out ); 2414 } /* end FNV128block */ 2416 /******************************************************************** 2417 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2418 ********************************************************************/ 2419 #ifdef FNV_64bitIntegers 2421 /* 128 bit FNV_prime = 2^88 + 2^8 + 0x3b */ 2422 /* 0x00000000 01000000 00000000 0000013B */ 2423 #define FNV128primeX 0x013B 2424 #define FNV128shift 24 2426 /* 0x6C62272E 07BB0142 62B82175 6295C58D */ 2427 #define FNV128basis0 0x6C62272E 2428 #define FNV128basis1 0x07BB0142 2429 #define FNV128basis2 0x62B82175 2430 #define FNV128basis3 0x6295C58D 2432 /******************************************************************** 2433 * Set of init, input, and output functions below * 2434 * to incrementally compute FNV128 * 2435 ********************************************************************/ 2437 /* initialize context (64 bit) 2438 ********************************************************************/ 2439 int FNV128init ( FNV128context * const ctx ) 2440 { 2441 if ( ctx ) 2442 { 2443 ctx->Hash[0] = FNV128basis0; 2444 ctx->Hash[1] = FNV128basis1; 2445 ctx->Hash[2] = FNV128basis2; 2446 ctx->Hash[3] = FNV128basis3; 2447 ctx->Computed = FNVinited+FNV128state; 2448 return fnvSuccess; 2449 } 2450 return fnvNull; 2451 } /* end FNV128init */ 2453 /* initialize context with a provided basis (64 bit) 2454 ********************************************************************/ 2455 int FNV128initBasis ( FNV128context * const ctx, 2456 const uint8_t basis[FNV128size] ) 2457 { 2458 int i; 2459 const uint8_t *ui8p; 2460 uint32_t temp; 2462 if ( ctx ) 2463 { 2464 #ifdef FNV_BigEndian 2465 ui8p = basis; 2466 for ( i=0; i < FNV128size/4; ++i ) 2467 { 2468 temp = (*ui8p++)<<8; 2469 temp = (temp + *ui8p++)<<8; 2470 temp = (temp + *ui8p++)<<8; 2471 ctx->Hash[i] = temp + *ui8p; 2472 } 2473 #else 2474 ui8p = basis + ( FNV128size/4 - 1 ); 2475 for ( i=0; i < FNV128size/4; ++i ) 2476 { 2477 temp = (*ui8p--)<<8; 2478 temp = (temp + *ui8p--)<<8; 2479 temp = (temp + *ui8p--)<<8; 2480 ctx->Hash[i] = temp + *ui8p; 2481 } 2482 #endif 2483 ctx->Computed = FNVinited+FNV128state; 2484 return fnvSuccess; 2485 } 2486 return fnvNull; 2487 } /* end FNV128initBasis */ 2489 /* hash in a counted block (64 bit) 2490 ********************************************************************/ 2491 int FNV128blockin ( FNV128context * const ctx, 2492 const void *vin, 2493 long int length ) 2494 { 2495 const uint8_t *in = (const uint8_t*)vin; 2496 uint64_t temp[FNV128size/4]; 2497 uint64_t temp2[2]; 2498 int i; 2500 if ( ctx && in ) 2501 { 2502 if ( length < 0 ) 2503 return fnvBadParam; 2504 switch ( ctx->Computed ) 2505 { 2506 case FNVinited+FNV128state: 2507 ctx->Computed = FNVcomputed+FNV128state; 2508 case FNVcomputed+FNV128state: 2509 break; 2510 default: 2511 return fnvStateError; 2512 } 2513 for ( i=0; iHash[i]; 2515 for ( ; length > 0; length-- ) 2516 { 2517 /* temp = FNV128prime * ( temp ^ *in++ ); */ 2518 temp2[1] = temp[3] << FNV128shift; 2519 temp2[0] = temp[2] << FNV128shift; 2520 temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); 2521 temp[2] *= FNV128primeX; 2522 temp[1] = temp[1] * FNV128primeX + temp2[1]; 2523 temp[0] = temp[0] * FNV128primeX + temp2[0]; 2524 temp[2] += temp[3] >> 32; 2525 temp[3] &= 0xFFFFFFFF; 2526 temp[1] += temp[2] >> 32; 2527 temp[2] &= 0xFFFFFFFF; 2528 temp[0] += temp[1] >> 32; 2529 temp[1] &= 0xFFFFFFFF; 2530 } 2531 for ( i=0; iHash[i] = temp[i]; 2533 return fnvSuccess; 2534 } 2535 return fnvNull; 2536 } /* end FNV128input */ 2538 /* hash in a string (64 bit) 2539 ********************************************************************/ 2540 int FNV128stringin ( FNV128context * const ctx, const char *in ) 2541 { 2542 uint64_t temp[FNV128size/4]; 2543 uint64_t temp2[2]; 2544 int i; 2545 uint8_t ch; 2547 if ( ctx && in ) 2548 { 2549 switch ( ctx->Computed ) 2550 { 2551 case FNVinited+FNV128state: 2552 ctx->Computed = FNVcomputed+FNV128state; 2553 case FNVcomputed+FNV128state: 2554 break; 2555 default: 2556 return fnvStateError; 2557 } 2558 for ( i=0; iHash[i]; 2560 while ( (ch = (uint8_t)*in++) ) 2561 { 2562 /* temp = FNV128prime * ( temp ^ ch ); */ 2563 temp2[1] = temp[3] << FNV128shift; 2564 temp2[0] = temp[2] << FNV128shift; 2565 temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); 2566 temp[2] *= FNV128primeX; 2567 temp[1] = temp[1] * FNV128primeX + temp2[1]; 2568 temp[0] = temp[0] * FNV128primeX + temp2[0]; 2569 temp[2] += temp[3] >> 32; 2570 temp[3] &= 0xFFFFFFFF; 2571 temp[1] += temp[2] >> 32; 2572 temp[2] &= 0xFFFFFFFF; 2573 temp[0] += temp[1] >> 32; 2574 temp[1] &= 0xFFFFFFFF; 2575 } 2576 for ( i=0; iHash[i] = temp[i]; 2578 return fnvSuccess; 2579 } 2580 return fnvNull; 2581 } /* end FNV128stringin */ 2583 /* return hash (64 bit) 2584 ********************************************************************/ 2585 int FNV128result ( FNV128context * const ctx, uint8_t out[FNV128size] ) 2586 { 2587 int i; 2589 if ( ctx && out ) 2590 { 2591 if ( ctx->Computed != FNVcomputed+FNV128state ) 2592 return fnvStateError; 2593 for ( i=0; iHash[i]; 2597 out[14-4*i] = ctx->Hash[i] >> 8; 2598 out[13-4*i] = ctx->Hash[i] >> 16; 2599 out[12-4*i] = ctx->Hash[i] >> 24; 2600 #else 2601 out[4*i] = ctx->Hash[i]; 2602 out[4*i+1] = ctx->Hash[i] >> 8; 2603 out[4*i+2] = ctx->Hash[i] >> 16; 2604 out[4*i+3] = ctx->Hash[i] >> 24; 2605 #endif 2606 ctx -> Hash[i] = 0; 2607 } 2608 ctx->Computed = FNVemptied+FNV128state; 2609 return fnvSuccess; 2610 } 2611 return fnvNull; 2612 } /* end FNV128result */ 2614 /****************************************************************** 2615 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2616 ******************************************************************/ 2617 #else /* FNV_64bitIntegers */ 2618 /****************************************************************** 2619 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2620 ******************************************************************/ 2622 /* 128 bit FNV_prime = 2^88 + 2^8 + 0x3b */ 2623 /* 0x00000000 01000000 00000000 0000013B */ 2624 #define FNV128primeX 0x013B 2625 #define FNV128shift 8 2627 /* 0x6C62272E 07BB0142 62B82175 6295C58D */ 2628 uint16_t FNV128basis[FNV128size/2] = 2629 { 0x6C62, 0x272E, 0x07BB, 0x0142, 2630 0x62B8, 0x2175, 0x6295, 0xC58D }; 2632 /******************************************************************** 2633 * Set of init, input, and output functions below * 2634 * to incrementally compute FNV128 * 2635 ********************************************************************/ 2637 /* initialize context (32 bit) 2638 ********************************************************************/ 2639 int FNV128init ( FNV128context *ctx ) 2640 { 2641 int i; 2642 if ( ctx ) 2643 { 2644 for ( i=0; iHash[i] = FNV128basis[i]; 2646 ctx->Computed = FNVinited+FNV128state; 2647 return fnvSuccess; 2648 } 2649 return fnvNull; 2650 } /* end FNV128init */ 2652 /* initialize context with a provided basis (32 bit) 2653 ********************************************************************/ 2654 int FNV128initBasis ( FNV128context *ctx, 2655 const uint8_t basis[FNV128size] ) 2656 { 2657 int i; 2658 const uint8_t *ui8p; 2659 uint32_t temp; 2661 if ( ctx ) 2662 { 2663 #ifdef FNV_BigEndian 2664 ui8p = basis; 2665 for ( i=0; i < FNV128size/2; ++i ) 2666 { 2667 temp = *ui8p++; 2668 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 2669 } 2670 #else 2671 ui8p = basis + (FNV128size/2 - 1); 2672 for ( i=0; i < FNV128size/2; ++i ) 2673 { 2674 temp = *ui8p--; 2675 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 2676 } 2677 #endif 2678 ctx->Computed = FNVinited+FNV128state; 2679 return fnvSuccess; 2680 } 2681 return fnvNull; 2682 } /* end FNV128initBasis */ 2684 /* hash in a counted block (32 bit) 2685 *******************************************************************/ 2686 int FNV128blockin ( FNV128context *ctx, 2687 const void *vin, 2688 long int length ) 2689 { 2690 const uint8_t *in = (const uint8_t*)vin; 2691 uint32_t temp[FNV128size/2]; 2692 uint32_t temp2[3]; 2693 int i; 2695 if ( ctx && in ) 2696 { 2697 if ( length < 0 ) 2698 return fnvBadParam; 2699 switch ( ctx->Computed ) 2700 { 2701 case FNVinited+FNV128state: 2702 ctx->Computed = FNVcomputed+FNV128state; 2703 case FNVcomputed+FNV128state: 2704 break; 2705 default: 2706 return fnvStateError; 2707 } 2708 for ( i=0; iHash[i]; 2710 for ( ; length > 0; length-- ) 2711 { 2712 /* temp = FNV128prime * ( temp ^ *in++ ); */ 2713 temp[7] ^= *in++; 2714 temp2[2] = temp[7] << FNV128shift; 2715 temp2[1] = temp[6] << FNV128shift; 2716 temp2[0] = temp[5] << FNV128shift; 2717 for ( i=0; i<8; ++i ) 2718 temp[i] *= FNV128primeX; 2719 temp[2] += temp2[2]; 2720 temp[1] += temp2[1]; 2721 temp[0] += temp2[0]; 2722 for ( i=7; i>0; --i ) 2723 { 2724 temp[i-1] += temp[i] >> 16; 2725 temp[i] &= 0xFFFF; 2726 } 2727 } 2728 for ( i=0; iHash[i] = temp[i]; 2730 return fnvSuccess; 2731 } 2732 return fnvNull; 2733 } /* end FNV128blockin */ 2735 /* hash in a string (32 bit) 2736 *******************************************************************/ 2737 int FNV128stringin ( FNV128context *ctx, 2738 const char *in ) 2739 { 2740 uint32_t temp[FNV128size/2]; 2741 uint32_t temp2[3]; 2742 int i; 2743 uint8_t ch; 2745 if ( ctx && in ) 2746 { 2747 switch ( ctx->Computed ) 2748 { 2749 case FNVinited+FNV128state: 2750 ctx->Computed = FNVcomputed+FNV128state; 2751 case FNVcomputed+FNV128state: 2752 break; 2753 default: 2754 return fnvStateError; 2755 } 2756 for ( i=0; iHash[i]; 2758 while ( (ch = (uint8_t)*in++) ) 2759 { 2760 /* temp = FNV128prime * ( temp ^ *in++ ); */ 2761 temp[7] ^= ch; 2762 temp2[2] = temp[7] << FNV128shift; 2763 temp2[1] = temp[6] << FNV128shift; 2764 temp2[0] = temp[5] << FNV128shift; 2765 for ( i=0; i<8; ++i ) 2766 temp[i] *= FNV128primeX; 2767 temp[2] += temp2[2]; 2768 temp[1] += temp2[1]; 2769 temp[0] += temp2[0]; 2770 for ( i=7; i>0; --i ) 2771 { 2772 temp[i-1] += temp[i] >> 16; 2773 temp[i] &= 0xFFFF; 2774 } 2775 } 2776 for ( i=0; iHash[i] = temp[i]; 2778 return fnvSuccess; 2779 } 2780 return fnvNull; 2781 } /* end FNV128stringin */ 2783 /* return hash (32 bit) 2784 ********************************************************************/ 2785 int FNV128result ( FNV128context *ctx, 2786 uint8_t out[FNV128size] ) 2787 { 2788 int i; 2790 if ( ctx && out ) 2791 { 2792 if ( ctx->Computed != FNVcomputed+FNV128state ) 2793 return fnvStateError; 2794 for ( i=0; iHash[i]; 2798 out[14-2*i] = ctx->Hash[i] >> 8; 2799 #else 2800 out[2*i] = ctx->Hash[i]; 2801 out[2*i+1] = ctx->Hash[i] >> 8; 2802 #endif 2803 ctx -> Hash[i] = 0; 2804 } 2805 ctx->Computed = FNVemptied+FNV128state; 2806 return fnvSuccess; 2807 } 2808 return fnvNull; 2809 } /* end FNV128result */ 2811 #endif /* Have64bitIntegers */ 2812 /******************************************************************** 2813 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2814 ********************************************************************/ 2816 #endif /* _FNV128_C_ */ 2817 2819 6.1.4 FNV256 C Code 2821 The header and C source for 256-bit FNV-1a returning a byte vector. 2823 2824 /**************************** FNV256.h **************************/ 2825 /***************** See RFC NNNN for details. ********************/ 2826 /* 2827 * Copyright (c) 2016 IETF Trust and the persons identified as 2828 * authors of the code. All rights reserved. 2829 * See fnv-private.h for terms of use and redistribution. 2830 */ 2832 #ifndef _FNV256_H_ 2833 #define _FNV256_H_ 2835 /* 2836 * Description: 2837 * This file provides headers for the 256-bit version of the 2838 * FNV-1a non-cryptographic hash algorithm. 2839 */ 2841 #include "FNVconfig.h" 2843 #include 2844 #define FNV256size (256/8) 2846 /* If you do not have the ISO standard stdint.h header file, then you 2847 * must typedef the following types: 2848 * 2849 * type meaning 2850 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 2851 * uint32_t unsigned 32 bit integer 2852 * uint16_t unsigned 16 bit integer 2853 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 2854 */ 2856 #ifndef _FNV_ErrCodes_ 2857 #define _FNV_ErrCodes_ 2858 /********************************************************************* 2859 * All FNV functions provided return as integer as follows: 2860 * 0 -> success 2861 * >0 -> error as listed below 2862 */ 2863 enum { /* success and errors */ 2864 fnvSuccess = 0, 2865 fnvNull, /* Null pointer parameter */ 2866 fnvStateError, /* called Input after Result or before Init */ 2867 fnvBadParam /* passed a bad parameter */ 2868 }; 2869 #endif /* _FNV_ErrCodes_ */ 2871 /* 2872 * This structure holds context information for an FNV256 hash 2873 */ 2874 #ifdef FNV_64bitIntegers 2875 /* version if 64 bit integers supported */ 2876 typedef struct FNV256context_s { 2877 int Computed; /* state */ 2878 uint32_t Hash[FNV256size/4]; 2879 } FNV256context; 2881 #else 2882 /* version if 64 bit integers NOT supported */ 2884 typedef struct FNV256context_s { 2885 int Computed; /* state */ 2886 uint16_t Hash[FNV256size/2]; 2887 } FNV256context; 2889 #endif /* FNV_64bitIntegers */ 2890 /* 2891 * Function Prototypes 2892 * FNV256string: hash a zero terminated string not including 2893 * the zero 2894 * FNV256block: FNV256 hash a specified length byte vector 2895 * FNV256init: initializes an FNV256 context 2896 * FNV256initBasis: initializes an FNV256 context with a provided 2897 * basis 2898 * FNV256blockin: hash in a specified length byte vector 2899 * FNV256stringin: hash in a zero terminated string not 2900 * including the zero 2901 * FNV256result: returns the hash value 2902 * 2903 * Hash is returned as an array of 8-bit integers 2904 */ 2906 #ifdef __cplusplus 2907 extern "C" { 2908 #endif 2910 /* FNV256 */ 2911 extern int FNV256string ( const char *in, 2912 uint8_t out[FNV256size] ); 2913 extern int FNV256block ( const void *in, 2914 long int length, 2915 uint8_t out[FNV256size] ); 2916 extern int FNV256init ( FNV256context *); 2917 extern int FNV256initBasis ( FNV256context * const, 2918 const uint8_t basis[FNV256size] ); 2919 extern int FNV256blockin ( FNV256context * const, 2920 const void *in, 2921 long int length ); 2922 extern int FNV256stringin ( FNV256context * const, 2923 const char *in ); 2924 extern int FNV256result ( FNV256context * const, 2925 uint8_t out[FNV256size] ); 2927 #ifdef __cplusplus 2928 } 2929 #endif 2931 #endif /* _FNV256_H_ */ 2932 2934 2935 /***************************** FNV256.c ****************************/ 2936 /******************** See RFC NNNN for details *********************/ 2937 /* Copyright (c) 2016 IETF Trust and the persons identified as 2938 * authors of the code. All rights 2939 * See fnv-private.h for terms of use and redistribution. 2941 */ 2943 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 2944 * hash function FNV-1a for 256-bit hashes. 2945 */ 2947 #ifndef _FNV256_C_ 2948 #define _FNV256_C_ 2950 #include "fnv-private.h" 2951 #include "FNV256.h" 2953 /* common code for 64 and 32 bit modes */ 2955 /* FNV256 hash a null terminated string (64/32 bit) 2956 ********************************************************************/ 2957 int FNV256string ( const char *in, uint8_t out[FNV256size] ) 2958 { 2959 FNV256context ctx; 2960 int err; 2962 if ( (err = FNV256init ( &ctx )) != fnvSuccess ) 2963 return err; 2964 if ( (err = FNV256stringin ( &ctx, in )) != fnvSuccess ) 2965 return err; 2966 return FNV256result ( &ctx, out ); 2967 } /* end FNV256string */ 2969 /* FNV256 hash a counted block (64/32 bit) 2970 ********************************************************************/ 2971 int FNV256block ( const void *in, 2972 long int length, 2973 uint8_t out[FNV256size] ) 2974 { 2975 FNV256context ctx; 2976 int err; 2978 if ( (err = FNV256init ( &ctx )) != fnvSuccess ) 2979 return err; 2980 if ( (err = FNV256blockin ( &ctx, in, length)) != fnvSuccess ) 2981 return err; 2982 return FNV256result ( &ctx, out ); 2983 } /* end FNV256block */ 2985 /******************************************************************** 2986 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2987 ********************************************************************/ 2988 #ifdef FNV_64bitIntegers 2989 /* 256 bit FNV_prime = 2^168 + 2^8 + 0x63 */ 2990 /* 0x0000000000000000 0000010000000000 2991 0000000000000000 0000000000000163 */ 2992 #define FNV256primeX 0x0163 2993 #define FNV256shift 8 2995 /* 0xDD268DBCAAC55036 2D98C384C4E576CC 2996 C8B1536847B6BBB3 1023B4C8CAEE0535 */ 2997 uint32_t FNV256basis[FNV256size/4] = { 2998 0xDD268DBC, 0xAAC55036, 0x2D98C384, 0xC4E576CC, 2999 0xC8B15368, 0x47B6BBB3, 0x1023B4C8, 0xCAEE0535 }; 3001 /******************************************************************** 3002 * Set of init, input, and output functions below * 3003 * to incrementally compute FNV256 * 3004 ********************************************************************/ 3006 /* initialize context (64 bit) 3007 ********************************************************************/ 3008 int FNV256init ( FNV256context *ctx ) 3009 { 3010 int i; 3012 if ( ctx ) 3013 { 3014 for ( i=0; iHash[i] = FNV256basis[i]; 3016 ctx->Computed = FNVinited+FNV256state; 3017 return fnvSuccess; 3018 } 3019 return fnvNull; 3020 } /* end FNV256init */ 3022 /* initialize context with a provided basis (64 bit) 3023 ********************************************************************/ 3024 int FNV256initBasis ( FNV256context* const ctx, 3025 const uint8_t basis[FNV256size] ) 3026 { 3027 int i; 3028 const uint8_t *ui8p; 3029 uint32_t temp; 3031 if ( ctx ) 3032 { 3033 #ifdef FNV_BigEndian 3034 ui8p = basis; 3035 for ( i=0; i < FNV256size/4; ++i ) 3036 { 3037 temp = (*ui8p++)<<8; 3038 temp = (temp + *ui8p++)<<8; 3039 temp = (temp + *ui8p++)<<8; 3040 ctx->Hash[i] = temp + *ui8p; 3041 } 3042 #else 3043 ui8p = basis + (FNV256size/4 - 1); 3044 for ( i=0; i < FNV256size/4; ++i ) 3045 { 3046 temp = (*ui8p--)<<8; 3047 temp = (temp + *ui8p--)<<8; 3048 temp = (temp + *ui8p--)<<8; 3049 ctx->Hash[i] = temp + *ui8p; 3050 } 3051 #endif 3052 ctx->Computed = FNVinited+FNV256state; 3053 return fnvSuccess; 3054 } 3055 return fnvNull; 3056 } /* end FNV256initBasis */ 3058 /* hash in a counted block (64 bit) 3059 ********************************************************************/ 3060 int FNV256blockin ( FNV256context *ctx, 3061 const void *vin, 3062 long int length ) 3063 { 3064 const uint8_t *in = (const uint8_t*)vin; 3065 uint64_t temp[FNV256size/4]; 3066 uint64_t temp2[3]; 3067 int i; 3069 if ( ctx && in ) 3070 { 3071 if ( length < 0 ) 3072 return fnvBadParam; 3073 switch ( ctx->Computed ) 3074 { 3075 case FNVinited+FNV256state: 3076 ctx->Computed = FNVcomputed+FNV256state; 3077 case FNVcomputed+FNV256state: 3078 break; 3079 default: 3080 return fnvStateError; 3081 } 3082 for ( i=0; iHash[i]; 3084 for ( ; length > 0; length-- ) 3085 { 3086 /* temp = FNV256prime * ( temp ^ *in++ ); */ 3087 temp[7] ^= *in++; 3088 temp2[2] = temp[7] << FNV256shift; 3089 temp2[1] = temp[6] << FNV256shift; 3090 temp2[0] = temp[5] << FNV256shift; 3091 for ( i=0; i0; --i ) 3097 { 3098 temp[i-1] += temp[i] >> 16; 3099 temp[i] &= 0xFFFF; 3100 } 3101 } 3102 for ( i=0; iHash[i] = temp[i]; 3104 return fnvSuccess; 3105 } 3106 return fnvNull; 3107 } /* end FNV256input */ 3109 /* hash in a string (64 bit) 3110 ********************************************************************/ 3111 int FNV256stringin ( FNV256context *ctx, const char *in ) 3112 { 3113 uint64_t temp[FNV256size/4]; 3114 uint64_t temp2[3]; 3115 int i; 3116 uint8_t ch; 3118 if ( ctx && in ) 3119 { 3120 switch ( ctx->Computed ) 3121 { 3122 case FNVinited+FNV256state: 3123 ctx->Computed = FNVcomputed+FNV256state; 3124 case FNVcomputed+FNV256state: 3125 break; 3126 default: 3127 return fnvStateError; 3128 } 3129 for ( i=0; iHash[i]; 3131 while ( (ch = (uint8_t)*in++) ) 3132 { 3133 /* temp = FNV256prime * ( temp ^ ch ); */ 3134 temp[7] ^= ch; 3135 temp2[2] = temp[7] << FNV256shift; 3136 temp2[1] = temp[6] << FNV256shift; 3137 temp2[0] = temp[5] << FNV256shift; 3138 for ( i=0; i0; --i ) 3144 { 3145 temp[i-1] += temp[i] >> 16; 3146 temp[i] &= 0xFFFF; 3147 } 3148 } 3149 for ( i=0; iHash[i] = temp[i]; 3151 return fnvSuccess; 3152 } 3153 return fnvNull; 3154 } /* end FNV256stringin */ 3156 /* return hash (64 bit) 3157 ********************************************************************/ 3158 int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] ) 3159 { 3160 int i; 3162 if ( ctx && out ) 3163 { 3164 if ( ctx->Computed != FNVcomputed+FNV256state ) 3165 return fnvStateError; 3166 for ( i=0; iHash[i]; 3170 out[31-4*i] = ctx->Hash[i] >> 8; 3171 out[31-4*i] = ctx->Hash[i] >> 16; 3172 out[31-4*i] = ctx->Hash[i] >> 24; 3173 #else 3174 out[4*i] = ctx->Hash[i]; 3175 out[4*i+1] = ctx->Hash[i] >> 8; 3176 out[4*i+2] = ctx->Hash[i] >> 16; 3177 out[4*i+3] = ctx->Hash[i] >> 24; 3178 #endif 3179 ctx -> Hash[i] = 0; 3180 } 3181 ctx->Computed = FNVemptied+FNV256state; 3182 return fnvSuccess; 3183 } 3184 return fnvNull; 3185 } /* end FNV256result */ 3187 /****************************************************************** 3188 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 3189 ******************************************************************/ 3190 #else /* FNV_64bitIntegers */ 3191 /****************************************************************** 3192 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3193 ******************************************************************/ 3195 /* version for when you only have 32-bit arithmetic 3196 ********************************************************************/ 3198 /* 256 bit FNV_prime = 2^168 + 2^8 + 0x63 */ 3199 /* 0x00000000 00000000 00000100 00000000 3200 00000000 00000000 00000000 00000163 */ 3201 #define FNV256primeX 0x0163 3202 #define FNV256shift 8 3204 /* 0xDD268DBCAAC55036 2D98C384C4E576CC 3205 C8B1536847B6BBB3 1023B4C8CAEE0535 */ 3206 uint16_t FNV256basis[FNV256size/2] = { 3207 0xDD26, 0x8DBC, 0xAAC5, 0x5036, 3208 0x2D98, 0xC384, 0xC4E5, 0x76CC, 3209 0xC8B1, 0x5368, 0x47B6, 0xBBB3, 3210 0x1023, 0xB4C8, 0xCAEE, 0x0535 }; 3212 /******************************************************************** 3213 * Set of init, input, and output functions below * 3214 * to incrementally compute FNV256 * 3215 ********************************************************************/ 3217 /* initialize context (32 bit) 3218 ********************************************************************/ 3219 int FNV256init ( FNV256context *ctx ) 3220 { 3221 int i; 3223 if ( ctx ) 3224 { 3225 for ( i=0; iHash[i] = FNV256basis[i]; 3227 ctx->Computed = FNVinited+FNV256state; 3228 return fnvSuccess; 3229 } 3230 return fnvNull; 3231 } /* end FNV256init */ 3233 /* initialize context with a provided basis (32 bit) 3234 ********************************************************************/ 3235 int FNV256initBasis ( FNV256context *ctx, 3236 const uint8_t basis[FNV256size] ) 3237 { 3238 int i; 3239 const uint8_t *ui8p; 3240 uint32_t temp; 3242 if ( ctx ) 3243 { 3244 #ifdef FNV_BigEndian 3245 ui8p = basis; 3246 for ( i=0; i < FNV256size/2; ++i ) 3247 { 3248 temp = *ui8p++; 3249 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 3250 } 3251 #else 3252 ui8p = basis + FNV256size/2 -1; 3253 for ( i=0; i < FNV256size/2; ++i ) 3254 { 3255 temp = *ui8p--; 3256 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 3257 } 3258 #endif 3259 ctx->Computed = FNVinited+FNV256state; 3260 return fnvSuccess; 3261 } 3262 return fnvNull; 3263 } /* end FNV256initBasis */ 3265 /* hash in a counted block (32 bit) 3266 *******************************************************************/ 3267 int FNV256blockin ( FNV256context *ctx, 3268 const void *vin, 3269 long int length ) 3270 { 3271 const uint8_t *in = (const uint8_t*)vin; 3272 uint32_t temp[FNV256size/2]; 3273 uint32_t temp2[6]; 3274 int i; 3276 if ( ctx && in ) 3277 { 3278 if ( length < 0 ) 3279 return fnvBadParam; 3280 switch ( ctx->Computed ) 3281 { 3282 case FNVinited+FNV256state: 3283 ctx->Computed = FNVcomputed+FNV256state; 3284 case FNVcomputed+FNV256state: 3285 break; 3286 default: 3287 return fnvStateError; 3288 } 3290 for ( i=0; iHash[i]; 3292 for ( ; length > 0; length-- ) 3293 { 3294 /* temp = FNV256prime * ( temp ^ *in++ ); */ 3295 temp[15] ^= *in++; 3296 for ( i=0; i<6; ++i ) 3297 temp2[i] = temp[10+i] << FNV256shift; 3298 for ( i=0; i0; --i ) 3303 { 3304 temp[i-1] += temp[i] >> 16; 3305 temp[i] &= 0xFFFF; 3306 } 3307 } 3308 for ( i=0; iHash[i] = temp[i]; 3310 return fnvSuccess; 3311 } 3312 return fnvNull; 3313 } /* end FNV256blockin */ 3315 /* hash in a string (32 bit) 3316 *******************************************************************/ 3317 int FNV256stringin ( FNV256context *ctx, const char *in ) 3318 { 3319 uint32_t temp[FNV256size/2]; 3320 uint32_t temp2[6]; 3321 int i; 3322 uint8_t ch; 3324 if ( ctx && in ) 3325 { 3326 switch ( ctx->Computed ) 3327 { 3328 case FNVinited+FNV256state: 3329 ctx->Computed = FNVcomputed+FNV256state; 3330 case FNVcomputed+FNV256state: 3331 break; 3332 default: 3333 return fnvStateError; 3334 } 3335 for ( i=0; iHash[i]; 3337 while ( ( ch = (uint8_t)*in++ ) != 0) 3338 { 3339 /* temp = FNV256prime * ( temp ^ *in++ ); */ 3340 temp[15] ^= ch; 3341 for ( i=0; i<6; ++i ) 3342 temp2[i] = temp[10+i] << FNV256shift; 3343 for ( i=0; i0; --i ) 3348 { 3349 temp[i-1] += temp[i] >> 16; 3350 temp[i] &= 0xFFFF; 3351 } 3352 } 3353 for ( i=0; iHash[i] = temp[i]; 3355 return fnvSuccess; 3356 } 3357 return fnvNull; 3358 } /* end FNV256stringin */ 3360 /* return hash (32 bit) 3361 ********************************************************************/ 3362 int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] ) 3363 { 3364 int i; 3366 if ( ctx && out ) 3367 { 3368 if ( ctx->Computed != FNVcomputed+FNV256state ) 3369 return fnvStateError; 3370 for ( i=0; iHash[i]; 3374 out[30-2*i] = ctx->Hash[i] >> 8; 3375 #else 3376 out[2*i] = ctx->Hash[i]; 3377 out[2*i+1] = ctx->Hash[i] >> 8; 3378 #endif 3379 ctx->Hash[i] = 0; 3380 } 3381 ctx->Computed = FNVemptied+FNV256state; 3382 return fnvSuccess; 3383 } 3384 return fnvNull; 3385 } /* end FNV256result */ 3387 #endif /* Have64bitIntegers */ 3388 /******************************************************************** 3389 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3390 ********************************************************************/ 3392 #endif /* _FNV256_C_ */ 3393 3395 6.1.5 FNV512 C Code 3397 The header and C source for 512-bit FNV-1a returning a byte vector. 3399 3400 /**************************** FNV512.h **************************/ 3401 /***************** See RFC NNNN for details. ********************/ 3402 /* 3403 * Copyright (c) 2016 IETF Trust and the persons identified as 3404 * authors of the code. All rights reserved. 3405 * See fnv-private.h for terms of use and redistribution. 3406 */ 3408 #ifndef _FNV512_H_ 3409 #define _FNV512_H_ 3411 /* 3412 * Description: 3413 * This file provides headers for the 512-bit version of the 3414 * FNV-1a non-cryptographic hash algorithm. 3415 */ 3417 #include "FNVconfig.h" 3419 #include 3420 #define FNV512size (512/8) 3422 /* If you do not have the ISO standard stdint.h header file, then you 3423 * must typedef the following types: 3424 * 3425 * type meaning 3426 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 3427 * uint32_t unsigned 32 bit integer 3428 * uint16_t unsigned 16 bit integer 3429 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 3430 */ 3432 #ifndef _FNV_ErrCodes_ 3433 #define _FNV_ErrCodes_ 3434 /********************************************************************* 3435 * All FNV functions provided return as integer as follows: 3436 * 0 -> success 3437 * >0 -> error as listed below 3438 */ 3439 enum { /* success and errors */ 3440 fnvSuccess = 0, 3441 fnvNull, /* Null pointer parameter */ 3442 fnvStateError, /* called Input after Result or before Init */ 3443 fnvBadParam /* passed a bad parameter */ 3444 }; 3445 #endif /* _FNV_ErrCodes_ */ 3447 /* 3448 * This structure holds context information for an FNV512 hash 3449 */ 3450 #ifdef FNV_64bitIntegers 3451 /* version if 64 bit integers supported */ 3452 typedef struct FNV512context_s { 3453 int Computed; /* state */ 3454 uint32_t Hash[FNV512size/4]; 3455 } FNV512context; 3457 #else 3458 /* version if 64 bit integers NOT supported */ 3460 typedef struct FNV512context_s { 3461 int Computed; /* state */ 3462 uint16_t Hash[FNV512size/2]; 3463 } FNV512context; 3465 #endif /* FNV_64bitIntegers */ 3467 /* 3468 * Function Prototypes 3469 * FNV512string: hash a zero terminated string not including 3470 * the terminating zero 3471 * FNV512block: FNV512 hash a specified length byte vector 3472 * FNV512init: initializes an FNV512 context 3473 * FNV512initBasis: initializes an FNV512 context with a 3474 * provided basis 3475 * FNV512blockin: hash in a specified length byte vector 3476 * FNV512stringin: hash in a zero terminated string not 3477 * including the zero 3478 * FNV512result: returns the hash value 3479 * 3480 * Hash is returned as an array of 8-bit integers 3481 */ 3483 #ifdef __cplusplus 3484 extern "C" { 3485 #endif 3487 /* FNV512 */ 3488 extern int FNV512string ( const char *in, 3489 uint8_t out[FNV512size] ); 3490 extern int FNV512block ( const void *in, 3491 long int length, 3492 uint8_t out[FNV512size] ); 3493 extern int FNV512init ( FNV512context *); 3494 extern int FNV512initBasis ( FNV512context * const, 3495 const uint8_t basis[FNV512size] ); 3496 extern int FNV512blockin ( FNV512context *, 3497 const void *in, 3498 long int length ); 3499 extern int FNV512stringin ( FNV512context *, 3500 const char *in ); 3501 extern int FNV512result ( FNV512context *, 3502 uint8_t out[FNV512size] ); 3504 #ifdef __cplusplus 3505 } 3506 #endif 3508 #endif /* _FNV512_H_ */ 3509 3511 3512 /***************************** FNV512.c ****************************/ 3513 /******************** See RFC NNNN for details *********************/ 3514 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 3515 * authors of the code. All rights 3516 * See fnv-private.h for terms of use and redistribution. 3517 */ 3519 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 3520 * hash function FNV-1a for 512-bit hashes. 3521 */ 3523 #ifndef _FNV512_C_ 3524 #define _FNV512_C_ 3526 #include "fnv-private.h" 3527 #include "FNV512.h" 3529 /* common code for 64 and 32 bit modes */ 3531 /* FNV512 hash a null terminated string (64/32 bit) 3532 ********************************************************************/ 3533 int FNV512string ( const char *in, uint8_t out[FNV512size] ) 3534 { 3535 FNV512context ctx; 3536 int err; 3537 if ( (err = FNV512init ( &ctx )) != fnvSuccess ) 3538 return err; 3539 if ( (err = FNV512stringin ( &ctx, in )) != fnvSuccess ) 3540 return err; 3541 return FNV512result ( &ctx, out ); 3542 } /* end FNV512string */ 3544 /* FNV512 hash a counted block (64/32 bit) 3545 ********************************************************************/ 3546 int FNV512block ( const void *in, 3547 long int length, 3548 uint8_t out[FNV512size] ) 3549 { 3550 FNV512context ctx; 3551 int err; 3553 if ( (err = FNV512init ( &ctx )) != fnvSuccess ) 3554 return err; 3555 if ( (err = FNV512blockin ( &ctx, in, length)) != fnvSuccess ) 3556 return err; 3557 return FNV512result ( &ctx, out ); 3558 } /* end FNV512block */ 3560 /******************************************************************** 3561 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 3562 ********************************************************************/ 3563 #ifdef FNV_64bitIntegers 3565 /* 3566 512 bit FNV_prime = 2^344 + 2^8 + 0x57 = 3567 0x0000000000000000 0000000000000000 3568 0000000001000000 0000000000000000 3569 0000000000000000 0000000000000000 3570 0000000000000000 0000000000000157 */ 3571 #define FNV512primeX 0x0157 3572 #define FNV512shift 24 3574 /* 0xB86DB0B1171F4416 DCA1E50F309990AC 3575 AC87D059C9000000 0000000000000D21 3576 E948F68A34C192F6 2EA79BC942DBE7CE 3577 182036415F56E34B AC982AAC4AFE9FD9 */ 3579 uint32_t FNV512basis[FNV512size/4] = { 3580 0xB86DB0B1, 0x171F4416, 0xDCA1E50F, 0x209990AC, 3581 0xAC87D059, 0x9C000000, 0x00000000, 0x00000D21, 3582 0xE948F68A, 0x34C192F6, 0x2EA79BC9, 0x42DBE7CE, 3583 0x18203641, 0x5F56E34B, 0xAC982AAC, 0x4AFE9FD9 }; 3585 /******************************************************************** 3586 * Set of init, input, and output functions below * 3587 * to incrementally compute FNV512 * 3588 ********************************************************************/ 3590 /* initialize context (64 bit) 3591 ********************************************************************/ 3592 int FNV512init ( FNV512context *ctx ) 3593 { 3594 if ( ctx ) 3595 { 3596 for ( i=0; iHash[i] = FNV512basis[i]; 3598 ctx->Computed = FNVinited+FNV512state; 3599 return fnvSuccess; 3600 } 3601 return fnvNull; 3602 } /* end FNV512init */ 3604 /* initialize context with a provided basis (64 bit) 3605 ********************************************************************/ 3606 int FNV512initBasis ( FNV512context* const ctx, 3607 const uint8_t basis[FNV512size] ) 3608 { 3609 int i; 3610 const uint8_t *ui8p; 3611 uint32_t temp; 3613 if ( ctx ) 3614 { 3615 #ifdef FNV_BigEndian 3616 ui8p = basis; 3617 for ( i=0; i < FNV512size/4; ++i ) 3618 { 3619 temp = (*ui8p++)<<8; 3620 temp = (temp + *ui8p++)<<8; 3621 temp = (temp + *ui8p++)<<8; 3622 ctx->Hash[i] = temp + *ui8p; 3623 } 3624 #else 3625 ui8p = basis + (FNV512size/4 - 1); 3626 for ( i=0; i < FNV512size/4; ++i ) 3627 { 3628 temp = (*ui8p--)<<8; 3629 temp = (temp + *ui8p--)<<8; 3630 temp = (temp + *ui8p--)<<8; 3631 ctx->Hash[i] = temp + *ui8p; 3632 } 3633 #endif 3634 ctx->Computed = FNVinited+FNV512state; 3635 return fnvSuccess; 3636 } 3637 return fnvNull; 3638 } /* end FNV512initBasis */ 3640 /* hash in a counted block (64 bit) 3641 ********************************************************************/ 3642 int FNV512blockin ( FNV512context *ctx, 3643 const void *vin, 3644 long int length ) 3645 { 3646 const uint8_t *in = (const uint8_t*)vin; 3647 uint64_t temp[FNV512size/4]; 3648 uint64_t temp2[3]; 3650 if ( ctx && in ) 3651 { 3652 switch ( ctx->Computed ) 3653 { 3654 case FNVinited+FNV512state: 3655 ctx->Computed = FNVcomputed+FNV128state; 3656 case FNVcomputed+FNV512state: 3657 break; 3658 default: 3659 return fnvStateError; 3660 } 3661 if ( length < 0 ) 3662 return fnvBadParam; 3663 for ( i=0; iHash[i]; 3665 for ( ; length > 0; length-- ) 3666 { 3667 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3668 temp[7] ^= *in++; 3669 temp2[2] = temp[7] << FNV512shift; 3670 temp2[1] = temp[6] << FNV512shift; 3671 temp2[0] = temp[5] << FNV512shift; 3672 for ( i=0; i0; --i ) 3678 { 3679 temp[i-1] += temp[i] >> 16; 3680 temp[i] &= 0xFFFF; 3681 } 3682 } 3683 for ( i=0; iHash[i] = temp[i]; 3685 return fnvSuccess; 3686 } 3687 return fnvNull; 3688 } /* end FNV512input */ 3690 /* hash in a string (64 bit) 3691 ********************************************************************/ 3692 inf FNV512stringin ( FNV512context *ctx, const char *in ) 3693 { 3694 uint64_t temp[FNV512size/4]; 3695 uint64_t temp2[2]; 3696 int i; 3697 uint8_t ch; 3699 if ( ctx && in ) 3700 { 3701 switch ( ctx->Computed ) 3702 { 3703 case FNVinited+FNV512state: 3704 ctx->Computed = FNVcomputed+FNV512state; 3705 case FNVcomputed+FNV512state: 3706 break; 3707 default: 3708 return fnvStateError; 3709 } 3710 for ( i=0; iHash[i]; 3712 while ( ch = (uint8_t)*in++ ) 3713 { 3714 /* temp = FNV512prime * ( temp ^ ch ); */ 3715 temp[7] ^= ch; 3716 temp2[2] = temp[7] << FNV128shift; 3717 temp2[1] = temp[6] << FNV128shift; 3718 temp2[0] = temp[5] << FNV128shift; 3719 for ( i=0; i0; --i ) 3725 { 3726 temp[i-1] += temp[i] >> 16; 3727 temp[i] &= 0xFFFF; 3728 } 3729 } 3730 for ( i=0; iHash[i] = temp[i]; 3732 return fnvSuccess; 3733 } 3734 return fnvNull; 3735 } /* end FNV512stringin */ 3736 /* return hash (64 bit) 3737 ********************************************************************/ 3738 int FNV512result ( FNV512context *ctx, uint8_t out[FNV512size] ) 3739 { 3740 if ( ctx && out ) 3741 { 3742 if ( ctx->Computed != FNVcomputed+FNV512state ) 3743 return fnvStateError; 3744 for ( i=0; iHash[i]; 3748 out[14-2*i] = ctx->Hash[i] >> 8; 3749 #else 3750 out[2*i] = ctx->Hash[i]; 3751 out[2*i+1] = ctx->Hash[i] >> 8; 3752 #endif 3753 ctx -> Hash[i] = 0; 3754 } 3755 ctx->Computed = FNVemptied+FNV512state; 3756 return fnvSuccess; 3757 } 3758 return fnvNull; 3759 } /* end FNV512result */ 3761 /****************************************************************** 3762 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 3763 ******************************************************************/ 3764 #else /* FNV_64bitIntegers */ 3765 /****************************************************************** 3766 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3767 ******************************************************************/ 3769 /* version for when you only have 32-bit arithmetic 3770 ********************************************************************/ 3772 /* 3773 512 bit FNV_prime = 2^344 + 2^8 + 0x57 = 3774 0x0000000000000000 0000000000000000 3775 0000000001000000 0000000000000000 3776 0000000000000000 0000000000000000 3777 0000000000000000 0000000000000157 */ 3778 #define FNV512primeX 0x0157 3779 #define FNV512shift 8 3781 /* 0xB86DB0B1171F4416 DCA1E50F309990AC 3782 AC87D059C9000000 0000000000000D21 3783 E948F68A34C192F6 2EA79BC942DBE7CE 3784 182036415F56E34B AC982AAC4AFE9FD9 */ 3786 uint16_t FNV512basis[FNV512size/2] = { 3787 0xB86D, 0xB0B1, 0x171F, 0x4416, 0xDCA1, 0xE50F, 0x3099, 0x90AC, 3788 0xAC87, 0xD059, 0xC900, 0x0000, 0x0000, 0x0000, 0x0000, 0x0D21, 3789 0xE948, 0xF68A, 0x34C1, 0x92F6, 0x2EA7, 0x9BC9, 0x42DB, 0xE7CE, 3790 0x1820, 0x3641, 0x5F56, 0xE34B, 0xAC98, 0x2AAC, 0x4AFE, 0x9FD9 }; 3792 /******************************************************************** 3793 * Set of init, input, and output functions below * 3794 * to incrementally compute FNV512 * 3795 ********************************************************************/ 3797 /* initialize context (32 bit) 3798 ********************************************************************/ 3799 int FNV512init ( FNV512context *ctx ) 3800 { 3801 int i; 3803 if ( ctx ) 3804 { 3805 for ( i=0; iHash[i] = FNV512basis[i]; 3807 ctx->Computed = FNVinited+FNV512state; 3808 return fnvSuccess; 3809 } 3810 return fnvNull; 3811 } /* end FNV512init */ 3813 /* initialize context with a provided basis (32 bit) 3814 ********************************************************************/ 3815 int FNV512initBasis ( FNV512context *ctx, 3816 const uint8_t basis[FNV512size] ) 3817 { 3818 int i; 3819 const uint8_t *ui8p; 3820 uint32_t temp; 3822 if ( ctx ) 3823 { 3824 #ifdef FNV_BigEndian 3825 ui8p = basis; 3826 for ( i=0; i < FNV512size/2; ++i ) 3827 { 3828 temp = *ui8p++; 3829 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 3830 } 3831 #else 3832 ui8p = basis + ( FNV512size/2 - 1 ); 3833 for ( i=0; i < FNV512size/2; ++i ) 3834 { 3835 temp = *ui8p--; 3836 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 3837 } 3838 #endif 3839 ctx->Computed = FNVinited+FNV512state; 3840 return fnvSuccess; 3841 } 3842 return fnvNull; 3843 } /* end FNV512initBasis */ 3845 /* hash in a counted block (32 bit) 3846 *******************************************************************/ 3847 int FNV512blockin ( FNV512context *ctx, 3848 const void *vin, 3849 long int length ) 3850 { 3851 const uint8_t *in = (const uint8_t*)vin; 3852 uint32_t temp[FNV512size/2]; 3853 uint32_t temp2[6]; 3854 int i; 3856 if ( ctx && in ) 3857 { 3858 switch ( ctx->Computed ) 3859 { 3860 case FNVinited+FNV512state: 3861 ctx->Computed = FNVcomputed+FNV512state; 3862 case FNVcomputed+FNV512state: 3863 break; 3864 default: 3865 return fnvStateError; 3866 } 3867 if ( length < 0 ) 3868 return fnvBadParam; 3869 for ( i=0; iHash[i]; 3871 for ( ; length > 0; length-- ) 3872 { 3873 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3874 temp[15] ^= *in++; 3875 for ( i=0; i<6; ++i ) 3876 temp2[i] = temp[10+i] << FNV512shift; 3877 for ( i=0; i0; --i ) 3882 { 3883 temp[i-1] += temp[i] >> 16; 3884 temp[i] &= 0xFFFF; 3885 } 3886 } 3887 for ( i=0; iHash[i] = temp[i]; 3889 return fnvSuccess; 3890 } 3891 return fnvNull; 3892 } /* end FNV512blockin */ 3894 /* hash in a string (32 bit) 3895 *******************************************************************/ 3896 int FNV512stringin ( FNV512context *ctx, const char *in ) 3897 { 3898 uint32_t temp[FNV512size/2]; 3899 uint32_t temp2[6]; 3900 int i; 3901 uint8_t ch; 3903 if ( ctx && in ) 3904 { 3905 switch ( ctx->Computed ) 3906 { 3907 case FNVinited+FNV512state: 3908 ctx->Computed = FNVcomputed+FNV512state; 3909 case FNVcomputed+FNV512state: 3910 break; 3911 default: 3912 return fnvStateError; 3913 } 3914 for ( i=0; iHash[i]; 3916 while ( (ch = (uint8_t)*in++) ) 3917 { 3918 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3919 temp[15] ^= ch; 3920 for ( i=0; i<6; ++i ) 3921 temp2[i] = temp[10+i] << FNV512shift; 3922 for ( i=0; i0; --i ) 3927 { 3928 temp[i-1] += temp[i] >> 16; 3929 temp[i] &= 0xFFFF; 3930 } 3931 } 3932 for ( i=0; iHash[i] = temp[i]; 3934 return fnvSuccess; 3935 } 3936 return fnvNull; 3937 } /* end FNV512stringin */ 3939 /* return hash (32 bit) 3940 ********************************************************************/ 3941 int FNV512result ( FNV512context *ctx, unsigned char out[16] ) 3942 { 3943 int i; 3945 if ( ctx && out ) 3946 { 3947 if ( ctx->Computed != FNVcomputed+FNV512state ) 3948 return fnvStateError; 3949 for ( i=0; iHash[i]; 3953 out[30-2*i] = ctx->Hash[i] >> 8; 3954 #else 3955 out[2*i] = ctx->Hash[i]; 3956 out[2*i+1] = ctx->Hash[i] >> 8; 3957 #endif 3958 ctx->Hash[i] = 0; 3959 } 3960 ctx->Computed = FNVemptied+FNV512state; 3961 return fnvSuccess; 3962 } 3963 return fnvNull; 3964 } /* end FNV512result */ 3966 #endif /* FNV_64bitIntegers */ 3967 /******************************************************************** 3968 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3969 ********************************************************************/ 3971 #endif /* _FNV512_C_ */ 3972 3974 6.1.6 FNV1024 C Code 3976 The header and C source for 1024-bit FNV-1a returning a byte vector. 3978 3979 /*************************** FNV1024.h **************************/ 3980 /***************** See RFC NNNN for details. ********************/ 3981 /* 3982 * Copyright (c) 2016 IETF Trust and the persons identified as 3983 * authors of the code. All rights reserved. 3984 * See fnv-private.h for terms of use and redistribution. 3985 */ 3987 #ifndef _FNV1024_H_ 3988 #define _FNV1024_H_ 3990 /* 3991 * Description: 3992 * This file provides headers for the 1024-bit version of the 3993 * FNV-1a non-cryptographic hash algorithm. 3994 */ 3996 #include "FNVconfig.h" 3998 #include 3999 #define FNV1024size (1024/8) 4001 /* If you do not have the ISO standard stdint.h header file, then you 4002 * must typedef the following types: 4003 * 4004 * type meaning 4005 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 4006 * uint32_t unsigned 32 bit integer 4007 * uint16_t unsigned 16 bit integer 4008 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 4009 */ 4011 #ifndef _FNV_ErrCodes_ 4012 #define _FNV_ErrCodes_ 4013 /********************************************************************* 4014 * All FNV functions provided return as integer as follows: 4015 * 0 -> success 4016 * >0 -> error as listed below 4017 */ 4018 enum { /* success and errors */ 4019 fnvSuccess = 0, 4020 fnvNull, /* Null pointer parameter */ 4021 fnvStateError, /* called Input after Result or before Init */ 4022 fnvBadParam /* passed a bad parameter */ 4023 }; 4024 #endif /* _FNV_ErrCodes_ */ 4026 /* 4027 * This structure holds context information for an FNV1024 hash 4028 */ 4029 #ifdef FNV_64bitIntegers 4030 /* version if 64 bit integers supported */ 4031 typedef struct FNV1024context_s { 4032 int Computed; /* state */ 4033 uint32_t Hash[FNV1024size/4]; 4034 } FNV1024context; 4036 #else 4037 /* version if 64 bit integers NOT supported */ 4039 typedef struct FNV1024context_s { 4040 int Computed; /* state */ 4041 uint16_t Hash[FNV1024size/2]; 4042 } FNV1024context; 4044 #endif /* FNV_64bitIntegers */ 4046 /* 4047 * Function Prototypes 4048 * FNV1024string: hash a zero terminated string not including 4049 * the terminating zero 4050 * FNV1024block: FNV1024 hash a specified length byte vector 4051 * FNV1024init: initializes an FNV1024 context 4052 * FNV1024initBasis: initializes an FNV1024 context with a 4053 * provided basis 4054 * FNV1024blockin: hash in a specified length byte vector 4055 * FNV1024stringin: hash in a zero terminated string not 4056 * including the zero 4057 * FNV1024result: returns the hash value 4058 * 4059 * Hash is returned as an array of 8-bit integers 4060 */ 4062 #ifdef __cplusplus 4063 extern "C" { 4064 #endif 4066 /* FNV1024 */ 4067 extern int FNV1024string ( const char *in, 4068 unsigned char out[FNV1024size] ); 4069 extern int FNV1024block ( const void *in, 4070 long int length, 4071 unsigned char out[FNV1024size] ); 4072 extern int FNV1024init ( FNV1024context *); 4073 extern int FNV1024initBasis ( FNV1024context * const, 4074 const uint8_t basis[FNV1024size] ); 4075 extern int FNV1024blockin ( FNV1024context *, 4076 const void *in, 4077 long int length ); 4078 extern int FNV1024stringin ( FNV1024context *, 4079 const char *in ); 4080 extern int FNV1024result ( FNV1024context *, 4081 unsigned char out[FNV1024size] ); 4083 #ifdef __cplusplus 4084 } 4085 #endif 4087 #endif /* _FNV1024_H_ */ 4088 4090 4091 /***************************** FNV1024.c ****************************/ 4092 /******************** See RFC NNNN for details *********************/ 4093 /* Copyright (c) 2016, 2017 IETF Trust and the persons identified as 4094 * authors of the code. All rights 4095 * See fnv-private.h for terms of use and redistribution. 4096 */ 4098 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 4099 * hash function FNV-1a for 1024-bit hashes. 4100 */ 4102 #ifndef _FNV1024_C_ 4103 #define _FNV1024_C_ 4105 #include "fnv-private.h" 4106 #include "FNV1024.h" 4108 /* common code for 64 and 32 bit modes */ 4110 /* FNV1024 hash a null terminated string (64/32 bit) 4111 ********************************************************************/ 4112 int FNV1024string ( const char *in, uint8_t out[FNV1024size] ) 4113 { 4114 FNV1024context ctx; 4115 int err; 4117 if ( (err = FNV1024init ( &ctx )) != fnvSuccess) 4118 return err; 4119 if ( (err = FNV1024stringin ( &ctx, in )) != fnvSuccess) 4120 return err; 4121 return FNV1024result ( &ctx, out ); 4122 } /* end FNV1024string */ 4124 /* FNV1024 hash a counted block (64/32 bit) 4125 ********************************************************************/ 4126 int FNV1024block ( const void *in, 4127 long int length, 4128 uint8_t out[FNV1024size] ) 4129 { 4130 FNV1024context ctx; 4131 int err; 4132 if ( (err = FNV1024init ( &ctx )) != fnvSuccess) 4133 return err; 4134 if ( (err = FNV1024blockin ( &ctx, in, length)) != fnvSuccess) 4135 return err; 4136 return FNV1024result ( &ctx, out ); 4137 } /* end FNV1024block */ 4139 /******************************************************************** 4140 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 4141 ********************************************************************/ 4142 #ifdef FNV_64bitIntegers 4144 /* 4145 1024 bit FNV_prime = 2^680 + 2^8 + 0x8d = 4146 0x0000000000000000 0000010000000000 4147 0000000000000000 0000000000000000 4148 0000000000000000 0000000000000000 4149 0000000000000000 0000000000000000 4150 0000000000000000 0000000000000000 4151 0000000000000000 000000000000018D 4152 #define FNV1024primeX 0x018D 4153 #define FNV1024shift 24 4155 /* 0x0000000000000000 005F7A76758ECC4D 4156 32E56D5A591028B7 4B29FC4223FDADA1 4157 6C3BF34EDA3674DA 9A21D90000000000 4158 0000000000000000 0000000000000000 4159 0000000000000000 0000000000000000 4160 0000000000000000 000000000004C6D7 4161 EB6E73802734510A 555F256CC005AE55 4162 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 */ 4164 uint32_t FNV1024basis[FNV1024size/4] = { 4165 0x00000000, 0x00000000, 0x005F7A76, 0x758ECC4D, 4166 0x32E56D5A, 0x591028B7, 0x4B29FC42, 0x23FDADA1, 4167 0x6C3BF34E, 0xDA3674DA, 0x9A21D900, 0x00000000, 4168 0x00000000, 0x00000000, 0x00000000, 0x00000000, 4169 0x00000000, 0x00000000, 0x00000000, 0x00000000, 4170 0x00000000, 0x00000000, 0x00000000, 0x0004C6D7, 4171 0xEB6E7380, 0x2734510A, 0x555F256C, 0xC005AE55, 4172 0x6BDE8CC9, 0xC6A93B21, 0xAFF4B16C, 0x71EE90B3 4173 }; 4175 /******************************************************************** 4176 * Set of init, input, and output functions below * 4177 * to incrementally compute FNV1024 * 4178 ********************************************************************/ 4180 /* initialize context (64 bit) 4181 ********************************************************************/ 4182 int FNV1024init ( FNV1024context *ctx ) 4183 { 4184 if ( ctx ) 4185 { 4186 for ( i=0; iHash[i] = FNV1024basis[i]; 4188 ctx->Computed = FNVinited+FNV1024state; 4189 return fnvSuccess; 4190 } 4191 return fnvNull; 4192 } /* end FNV1024init */ 4194 /* initialize context with a provided basis (64 bit) 4195 ********************************************************************/ 4196 int FNV1024initBasis ( FNV1024context* const ctx, 4197 const uint8_t basis[FNV1024size] ) 4198 { 4199 int i; 4200 uint8_t *ui8p; 4201 uint32_t temp; 4203 if ( ctx ) 4204 { 4205 #ifdef FNV_BigEndian 4206 ui8p = basis; 4207 for ( i=0; i < FNV1024size/4; ++i ) 4208 { 4209 temp = (*ui8p++)<<8; 4210 temp = (temp + *ui8p++)<<8; 4211 temp = (temp + *ui8p++)<<8; 4212 ctx->Hash[i] = temp + *ui8p; 4213 } 4214 #else 4215 ui8p = basis + (FNV1024size/4 - 1); 4216 for ( i=0; i < FNV1024size/4; ++i ) 4217 { 4218 temp = (*ui8p--)<<8; 4219 temp = (temp + *ui8p--)<<8; 4220 temp = (temp + *ui8p--)<<8; 4221 ctx->Hash[i] = temp + *ui8p; 4222 } 4223 #endif 4224 ctx->Computed = FNVinited+FNV1024state; 4225 return fnvSuccess; 4226 } 4227 return fnvNull; 4228 } /* end FNV1024initBasis */ 4230 /* hash in a counted block (64 bit) 4231 ********************************************************************/ 4232 int FNV1024blockin ( FNV1024context *ctx, 4233 const void *vin, 4234 long int length ) 4235 { 4236 const uint8_t *in = (const uint8_t*)vin; 4237 uint64_t temp[FNV1024size/4]; 4238 uint64_t temp2[3]; 4240 if ( ctx && in ) 4241 { 4242 switch ( ctx->Computed ) 4243 { 4244 case FNVinited+FNV1024state: 4245 ctx->Computed = FNVcomputed+FNV128state; 4246 case FNVcomputed+FNV1024state: 4247 break; 4248 default: 4249 return fnvStateError; 4250 } 4251 if ( length < 0 ) 4252 return fnvBadParam; 4253 for ( i=0; iHash[i]; 4255 for ( ; length > 0; length-- ) 4256 { 4257 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 4258 temp[7] ^= *in++; 4259 temp2[2] = temp[7] << FNV1024shift; 4260 temp2[1] = temp[6] << FNV1024shift; 4261 temp2[0] = temp[5] << FNV1024shift; 4262 for ( i=0; i0; --i ) 4268 { 4269 temp[i-1] += temp[i] >> 16; 4270 temp[i] &= 0xFFFF; 4271 } 4272 } 4273 for ( i=0; iHash[i] = temp[i]; 4275 return fnvSuccess; 4276 } 4277 return fnvNull; 4278 } /* end FNV1024input */ 4280 /* hash in a string (64 bit) 4281 ********************************************************************/ 4282 inf FNV1024stringin ( FNV1024context *ctx, const char *in ) 4283 { 4284 uint64_t temp[FNV1024size/4]; 4285 uint64_t temp2[2]; 4286 int i; 4287 uint8_t ch; 4289 if ( ctx && in ) 4290 { 4291 switch ( ctx->Computed ) 4292 { 4293 case FNVinited+FNV1024state: 4294 ctx->Computed = FNVcomputed+FNV1024state; 4295 case FNVcomputed+FNV1024state: 4296 break; 4297 default: 4298 return fnvStateError; 4299 } 4300 for ( i=0; iHash[i]; 4302 while ( ch = (uint8_t)*in++ ) 4303 { 4304 /* temp = FNV1024prime * ( temp ^ ch ); */ 4305 temp[7] ^= ch; 4306 temp2[2] = temp[7] << FNV128shift; 4307 temp2[1] = temp[6] << FNV128shift; 4308 temp2[0] = temp[5] << FNV128shift; 4309 for ( i=0; i0; --i ) 4315 { 4316 temp[i-1] += temp[i] >> 16; 4317 temp[i] &= 0xFFFF; 4318 } 4319 } 4320 for ( i=0; iHash[i] = temp[i]; 4322 return fnvSuccess; 4323 } 4324 return fnvNull; 4325 } /* end FNV1024stringin */ 4327 /* return hash (64 bit) 4328 ********************************************************************/ 4329 int FNV1024result ( FNV1024context *ctx, uint8_t out[FNV1024size] ) 4330 { 4331 if ( ctx && out ) 4332 { 4333 if ( ctx->Computed != FNVcomputed+FNV1024state ) 4334 return fnvStateError; 4335 for ( i=0; iHash[i]; 4339 out[14-2*i] = ctx->Hash[i] >> 8; 4340 #else 4341 out[2*i] = ctx->Hash[i]; 4342 out[2*i+1] = ctx->Hash[i] >> 8; 4343 #endif 4344 ctx -> Hash[i] = 0; 4345 } 4346 ctx->Computed = FNVemptied+FNV1024state; 4347 return fnvSuccess; 4348 } 4349 return fnvNull; 4350 } /* end FNV1024result */ 4352 /****************************************************************** 4353 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 4354 ******************************************************************/ 4355 #else /* FNV_64bitIntegers */ 4356 /****************************************************************** 4357 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 4358 ******************************************************************/ 4360 /* version for when you only have 32-bit arithmetic 4361 ********************************************************************/ 4363 /* 4364 1024 bit FNV_prime = 2^680 + 2^8 + 0x8d = 4365 0x0000000000000000 0000010000000000 4366 0000000000000000 0000000000000000 4367 0000000000000000 0000000000000000 4368 0000000000000000 0000000000000000 4369 0000000000000000 0000000000000000 4370 0000000000000000 000000000000018D */ 4371 #define FNV1024primeX 0x018D 4372 #define FNV1024shift 8 4374 /* 0x0000000000000000 005F7A76758ECC4D 4375 32E56D5A591028B7 4B29FC4223FDADA1 4376 6C3BF34EDA3674DA 9A21D90000000000 4377 0000000000000000 0000000000000000 4378 0000000000000000 0000000000000000 4379 0000000000000000 000000000004C6D7 4380 EB6E73802734510A 555F256CC005AE55 4381 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 */ 4383 uint16_t FNV1024basis[FNV1024size/2] = { 4384 0x0000, 0x0000, 0x0000, 0x0000, 0x005F, 0x7A76, 0x758E, 0xCC4D, 4385 0x32E5, 0x6D5A, 0x5910, 0x28B7, 0x4B29, 0xFC42, 0x23FD, 0xADA1, 4386 0x6C3B, 0xF34E, 0xDA36, 0x74DA, 0x9A21, 0xD900, 0x0000, 0x0000, 4387 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 4388 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 4389 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0004, 0xC6D7, 4390 0xEB6E, 0x7380, 0x2734, 0x510A, 0x555F, 0x256C, 0xC005, 0xAE55, 4391 0x6BDE, 0x8CC9, 0xC6A9, 0x3B21, 0xAFF4, 0xB16C, 0x71EE, 0x90B3 4392 }; 4394 /******************************************************************** 4395 * Set of init, input, and output functions below * 4396 * to incrementally compute FNV1024 * 4397 ********************************************************************/ 4399 /* initialize context (32 bit) 4400 ********************************************************************/ 4401 int FNV1024init ( FNV1024context *ctx ) 4402 { 4403 int i; 4405 if ( ctx ) 4406 { 4407 for ( i=0; iHash[i] = FNV1024basis[i]; 4409 ctx->Computed = FNVinited+FNV1024state; 4410 return fnvSuccess; 4411 } 4412 return fnvNull; 4413 } /* end FNV1024init */ 4415 /* initialize context with a provided basis (32 bit) 4416 ********************************************************************/ 4417 int FNV1024initBasis ( FNV1024context *ctx, 4418 const uint8_t basis[FNV1024size] ) 4419 { 4420 int i; 4421 const uint8_t *ui8p; 4422 uint32_t temp; 4424 if ( ctx ) 4425 { 4426 #ifdef FNV_BigEndian 4427 ui8p = basis; 4428 for ( i=0; i < FNV1024size/2; ++i ) 4429 { 4430 temp = *ui8p++; 4431 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 4432 } 4433 #else 4434 ui8p = basis + ( FNV1024size/2 - 1 ); 4435 for ( i=0; i < FNV1024size/2; ++i ) 4436 { 4437 temp = *ui8p--; 4438 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 4439 } 4440 #endif 4441 ctx->Computed = FNVinited+FNV1024state; 4442 return fnvSuccess; 4443 } 4444 return fnvNull; 4445 } /* end FNV1024initBasis */ 4447 /* hash in a counted block (32 bit) 4448 *******************************************************************/ 4449 int FNV1024blockin ( FNV1024context *ctx, 4450 const void *vin, 4451 long int length ) 4452 { 4453 const uint8_t *in = (const uint8_t*)vin; 4454 uint32_t temp[FNV1024size/2]; 4455 uint32_t temp2[6]; 4456 int i; 4458 if ( ctx && in ) 4459 { 4460 switch ( ctx->Computed ) 4461 { 4462 case FNVinited+FNV1024state: 4463 ctx->Computed = FNVcomputed+FNV1024state; 4464 case FNVcomputed+FNV1024state: 4465 break; 4466 default: 4467 return fnvStateError; 4468 } 4469 if ( length < 0 ) 4470 return fnvBadParam; 4471 for ( i=0; iHash[i]; 4473 for ( ; length > 0; length-- ) 4474 { 4475 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 4476 temp[15] ^= *in++; 4477 for ( i=0; i<6; ++i ) 4478 temp2[i] = temp[10+i] << FNV1024shift; 4479 for ( i=0; i0; --i ) 4484 { 4485 temp[i-1] += temp[i] >> 16; 4486 temp[i] &= 0xFFFF; 4487 } 4488 } 4489 for ( i=0; iHash[i] = temp[i]; 4491 return fnvSuccess; 4492 } 4493 return fnvNull; 4494 } /* end FNV1024blockin */ 4496 /* hash in a string (32 bit) 4497 *******************************************************************/ 4498 int FNV1024stringin ( FNV1024context *ctx, const char *in ) 4499 { 4500 uint32_t temp[FNV1024size/2]; 4501 uint32_t temp2[6]; 4502 int i; 4503 uint8_t ch; 4505 if ( ctx && in ) 4506 { 4507 switch ( ctx->Computed ) 4508 { 4509 case FNVinited+FNV1024state: 4510 ctx->Computed = FNVcomputed+FNV1024state; 4511 case FNVcomputed+FNV1024state: 4512 break; 4513 default: 4514 return fnvStateError; 4515 } 4516 for ( i=0; iHash[i]; 4518 while ( (ch = (uint8_t)*in++) ) 4519 { 4520 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 4521 temp[15] ^= ch; 4522 for ( i=0; i<6; ++i ) 4523 temp2[i] = temp[10+i] << FNV1024shift; 4524 for ( i=0; i0; --i ) 4529 { 4530 temp[i-1] += temp[i] >> 16; 4531 temp[i] &= 0xFFFF; 4532 } 4533 } 4534 for ( i=0; iHash[i] = temp[i]; 4536 return fnvSuccess; 4537 } 4538 return fnvNull; 4539 } /* end FNV1024stringin */ 4541 /* return hash (32 bit) 4542 ********************************************************************/ 4543 int FNV1024result ( FNV1024context *ctx, unsigned char out[16] ) 4544 { 4545 int i; 4547 if ( ctx && out ) 4548 { 4549 if ( ctx->Computed != FNVcomputed+FNV1024state ) 4550 return fnvStateError; 4551 for ( i=0; iHash[i]; 4555 out[30-2*i] = ctx->Hash[i] >> 8; 4556 #else 4557 out[2*i] = ctx->Hash[i]; 4558 out[2*i+1] = ctx->Hash[i] >> 8; 4559 #endif 4560 ctx->Hash[i] = 0; 4561 } 4562 ctx->Computed = FNVemptied+FNV1024state; 4563 return fnvSuccess; 4564 } 4565 return fnvNull; 4566 } /* end FNV1024result */ 4568 #endif /* FNV_64bitIntegers */ 4569 /******************************************************************** 4570 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 4571 ********************************************************************/ 4573 #endif /* _FNV1024_C_ */ 4574 4576 6.2 FNV Test Code 4578 Here is a test driver: 4580 4581 /**************************** MAIN.c ****************************/ 4582 /****************** See RFC NNNN for details. *******************/ 4583 /* 4584 * Copyright (c) 2016 IETF Trust and the persons identified as 4585 * authors of the code. All rights reserved. 4586 * See fnv-private.h for terms of use and redistribution. 4587 */ 4588 /* to do a thorough test you need to run will all four 4589 combinations of the following defined/undefined */ 4591 // #define FNV_64bitIntegers 4592 // #define FNV_BigEndian 4594 #include 4595 #include 4597 #include "fnv-private.h" 4598 #include "FNV.h" 4600 /* global variables */ 4601 char *funcName; 4602 char *errteststring = "foo"; 4603 int Terr; /* Total errors */ 4604 #define NTestBytes 3 4605 uint8_t errtestbytes[NTestBytes] = { (uint8_t)1, 4606 (uint8_t)2, (uint8_t)3 }; 4608 #define NTstrings 3 4609 char *teststring[NTstrings] = { "", "a", "foobar" }; 4611 /***************************************************************** 4612 * local prototypes 4613 *****************************************************************/ 4614 int TestR ( char *, int should, int was ); 4615 void TestNValue ( char *subfunc, 4616 char *string, 4617 int N, 4618 uint8_t *should, 4619 uint8_t *was ); 4620 void HexPrint ( int i, unsigned char *p ); 4621 void Test32 (); 4622 void Test32Value ( char *subfunc, char *string, 4623 uint32_t was, uint32_t should ); 4624 void Test64 (); 4625 #ifdef FNV_64bitIntegers 4626 void Test64Value ( char *subfunc, char *string, 4627 uint64_t should, uint64_t was ); 4628 #else 4629 #define uint64_t foobar 4630 #endif /* FNB_64bitIntegers */ 4631 void Test128 (); 4632 void Test256 (); 4633 void Test512 (); 4634 void Test1024 (); 4636 void TestNValue ( char *subfunc, 4637 char *string, 4638 int N, 4639 uint8_t was[N], 4640 uint8_t should[N] ); 4642 /***************************************************************** 4643 * main 4644 *****************************************************************/ 4645 int main (int argc, const char * argv[]) 4646 { 4647 #ifdef FNV_64bitIntegers 4648 printf ("Have 64-bit Integers. "); 4649 #else 4650 printf ("Do not have 64-bit integers. "); 4651 #endif 4652 #ifdef FNV_BigEndian 4653 printf ("Calculating for Big Endian.0); 4654 #else 4655 printf ("Not calculating for Big Endian.0); 4656 #endif 4657 funcName = "Testing TestR "; 4658 /* test the Test Return function */ 4659 TestR ( "should fail", 1, 2 ); 4660 TestR ( "should not have failed", 0, 0 ); 4662 Test32(); 4663 Test64(); 4664 Test128(); 4665 Test256(); 4666 Test512(); 4667 Test1024(); 4669 printf ("Type return to exit.0); 4670 (void)getchar(); 4671 printf ("Goodbye!0); 4673 return 0; 4674 } /* end main */ 4675 /* Test status returns 4676 *****************************************************************/ 4677 int TestR ( char *name, int expect, int actual ) 4678 { 4679 if ( expect != actual ) 4680 { 4681 printf ( "%s%s returned %i instead of %i.0, 4682 funcName, name, actual, expect ); 4683 ++Terr; 4684 } 4685 return actual; 4686 } /* end TestR */ 4688 /* Return true if the bytes are in reverse order from each other */ 4689 int revcmp(uint8_t *buf1, uint8_t *buf2, int N) { 4690 int i; 4691 uint8_t *bufc = buf2 + N; 4692 for ( i = 0; i < N / 2; i++ ) 4693 if (*buf1++ != *--bufc) 4694 return 0; 4695 return 1; 4696 } 4698 /* General byte vector return error test 4699 *****************************************************************/ 4700 void TestNValue ( char *subfunc, 4701 char *string, 4702 int N, 4703 uint8_t *was, 4704 uint8_t *should ) 4705 { 4706 #ifdef FNV_BigEndian 4707 if ( revcmp ( was, should, N) == 0) 4708 #else 4709 if ( memcmp ( was, should, N) != 0) 4710 #endif 4711 { 4712 printf ( "%s %s of '%s' computed ", funcName, subfunc, string ); 4713 HexPrint ( N, was ); 4714 printf ( ", should have been " ); 4715 HexPrint ( N, should ); 4716 printf ( ".0 ); 4717 ++Terr; 4718 } 4719 } /* end TestNValue */ 4721 /* print some hex 4722 *****************************************************************/ 4723 void HexPrint ( int count, unsigned char *ptr ) 4724 { 4725 int i; 4727 for ( i = 0; i < count; ++i ) 4728 printf ( "%02X", ptr[i] ); 4729 } /* end HexPrint */ 4731 /***************************************************************** 4732 * FNV32 test 4733 *****************************************************************/ 4734 void Test32 () 4735 { 4736 int i, err; 4737 long int iLen; 4738 uint32_t eUint32; 4739 FNV32context eContext; 4740 uint32_t FNV32svalues[NTstrings] = { 4741 0x811c9dc5, 0xe40c292c, 0xbf9cf968 }; 4742 uint32_t FNV32bvalues[NTstrings] = { 4743 0x050c5d1f, 0x2b24d044, 0x0c1c9eb8 }; 4745 /* test Test32Value */ 4746 funcName = "Test32Value"; 4747 Test32Value ( "should fail", "test", FNV32svalues[1], FNV32svalues[2] ); 4749 funcName = "FNV32"; 4751 /* test error checks */ 4752 Terr = 0; 4753 TestR ( "init", fnvSuccess, FNV32init (&eContext) ); 4754 TestR ( "string", fnvNull, 4755 FNV32string ( (char *)0, &eUint32 ) ); 4756 TestR ( "string", fnvNull, 4757 FNV32string ( errteststring, (uint32_t *)0 ) ); 4758 TestR ( "block", fnvNull, 4759 FNV32block ( (uint8_t *)0, 1, &eUint32 ) ); 4760 TestR ( "block", fnvBadParam, 4761 FNV32block ( errtestbytes, -1, &eUint32 ) ); 4762 TestR ( "block", fnvNull, 4763 FNV32block ( errtestbytes, 1, (uint32_t *)0 ) ); 4764 TestR ( "init", fnvNull, 4765 FNV32init ( (FNV32context *)0 ) ); 4766 TestR ( "initBasis", fnvNull, 4767 FNV32initBasis ( (FNV32context *)0, 42 ) ); 4768 TestR ( "blockin", fnvNull, 4769 FNV32blockin ( (FNV32context *)0, 4770 errtestbytes, NTestBytes ) ); 4771 TestR ( "blockin", fnvNull, 4772 FNV32blockin ( &eContext, (uint8_t *)0, 4773 NTestBytes ) ); 4775 TestR ( "blockin", fnvBadParam, 4776 FNV32blockin ( &eContext, errtestbytes, -1 ) ); 4777 eContext.Computed = FNVclobber+FNV32state; 4778 TestR ( "blockin", fnvStateError, 4779 FNV32blockin ( &eContext, errtestbytes, 4780 NTestBytes ) ); 4781 TestR ( "stringin", fnvNull, 4782 FNV32stringin ( (FNV32context *)0, errteststring ) ); 4783 TestR ( "stringin", fnvNull, 4784 FNV32stringin ( &eContext, (char *)0 ) ); 4785 TestR ( "stringin", fnvStateError, 4786 FNV32stringin ( &eContext, errteststring ) ); 4787 TestR ( "result", fnvNull, 4788 FNV32result ( (FNV32context *)0, &eUint32 ) ); 4789 TestR ( "result", fnvNull, 4790 FNV32result ( &eContext, (uint32_t *)0 ) ); 4791 TestR ( "result", fnvStateError, 4792 FNV32result ( &eContext, &eUint32 ) ); 4793 if ( Terr ) 4794 printf ( "%s test of error checks failed %i times.0, 4795 funcName, Terr ); 4796 else 4797 printf ( "%s test of error checks passed0, funcName ); 4799 /* test actual results */ 4800 Terr = 0; 4801 for ( i = 0; i < NTstrings; ++i ) 4802 { 4803 err = TestR ( "string", fnvSuccess, 4804 FNV32string ( teststring[i], &eUint32 ) ); 4805 if ( err == fnvSuccess ) 4806 Test32Value ( "string", teststring[i], eUint32, 4807 FNV32svalues[i] ); 4808 err = TestR ( "block", fnvSuccess, 4809 FNV32block ( (uint8_t *)teststring[i], 4810 (unsigned long)(strlen(teststring[i])+1), 4811 &eUint32 ) ); 4812 if ( err == fnvSuccess ) 4813 Test32Value ( "block", teststring[i], eUint32, 4814 FNV32bvalues[i] ); 4815 /* now try testing the incremental stuff */ 4816 err = TestR ( "init", fnvSuccess, FNV32init ( &eContext ) ); 4817 if ( err ) break; 4818 iLen = strlen ( teststring[i] ); 4819 err = TestR ( "blockin", fnvSuccess, 4820 FNV32blockin ( &eContext, 4821 (uint8_t *)teststring[i], 4822 iLen/2 ) ); 4823 if ( err ) break; 4824 err = TestR ( "stringin", fnvSuccess, 4825 FNV32stringin ( &eContext, 4826 teststring[i] + iLen/2 ) ); 4827 err = TestR ( "result", fnvSuccess, 4828 FNV32result ( &eContext, &eUint32 ) ); 4829 if ( err ) break; 4830 Test32Value ( " incremental", teststring[i], eUint32, 4831 FNV32svalues[i] ); 4832 } 4833 if ( Terr ) 4834 printf ( "%s test of return values failed %i times.0, 4835 funcName, Terr ); 4836 else 4837 printf ( "%s test of return values passed.0, funcName ); 4838 } /* end Test32 */ 4840 /* start Test32Value 4841 *****************************************************************/ 4842 void Test32Value ( char *subfunc, 4843 char *string, 4844 uint32_t was, 4845 uint32_t should ) 4846 { 4847 TestNValue(subfunc, string, sizeof(uint32_t), (uint8_t*)&was, 4848 (uint8_t*)&should); 4849 } /* end Test32Value */ 4851 #ifdef FNV_64bitIntegers 4852 /***************************************************************** 4853 * Code for FNV64 using 64-bit integers 4854 *****************************************************************/ 4856 void Test64 () 4857 { 4858 int i, err; 4859 uint64_t eUint64 = 42; 4860 FNV64context eContext; 4861 uint64_t FNV64svalues[NTstrings] = { 4862 0xcbf29ce484222325, 0xaf63dc4c8601ec8c, 0x85944171f73967e8 }; 4863 uint64_t FNV64bvalues[NTstrings] = { 4864 0xaf63bd4c8601b7df, 0x089be207b544f1e4, 0x34531ca7168b8f38 }; 4866 funcName = "FNV64"; 4868 /* test error checks */ 4869 Terr = 0; 4870 TestR ( "init", fnvSuccess, FNV64init (&eContext) ); 4871 TestR ( "string", fnvNull, 4872 FNV64string ( (char *)0, &eUint64 ) ); 4873 TestR ( "string", fnvNull, 4874 FNV64string ( errteststring, (uint64_t *)0 ) ); 4875 TestR ( "block", fnvNull, 4876 FNV64block ( (uint8_t *)0, 1, &eUint64 ) ); 4877 TestR ( "block", fnvBadParam, 4878 FNV64block ( errtestbytes, -1, &eUint64 ) ); 4879 TestR ( "block", fnvNull, 4880 FNV64block ( errtestbytes, 1, (uint64_t *)0 ) ); 4881 TestR ( "init", fnvNull, 4882 FNV64init ( (FNV64context *)0 ) ); 4883 TestR ( "initBasis", fnvNull, 4884 FNV64initBasis ( (FNV64context *)0, 42 ) ); 4885 TestR ( "blockin", fnvNull, 4886 FNV64blockin ( (FNV64context *)0, 4887 errtestbytes, NTestBytes ) ); 4888 TestR ( "blockin", fnvNull, 4889 FNV64blockin ( &eContext, (uint8_t *)0, 4890 NTestBytes ) ); 4891 TestR ( "blockin", fnvBadParam, 4892 FNV64blockin ( &eContext, errtestbytes, -1 ) ); 4893 eContext.Computed = FNVclobber+FNV64state; 4894 TestR ( "blockin", fnvStateError, 4895 FNV64blockin ( &eContext, errtestbytes, 4896 NTestBytes ) ); 4897 TestR ( "stringin", fnvNull, 4898 FNV64stringin ( (FNV64context *)0, errteststring ) ); 4899 TestR ( "stringin", fnvNull, 4900 FNV64stringin ( &eContext, (char *)0 ) ); 4901 TestR ( "stringin", fnvStateError, 4902 FNV64stringin ( &eContext, errteststring ) ); 4903 TestR ( "result", fnvNull, 4904 FNV64result ( (FNV64context *)0, &eUint64 ) ); 4905 TestR ( "result", fnvNull, 4906 FNV64result ( &eContext, (uint64_t *)0 ) ); 4907 TestR ( "result", fnvStateError, 4908 FNV64result ( &eContext, &eUint64 ) ); 4909 if ( Terr ) 4910 printf ( "%s test of error checks failed %i times.0, 4911 funcName, Terr ); 4912 else 4913 printf ( "%s test of error checks passed0, funcName ); 4915 /* test actual results */ 4916 Terr = 0; 4917 for ( i = 0; i < NTstrings; ++i ) 4918 { 4919 err = TestR ( "string", fnvSuccess, 4920 FNV64string ( teststring[i], &eUint64 ) ); 4921 if ( err == fnvSuccess ) 4922 Test64Value ( "string", teststring[i], eUint64, 4923 FNV64svalues[i] ); 4925 err = TestR ( "block", fnvSuccess, 4926 FNV64block ( (uint8_t *)teststring[i], 4927 (unsigned long)(strlen(teststring[i])+1), 4928 &eUint64 ) ); 4929 if ( err == fnvSuccess ) 4930 Test64Value ( "block", teststring[i], eUint64, 4931 FNV64bvalues[i] ); 4932 /* now try testing the incremental stuff */ 4933 err = TestR ( "init", fnvSuccess, FNV64init ( &eContext ) ); 4935 } 4936 if ( Terr ) 4937 printf ( "%s test of return values failed %i times.0, 4938 funcName, Terr ); 4939 else 4940 printf ( "%s test of return values passed.0, funcName ); 4941 } /* end Test64 */ 4943 /* start Test64Value 4944 *****************************************************************/ 4945 void Test64Value ( char *subfunc, 4946 char *string, 4947 uint64_t should, 4948 uint64_t was ) 4949 { 4950 TestNValue(subfunc, string, sizeof(uint64_t), (uint8_t*)&was, 4951 . (uint8_t*)&should); 4952 } /* end Test64Value */ 4953 #else 4954 void Test64 () 4955 { 4956 /* TBD */ 4957 } 4958 #endif /* FNV_64bitIntegers */ 4960 /***************************************************************** 4961 * Code for FNV128 using 64-bit integers 4962 *****************************************************************/ 4964 void Test128 () 4965 { 4966 //int i, err; 4967 uint8_t eUint128[FNV128size]; 4968 FNV128context eContext; 4970 funcName = "FNV128"; 4972 /* test error checks */ 4973 Terr = 0; 4974 TestR ( "init", fnvSuccess, FNV128init (&eContext) ); 4975 TestR ( "string", fnvNull, 4976 FNV128string ( (char *)0, eUint128 ) ); 4977 TestR ( "string", fnvNull, 4978 FNV128string ( errteststring, (uint8_t *)0 ) ); 4979 TestR ( "block", fnvNull, 4980 FNV128block ( (uint8_t *)0, 1, eUint128 ) ); 4981 TestR ( "block", fnvBadParam, 4982 FNV128block ( errtestbytes, -1, eUint128 ) ); 4983 TestR ( "block", fnvNull, 4984 FNV128block ( errtestbytes, 1, (uint8_t *)0 ) ); 4985 TestR ( "init", fnvNull, 4986 FNV128init ( (FNV128context *)0 ) ); 4987 TestR ( "initBasis", fnvNull, 4988 FNV128initBasis ( (FNV128context *)0, eUint128 ) ); 4989 TestR ( "blockin", fnvNull, 4990 FNV128blockin ( (FNV128context *)0, 4991 errtestbytes, NTestBytes ) ); 4992 TestR ( "blockin", fnvNull, 4993 FNV128blockin ( &eContext, (uint8_t *)0, 4994 NTestBytes ) ); 4995 TestR ( "blockin", fnvBadParam, 4996 FNV128blockin ( &eContext, errtestbytes, -1 ) ); 4997 eContext.Computed = FNVclobber+FNV128state; 4998 TestR ( "blockin", fnvStateError, 4999 FNV128blockin ( &eContext, errtestbytes, 5000 NTestBytes ) ); 5001 TestR ( "stringin", fnvNull, 5002 FNV128stringin ( (FNV128context *)0, errteststring ) ); 5003 TestR ( "stringin", fnvNull, 5004 FNV128stringin ( &eContext, (char *)0 ) ); 5005 TestR ( "stringin", fnvStateError, 5006 FNV128stringin ( &eContext, errteststring ) ); 5007 TestR ( "result", fnvNull, 5008 FNV128result ( (FNV128context *)0, eUint128 ) ); 5009 TestR ( "result", fnvNull, 5010 FNV128result ( &eContext, (uint8_t *)0 ) ); 5011 TestR ( "result", fnvStateError, 5012 FNV128result ( &eContext, eUint128 ) ); 5013 if ( Terr ) 5014 printf ( "%s test of error checks failed %i times.0, 5015 funcName, Terr ); 5016 else 5017 printf ( "%s test of error checks passed0, funcName ); 5019 /* test actual results */ 5020 Terr = 0; 5021 /* tbd */ 5022 } /* end Test128 */ 5023 /***************************************************************** 5024 * Code for FNV256 using 64-bit integers 5025 *****************************************************************/ 5027 void Test256 () 5028 { 5029 //int i, err; 5030 uint8_t eUint256[FNV256size]; 5031 FNV256context eContext; 5033 funcName = "FNV256"; 5035 /* test error checks */ 5036 Terr = 0; 5037 TestR ( "init", fnvSuccess, FNV256init (&eContext) ); 5038 TestR ( "string", fnvNull, 5039 FNV256string ( (char *)0, eUint256 ) ); 5040 TestR ( "string", fnvNull, 5041 FNV256string ( errteststring, (uint8_t *)0 ) ); 5042 TestR ( "block", fnvNull, 5043 FNV256block ( (uint8_t *)0, 1, eUint256 ) ); 5044 TestR ( "block", fnvBadParam, 5045 FNV256block ( errtestbytes, -1, eUint256 ) ); 5046 TestR ( "block", fnvNull, 5047 FNV256block ( errtestbytes, 1, (uint8_t *)0 ) ); 5048 TestR ( "init", fnvNull, 5049 FNV256init ( (FNV256context *)0 ) ); 5050 TestR ( "initBasis", fnvNull, 5051 FNV256initBasis ( (FNV256context *)0, eUint256 ) ); 5052 TestR ( "blockin", fnvNull, 5053 FNV256blockin ( (FNV256context *)0, 5054 errtestbytes, NTestBytes ) ); 5055 TestR ( "blockin", fnvNull, 5056 FNV256blockin ( &eContext, (uint8_t *)0, 5057 NTestBytes ) ); 5058 TestR ( "blockin", fnvBadParam, 5059 FNV256blockin ( &eContext, errtestbytes, -1 ) ); 5060 eContext.Computed = FNVclobber+FNV256state; 5061 TestR ( "blockin", fnvStateError, 5062 FNV256blockin ( &eContext, errtestbytes, 5063 NTestBytes ) ); 5064 TestR ( "stringin", fnvNull, 5065 FNV256stringin ( (FNV256context *)0, errteststring ) ); 5066 TestR ( "stringin", fnvNull, 5067 FNV256stringin ( &eContext, (char *)0 ) ); 5068 TestR ( "stringin", fnvStateError, 5069 FNV256stringin ( &eContext, errteststring ) ); 5070 TestR ( "result", fnvNull, 5071 FNV256result ( (FNV256context *)0, eUint256 ) ); 5072 TestR ( "result", fnvNull, 5073 FNV256result ( &eContext, (uint8_t *)0 ) ); 5074 TestR ( "result", fnvStateError, 5075 FNV256result ( &eContext, eUint256 ) ); 5076 if ( Terr ) 5077 printf ( "%s test of error checks failed %i times.0, 5078 funcName, Terr ); 5079 else 5080 printf ( "%s test of error checks passed0, funcName ); 5082 /* test actual results */ 5083 Terr = 0; 5084 /* tbd */ 5085 } /* end Test256 */ 5087 /***************************************************************** 5088 * Code for FNV512 using 64-bit integers 5089 *****************************************************************/ 5091 void Test512 () 5092 { 5093 //int i, err; 5094 uint8_t eUint512[FNV512size]; 5095 FNV512context eContext; 5097 funcName = "FNV512"; 5099 /* test error checks */ 5100 Terr = 0; 5101 TestR ( "init", fnvSuccess, FNV512init (&eContext) ); 5102 TestR ( "string", fnvNull, 5103 FNV512string ( (char *)0, eUint512 ) ); 5104 TestR ( "string", fnvNull, 5105 FNV512string ( errteststring, (uint8_t *)0 ) ); 5106 TestR ( "block", fnvNull, 5107 FNV512block ( (uint8_t *)0, 1, eUint512 ) ); 5108 TestR ( "block", fnvBadParam, 5109 FNV512block ( errtestbytes, -1, eUint512 ) ); 5110 TestR ( "block", fnvNull, 5111 FNV512block ( errtestbytes, 1, (uint8_t *)0 ) ); 5112 TestR ( "init", fnvNull, 5113 FNV512init ( (FNV512context *)0 ) ); 5114 TestR ( "initBasis", fnvNull, 5115 FNV512initBasis ( (FNV512context *)0, eUint512 ) ); 5116 TestR ( "blockin", fnvNull, 5117 FNV512blockin ( (FNV512context *)0, 5118 errtestbytes, NTestBytes ) ); 5119 TestR ( "blockin", fnvNull, 5120 FNV512blockin ( &eContext, (uint8_t *)0, 5121 NTestBytes ) ); 5123 TestR ( "blockin", fnvBadParam, 5124 FNV512blockin ( &eContext, errtestbytes, -1 ) ); 5125 eContext.Computed = FNVclobber+FNV512state; 5126 TestR ( "blockin", fnvStateError, 5127 FNV512blockin ( &eContext, errtestbytes, 5128 NTestBytes ) ); 5129 TestR ( "stringin", fnvNull, 5130 FNV512stringin ( (FNV512context *)0, errteststring ) ); 5131 TestR ( "stringin", fnvNull, 5132 FNV512stringin ( &eContext, (char *)0 ) ); 5133 TestR ( "stringin", fnvStateError, 5134 FNV512stringin ( &eContext, errteststring ) ); 5135 TestR ( "result", fnvNull, 5136 FNV512result ( (FNV512context *)0, eUint512 ) ); 5137 TestR ( "result", fnvNull, 5138 FNV512result ( &eContext, (uint8_t *)0 ) ); 5139 TestR ( "result", fnvStateError, 5140 FNV512result ( &eContext, eUint512 ) ); 5141 if ( Terr ) 5142 printf ( "%s test of error checks failed %i times.0, 5143 funcName, Terr ); 5144 else 5145 printf ( "%s test of error checks passed0, funcName ); 5147 /* test actual results */ 5148 Terr = 0; 5149 /* tbd */ 5150 } /* end Test512 */ 5152 /***************************************************************** 5153 * Code for FNV1024 using 64-bit integers 5154 *****************************************************************/ 5156 void Test1024 () 5157 { 5158 //int i, err; 5159 uint8_t eUint1024[FNV1024size]; 5160 FNV1024context eContext; 5162 funcName = "FNV1024"; 5164 /* test error checks */ 5165 Terr = 0; 5166 TestR ( "init", fnvSuccess, FNV1024init (&eContext) ); 5167 TestR ( "string", fnvNull, 5168 FNV1024string ( (char *)0, eUint1024 ) ); 5169 TestR ( "string", fnvNull, 5170 FNV1024string ( errteststring, (uint8_t *)0 ) ); 5171 TestR ( "block", fnvNull, 5172 FNV1024block ( (uint8_t *)0, 1, eUint1024 ) ); 5173 TestR ( "block", fnvBadParam, 5174 FNV1024block ( errtestbytes, -1, eUint1024 ) ); 5175 TestR ( "block", fnvNull, 5176 FNV1024block ( errtestbytes, 1, (uint8_t *)0 ) ); 5177 TestR ( "init", fnvNull, 5178 FNV1024init ( (FNV1024context *)0 ) ); 5179 TestR ( "initBasis", fnvNull, 5180 FNV1024initBasis ( (FNV1024context *)0, eUint1024 ) ); 5181 TestR ( "blockin", fnvNull, 5182 FNV1024blockin ( (FNV1024context *)0, 5183 errtestbytes, NTestBytes ) ); 5184 TestR ( "blockin", fnvNull, 5185 FNV1024blockin ( &eContext, (uint8_t *)0, 5186 NTestBytes ) ); 5187 TestR ( "blockin", fnvBadParam, 5188 FNV1024blockin ( &eContext, errtestbytes, -1 ) ); 5189 eContext.Computed = FNVclobber+FNV1024state; 5190 TestR ( "blockin", fnvStateError, 5191 FNV1024blockin ( &eContext, errtestbytes, 5192 NTestBytes ) ); 5193 TestR ( "stringin", fnvNull, 5194 FNV1024stringin ( (FNV1024context *)0, errteststring ) ); 5195 TestR ( "stringin", fnvNull, 5196 FNV1024stringin ( &eContext, (char *)0 ) ); 5197 TestR ( "stringin", fnvStateError, 5198 FNV1024stringin ( &eContext, errteststring ) ); 5199 TestR ( "result", fnvNull, 5200 FNV1024result ( (FNV1024context *)0, eUint1024 ) ); 5201 TestR ( "result", fnvNull, 5202 FNV1024result ( &eContext, (uint8_t *)0 ) ); 5203 TestR ( "result", fnvStateError, 5204 FNV1024result ( &eContext, eUint1024 ) ); 5205 if ( Terr ) 5206 printf ( "%s test of error checks failed %i times.0, 5207 funcName, Terr ); 5208 else 5209 printf ( "%s test of error checks passed0, funcName ); 5211 /* test actual results */ 5212 Terr = 0; 5213 /* tbd */ 5214 } /* end Test1024 */ 5215 5217 7. Security Considerations 5219 This document is intended to provide convenient open source access by 5220 the Internet community to the FNV non-cryptographic hash. No 5221 assertion of suitability for cryptographic applications is made for 5222 the FNV hash algorithms. 5224 7.1 Why is FNV Non-Cryptographic? 5226 A full discussion of cryptographic hash requirements and strength is 5227 beyond the scope of this document. However, here are three 5228 characteristics of FNV that would generally be considered to make it 5229 non-cryptographic: 5231 1. Sticky State - A cryptographic hash should not have a state in 5232 which it can stick for a plausible input pattern. But, in the very 5233 unlikely event that the FNV hash variable becomes zero and the 5234 input is a sequence of zeros, the hash variable will remain at 5235 zero until there is a non-zero input byte and the final hash value 5236 will be unaffected by the length of that sequence of zero input 5237 bytes. Of course, for the common case of fixed length input, this 5238 would usually not be significant because the number of non-zero 5239 bytes would vary inversely with the number of zero bytes and for 5240 some types of input, runs of zeros do not occur. Furthermore, the 5241 inclusion of even a little unpredictable input may be sufficient 5242 to stop an adversary from inducing a zero hash variable. 5244 2. Diffusion - Every output bit of a cryptographic hash should be an 5245 equally complex function of every input bit. But it is easy to see 5246 that the least significant bit of a direct FNV hash is the XOR of 5247 the least significant bits of every input byte and does not depend 5248 on any other input bit. While more complex, the second through 5249 seventh least significant bits of an FNV hash have a similar 5250 weakness; only the top bit of the bottom byte of output, and 5251 higher order bits, depend on all input bits. If these properties 5252 are considered a problem, they can be easily fixed by XOR folding 5253 (see Section 3). 5255 3. Work Factor - Depending on intended use, it is frequently 5256 desirable that a hash function should be computationally expensive 5257 for general purpose and graphics processors since these may be 5258 profusely available through elastic cloud services or botnets. 5259 This is to slow down testing of possible inputs if the output is 5260 known. But FNV is designed to be very inexpensive on a general- 5261 purpose processor. (See Appendix A.) 5263 Nevertheless, none of the above have proven to be a problem in actual 5264 practice for the many applications of FNV. 5266 7.2 Inducing Collisions 5268 While use of a cryptographic hash should be considered when active 5269 adversaries are a factor, the following attack can be made much more 5270 difficult with very minor changes in the use of FNV. 5272 If FNV is being used in a known way for hash tables in a network 5273 server or the like, for example some part of a web server, an 5274 adversary could send requests calculated to cause hash table 5275 collisions and induce substantial processing delays. As mentioned in 5276 Section 2.2, use of an offset_basis not knownable by the adversary 5277 will substantially eliminate this problem. 5279 8. IANA Considerations 5281 This document requires no IANA Actions. RFC Ediotor: Please delete 5282 this section before publication. 5284 Normative References 5286 [RFC20] - Cerf, V., "ASCII format for network interchange", STD 80, 5287 RFC 20, October 1969, . 5289 Informative References 5291 [FNV] - FNV web site: 5292 http://www.isthe.com/chongo/tech/comp/fnv/index.html 5294 [IEEE] - http://www.ieee.org 5296 [IPv6flow] - https://researchspace.auckland.ac.nz/bitstream/handle/ 5297 2292/13240/flowhashRep.pdf 5299 [RFC2460] - Deering, S. and R. Hinden, "Internet Protocol, Version 6 5300 (IPv6) Specification", RFC 2460, December 1998, 5301 . 5303 [RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm 5304 1 (SHA1)", RFC 3174, September 2001. 5306 [RFC6194] - Polk, T., Chen, L., Turner, S., and P. Hoffman, "Security 5307 Considerations for the SHA-0 and SHA-1 Message-Digest 5308 Algorithms", RFC 6194, March 2011. 5310 [RFC6234] - Eastlake 3rd, D. and T. Hansen, "US Secure Hash 5311 Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 5312 2011. 5314 [RFC6437] - Amante, S., Carpenter, B., Jiang, S., and J. Rajahalme, 5315 "IPv6 Flow Label Specification", RFC 6437, November 2011, 5316 . 5318 Acknowledgements 5320 The contributions of the following are gratefully acknowledged: 5322 Roman Donchenko, Frank Ellermann, Tony Finch, Bob Moskowitz, 5323 Gayle Noble, Stefan Santesson, and Mukund Sivaraman. 5325 Appendix A: Work Comparison with SHA-1 5327 This section provides a simplistic rough comparison of the level of 5328 effort required per input byte to compute FNV-1a and SHA-1 [RFC3174]. 5330 Ignoring transfer of control and conditional tests and equating all 5331 logical and arithmetic operations, FNV requires 2 operations per 5332 byte, an XOR and a multiply. 5334 SHA-1 is a relatively weak cryptographic hash producing a 160-bit 5335 hash. It has been partially broken [RFC6194]. It is actually designed 5336 to accept a bit vector input although almost all computer uses apply 5337 it to an integer number of bytes. It processes blocks of 512 bits (64 5338 bytes) and we estimate the effort involved in SHA-1 processing a full 5339 block. Ignoring SHA-1 initial set up, transfer of control, and 5340 conditional tests, but counting all logical and arithmetic 5341 operations, including counting indexing as an addition, SHA-1 5342 requires 1,744 operations per 64 bytes block or 27.25 operations per 5343 byte. So by this rough measure, it is a little over 13 times the 5344 effort of FNV for large amounts of data. However, FNV is commonly 5345 used for small inputs. Using the above method, for inputs of N bytes, 5346 where N is <= 55 so SHA-1 will take one block (SHA-1 includes padding 5347 and an 8-byte length at the end of the data in the last block), the 5348 ratio of the effort for SHA-1 to the effort for FNV will be 872/N. 5349 For example, with an 8 byte input, SHA-1 will take 109 times as much 5350 effort as FNV. 5352 Stronger cryptographic functions than SHA-1 generally have an even 5353 higher work factor. 5355 Appendix B: Previous IETF Reference to FNV 5357 FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has 5358 since expired. It was later decided that it would be better to use a 5359 cryptographic hash for that application. 5361 Below is the Java code for FNV64 from that TLS draft included by the 5362 kind permission of the author: 5364 5365 /** 5366 * Java code sample, implementing 64 bit FNV-1a 5367 * By Stefan Santesson 5368 */ 5370 import java.math.BigInteger; 5372 public class FNV { 5374 static public BigInteger getFNV1aToByte(byte[] inp) { 5376 BigInteger m = new BigInteger("2").pow(64); 5377 BigInteger fnvPrime = new BigInteger("1099511628211"); 5378 BigInteger fnvOffsetBasis = 5379 new BigInteger("14695981039346656037"); 5381 BigInteger digest = fnvOffsetBasis; 5383 for (byte b : inp) { 5384 digest = digest.xor(BigInteger.valueOf((int) b & 255)); 5385 digest = digest.multiply(fnvPrime).mod(m); 5386 } 5387 return digest; 5389 } 5390 } 5391 5393 Appendix C: A Few Test Vectors 5395 Below are a few test vectors in the form of ASCII strings and their 5396 FNV32 and FNV64 hashes using the FNV-1a algorithm. 5398 Strings without null (zero byte) termination: 5400 String FNV32 FNV64 5401 "" 0x811c9dc5 0xcbf29ce484222325 5402 "a" 0xe40c292c 0xaf63dc4c8601ec8c 5403 "foobar" 0xbf9cf968 0x85944171f73967e8 5405 Strings including null (zero byte) termination: 5407 String FNV32 FNV64 5408 "" 0x050c5d1f 0xaf63bd4c8601b7df 5409 "a" 0x2b24d044 0x089be207b544f1e4 5410 "foobar" 0x0c1c9eb8 0x34531ca7168b8f38 5412 Appendix Z: Change Summary 5414 RFC Editor Note: Please delete this appendix on publication. 5416 From -00 to -01 5418 1. Add Security Considerations section on why FNV is non- 5419 cryptographic. 5421 2. Add Appendix A on a work factor comparison with SHA-1. 5423 3. Add Appendix B concerning previous IETF draft referenced to FNV. 5425 4. Minor editorial changes. 5427 From -01 to -02 5429 1. Correct FNV_Prime determination criteria and add note as to why s 5430 < 5 and s > 10 are not considered. 5432 2. Add acknowledgements list. 5434 3. Add a couple of references. 5436 4. Minor editorial changes. 5438 From -02 to -03 5440 1. Replace direct reference to US-ASCII standard with reference to 5441 RFC 20. 5443 2. Update dates and version number. 5445 3. Minor editing changes. 5447 From -03 to -04 5449 1. Change reference to RFC 20 back to a reference to the ANSI 1968 5450 ASCII standard. 5452 2. Minor addition to Section 6, point 3. 5454 3. Update dates and version number. 5456 4. Minor editing changes. 5458 From -04 to -05 5460 1. Add Twitter as a use example and IPv6 flow hash study reference. 5462 2. Update dates and version number. 5464 From -05 to -06 5466 1. Add code subsections. 5468 2. Update dates and version number. 5470 From -06 to -07 to -08 5472 1. Update Author info. 5474 2. Minor edits. 5476 From -08 to -09 5478 1. Change reference for ASCII to [RFC20]. 5480 2. Add more details on history of the string used to compute 5481 offset_basis. 5483 3. Re-write "Work Factor" part of Section 6 to be more precise. 5485 4. Minor editorial changes. 5487 From -09 to -10 5489 1. Inclusion of initial partial version of code and some 5490 documentation about the code, Section 6. 5492 2. Insertion of new Section 4 on hashing values. 5494 From -10 to -11 5496 Changes based on code improvements primarily from Tony Hansen who has 5497 been added as an author. Changes based on comments from Mukund 5498 Sivaraman and Roman Donchenko. 5500 From -11 to -12 5502 Keep alive update. 5504 From -12 to -13 5506 Fixed bug in pseudocode in Section 2.3. 5508 Change code to eliminate the BigEndian flag and so there are separate 5509 byte vector output routines for FNV32 and FNV64, equivalent to the 5510 other routines, and integer output routines for cases where 5511 Endianness consistency is not required. 5513 From -13 to -14 to -15 to -16 5515 Keep alive updates. Update an author address. 5517 Author's Address 5519 Glenn Fowler 5520 Google 5522 Email: glenn.s.fowler@gmail.com 5524 Landon Curt Noll 5525 Cisco Systems 5526 170 West Tasman Drive 5527 San Jose, CA 95134 USA 5529 Telephone: +1-408-424-1102 5530 Email: fnv-ietf4-mail@asthe.com 5531 URL: http://www.isthe.com/chongo/index.html 5533 Kiem-Phong Vo 5534 Google 5536 Email: phongvo@gmail.com 5538 Donald Eastlake 5539 Huawei Technologies 5540 1424 Pro Shop Court 5541 Davenport, FL 33896 USA 5543 Telephone: +1-508-333-2270 5544 EMail: d3e3e3@gmail.com 5546 Tony Hansen 5547 AT&T Laboratories 5548 200 Laurel Ave. South 5549 Middletown, NJ 07748 5550 USA 5552 Email: tony@att.com 5554 Copyright, Disclaimer, and Additional IPR Provisions 5556 Copyright (c) 2018 IETF Trust and the persons identified as the 5557 document authors. All rights reserved. 5559 This document is subject to BCP 78 and the IETF Trust's Legal 5560 Provisions Relating to IETF Documents 5561 (http://trustee.ietf.org/license-info) in effect on the date of 5562 publication of this document. Please review these documents 5563 carefully, as they describe your rights and restrictions with respect 5564 to this document. Code Components extracted from this document must 5565 include Simplified BSD License text as described in Section 4.e of 5566 the Trust Legal Provisions and are provided without warranty as 5567 described in the Simplified BSD License. This Internet-Draft is 5568 submitted to IETF in full conformance with the provisions of BCP 78 5569 and BCP 79.