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