idnits 2.17.1 draft-eastlake-fnv-11.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 236 has weird spacing: '...ed char hash...' == Line 1436 has weird spacing: '...int i;...' == Line 1605 has weird spacing: '...context ctx...' == Line 1621 has weird spacing: '...context ctx...' == Line 2005 has weird spacing: '...int i;...' == (17 more instances...) -- The document date (June 16, 2016) is 2871 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'N' is mentioned on line 236, but not defined == Missing Reference: 'FNV128size' is mentioned on line 4194, but not defined == Missing Reference: 'FNV256size' is mentioned on line 4258, but not defined == Missing Reference: 'FNV512size' is mentioned on line 4322, but not defined == Missing Reference: 'FNV1024size' is mentioned on line 4386, but not defined -- Obsolete informational reference (is this intentional?): RFC 2460 (Obsoleted by RFC 8200) Summary: 0 errors (**), 0 flaws (~~), 12 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group Glenn Fowler 2 INTERNET-DRAFT Google 3 Intended Status: Informational Landon Curt Noll 4 Cisco Systems 5 Kiem-Phong Vo 6 Google 7 Donald Eastlake 8 Huawei Technologies 9 Tony Hansen 10 AT&T Laboratories 11 Expires: December 15, 2016 June 16, 2016 13 The FNV Non-Cryptographic Hash Algorithm 14 16 Abstract 18 FNV (Fowler/Noll/Vo) is a fast, non-cryptographic hash algorithm with 19 good dispersion. The purpose of this document is to make information 20 on FNV and open source code performing FNV conveniently available to 21 the Internet community. 23 Status of This Memo 25 This Internet-Draft is submitted to IETF in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Distribution of this document is unlimited. Comments should be sent 29 to the authors. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF), its areas, and its working groups. Note that 33 other groups may also distribute working documents as Internet- 34 Drafts. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 The list of current Internet-Drafts can be accessed at 42 http://www.ietf.org/1id-abstracts.html. The list of Internet-Draft 43 Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html. 46 Table of Contents 48 1. Introduction............................................3 50 2. FNV Basics..............................................4 51 2.1 FNV Primes.............................................4 52 2.2 FNV offset_basis.......................................5 53 2.3 FNV Endianism..........................................6 55 3. Other Hash Sizes and XOR Folding........................7 56 4. Hashing Multiple Values Together........................8 57 5. FNV Constants...........................................9 59 6. The Source Code........................................11 60 6.1 FNV-1a C Code.........................................11 61 6.1.1 FNV32 Code..........................................15 62 6.1.2 FNV64 C Code........................................21 63 6.1.3 FNV128 C Code.......................................32 64 6.1.4 FNV256 C Code.......................................44 65 6.1.5 FNV512 C Code.......................................55 66 6.1.6 FNV1024 C Code......................................67 67 6.2 FNV Test Code.........................................79 69 7. Security Considerations................................93 70 7.1 Why is FNV Non-Cryptographic?.........................93 71 7.2 Inducing Collisions...................................94 73 8. IANA Considerations....................................95 75 Normative References......................................95 76 Informative References....................................95 77 Acknowledgements..........................................96 79 Appendix A: Work Comparison with SHA-1....................97 80 Appendix B: Previous IETF Reference to FNV................98 81 Appendix C: A Few Test Vectors............................99 82 Appendix Z: Change Summary...............................100 83 From -00 to -01..........................................100 84 From -01 to -02..........................................100 85 From -02 to -03..........................................100 86 From -03 to -04..........................................100 87 From -04 to -05..........................................101 88 From -05 to -06..........................................101 89 From -06 to -07 to -08...................................101 90 From -08 to -09..........................................101 91 From -09 to -10..........................................101 92 From -10 to -11..........................................102 94 Author's Address.........................................103 96 1. Introduction 98 The FNV hash algorithm is based on an idea sent as reviewer comments 99 to the [IEEE] POSIX P1003.2 committee by Glenn Fowler and Phong Vo in 100 1991. In a subsequent ballot round Landon Curt Noll suggested an 101 improvement on their algorithm. Some people tried this hash and found 102 that it worked rather well. In an EMail message to Landon, they named 103 it the "Fowler/Noll/Vo" or FNV hash. [FNV] 105 FNV hashes are designed to be fast while maintaining a low collision 106 rate. The high dispersion of the FNV hashes makes them well suited 107 for hashing nearly identical strings such as URLs, hostnames, 108 filenames, text, IP addresses, etc. Their speed allows one to quickly 109 hash lots of data while maintaining a reasonably low collision rate. 110 However, they are generally not suitable for cryptographic use. (See 111 Section 7.1.) 113 The FNV hash is widely used, for example in DNS servers, the Twitter 114 service, database indexing hashes, major web search / indexing 115 engines, netnews history file Message-ID lookup functions, anti-spam 116 filters, a spellchecker programmed in Ada 95, flatassembler's open 117 source x86 assembler - user-defined symbol hashtree, non- 118 cryptographic file fingerprints, computing Unique IDs in DASM (DTN 119 (Delay Tolerant Networking) Applications for Symbian Mobile-phones), 120 Microsoft's hash_map implementation for VC++ 2005, the realpath cache 121 in PHP 5.x (php-5.2.3/TSRM/tsrm_virtual_cwd.c), and many other uses. 123 A study has recommended FNV in connection with the IPv6 Flow Label 124 field [IPv6flow]. 126 FNV hash algorithms and source code have been released into the 127 public domain. The authors of the FNV algorithm took deliberate steps 128 to disclose the algorithm in a public forum soon after it was 129 invented. More than a year passed after this public disclosure and 130 the authors deliberately took no steps to patent the FNV algorithm. 131 Therefore, it is safe to say that the FNV authors have no patent 132 claims on the FNV algorithm as published. 134 If you use an FNV function in an application, you are kindly 135 requested to send an EMail about it to: fnv-mail@asthe.com 137 2. FNV Basics 139 This document focuses on the FNV-1a function whose pseudo-code is as 140 follows: 142 hash = offset_basis 143 for each octet_of_data to be hashed 144 hash = hash xor octet_of_data 145 hash = hash * FNV_Prime 146 return hash 148 In the pseudo-code above, hash is a power-of-two number of bits (32, 149 64, ... 1024) and offset_basis and FNV_Prime depend on the size of 150 hash. 152 The FNV-1 algorithm is the same, including the values of offset_basis 153 and FNV_Prime, except that the order of the two lines with the "xor" 154 and multiply operations are reversed. Operational experience 155 indicates better hash dispersion for small amounts of data with 156 FNV-1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero. 157 FNV-1a is suggested for general use. 159 2.1 FNV Primes 161 The theory behind FNV_Prime's is beyond the scope of this document 162 but the basic property to look for is how an FNV_Prime would impact 163 dispersion. Now, consider any n-bit FNV hash where n is >= 32 and 164 also a power of 2, in particular n = 2**s. For each such n-bit FNV 165 hash, an FNV_Prime p is defined as: 167 When s is an integer and 4 < s < 11, then FNV_Prime is the 168 smallest prime p of the form: 170 256**int((5 + 2**s)/12) + 2**8 + b 172 where b is an integer such that: 174 0 < b < 2**8 175 The number of one-bits in b is 4 or 5 177 and where ( p mod (2**40 - 2**24 - 1) ) > (2**24 + 2**8 + 2**7). 179 Experimentally, FNV_Primes matching the above constraints tend to 180 have better dispersion properties. They improve the polynomial 181 feedback characteristic when an FNV_Prime multiplies an intermediate 182 hash value. As such, the hash values produced are more scattered 183 throughout the n-bit hash space. 185 The case where s < 5 is not considered because the resulting hash 186 quality is too low. Such small hashes can, if desired, be derived 187 from a 32 bit FNV hash by XOR folding (see Section 3). The case where 188 s > 10 is not considered because of the doubtful utility of such 189 large FNV hashes and because the criteria for such large FNV_Primes 190 is more complex, due to the sparsity of such large primes, and would 191 needlessly clutter the criteria given above. 193 Per the above constraints, an FNV_Prime should have only 6 or 7 one- 194 bits in it. Therefore, some compilers may seek to improve the 195 performance of a multiplication with an FNV_Prime by replacing the 196 multiplication with shifts and adds. However, note that the 197 performance of this substitution is highly hardware-dependent and 198 should be done with care. FNV_Primes were selected primarily for the 199 quality of resulting hash function, not for compiler optimization. 201 2.2 FNV offset_basis 203 The offset_basis values for the n-bit FNV-1a algorithms are computed 204 by applying the n-bit FNV-0 algorithm to the 32 octets representing 205 the following character string in [RFC20]: 207 chongo /\../\ 209 The \'s in the above string are not C-style escape characters. In C- 210 string notation, these 32 octets are: 212 "chongo /\\../\\" 214 That string was used because the person testing FNV with non-zero 215 offset_basis values was looking at an email message from Landon and 216 was copying his standard email signature line; however, they couldn't 217 see very well and copied it incorrectly. In fact, he uses 219 chongo (Landon Curt Noll) /\oo/\ 221 but, since it doesn't matter, no effort has been made to correct 222 this. 224 In the general case, almost any offset_basis will serve so long as it 225 is non-zero. The choice of a non-standard offset_basis may be 226 beneficial in defending against some attacks that try to induce hash 227 collisions. 229 2.3 FNV Endianism 231 For persistent storage or interoperability between different hardware 232 platforms, an FNV hash shall be represented in the little endian 233 format. That is, the FNV hash will be stored in an array hash[N] with 234 N bytes such that its integer value can be retrieved as follows: 236 unsigned char hash[N]; 237 for ( i = N-1, value = 0; i >= 0; --i ) 238 value = value << 8 + hash[i]; 240 Of course, when FNV hashes are used in a single process or a group of 241 processes sharing memory on processors with compatible endian-ness, 242 the natural endian-ness of those processors can be used regardless of 243 its type, little, big, or some other exotic form. 245 3. Other Hash Sizes and XOR Folding 247 Many hash uses require a hash that is not one of the FNV sizes for 248 which constants are provided in Section 5. If a larger hash size is 249 needed, please contact the authors of this document. 251 Most hash applications make use of a hash that is a fixed size binary 252 field. Assume that k bits of hash are desired and k is less than 1024 253 but not one of the sizes for which constants are provided in Section 254 5. The recommended technique is to take the smallest FNV hash of size 255 S, where S is larger than k, and calculate the desired k-bit-hash 256 using xor folding as shown below. The final bit masking operation is 257 logically unnecessary if the size of the variable k-bit-hash is 258 exactly k bits. 260 temp = FNV_S ( data-to-be-hashed ) 261 k-bit-hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 ) 263 Hash functions are a trade-off between speed and strength. For 264 example, a somewhat stronger hash may be obtained for exact FNV sizes 265 by calculating an FNV twice as long as the desired output ( S = 2*k ) 266 and performing such data folding using a k equal to the size of the 267 desired output. However, if a much stronger hash, for example one 268 suitable for cryptographic applications, is wanted, algorithms 269 designed for that purpose, such as those in [RFC6234], should be 270 used. 272 If it is desired to obtain a hash result that is a value between 0 273 and max, where max+1 is a not a power of two, simply choose an FNV 274 hash size S such that 2**S > max. Then calculate the following: 276 FNV_S mod ( max+1 ) 278 The resulting remainder will be in the range desired but will suffer 279 from a bias against large values with the bias being larger if 2**S 280 is only a little bigger than max. If this bias is acceptable, no 281 further processing is needed. If this bias is unacceptable, it can be 282 avoided by retrying for certain high values of hash, as follows, 283 before applying the mod operation above: 285 X = ( int( ( 2**S - 1 ) / ( max+1 ) ) ) * ( max+1 ) 286 while ( hash >= X ) 287 hash = ( hash * FNV_Prime ) + offset_basis 289 4. Hashing Multiple Values Together 291 It is common for there to be a few different component values, say 292 three strings X, Y, and Z, where a hash over all of them is desired. 293 The simplest thing to do is to concatenate them and compute the hash 294 of that concatenation, as in 296 hash ( X | Y | Z ) 298 where the vertical bar character ("|") represents string 299 concatenation. Note that, for FNV, the same hash results if X, Y, 300 and Z are actually concatenated and the FNV hash applied to the 301 resulting string or if FNV is calculated on an initial substring and 302 the result used as the offset_basis when calculating the FNV hash of 303 the remainder of the string. This can be done several times. 304 Assuming FNVoffset_basis ( v, w ) is FNV of w using v as the 305 offset_basis, then in the example above, fnvx = FNV ( X ) could be 306 calculated and then fnvxy = FNVoffset_basis ( fnvx, Y ), and finally 307 fnvxyz = FNVoffset_basis ( fnvxy, Z). The resulting fnvxyz would be 308 the same as FNV ( X | Y | Z ); 310 Cases are also common where such a hash needs to be repeatedly 311 calculated where the component values vary but some vary more 312 frequently than others. For example, assume some sort of computer 313 network traffic flow ID, such as the IPv6 flow ID [RFC6437], is to be 314 calculated for network packets based on the source and destination 315 IPv6 address and the Traffic Class [RFC2460]. If the Flow ID is 316 calculated in the originating host, the source IPv6 address would 317 likely always be the same or perhaps assume one of a very small 318 number of values. By placing this quasi-constant IPv6 source address 319 first in the string being FNV hashed, FNV ( IPv6source ) could be 320 calculated and used as the offset_basis for calculating FNV of the 321 IPv6 destination address and Traffic Class for each packet. As a 322 result, the per packet hash would be over 17 bytes rather than over 323 33 bytes saving computational resources. The code in this document 324 includes functions facilitating the use of a non-standard 325 offset_basis. 327 5. FNV Constants 329 The FNV Primes are as follows: 331 32 bit FNV_Prime = 2**24 + 2**8 + 0x93 = 16,777,619 332 = 0x01000193 334 64 bit FNV_Prime = 2**40 + 2**8 + 0xB3 = 1,099,511,628,211 335 = 0x00000100 000001B3 337 128 bit FNV_Prime = 2**88 + 2**8 + 0x3B = 338 309,485,009,821,345,068,724,781,371 339 = 0x00000000 01000000 00000000 0000013B 341 256 bit FNV_Prime = 2**168 + 2**8 + 0x63 = 342 374,144,419,156,711,147,060,143,317,175,368,453,031,918,731,002,211 = 343 0x0000000000000000 0000010000000000 0000000000000000 0000000000000163 345 512 bit FNV_Prime = 2**344 + 2**8 + 0x57 = 35, 346 835,915,874,844,867,368,919,076,489,095,108,449,946,327,955,754,392, 347 558,399,825,615,420,669,938,882,575,126,094,039,892,345,713,852,759 = 348 0x0000000000000000 0000000000000000 0000000001000000 0000000000000000 349 0000000000000000 0000000000000000 0000000000000000 0000000000000157 351 1024 bit FNV_Prime = 2**680 + 2**8 + 0x8D = 5, 352 016,456,510,113,118,655,434,598,811,035,278,955,030,765,345,404,790, 353 744,303,017,523,831,112,055,108,147,451,509,157,692,220,295,382,716, 354 162,651,878,526,895,249,385,292,291,816,524,375,083,746,691,371,804, 355 094,271,873,160,484,737,966,720,260,389,217,684,476,157,468,082,573 = 356 0x0000000000000000 0000000000000000 0000000000000000 0000000000000000 357 0000000000000000 0000010000000000 0000000000000000 0000000000000000 358 0000000000000000 0000000000000000 0000000000000000 0000000000000000 359 0000000000000000 0000000000000000 0000000000000000 000000000000018D 361 The FNV offset_basis values are as follows: 363 32 bit offset_basis = 2,166,136,261 = 0x811C9DC5 365 64 bit offset_basis = 14695981039346656037 = 0xCBF29CE4 84222325 367 128 bit offset_basis = 144066263297769815596495629667062367629 = 368 0x6C62272E 07BB0142 62B82175 6295C58D 370 256 bit offset_basis = 100,029,257,958,052,580,907,070,968, 371 620,625,704,837,092,796,014,241,193,945,225,284,501,741,471,925,557 = 372 0xDD268DBCAAC55036 2D98C384C4E576CC C8B1536847B6BBB3 1023B4C8CAEE0535 373 512 bit offset_basis = 9, 374 659,303,129,496,669,498,009,435,400,716,310,466,090,418,745,672,637, 375 896,108,374,329,434,462,657,994,582,932,197,716,438,449,813,051,892, 376 206,539,805,784,495,328,239,340,083,876,191,928,701,583,869,517,785 = 377 0xB86DB0B1171F4416 DCA1E50F309990AC AC87D059C9000000 0000000000000D21 378 E948F68A34C192F6 2EA79BC942DBE7CE 182036415F56E34B AC982AAC4AFE9FD9 380 1024 bit offset_basis = 14,197,795,064,947,621,068,722,070,641,403, 381 218,320,880,622,795,441,933,960,878,474,914,617,582,723,252,296,732, 382 303,717,722,150,864,096,521,202,355,549,365,628,174,669,108,571,814, 383 760,471,015,076,148,029,755,969,804,077,320,157,692,458,563,003,215, 384 304,957,150,157,403,644,460,363,550,505,412,711,285,966,361,610,267, 385 868,082,893,823,963,790,439,336,411,086,884,584,107,735,010,676,915 = 386 0x0000000000000000 005F7A76758ECC4D 32E56D5A591028B7 4B29FC4223FDADA1 387 6C3BF34EDA3674DA 9A21D90000000000 0000000000000000 0000000000000000 388 0000000000000000 0000000000000000 0000000000000000 000000000004C6D7 389 EB6E73802734510A 555F256CC005AE55 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 391 6. The Source Code 393 [This section is not yet complete.] 395 The following sub-sections provide reference C source code and a test 396 driver for FNV-1a. 398 Alternative source code, including 32 and 64 bit FNV-1 and FNV-1a in 399 x86 assembler, is currently available at [FNV]. 401 Section 6.2 provides a test driver. 403 6.1 FNV-1a C Code 405 This section provides the direct FNV-1a function for each of the 406 lengths for which it is specified in this document. The following 407 functions are provided, where XXX is "32", "64", "128", "256", "512", 408 or "1024": 410 FNVXXXstring, FNVXXXblock: These are simple functions for directly 411 returning the FNV hash of a zero terminated byte string not 412 including the zero and the FNV hash of a counted block of 413 bytes. Note that for applications of FNV-32 where 32-bit 414 integers are supported and FNV-64 where 64-bit integers are 415 supported, the code is sufficiently simple that, to maximize 416 performance, use of open coding or macros may be more 417 appropriate than calling a subroutine. 419 FNVXXXinit, FNVXXXinitBasis: These functions and the next two sets of 420 functions below provide facilities for incrementally 421 calculating FNV hashes. They all assume a data structure of 422 type FNVXXXcontext that holds the current state of the hash. 423 FNVXXXinit initializes that context to the standard 424 offset_basis. FNVXXXinitBasis takes an offset_basis value as a 425 parameter and may be useful for hashing concatenations, as 426 described in Section 4, as well as for simply using a non- 427 standard offset_basis. 429 FNXXXVblockin, FNVXXXstringin: These functions hash a sequence of 430 bytes into an FNVXXXcontext that was originally initialized by 431 FNVXXXinit or FNVXXXinitBasis. FNVXXXblockin hashes in a 432 counted block of bytes. FNVXXXstringin hashes in a zero 433 terminated byte string not incuding the final zero. 435 FNVXXXresult: This function extracts the final FNV hash result from 436 an FNVXXXcontext. 438 The following code is a private header file used by all the FNV 439 functions further below and which states the terms for use and 440 redistribution of all of this code. 442 443 /************************ fnv-private.h ************************/ 444 /****************** See RFC NNNN for details *******************/ 445 /* Copyright (c) 2016 IETF Trust and the persons identified as 446 * authors of the code. All rights reserved. 447 * 448 * Redistribution and use in source and binary forms, with or without 449 * modification, are permitted provided that the following conditions 450 * are met: 451 * 452 * * Redistributions of source code must retain the above copyright 453 * notice, this list of conditions and the following disclaimer. 454 * 455 * * Redistributions in binary form must reproduce the above copyright 456 * notice, this list of conditions and the following disclaimer in 457 * the documentation and/or other materials provided with the 458 * distribution. 459 * 460 * * Neither the name of Internet Society, IETF or IETF Trust, nor the 461 * names of specific contributors, may be used to endorse or promote 462 * products derived from this software without specific prior 463 * written permission. 464 * 465 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 466 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 467 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 468 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 469 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 470 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 471 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 472 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 473 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 474 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 475 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 476 * POSSIBILITY OF SUCH DAMAGE. 477 */ 479 #ifndef _FNV_PRIVATE_H_ 480 #define _FNV_PRIVATE_H_ 482 /* 483 * Six FNV-1a hashes are defined with these sizes: 484 * FNV32 32 bits, 4 bytes 485 * FNV64 64 bits, 8 bytes 486 * FNV128 128 bits, 16 bytes 487 * FNV256 256 bits, 32 bytes 488 * FNV512 512 bits, 64 bytes 489 * FNV1024 1024 bits, 128 bytes 490 */ 492 /* Private stuff used by this implementation of the FNV 493 * (Fowler, Noll, Vo) non-cryptographic hash function FNV-1a. 494 * External callers don't need to know any of this. */ 496 enum { /* State value bases for context->Computed */ 497 FNVinited = 22, 498 FNVcomputed = 76, 499 FNVemptied = 220, 500 FNVclobber = 122 /* known bad value for testing */ 501 }; 503 /* Deltas to assure distinct state values for different lengths */ 504 enum { 505 FNV32state = 1, 506 FNV64state = 3, 507 FNV128state = 5, 508 FNV256state = 7, 509 FNV512state = 11, 510 FNV1024state = 13 511 }; 513 #endif 514 516 The following code is a simple header file to include all the 517 specific length FNV header files. 519 520 /****************************** FNV.h *******************************/ 521 /******************* See RFC NNNN for details. **********************/ 522 /* 523 * Copyright (c) 2016 IETF Trust and the persons identified as 524 * authors of the code. All rights reserved. 525 * See fnv-private.h for terms of use and redistribution. 526 */ 528 #ifndef _FNV_H_ 529 #define _FNV_H_ 531 #include "FNV32.h" 532 #include "FNV64.h" 533 #include "FNV128.h" 534 #include "FNV256.h" 535 #include "FNV512.h" 536 #include "FNV1024.h" 538 #endif /* _FNV_H_ */ 539 541 The following code is a simple header file to control configuration 542 related to big integer and big endian support. 544 545 /*************************** FNVconfig.h ****************************/ 546 /******************* See RFC NNNN for details. **********************/ 547 /* 548 * Copyright (c) 2016 IETF Trust and the persons identified as 549 * authors of the code. All rights reserved. 550 * See fnv-private.h for terms of use and redistribution. 551 */ 553 #ifndef _FNVconfig_H_ 554 #define _FNVconfig_H_ 556 /* 557 * Description: 558 * This file provides configuration ifdefs for the 559 * FNV-1a non-cryptographic hash algorithms. 560 * 561 * >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */ 563 /* FNV_64bitIntegers - Define this if your system supports 64-bit 564 * arithmetic including 32-bit x 32-bit multiplication 565 * producing a 64-bit product. If undefined, it will be 566 * assumed that 32-bit arithmetic is supported including 567 * 16-bit x 16-bit multiplication producing a 32-bit result. 568 */ 569 // #define FNV_64bitIntegers 571 /* 572 * 573 * FNV_BigEndian - Define this ONLY if your system uses big 574 * endian representation AND your FNV hashes need to 575 * interoperate with little endian systems. If you #define 576 * this symbol when not needed, it will unnecessarily slow 577 * down and increase the code size of the FNV functions. 578 */ 579 // #define FNV_BigEndian 581 /* 582 * The following allow the FNV test program to override the 583 * above configuration settings. 584 */ 586 #ifdef FNV_TEST_PROGRAM 587 # ifdef TEST_FNV_64bitIntegers 588 # ifndef FNV_64bitIntegers 589 # define FNV_64bitIntegers 590 # endif 591 # else 592 # undef FNV_64bitIntegers 593 # endif 594 # ifndef FNV_64bitIntegers /* causes an error if uint64_t is used */ 595 # define uint64_t foobar 596 # endif 597 # ifdef TEST_FNV_BigEndian 598 # ifndef FNV_BigEndian 599 # define FNV_BigEndian 600 # endif 601 # else 602 # undef FNV_BigEndian 603 # endif 604 #endif 606 #endif /* _FNVconfig_H_ */ 607 609 6.1.1 FNV32 Code 611 The header and C source for 32-bit FNV-1a. 613 614 /***************************** FNV32.h ******************************/ 615 /******************** See RFC NNNN for details **********************/ 616 /* 617 * Copyright (c) 2016 IETF Trust and the persons identified as 618 * authors of the code. All rights reserved. 619 * See fnv-private.h for terms of use and redistribution. 620 */ 622 #ifndef _FNV32_H_ 623 #define _FNV32_H_ 625 #include "FNVconfig.h" 627 #include 628 /* #define FNV32size (32/8) not used */ 630 /* If you do not have the ISO standard stdint.h header file, then you 631 * must typedef the following types: 632 * 633 * type meaning 634 * uint32_t unsigned 32 bit integer 635 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 636 */ 638 #ifndef _FNV_ErrCodes_ 639 #define _FNV_ErrCodes_ 640 /******************************************************************** 641 * All FNV functions provided return as integer as follows: 642 * 0 -> success 643 * >0 -> error as listed below 644 */ 645 enum { /* success and errors */ 646 fnvSuccess = 0, 647 fnvNull, /* Null pointer parameter */ 648 fnvStateError, /* called Input after Result, etc. */ 649 fnvBadParam /* passed a bad parameter */ 650 }; 651 #endif /* _FNV_ErrCodes_ */ 653 /* 654 * This structure holds context information for an FNV32 hash 655 */ 656 typedef struct FNV32context_s { 657 int Computed; /* state */ 658 uint32_t Hash; 659 } FNV32context; 661 /* 662 * Function Prototypes 663 * FNV32string: hash a zero terminated string not including 664 * the terminating zero 665 * FNV32block: hash a specified length byte vector 666 * FNV32init: initializes an FNV32 context 667 * FNV32initBasis: initializes an FNV32 context with a 668 * provided basis 669 * FNV32blockin: hash in a specified length byte vector 670 * FNV32stringin: hash in a zero terminated string not 671 * including the zero 672 * FNV32result: returns the hash value 673 * 674 * Hash is returned as a 32-bit integer 675 */ 677 #ifdef __cplusplus 678 extern "C" { 679 #endif 681 /* FNV32 */ 682 extern int FNV32string ( const char *in, 683 uint32_t * const out ); 684 extern int FNV32block ( const void *in, 685 long int inlength, 686 uint32_t * const out ); 687 extern int FNV32init ( FNV32context * const ); 688 extern int FNV32initBasis ( FNV32context * const, 689 uint32_t basis ); 690 extern int FNV32blockin ( FNV32context * const, 691 const void *in, 692 long int inlength ); 693 extern int FNV32stringin ( FNV32context * const, 694 const char *in ); 695 extern int FNV32result ( FNV32context * const, 696 uint32_t * const out ); 698 #ifdef __cplusplus 699 } 700 #endif 702 #endif /* _FNV32_H_ */ 703 705 706 /**************************** FNV32.c ****************************/ 707 /****************** See RFC NNNN for details. ********************/ 708 /* Copyright (c) 2016 IETF Trust and the persons identified as 709 * authors of the code. All rights reserved. 710 * See fnv-private.h for terms of use and redistribution. 711 */ 713 /* This code implements the FNV (Fowler, Noll, Vo) non-cryptographic 714 * hash function FNV-1a for 32-bit hashes. 715 */ 717 #ifndef _FNV32_C_ 718 #define _FNV32_C_ 720 #include "fnv-private.h" 721 #include "FNV32.h" 723 /* 32 bit FNV_prime = 2^24 + 2^8 + 0x93 */ 724 #define FNV32prime 0x01000193 725 #define FNV32basis 0x811C9DC5 727 #ifdef FNV_BigEndian 728 /* Local prototype */ 729 static void FNV32reverse ( uint32_t *out, uint32_t hash ); 730 #endif 732 /* FNV32 hash a zero terminated string not including the zero 733 *********************************************************************/ 734 int FNV32string ( const char *in, uint32_t * const out ) 735 { 736 uint32_t temp; 737 uint8_t ch; 739 if ( in && out ) 740 { 741 temp = FNV32basis; 742 while ( (ch = *in++) ) 743 temp = FNV32prime * ( temp ^ ch ); 744 #ifdef FNV_BigEndian 745 FNV32reverse ( out, temp ); 746 #else 747 *out = temp; 748 #endif 749 return fnvSuccess; 750 } 751 return fnvNull; /* Null input pointer */ 752 } /* end FNV32string */ 754 /* FNV32 hash a counted block 755 ***************************************************************/ 756 int FNV32block ( const void *vin, 757 long int length, 758 uint32_t * const out ) 759 { 760 const uint8_t *in = (const uint8_t*)vin; 761 uint32_t temp; 763 if ( in && out ) 764 { 765 if ( length < 0 ) 766 return fnvBadParam; 767 for ( temp = FNV32basis; length > 0; length-- ) 768 temp = FNV32prime * ( temp ^ *in++ ); 769 #ifdef FNV_BigEndian 770 FNV32reverse ( out, temp ); 771 #else 772 *out = temp; 773 #endif 774 return fnvSuccess; 775 } 776 return fnvNull; /* Null input pointer */ 777 } /* end FNV32block */ 779 #ifdef FNV_BigEndian 781 /* Store a Big Endian result back as Little Endian 782 ***************************************************************/ 783 static void FNV32reverse ( uint32_t *out, uint32_t hash ) 784 { 785 uint32_t temp; 786 temp = hash & 0xFF; 787 hash >>= 8; 788 temp = ( temp << 8 ) + ( hash & 0xFF ); 789 hash >>= 8; 790 temp = ( temp << 8 ) + ( hash & 0xFF ); 791 hash >>= 8; 792 *out = ( temp << 8 ) + ( hash & 0xFF ); 793 } /* end FNV32reverse */ 795 #endif /* FNV_BigEndian */ 797 /*************************************************************** 798 * Set of init, input, and output functions below * 799 * to incrementally compute FNV32 * 800 ***************************************************************/ 802 /* initialize context 803 ***************************************************************/ 804 int FNV32init ( FNV32context * const ctx ) 805 { 806 return FNV32initBasis ( ctx, FNV32basis ); 807 } /* end FNV32init */ 809 /* initialize context with a provided basis 810 ***************************************************************/ 811 int FNV32initBasis ( FNV32context * const ctx, uint32_t basis ) 812 { 813 if ( ctx ) 814 { 815 ctx->Hash = basis; 816 ctx->Computed = FNVinited+FNV32state; 817 return fnvSuccess; 818 } 819 return fnvNull; 820 } /* end FNV32initBasis */ 822 /* hash in a counted block 823 ***************************************************************/ 824 int FNV32blockin ( FNV32context * const ctx, 825 const void *vin, 826 long int length ) 827 { 828 const uint8_t *in = (const uint8_t*)vin; 829 uint32_t temp; 831 if ( ctx && in ) 832 { 833 if ( length < 0 ) 834 return fnvBadParam; 836 switch ( ctx->Computed ) 837 { 838 case FNVinited+FNV32state: 839 ctx->Computed = FNVcomputed+FNV32state; 840 case FNVcomputed+FNV32state: 841 break; 842 default: 843 return fnvStateError; 844 } 845 for ( temp = ctx->Hash; length > 0; length-- ) 846 temp = FNV32prime * ( temp ^ *in++ ); 847 ctx->Hash = temp; 848 return fnvSuccess; 849 } 850 return fnvNull; 851 } /* end FNV32blockin */ 853 /* hash in a zero terminated string not including the zero 854 ***************************************************************/ 855 int FNV32stringin ( FNV32context * const ctx, 856 const char *in ) 857 { 858 uint32_t temp; 859 uint8_t ch; 861 if ( ctx && in ) 862 { 863 switch ( ctx->Computed ) 864 { 865 case FNVinited+FNV32state: 866 ctx->Computed = FNVcomputed+FNV32state; 867 case FNVcomputed+FNV32state: 868 break; 869 default: 870 return fnvStateError; 871 } 872 temp = ctx->Hash; 873 while ( (ch = (uint8_t)*in++) ) 874 temp = FNV32prime * ( temp ^ ch ); 875 ctx->Hash = temp; 876 return fnvSuccess; 877 } 878 return fnvNull; 879 } /* end FNV32stringin */ 881 /* return hash 882 ***************************************************************/ 883 int FNV32result ( FNV32context * const ctx, 884 uint32_t * const out ) 885 { 886 if ( ctx && out ) 887 { 888 if ( ctx->Computed != FNVcomputed+FNV32state ) 889 return fnvStateError; 890 ctx->Computed = FNVemptied+FNV32state; 891 #ifdef FNV_BigEndian 892 FNV32reverse ( out, ctx->Hash ); 893 #else 894 *out = ctx->Hash; 895 #endif 896 ctx->Hash = 0; 897 return fnvSuccess; 898 } 899 return fnvNull; 900 } /* end FNV32result */ 902 #endif /* _FNV32_C_ */ 903 905 6.1.2 FNV64 C Code 907 The header and C source for 64-bit FNV-1a. 909 910 /***************************** FNV64.h ******************************/ 911 /******************* See RFC NNNN for details. **********************/ 912 /* 913 * Copyright (c) 2016 IETF Trust and the persons identified as 914 * authors of the code. All rights reserved. 915 * See fnv-private.h for terms of use and redistribution. 916 */ 918 #ifndef _FNV64_H_ 919 #define _FNV64_H_ 921 /* 922 * Description: 923 * This file provides headers for the 64-bit version of the FNV-1a 924 * non-cryptographic hash algorithm. 925 */ 927 #include "FNVconfig.h" 929 #include 930 #define FNV64size (64/8) 932 /* If you do not have the ISO standard stdint.h header file, then you 933 * must typedef the following types: 935 * 936 * type meaning 937 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 938 * uint32_t unsigned 32 bit integer 939 * uint16_t unsigned 16 bit integer 940 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 941 */ 943 #ifndef _FNV_ErrCodes_ 944 #define _FNV_ErrCodes_ 945 /********************************************************************* 946 * All FNV functions provided return as integer as follows: 947 * 0 -> success 948 * >0 -> error as listed below 949 */ 950 enum { /* success and errors */ 951 fnvSuccess = 0, 952 fnvNull, /* Null pointer parameter */ 953 fnvStateError, /* called Input after Result, etc. */ 954 fnvBadParam /* passed a bad parameter */ 955 }; 956 #endif /* _FNV_ErrCodes_ */ 958 /* 959 * This structure holds context information for an FNV64 hash 960 */ 961 #ifdef FNV_64bitIntegers 962 /* version if 64 bit integers supported */ 964 typedef struct FNV64context_s { 965 int Computed; /* state */ 966 uint64_t Hash; 967 } FNV64context; 969 #else 970 /* version if 64 bit integers NOT supported */ 972 typedef struct FNV64context_s { 973 int Computed; /* state */ 974 uint16_t Hash[FNV64size/2]; 975 } FNV64context; 977 #endif /* FNV_64bitIntegers */ 979 /* 980 * Function Prototypes 981 * FNV64string: hash a zero terminated string not including 982 * the terminating zero 983 * FNV64block: FNV64 hash a specified length byte vector 984 * FNV64init: initializes an FNV64 context 985 * FNV64initBasis: initializes an FNV64 context with a 986 * provided basis 987 * FNV64blockin: hash in a specified length byte vector 988 * FNV64stringin: hash in a zero terminated string not 989 * incluing the zero 990 * FNV64result: returns the hash value 991 * 992 * Hash is returned as a 64-bit integer if supported, otherwise 993 * as a vector of 8-bit integers 994 */ 996 #ifdef __cplusplus 997 extern "C" { 998 #endif 1000 /* FNV64 */ 1001 extern int FNV64init ( FNV64context * const ); 1002 extern int FNV64blockin ( FNV64context * const, 1003 const void * in, 1004 long int length ); 1005 extern int FNV64stringin ( FNV64context * const, 1006 const char * in ); 1008 #ifdef FNV_64bitIntegers 1009 extern int FNV64string ( const char *in, 1010 uint64_t * const out ); 1011 extern int FNV64block ( const void *in, 1012 long int length, 1013 uint64_t * const out ); 1014 extern int FNV64initBasis ( FNV64context * const, 1015 uint64_t basis ); 1016 extern int FNV64result ( FNV64context * const, 1017 uint64_t * const out ); 1018 #else 1019 extern int FNV64string ( const char *in, 1020 uint8_t out[FNV64size] ); 1021 extern int FNV64block ( const void *in, 1022 long int length, 1023 uint8_t out[FNV64size] ); 1024 extern int FNV64initBasis ( FNV64context * const, 1025 const uint8_t basis[FNV64size] ); 1026 extern int FNV64result ( FNV64context * const, 1027 uint8_t out[FNV64size] ); 1028 #endif /* FNV_64bitIntegers */ 1030 #ifdef __cplusplus 1031 } 1032 #endif 1034 #endif /* _FNV64_H_ */ 1035 1037 1038 /***************************** FNV64.c ******************************/ 1039 /******************** See RFC NNNN for details **********************/ 1040 /* Copyright (c) 2016 IETF Trust and the persons identified as 1041 * authors of the code. All rights reserved. 1042 * See fnv-private.h for terms of use and redistribution. 1043 */ 1045 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 1046 * hash function FNV-1a for 64-bit hashes. 1047 */ 1049 #ifndef _FNV64_C_ 1050 #define _FNV64_C_ 1052 #include "fnv-private.h" 1053 #include "FNV64.h" 1055 /******************************************************************** 1056 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1057 ********************************************************************/ 1058 #ifdef FNV_64bitIntegers 1060 #ifdef FNV_BigEndian 1061 /* Local prototype */ 1062 static void FNV64reverse ( uint64_t * out, uint64_t hash ); 1063 #endif /* FNV_BigEndian */ 1065 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 1066 #define FNV64prime 0x00000100000001B3 1067 #define FNV64basis 0xCBF29CE484222325 1069 /* FNV64 hash a null terminated string (64 bit) 1070 ********************************************************************/ 1071 int FNV64string ( const char *in, uint64_t * const out ) 1072 { 1073 uint64_t temp; 1074 uint8_t ch; 1076 if ( in && out ) 1077 { 1078 temp = FNV64basis; 1079 while ( (ch = *in++) ) 1080 temp = FNV64prime * ( temp ^ ch ); 1081 #ifdef FNV_BigEndian 1082 FNV64reverse ( out, temp ); 1083 #else 1084 *out = temp; 1086 #endif 1087 return fnvSuccess; 1088 } 1089 return fnvNull; /* Null input pointer */ 1090 } /* end FNV64string */ 1092 /* FNV64 hash a counted block (64 bit) 1093 ********************************************************************/ 1094 int FNV64block ( const void *vin, 1095 long int length, 1096 uint64_t * const out ) 1097 { 1098 const uint8_t *in = (const uint8_t*)vin; 1099 uint64_t temp; 1101 if ( in && out ) 1102 { 1103 if ( length < 0 ) 1104 return fnvBadParam; 1105 for ( temp = FNV64basis; length > 0; length-- ) 1106 temp = FNV64prime * ( temp ^ *in++ ); 1107 #ifdef FNV_BigEndian 1108 FNV64reverse ( out, temp ); 1109 #else 1110 *out = temp; 1111 #endif 1112 return fnvSuccess; 1113 } 1114 return fnvNull; /* Null input pointer */ 1115 } /* end FNV64block */ 1117 #ifdef FNV_BigEndian 1119 /* Store a Big Endian result back as Little Endian 1120 ***************************************************************/ 1121 static void FNV64reverse ( uint64_t *out, uint64_t hash ) 1122 { 1123 uint64_t temp; 1124 int i; 1126 temp = hash & 0xFF; 1127 for ( i = FNV64size - 1; i > 0; i-- ) 1128 { 1129 hash >>= 8; 1130 temp = ( temp << 8 ) + ( hash & 0xFF ); 1131 } 1132 *out = temp; 1133 } /* end FNV64reverse */ 1135 #endif /* FNV_BigEndian */ 1136 /******************************************************************** 1137 * Set of init, input, and output functions below * 1138 * to incrementally compute FNV64 * 1139 ********************************************************************/ 1141 /* initialize context (64 bit) 1142 ********************************************************************/ 1143 int FNV64init ( FNV64context * const ctx ) 1144 { 1145 return FNV64initBasis ( ctx, FNV64basis ); 1146 } /* end FNV64init */ 1148 /* initialize context with a provided basis (64 bit) 1149 ********************************************************************/ 1150 int FNV64initBasis ( FNV64context * const ctx, uint64_t basis ) 1151 { 1152 if ( ctx ) 1153 { 1154 ctx->Hash = basis; 1155 ctx->Computed = FNVinited+FNV64state; 1156 return fnvSuccess; 1157 } 1158 return fnvNull; 1159 } /* end FNV64initBasis */ 1161 /* hash in a counted block (64 bit) 1162 ********************************************************************/ 1163 int FNV64blockin ( FNV64context * const ctx, 1164 const void *vin, 1165 long int length ) 1166 { 1167 const uint8_t *in = (const uint8_t*)vin; 1168 uint64_t temp; 1170 if ( ctx && in ) 1171 { 1172 if ( length < 0 ) 1173 return fnvBadParam; 1174 switch ( ctx->Computed ) 1175 { 1176 case FNVinited+FNV64state: 1177 ctx->Computed = FNVcomputed+FNV64state; 1178 case FNVcomputed+FNV64state: 1179 break; 1180 default: 1181 return fnvStateError; 1182 } 1183 for ( temp = ctx->Hash; length > 0; length-- ) 1184 temp = FNV64prime * ( temp ^ *in++ ); 1185 ctx->Hash = temp; 1186 return fnvSuccess; 1187 } 1188 return fnvNull; 1189 } /* end FNV64input */ 1191 /* hash in a zero terminated string not including the zero (64 bit) 1192 ********************************************************************/ 1193 int FNV64stringin ( FNV64context * const ctx, 1194 const char *in ) 1195 { 1196 uint64_t temp; 1197 uint8_t ch; 1199 if ( ctx && in ) 1200 { 1201 switch ( ctx->Computed ) 1202 { 1203 case FNVinited+FNV64state: 1204 ctx->Computed = FNVcomputed+FNV64state; 1205 case FNVcomputed+FNV64state: 1206 break; 1207 default: 1208 return fnvStateError; 1209 } 1210 temp = ctx->Hash; 1211 while ( (ch = *in++) ) 1212 temp = FNV64prime * ( temp ^ ch ); 1213 ctx->Hash = temp; 1214 return fnvSuccess; 1215 } 1216 return fnvNull; 1217 } /* end FNV64stringin */ 1219 /* return hash (64 bit) 1220 ********************************************************************/ 1221 int FNV64result ( FNV64context * const ctx, 1222 uint64_t * const out ) 1223 { 1224 if ( ctx && out ) 1225 { 1226 if ( ctx->Computed != FNVcomputed+FNV64state ) 1227 return fnvStateError; 1228 ctx->Computed = FNVemptied+FNV64state; 1229 #ifdef FNV_BigEndian 1230 FNV64reverse ( out, ctx->Hash ); 1231 #else 1232 *out = ctx->Hash; 1233 #endif 1234 ctx->Hash = 0; 1235 return fnvSuccess; 1236 } 1237 return fnvNull; 1238 } /* end FNV64result */ 1240 /****************************************************************** 1241 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1242 ******************************************************************/ 1243 #else /* FNV_64bitIntegers */ 1244 /****************************************************************** 1245 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1246 ******************************************************************/ 1248 /* 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 */ 1249 /* #define FNV64prime 0x00000100000001B3 */ 1250 #define FNV64primeX 0x01B3 1251 #define FNV64shift 8 1253 /* #define FNV64basis 0xCBF29CE484222325 */ 1254 #define FNV64basis0 0xCBF2 1255 #define FNV64basis1 0x9CE4 1256 #define FNV64basis2 0x8422 1257 #define FNV64basis3 0x2325 1259 /* FNV64 hash a null terminated string (32 bit) 1260 ********************************************************************/ 1261 int FNV64string ( const char *in, uint8_t out[FNV64size] ) 1262 { 1263 FNV64context ctx; 1264 int err; 1266 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 1267 return err; 1268 if ( ( err = FNV64stringin (&ctx, in) ) != fnvSuccess ) 1269 return err; 1270 return FNV64result (&ctx, out); 1271 } /* end FNV64string */ 1273 /* FNV64 hash a counted block (32 bit) 1274 ********************************************************************/ 1275 int FNV64block ( const void *in, 1276 long int length, 1277 uint8_t out[FNV64size] ) 1278 { 1279 FNV64context ctx; 1280 int err; 1282 if ( ( err = FNV64init (&ctx) ) != fnvSuccess ) 1283 return err; 1284 if ( ( err = FNV64blockin (&ctx, in, length) ) != fnvSuccess ) 1285 return err; 1287 return FNV64result (&ctx, out); 1288 } /* end FNV64block */ 1290 /******************************************************************** 1291 * Set of init, input, and output functions below * 1292 * to incrementally compute FNV64 * 1293 ********************************************************************/ 1295 /* initialize context (32 bit) 1296 ********************************************************************/ 1297 int FNV64init ( FNV64context * const ctx ) 1298 { 1299 if ( ctx ) 1300 { 1301 ctx->Hash[0] = FNV64basis0; 1302 ctx->Hash[1] = FNV64basis1; 1303 ctx->Hash[2] = FNV64basis2; 1304 ctx->Hash[3] = FNV64basis3; 1305 ctx->Computed = FNVinited+FNV64state; 1306 return fnvSuccess; 1307 } 1308 return fnvNull; 1309 } /* end FNV64init */ 1311 /* initialize context (32 bit) 1312 ********************************************************************/ 1313 int FNV64initBasis ( FNV64context * const ctx, 1314 const uint8_t basis[FNV64size] ) 1315 { 1316 if ( ctx ) 1317 { 1318 #ifdef FNV_BigEndian 1319 ctx->Hash[0] = basis[1] + ( basis[0]<<8 ); 1320 ctx->Hash[1] = basis[3] + ( basis[2]<<8 ); 1321 ctx->Hash[2] = basis[5] + ( basis[4]<<8 ); 1322 ctx->Hash[3] = basis[7] + ( basis[6]<<8 ); 1323 #else 1324 ctx->Hash[0] = basis[0] + ( basis[1]<<8 ); 1325 ctx->Hash[1] = basis[2] + ( basis[3]<<8 ); 1326 ctx->Hash[2] = basis[4] + ( basis[5]<<8 ); 1327 ctx->Hash[3] = basis[6] + ( basis[7]<<8 ); 1328 #endif 1329 ctx->Computed = FNVinited+FNV64state; 1330 return fnvSuccess; 1331 } 1332 return fnvNull; 1333 } /* end FNV64initBasis */ 1335 /* hash in a counted block (32 bit) 1336 ********************************************************************/ 1337 int FNV64blockin ( FNV64context * const ctx, 1338 const void *vin, 1339 long int length ) 1340 { 1341 const uint8_t *in = (const uint8_t*)vin; 1342 uint32_t temp[FNV64size/2]; 1343 uint32_t temp2[2]; 1344 int i; 1346 if ( ctx && in ) 1347 { 1348 if ( length < 0 ) 1349 return fnvBadParam; 1350 switch ( ctx->Computed ) 1351 { 1352 case FNVinited+FNV64state: 1353 ctx->Computed = FNVcomputed+FNV64state; 1354 case FNVcomputed+FNV64state: 1355 break; 1356 default: 1357 return fnvStateError; 1358 } 1359 for ( i=0; iHash[i]; 1361 for ( ; length > 0; length-- ) 1362 { 1363 /* temp = FNV64prime * ( temp ^ *in++ ); */ 1364 temp2[1] = temp[3] << FNV64shift; 1365 temp2[0] = temp[2] << FNV64shift; 1366 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 1367 temp[2] *= FNV64primeX; 1368 temp[1] = temp[1] * FNV64primeX + temp2[1]; 1369 temp[0] = temp[0] * FNV64primeX + temp2[0]; 1370 temp[2] += temp[3] >> 16; 1371 temp[3] &= 0xFFFF; 1372 temp[1] += temp[2] >> 16; 1373 temp[2] &= 0xFFFF; 1374 temp[0] += temp[1] >> 16; 1375 temp[1] &= 0xFFFF; 1376 } 1377 for ( i=0; iHash[i] = temp[i]; 1379 return fnvSuccess; 1380 } 1381 return fnvNull; 1382 } /* end FNV64blockin */ 1384 /* hash in a string (32 bit) 1385 ********************************************************************/ 1387 int FNV64stringin ( FNV64context * const ctx, 1388 const char *in ) 1389 { 1390 uint32_t temp[FNV64size/2]; 1391 uint32_t temp2[2]; 1392 int i; 1393 uint8_t ch; 1395 if ( ctx && in ) 1396 { 1397 switch ( ctx->Computed ) 1398 { 1399 case FNVinited+FNV64state: 1400 ctx->Computed = FNVcomputed+FNV64state; 1401 case FNVcomputed+FNV64state: 1402 break; 1403 default: 1404 return fnvStateError; 1405 } 1406 for ( i=0; iHash[i]; 1408 while ( ( ch = (uint8_t)*in++ ) != 0) 1409 { 1410 /* temp = FNV64prime * ( temp ^ ch ); */ 1411 temp2[1] = temp[3] << FNV64shift; 1412 temp2[0] = temp[2] << FNV64shift; 1413 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 1414 temp[2] *= FNV64primeX; 1415 temp[1] = temp[1] * FNV64primeX + temp2[1]; 1416 temp[0] = temp[0] * FNV64primeX + temp2[0]; 1417 temp[2] += temp[3] >> 16; 1418 temp[3] &= 0xFFFF; 1419 temp[1] += temp[2] >> 16; 1420 temp[2] &= 0xFFFF; 1421 temp[0] += temp[1] >> 16; 1422 temp[1] &= 0xFFFF; 1423 } 1424 for ( i=0; iHash[i] = temp[i]; 1426 return fnvSuccess; 1427 } 1428 return fnvNull; 1429 } /* end FNV64stringin */ 1431 /* return hash (32 bit) 1432 ********************************************************************/ 1433 int FNV64result ( FNV64context * const ctx, 1434 uint8_t out[FNV64size] ) 1435 { 1436 int i; 1437 if ( ctx && out ) 1438 { 1439 if ( ctx->Computed != FNVcomputed+FNV64state ) 1440 return fnvStateError; 1441 for ( i=0; iHash[i]; 1445 out[6-2*i] = ctx->Hash[i] >> 8; 1446 #else 1447 out[2*i] = ctx->Hash[i]; 1448 out[2*i+1] = ctx->Hash[i] >> 8; 1449 #endif 1450 ctx -> Hash[i] = 0; 1451 } 1452 ctx->Computed = FNVemptied+FNV64state; 1453 return fnvSuccess; 1454 } 1455 return fnvNull; 1456 } /* end FNV64result */ 1458 #endif /* FNV_64bitIntegers */ 1459 /******************************************************************** 1460 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1461 ********************************************************************/ 1463 #endif /* _FNV64_C_ */ 1464 1466 6.1.3 FNV128 C Code 1468 The header and C source for 128-bit FNV-1a. 1470 1471 /**************************** FNV128.h **************************/ 1472 /***************** See RFC NNNN for details. ********************/ 1473 /* 1474 * Copyright (c) 2016 IETF Trust and the persons identified as 1475 * authors of the code. All rights reserved. 1476 * See fnv-private.h for terms of use and redistribution. 1477 */ 1479 #ifndef _FNV128_H_ 1480 #define _FNV128_H_ 1482 /* 1483 * Description: 1484 * This file provides headers for the 128-bit version of the 1485 * FNV-1a non-cryptographic hash algorithm. 1486 */ 1488 #include "FNVconfig.h" 1490 #include 1491 #define FNV128size (128/8) 1493 /* If you do not have the ISO standard stdint.h header file, then you 1494 * must typedef the following types: 1495 * 1496 * type meaning 1497 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 1498 * uint32_t unsigned 32 bit integer 1499 * uint16_t unsigned 16 bit integer 1500 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 1501 */ 1503 #ifndef _FNV_ErrCodes_ 1504 #define _FNV_ErrCodes_ 1505 /********************************************************************* 1506 * All FNV functions provided return as integer as follows: 1507 * 0 -> success 1508 * >0 -> error as listed below 1509 */ 1510 enum { /* success and errors */ 1511 fnvSuccess = 0, 1512 fnvNull, /* Null pointer parameter */ 1513 fnvStateError, /* called Input after Result or before Init */ 1514 fnvBadParam /* passed a bad parameter */ 1515 }; 1516 #endif /* _FNV_ErrCodes_ */ 1518 /* 1519 * This structure holds context information for an FNV128 hash 1520 */ 1521 #ifdef FNV_64bitIntegers 1522 /* version if 64 bit integers supported */ 1523 typedef struct FNV128context_s { 1524 int Computed; /* state */ 1525 uint32_t Hash[FNV128size/4]; 1526 } FNV128context; 1528 #else 1529 /* version if 64 bit integers NOT supported */ 1531 typedef struct FNV128context_s { 1532 int Computed; /* state */ 1533 uint16_t Hash[FNV128size/2]; 1534 } FNV128context; 1535 #endif /* FNV_64bitIntegers */ 1537 /* 1538 * Function Prototypes 1539 * FNV128string: hash a zero terminated string not including 1540 * the terminating zero 1541 * FNV128block: FNV128 hash a specified length byte vector 1542 * FNV128init: initializes an FNV128 context 1543 * FNV128initBasis: initializes an FNV128 context with a 1544 * provided basis 1545 * FNV128blockin: hash in a specified length byte vector 1546 * FNV128stringin: hash in a zero terminated string not 1547 * including the zero 1548 * FNV128result: returns the hash value 1549 * 1550 * Hash is returned as an array of 8-bit integers 1551 */ 1553 #ifdef __cplusplus 1554 extern "C" { 1555 #endif 1557 /* FNV128 */ 1558 extern int FNV128string ( const char *in, 1559 uint8_t out[FNV128size] ); 1560 extern int FNV128block ( const void *in, 1561 long int length, 1562 uint8_t out[FNV128size] ); 1563 extern int FNV128init ( FNV128context * const ); 1564 extern int FNV128initBasis ( FNV128context * const, 1565 const uint8_t basis[FNV128size] ); 1566 extern int FNV128blockin ( FNV128context * const, 1567 const void *in, 1568 long int length ); 1569 extern int FNV128stringin ( FNV128context * const, 1570 const char *in ); 1571 extern int FNV128result ( FNV128context * const, 1572 uint8_t out[FNV128size] ); 1574 #ifdef __cplusplus 1575 } 1576 #endif 1578 #endif /* _FNV128_H_ */ 1579 1581 1582 /***************************** FNV128.c ****************************/ 1583 /******************** See RFC NNNN for details *********************/ 1584 /* Copyright (c) 2016 IETF Trust and the persons identified as 1585 * authors of the code. All rights 1586 * See fnv-private.h for terms of use and redistribution. 1587 */ 1589 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 1590 * hash function FNV-1a for 128-bit hashes. 1591 */ 1593 #ifndef _FNV128_C_ 1594 #define _FNV128_C_ 1596 #include "fnv-private.h" 1597 #include "FNV128.h" 1599 /* common code for 64 and 32 bit modes */ 1601 /* FNV128 hash a null terminated string (64/32 bit) 1602 ********************************************************************/ 1603 int FNV128string ( const char *in, uint8_t out[FNV128size] ) 1604 { 1605 FNV128context ctx; 1606 int err; 1608 err = FNV128init ( &ctx ); 1609 if ( err != fnvSuccess ) return err; 1610 err = FNV128stringin ( &ctx, in ); 1611 if ( err != fnvSuccess ) return err; 1612 return FNV128result (&ctx, out); 1613 } /* end FNV128string */ 1615 /* FNV128 hash a counted block (64/32 bit) 1616 ********************************************************************/ 1617 int FNV128block ( const void *in, 1618 long int length, 1619 uint8_t out[FNV128size] ) 1620 { 1621 FNV128context ctx; 1622 int err; 1624 err = FNV128init ( &ctx ); 1625 if ( err != fnvSuccess ) return err; 1626 err = FNV128blockin ( &ctx, in, length ); 1627 if ( err != fnvSuccess ) return err; 1628 return FNV128result ( &ctx, out ); 1629 } /* end FNV128block */ 1631 /******************************************************************** 1632 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1633 ********************************************************************/ 1635 #ifdef FNV_64bitIntegers 1637 /* 128 bit FNV_prime = 2^88 + 2^8 + 0x3b */ 1638 /* 0x00000000 01000000 00000000 0000013B */ 1639 #define FNV128primeX 0x013B 1640 #define FNV128shift 24 1642 /* 0x6C62272E 07BB0142 62B82175 6295C58D */ 1643 #define FNV128basis0 0x6C62272E 1644 #define FNV128basis1 0x07BB0142 1645 #define FNV128basis2 0x62B82175 1646 #define FNV128basis3 0x6295C58D 1648 /******************************************************************** 1649 * Set of init, input, and output functions below * 1650 * to incrementally compute FNV128 * 1651 ********************************************************************/ 1653 /* initialize context (64 bit) 1654 ********************************************************************/ 1655 int FNV128init ( FNV128context * const ctx ) 1656 { 1657 if ( ctx ) 1658 { 1659 ctx->Hash[0] = FNV128basis0; 1660 ctx->Hash[1] = FNV128basis1; 1661 ctx->Hash[2] = FNV128basis2; 1662 ctx->Hash[3] = FNV128basis3; 1663 ctx->Computed = FNVinited+FNV128state; 1664 return fnvSuccess; 1665 } 1666 return fnvNull; 1667 } /* end FNV128init */ 1669 /* initialize context with a provided basis (64 bit) 1670 ********************************************************************/ 1671 int FNV128initBasis ( FNV128context * const ctx, 1672 const uint8_t basis[FNV128size] ) 1673 { 1674 int i; 1675 const uint8_t *ui8p; 1676 uint32_t temp; 1678 if ( ctx ) 1679 { 1680 #ifdef FNV_BigEndian 1681 ui8p = basis; 1682 for ( i=0; i < FNV128size/4; ++i ) 1683 { 1684 temp = (*ui8p++)<<8; 1685 temp = (temp + *ui8p++)<<8; 1686 temp = (temp + *ui8p++)<<8; 1687 ctx->Hash[i] = temp + *ui8p; 1688 } 1689 #else 1690 ui8p = basis + ( FNV128size/4 - 1 ); 1691 for ( i=0; i < FNV128size/4; ++i ) 1692 { 1693 temp = (*ui8p--)<<8; 1694 temp = (temp + *ui8p--)<<8; 1695 temp = (temp + *ui8p--)<<8; 1696 ctx->Hash[i] = temp + *ui8p; 1697 } 1698 #endif 1699 ctx->Computed = FNVinited+FNV128state; 1700 return fnvSuccess; 1701 } 1702 return fnvNull; 1703 } /* end FNV128initBasis */ 1705 /* hash in a counted block (64 bit) 1706 ********************************************************************/ 1707 int FNV128blockin ( FNV128context * const ctx, 1708 const void *vin, 1709 long int length ) 1710 { 1711 const uint8_t *in = (const uint8_t*)vin; 1712 uint64_t temp[FNV128size/4]; 1713 uint64_t temp2[2]; 1714 int i; 1716 if ( ctx && in ) 1717 { 1718 if ( length < 0 ) 1719 return fnvBadParam; 1720 switch ( ctx->Computed ) 1721 { 1722 case FNVinited+FNV128state: 1723 ctx->Computed = FNVcomputed+FNV128state; 1724 case FNVcomputed+FNV128state: 1725 break; 1726 default: 1727 return fnvStateError; 1728 } 1729 for ( i=0; iHash[i]; 1731 for ( ; length > 0; length-- ) 1732 { 1733 /* temp = FNV128prime * ( temp ^ *in++ ); */ 1734 temp2[1] = temp[3] << FNV128shift; 1735 temp2[0] = temp[2] << FNV128shift; 1736 temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); 1737 temp[2] *= FNV128primeX; 1738 temp[1] = temp[1] * FNV128primeX + temp2[1]; 1739 temp[0] = temp[0] * FNV128primeX + temp2[0]; 1740 temp[2] += temp[3] >> 32; 1741 temp[3] &= 0xFFFFFFFF; 1742 temp[1] += temp[2] >> 32; 1743 temp[2] &= 0xFFFFFFFF; 1744 temp[0] += temp[1] >> 32; 1745 temp[1] &= 0xFFFFFFFF; 1746 } 1747 for ( i=0; iHash[i] = temp[i]; 1749 return fnvSuccess; 1750 } 1751 return fnvNull; 1752 } /* end FNV128input */ 1754 /* hash in a string (64 bit) 1755 ********************************************************************/ 1756 int FNV128stringin ( FNV128context * const ctx, const char *in ) 1757 { 1758 uint64_t temp[FNV128size/4]; 1759 uint64_t temp2[2]; 1760 int i; 1761 uint8_t ch; 1763 if ( ctx && in ) 1764 { 1765 switch ( ctx->Computed ) 1766 { 1767 case FNVinited+FNV128state: 1768 ctx->Computed = FNVcomputed+FNV128state; 1769 case FNVcomputed+FNV128state: 1770 break; 1771 default: 1772 return fnvStateError; 1773 } 1774 for ( i=0; iHash[i]; 1776 while ( (ch = (uint8_t)*in++) ) 1777 { 1778 /* temp = FNV128prime * ( temp ^ ch ); */ 1779 temp2[1] = temp[3] << FNV128shift; 1780 temp2[0] = temp[2] << FNV128shift; 1781 temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); 1782 temp[2] *= FNV128primeX; 1783 temp[1] = temp[1] * FNV128primeX + temp2[1]; 1784 temp[0] = temp[0] * FNV128primeX + temp2[0]; 1785 temp[2] += temp[3] >> 32; 1786 temp[3] &= 0xFFFFFFFF; 1787 temp[1] += temp[2] >> 32; 1788 temp[2] &= 0xFFFFFFFF; 1789 temp[0] += temp[1] >> 32; 1790 temp[1] &= 0xFFFFFFFF; 1791 } 1792 for ( i=0; iHash[i] = temp[i]; 1794 return fnvSuccess; 1795 } 1796 return fnvNull; 1797 } /* end FNV128stringin */ 1799 /* return hash (64 bit) 1800 ********************************************************************/ 1801 int FNV128result ( FNV128context * const ctx, uint8_t out[FNV128size] ) 1802 { 1803 int i; 1805 if ( ctx && out ) 1806 { 1807 if ( ctx->Computed != FNVcomputed+FNV128state ) 1808 return fnvStateError; 1809 for ( i=0; iHash[i]; 1813 out[14-4*i] = ctx->Hash[i] >> 8; 1814 out[13-4*i] = ctx->Hash[i] >> 16; 1815 out[12-4*i] = ctx->Hash[i] >> 24; 1816 #else 1817 out[4*i] = ctx->Hash[i]; 1818 out[4*i+1] = ctx->Hash[i] >> 8; 1819 out[4*i+2] = ctx->Hash[i] >> 16; 1820 out[4*i+3] = ctx->Hash[i] >> 24; 1821 #endif 1822 ctx -> Hash[i] = 0; 1823 } 1824 ctx->Computed = FNVemptied+FNV128state; 1825 return fnvSuccess; 1826 } 1827 return fnvNull; 1828 } /* end FNV128result */ 1830 /****************************************************************** 1831 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1832 ******************************************************************/ 1833 #else /* FNV_64bitIntegers */ 1834 /****************************************************************** 1835 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1836 ******************************************************************/ 1838 /* 128 bit FNV_prime = 2^88 + 2^8 + 0x3b */ 1839 /* 0x00000000 01000000 00000000 0000013B */ 1840 #define FNV128primeX 0x013B 1841 #define FNV128shift 8 1843 /* 0x6C62272E 07BB0142 62B82175 6295C58D */ 1844 uint16_t FNV128basis[FNV128size/2] = 1845 { 0x6C62, 0x272E, 0x07BB, 0x0142, 1846 0x62B8, 0x2175, 0x6295, 0xC58D }; 1848 /******************************************************************** 1849 * Set of init, input, and output functions below * 1850 * to incrementally compute FNV128 * 1851 ********************************************************************/ 1853 /* initialize context (32 bit) 1854 ********************************************************************/ 1855 int FNV128init ( FNV128context *ctx ) 1856 { 1857 int i; 1859 if ( ctx ) 1860 { 1861 for ( i=0; iHash[i] = FNV128basis[i]; 1863 ctx->Computed = FNVinited+FNV128state; 1864 return fnvSuccess; 1865 } 1866 return fnvNull; 1867 } /* end FNV128init */ 1869 /* initialize context with a provided basis (32 bit) 1870 ********************************************************************/ 1871 int FNV128initBasis ( FNV128context *ctx, 1872 const uint8_t basis[FNV128size] ) 1873 { 1874 int i; 1875 const uint8_t *ui8p; 1876 uint32_t temp; 1878 if ( ctx ) 1879 { 1880 #ifdef FNV_BigEndian 1881 ui8p = basis; 1882 for ( i=0; i < FNV128size/2; ++i ) 1883 { 1884 temp = *ui8p++; 1885 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 1886 } 1887 #else 1888 ui8p = basis + (FNV128size/2 - 1); 1889 for ( i=0; i < FNV128size/2; ++i ) 1890 { 1891 temp = *ui8p--; 1892 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 1893 } 1894 #endif 1895 ctx->Computed = FNVinited+FNV128state; 1896 return fnvSuccess; 1897 } 1898 return fnvNull; 1899 } /* end FNV128initBasis */ 1901 /* hash in a counted block (32 bit) 1902 *******************************************************************/ 1903 int FNV128blockin ( FNV128context *ctx, 1904 const void *vin, 1905 long int length ) 1906 { 1907 const uint8_t *in = (const uint8_t*)vin; 1908 uint32_t temp[FNV128size/2]; 1909 uint32_t temp2[3]; 1910 int i; 1912 if ( ctx && in ) 1913 { 1914 if ( length < 0 ) 1915 return fnvBadParam; 1916 switch ( ctx->Computed ) 1917 { 1918 case FNVinited+FNV128state: 1919 ctx->Computed = FNVcomputed+FNV128state; 1920 case FNVcomputed+FNV128state: 1921 break; 1922 default: 1923 return fnvStateError; 1924 } 1925 for ( i=0; iHash[i]; 1927 for ( ; length > 0; length-- ) 1928 { 1929 /* temp = FNV128prime * ( temp ^ *in++ ); */ 1930 temp[7] ^= *in++; 1931 temp2[2] = temp[7] << FNV128shift; 1932 temp2[1] = temp[6] << FNV128shift; 1933 temp2[0] = temp[5] << FNV128shift; 1934 for ( i=0; i<8; ++i ) 1935 temp[i] *= FNV128primeX; 1936 temp[2] += temp2[2]; 1937 temp[1] += temp2[1]; 1938 temp[0] += temp2[0]; 1939 for ( i=7; i>0; --i ) 1940 { 1941 temp[i-1] += temp[i] >> 16; 1942 temp[i] &= 0xFFFF; 1943 } 1944 } 1945 for ( i=0; iHash[i] = temp[i]; 1947 return fnvSuccess; 1948 } 1949 return fnvNull; 1950 } /* end FNV128blockin */ 1952 /* hash in a string (32 bit) 1953 *******************************************************************/ 1954 int FNV128stringin ( FNV128context *ctx, 1955 const char *in ) 1956 { 1957 uint32_t temp[FNV128size/2]; 1958 uint32_t temp2[3]; 1959 int i; 1960 uint8_t ch; 1962 if ( ctx && in ) 1963 { 1964 switch ( ctx->Computed ) 1965 { 1966 case FNVinited+FNV128state: 1967 ctx->Computed = FNVcomputed+FNV128state; 1968 case FNVcomputed+FNV128state: 1969 break; 1970 default: 1971 return fnvStateError; 1972 } 1973 for ( i=0; iHash[i]; 1975 while ( (ch = (uint8_t)*in++) ) 1976 { 1977 /* temp = FNV128prime * ( temp ^ *in++ ); */ 1978 temp[7] ^= ch; 1979 temp2[2] = temp[7] << FNV128shift; 1980 temp2[1] = temp[6] << FNV128shift; 1981 temp2[0] = temp[5] << FNV128shift; 1982 for ( i=0; i<8; ++i ) 1983 temp[i] *= FNV128primeX; 1984 temp[2] += temp2[2]; 1985 temp[1] += temp2[1]; 1986 temp[0] += temp2[0]; 1987 for ( i=7; i>0; --i ) 1988 { 1989 temp[i-1] += temp[i] >> 16; 1990 temp[i] &= 0xFFFF; 1991 } 1992 } 1993 for ( i=0; iHash[i] = temp[i]; 1995 return fnvSuccess; 1996 } 1997 return fnvNull; 1998 } /* end FNV128stringin */ 2000 /* return hash (32 bit) 2001 ********************************************************************/ 2002 int FNV128result ( FNV128context *ctx, 2003 uint8_t out[FNV128size] ) 2004 { 2005 int i; 2007 if ( ctx && out ) 2008 { 2009 if ( ctx->Computed != FNVcomputed+FNV128state ) 2010 return fnvStateError; 2011 for ( i=0; iHash[i]; 2015 out[14-2*i] = ctx->Hash[i] >> 8; 2016 #else 2017 out[2*i] = ctx->Hash[i]; 2018 out[2*i+1] = ctx->Hash[i] >> 8; 2019 #endif 2020 ctx -> Hash[i] = 0; 2021 } 2022 ctx->Computed = FNVemptied+FNV128state; 2023 return fnvSuccess; 2024 } 2025 return fnvNull; 2026 } /* end FNV128result */ 2028 #endif /* Have64bitIntegers */ 2029 /******************************************************************** 2030 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2031 ********************************************************************/ 2033 #endif /* _FNV128_C_ */ 2034 2036 6.1.4 FNV256 C Code 2038 The header and C source for 256-bit FNV-1a. 2040 2041 /**************************** FNV256.h **************************/ 2042 /***************** See RFC NNNN for details. ********************/ 2043 /* 2044 * Copyright (c) 2016 IETF Trust and the persons identified as 2045 * authors of the code. All rights reserved. 2046 * See fnv-private.h for terms of use and redistribution. 2047 */ 2049 #ifndef _FNV256_H_ 2050 #define _FNV256_H_ 2052 /* 2053 * Description: 2054 * This file provides headers for the 256-bit version of the 2055 * FNV-1a non-cryptographic hash algorithm. 2056 */ 2058 #include "FNVconfig.h" 2060 #include 2061 #define FNV256size (256/8) 2063 /* If you do not have the ISO standard stdint.h header file, then you 2064 * must typedef the following types: 2065 * 2066 * type meaning 2067 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 2068 * uint32_t unsigned 32 bit integer 2069 * uint16_t unsigned 16 bit integer 2070 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 2071 */ 2073 #ifndef _FNV_ErrCodes_ 2074 #define _FNV_ErrCodes_ 2075 /********************************************************************* 2076 * All FNV functions provided return as integer as follows: 2077 * 0 -> success 2078 * >0 -> error as listed below 2079 */ 2080 enum { /* success and errors */ 2081 fnvSuccess = 0, 2082 fnvNull, /* Null pointer parameter */ 2083 fnvStateError, /* called Input after Result or before Init */ 2084 fnvBadParam /* passed a bad parameter */ 2085 }; 2086 #endif /* _FNV_ErrCodes_ */ 2088 /* 2089 * This structure holds context information for an FNV256 hash 2090 */ 2091 #ifdef FNV_64bitIntegers 2092 /* version if 64 bit integers supported */ 2093 typedef struct FNV256context_s { 2094 int Computed; /* state */ 2095 uint32_t Hash[FNV256size/4]; 2096 } FNV256context; 2098 #else 2099 /* version if 64 bit integers NOT supported */ 2101 typedef struct FNV256context_s { 2102 int Computed; /* state */ 2103 uint16_t Hash[FNV256size/2]; 2104 } FNV256context; 2106 #endif /* FNV_64bitIntegers */ 2108 /* 2109 * Function Prototypes 2110 * FNV256string: hash a zero terminated string not including 2111 * the zero 2112 * FNV256block: FNV256 hash a specified length byte vector 2113 * FNV256init: initializes an FNV256 context 2114 * FNV256initBasis: initializes an FNV256 context with a provided 2115 * basis 2116 * FNV256blockin: hash in a specified length byte vector 2117 * FNV256stringin: hash in a zero terminated string not 2118 * including the zero 2119 * FNV256result: returns the hash value 2120 * 2121 * Hash is returned as an array of 8-bit integers 2122 */ 2124 #ifdef __cplusplus 2125 extern "C" { 2126 #endif 2128 /* FNV256 */ 2129 extern int FNV256string ( const char *in, 2130 uint8_t out[FNV256size] ); 2131 extern int FNV256block ( const void *in, 2132 long int length, 2133 uint8_t out[FNV256size] ); 2134 extern int FNV256init ( FNV256context *); 2135 extern int FNV256initBasis ( FNV256context * const, 2136 const uint8_t basis[FNV256size] ); 2137 extern int FNV256blockin ( FNV256context * const, 2138 const void *in, 2139 long int length ); 2140 extern int FNV256stringin ( FNV256context * const, 2141 const char *in ); 2142 extern int FNV256result ( FNV256context * const, 2143 uint8_t out[FNV256size] ); 2145 #ifdef __cplusplus 2146 } 2147 #endif 2149 #endif /* _FNV256_H_ */ 2150 2152 2153 /***************************** FNV256.c ****************************/ 2154 /******************** See RFC NNNN for details *********************/ 2155 /* Copyright (c) 2016 IETF Trust and the persons identified as 2156 * authors of the code. All rights 2157 * See fnv-private.h for terms of use and redistribution. 2158 */ 2160 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 2161 * hash function FNV-1a for 256-bit hashes. 2162 */ 2164 #ifndef _FNV256_C_ 2165 #define _FNV256_C_ 2167 #include "fnv-private.h" 2168 #include "FNV256.h" 2170 /* common code for 64 and 32 bit modes */ 2172 /* FNV256 hash a null terminated string (64/32 bit) 2173 ********************************************************************/ 2174 int FNV256string ( const char *in, uint8_t out[FNV256size] ) 2175 { 2176 FNV256context ctx; 2177 int err; 2179 if ( (err = FNV256init ( &ctx )) != fnvSuccess ) 2180 return err; 2181 if ( (err = FNV256stringin ( &ctx, in )) != fnvSuccess ) 2182 return err; 2183 return FNV256result ( &ctx, out ); 2184 } /* end FNV256string */ 2185 /* FNV256 hash a counted block (64/32 bit) 2186 ********************************************************************/ 2187 int FNV256block ( const void *in, 2188 long int length, 2189 uint8_t out[FNV256size] ) 2190 { 2191 FNV256context ctx; 2192 int err; 2194 if ( (err = FNV256init ( &ctx )) != fnvSuccess ) 2195 return err; 2196 if ( (err = FNV256blockin ( &ctx, in, length)) != fnvSuccess ) 2197 return err; 2198 return FNV256result ( &ctx, out ); 2199 } /* end FNV256block */ 2201 /******************************************************************** 2202 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2203 ********************************************************************/ 2204 #ifdef FNV_64bitIntegers 2206 /* 256 bit FNV_prime = 2^168 + 2^8 + 0x63 */ 2207 /* 0x0000000000000000 0000010000000000 2208 0000000000000000 0000000000000163 */ 2209 #define FNV256primeX 0x0163 2210 #define FNV256shift 8 2212 /* 0xDD268DBCAAC55036 2D98C384C4E576CC 2213 C8B1536847B6BBB3 1023B4C8CAEE0535 */ 2214 uint32_t FNV256basis[FNV256size/4] = { 2215 0xDD268DBC, 0xAAC55036, 0x2D98C384, 0xC4E576CC, 2216 0xC8B15368, 0x47B6BBB3, 0x1023B4C8, 0xCAEE0535 }; 2218 /******************************************************************** 2219 * Set of init, input, and output functions below * 2220 * to incrementally compute FNV256 * 2221 ********************************************************************/ 2223 /* initialize context (64 bit) 2224 ********************************************************************/ 2225 int FNV256init ( FNV256context *ctx ) 2226 { 2227 int i; 2229 if ( ctx ) 2230 { 2231 for ( i=0; iHash[i] = FNV256basis[i]; 2233 ctx->Computed = FNVinited+FNV256state; 2234 return fnvSuccess; 2235 } 2236 return fnvNull; 2237 } /* end FNV256init */ 2239 /* initialize context with a provided basis (64 bit) 2240 ********************************************************************/ 2241 int FNV256initBasis ( FNV256context* const ctx, 2242 const uint8_t basis[FNV256size] ) 2243 { 2244 int i; 2245 const uint8_t *ui8p; 2246 uint32_t temp; 2248 if ( ctx ) 2249 { 2250 #ifdef FNV_BigEndian 2251 ui8p = basis; 2252 for ( i=0; i < FNV256size/4; ++i ) 2253 { 2254 temp = (*ui8p++)<<8; 2255 temp = (temp + *ui8p++)<<8; 2256 temp = (temp + *ui8p++)<<8; 2257 ctx->Hash[i] = temp + *ui8p; 2258 } 2259 #else 2260 ui8p = basis + (FNV256size/4 - 1); 2261 for ( i=0; i < FNV256size/4; ++i ) 2262 { 2263 temp = (*ui8p--)<<8; 2264 temp = (temp + *ui8p--)<<8; 2265 temp = (temp + *ui8p--)<<8; 2266 ctx->Hash[i] = temp + *ui8p; 2267 } 2268 #endif 2269 ctx->Computed = FNVinited+FNV256state; 2270 return fnvSuccess; 2271 } 2272 return fnvNull; 2273 } /* end FNV256initBasis */ 2275 /* hash in a counted block (64 bit) 2276 ********************************************************************/ 2277 int FNV256blockin ( FNV256context *ctx, 2278 const void *vin, 2279 long int length ) 2280 { 2281 const uint8_t *in = (const uint8_t*)vin; 2282 uint64_t temp[FNV256size/4]; 2283 uint64_t temp2[3]; 2284 int i; 2286 if ( ctx && in ) 2287 { 2288 if ( length < 0 ) 2289 return fnvBadParam; 2290 switch ( ctx->Computed ) 2291 { 2292 case FNVinited+FNV256state: 2293 ctx->Computed = FNVcomputed+FNV256state; 2294 case FNVcomputed+FNV256state: 2295 break; 2296 default: 2297 return fnvStateError; 2298 } 2299 for ( i=0; iHash[i]; 2301 for ( ; length > 0; length-- ) 2302 { 2303 /* temp = FNV256prime * ( temp ^ *in++ ); */ 2304 temp[7] ^= *in++; 2305 temp2[2] = temp[7] << FNV256shift; 2306 temp2[1] = temp[6] << FNV256shift; 2307 temp2[0] = temp[5] << FNV256shift; 2308 for ( i=0; i0; --i ) 2314 { 2315 temp[i-1] += temp[i] >> 16; 2316 temp[i] &= 0xFFFF; 2317 } 2318 } 2319 for ( i=0; iHash[i] = temp[i]; 2321 return fnvSuccess; 2322 } 2323 return fnvNull; 2324 } /* end FNV256input */ 2326 /* hash in a string (64 bit) 2327 ********************************************************************/ 2328 int FNV256stringin ( FNV256context *ctx, const char *in ) 2329 { 2330 uint64_t temp[FNV256size/4]; 2331 uint64_t temp2[3]; 2332 int i; 2333 uint8_t ch; 2334 if ( ctx && in ) 2335 { 2336 switch ( ctx->Computed ) 2337 { 2338 case FNVinited+FNV256state: 2339 ctx->Computed = FNVcomputed+FNV256state; 2340 case FNVcomputed+FNV256state: 2341 break; 2342 default: 2343 return fnvStateError; 2344 } 2345 for ( i=0; iHash[i]; 2347 while ( (ch = (uint8_t)*in++) ) 2348 { 2349 /* temp = FNV256prime * ( temp ^ ch ); */ 2350 temp[7] ^= ch; 2351 temp2[2] = temp[7] << FNV256shift; 2352 temp2[1] = temp[6] << FNV256shift; 2353 temp2[0] = temp[5] << FNV256shift; 2354 for ( i=0; i0; --i ) 2360 { 2361 temp[i-1] += temp[i] >> 16; 2362 temp[i] &= 0xFFFF; 2363 } 2364 } 2365 for ( i=0; iHash[i] = temp[i]; 2367 return fnvSuccess; 2368 } 2369 return fnvNull; 2370 } /* end FNV256stringin */ 2372 /* return hash (64 bit) 2373 ********************************************************************/ 2374 int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] ) 2375 { 2376 int i; 2378 if ( ctx && out ) 2379 { 2380 if ( ctx->Computed != FNVcomputed+FNV256state ) 2381 return fnvStateError; 2382 for ( i=0; iHash[i]; 2387 out[31-4*i] = ctx->Hash[i] >> 8; 2388 out[31-4*i] = ctx->Hash[i] >> 16; 2389 out[31-4*i] = ctx->Hash[i] >> 24; 2390 #else 2391 out[4*i] = ctx->Hash[i]; 2392 out[4*i+1] = ctx->Hash[i] >> 8; 2393 out[4*i+2] = ctx->Hash[i] >> 16; 2394 out[4*i+3] = ctx->Hash[i] >> 24; 2395 #endif 2396 ctx -> Hash[i] = 0; 2397 } 2398 ctx->Computed = FNVemptied+FNV256state; 2399 return fnvSuccess; 2400 } 2401 return fnvNull; 2402 } /* end FNV256result */ 2404 /****************************************************************** 2405 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2406 ******************************************************************/ 2407 #else /* FNV_64bitIntegers */ 2408 /****************************************************************** 2409 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2410 ******************************************************************/ 2412 /* version for when you only have 32-bit arithmetic 2413 ********************************************************************/ 2415 /* 256 bit FNV_prime = 2^168 + 2^8 + 0x63 */ 2416 /* 0x00000000 00000000 00000100 00000000 2417 00000000 00000000 00000000 00000163 */ 2418 #define FNV256primeX 0x0163 2419 #define FNV256shift 8 2421 /* 0xDD268DBCAAC55036 2D98C384C4E576CC 2422 C8B1536847B6BBB3 1023B4C8CAEE0535 */ 2423 uint16_t FNV256basis[FNV256size/2] = { 2424 0xDD26, 0x8DBC, 0xAAC5, 0x5036, 2425 0x2D98, 0xC384, 0xC4E5, 0x76CC, 2426 0xC8B1, 0x5368, 0x47B6, 0xBBB3, 2427 0x1023, 0xB4C8, 0xCAEE, 0x0535 }; 2429 /******************************************************************** 2430 * Set of init, input, and output functions below * 2431 * to incrementally compute FNV256 * 2432 ********************************************************************/ 2434 /* initialize context (32 bit) 2435 ********************************************************************/ 2436 int FNV256init ( FNV256context *ctx ) 2437 { 2438 int i; 2440 if ( ctx ) 2441 { 2442 for ( i=0; iHash[i] = FNV256basis[i]; 2444 ctx->Computed = FNVinited+FNV256state; 2445 return fnvSuccess; 2446 } 2447 return fnvNull; 2448 } /* end FNV256init */ 2450 /* initialize context with a provided basis (32 bit) 2451 ********************************************************************/ 2452 int FNV256initBasis ( FNV256context *ctx, 2453 const uint8_t basis[FNV256size] ) 2454 { 2455 int i; 2456 const uint8_t *ui8p; 2457 uint32_t temp; 2459 if ( ctx ) 2460 { 2461 #ifdef FNV_BigEndian 2462 ui8p = basis; 2463 for ( i=0; i < FNV256size/2; ++i ) 2464 { 2465 temp = *ui8p++; 2466 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 2467 } 2468 #else 2469 ui8p = basis + FNV256size/2 -1; 2470 for ( i=0; i < FNV256size/2; ++i ) 2471 { 2472 temp = *ui8p--; 2473 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 2474 } 2475 #endif 2476 ctx->Computed = FNVinited+FNV256state; 2477 return fnvSuccess; 2478 } 2479 return fnvNull; 2480 } /* end FNV256initBasis */ 2482 /* hash in a counted block (32 bit) 2483 *******************************************************************/ 2484 int FNV256blockin ( FNV256context *ctx, 2485 const void *vin, 2486 long int length ) 2487 { 2488 const uint8_t *in = (const uint8_t*)vin; 2489 uint32_t temp[FNV256size/2]; 2490 uint32_t temp2[6]; 2491 int i; 2493 if ( ctx && in ) 2494 { 2495 if ( length < 0 ) 2496 return fnvBadParam; 2497 switch ( ctx->Computed ) 2498 { 2499 case FNVinited+FNV256state: 2500 ctx->Computed = FNVcomputed+FNV256state; 2501 case FNVcomputed+FNV256state: 2502 break; 2503 default: 2504 return fnvStateError; 2505 } 2506 for ( i=0; iHash[i]; 2508 for ( ; length > 0; length-- ) 2509 { 2510 /* temp = FNV256prime * ( temp ^ *in++ ); */ 2511 temp[15] ^= *in++; 2512 for ( i=0; i<6; ++i ) 2513 temp2[i] = temp[10+i] << FNV256shift; 2514 for ( i=0; i0; --i ) 2519 { 2520 temp[i-1] += temp[i] >> 16; 2521 temp[i] &= 0xFFFF; 2522 } 2523 } 2524 for ( i=0; iHash[i] = temp[i]; 2526 return fnvSuccess; 2527 } 2528 return fnvNull; 2529 } /* end FNV256blockin */ 2531 /* hash in a string (32 bit) 2532 *******************************************************************/ 2533 int FNV256stringin ( FNV256context *ctx, const char *in ) 2534 { 2535 uint32_t temp[FNV256size/2]; 2536 uint32_t temp2[6]; 2537 int i; 2538 uint8_t ch; 2540 if ( ctx && in ) 2541 { 2542 switch ( ctx->Computed ) 2543 { 2544 case FNVinited+FNV256state: 2545 ctx->Computed = FNVcomputed+FNV256state; 2546 case FNVcomputed+FNV256state: 2547 break; 2548 default: 2549 return fnvStateError; 2550 } 2551 for ( i=0; iHash[i]; 2553 while ( ( ch = (uint8_t)*in++ ) != 0) 2554 { 2555 /* temp = FNV256prime * ( temp ^ *in++ ); */ 2556 temp[15] ^= ch; 2557 for ( i=0; i<6; ++i ) 2558 temp2[i] = temp[10+i] << FNV256shift; 2559 for ( i=0; i0; --i ) 2564 { 2565 temp[i-1] += temp[i] >> 16; 2566 temp[i] &= 0xFFFF; 2567 } 2568 } 2569 for ( i=0; iHash[i] = temp[i]; 2571 return fnvSuccess; 2572 } 2573 return fnvNull; 2574 } /* end FNV256stringin */ 2576 /* return hash (32 bit) 2577 ********************************************************************/ 2578 int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] ) 2579 { 2580 int i; 2582 if ( ctx && out ) 2583 { 2584 if ( ctx->Computed != FNVcomputed+FNV256state ) 2585 return fnvStateError; 2586 for ( i=0; iHash[i]; 2590 out[30-2*i] = ctx->Hash[i] >> 8; 2591 #else 2592 out[2*i] = ctx->Hash[i]; 2593 out[2*i+1] = ctx->Hash[i] >> 8; 2594 #endif 2595 ctx->Hash[i] = 0; 2596 } 2597 ctx->Computed = FNVemptied+FNV256state; 2598 return fnvSuccess; 2599 } 2600 return fnvNull; 2601 } /* end FNV256result */ 2603 #endif /* Have64bitIntegers */ 2604 /******************************************************************** 2605 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2606 ********************************************************************/ 2608 #endif /* _FNV256_C_ */ 2609 2611 6.1.5 FNV512 C Code 2613 The header and C source for 512-bit FNV-1a. 2615 2616 /**************************** FNV512.h **************************/ 2617 /***************** See RFC NNNN for details. ********************/ 2618 /* 2619 * Copyright (c) 2016 IETF Trust and the persons identified as 2620 * authors of the code. All rights reserved. 2621 * See fnv-private.h for terms of use and redistribution. 2622 */ 2624 #ifndef _FNV512_H_ 2625 #define _FNV512_H_ 2627 /* 2628 * Description: 2629 * This file provides headers for the 512-bit version of the 2630 * FNV-1a non-cryptographic hash algorithm. 2631 */ 2633 #include "FNVconfig.h" 2635 #include 2636 #define FNV512size (512/8) 2638 /* If you do not have the ISO standard stdint.h header file, then you 2639 * must typedef the following types: 2640 * 2641 * type meaning 2642 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 2643 * uint32_t unsigned 32 bit integer 2644 * uint16_t unsigned 16 bit integer 2645 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 2646 */ 2648 #ifndef _FNV_ErrCodes_ 2649 #define _FNV_ErrCodes_ 2650 /********************************************************************* 2651 * All FNV functions provided return as integer as follows: 2652 * 0 -> success 2653 * >0 -> error as listed below 2654 */ 2655 enum { /* success and errors */ 2656 fnvSuccess = 0, 2657 fnvNull, /* Null pointer parameter */ 2658 fnvStateError, /* called Input after Result or before Init */ 2659 fnvBadParam /* passed a bad parameter */ 2660 }; 2661 #endif /* _FNV_ErrCodes_ */ 2663 /* 2664 * This structure holds context information for an FNV512 hash 2665 */ 2666 #ifdef FNV_64bitIntegers 2667 /* version if 64 bit integers supported */ 2668 typedef struct FNV512context_s { 2669 int Computed; /* state */ 2670 uint32_t Hash[FNV512size/4]; 2671 } FNV512context; 2673 #else 2674 /* version if 64 bit integers NOT supported */ 2676 typedef struct FNV512context_s { 2677 int Computed; /* state */ 2678 uint16_t Hash[FNV512size/2]; 2679 } FNV512context; 2681 #endif /* FNV_64bitIntegers */ 2682 /* 2683 * Function Prototypes 2684 * FNV512string: hash a zero terminated string not including 2685 * the terminating zero 2686 * FNV512block: FNV512 hash a specified length byte vector 2687 * FNV512init: initializes an FNV512 context 2688 * FNV512initBasis: initializes an FNV512 context with a 2689 * provided basis 2690 * FNV512blockin: hash in a specified length byte vector 2691 * FNV512stringin: hash in a zero terminated string not 2692 * including the zero 2693 * FNV512result: returns the hash value 2694 * 2695 * Hash is returned as an array of 8-bit integers 2696 */ 2698 #ifdef __cplusplus 2699 extern "C" { 2700 #endif 2702 /* FNV512 */ 2703 extern int FNV512string ( const char *in, 2704 uint8_t out[FNV512size] ); 2705 extern int FNV512block ( const void *in, 2706 long int length, 2707 uint8_t out[FNV512size] ); 2708 extern int FNV512init ( FNV512context *); 2709 extern int FNV512initBasis ( FNV512context * const, 2710 const uint8_t basis[FNV512size] ); 2711 extern int FNV512blockin ( FNV512context *, 2712 const void *in, 2713 long int length ); 2714 extern int FNV512stringin ( FNV512context *, 2715 const char *in ); 2716 extern int FNV512result ( FNV512context *, 2717 uint8_t out[FNV512size] ); 2719 #ifdef __cplusplus 2720 } 2721 #endif 2723 #endif /* _FNV512_H_ */ 2724 2726 2727 /***************************** FNV512.c ****************************/ 2728 /******************** See RFC NNNN for details *********************/ 2729 /* Copyright (c) 2016 IETF Trust and the persons identified as 2730 * authors of the code. All rights 2731 * See fnv-private.h for terms of use and redistribution. 2733 */ 2735 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 2736 * hash function FNV-1a for 512-bit hashes. 2737 */ 2739 #ifndef _FNV512_C_ 2740 #define _FNV512_C_ 2742 #include "fnv-private.h" 2743 #include "FNV512.h" 2745 /* common code for 64 and 32 bit modes */ 2747 /* FNV512 hash a null terminated string (64/32 bit) 2748 ********************************************************************/ 2749 int FNV512string ( const char *in, uint8_t out[FNV512size] ) 2750 { 2751 FNV512context ctx; 2752 int err; 2754 if ( (err = FNV512init ( &ctx )) != fnvSuccess ) 2755 return err; 2756 if ( (err = FNV512stringin ( &ctx, in )) != fnvSuccess ) 2757 return err; 2758 return FNV512result ( &ctx, out ); 2759 } /* end FNV512string */ 2761 /* FNV512 hash a counted block (64/32 bit) 2762 ********************************************************************/ 2763 int FNV512block ( const void *in, 2764 long int length, 2765 uint8_t out[FNV512size] ) 2766 { 2767 FNV512context ctx; 2768 int err; 2770 if ( (err = FNV512init ( &ctx )) != fnvSuccess ) 2771 return err; 2772 if ( (err = FNV512blockin ( &ctx, in, length)) != fnvSuccess ) 2773 return err; 2774 return FNV512result ( &ctx, out ); 2775 } /* end FNV512block */ 2777 /******************************************************************** 2778 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2779 ********************************************************************/ 2780 #ifdef Have64bitIntegers 2781 /* 2782 512 bit FNV_prime = 2^344 + 2^8 + 0x57 = 2783 0x0000000000000000 0000000000000000 2784 0000000001000000 0000000000000000 2785 0000000000000000 0000000000000000 2786 0000000000000000 0000000000000157 */ 2787 #define FNV512primeX 0x0157 2788 #define FNV512shift 24 2790 /* 0xB86DB0B1171F4416 DCA1E50F309990AC 2791 AC87D059C9000000 0000000000000D21 2792 E948F68A34C192F6 2EA79BC942DBE7CE 2793 182036415F56E34B AC982AAC4AFE9FD9 */ 2795 uint32_t FNV512basis[FNV512size/4] = { 2796 0xB86DB0B1, 0x171F4416, 0xDCA1E50F, 0x209990AC, 2797 0xAC87D059, 0x9C000000, 0x00000000, 0x00000D21, 2798 0xE948F68A, 0x34C192F6, 0x2EA79BC9, 0x42DBE7CE, 2799 0x18203641, 0x5F56E34B, 0xAC982AAC, 0x4AFE9FD9 }; 2801 /******************************************************************** 2802 * Set of init, input, and output functions below * 2803 * to incrementally compute FNV512 * 2804 ********************************************************************/ 2806 /* initialize context (64 bit) 2807 ********************************************************************/ 2808 int FNV512init ( FNV512context *ctx ) 2809 { 2810 if ( ctx ) 2811 { 2812 for ( i=0; iHash[i] = FNV512basis[i]; 2814 ctx->Computed = FNVinited+FNV512state; 2815 return fnvSuccess; 2816 } 2817 return fnvNull; 2818 } /* end FNV512init */ 2820 /* initialize context with a provided basis (64 bit) 2821 ********************************************************************/ 2822 int FNV512initBasis ( FNV512context* const ctx, 2823 const uint8_t basis[FNV512size] ) 2824 { 2825 int i; 2826 const uint8_t *ui8p; 2827 uint32_t temp; 2829 if ( ctx ) 2830 { 2832 #ifdef FNV_BigEndian 2833 ui8p = basis; 2834 for ( i=0; i < FNV512size/4; ++i ) 2835 { 2836 temp = (*ui8p++)<<8; 2837 temp = (temp + *ui8p++)<<8; 2838 temp = (temp + *ui8p++)<<8; 2839 ctx->Hash[i] = temp + *ui8p; 2840 } 2841 #else 2842 ui8p = basis + (FNV512size/4 - 1); 2843 for ( i=0; i < FNV512size/4; ++i ) 2844 { 2845 temp = (*ui8p--)<<8; 2846 temp = (temp + *ui8p--)<<8; 2847 temp = (temp + *ui8p--)<<8; 2848 ctx->Hash[i] = temp + *ui8p; 2849 } 2850 #endif 2851 ctx->Computed = FNVinited+FNV512state; 2852 return fnvSuccess; 2853 } 2854 return fnvNull; 2855 } /* end FNV512initBasis */ 2857 /* hash in a counted block (64 bit) 2858 ********************************************************************/ 2859 int FNV512blockin ( FNV512context *ctx, 2860 const void *vin, 2861 long int length ) 2862 { 2863 const uint8_t *in = (const uint8_t*)vin; 2864 uint64_t temp[FNV512size/4]; 2865 uint64_t temp2[3]; 2867 if ( ctx && in ) 2868 { 2869 switch ( ctx->Computed ) 2870 { 2871 case FNVinited+FNV512state: 2872 ctx->Computed = FNVcomputed+FNV128state; 2873 case FNVcomputed+FNV512state: 2874 break; 2875 default: 2876 return fnvStateError; 2877 } 2878 if ( length < 0 ) 2879 return fnvBadParam; 2880 for ( i=0; iHash[i]; 2883 for ( ; length > 0; length-- ) 2884 { 2885 /* temp = FNV512prime * ( temp ^ *in++ ); */ 2886 temp[7] ^= *in++; 2887 temp2[2] = temp[7] << FNV512shift; 2888 temp2[1] = temp[6] << FNV512shift; 2889 temp2[0] = temp[5] << FNV512shift; 2890 for ( i=0; i0; --i ) 2896 { 2897 temp[i-1] += temp[i] >> 16; 2898 temp[i] &= 0xFFFF; 2899 } 2900 } 2901 for ( i=0; iHash[i] = temp[i]; 2903 return fnvSuccess; 2904 } 2905 return fnvNull; 2906 } /* end FNV512input */ 2908 /* hash in a string (64 bit) 2909 ********************************************************************/ 2910 inf FNV512stringin ( FNV512context *ctx, const char *in ) 2911 { 2912 uint64_t temp[FNV512size/4]; 2913 uint64_t temp2[2]; 2914 int i; 2915 uint8_t ch; 2917 if ( ctx && in ) 2918 { 2919 switch ( ctx->Computed ) 2920 { 2921 case FNVinited+FNV512state: 2922 ctx->Computed = FNVcomputed+FNV512state; 2923 case FNVcomputed+FNV512state: 2924 break; 2925 default: 2926 return fnvStateError; 2927 } 2928 for ( i=0; iHash[i]; 2930 while ( ch = (uint8_t)*in++ ) 2931 { 2932 /* temp = FNV512prime * ( temp ^ ch ); */ 2933 temp[7] ^= ch; 2934 temp2[2] = temp[7] << FNV128shift; 2935 temp2[1] = temp[6] << FNV128shift; 2936 temp2[0] = temp[5] << FNV128shift; 2937 for ( i=0; i0; --i ) 2943 { 2944 temp[i-1] += temp[i] >> 16; 2945 temp[i] &= 0xFFFF; 2946 } 2947 } 2948 for ( i=0; iHash[i] = temp[i]; 2950 return fnvSuccess; 2951 } 2952 return fnvNull; 2953 } /* end FNV512stringin */ 2955 /* return hash (64 bit) 2956 ********************************************************************/ 2957 int FNV512result ( FNV512context *ctx, uint8_t out[FNV512size] ) 2958 { 2959 if ( ctx && out ) 2960 { 2961 if ( ctx->Computed != FNVcomputed+FNV512state ) 2962 return fnvStateError; 2963 for ( i=0; iHash[i]; 2967 out[14-2*i] = ctx->Hash[i] >> 8; 2968 #else 2969 out[2*i] = ctx->Hash[i]; 2970 out[2*i+1] = ctx->Hash[i] >> 8; 2971 #endif 2972 ctx -> Hash[i] = 0; 2973 } 2974 ctx->Computed = FNVemptied+FNV512state; 2975 return fnvSuccess; 2976 } 2977 return fnvNull; 2978 } /* end FNV512result */ 2980 /****************************************************************** 2981 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2982 ******************************************************************/ 2984 #else /* FNV_64bitIntegers */ 2985 /****************************************************************** 2986 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2987 ******************************************************************/ 2989 /* version for when you only have 32-bit arithmetic 2990 ********************************************************************/ 2992 /* 2993 512 bit FNV_prime = 2^344 + 2^8 + 0x57 = 2994 0x0000000000000000 0000000000000000 2995 0000000001000000 0000000000000000 2996 0000000000000000 0000000000000000 2997 0000000000000000 0000000000000157 */ 2998 #define FNV512primeX 0x0157 2999 #define FNV512shift 8 3001 /* 0xB86DB0B1171F4416 DCA1E50F309990AC 3002 AC87D059C9000000 0000000000000D21 3003 E948F68A34C192F6 2EA79BC942DBE7CE 3004 182036415F56E34B AC982AAC4AFE9FD9 */ 3006 uint16_t FNV512basis[FNV512size/2] = { 3007 0xB86D, 0xB0B1, 0x171F, 0x4416, 0xDCA1, 0xE50F, 0x3099, 0x90AC, 3008 0xAC87, 0xD059, 0xC900, 0x0000, 0x0000, 0x0000, 0x0000, 0x0D21, 3009 0xE948, 0xF68A, 0x34C1, 0x92F6, 0x2EA7, 0x9BC9, 0x42DB, 0xE7CE, 3010 0x1820, 0x3641, 0x5F56, 0xE34B, 0xAC98, 0x2AAC, 0x4AFE, 0x9FD9 }; 3012 /******************************************************************** 3013 * Set of init, input, and output functions below * 3014 * to incrementally compute FNV512 * 3015 ********************************************************************/ 3017 /* initialize context (32 bit) 3018 ********************************************************************/ 3019 int FNV512init ( FNV512context *ctx ) 3020 { 3021 int i; 3023 if ( ctx ) 3024 { 3025 for ( i=0; iHash[i] = FNV512basis[i]; 3027 ctx->Computed = FNVinited+FNV512state; 3028 return fnvSuccess; 3029 } 3030 return fnvNull; 3031 } /* end FNV512init */ 3032 /* initialize context with a provided basis (32 bit) 3033 ********************************************************************/ 3034 int FNV512initBasis ( FNV512context *ctx, 3035 const uint8_t basis[FNV512size] ) 3036 { 3037 int i; 3038 const uint8_t *ui8p; 3039 uint32_t temp; 3041 if ( ctx ) 3042 { 3043 #ifdef FNV_BigEndian 3044 ui8p = basis; 3045 for ( i=0; i < FNV512size/2; ++i ) 3046 { 3047 temp = *ui8p++; 3048 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 3049 } 3050 #else 3051 ui8p = basis + ( FNV512size/2 - 1 ); 3052 for ( i=0; i < FNV512size/2; ++i ) 3053 { 3054 temp = *ui8p--; 3055 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 3056 } 3057 #endif 3058 ctx->Computed = FNVinited+FNV512state; 3059 return fnvSuccess; 3060 } 3061 return fnvNull; 3062 } /* end FNV512initBasis */ 3064 /* hash in a counted block (32 bit) 3065 *******************************************************************/ 3066 int FNV512blockin ( FNV512context *ctx, 3067 const void *vin, 3068 long int length ) 3069 { 3070 const uint8_t *in = (const uint8_t*)vin; 3071 uint32_t temp[FNV512size/2]; 3072 uint32_t temp2[6]; 3073 int i; 3075 if ( ctx && in ) 3076 { 3077 switch ( ctx->Computed ) 3078 { 3079 case FNVinited+FNV512state: 3080 ctx->Computed = FNVcomputed+FNV512state; 3081 case FNVcomputed+FNV512state: 3083 break; 3084 default: 3085 return fnvStateError; 3086 } 3087 if ( length < 0 ) 3088 return fnvBadParam; 3089 for ( i=0; iHash[i]; 3091 for ( ; length > 0; length-- ) 3092 { 3093 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3094 temp[15] ^= *in++; 3095 for ( i=0; i<6; ++i ) 3096 temp2[i] = temp[10+i] << FNV512shift; 3097 for ( i=0; i0; --i ) 3102 { 3103 temp[i-1] += temp[i] >> 16; 3104 temp[i] &= 0xFFFF; 3105 } 3106 } 3107 for ( i=0; iHash[i] = temp[i]; 3109 return fnvSuccess; 3110 } 3111 return fnvNull; 3112 } /* end FNV512blockin */ 3114 /* hash in a string (32 bit) 3115 *******************************************************************/ 3116 int FNV512stringin ( FNV512context *ctx, const char *in ) 3117 { 3118 uint32_t temp[FNV512size/2]; 3119 uint32_t temp2[6]; 3120 int i; 3121 uint8_t ch; 3123 if ( ctx && in ) 3124 { 3125 switch ( ctx->Computed ) 3126 { 3127 case FNVinited+FNV512state: 3128 ctx->Computed = FNVcomputed+FNV512state; 3129 case FNVcomputed+FNV512state: 3130 break; 3131 default: 3132 return fnvStateError; 3134 } 3135 for ( i=0; iHash[i]; 3137 while ( (ch = (uint8_t)*in++) ) 3138 { 3139 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3140 temp[15] ^= ch; 3141 for ( i=0; i<6; ++i ) 3142 temp2[i] = temp[10+i] << FNV512shift; 3143 for ( i=0; i0; --i ) 3148 { 3149 temp[i-1] += temp[i] >> 16; 3150 temp[i] &= 0xFFFF; 3151 } 3152 } 3153 for ( i=0; iHash[i] = temp[i]; 3155 return fnvSuccess; 3156 } 3157 return fnvNull; 3158 } /* end FNV512stringin */ 3160 /* return hash (32 bit) 3161 ********************************************************************/ 3162 int FNV512result ( FNV512context *ctx, unsigned char out[16] ) 3163 { 3164 int i; 3166 if ( ctx && out ) 3167 { 3168 if ( ctx->Computed != FNVcomputed+FNV512state ) 3169 return fnvStateError; 3170 for ( i=0; iHash[i]; 3174 out[30-2*i] = ctx->Hash[i] >> 8; 3175 #else 3176 out[2*i] = ctx->Hash[i]; 3177 out[2*i+1] = ctx->Hash[i] >> 8; 3178 #endif 3179 ctx->Hash[i] = 0; 3180 } 3181 ctx->Computed = FNVemptied+FNV512state; 3182 return fnvSuccess; 3183 } 3185 return fnvNull; 3186 } /* end FNV512result */ 3188 #endif /* Have64bitIntegers */ 3189 /******************************************************************** 3190 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3191 ********************************************************************/ 3193 #endif /* _FNV512_C_ */ 3194 3196 6.1.6 FNV1024 C Code 3198 The header and C source for 1024-bit FNV-1a. 3200 3201 /*************************** FNV1024.h **************************/ 3202 /***************** See RFC NNNN for details. ********************/ 3203 /* 3204 * Copyright (c) 2016 IETF Trust and the persons identified as 3205 * authors of the code. All rights reserved. 3206 * See fnv-private.h for terms of use and redistribution. 3207 */ 3209 #ifndef _FNV1024_H_ 3210 #define _FNV1024_H_ 3212 /* 3213 * Description: 3214 * This file provides headers for the 1024-bit version of the 3215 * FNV-1a non-cryptographic hash algorithm. 3216 */ 3218 #include "FNVconfig.h" 3220 #include 3221 #define FNV1024size (1024/8) 3223 /* If you do not have the ISO standard stdint.h header file, then you 3224 * must typedef the following types: 3225 * 3226 * type meaning 3227 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 3228 * uint32_t unsigned 32 bit integer 3229 * uint16_t unsigned 16 bit integer 3230 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 3231 */ 3233 #ifndef _FNV_ErrCodes_ 3234 #define _FNV_ErrCodes_ 3235 /********************************************************************* 3236 * All FNV functions provided return as integer as follows: 3237 * 0 -> success 3238 * >0 -> error as listed below 3239 */ 3240 enum { /* success and errors */ 3241 fnvSuccess = 0, 3242 fnvNull, /* Null pointer parameter */ 3243 fnvStateError, /* called Input after Result or before Init */ 3244 fnvBadParam /* passed a bad parameter */ 3245 }; 3246 #endif /* _FNV_ErrCodes_ */ 3248 /* 3249 * This structure holds context information for an FNV1024 hash 3250 */ 3251 #ifdef FNV_64bitIntegers 3252 /* version if 64 bit integers supported */ 3253 typedef struct FNV1024context_s { 3254 int Computed; /* state */ 3255 uint32_t Hash[FNV1024size/4]; 3256 } FNV1024context; 3258 #else 3259 /* version if 64 bit integers NOT supported */ 3261 typedef struct FNV1024context_s { 3262 int Computed; /* state */ 3263 uint16_t Hash[FNV1024size/2]; 3264 } FNV1024context; 3266 #endif /* FNV_64bitIntegers */ 3268 /* 3269 * Function Prototypes 3270 * FNV1024string: hash a zero terminated string not including 3271 * the terminating zero 3272 * FNV1024block: FNV1024 hash a specified length byte vector 3273 * FNV1024init: initializes an FNV1024 context 3274 * FNV1024initBasis: initializes an FNV1024 context with a 3275 * provided basis 3276 * FNV1024blockin: hash in a specified length byte vector 3277 * FNV1024stringin: hash in a zero terminated string not 3278 * including the zero 3279 * FNV1024result: returns the hash value 3280 * 3281 * Hash is returned as an array of 8-bit integers 3282 */ 3284 #ifdef __cplusplus 3285 extern "C" { 3286 #endif 3288 /* FNV1024 */ 3289 extern int FNV1024string ( const char *in, 3290 unsigned char out[FNV1024size] ); 3291 extern int FNV1024block ( const void *in, 3292 long int length, 3293 unsigned char out[FNV1024size] ); 3294 extern int FNV1024init ( FNV1024context *); 3295 extern int FNV1024initBasis ( FNV1024context * const, 3296 const uint8_t basis[FNV1024size] ); 3297 extern int FNV1024blockin ( FNV1024context *, 3298 const void *in, 3299 long int length ); 3300 extern int FNV1024stringin ( FNV1024context *, 3301 const char *in ); 3302 extern int FNV1024result ( FNV1024context *, 3303 unsigned char out[FNV1024size] ); 3305 #ifdef __cplusplus 3306 } 3307 #endif 3309 #endif /* _FNV1024_H_ */ 3310 3312 3313 /***************************** FNV1024.c ****************************/ 3314 /******************** See RFC NNNN for details *********************/ 3315 /* Copyright (c) 2016 IETF Trust and the persons identified as 3316 * authors of the code. All rights 3317 * See fnv-private.h for terms of use and redistribution. 3318 */ 3320 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 3321 * hash function FNV-1a for 1024-bit hashes. 3322 */ 3324 #ifndef _FNV1024_C_ 3325 #define _FNV1024_C_ 3327 #include "fnv-private.h" 3328 #include "FNV1024.h" 3330 /* common code for 64 and 32 bit modes */ 3332 /* FNV1024 hash a null terminated string (64/32 bit) 3333 ********************************************************************/ 3335 int FNV1024string ( const char *in, uint8_t out[FNV1024size] ) 3336 { 3337 FNV1024context ctx; 3338 int err; 3340 if ( (err = FNV1024init ( &ctx )) != fnvSuccess) 3341 return err; 3342 if ( (err = FNV1024stringin ( &ctx, in )) != fnvSuccess) 3343 return err; 3344 return FNV1024result ( &ctx, out ); 3345 } /* end FNV1024string */ 3347 /* FNV1024 hash a counted block (64/32 bit) 3348 ********************************************************************/ 3349 int FNV1024block ( const void *in, 3350 long int length, 3351 uint8_t out[FNV1024size] ) 3352 { 3353 FNV1024context ctx; 3354 int err; 3356 if ( (err = FNV1024init ( &ctx )) != fnvSuccess) 3357 return err; 3358 if ( (err = FNV1024blockin ( &ctx, in, length)) != fnvSuccess) 3359 return err; 3360 return FNV1024result ( &ctx, out ); 3361 } /* end FNV1024block */ 3363 /******************************************************************** 3364 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 3365 ********************************************************************/ 3366 #ifdef Have64bitIntegers 3368 /* 3369 1024 bit FNV_prime = 2^680 + 2^8 + 0x8d = 3370 0x0000000000000000 0000010000000000 3371 0000000000000000 0000000000000000 3372 0000000000000000 0000000000000000 3373 0000000000000000 0000000000000000 3374 0000000000000000 0000000000000000 3375 0000000000000000 000000000000018D 3376 #define FNV1024primeX 0x018D 3377 #define FNV1024shift 24 3379 /* 0x0000000000000000 005F7A76758ECC4D 3380 32E56D5A591028B7 4B29FC4223FDADA1 3381 6C3BF34EDA3674DA 9A21D90000000000 3382 0000000000000000 0000000000000000 3383 0000000000000000 0000000000000000 3384 0000000000000000 000000000004C6D7 3385 EB6E73802734510A 555F256CC005AE55 3386 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 */ 3388 uint32_t FNV1024basis[FNV1024size/4] = { 3389 0x00000000, 0x00000000, 0x005F7A76, 0x758ECC4D, 3390 0x32E56D5A, 0x591028B7, 0x4B29FC42, 0x23FDADA1, 3391 0x6C3BF34E, 0xDA3674DA, 0x9A21D900, 0x00000000, 3392 0x00000000, 0x00000000, 0x00000000, 0x00000000, 3393 0x00000000, 0x00000000, 0x00000000, 0x00000000, 3394 0x00000000, 0x00000000, 0x00000000, 0x0004C6D7, 3395 0xEB6E7380, 0x2734510A, 0x555F256C, 0xC005AE55, 3396 0x6BDE8CC9, 0xC6A93B21, 0xAFF4B16C, 0x71EE90B3 3397 }; 3399 /******************************************************************** 3400 * Set of init, input, and output functions below * 3401 * to incrementally compute FNV1024 * 3402 ********************************************************************/ 3404 /* initialize context (64 bit) 3405 ********************************************************************/ 3406 int FNV1024init ( FNV1024context *ctx ) 3407 { 3408 if ( ctx ) 3409 { 3410 for ( i=0; iHash[i] = FNV1024basis[i]; 3412 ctx->Computed = FNVinited+FNV1024state; 3413 return fnvSuccess; 3414 } 3415 return fnvNull; 3416 } /* end FNV1024init */ 3418 /* initialize context with a provided basis (64 bit) 3419 ********************************************************************/ 3420 int FNV1024initBasis ( FNV1024context* const ctx, 3421 const uint8_t basis[FNV1024size] ) 3422 { 3423 int i; 3424 uint8_t *ui8p; 3425 uint32_t temp; 3427 if ( ctx ) 3428 { 3429 #ifdef FNV_BigEndian 3430 ui8p = basis; 3431 for ( i=0; i < FNV1024size/4; ++i ) 3432 { 3433 temp = (*ui8p++)<<8; 3434 temp = (temp + *ui8p++)<<8; 3435 temp = (temp + *ui8p++)<<8; 3436 ctx->Hash[i] = temp + *ui8p; 3437 } 3438 #else 3439 ui8p = basis + (FNV1024size/4 - 1); 3440 for ( i=0; i < FNV1024size/4; ++i ) 3441 { 3442 temp = (*ui8p--)<<8; 3443 temp = (temp + *ui8p--)<<8; 3444 temp = (temp + *ui8p--)<<8; 3445 ctx->Hash[i] = temp + *ui8p; 3446 } 3447 #endif 3448 ctx->Computed = FNVinited+FNV1024state; 3449 return fnvSuccess; 3450 } 3451 return fnvNull; 3452 } /* end FNV1024initBasis */ 3454 /* hash in a counted block (64 bit) 3455 ********************************************************************/ 3456 int FNV1024blockin ( FNV1024context *ctx, 3457 const void *vin, 3458 long int length ) 3459 { 3460 const uint8_t *in = (const uint8_t*)vin; 3461 uint64_t temp[FNV1024size/4]; 3462 uint64_t temp2[3]; 3464 if ( ctx && in ) 3465 { 3466 switch ( ctx->Computed ) 3467 { 3468 case FNVinited+FNV1024state: 3469 ctx->Computed = FNVcomputed+FNV128state; 3470 case FNVcomputed+FNV1024state: 3471 break; 3472 default: 3473 return fnvStateError; 3474 } 3475 if ( length < 0 ) 3476 return fnvBadParam; 3477 for ( i=0; iHash[i]; 3479 for ( ; length > 0; length-- ) 3480 { 3481 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 3482 temp[7] ^= *in++; 3483 temp2[2] = temp[7] << FNV1024shift; 3484 temp2[1] = temp[6] << FNV1024shift; 3485 temp2[0] = temp[5] << FNV1024shift; 3486 for ( i=0; i0; --i ) 3492 { 3493 temp[i-1] += temp[i] >> 16; 3494 temp[i] &= 0xFFFF; 3495 } 3496 } 3497 for ( i=0; iHash[i] = temp[i]; 3499 return fnvSuccess; 3500 } 3501 return fnvNull; 3502 } /* end FNV1024input */ 3504 /* hash in a string (64 bit) 3505 ********************************************************************/ 3506 inf FNV1024stringin ( FNV1024context *ctx, const char *in ) 3507 { 3508 uint64_t temp[FNV1024size/4]; 3509 uint64_t temp2[2]; 3510 int i; 3511 uint8_t ch; 3513 if ( ctx && in ) 3514 { 3515 switch ( ctx->Computed ) 3516 { 3517 case FNVinited+FNV1024state: 3518 ctx->Computed = FNVcomputed+FNV1024state; 3519 case FNVcomputed+FNV1024state: 3520 break; 3521 default: 3522 return fnvStateError; 3523 } 3524 for ( i=0; iHash[i]; 3526 while ( ch = (uint8_t)*in++ ) 3527 { 3528 /* temp = FNV1024prime * ( temp ^ ch ); */ 3529 temp[7] ^= ch; 3530 temp2[2] = temp[7] << FNV128shift; 3531 temp2[1] = temp[6] << FNV128shift; 3532 temp2[0] = temp[5] << FNV128shift; 3533 for ( i=0; i0; --i ) 3539 { 3540 temp[i-1] += temp[i] >> 16; 3541 temp[i] &= 0xFFFF; 3542 } 3543 } 3544 for ( i=0; iHash[i] = temp[i]; 3546 return fnvSuccess; 3547 } 3548 return fnvNull; 3549 } /* end FNV1024stringin */ 3551 /* return hash (64 bit) 3552 ********************************************************************/ 3553 int FNV1024result ( FNV1024context *ctx, uint8_t out[FNV1024size] ) 3554 { 3555 if ( ctx && out ) 3556 { 3557 if ( ctx->Computed != FNVcomputed+FNV1024state ) 3558 return fnvStateError; 3559 for ( i=0; iHash[i]; 3563 out[14-2*i] = ctx->Hash[i] >> 8; 3564 #else 3565 out[2*i] = ctx->Hash[i]; 3566 out[2*i+1] = ctx->Hash[i] >> 8; 3567 #endif 3568 ctx -> Hash[i] = 0; 3569 } 3570 ctx->Computed = FNVemptied+FNV1024state; 3571 return fnvSuccess; 3572 } 3573 return fnvNull; 3574 } /* end FNV1024result */ 3576 /****************************************************************** 3577 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 3578 ******************************************************************/ 3579 #else /* FNV_64bitIntegers */ 3580 /****************************************************************** 3581 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3582 ******************************************************************/ 3584 /* version for when you only have 32-bit arithmetic 3585 ********************************************************************/ 3587 /* 3588 1024 bit FNV_prime = 2^680 + 2^8 + 0x8d = 3589 0x0000000000000000 0000010000000000 3590 0000000000000000 0000000000000000 3591 0000000000000000 0000000000000000 3592 0000000000000000 0000000000000000 3593 0000000000000000 0000000000000000 3594 0000000000000000 000000000000018D */ 3595 #define FNV1024primeX 0x018D 3596 #define FNV1024shift 8 3598 /* 0x0000000000000000 005F7A76758ECC4D 3599 32E56D5A591028B7 4B29FC4223FDADA1 3600 6C3BF34EDA3674DA 9A21D90000000000 3601 0000000000000000 0000000000000000 3602 0000000000000000 0000000000000000 3603 0000000000000000 000000000004C6D7 3604 EB6E73802734510A 555F256CC005AE55 3605 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 */ 3607 uint16_t FNV1024basis[FNV1024size/2] = { 3608 0x0000, 0x0000, 0x0000, 0x0000, 0x005F, 0x7A76, 0x758E, 0xCC4D, 3609 0x32E5, 0x6D5A, 0x5910, 0x28B7, 0x4B29, 0xFC42, 0x23FD, 0xADA1, 3610 0x6C3B, 0xF34E, 0xDA36, 0x74DA, 0x9A21, 0xD900, 0x0000, 0x0000, 3611 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 3612 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 3613 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0004, 0xC6D7, 3614 0xEB6E, 0x7380, 0x2734, 0x510A, 0x555F, 0x256C, 0xC005, 0xAE55, 3615 0x6BDE, 0x8CC9, 0xC6A9, 0x3B21, 0xAFF4, 0xB16C, 0x71EE, 0x90B3 3616 }; 3618 /******************************************************************** 3619 * Set of init, input, and output functions below * 3620 * to incrementally compute FNV1024 * 3621 ********************************************************************/ 3623 /* initialize context (32 bit) 3624 ********************************************************************/ 3625 int FNV1024init ( FNV1024context *ctx ) 3626 { 3627 int i; 3629 if ( ctx ) 3630 { 3631 for ( i=0; iHash[i] = FNV1024basis[i]; 3634 ctx->Computed = FNVinited+FNV1024state; 3635 return fnvSuccess; 3636 } 3637 return fnvNull; 3638 } /* end FNV1024init */ 3640 /* initialize context with a provided basis (32 bit) 3641 ********************************************************************/ 3642 int FNV1024initBasis ( FNV1024context *ctx, 3643 const uint8_t basis[FNV1024size] ) 3644 { 3645 int i; 3646 const uint8_t *ui8p; 3647 uint32_t temp; 3649 if ( ctx ) 3650 { 3651 #ifdef FNV_BigEndian 3652 ui8p = basis; 3653 for ( i=0; i < FNV1024size/2; ++i ) 3654 { 3655 temp = *ui8p++; 3656 ctx->Hash[i] = ( temp<<8 ) + (*ui8p++); 3657 } 3658 #else 3659 ui8p = basis + ( FNV1024size/2 - 1 ); 3660 for ( i=0; i < FNV1024size/2; ++i ) 3661 { 3662 temp = *ui8p--; 3663 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 3664 } 3665 #endif 3666 ctx->Computed = FNVinited+FNV1024state; 3667 return fnvSuccess; 3668 } 3669 return fnvNull; 3670 } /* end FNV1024initBasis */ 3672 /* hash in a counted block (32 bit) 3673 *******************************************************************/ 3674 int FNV1024blockin ( FNV1024context *ctx, 3675 const void *vin, 3676 long int length ) 3677 { 3678 const uint8_t *in = (const uint8_t*)vin; 3679 uint32_t temp[FNV1024size/2]; 3680 uint32_t temp2[6]; 3681 int i; 3683 if ( ctx && in ) 3684 { 3685 switch ( ctx->Computed ) 3686 { 3687 case FNVinited+FNV1024state: 3688 ctx->Computed = FNVcomputed+FNV1024state; 3689 case FNVcomputed+FNV1024state: 3690 break; 3691 default: 3692 return fnvStateError; 3693 } 3694 if ( length < 0 ) 3695 return fnvBadParam; 3696 for ( i=0; iHash[i]; 3698 for ( ; length > 0; length-- ) 3699 { 3700 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 3701 temp[15] ^= *in++; 3702 for ( i=0; i<6; ++i ) 3703 temp2[i] = temp[10+i] << FNV1024shift; 3704 for ( i=0; i0; --i ) 3709 { 3710 temp[i-1] += temp[i] >> 16; 3711 temp[i] &= 0xFFFF; 3712 } 3713 } 3714 for ( i=0; iHash[i] = temp[i]; 3716 return fnvSuccess; 3717 } 3718 return fnvNull; 3719 } /* end FNV1024blockin */ 3721 /* hash in a string (32 bit) 3722 *******************************************************************/ 3723 int FNV1024stringin ( FNV1024context *ctx, const char *in ) 3724 { 3725 uint32_t temp[FNV1024size/2]; 3726 uint32_t temp2[6]; 3727 int i; 3728 uint8_t ch; 3730 if ( ctx && in ) 3731 { 3732 switch ( ctx->Computed ) 3733 { 3734 case FNVinited+FNV1024state: 3735 ctx->Computed = FNVcomputed+FNV1024state; 3736 case FNVcomputed+FNV1024state: 3737 break; 3738 default: 3739 return fnvStateError; 3740 } 3741 for ( i=0; iHash[i]; 3743 while ( (ch = (uint8_t)*in++) ) 3744 { 3745 /* temp = FNV1024prime * ( temp ^ *in++ ); */ 3746 temp[15] ^= ch; 3747 for ( i=0; i<6; ++i ) 3748 temp2[i] = temp[10+i] << FNV1024shift; 3749 for ( i=0; i0; --i ) 3754 { 3755 temp[i-1] += temp[i] >> 16; 3756 temp[i] &= 0xFFFF; 3757 } 3758 } 3759 for ( i=0; iHash[i] = temp[i]; 3761 return fnvSuccess; 3762 } 3763 return fnvNull; 3764 } /* end FNV1024stringin */ 3766 /* return hash (32 bit) 3767 ********************************************************************/ 3768 int FNV1024result ( FNV1024context *ctx, unsigned char out[16] ) 3769 { 3770 int i; 3772 if ( ctx && out ) 3773 { 3774 if ( ctx->Computed != FNVcomputed+FNV1024state ) 3775 return fnvStateError; 3776 for ( i=0; iHash[i]; 3780 out[30-2*i] = ctx->Hash[i] >> 8; 3781 #else 3782 out[2*i] = ctx->Hash[i]; 3783 out[2*i+1] = ctx->Hash[i] >> 8; 3785 #endif 3786 ctx->Hash[i] = 0; 3787 } 3788 ctx->Computed = FNVemptied+FNV1024state; 3789 return fnvSuccess; 3790 } 3791 return fnvNull; 3792 } /* end FNV1024result */ 3794 #endif /* Have64bitIntegers */ 3795 /******************************************************************** 3796 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3797 ********************************************************************/ 3799 #endif /* _FNV1024_C_ */ 3800 3802 6.2 FNV Test Code 3804 Here is a test driver: 3806 3807 /**************************** MAIN.c ****************************/ 3808 /****************** See RFC NNNN for details. *******************/ 3809 /* 3810 * Copyright (c) 2016 IETF Trust and the persons identified as 3811 * authors of the code. All rights reserved. 3812 * See fnv-private.h for terms of use and redistribution. 3813 */ 3814 /* to do a thorough test you need to run will all four 3815 combinations of the following defined/undefined */ 3817 // #define FNV_64bitIntegers 3818 // #define FNV_BigEndian 3820 #include 3821 #include 3823 #include "fnv-private.h" 3824 #include "FNV.h" 3826 /* global variables */ 3827 char *funcName; 3828 char *errteststring = "foo"; 3829 int Terr; /* Total errors */ 3830 #define NTestBytes 3 3831 uint8_t errtestbytes[NTestBytes] = { (uint8_t)1, 3832 (uint8_t)2, (uint8_t)3 }; 3834 #define NTstrings 3 3835 char *teststring[NTstrings] = { "", "a", "foobar" }; 3837 /***************************************************************** 3838 * local prototypes 3839 *****************************************************************/ 3840 int TestR ( char *, int should, int was ); 3841 void TestNValue ( char *subfunc, 3842 char *string, 3843 int N, 3844 uint8_t *should, 3845 uint8_t *was ); 3846 void HexPrint ( int i, unsigned char *p ); 3847 void Test32 (); 3848 void Test32Value ( char *subfunc, char *string, 3849 uint32_t was, uint32_t should ); 3850 void Test64 (); 3851 #ifdef FNV_64bitIntegers 3852 void Test64Value ( char *subfunc, char *string, 3853 uint64_t should, uint64_t was ); 3854 #else 3855 #define uint64_t foobar 3856 #endif /* FNB_64bitIntegers */ 3857 void Test128 (); 3858 void Test256 (); 3859 void Test512 (); 3860 void Test1024 (); 3862 void TestNValue ( char *subfunc, 3863 char *string, 3864 int N, 3865 uint8_t was[N], 3866 uint8_t should[N] ); 3868 /***************************************************************** 3869 * main 3870 *****************************************************************/ 3871 int main (int argc, const char * argv[]) 3872 { 3873 #ifdef FNV_64bitIntegers 3874 printf ("Have 64-bit Integers. "); 3875 #else 3876 printf ("Do not have 64-bit integers. "); 3877 #endif 3878 #ifdef FNV_BigEndian 3879 printf ("Calculating for Big Endian.0); 3880 #else 3881 printf ("Not calculating for Big Endian.0); 3882 #endif 3883 funcName = "Testing TestR "; 3884 /* test the Test Return function */ 3885 TestR ( "should fail", 1, 2 ); 3886 TestR ( "should not have failed", 0, 0 ); 3888 Test32(); 3889 Test64(); 3890 Test128(); 3891 Test256(); 3892 Test512(); 3893 Test1024(); 3895 printf ("Type return to exit.0); 3896 (void)getchar(); 3897 printf ("Goodbye!0); 3899 return 0; 3900 } /* end main */ 3902 /* Test status returns 3903 *****************************************************************/ 3904 int TestR ( char *name, int expect, int actual ) 3905 { 3906 if ( expect != actual ) 3907 { 3908 printf ( "%s%s returned %i instead of %i.0, 3909 funcName, name, actual, expect ); 3910 ++Terr; 3911 } 3912 return actual; 3913 } /* end TestR */ 3915 /* Return true if the bytes are in reverse order from each other */ 3916 int revcmp(uint8_t *buf1, uint8_t *buf2, int N) { 3917 int i; 3918 uint8_t *bufc = buf2 + N; 3919 for ( i = 0; i < N / 2; i++ ) 3920 if (*buf1++ != *--bufc) 3921 return 0; 3922 return 1; 3923 } 3925 /* General byte vector return error test 3926 *****************************************************************/ 3927 void TestNValue ( char *subfunc, 3928 char *string, 3929 int N, 3930 uint8_t *was, 3931 uint8_t *should ) 3932 { 3933 #ifdef FNV_BigEndian 3934 if ( revcmp ( was, should, N) == 0) 3935 #else 3936 if ( memcmp ( was, should, N) != 0) 3937 #endif 3938 { 3939 printf ( "%s %s of '%s' computed ", funcName, subfunc, string ); 3940 HexPrint ( N, was ); 3941 printf ( ", should have been " ); 3942 HexPrint ( N, should ); 3943 printf ( ".0 ); 3944 ++Terr; 3945 } 3946 } /* end TestNValue */ 3948 /* print some hex 3949 *****************************************************************/ 3950 void HexPrint ( int count, unsigned char *ptr ) 3951 { 3952 int i; 3954 for ( i = 0; i < count; ++i ) 3955 printf ( "%02X", ptr[i] ); 3956 } /* end HexPrint */ 3958 /***************************************************************** 3959 * FNV32 test 3960 *****************************************************************/ 3961 void Test32 () 3962 { 3963 int i, err; 3964 long int iLen; 3965 uint32_t eUint32; 3966 FNV32context eContext; 3967 uint32_t FNV32svalues[NTstrings] = { 3968 0x811c9dc5, 0xe40c292c, 0xbf9cf968 }; 3969 uint32_t FNV32bvalues[NTstrings] = { 3970 0x050c5d1f, 0x2b24d044, 0x0c1c9eb8 }; 3972 /* test Test32Value */ 3973 funcName = "Test32Value"; 3974 Test32Value ( "should fail", "test", FNV32svalues[1], FNV32svalues[2] ); 3976 funcName = "FNV32"; 3978 /* test error checks */ 3979 Terr = 0; 3980 TestR ( "init", fnvSuccess, FNV32init (&eContext) ); 3981 TestR ( "string", fnvNull, 3982 FNV32string ( (char *)0, &eUint32 ) ); 3984 TestR ( "string", fnvNull, 3985 FNV32string ( errteststring, (uint32_t *)0 ) ); 3986 TestR ( "block", fnvNull, 3987 FNV32block ( (uint8_t *)0, 1, &eUint32 ) ); 3988 TestR ( "block", fnvBadParam, 3989 FNV32block ( errtestbytes, -1, &eUint32 ) ); 3990 TestR ( "block", fnvNull, 3991 FNV32block ( errtestbytes, 1, (uint32_t *)0 ) ); 3992 TestR ( "init", fnvNull, 3993 FNV32init ( (FNV32context *)0 ) ); 3994 TestR ( "initBasis", fnvNull, 3995 FNV32initBasis ( (FNV32context *)0, 42 ) ); 3996 TestR ( "blockin", fnvNull, 3997 FNV32blockin ( (FNV32context *)0, 3998 errtestbytes, NTestBytes ) ); 3999 TestR ( "blockin", fnvNull, 4000 FNV32blockin ( &eContext, (uint8_t *)0, 4001 NTestBytes ) ); 4002 TestR ( "blockin", fnvBadParam, 4003 FNV32blockin ( &eContext, errtestbytes, -1 ) ); 4004 eContext.Computed = FNVclobber+FNV32state; 4005 TestR ( "blockin", fnvStateError, 4006 FNV32blockin ( &eContext, errtestbytes, 4007 NTestBytes ) ); 4008 TestR ( "stringin", fnvNull, 4009 FNV32stringin ( (FNV32context *)0, errteststring ) ); 4010 TestR ( "stringin", fnvNull, 4011 FNV32stringin ( &eContext, (char *)0 ) ); 4012 TestR ( "stringin", fnvStateError, 4013 FNV32stringin ( &eContext, errteststring ) ); 4014 TestR ( "result", fnvNull, 4015 FNV32result ( (FNV32context *)0, &eUint32 ) ); 4016 TestR ( "result", fnvNull, 4017 FNV32result ( &eContext, (uint32_t *)0 ) ); 4018 TestR ( "result", fnvStateError, 4019 FNV32result ( &eContext, &eUint32 ) ); 4020 if ( Terr ) 4021 printf ( "%s test of error checks failed %i times.0, 4022 funcName, Terr ); 4023 else 4024 printf ( "%s test of error checks passed0, funcName ); 4026 /* test actual results */ 4027 Terr = 0; 4028 for ( i = 0; i < NTstrings; ++i ) 4029 { 4030 err = TestR ( "string", fnvSuccess, 4031 FNV32string ( teststring[i], &eUint32 ) ); 4032 if ( err == fnvSuccess ) 4033 Test32Value ( "string", teststring[i], eUint32, 4034 FNV32svalues[i] ); 4035 err = TestR ( "block", fnvSuccess, 4036 FNV32block ( (uint8_t *)teststring[i], 4037 (unsigned long)(strlen(teststring[i])+1), 4038 &eUint32 ) ); 4039 if ( err == fnvSuccess ) 4040 Test32Value ( "block", teststring[i], eUint32, 4041 FNV32bvalues[i] ); 4042 /* now try testing the incremental stuff */ 4043 err = TestR ( "init", fnvSuccess, FNV32init ( &eContext ) ); 4044 if ( err ) break; 4045 iLen = strlen ( teststring[i] ); 4046 err = TestR ( "blockin", fnvSuccess, 4047 FNV32blockin ( &eContext, 4048 (uint8_t *)teststring[i], 4049 iLen/2 ) ); 4050 if ( err ) break; 4051 err = TestR ( "stringin", fnvSuccess, 4052 FNV32stringin ( &eContext, 4053 teststring[i] + iLen/2 ) ); 4054 err = TestR ( "result", fnvSuccess, 4055 FNV32result ( &eContext, &eUint32 ) ); 4056 if ( err ) break; 4057 Test32Value ( " incremental", teststring[i], eUint32, 4058 FNV32svalues[i] ); 4059 } 4060 if ( Terr ) 4061 printf ( "%s test of return values failed %i times.0, 4062 funcName, Terr ); 4063 else 4064 printf ( "%s test of return values passed.0, funcName ); 4065 } /* end Test32 */ 4067 /* start Test32Value 4068 *****************************************************************/ 4069 void Test32Value ( char *subfunc, 4070 char *string, 4071 uint32_t was, 4072 uint32_t should ) 4073 { 4074 TestNValue(subfunc, string, sizeof(uint32_t), (uint8_t*)&was, 4075 (uint8_t*)&should); 4076 } /* end Test32Value */ 4078 #ifdef FNV_64bitIntegers 4079 /***************************************************************** 4080 * Code for FNV64 using 64-bit integers 4081 *****************************************************************/ 4083 void Test64 () 4084 { 4085 int i, err; 4086 uint64_t eUint64 = 42; 4087 FNV64context eContext; 4088 uint64_t FNV64svalues[NTstrings] = { 4089 0xcbf29ce484222325, 0xaf63dc4c8601ec8c, 0x85944171f73967e8 }; 4090 uint64_t FNV64bvalues[NTstrings] = { 4091 0xaf63bd4c8601b7df, 0x089be207b544f1e4, 0x34531ca7168b8f38 }; 4093 funcName = "FNV64"; 4095 /* test error checks */ 4096 Terr = 0; 4097 TestR ( "init", fnvSuccess, FNV64init (&eContext) ); 4098 TestR ( "string", fnvNull, 4099 FNV64string ( (char *)0, &eUint64 ) ); 4100 TestR ( "string", fnvNull, 4101 FNV64string ( errteststring, (uint64_t *)0 ) ); 4102 TestR ( "block", fnvNull, 4103 FNV64block ( (uint8_t *)0, 1, &eUint64 ) ); 4104 TestR ( "block", fnvBadParam, 4105 FNV64block ( errtestbytes, -1, &eUint64 ) ); 4106 TestR ( "block", fnvNull, 4107 FNV64block ( errtestbytes, 1, (uint64_t *)0 ) ); 4108 TestR ( "init", fnvNull, 4109 FNV64init ( (FNV64context *)0 ) ); 4110 TestR ( "initBasis", fnvNull, 4111 FNV64initBasis ( (FNV64context *)0, 42 ) ); 4112 TestR ( "blockin", fnvNull, 4113 FNV64blockin ( (FNV64context *)0, 4114 errtestbytes, NTestBytes ) ); 4115 TestR ( "blockin", fnvNull, 4116 FNV64blockin ( &eContext, (uint8_t *)0, 4117 NTestBytes ) ); 4118 TestR ( "blockin", fnvBadParam, 4119 FNV64blockin ( &eContext, errtestbytes, -1 ) ); 4120 eContext.Computed = FNVclobber+FNV64state; 4121 TestR ( "blockin", fnvStateError, 4122 FNV64blockin ( &eContext, errtestbytes, 4123 NTestBytes ) ); 4124 TestR ( "stringin", fnvNull, 4125 FNV64stringin ( (FNV64context *)0, errteststring ) ); 4126 TestR ( "stringin", fnvNull, 4127 FNV64stringin ( &eContext, (char *)0 ) ); 4128 TestR ( "stringin", fnvStateError, 4129 FNV64stringin ( &eContext, errteststring ) ); 4130 TestR ( "result", fnvNull, 4131 FNV64result ( (FNV64context *)0, &eUint64 ) ); 4132 TestR ( "result", fnvNull, 4133 FNV64result ( &eContext, (uint64_t *)0 ) ); 4134 TestR ( "result", fnvStateError, 4135 FNV64result ( &eContext, &eUint64 ) ); 4136 if ( Terr ) 4137 printf ( "%s test of error checks failed %i times.0, 4138 funcName, Terr ); 4139 else 4140 printf ( "%s test of error checks passed0, funcName ); 4142 /* test actual results */ 4143 Terr = 0; 4144 for ( i = 0; i < NTstrings; ++i ) 4145 { 4146 err = TestR ( "string", fnvSuccess, 4147 FNV64string ( teststring[i], &eUint64 ) ); 4148 if ( err == fnvSuccess ) 4149 Test64Value ( "string", teststring[i], eUint64, 4150 FNV64svalues[i] ); 4151 err = TestR ( "block", fnvSuccess, 4152 FNV64block ( (uint8_t *)teststring[i], 4153 (unsigned long)(strlen(teststring[i])+1), 4154 &eUint64 ) ); 4155 if ( err == fnvSuccess ) 4156 Test64Value ( "block", teststring[i], eUint64, 4157 FNV64bvalues[i] ); 4158 /* now try testing the incremental stuff */ 4159 err = TestR ( "init", fnvSuccess, FNV64init ( &eContext ) ); 4161 } 4162 if ( Terr ) 4163 printf ( "%s test of return values failed %i times.0, 4164 funcName, Terr ); 4165 else 4166 printf ( "%s test of return values passed.0, funcName ); 4167 } /* end Test64 */ 4169 /* start Test64Value 4170 *****************************************************************/ 4171 void Test64Value ( char *subfunc, 4172 char *string, 4173 uint64_t should, 4174 uint64_t was ) 4175 { 4176 TestNValue(subfunc, string, sizeof(uint64_t), (uint8_t*)&was, 4177 . (uint8_t*)&should); 4178 } /* end Test64Value */ 4179 #else 4180 void Test64 () 4181 { 4182 /* TBD */ 4184 } 4185 #endif /* FNV_64bitIntegers */ 4187 /***************************************************************** 4188 * Code for FNV128 using 64-bit integers 4189 *****************************************************************/ 4191 void Test128 () 4192 { 4193 //int i, err; 4194 uint8_t eUint128[FNV128size]; 4195 FNV128context eContext; 4197 funcName = "FNV128"; 4199 /* test error checks */ 4200 Terr = 0; 4201 TestR ( "init", fnvSuccess, FNV128init (&eContext) ); 4202 TestR ( "string", fnvNull, 4203 FNV128string ( (char *)0, eUint128 ) ); 4204 TestR ( "string", fnvNull, 4205 FNV128string ( errteststring, (uint8_t *)0 ) ); 4206 TestR ( "block", fnvNull, 4207 FNV128block ( (uint8_t *)0, 1, eUint128 ) ); 4208 TestR ( "block", fnvBadParam, 4209 FNV128block ( errtestbytes, -1, eUint128 ) ); 4210 TestR ( "block", fnvNull, 4211 FNV128block ( errtestbytes, 1, (uint8_t *)0 ) ); 4212 TestR ( "init", fnvNull, 4213 FNV128init ( (FNV128context *)0 ) ); 4214 TestR ( "initBasis", fnvNull, 4215 FNV128initBasis ( (FNV128context *)0, eUint128 ) ); 4216 TestR ( "blockin", fnvNull, 4217 FNV128blockin ( (FNV128context *)0, 4218 errtestbytes, NTestBytes ) ); 4219 TestR ( "blockin", fnvNull, 4220 FNV128blockin ( &eContext, (uint8_t *)0, 4221 NTestBytes ) ); 4222 TestR ( "blockin", fnvBadParam, 4223 FNV128blockin ( &eContext, errtestbytes, -1 ) ); 4224 eContext.Computed = FNVclobber+FNV128state; 4225 TestR ( "blockin", fnvStateError, 4226 FNV128blockin ( &eContext, errtestbytes, 4227 NTestBytes ) ); 4228 TestR ( "stringin", fnvNull, 4229 FNV128stringin ( (FNV128context *)0, errteststring ) ); 4230 TestR ( "stringin", fnvNull, 4231 FNV128stringin ( &eContext, (char *)0 ) ); 4232 TestR ( "stringin", fnvStateError, 4233 FNV128stringin ( &eContext, errteststring ) ); 4234 TestR ( "result", fnvNull, 4235 FNV128result ( (FNV128context *)0, eUint128 ) ); 4236 TestR ( "result", fnvNull, 4237 FNV128result ( &eContext, (uint8_t *)0 ) ); 4238 TestR ( "result", fnvStateError, 4239 FNV128result ( &eContext, eUint128 ) ); 4240 if ( Terr ) 4241 printf ( "%s test of error checks failed %i times.0, 4242 funcName, Terr ); 4243 else 4244 printf ( "%s test of error checks passed0, funcName ); 4246 /* test actual results */ 4247 Terr = 0; 4248 /* tbd */ 4249 } /* end Test128 */ 4251 /***************************************************************** 4252 * Code for FNV256 using 64-bit integers 4253 *****************************************************************/ 4255 void Test256 () 4256 { 4257 //int i, err; 4258 uint8_t eUint256[FNV256size]; 4259 FNV256context eContext; 4261 funcName = "FNV256"; 4263 /* test error checks */ 4264 Terr = 0; 4265 TestR ( "init", fnvSuccess, FNV256init (&eContext) ); 4266 TestR ( "string", fnvNull, 4267 FNV256string ( (char *)0, eUint256 ) ); 4268 TestR ( "string", fnvNull, 4269 FNV256string ( errteststring, (uint8_t *)0 ) ); 4270 TestR ( "block", fnvNull, 4271 FNV256block ( (uint8_t *)0, 1, eUint256 ) ); 4272 TestR ( "block", fnvBadParam, 4273 FNV256block ( errtestbytes, -1, eUint256 ) ); 4274 TestR ( "block", fnvNull, 4275 FNV256block ( errtestbytes, 1, (uint8_t *)0 ) ); 4276 TestR ( "init", fnvNull, 4277 FNV256init ( (FNV256context *)0 ) ); 4278 TestR ( "initBasis", fnvNull, 4279 FNV256initBasis ( (FNV256context *)0, eUint256 ) ); 4280 TestR ( "blockin", fnvNull, 4281 FNV256blockin ( (FNV256context *)0, 4282 errtestbytes, NTestBytes ) ); 4283 TestR ( "blockin", fnvNull, 4284 FNV256blockin ( &eContext, (uint8_t *)0, 4285 NTestBytes ) ); 4286 TestR ( "blockin", fnvBadParam, 4287 FNV256blockin ( &eContext, errtestbytes, -1 ) ); 4288 eContext.Computed = FNVclobber+FNV256state; 4289 TestR ( "blockin", fnvStateError, 4290 FNV256blockin ( &eContext, errtestbytes, 4291 NTestBytes ) ); 4292 TestR ( "stringin", fnvNull, 4293 FNV256stringin ( (FNV256context *)0, errteststring ) ); 4294 TestR ( "stringin", fnvNull, 4295 FNV256stringin ( &eContext, (char *)0 ) ); 4296 TestR ( "stringin", fnvStateError, 4297 FNV256stringin ( &eContext, errteststring ) ); 4298 TestR ( "result", fnvNull, 4299 FNV256result ( (FNV256context *)0, eUint256 ) ); 4300 TestR ( "result", fnvNull, 4301 FNV256result ( &eContext, (uint8_t *)0 ) ); 4302 TestR ( "result", fnvStateError, 4303 FNV256result ( &eContext, eUint256 ) ); 4304 if ( Terr ) 4305 printf ( "%s test of error checks failed %i times.0, 4306 funcName, Terr ); 4307 else 4308 printf ( "%s test of error checks passed0, funcName ); 4310 /* test actual results */ 4311 Terr = 0; 4312 /* tbd */ 4313 } /* end Test256 */ 4315 /***************************************************************** 4316 * Code for FNV512 using 64-bit integers 4317 *****************************************************************/ 4319 void Test512 () 4320 { 4321 //int i, err; 4322 uint8_t eUint512[FNV512size]; 4323 FNV512context eContext; 4325 funcName = "FNV512"; 4327 /* test error checks */ 4328 Terr = 0; 4329 TestR ( "init", fnvSuccess, FNV512init (&eContext) ); 4330 TestR ( "string", fnvNull, 4331 FNV512string ( (char *)0, eUint512 ) ); 4332 TestR ( "string", fnvNull, 4333 FNV512string ( errteststring, (uint8_t *)0 ) ); 4334 TestR ( "block", fnvNull, 4335 FNV512block ( (uint8_t *)0, 1, eUint512 ) ); 4336 TestR ( "block", fnvBadParam, 4337 FNV512block ( errtestbytes, -1, eUint512 ) ); 4338 TestR ( "block", fnvNull, 4339 FNV512block ( errtestbytes, 1, (uint8_t *)0 ) ); 4340 TestR ( "init", fnvNull, 4341 FNV512init ( (FNV512context *)0 ) ); 4342 TestR ( "initBasis", fnvNull, 4343 FNV512initBasis ( (FNV512context *)0, eUint512 ) ); 4344 TestR ( "blockin", fnvNull, 4345 FNV512blockin ( (FNV512context *)0, 4346 errtestbytes, NTestBytes ) ); 4347 TestR ( "blockin", fnvNull, 4348 FNV512blockin ( &eContext, (uint8_t *)0, 4349 NTestBytes ) ); 4350 TestR ( "blockin", fnvBadParam, 4351 FNV512blockin ( &eContext, errtestbytes, -1 ) ); 4352 eContext.Computed = FNVclobber+FNV512state; 4353 TestR ( "blockin", fnvStateError, 4354 FNV512blockin ( &eContext, errtestbytes, 4355 NTestBytes ) ); 4356 TestR ( "stringin", fnvNull, 4357 FNV512stringin ( (FNV512context *)0, errteststring ) ); 4358 TestR ( "stringin", fnvNull, 4359 FNV512stringin ( &eContext, (char *)0 ) ); 4360 TestR ( "stringin", fnvStateError, 4361 FNV512stringin ( &eContext, errteststring ) ); 4362 TestR ( "result", fnvNull, 4363 FNV512result ( (FNV512context *)0, eUint512 ) ); 4364 TestR ( "result", fnvNull, 4365 FNV512result ( &eContext, (uint8_t *)0 ) ); 4366 TestR ( "result", fnvStateError, 4367 FNV512result ( &eContext, eUint512 ) ); 4368 if ( Terr ) 4369 printf ( "%s test of error checks failed %i times.0, 4370 funcName, Terr ); 4371 else 4372 printf ( "%s test of error checks passed0, funcName ); 4374 /* test actual results */ 4375 Terr = 0; 4376 /* tbd */ 4377 } /* end Test512 */ 4379 /***************************************************************** 4380 * Code for FNV1024 using 64-bit integers 4381 *****************************************************************/ 4383 void Test1024 () 4384 { 4385 //int i, err; 4386 uint8_t eUint1024[FNV1024size]; 4387 FNV1024context eContext; 4389 funcName = "FNV1024"; 4391 /* test error checks */ 4392 Terr = 0; 4393 TestR ( "init", fnvSuccess, FNV1024init (&eContext) ); 4394 TestR ( "string", fnvNull, 4395 FNV1024string ( (char *)0, eUint1024 ) ); 4396 TestR ( "string", fnvNull, 4397 FNV1024string ( errteststring, (uint8_t *)0 ) ); 4398 TestR ( "block", fnvNull, 4399 FNV1024block ( (uint8_t *)0, 1, eUint1024 ) ); 4400 TestR ( "block", fnvBadParam, 4401 FNV1024block ( errtestbytes, -1, eUint1024 ) ); 4402 TestR ( "block", fnvNull, 4403 FNV1024block ( errtestbytes, 1, (uint8_t *)0 ) ); 4404 TestR ( "init", fnvNull, 4405 FNV1024init ( (FNV1024context *)0 ) ); 4406 TestR ( "initBasis", fnvNull, 4407 FNV1024initBasis ( (FNV1024context *)0, eUint1024 ) ); 4408 TestR ( "blockin", fnvNull, 4409 FNV1024blockin ( (FNV1024context *)0, 4410 errtestbytes, NTestBytes ) ); 4411 TestR ( "blockin", fnvNull, 4412 FNV1024blockin ( &eContext, (uint8_t *)0, 4413 NTestBytes ) ); 4414 TestR ( "blockin", fnvBadParam, 4415 FNV1024blockin ( &eContext, errtestbytes, -1 ) ); 4416 eContext.Computed = FNVclobber+FNV1024state; 4417 TestR ( "blockin", fnvStateError, 4418 FNV1024blockin ( &eContext, errtestbytes, 4419 NTestBytes ) ); 4420 TestR ( "stringin", fnvNull, 4421 FNV1024stringin ( (FNV1024context *)0, errteststring ) ); 4422 TestR ( "stringin", fnvNull, 4423 FNV1024stringin ( &eContext, (char *)0 ) ); 4424 TestR ( "stringin", fnvStateError, 4425 FNV1024stringin ( &eContext, errteststring ) ); 4426 TestR ( "result", fnvNull, 4427 FNV1024result ( (FNV1024context *)0, eUint1024 ) ); 4428 TestR ( "result", fnvNull, 4429 FNV1024result ( &eContext, (uint8_t *)0 ) ); 4431 TestR ( "result", fnvStateError, 4432 FNV1024result ( &eContext, eUint1024 ) ); 4433 if ( Terr ) 4434 printf ( "%s test of error checks failed %i times.0, 4435 funcName, Terr ); 4436 else 4437 printf ( "%s test of error checks passed0, funcName ); 4439 /* test actual results */ 4440 Terr = 0; 4441 /* tbd */ 4442 } /* end Test1024 */ 4443 4445 7. Security Considerations 4447 This document is intended to provide convenient open source access by 4448 the Internet community to the FNV non-cryptographic hash. No 4449 assertion of suitability for cryptographic applications is made for 4450 the FNV hash algorithms. 4452 7.1 Why is FNV Non-Cryptographic? 4454 A full discussion of cryptographic hash requirements and strength is 4455 beyond the scope of this document. However, here are three 4456 characteristics of FNV that would generally be considered to make it 4457 non-cryptographic: 4459 1. Sticky State - A cryptographic hash should not have a state in 4460 which it can stick for a plausible input pattern. But, in the very 4461 unlikely event that the FNV hash variable becomes zero and the 4462 input is a sequence of zeros, the hash variable will remain at 4463 zero until there is a non-zero input byte and the final hash value 4464 will be unaffected by the length of that sequence of zero input 4465 bytes. Of course, for the common case of fixed length input, this 4466 would usually not be significant because the number of non-zero 4467 bytes would vary inversely with the number of zero bytes and for 4468 some types of input, runs of zeros do not occur. Furthermore, the 4469 inclusion of even a little unpredictable input may be sufficient 4470 to stop an adversary from inducing a zero hash variable. 4472 2. Diffusion - Every output bit of a cryptographic hash should be an 4473 equally complex function of every input bit. But it is easy to see 4474 that the least significant bit of a direct FNV hash is the XOR of 4475 the least significant bits of every input byte and does not depend 4476 on any other input bit. While more complex, the second through 4477 seventh least significant bits of an FNV hash have a similar 4478 weakness; only the top bit of the bottom byte of output, and 4479 higher order bits, depend on all input bits. If these properties 4480 are considered a problem, they can be easily fixed by XOR folding 4481 (see Section 3). 4483 3. Work Factor - Depending on intended use, it is frequently 4484 desirable that a hash function should be computationally expensive 4485 for general purpose and graphics processors since these may be 4486 profusely available through elastic cloud services or botnets. 4487 This is to slow down testing of possible inputs if the output is 4488 known. But FNV is designed to be very inexpensive on a general- 4489 purpose processor. (See Appendix A.) 4491 Nevertheless, none of the above have proven to be a problem in actual 4492 practice for the many applications of FNV. 4494 7.2 Inducing Collisions 4496 While use of a cryptographic hash should be considered when active 4497 adversaries are a factor, the following attack can be made much more 4498 difficult with very minor changes in the use of FNV. 4500 If FNV is being used in a known way for hash tables in a network 4501 server or the like, for example some part of a web server, an 4502 adversary could send requests calculated to cause hash table 4503 collisions and induce substantial processing delays. As mentioned in 4504 Section 2.2, use of an offset_basis not knownable by the adversary 4505 will substantially eliminate this problem. 4507 8. IANA Considerations 4509 This document requires no IANA Actions. RFC Ediotor: Please delete 4510 this section before publication. 4512 Normative References 4514 [RFC20] - Cerf, V., "ASCII format for network interchange", STD 80, 4515 RFC 20, October 1969, . 4517 Informative References 4519 [FNV] - FNV web site: 4520 http://www.isthe.com/chongo/tech/comp/fnv/index.html 4522 [IEEE] - http://www.ieee.org 4524 [IPv6flow] - https://researchspace.auckland.ac.nz/bitstream/handle/ 4525 2292/13240/flowhashRep.pdf 4527 [RFC2460] - Deering, S. and R. Hinden, "Internet Protocol, Version 6 4528 (IPv6) Specification", RFC 2460, December 1998, 4529 . 4531 [RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm 4532 1 (SHA1)", RFC 3174, September 2001. 4534 [RFC6194] - Polk, T., Chen, L., Turner, S., and P. Hoffman, "Security 4535 Considerations for the SHA-0 and SHA-1 Message-Digest 4536 Algorithms", RFC 6194, March 2011. 4538 [RFC6234] - Eastlake 3rd, D. and T. Hansen, "US Secure Hash 4539 Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 4540 2011. 4542 [RFC6437] - Amante, S., Carpenter, B., Jiang, S., and J. Rajahalme, 4543 "IPv6 Flow Label Specification", RFC 6437, November 2011, 4544 . 4546 Acknowledgements 4548 The contributions of the following are gratefully acknowledged: 4550 Roman Donchenko, Frank Ellermann, Tony Finch, Bob Moskowitz, 4551 Gayle Noble, Stefan Santesson, and Mukund Sivaraman. 4553 Appendix A: Work Comparison with SHA-1 4555 This section provides a simplistic rough comparison of the level of 4556 effort required per input byte to compute FNV-1a and SHA-1 [RFC3174]. 4558 Ignoring transfer of control and conditional tests and equating all 4559 logical and arithmetic operations, FNV requires 2 operations per 4560 byte, an XOR and a multiply. 4562 SHA-1 is a relatively weak cryptographic hash producing a 160-bit 4563 hash. It has been partially broken [RFC6194]. It is actually designed 4564 to accept a bit vector input although almost all computer uses apply 4565 it to an integer number of bytes. It processes blocks of 512 bits (64 4566 bytes) and we estimate the effort involved in SHA-1 processing a full 4567 block. Ignoring SHA-1 initial set up, transfer of control, and 4568 conditional tests, but counting all logical and arithmetic 4569 operations, including counting indexing as an addition, SHA-1 4570 requires 1,744 operations per 64 bytes block or 27.25 operations per 4571 byte. So by this rough measure, it is a little over 13 times the 4572 effort of FNV for large amounts of data. However, FNV is commonly 4573 used for small inputs. Using the above method, for inputs of N bytes, 4574 where N is <= 55 so SHA-1 will take one block (SHA-1 includes padding 4575 and an 8-byte length at the end of the data in the last block), the 4576 ratio of the effort for SHA-1 to the effort for FNV will be 872/N. 4577 For example, with an 8 byte input, SHA-1 will take 109 times as much 4578 effort as FNV. 4580 Stronger cryptographic functions than SHA-1 generally have an even 4581 higher work factor. 4583 Appendix B: Previous IETF Reference to FNV 4585 FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has 4586 since expired. It was later decided that it would be better to use a 4587 cryptographic hash for that application. 4589 Below is the Java code for FNV64 from that TLS draft included by the 4590 kind permission of the author: 4592 4593 /** 4594 * Java code sample, implementing 64 bit FNV-1a 4595 * By Stefan Santesson 4596 */ 4598 import java.math.BigInteger; 4600 public class FNV { 4602 static public BigInteger getFNV1aToByte(byte[] inp) { 4604 BigInteger m = new BigInteger("2").pow(64); 4605 BigInteger fnvPrime = new BigInteger("1099511628211"); 4606 BigInteger fnvOffsetBasis = 4607 new BigInteger("14695981039346656037"); 4609 BigInteger digest = fnvOffsetBasis; 4611 for (byte b : inp) { 4612 digest = digest.xor(BigInteger.valueOf((int) b & 255)); 4613 digest = digest.multiply(fnvPrime).mod(m); 4614 } 4615 return digest; 4617 } 4618 } 4619 4621 Appendix C: A Few Test Vectors 4623 Below are a few test vectors in the form of ASCII strings and their 4624 FNV32 and FNV64 hashes using the FNV-1a algorithm. 4626 Strings without null (zero byte) termination: 4628 String FNV32 FNV64 4629 "" 0x811c9dc5 0xcbf29ce484222325 4630 "a" 0xe40c292c 0xaf63dc4c8601ec8c 4631 "foobar" 0xbf9cf968 0x85944171f73967e8 4633 Strings including null (zero byte) termination: 4635 String FNV32 FNV64 4636 "" 0x050c5d1f 0xaf63bd4c8601b7df 4637 "a" 0x2b24d044 0x089be207b544f1e4 4638 "foobar" 0x0c1c9eb8 0x34531ca7168b8f38 4640 Appendix Z: Change Summary 4642 RFC Editor Note: Please delete this appendix on publication. 4644 From -00 to -01 4646 1. Add Security Considerations section on why FNV is non- 4647 cryptographic. 4649 2. Add Appendix A on a work factor comparison with SHA-1. 4651 3. Add Appendix B concerning previous IETF draft referenced to FNV. 4653 4. Minor editorial changes. 4655 From -01 to -02 4657 1. Correct FNV_Prime determination criteria and add note as to why s 4658 < 5 and s > 10 are not considered. 4660 2. Add acknowledgements list. 4662 3. Add a couple of references. 4664 4. Minor editorial changes. 4666 From -02 to -03 4668 1. Replace direct reference to US-ASCII standard with reference to 4669 RFC 20. 4671 2. Update dates and version number. 4673 3. Minor editing changes. 4675 From -03 to -04 4677 1. Change reference to RFC 20 back to a reference to the ANSI 1968 4678 ASCII standard. 4680 2. Minor addition to Section 6, point 3. 4682 3. Update dates and version number. 4684 4. Minor editing changes. 4686 From -04 to -05 4688 1. Add Twitter as a use example and IPv6 flow hash study reference. 4690 2. Update dates and version number. 4692 From -05 to -06 4694 1. Add code subsections. 4696 2. Update dates and version number. 4698 From -06 to -07 to -08 4700 1. Update Author info. 4702 2. Minor edits. 4704 From -08 to -09 4706 1. Change reference for ASCII to [RFC20]. 4708 2. Add more details on history of the string used to compute 4709 offset_basis. 4711 3. Re-write "Work Factor" part of Section 6 to be more precise. 4713 4. Minor editorial changes. 4715 From -09 to -10 4717 1. Inclusion of initial partial version of code and some 4718 documentation about the code, Section 6. 4720 2. Insertion of new Section 4 on hashing values. 4722 From -10 to -11 4724 Changes based on code improvements primarily from Tony Hansen who has 4725 been added as an author. Changes based on comments from Mukund 4726 Sivaraman and Roman Donchenko. 4728 Author's Address 4730 Glenn Fowler 4731 Google 4733 Email: glenn.s.fowler@gmail.com 4735 Landon Curt Noll 4736 Cisco Systems 4737 170 West Tasman Drive 4738 San Jose, CA 95134 USA 4740 Telephone: +1-408-424-1102 4741 Email: fnv-ietf2-mail@asthe.com 4742 URL: http://www.isthe.com/chongo/index.html 4744 Kiem-Phong Vo 4745 Google 4747 Email: phongvo@gmail.com 4749 Donald Eastlake 4750 Huawei Technologies 4751 155 Beaver Street 4752 Milford, MA 01757 USA 4754 Telephone: +1-508-333-2270 4755 EMail: d3e3e3@gmail.com 4757 Tony Hansen 4758 AT&T Laboratories 4759 200 Laurel Ave. South 4760 Middletown, NJ 07748 4761 USA 4763 Email: tony@att.com 4765 Copyright, Disclaimer, and Additional IPR Provisions 4767 Copyright (c) 2016 IETF Trust and the persons identified as the 4768 document authors. All rights reserved. 4770 This document is subject to BCP 78 and the IETF Trust's Legal 4771 Provisions Relating to IETF Documents 4772 (http://trustee.ietf.org/license-info) in effect on the date of 4773 publication of this document. Please review these documents 4774 carefully, as they describe your rights and restrictions with respect 4775 to this document. Code Components extracted from this document must 4776 include Simplified BSD License text as described in Section 4.e of 4777 the Trust Legal Provisions and are provided without warranty as 4778 described in the Simplified BSD License. This Internet-Draft is 4779 submitted to IETF in full conformance with the provisions of BCP 78 4780 and BCP 79.