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