idnits 2.17.1 draft-eastlake-fnv-10.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 228 has weird spacing: '...ed char hash...' == Line 1339 has weird spacing: '...int i;...' == Line 1516 has weird spacing: '...context ctx...' == Line 1532 has weird spacing: '...context ctx...' == Line 1912 has weird spacing: '...int i;...' == (12 more instances...) -- The document date (October 6, 2015) is 3115 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'N' is mentioned on line 228, but not defined -- Obsolete informational reference (is this intentional?): RFC 2460 (Obsoleted by RFC 8200) Summary: 0 errors (**), 0 flaws (~~), 8 warnings (==), 2 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 Expires: April 5, 2016 October 6, 2015 11 The FNV Non-Cryptographic Hash Algorithm 12 14 Abstract 16 FNV (Fowler/Noll/Vo) is a fast, non-cryptographic hash algorithm with 17 good dispersion. The purpose of this document is to make information 18 on FNV and open source code performing FNV conveniently available to 19 the Internet community. 21 Status of This Memo 23 This Internet-Draft is submitted to IETF in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Distribution of this document is unlimited. Comments should be sent 27 to the authors. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF), its areas, and its working groups. Note that 31 other groups may also distribute working documents as Internet- 32 Drafts. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 The list of current Internet-Drafts can be accessed at 40 http://www.ietf.org/1id-abstracts.html. The list of Internet-Draft 41 Shadow Directories can be accessed at 42 http://www.ietf.org/shadow.html. 44 Table of Contents 46 1. Introduction............................................3 48 2. FNV Basics..............................................4 49 2.1 FNV Primes.............................................4 50 2.2 FNV offset_basis.......................................5 51 2.3 FNV Endianism..........................................5 53 3. Other Hash Sizes and XOR Folding........................7 54 4. Hashing Multiple Values Together........................8 55 5. FNV Constants...........................................9 57 6. The Source Code........................................11 58 6.1 FNV-1a C Code.........................................11 59 6.1.1 FNV32 Code..........................................13 60 6.1.2 FNV64 C Code........................................19 61 6.1.3 FNV128 C Code.......................................30 62 6.1.4 FNV256 C Code.......................................42 63 6.1.5 FNV512 C Code.......................................54 64 6.1.6 FNV1024 C Code......................................65 65 6.2 FNV Test Code.........................................68 67 7. Security Considerations................................79 68 7.1 Why is FNV Non-Cryptographic?.........................79 70 8. IANA Considerations....................................80 72 Normative References......................................80 73 Informative References....................................80 74 Acknowledgements..........................................81 76 Appendix A: Work Comparison with SHA-1....................82 77 Appendix B: Previous IETF Reference to FNV................83 79 Appendix Z: Change Summary................................84 80 From -00 to -01...........................................84 81 From -01 to -02...........................................84 82 From -02 to -03...........................................84 83 From -03 to -04...........................................84 84 From -04 to -05...........................................85 85 From -05 to -06...........................................85 86 From -06 to -07 to -08....................................85 87 From -08 to -09...........................................85 88 From -09 to -10...........................................85 90 Author's Address..........................................86 92 1. Introduction 94 The FNV hash algorithm is based on an idea sent as reviewer comments 95 to the [IEEE] POSIX P1003.2 committee by Glenn Fowler and Phong Vo in 96 1991. In a subsequent ballot round Landon Curt Noll suggested an 97 improvement on their algorithm. Some people tried this hash and found 98 that it worked rather well. In an EMail message to Landon, they named 99 it the "Fowler/Noll/Vo" or FNV hash. [FNV] 101 FNV hashes are designed to be fast while maintaining a low collision 102 rate. The high dispersion of the FNV hashes makes them well suited 103 for hashing nearly identical strings such as URLs, hostnames, 104 filenames, text, IP addresses, etc. Their speed allows one to quickly 105 hash lots of data while maintaining a reasonably low collision rate. 106 However, they are generally not suitable for cryptographic use. (See 107 Section 7.1.) 109 The FNV hash is widely used, for example in DNS servers, the Twitter 110 service, database indexing hashes, major web search / indexing 111 engines, netnews history file Message-ID lookup functions, anti-spam 112 filters, a spellchecker programmed in Ada 95, flatassembler's open 113 source x86 assembler - user-defined symbol hashtree, non- 114 cryptographic file fingerprints, computing Unique IDs in DASM (DTN 115 (Delay Tolerant Networking) Applications for Symbian Mobile-phones), 116 Microsoft's hash_map implementation for VC++ 2005, the realpath cache 117 in PHP 5.x (php-5.2.3/TSRM/tsrm_virtual_cwd.c), and many other uses. 119 A study has recommended FNV in connection with the IPv6 Flow Label 120 field [IPv6flow]. 122 FNV hash algorithms and source code have been released into the 123 public domain. The authors of the FNV algorithm took deliberate steps 124 to disclose the algorithm in a public forum soon after it was 125 invented. More than a year passed after this public disclosure and 126 the authors deliberately took no steps to patent the FNV algorithm. 127 Therefore, it is safe to say that the FNV authors have no patent 128 claims on the FNV algorithm as published. 130 If you use an FNV function in an application, you are kindly 131 requested to send an EMail about it to: fnv-mail@asthe.com 133 2. FNV Basics 135 This document focuses on the FNV-1a function whose pseudo-code is as 136 follows: 138 hash = offset_basis 139 for each octet_of_data to be hashed 140 hash = hash xor octet_of_data 141 hash = hash * FNV_Prime 142 return hash 144 In the pseudo-code above, hash is a power-of-two number of bits (32, 145 64, ... 1024) and offset_basis and FNV_Prime depend on the size of 146 hash. 148 The FNV-1 algorithm is the same, including the values of offset_basis 149 and FNV_Prime, except that the order of the two lines with the "xor" 150 and multiply operations are reversed. Operational experience 151 indicates better hash dispersion for small amounts of data with 152 FNV-1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero. 153 FNV-1a is suggested for general use. 155 2.1 FNV Primes 157 The theory behind FNV_Prime's is beyond the scope of this document 158 but the basic property to look for is how an FNV_Prime would impact 159 dispersion. Now, consider any n-bit FNV hash where n is >= 32 and 160 also a power of 2. For each such n-bit FNV hash, an FNV_Prime p is 161 defined as: 163 When s is an integer and 4 < s < 11, then FNV_Prime is the 164 smallest prime p of the form: 166 256**int((5 + 2^s)/12) + 2**8 + b 168 where b is an integer such that: 170 0 < b < 2**8 171 The number of one-bits in b is 4 or 5 173 and where p mod (2**40 - 2**24 - 1) > (2**24 + 2**8 + 2**7). 175 Experimentally, FNV_Primes matching the above constraints tend to 176 have better dispersion properties. They improve the polynomial 177 feedback characteristic when an FNV_Prime multiplies an intermediate 178 hash value. As such, the hash values produced are more scattered 179 throughout the n-bit hash space. 181 The case where s < 5 is not considered because the resulting hash 182 quality is too low. Such small hashes can, if desired, be derived 183 from a 32 bit FNV hash by XOR folding (see Section 3). The case where 184 s > 10 is not considered because of the doubtful utility of such 185 large FNV hashes and because the criteria for such large FNV_Primes 186 is more complex, due to the sparsity of such large primes, and would 187 needlessly clutter the criteria given above. 189 Per the above constraints, an FNV_Prime should have only 6 or 7 one- 190 bits in it. Therefore, some compilers may seek to improve the 191 performance of a multiplication with an FNV_Prime by replacing the 192 multiplication with shifts and adds. However, note that the 193 performance of this substitution is highly hardware-dependent and 194 should be done with care. FNV_Primes were selected primarily for the 195 quality of resulting hash function, not for compiler optimization. 197 2.2 FNV offset_basis 199 The offset_basis values for the n-bit FNV-1a algorithms are computed 200 by applying the n-bit FNV-0 algorithm to the 32 octets representing 201 the following character string in [RFC20]: 203 chongo /\../\ 205 The \'s in the above string are not C-style escape characters. In C- 206 string notation, these 32 octets are: 208 "chongo /\\../\\" 210 That string was used because the person testing FNV with non-zero 211 offset_basis values was looking at an email message from Landon and 212 was copying his standard email signature line; however, they couldn't 213 see very well and copied it incorrectly. In fact, he uses 215 chongo (Landon Curt Noll) /\oo/\ 217 but, since it doesn't matter, no effort has been made to correct 218 this. In the general case, almost any offset_basis will serve so 219 long as it is non-zero. 221 2.3 FNV Endianism 223 For persistent storage or interoperability between different hardware 224 platforms, an FNV hash shall be represented in the little endian 225 format. That is, the FNV hash will be stored in an array hash[N] with 226 N bytes such that its integer value can be retrieved as follows: 228 unsigned char hash[N]; 229 for ( i = N-1, value = 0; i >= 0; --i ) 230 value = value << 8 + hash[i]; 232 Of course, when FNV hashes are used in a single process or a group of 233 processes sharing memory on processors with compatible endian-ness, 234 the natural endianness of those processors can be used regardless of 235 its type, little, big, or some other exotic form. 237 3. Other Hash Sizes and XOR Folding 239 Many hash uses require a hash that is not one of the FNV sizes for 240 which constants are provided in Section 5. If a larger hash size is 241 needed, please contact the authors of this document. 243 Most hash applications make use of a hash that is a fixed size binary 244 field. Assume that k bits of hash are desired and k is less than 1024 245 but not one of the sizes for which constants are provided in Section 246 5. The recommended technique is to take the smallest FNV hash of size 247 S, where S is larger than k, and calculate the desired hash using xor 248 folding as shown below. The final bit masking operation is logically 249 unnecessarily if the size of hash is exactly the number of desired 250 bits. 252 temp = FNV_S ( data-to-be-hashed ) 253 hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 ) 255 Hash functions are a trade-off between speed and strength. For 256 example, a somewhat stronger hash may be obtained for exact FNV sizes 257 by calculating an FNV twice as long as the desired output ( S = 2*k ) 258 and performing such data folding using a k equal to the size of the 259 desired output. However, if a much stronger hash, for example one 260 suitable for cryptographic applications, is wanted, algorithms 261 designed for that purpose, such as those in [RFC6234], should be 262 used. 264 If it is desired to obtain a hash result that is a value between 0 265 and max, where max is a not a power of two, simply choose an FNV hash 266 size S such that 2**S > max. Then calculate the following: 268 FNV_S mod ( max+1 ) 270 The resulting remainder will be in the range desired but will suffer 271 from a bias against large values with the bias being larger if 2**S 272 is only a little bigger than max. If this bias is acceptable, no 273 further processing is needed. If this bias is unacceptable, it can be 274 avoided by retrying for certain high values of hash, as follows, 275 before applying the mod operation above: 277 X = ( int( ( 2**S - 1 ) / ( max+1 ) ) ) * ( max+1 ) 278 while ( hash >= X ) 279 hash = ( hash * FNV_Prime ) + offset_basis 281 4. Hashing Multiple Values Together 283 It is common for there to be a few different component values, say 284 three strings X, Y, and Z, where a hash over all of them is desired. 285 The simplest thing to do is to concatenate them and compute the hash 286 of that concatenation, as in 288 hash ( X | Y | Z ) 290 where the vertical bar character ("|") represents string 291 concatenation. Note that, for FNV, the same hash results if X, Y, 292 and Z are actually concatenated and the FNV hash applied to the 293 resulting string or if FNV is calculated on an initial substring and 294 the result used as the offset_basis when calculating the FNV hash of 295 the remainder of the string. This can be done several times. 296 Assuming FNVoffset_basis ( v, w ) is FNV of w using v as the 297 offset_basis, then in the example above, fnvx = FNV ( X ) could be 298 calculated and then fnvxy = FNVoffset_basis ( fnvx, Y ), and finally 299 fnvxyz = FNVoffset_basis ( fnvxy, Z). The resulting fnvxyz would be 300 the same as FNV ( X | Y | Z ); 302 Cases are also common where such a hash needs to be repeatedly 303 calculated where the component values vary but some vary more 304 frequently than others. For example, assume some sort of computer 305 network traffic flow ID, such as the IPv6 flow ID [RFC6437], is to be 306 calculated for network packets based on the source and destination 307 IPv6 address and the Traffic Class [RFC2460]. If the Flow ID is 308 calculate in the originating host, the source IPv6 address would 309 likely always be the same or perhaps assume one of a very small 310 number of values. By placing this quasi-constant IPv6 source address 311 first in the string being FNV hashed, FNV ( IPv6source ) could be 312 calculated and used as the offset_basis for calculating FNV of the 313 IPv6 destination address and Traffic Class for each packet. As a 314 result, the per packet hash would be over 17 bytes rather than over 315 33 bytes saving computational resources. The code in this document 316 includes functions facilitating the use of a non-standard 317 offset_basis. 319 5. FNV Constants 321 The FNV Primes are as follows: 323 32 bit FNV_Prime = 2**24 + 2**8 + 0x93 = 16,777,619 324 = 0x01000193 326 64 bit FNV_Prime = 2**40 + 2**8 + 0xB3 = 1,099,511,628,211 327 = 0x00000100 000001B3 329 128 bit FNV_Prime = 2**88 + 2**8 + 0x3B = 330 309,485,009,821,345,068,724,781,371 331 = 0x00000000 01000000 00000000 0000013B 333 256 bit FNV_Prime = 2**168 + 2**8 + 0x63 = 334 374,144,419,156,711,147,060,143,317,175,368,453,031,918,731,002,211 = 335 0x0000000000000000 0000010000000000 0000000000000000 0000000000000163 337 512 bit FNV_Prime = 2**344 + 2**8 + 0x57 = 35, 338 835,915,874,844,867,368,919,076,489,095,108,449,946,327,955,754,392, 339 558,399,825,615,420,669,938,882,575,126,094,039,892,345,713,852,759 = 340 0x0000000000000000 0000000000000000 0000000001000000 0000000000000000 341 0000000000000000 0000000000000000 0000000000000000 0000000000000157 343 1024 bit FNV_Prime = 2**680 + 2**8 + 0x8D = 5, 344 016,456,510,113,118,655,434,598,811,035,278,955,030,765,345,404,790, 345 744,303,017,523,831,112,055,108,147,451,509,157,692,220,295,382,716, 346 162,651,878,526,895,249,385,292,291,816,524,375,083,746,691,371,804, 347 094,271,873,160,484,737,966,720,260,389,217,684,476,157,468,082,573 = 348 0x0000000000000000 0000000000000000 0000000000000000 0000000000000000 349 0000000000000000 0000010000000000 0000000000000000 0000000000000000 350 0000000000000000 0000000000000000 0000000000000000 0000000000000000 351 0000000000000000 0000000000000000 0000000000000000 000000000000018D 353 The FNV offset_basis values are as follows: 355 32 bit offset_basis = 2,166,136,261 = 0x811C9DC5 357 64 bit offset_basis = 14695981039346656037 = 0xCBF29CE4 84222325 359 128 bit offset_basis = 144066263297769815596495629667062367629 = 360 0x6C62272E 07BB0142 62B82175 6295C58D 362 256 bit offset_basis = 100,029,257,958,052,580,907,070,968, 363 620,625,704,837,092,796,014,241,193,945,225,284,501,741,471,925,557 = 364 0xDD268DBCAAC55036 2D98C384C4E576CC C8B1536847B6BBB3 1023B4C8CAEE0535 365 512 bit offset_basis = 9, 366 659,303,129,496,669,498,009,435,400,716,310,466,090,418,745,672,637, 367 896,108,374,329,434,462,657,994,582,932,197,716,438,449,813,051,892, 368 206,539,805,784,495,328,239,340,083,876,191,928,701,583,869,517,785 = 369 0xB86DB0B1171F4416 DCA1E50F309990AC AC87D059C9000000 0000000000000D21 370 E948F68A34C192F6 2EA79BC942DBE7CE 182036415F56E34B AC982AAC4AFE9FD9 372 1024 bit offset_basis = 14,197,795,064,947,621,068,722,070,641,403, 373 218,320,880,622,795,441,933,960,878,474,914,617,582,723,252,296,732, 374 303,717,722,150,864,096,521,202,355,549,365,628,174,669,108,571,814, 375 760,471,015,076,148,029,755,969,804,077,320,157,692,458,563,003,215, 376 304,957,150,157,403,644,460,363,550,505,412,711,285,966,361,610,267, 377 868,082,893,823,963,790,439,336,411,086,884,584,107,735,010,676,915 = 378 0x0000000000000000 005F7A76758ECC4D 32E56D5A591028B7 4B29FC4223FDADA1 379 6C3BF34EDA3674DA 9A21D90000000000 0000000000000000 0000000000000000 380 0000000000000000 0000000000000000 0000000000000000 000000000004C6D7 381 EB6E73802734510A 555F256CC005AE55 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 383 6. The Source Code 385 [This section is not yet complete.] 387 The following sub-sections provide reference C source code and a test 388 driver for FNV-1a. 390 Alternative source code, including 32 and 64 bit FNV-1 and FNV-1a in 391 x86 assembler, is currently available at [FNV]. 393 Section 6.2 provides a test driver. 395 6.1 FNV-1a C Code 397 This section provides the direct FNV-1a function for each of the 398 lengths for which it is specified in this document. The following 399 functions are provided, where XXX is "32", "64", "128", "256", "512", 400 or "1024": 402 FNVXXXstring, FNVXXXblock: These are simple functions for directly 403 returning the FNV hash of a zero terminated byte string not 404 including the zero and the FNV hash of a counted block of 405 bytes. Note that for applications of FNV-32 where 32-bit 406 integers are supported and FNV-64 where 64-bit integers are 407 supported, the code is sufficiently simple that use of open 408 coding or macros may be more appropriate to maximize 409 performance. 411 FNVXXXinit, FNVXXXinitBasis: These function and the next two sets of 412 functions below provide facilities for incrementally 413 calculating FNV hashes. They all assume a data structure of 414 type FNVXXXcontext that holds the current state of the hash. 415 FNVXXXinit initializes that context to the standard 416 offset_basis. FNVXXXinitBasis takes an offset_basis value as a 417 parameter and may be useful for hashing concatenations, as 418 described in Section 4, as well as for simply using a non- 419 standard offset_basis. 421 FNXXXVblockin, FNVXXXstringin: These functions hash a sequence of 422 bytes into an FNVXXXcontext that was originally initialized by 423 FNVXXXinit or FNVXXXinitBasis. FNVXXXblockin hashes in a 424 counted block of bytes. FNVXXXstringin hashes in a zero 425 terminated byte string not incuding the final zero. 427 FNVXXXresult: This function extracts the final FNV hash result from 428 an FNVXXXcontext. 430 The following code is a private header file used by all the FNV 431 functions further below and which states the terms for use and 432 redistribution of all of this code. 434 435 /************************ fnv-private.h ************************/ 436 /****************** See RFC NNNN for details *******************/ 437 /* Copyright (c) 2015 IETF Trust and the persons identified as 438 * authors of the code. All rights reserved. 439 * 440 * Redistribution and use in source and binary forms, with or without 441 * modification, are permitted provided that the following conditions 442 * are met: 443 * 444 * * Redistributions of source code must retain the above copyright 445 * notice, this list of conditions and the following disclaimer. 446 * 447 * * Redistributions in binary form must reproduce the above copyright 448 * notice, this list of conditions and the following disclaimer in 449 * the documentation and/or other materials provided with the 450 * distribution. 451 * 452 * * Neither the name of Internet Society, IETF or IETF Trust, nor the 453 * names of specific contributors, may be used to endorse or promote 454 * products derived from this software without specific prior 455 * written permission. 456 * 457 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 458 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 459 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 460 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 461 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 462 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 463 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 464 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 465 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 466 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 467 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 468 * POSSIBILITY OF SUCH DAMAGE. 469 */ 471 #ifndef _FNV_PRIVATE_H_ 472 #define _FNV_PRIVATE_H_ 474 /* 475 * Six FNV-1a hashes are defined with these sizes: 476 * FNV32 32 bit, 4 byte 477 * FNV64 64 bit, 8 byte 478 * FNV128 128 bit, 16 byte 479 * FNV256 256 bit, 32 byte 480 * FNV512 512 bit, 64 byte 481 * FNV1024 1024 bit, 128 bytes 482 */ 484 /* Private stuff used by this implementation of the FNV 485 * (Fowler, Noll, Vo) non-cryptographic hash function FNV-1a. 486 * External callers don't need to know any of this. */ 488 enum { /* State value bases for context->Computed */ 489 FNVinited = 22, 490 FNVcomputed = 76, 491 FNVemptied = 220, 492 FNVclobber = 122 /* know bad value for testing */ 493 }; 495 /* Deltas to assure distinct state values for different lengths */ 496 enum { 497 FNV32state = 1, 498 FNV64state = 3, 499 FNV128state = 5, 500 FNV256state = 7, 501 FNV512state = 11, 502 FNV1024state = 13 503 }; 505 #endif 506 508 6.1.1 FNV32 Code 510 The header and C source for 32-bit FNV-1a. 512 513 /***************************** FNV32.h ******************************/ 514 /******************** See RFC NNNN for details **********************/ 515 /* 516 * Copyright (c) 2015 IETF Trust and the persons identified as 517 * authors of the code. All rights reserved. 518 * See fnv-private.h for terms of use and redistribution. 519 */ 521 #ifndef _FNV32_H_ 522 #define _FNV32_H_ 524 /* 525 * Description: 526 * This file provides headers for the 32-bit version of the FNV-1a 527 * non-cryptographic hash algorithm. 528 * 529 * >>>>>>>> IMPORTANT CONFIGURATION ifdef: <<<<<<<<<< 530 * 531 * FNV_BigEndian - Define this ONLY if your system uses big 532 * endian representation AND your FNV hashes need to 533 * interoperate with little endian systems. If you #define 534 * this symbol when not needed, it will unnecessarily slow 535 * execution and increase the code size of FNV functions. 536 * 537 * It is assumed that your system supports 32-bit arithemetic 538 * including 6-bit x 16-bit multiplication producing a 539 * 32-bit result. 540 */ 542 #include 543 /* #define FNV32size (32/8) not used */ 545 /* If you do not have the ISO standard stdint.h header file, then you 546 * must typedef the following types: 547 * 548 * type meaning 549 * uint32_t unsigned 32 bit integer 550 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 551 */ 553 #ifndef _FNV_ErrCodes_ 554 #define _FNV_ErrCodes_ 555 /******************************************************************** 556 * All FNV functions provided return as integer as follows: 557 * 0 -> success 558 * >0 -> error as listed below 559 */ 560 enum { /* success and errors */ 561 fnvSuccess = 0, 562 fnvNull, /* Null pointer parameter */ 563 fnvStateError, /* called Input after Result, etc. */ 564 fnvBadParam /* passed a bad parameter */ 565 }; 566 #endif /* _FNV_ErrCodes_ */ 568 /* 569 * This structure holds context information for an FNV32 hash 570 */ 571 typedef struct FNV32context_s { 572 int Computed; /* state */ 573 uint32_t Hash; 574 } FNV32context; 576 /* 577 * Function Prototypes 578 * FNV32string: hash a zero terminated string not including 579 * the terminating zero 580 * FNV32block: hash a specified length byte vector 581 * FNV32init: initializes an FNV32 context 582 * FNV32initBasis: initializes an FNV32 context with a 583 * provided basis 584 * FNV32blockin: hash in a specified length byte vector 585 * FNV32stringin: hash in a zero terminated string not 586 * including the zero 587 * FNV32result: returns the hash value 588 * 589 * Hash is returned as a 32-bit integer 590 */ 592 /* FNV32 */ 593 extern int FNV32string ( const char *in, 594 uint32_t * const out ); 595 extern int FNV32block ( const uint8_t *in, 596 long int inlength, 597 uint32_t * const out ); 598 extern int FNV32init ( FNV32context * const ); 599 extern int FNV32initBasis ( FNV32context * const, 600 uint32_t basis ); 601 extern int FNV32blockin ( FNV32context * const, 602 const uint8_t *in, 603 long int inlength ); 604 extern int FNV32stringin ( FNV32context * const, 605 const char *in ); 606 extern int FNV32result ( FNV32context * const, 607 uint32_t * const out ); 609 #endif /* _FNV32_H_ */ 610 612 613 /**************************** FNV32.c ****************************/ 614 /****************** See RFC NNNN for details. ********************/ 615 /* Copyright (c) 2015 IETF Trust and the persons identified as 616 * authors of the code. All rights reserved. 617 * See fnv-private.h for terms of use and redistribution. 618 */ 620 /* This code implements the FNV (Fowler, Noll, Vo) non-cryptographic 621 * hash function FNV-1a for 32-bit hashes. 622 */ 624 #ifndef _FNV32_C_ 625 #define _FNV32_C_ 627 #include "fnv-private.h" 628 #include "FNV32.h" 629 #define FNV32prime 0x01000193 630 #define FNV32basis 0x811C9DC5 632 #ifdef FNV_BigEndian 633 /* Local prototype */ 634 void FNV32reverse ( uint32_t const *out, uint32_t hash ); 635 #endif 637 /* FNV32 hash a zero terminated string not including the zero 638 *********************************************************************/ 639 int FNV32string ( const char *in, uint32_t * const out ) 640 { 641 uint32_t temp; 642 uint8_t ch; 644 if ( in && out ) 645 { 646 temp = FNV32basis; 647 while ( (ch = *in++) ) 648 temp = FNV32prime * ( temp ^ ch ); 649 #ifdef FNV_BigEndian 650 FNV32reverse ( out, temp ); 651 #else 652 *out = temp; 653 #endif 654 return fnvSuccess; 655 } 656 return fnvNull; /* Null input pointer */ 657 } /* end FNV32string */ 659 /* FNV32 hash a counted block 660 ***************************************************************/ 661 int FNV32block ( const uint8_t *in, 662 long int length, 663 uint32_t * const out ) 664 { 665 uint32_t temp; 667 if ( in && out ) 668 { 669 if ( length < 0 ) 670 return fnvBadParam; 671 for ( temp = FNV32basis; length > 0; length-- ) 672 temp = FNV32prime * ( temp ^ *in++ ); 673 #ifdef FNV_BigEndian 674 FNV32reverse ( out, temp ); 675 #else 676 *out = temp; 677 #endif 678 return fnvSuccess; 679 } 680 return fnvNull; /* Null input pointer */ 681 } /* end FNV32block */ 683 #ifdef FNV_BigEndian 685 /* Store a Big Endian result back as Little Endian 686 ***************************************************************/ 687 static void FNV32reverse ( uint32_t const *out, uint32_t hash ) 688 { 689 uint32_t temp; 691 temp = hash & 0xFF; 692 hash >>= 8; 693 temp = ( temp << 8 ) + ( hash & 0xFF ); 694 hash >>= 8; 695 temp = ( temp << 8 ) + ( hash & 0xFF ); 696 hash >>= 8; 697 *out = ( temp << 8 ) + ( hash & 0xFF ); 698 } /* end FNV32reverse */ 700 #endif /* FNV_BigEndian */ 702 /*************************************************************** 703 * Set of init, input, and output functions below * 704 * to incrementally compute FNV32 * 705 ***************************************************************/ 707 /* initialize context 708 ***************************************************************/ 709 int FNV32init ( FNV32context * const ctx ) 710 { 711 return FNV32initBasis ( ctx, FNV32basis ); 712 } /* end FNV32init */ 714 /* initialize context with a provided basis 715 ***************************************************************/ 716 int FNV32initBasis ( FNV32context * const ctx, uint32_t basis ) 717 { 718 if ( ctx ) 719 { 720 ctx->Hash = basis; 721 ctx->Computed = FNVinited+FNV32state; 722 return fnvSuccess; 723 } 724 return fnvNull; 725 } /* end FNV32initBasis */ 727 /* hash in a counted block 728 ***************************************************************/ 729 int FNV32blockin ( FNV32context * const ctx, 730 const uint8_t *in, 731 long int length ) 732 { 733 uint32_t temp; 735 if ( ctx && in ) 736 { 737 if ( length < 0 ) 738 return fnvBadParam; 739 switch ( ctx->Computed ) 740 { 741 case FNVinited+FNV32state: 742 ctx->Computed = FNVcomputed+FNV32state; 743 case FNVcomputed+FNV32state: 744 break; 745 default: 746 return fnvStateError; 747 } 748 for ( temp = ctx->Hash; length > 0; length-- ) 749 temp = FNV32prime * ( temp ^ *in++ ); 750 ctx->Hash = temp; 751 return fnvSuccess; 752 } 753 return fnvNull; 754 } /* end FNV32blockin */ 756 /* hash in a zero terminated string not including the zero 757 ***************************************************************/ 758 int FNV32stringin ( FNV32context * const ctx, 759 const char *in ) 760 { 761 uint32_t temp; 762 uint8_t ch; 764 if ( ctx && in ) 765 { 766 switch ( ctx->Computed ) 767 { 768 case FNVinited+FNV32state: 769 ctx->Computed = FNVcomputed+FNV32state; 770 case FNVcomputed+FNV32state: 771 break; 772 default: 773 return fnvStateError; 774 } 775 temp = ctx->Hash; 776 while ( (ch = (uint8_t)*in++) ) 777 temp = FNV32prime * ( temp ^ ch ); 779 ctx->Hash = temp; 780 return fnvSuccess; 781 } 782 return fnvNull; 783 } /* end FNV32stringin */ 785 /* return hash 786 ***************************************************************/ 787 int FNV32result ( FNV32context * const ctx, 788 uint32_t * const out ) 789 { 790 if ( ctx && out ) 791 { 792 if ( ctx->Computed != FNVcomputed+FNV32state ) 793 return fnvStateError; 794 ctx->Computed = FNVemptied+FNV32state; 795 #ifdef FNV_BigEndian 796 FNV32reverse ( out, ctx->Hash ); 797 #else 798 *out = ctx->Hash; 799 #endif 800 ctx->Hash = 0; 801 return fnvSuccess; 802 } 803 return fnvNull; 804 } /* end FNV32result */ 806 #endif /* _FNV32_C_ */ 807 809 6.1.2 FNV64 C Code 811 The header and C source for 64-bit FNV-1a. 813 814 /***************************** FNV64.h ******************************/ 815 /******************* See RFC NNNN for details. **********************/ 816 /* 817 * Copyright (c) 2015 IETF Trust and the persons identified as 818 * authors of the code. All rights reserved. 819 * See fnv-private.h for terms of use and redistribution. 820 */ 822 #ifndef _FNV64_H_ 823 #define _FNV64_H_ 825 /* 826 * Description: 828 * This file provides headers for the 64-bit version of the FNV-1a 829 * non-cryptographic hash algorithm. 830 * 831 * >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */ 833 #define FNV_64bitIntegers 835 /* FNV_64bitIntegers - Define this if your system supports 64-bit 836 * arithmetic including 32-bit x 32-bit multiplication 837 * producing a 64-bit product. If undefined, it will be 838 * assumed that 32-bit arithmetic is supported including 839 * 16-bit x 16-bit multiplication producing a 32-bit result. 840 * 841 * FNV_BigEndian - Define this ONLY if your system uses big 842 * endian representation AND your FNV hashes need to 843 * interoperate with little endian systems. If you #define 844 * this symbol when not needed, it will unnecessarily slow 845 * down and increase the code size of the FNV functions. 846 */ 848 #include 849 #define FNV64size (64/8) 851 /* If you do not have the ISO standard stdint.h header file, then you 852 * must typedef the following types: 853 * 854 * type meaning 855 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 856 * uint32_t unsigned 32 bit integer 857 * uint16_t unsigned 16 bit integer 858 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 859 */ 861 #ifndef _FNV_ErrCodes_ 862 #define _FNV_ErrCodes_ 863 /********************************************************************* 864 * All FNV functions provided return as integer as follows: 865 * 0 -> success 866 * >0 -> error as listed below 867 */ 868 enum { /* success and errors */ 869 fnvSuccess = 0, 870 fnvNull, /* Null pointer parameter */ 871 fnvStateError, /* called Input after Result, etc. */ 872 fnvBadParam /* passed a bad parameter */ 873 }; 874 #endif /* _FNV_ErrCodes_ */ 876 /* 877 * This structure holds context information for an FNV64 hash 878 */ 879 #ifdef FNV_64bitIntegers 880 /* version if 64 bit integers supported */ 882 typedef struct FNV64context_s { 883 int Computed; /* state */ 884 uint64_t Hash; 885 } FNV64context; 887 #else 888 /* version if 64 bit integers NOT supported */ 890 typedef struct FNV64context_s { 891 int Computed; /* state */ 892 uint16_t Hash[FNV64size/2]; 893 } FNV64context; 895 #endif /* FNV_64bitIntegers */ 897 /* 898 * Function Prototypes 899 * FNV64string: hash a zero terminated string not including 900 * the terminating zero 901 * FNV64block: FNV64 hash a specified length byte vector 902 * FNV64init: initializes an FNV64 context 903 * FNV64initBasis: initializes an FNV64 context with a 904 * provided basis 905 * FNV64blockin: hash in a specified length byte vector 906 * FNV64stringin: hash in a zero terminated string not 907 * incluing the zero 908 * FNV64result: returns the hash value 909 * 910 * Hash is returned as a 64-bit integer if supported, otherwise 911 * as a vector of 8-bit integers 912 */ 914 /* FNV64 */ 915 extern int FNV64init ( FNV64context * const ); 916 extern int FNV64blockin ( FNV64context * const, 917 const uint8_t * in, 918 long int length ); 919 extern int FNV64stringin ( FNV64context * const, 920 const char * in ); 922 #ifdef FNV_64bitIntegers 923 extern int FNV64string ( const char *in, 924 uint64_t * const out ); 925 extern int FNV64block ( const uint8_t *in, 926 long int length, 927 uint64_t * const out ); 929 extern int FNV64initBasis ( FNV64context * const, 930 uint64_t basis ); 931 extern int FNV64result ( FNV64context * const, 932 uint64_t * const out ); 933 #else 934 extern int FNV64string ( const char *in, 935 uint8_t out[FNV64size] ); 936 extern int FNV64block ( const unsigned char *in, 937 long int length, 938 uint8_t out[FNV64size] ); 939 extern int FNV32initBasis ( FNV64context * const, 940 const uint8_t basis[FNV64size] ); 941 extern int FNV64result ( FNV64context * const, 942 uint8_t out[FNV64size] ); 943 #endif /* FNV_64bitIntegers */ 945 #endif /* _FNV64_H_ */ 946 948 949 /***************************** FNV64.c ******************************/ 950 /******************** See RFC NNNN for details **********************/ 951 /* Copyright (c) 2015 IETF Trust and the persons identified as 952 * authors of the code. All rights reserved. 953 * See fnv-private.h for terms of use and redistribution. 954 */ 956 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 957 * hash function FNV-1a for 64-bit hashes. 958 */ 960 #ifndef _FNV64_C_ 961 #define _FNV64_C_ 963 #include "fnv-private.h" 964 #include "FNV64.h" 966 /******************************************************************** 967 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 968 ********************************************************************/ 969 #ifdef FNV_64bitIntegers 971 #ifdef FNV_BigEndian 972 /* Local prototype */ 973 void FNV64reverse ( uint64_t * const out, uint64_t hash ); 974 #endif /* FNV_BigEndian */ 976 #define FNV64prime 0x00000100000001B3 977 #define FNV64basis 0xCBF29CE484222325 978 /* FNV64 hash a null terminated string (64 bit) 979 ********************************************************************/ 980 int FNV64string ( const char *in, uint64_t * const out ) 981 { 982 uint64_t temp; 983 uint8_t ch; 985 if ( in && out ) 986 { 987 temp = FNV64basis; 988 while ( (ch = *in++) ) 989 temp = FNV64prime * ( temp ^ ch ); 990 #ifdef FNV_BigEndian 991 FNV64reverse ( out, temp ); 992 #else 993 *out = temp; 994 #endif 995 return fnvSuccess; 996 } 997 return fnvNull; /* Null input pointer */ 998 } /* end FNV64string */ 1000 /* FNV64 hash a counted block (64 bit) 1001 ********************************************************************/ 1002 int FNV64block ( const uint8_t *in, 1003 long int length, 1004 uint64_t * const out ) 1005 { 1006 uint64_t temp; 1008 if ( in && out ) 1009 { 1010 if ( length < 0 ) 1011 return fnvBadParam; 1012 for ( temp = FNV64basis; length > 0; length-- ) 1013 temp = FNV64prime * ( temp ^ *in++ ); 1014 #ifdef FNV_BigEndian 1015 FNV64reverse ( out, temp ); 1016 #else 1017 *out = temp; 1018 #endif 1019 return fnvSuccess; 1020 } 1021 return fnvNull; /* Null input pointer */ 1022 } /* end FNV64block */ 1024 #ifdef FNV_BigEndian 1026 /* Store a Big Endian result back as Little Endian 1027 ***************************************************************/ 1029 static void FNV64reverse ( uint64_t const *out, uint64_t hash ) 1030 { 1031 uint64_t temp; 1032 int i; 1034 temp = hash & 0xFF; 1035 for ( i = FNV64size - 1; i > 0; i-- ) 1036 { 1037 hash >>= 8; 1038 temp = ( temp << 8 ) + ( hash & 0xFF ); 1039 } 1040 *out = temp; 1041 } /* end FNV64reverse */ 1043 #endif /* FNV_BigEndian */ 1045 /******************************************************************** 1046 * Set of init, input, and output functions below * 1047 * to incrementally compute FNV64 * 1048 ********************************************************************/ 1050 /* initialize context (64 bit) 1051 ********************************************************************/ 1052 int FNV64init ( FNV64context * const ctx ) 1053 { 1054 return FNV64initBasis ( ctx, FNV64basis ); 1055 } /* end FNV64init */ 1057 /* initialize context with a provided basis (64 bit) 1058 ********************************************************************/ 1059 int FNV64initBasis ( FNV64context * const ctx, uint64_t basis ) 1060 { 1061 if ( ctx ) 1062 { 1063 ctx->Hash = basis; 1064 ctx->Computed = FNVinited+FNV64state; 1065 return fnvSuccess; 1066 } 1067 return fnvNull; 1068 } /* end FNV64initBasis */ 1070 /* hash in a counted block (64 bit) 1071 ********************************************************************/ 1072 int FNV64blockin ( FNV64context * const ctx, 1073 const uint8_t *in, 1074 long int length ) 1075 { 1076 uint64_t temp; 1077 if ( ctx && in ) 1078 { 1079 if ( length < 0 ) 1080 return fnvBadParam; 1081 switch ( ctx->Computed ) 1082 { 1083 case FNVinited+FNV64state: 1084 ctx->Computed = FNVcomputed+FNV64state; 1085 case FNVcomputed+FNV64state: 1086 break; 1087 default: 1088 return fnvStateError; 1089 } 1090 for ( temp = ctx->Hash; length > 0; length-- ) 1091 temp = FNV64prime * ( temp ^ *in++ ); 1092 ctx->Hash = temp; 1093 return fnvSuccess; 1094 } 1095 return fnvNull; 1096 } /* end FNV64input */ 1098 /* hash in a zero terminated string not including the zero (64 bit) 1099 ********************************************************************/ 1100 int FNV64stringin ( FNV64context * const ctx, 1101 const char *in ) 1102 { 1103 uint64_t temp; 1104 uint8_t ch; 1106 if ( ctx && in ) 1107 { 1108 switch ( ctx->Computed ) 1109 { 1110 case FNVinited+FNV64state: 1111 ctx->Computed = FNVcomputed+FNV64state; 1112 case FNVcomputed+FNV64state: 1113 break; 1114 default: 1115 return fnvStateError; 1116 } 1117 temp = ctx->Hash; 1118 while ( (ch = *in++) ) 1119 temp = FNV64prime * ( temp ^ ch ); 1120 ctx->Hash = temp; 1121 return fnvSuccess; 1122 } 1123 return fnvNull; 1124 } /* end FNV64stringin */ 1126 /* return hash (64 bit) 1127 ********************************************************************/ 1128 int FNV64result ( FNV64context * const ctx, 1129 uint64_t * const out ) 1130 { 1131 if ( ctx && out ) 1132 { 1133 if ( ctx->Computed != FNVcomputed+FNV64state ) 1134 return fnvStateError; 1135 ctx->Computed = FNVemptied+FNV64state; 1136 #ifdef FNV_BigEndian 1137 FNV64reverse ( out, ctx->Hash ); 1138 #else 1139 *out = ctx->Hash; 1140 #endif 1141 ctx->Hash = 0; 1142 return fnvSuccess; 1143 } 1144 return fnvNull; 1145 } /* end FNV64result */ 1147 /****************************************************************** 1148 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1149 ******************************************************************/ 1150 #else /* FNV_64bitIntegers */ 1151 /****************************************************************** 1152 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1153 ******************************************************************/ 1155 /* #define FNV64prime 0x00000100000001B3 */ 1156 #define FNV64primeX 0x01B3 1157 #define FNV64shift 8 1159 /* #define FNV64basis 0xCBF29CE484222325 */ 1160 #define FNV64basis0 0xCBF2 1161 #define FNV64basis1 0x9CE4 1162 #define FNV64basis2 0x8422 1163 #define FN64Vbasis3 0x2325 1165 /* FNV64 hash a null terminated string (32 bit) 1166 ********************************************************************/ 1167 int FNV64string ( const char *in, uint8_t out[FNV64size] ) 1168 { 1169 FNV64context ctx; 1170 int err; 1172 if (err = FNV64init (&ctx)) 1173 return err; 1174 if (err = FNV64stringin (&ctx, in)) 1175 return err; 1176 return FNV64result (&ctx, out); 1177 } /* end FNV64string */ 1179 /* FNV64 hash a counted block (32 bit) 1180 ********************************************************************/ 1181 int FNV64block ( const char *in, 1182 long int length, 1183 uint8_t out[FNV64size] ) 1184 { 1185 FNV64context ctx; 1186 int err; 1188 if (err = FNV64init (&ctx)) 1189 return err; 1190 if (err = FNV64blockin (&ctx, in, length)) 1191 return err; 1192 return FNV64result (&ctx, out)); 1193 } /* end FNV64block */ 1195 /******************************************************************** 1196 * Set of init, input, and output functions below * 1197 * to incrementally compute FNV64 * 1198 ********************************************************************/ 1200 /* initialize context (32 bit) 1201 ********************************************************************/ 1202 int FNV64init ( FNV64context * const ctx ) 1203 { 1204 if ( ctx ) 1205 { 1206 ctx->Hash[0] = FNV64basis0; 1207 ctx->Hash[1] = FNV64basis1; 1208 ctx->Hash[2] = FNV64basis2; 1209 ctx->Hash[3] = FNV64basis3; 1210 ctx->Computed = FNVinited+FNV64state; 1211 return fnvSuccess; 1212 } 1213 return fnvNull; 1214 } /* end FNV64init */ 1216 /* initialize context (32 bit) 1217 ********************************************************************/ 1218 int FNV64initBasis ( FNV64context * const ctx, 1219 const uint8_t basis[FNV64size] ) 1220 { 1221 if ( ctx ) 1222 { 1223 #ifdef FNV_BigEndian 1224 ctx->Hash[0] = basis[1] + basis[0]<<8; 1225 ctx->Hash[1] = basis[3] + basis[2]<<8; 1226 ctx->Hash[2] = basis[5] + basis[4]<<8; 1227 ctx->Hash[3] = basis[7] + basis[6]<<8; 1228 #else 1229 ctx->Hash[0] = basis[0] + basis[1]<<8; 1230 ctx->Hash[1] = basis[2] + basis[3]<<8; 1231 ctx->Hash[2] = basis[4] + basis[5]<<8; 1232 ctx->Hash[3] = basis[6] + basis[7]<<8; 1233 #endif 1234 ctx->Computed = FNVinited+FNV64state; 1235 return fnvSuccess; 1236 } 1237 return fnvNull; 1238 } /* end FNV64initBasis */ 1240 /* hash in a counted block (32 bit) 1241 ********************************************************************/ 1242 int FNV64blockin ( FNV64context * const ctx, 1243 const unsigned char *in, 1244 long int length ) 1245 { 1246 uint32_t temp[FNV64size/2]; 1247 uint32_t temp2[2]; 1248 int i; 1250 if ( ctx && in ) 1251 { 1252 if ( length < 0 ) 1253 return fnvBadParam; 1254 switch ( ctx->Computed ) 1255 { 1256 case FNVinited+FNV64state: 1257 ctx->Computed = FNVcomputed+FNV64state; 1258 case FNVcomputed+FNV64state: 1259 break; 1260 default: 1261 return fnvStateError; 1262 } 1263 for ( i=0; iHash[i]; 1265 for ( ; length > 0; length-- ) 1266 { 1267 /* temp = FNV64prime * ( temp ^ *in++ ); */ 1268 temp2[1] = temp[3] << FNV64shift; 1269 temp2[0] = temp[2] << FNV64shift; 1270 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 1271 temp[2] *= FNV64primeX; 1272 temp[1] = temp[1] * FNV64primeX + temp2[1]; 1273 temp[0] = temp[0] * FNV64primeX + temp2[0]; 1274 temp[2] += temp[3] >> 16; 1275 temp[3] &= 0xFFFF; 1276 temp[1] += temp[2] >> 16; 1277 temp[2] &= 0xFFFF; 1278 temp[0] += temp[1] >> 16; 1279 temp[1] &= 0xFFFF; 1280 } 1281 for ( i=0; iHash[i] = temp[i]; 1283 return fnvSuccess; 1284 } 1285 return fnvNull; 1286 } /* end FNV64blockin */ 1288 /* hash in a string (32 bit) 1289 ********************************************************************/ 1290 int FNV64stringin ( FNV64context * const ctx, 1291 const char *in ) 1292 { 1293 uint32_t temp[FNV64size/2]; 1294 uint32_t temp2[2]; 1295 int i; 1296 uint8_t ch; 1298 if ( ctx && in ) 1299 { 1300 switch ( ctx->Computed ) 1301 { 1302 case FNVinited+FNV64state: 1303 ctx->Computed = FNVcomputed+FNV64state; 1304 case FNVcomputed+FNV64state: 1305 break; 1306 default: 1307 return fnvStateError; 1308 } 1309 for ( i=0; iHash[i]; 1311 while ( ch = (uint8_t)*in++ ) 1312 { 1313 /* temp = FNV64prime * ( temp ^ ch ); */ 1314 temp2[1] = temp[3] << FNV64shift; 1315 temp2[0] = temp[2] << FNV64shift; 1316 temp[3] = FNV64primeX * ( temp[3] ^ *in++ ); 1317 temp[2] *= FNV64primeX; 1318 temp[1] = temp[1] * FNV64primeX + temp2[1]; 1319 temp[0] = temp[0] * FNV64primeX + temp2[0]; 1320 temp[2] += temp[3] >> 16; 1321 temp[3] &= 0xFFFF; 1322 temp[1] += temp[2] >> 16; 1323 temp[2] &= 0xFFFF; 1324 temp[0] += temp[1] >> 16; 1325 temp[1] &= 0xFFFF; 1326 } 1327 for ( i=0; iHash[i] = temp[i]; 1329 return fnvSuccess; 1330 } 1331 return fnvNull; 1332 } /* end FNV64stringin */ 1334 /* return hash (32 bit) 1335 ********************************************************************/ 1336 int FNV64result ( FNV64context * const ctx, 1337 uint8_t out[FNV64size] ) 1338 { 1339 int i; 1341 if ( ctx && out ) 1342 { 1343 if ( ctx->Computed != FNVcomputed+FNV64state ) 1344 return fnvStateError; 1345 for ( i=0; iHash[i]; 1349 out[6-2*i] = ctx->Hash[i] >> 8; 1350 #else 1351 out[2*i] = ctx->Hash[i]; 1352 out[2*i+1] = ctx->Hash[i] >> 8; 1353 #endif 1354 ctx -> Hash[i] = 0; 1355 } 1356 ctx->Computed = FNVemptied+FNV64state; 1357 return fnvSuccess; 1358 } 1359 return fnvNull; 1360 } /* end FNV64result */ 1362 #endif /* FNV_64bitIntegers */ 1363 /******************************************************************** 1364 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1365 ********************************************************************/ 1367 #endif /* _FNV64_C_ */ 1368 1370 6.1.3 FNV128 C Code 1372 The header and C source for 128-bit FNV-1a. 1374 1375 /**************************** FNV128.h **************************/ 1376 /***************** See RFC NNNN for details. ********************/ 1377 /* 1378 * Copyright (c) 2015 IETF Trust and the persons identified as 1379 * authors of the code. All rights reserved. 1380 * See fnv-private.h for terms of use and redistribution. 1381 */ 1383 #ifndef _FNV128_H_ 1384 #define _FNV128_H_ 1386 /* 1387 * Description: 1388 * This file provides headers for the 128-bit version of the 1389 * FNV-1a non-cryptographic hash algorithm. 1390 * 1391 * >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */ 1393 #define FNV_64bitIntegers 1395 /* FNV_64bitIntegers - Define this if your system supports 64-bit 1396 * arithmetic including 32-bit x 32-bit multiplication 1397 * producing a 64-bit product. If undefined, it will be 1398 * assumed that 32-bit arithmetic is supported including 1399 * 16-bit x 16-bit multiplication producing a 32-bit result. 1400 * 1401 * FNV_BigEndian - Define this ONLY if your system uses big 1402 * endian representation AND your FNV hashes need to 1403 * interoperate with little endian systems. If you #define 1404 * this symbol when not needed, it will unnecessarily slow 1405 * down and increase the code size of the FNV functions. 1406 */ 1408 #include 1409 #define FNV128size (128/8) 1411 /* If you do not have the ISO standard stdint.h header file, then you 1412 * must typedef the following types: 1413 * 1414 * type meaning 1415 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 1416 * uint32_t unsigned 32 bit integer 1417 * uint16_t unsigned 16 bit integer 1418 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 1419 */ 1421 #ifndef _FNV_ErrCodes_ 1422 #define _FNV_ErrCodes_ 1423 /********************************************************************* 1424 * All FNV functions provided return as integer as follows: 1425 * 0 -> success 1426 * >0 -> error as listed below 1427 */ 1428 enum { /* success and errors */ 1429 fnvSuccess = 0, 1430 fnvNull, /* Null pointer parameter */ 1431 fnvStateError, /* called Input after Result or before Init */ 1432 fnvBadParam /* passed a bad parameter */ 1433 }; 1434 #endif /* _FNV_ErrCodes_ */ 1436 /* 1437 * This structure holds context information for an FNV128 hash 1438 */ 1439 #ifdef FNV_64bitIntegers 1440 /* version if 64 bit integers supported */ 1441 typedef struct FNV128context_s { 1442 int Computed; /* state */ 1443 uint32_t Hash[FNV128size/4]; 1444 } FNV128context; 1446 #else 1447 /* version if 64 bit integers NOT supported */ 1449 typedef struct FNV128context_s { 1450 int Computed; /* state */ 1451 uint16_t Hash[FNV128size/2]; 1452 } FNV128context; 1454 #endif /* FNV_64bitIntegers */ 1456 /* 1457 * Function Prototypes 1458 * FNV128string: hash a zero terminated string not including 1459 * the terminating zero 1460 * FNV128block: FNV128 hash a specified length byte vector 1461 * FNV128init: initializes an FNV128 context 1462 * FNV128initBasis: initializes an FNV128 context with a 1463 * provided basis 1464 * FNV128blockin: hash in a specified length byte vector 1465 * FNV128stringin: hash in a zero terminated string not 1466 * including the zero 1467 * FNV128result: returns the hash value 1468 * 1469 * Hash is returned as an array of 8-bit integers 1470 */ 1472 /* FNV128 */ 1473 extern int FNV128string ( const char *in, 1474 uint8_t out[FNV128size] ); 1475 extern int FNV128block ( const unsigned char *in, 1476 long int length, 1477 uint8_t out[FNV128size] ); 1478 extern int FNV128init ( FNV128context * const ); 1479 extern int FNV128initBasis ( FNV128context * const, 1480 const uint8_t basis[FNV128size] ); 1481 extern int FNV128blockin ( FNV128context * const, 1482 const unsigned char *in, 1483 long int length ); 1484 extern int FNV128stringin ( FNV128context * const, 1485 const char *in ); 1486 extern int FNV128result ( FNV128context * const, 1487 uint8_t out[FNV128size] ); 1489 #endif /* _FNV128_H_ */ 1490 1492 1493 /***************************** FNV128.c ****************************/ 1494 /******************** See RFC NNNN for details *********************/ 1495 /* Copyright (c) 2015 IETF Trust and the persons identified as 1496 * authors of the code. All rights 1497 * See fnv-private.h for terms of use and redistribution. 1498 */ 1500 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 1501 * hash function FNV-1a for 128-bit hashes. 1502 */ 1504 #ifndef _FNV128_C_ 1505 #define _FNV128_C_ 1507 #include "fnv-private.h" 1508 #include "FNV128.h" 1510 /* common code for 64 and 32 bit modes */ 1512 /* FNV128 hash a null terminated string (64/32 bit) 1513 ********************************************************************/ 1514 int FNV128string ( const char *in, uint8_t out[FNV128size] ) 1515 { 1516 FNV128context ctx; 1517 int err; 1519 err = FNV128init ( &ctx ); 1520 if ( err ) return err; 1521 err = FNV128stringin ( &ctx, in ); 1522 if ( err ) return err; 1523 return FNV128result (&ctx, out); 1524 } /* end FNV128string */ 1526 /* FNV128 hash a counted block (64/32 bit) 1527 ********************************************************************/ 1528 int FNV128block ( const unsigned char *in, 1529 long int length, 1530 uint8_t out[FNV128size] ) 1531 { 1532 FNV128context ctx; 1533 int err; 1535 err = FNV128init ( &ctx ); 1536 if ( err ) return err; 1537 err = FNV128blockin ( &ctx, in, length ); 1538 if ( err ) return err; 1539 return FNV128result ( &ctx, out ); 1540 } /* end FNV128block */ 1542 /******************************************************************** 1543 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1544 ********************************************************************/ 1545 #ifdef FNV_64bitIntegers 1547 /* 0x00000000 01000000 00000000 0000013B */ 1548 #define FNV128primeX 0x013B 1549 #define FNV128shift 24 1551 /* 0x6C62272E 07BB0142 62B82175 6295C58D */ 1552 #define FNV128basis0 0x6C62272E 1553 #define FNV128basis1 0x07BB0142 1554 #define FNV128basis2 0x62B82175 1555 #define FNV128basis3 0x6295C58D 1557 /******************************************************************** 1558 * Set of init, input, and output functions below * 1559 * to incrementally compute FNV128 * 1560 ********************************************************************/ 1562 /* initialize context (64 bit) 1563 ********************************************************************/ 1564 int FNV128init ( FNV128context * const ctx ) 1565 { 1566 if ( ctx ) 1567 { 1568 ctx->Hash[0] = FNV128basis0; 1569 ctx->Hash[1] = FNV128basis1; 1570 ctx->Hash[2] = FNV128basis2; 1571 ctx->Hash[3] = FNV128basis3; 1572 ctx->Computed = FNVinited+FNV128state; 1573 return fnvSuccess; 1574 } 1575 return fnvNull; 1576 } /* end FNV128init */ 1578 /* initialize context with a provided basis (64 bit) 1579 ********************************************************************/ 1580 int FNV128initBasis ( FNV128context * const ctx, 1581 const uint8_t basis[FNV128size] ) 1582 { 1583 int i; 1584 uint8_t *ui8p; 1585 uint32_t temp; 1587 if ( ctx ) 1588 { 1589 #ifdef FNV_BigEndian 1590 ui8p = basis; 1591 for ( i=0; i < FNV128size/4; ++i ) 1592 { 1593 temp = (*ui8p++)<<8; 1594 temp = (temp + *ui8p++)<<8; 1595 temp = (temp + *ui8p++)<<8; 1596 ctx->Hash[i] = temp + *ui8p; 1597 } 1598 #else 1599 ui8p = basis + ( FNV128size/4 - 1 ); 1600 for ( i=0; i < FNV128size/4; ++i ) 1601 { 1602 temp = (*ui8p--)<<8; 1603 temp = (temp + *ui8p--)<<8; 1604 temp = (temp + *ui8p--)<<8; 1605 ctx->Hash[i] = temp + *ui8p; 1606 } 1607 #endif 1608 ctx->Computed = FNVinited+FNV128state; 1609 return fnvSuccess; 1610 } 1611 return fnvNull; 1612 } /* end FNV128initBasis */ 1614 /* hash in a counted block (64 bit) 1615 ********************************************************************/ 1616 int FNV128blockin ( FNV128context * const ctx, 1617 const unsigned char *in, 1618 long int length ) 1619 { 1620 uint64_t temp[FNV128size/4]; 1621 uint64_t temp2[2]; 1622 int i; 1623 if ( ctx && in ) 1624 { 1625 if ( length < 0 ) 1626 return fnvBadParam; 1627 switch ( ctx->Computed ) 1628 { 1629 case FNVinited+FNV128state: 1630 ctx->Computed = FNVcomputed+FNV128state; 1631 case FNVcomputed+FNV128state: 1632 break; 1633 default: 1634 return fnvStateError; 1635 } 1636 for ( i=0; iHash[i]; 1638 for ( ; length > 0; length-- ) 1639 { 1640 /* temp = FNV128prime * ( temp ^ *in++ ); */ 1641 temp2[1] = temp[3] << FNV128shift; 1642 temp2[0] = temp[2] << FNV128shift; 1643 temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); 1644 temp[2] *= FNV128primeX; 1645 temp[1] = temp[1] * FNV128primeX + temp2[1]; 1646 temp[0] = temp[0] * FNV128primeX + temp2[0]; 1647 temp[2] += temp[3] >> 32; 1648 temp[3] &= 0xFFFFFFFF; 1649 temp[1] += temp[2] >> 32; 1650 temp[2] &= 0xFFFFFFFF; 1651 temp[0] += temp[1] >> 32; 1652 temp[1] &= 0xFFFFFFFF; 1653 } 1654 for ( i=0; iHash[i] = temp[i]; 1656 return fnvSuccess; 1657 } 1658 return fnvNull; 1659 } /* end FNV128input */ 1661 /* hash in a string (64 bit) 1662 ********************************************************************/ 1663 int FNV128stringin ( FNV128context * const ctx, const char *in ) 1664 { 1665 uint64_t temp[FNV128size/4]; 1666 uint64_t temp2[2]; 1667 int i; 1668 uint8_t ch; 1670 if ( ctx && in ) 1671 { 1672 switch ( ctx->Computed ) 1673 { 1674 case FNVinited+FNV128state: 1675 ctx->Computed = FNVcomputed+FNV128state; 1676 case FNVcomputed+FNV128state: 1677 break; 1678 default: 1679 return fnvStateError; 1680 } 1681 for ( i=0; iHash[i]; 1683 while ( (ch = (uint8_t)*in++) ) 1684 { 1685 /* temp = FNV128prime * ( temp ^ ch ); */ 1686 temp2[1] = temp[3] << FNV128shift; 1687 temp2[0] = temp[2] << FNV128shift; 1688 temp[3] = FNV128primeX * ( temp[3] ^ *in++ ); 1689 temp[2] *= FNV128primeX; 1690 temp[1] = temp[1] * FNV128primeX + temp2[1]; 1691 temp[0] = temp[0] * FNV128primeX + temp2[0]; 1692 temp[2] += temp[3] >> 32; 1693 temp[3] &= 0xFFFFFFFF; 1694 temp[1] += temp[2] >> 32; 1695 temp[2] &= 0xFFFFFFFF; 1696 temp[0] += temp[1] >> 32; 1697 temp[1] &= 0xFFFFFFFF; 1698 } 1699 for ( i=0; iHash[i] = temp[i]; 1701 return fnvSuccess; 1702 } 1703 return fnvNull; 1704 } /* end FNV128stringin */ 1706 /* return hash (64 bit) 1707 ********************************************************************/ 1708 int FNV128result ( FNV128context * const ctx, uint8_t out[FNV128size] ) 1709 { 1710 int i; 1712 if ( ctx && out ) 1713 { 1714 if ( ctx->Computed != FNVcomputed+FNV128state ) 1715 return fnvStateError; 1716 for ( i=0; iHash[i]; 1720 out[14-4*i] = ctx->Hash[i] >> 8; 1721 out[13-4*i] = ctx->Hash[i] >> 16; 1722 out[12-4*i] = ctx->Hash[i] >> 24; 1724 #else 1725 out[4*i] = ctx->Hash[i]; 1726 out[4*i+1] = ctx->Hash[i] >> 8; 1727 out[4*i+2] = ctx->Hash[i] >> 16; 1728 out[4*i+3] = ctx->Hash[i] >> 24; 1729 #endif 1730 ctx -> Hash[i] = 0; 1731 } 1732 ctx->Computed = FNVemptied+FNV128state; 1733 return fnvSuccess; 1734 } 1735 return fnvNull; 1736 } /* end FNV128result */ 1738 /****************************************************************** 1739 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 1740 ******************************************************************/ 1741 #else /* FNV_64bitIntegers */ 1742 /****************************************************************** 1743 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1744 ******************************************************************/ 1746 /* 0x00000000 01000000 00000000 0000013B */ 1747 #define FNV128primeX 0x013B 1748 #define FNV128shift 8 1750 /* 0x6C62272E 07BB0142 62B82175 6295C58D */ 1751 uint16_t FNV128basis[FNV128size/2] = 1752 { 0x6C62, 0x272E, 0x07BB, 0x0142, 1753 0x62B8, 0x2175, 0x6295, 0xC58D }; 1755 /******************************************************************** 1756 * Set of init, input, and output functions below * 1757 * to incrementally compute FNV128 * 1758 ********************************************************************/ 1760 /* initialize context (32 bit) 1761 ********************************************************************/ 1762 int FNV128init ( FNV128context *ctx ) 1763 { 1764 int i; 1766 if ( ctx ) 1767 { 1768 for ( i=0; iHash[i] = FNV128basis[i]; 1770 ctx->Computed = FNVinited+FNV128state; 1771 return fnvSuccess; 1772 } 1773 return fnvNull; 1774 } /* end FNV128init */ 1776 /* initialize context with a provided basis (32 bit) 1777 ********************************************************************/ 1778 int FNV128initBasis ( FNV128context *ctx, 1779 const uint8_t basis[FNV128size] ) 1780 { 1781 int i; 1782 uint8_t *ui8p; 1783 uint32_t temp; 1785 if ( ctx ) 1786 { 1787 #ifdef FNV_BigEndian 1788 ui8p = basis; 1789 for ( i=0; i < FNV128size/2; ++i ) 1790 { 1791 temp = *ui8p++; 1792 ctx->Hash[i] = temp<<8 + (*ui8p++); 1793 } 1794 #else 1795 ui8p = basis + (FNV128size/2 - 1); 1796 for ( i=0; i < FNV128size/2; ++i ) 1797 { 1798 temp = *ui8p--; 1799 ctx->Hash[i] = (temp<<8) + (*ui8p--); 1800 } 1801 #endif 1802 ctx->Computed = FNVinited+FNV128state; 1803 return fnvSuccess; 1804 } 1805 return fnvNull; 1806 } /* end FNV128initBasis */ 1808 /* hash in a counted block (32 bit) 1809 *******************************************************************/ 1810 int FNV128blockin ( FNV128context *ctx, 1811 const unsigned char *in, 1812 long int length ) 1813 { 1814 uint32_t temp[FNV128size/2]; 1815 uint32_t temp2[3]; 1816 int i; 1818 if ( ctx && in ) 1819 { 1820 if ( length < 0 ) 1821 return fnvBadParam; 1822 switch ( ctx->Computed ) 1823 { 1824 case FNVinited+FNV128state: 1825 ctx->Computed = FNVcomputed+FNV128state; 1826 case FNVcomputed+FNV128state: 1827 break; 1828 default: 1829 return fnvStateError; 1830 } 1831 for ( i=0; iHash[i]; 1833 for ( ; length > 0; length-- ) 1834 { 1835 /* temp = FNV128prime * ( temp ^ *in++ ); */ 1836 temp[7] ^= *in++; 1837 temp2[2] = temp[7] << FNV128shift; 1838 temp2[1] = temp[6] << FNV128shift; 1839 temp2[0] = temp[5] << FNV128shift; 1840 for ( i=0; i<8; ++i ) 1841 temp[i] *= FNV128primeX; 1842 temp[2] += temp2[2]; 1843 temp[1] += temp2[1]; 1844 temp[0] += temp2[0]; 1845 for ( i=7; i>0; --i ) 1846 { 1847 temp[i-1] += temp[i] >> 16; 1848 temp[i] &= 0xFFFF; 1849 } 1850 } 1851 for ( i=0; iHash[i] = temp[i]; 1853 return fnvSuccess; 1854 } 1855 return fnvNull; 1856 } /* end FNV128blockin */ 1858 /* hash in a string (32 bit) 1859 *******************************************************************/ 1860 int FNV128stringin ( FNV128context *ctx, 1861 const char *in ) 1862 { 1863 uint32_t temp[FNV128size/2]; 1864 uint32_t temp2[3]; 1865 int i; 1866 uint8_t ch; 1868 if ( ctx && in ) 1869 { 1870 switch ( ctx->Computed ) 1871 { 1872 case FNVinited+FNV128state: 1873 ctx->Computed = FNVcomputed+FNV128state; 1875 case FNVcomputed+FNV128state: 1876 break; 1877 default: 1878 return fnvStateError; 1879 } 1880 for ( i=0; iHash[i]; 1882 while ( (ch = (uint8_t)*in++) ) 1883 { 1884 /* temp = FNV128prime * ( temp ^ *in++ ); */ 1885 temp[7] ^= ch; 1886 temp2[2] = temp[7] << FNV128shift; 1887 temp2[1] = temp[6] << FNV128shift; 1888 temp2[0] = temp[5] << FNV128shift; 1889 for ( i=0; i<8; ++i ) 1890 temp[i] *= FNV128primeX; 1891 temp[2] += temp2[2]; 1892 temp[1] += temp2[1]; 1893 temp[0] += temp2[0]; 1894 for ( i=7; i>0; --i ) 1895 { 1896 temp[i-1] += temp[i] >> 16; 1897 temp[i] &= 0xFFFF; 1898 } 1899 } 1900 for ( i=0; iHash[i] = temp[i]; 1902 return fnvSuccess; 1903 } 1904 return fnvNull; 1905 } /* end FNV128stringin */ 1907 /* return hash (32 bit) 1908 ********************************************************************/ 1909 int FNV128result ( FNV128context *ctx, 1910 uint8_t out[FNV128size] ) 1911 { 1912 int i; 1914 if ( ctx && out ) 1915 { 1916 if ( ctx->Computed != FNVcomputed+FNV128state ) 1917 return fnvStateError; 1918 for ( i=0; iHash[i]; 1922 out[14-2*i] = ctx->Hash[i] >> 8; 1923 #else 1924 out[2*i] = ctx->Hash[i]; 1925 out[2*i+1] = ctx->Hash[i] >> 8; 1926 #endif 1927 ctx -> Hash[i] = 0; 1928 } 1929 ctx->Computed = FNVemptied+FNV128state; 1930 return fnvSuccess; 1931 } 1932 return fnvNull; 1933 } /* end FNV128result */ 1935 #endif /* Have64bitIntegers */ 1936 /******************************************************************** 1937 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 1938 ********************************************************************/ 1940 #endif /* _FNV128_C_ */ 1941 1943 6.1.4 FNV256 C Code 1945 The header and C source for 256-bit FNV-1a. 1947 1948 /**************************** FNV256.h **************************/ 1949 /***************** See RFC NNNN for details. ********************/ 1950 /* 1951 * Copyright (c) 2015 IETF Trust and the persons identified as 1952 * authors of the code. All rights reserved. 1953 * See fnv-private.h for terms of use and redistribution. 1954 */ 1956 #ifndef _FNV256_H_ 1957 #define _FNV256_H_ 1959 /* 1960 * Description: 1961 * This file provides headers for the 256-bit version of the 1962 * FNV-1a non-cryptographic hash algorithm. 1963 * 1964 * >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */ 1966 #define FNV_64bitIntegers 1968 /* FNV_64bitIntegers - Define this if your system supports 64-bit 1969 * arithmetic including 32-bit x 32-bit multiplication 1970 * producing a 64-bit product. If undefined, it will be 1971 * assumed that 32-bit arithmetic is supported including 1972 * 16-bit x 16-bit multiplication producing a 32-bit result. 1974 * 1975 * FNV_BigEndian - Define this ONLY if your system uses big 1976 * endian representation AND your FNV hashes need to 1977 * interoperate with little endian systems. If you #define 1978 * this symbol when not needed, it will unnecessarily slow 1979 * down and increase the code size of the FNV functions. 1980 */ 1982 #include 1983 #define FNV256size (256/8) 1985 /* If you do not have the ISO standard stdint.h header file, then you 1986 * must typedef the following types: 1987 * 1988 * type meaning 1989 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 1990 * uint32_t unsigned 32 bit integer 1991 * uint16_t unsigned 16 bit integer 1992 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 1993 */ 1995 #ifndef _FNV_ErrCodes_ 1996 #define _FNV_ErrCodes_ 1997 /********************************************************************* 1998 * All FNV functions provided return as integer as follows: 1999 * 0 -> success 2000 * >0 -> error as listed below 2001 */ 2002 enum { /* success and errors */ 2003 fnvSuccess = 0, 2004 fnvNull, /* Null pointer parameter */ 2005 fnvStateError, /* called Input after Result or before Init */ 2006 fnvBadParam /* passed a bad parameter */ 2007 }; 2008 #endif /* _FNV_ErrCodes_ */ 2010 /* 2011 * This structure holds context information for an FNV256 hash 2012 */ 2013 #ifdef FNV_64bitIntegers 2014 /* version if 64 bit integers supported */ 2015 typedef struct FNV256context_s { 2016 int Computed; /* state */ 2017 uint32_t Hash[FNV256size/4]; 2018 } FNV256context; 2020 #else 2021 /* version if 64 bit integers NOT supported */ 2023 typedef struct FNV256context_s { 2024 int Computed; /* state */ 2025 uint16_t Hash[FNV256size/2]; 2026 } FNV256context; 2028 #endif /* FNV_64bitIntegers */ 2030 /* 2031 * Function Prototypes 2032 * FNV256string: hash a zero terminated string not including 2033 * the zero 2034 * FNV256block: FNV256 hash a specified length byte vector 2035 * FNV256init: initializes an FNV256 context 2036 * FNV256initBasis: initializes an FNV256 context with a provided 2037 * basis 2038 * FNV256blockin: hash in a specified length byte vector 2039 * FNV256stringin: hash in a zero terminated string not 2040 * including the zero 2041 * FNV256result: returns the hash value 2042 * 2043 * Hash is returned as an array of 8-bit integers 2044 */ 2046 /* FNV256 */ 2047 extern int FNV256string ( const char *in, 2048 uint8_t out[FNV256size] ); 2049 extern int FNV256block ( const unsigned char *in, 2050 long int length, 2051 uint8_t out[FNV256size] ); 2052 extern int FNV256init ( FNV256context *); 2053 extern int FNV256initBasis ( FNV256context * const, 2054 const uint8_t basis[FNV256size] ); 2055 extern int FNV256blockin ( FNV256context * const, 2056 const unsigned char *in, 2057 long int length ); 2058 extern int FNV256stringin ( FNV256context * const, 2059 const char *in ); 2060 extern int FNV256result ( FNV256context * const, 2061 uint8_t out[FNV256size] ); 2063 #endif /* _FNV256_H_ */ 2064 2066 2067 /***************************** FNV256.c ****************************/ 2068 /******************** See RFC NNNN for details *********************/ 2069 /* Copyright (c) 2015 IETF Trust and the persons identified as 2070 * authors of the code. All rights 2071 * See fnv-private.h for terms of use and redistribution. 2072 */ 2074 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 2075 * hash function FNV-1a for 256-bit hashes. 2076 */ 2078 #ifndef _FNV256_C_ 2079 #define _FNV256_C_ 2081 #include "fnv-private.h" 2082 #include "FNV256.h" 2084 /* common code for 64 and 32 bit modes */ 2086 /* FNV256 hash a null terminated string (64/32 bit) 2087 ********************************************************************/ 2088 int FNV256string ( const char *in, uint8_t out[FNV256size] ) 2089 { 2090 FNV256context ctx; 2091 int err; 2093 if ( (err = FNV256init ( &ctx )) ) 2094 return err; 2095 if ( (err = FNV256stringin ( &ctx, in )) ) 2096 return err; 2097 return FNV256result ( &ctx, out ); 2098 } /* end FNV256string */ 2100 /* FNV256 hash a counted block (64/32 bit) 2101 ********************************************************************/ 2102 int FNV256block ( const unsigned char *in, 2103 long int length, 2104 uint8_t out[FNV256size] ) 2105 { 2106 FNV256context ctx; 2107 int err; 2109 if ( (err = FNV256init ( &ctx )) ) 2110 return err; 2111 if ( (err = FNV256blockin ( &ctx, in, length)) ) 2112 return err; 2113 return FNV256result ( &ctx, out ); 2114 } /* end FNV256block */ 2116 /******************************************************************** 2117 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2118 ********************************************************************/ 2119 #ifdef FNV_64bitIntegers 2121 /* 0x0000000000000000 0000010000000000 2122 0000000000000000 0000000000000163 */ 2124 #define FNV256primeX 0x0163 2125 #define FNV256shift 8 2127 /* 0xDD268DBCAAC55036 2D98C384C4E576CC 2128 C8B1536847B6BBB3 1023B4C8CAEE0535 */ 2129 uint32_t FNV256basis[FNV256size/4] = { 2130 0xDD268DBC, 0xAAC55036, 0x2D98C384, 0xC4E576CC, 2131 0xC8B15368, 0x47B6BBB3, 0x1023B4C8, 0xCAEE0535 }; 2133 /******************************************************************** 2134 * Set of init, input, and output functions below * 2135 * to incrementally compute FNV256 * 2136 ********************************************************************/ 2138 /* initialize context (64 bit) 2139 ********************************************************************/ 2140 int FNV256init ( FNV256context *ctx ) 2141 { 2142 int i; 2144 if ( ctx ) 2145 { 2146 for ( i=0; iHash[i] = FNV256basis[i]; 2148 ctx->Computed = FNVinited+FNV256state; 2149 return fnvSuccess; 2150 } 2151 return fnvNull; 2152 } /* end FNV256init */ 2154 /* initialize context with a provided basis (64 bit) 2155 ********************************************************************/ 2156 int FNV256initBasis ( FNV256context* const ctx, 2157 const uint8_t basis[FNV256size] ) 2158 { 2159 int i; 2160 uint8_t *ui8p; 2161 uint32_t temp; 2163 if ( ctx ) 2164 { 2165 #ifdef FNV_BigEndian 2166 ui8p = basis; 2167 for ( i=0; i < FNV256size/4; ++i ) 2168 { 2169 temp = (*ui8p++)<<8; 2170 temp = (temp + *ui8p++)<<8; 2171 temp = (temp + *ui8p++)<<8; 2172 ctx->Hash[i] = temp + *ui8p; 2173 } 2175 #else 2176 ui8p = basis + (FNV256size/4 - 1); 2177 for ( i=0; i < FNV256size/4; ++i ) 2178 { 2179 temp = (*ui8p--)<<8; 2180 temp = (temp + *ui8p--)<<8; 2181 temp = (temp + *ui8p--)<<8; 2182 ctx->Hash[i] = temp + *ui8p; 2183 } 2184 #endif 2185 ctx->Computed = FNVinited+FNV256state; 2186 return fnvSuccess; 2187 } 2188 return fnvNull; 2189 } /* end FNV256initBasis */ 2191 /* hash in a counted block (64 bit) 2192 ********************************************************************/ 2193 int FNV256blockin ( FNV256context *ctx, 2194 const unsigned char *in, 2195 long int length ) 2196 { 2197 uint64_t temp[FNV256size/4]; 2198 uint64_t temp2[3]; 2199 int i; 2201 if ( ctx && in ) 2202 { 2203 if ( length < 0 ) 2204 return fnvBadParam; 2205 switch ( ctx->Computed ) 2206 { 2207 case FNVinited+FNV256state: 2208 ctx->Computed = FNVcomputed+FNV256state; 2209 case FNVcomputed+FNV256state: 2210 break; 2211 default: 2212 return fnvStateError; 2213 } 2214 for ( i=0; iHash[i]; 2216 for ( ; length > 0; length-- ) 2217 { 2218 /* temp = FNV256prime * ( temp ^ *in++ ); */ 2219 temp[7] ^= *in++; 2220 temp2[2] = temp[7] << FNV256shift; 2221 temp2[1] = temp[6] << FNV256shift; 2222 temp2[0] = temp[5] << FNV256shift; 2223 for ( i=0; i0; --i ) 2230 { 2231 temp[i-1] += temp[i] >> 16; 2232 temp[i] &= 0xFFFF; 2233 } 2234 } 2235 for ( i=0; iHash[i] = temp[i]; 2237 return fnvSuccess; 2238 } 2239 return fnvNull; 2240 } /* end FNV256input */ 2242 /* hash in a string (64 bit) 2243 ********************************************************************/ 2244 int FNV256stringin ( FNV256context *ctx, const char *in ) 2245 { 2246 uint64_t temp[FNV256size/4]; 2247 uint64_t temp2[3]; 2248 int i; 2249 uint8_t ch; 2251 if ( ctx && in ) 2252 { 2253 switch ( ctx->Computed ) 2254 { 2255 case FNVinited+FNV256state: 2256 ctx->Computed = FNVcomputed+FNV256state; 2257 case FNVcomputed+FNV256state: 2258 break; 2259 default: 2260 return fnvStateError; 2261 } 2262 for ( i=0; iHash[i]; 2264 while ( (ch = (uint8_t)*in++) ) 2265 { 2266 /* temp = FNV256prime * ( temp ^ ch ); */ 2267 temp[7] ^= ch; 2268 temp2[2] = temp[7] << FNV256shift; 2269 temp2[1] = temp[6] << FNV256shift; 2270 temp2[0] = temp[5] << FNV256shift; 2271 for ( i=0; i0; --i ) 2277 { 2278 temp[i-1] += temp[i] >> 16; 2279 temp[i] &= 0xFFFF; 2280 } 2281 } 2282 for ( i=0; iHash[i] = temp[i]; 2284 return fnvSuccess; 2285 } 2286 return fnvNull; 2287 } /* end FNV256stringin */ 2289 /* return hash (64 bit) 2290 ********************************************************************/ 2291 int FNV256result ( FNV256context *ctx, uint8_t out[FNV256size] ) 2292 { 2293 int i; 2295 if ( ctx && out ) 2296 { 2297 if ( ctx->Computed != FNVcomputed+FNV256state ) 2298 return fnvStateError; 2299 for ( i=0; iHash[i]; 2303 out[31-4*i] = ctx->Hash[i] >> 8; 2304 out[31-4*i] = ctx->Hash[i] >> 16; 2305 out[31-4*i] = ctx->Hash[i] >> 24; 2306 #else 2307 out[4*i] = ctx->Hash[i]; 2308 out[4*i+1] = ctx->Hash[i] >> 8; 2309 out[4*i+2] = ctx->Hash[i] >> 16; 2310 out[4*i+3] = ctx->Hash[i] >> 24; 2311 #endif 2312 ctx -> Hash[i] = 0; 2313 } 2314 ctx->Computed = FNVemptied+FNV256state; 2315 return fnvSuccess; 2316 } 2317 return fnvNull; 2318 } /* end FNV256result */ 2320 /****************************************************************** 2321 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2322 ******************************************************************/ 2323 #else /* FNV_64bitIntegers */ 2324 /****************************************************************** 2325 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2326 ******************************************************************/ 2328 /* version for when you only have 32-bit arithmetic 2329 ********************************************************************/ 2331 /* 0x00000000 00000000 00000100 00000000 2332 00000000 00000000 00000000 00000163 */ 2333 #define FNV256primeX 0x0163 2334 #define FNV256shift 8 2336 /* 0xDD268DBCAAC55036 2D98C384C4E576CC 2337 C8B1536847B6BBB3 1023B4C8CAEE0535 */ 2338 uint16_t FNV256basis[FNV256size/2] = { 2339 0xDD26, 0x8DBC, 0xAAC5, 0x5036, 2340 0x2D98, 0xC384, 0xC4E5, 0x76CC, 2341 0xC8B1, 0x5368, 0x47B6, 0xBBB3, 2342 0x1023, 0xB4C8, 0xCAEE, 0x0535 }; 2344 /******************************************************************** 2345 * Set of init, input, and output functions bel ow * 2346 * to incrementally compute FNV256 * 2347 ********************************************************************/ 2349 /* initialize context (32 bit) 2350 ********************************************************************/ 2351 int FNV256init ( FNV256context *ctx ) 2352 { 2353 int i; 2355 if ( ctx ) 2356 { 2357 for ( i=0; iHash[i] = FNV256basis[i]; 2359 ctx->Computed = FNVinited+FNV256state; 2360 return fnvSuccess; 2361 } 2362 return fnvNull; 2363 } /* end FNV256init */ 2365 /* initialize context with a provided basis (32 bit) 2366 ********************************************************************/ 2367 int FNV256initBasis ( FNV128context *ctx, 2368 const unint8_t basis[FNV256size) ) 2369 { 2370 int i; 2371 unit8_t *ui8p; 2372 uint32_t temp; 2374 if ( ctx ) 2375 { 2377 #ifdef FNV_BigEndian 2378 ui8p = basis; 2379 for ( i=0; i < FNV256size/2; ++i ) 2380 { 2381 temp = *ui8p++; 2382 ctx->Hash[i] = temp<<8 + (*ui8p++); 2383 } 2384 #else 2385 ui8p = basis + FNV256size/2 -1; 2386 for ( i=0; i < FNV256size/2; ++i ) 2387 { 2388 temp = *ui8p--; 2389 ctx->Hash[i] = temp<<8 + (*ui8p--); 2390 } 2391 #endif 2392 ctx->Computed = FNVinited+FNV256state; 2393 return fnvSuccess; 2394 } 2395 return fnvNull; 2396 } /* end FNV256initBasis */ 2398 /* hash in a counted block (32 bit) 2399 *******************************************************************/ 2400 int FNV256blockin ( FNV256context *ctx, 2401 const unsigned char *in, 2402 long int length ) 2403 { 2404 uint32_t temp[FNV256size/2]; 2405 uint32_t temp2[6]; 2406 int i; 2408 if ( ctx && in ) 2409 { 2410 if ( length < 0 ) 2411 return fnvBadParam; 2412 switch ( ctx->Computed ) 2413 { 2414 case FNVinited+FNV256state: 2415 ctx->Computed = FNVcomputed+FNV256state; 2416 case FNVcomputed+FNV256state: 2417 break; 2418 default: 2419 return fnvStateError; 2420 } 2421 for ( i=0; iHash[i]; 2423 for ( ; length > 0; length-- ) 2424 { 2425 /* temp = FNV256prime * ( temp ^ *in++ ); */ 2426 temp[15] ^= *in++; 2427 for ( i=0; i<6; ++i ) 2428 temp2[i] = temp[10+i] << FNV256shift; 2429 for ( i=0; i0; --i ) 2434 { 2435 temp[i-1] += temp[i] >> 16; 2436 temp[i] &= 0xFFFF; 2437 } 2438 } 2439 for ( i=0; iHash[i] = temp[i]; 2441 return fnvSuccess; 2442 } 2443 return fnvNull; 2444 } /* end FNV256blockin */ 2446 /* hash in a string (32 bit) 2447 *******************************************************************/ 2448 int FNV256stringin ( FNV256context *ctx, const char *in ) 2449 { 2450 uint32_t temp[FNV256size/2]; 2451 uint32_t temp2[6]; 2452 int i; 2453 uint8_t ch; 2455 if ( ctx && in ) 2456 { 2457 switch ( ctx->Computed ) 2458 { 2459 case FNVinited+FNV256state: 2460 ctx->Computed = FNVcomputed+FNV256state; 2461 case FNVcomputed+FNV256state: 2462 break; 2463 default: 2464 return fnvStateError; 2465 } 2466 for ( i=0; iHash[i]; 2468 while ( ch = (uint8_t)*in++ ) 2469 { 2470 /* temp = FNV256prime * ( temp ^ *in++ ); */ 2471 temp[15] ^= ch; 2472 for ( i=0; i<6; ++i ) 2473 temp2[i] = temp[10+i] << FNV256shift; 2474 for ( i=0; i0; --i ) 2479 { 2480 temp[i-1] += temp[i] >> 16; 2481 temp[i] &= 0xFFFF; 2482 } 2483 } 2484 for ( i=0; iHash[i] = temp[i]; 2486 return fnvSuccess; 2487 } 2488 return fnvNull; 2489 } /* end FNV256stringin */ 2491 /* return hash (32 bit) 2492 ********************************************************************/ 2493 int FNV256result ( FNV256context *ctx, unit8_t out[FNV256size] ) 2494 { 2495 int i; 2497 if ( ctx && out ) 2498 { 2499 if ( ctx->Computed != FNVcomputed+FNV256state ) 2500 return fnvStateError; 2501 for ( i=0; iHash[i]; 2505 out[30-2*i] = ctx->Hash[i] >> 8; 2506 #else 2507 out[2*i] = ctx->Hash[i]; 2508 out[2*i+1] = ctx->Hash[i] >> 8; 2509 #endif 2510 ctx->Hash[i] = 0; 2511 } 2512 ctx->Computed = FNVemptied+FNV256state; 2513 return fnvSuccess; 2514 } 2515 return fnvNull; 2516 } /* end FNV256result */ 2518 #endif /* Have64bitIntegers */ 2519 /******************************************************************** 2520 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2521 ********************************************************************/ 2523 #endif /* _FNV256_C_ */ 2524 2526 6.1.5 FNV512 C Code 2528 The header and C source for 512-bit FNV-1a. 2530 2531 /**************************** FNV512.h **************************/ 2532 /***************** See RFC NNNN for details. ********************/ 2533 /* 2534 * Copyright (c) 2015 IETF Trust and the persons identified as 2535 * authors of the code. All rights reserved. 2536 * See fnv-private.h for terms of use and redistribution. 2537 */ 2539 #ifndef _FNV512_H_ 2540 #define _FNV512_H_ 2542 /* 2543 * Description: 2544 * This file provides headers for the 512-bit version of the 2545 * FNV-1a non-cryptographic hash algorithm. 2546 * 2547 * >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */ 2549 #define FNV_64bitIntegers 2551 /* FNV_64bitIntegers - Define this if your system supports 64-bit 2552 * arithmetic including 32-bit x 32-bit multiplication 2553 * producing a 64-bit product. If undefined, it will be 2554 * assumed that 32-bit arithmetic is supported including 2555 * 16-bit x 16-bit multiplication producing a 32-bit result. 2556 * 2557 * FNV_BigEndian - Define this ONLY if your system uses big 2558 * endian representation AND your FNV hashes need to 2559 * interoperate with little endian systems. If you #define 2560 * this symbol when not needed, it will unnecessarily slow 2561 * down and increase the code size of the FNV functions. 2562 */ 2564 #include 2565 #define FNV512size (512/8) 2567 /* If you do not have the ISO standard stdint.h header file, then you 2568 * must typedef the following types: 2569 * 2570 * type meaning 2571 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 2572 * uint32_t unsigned 32 bit integer 2573 * uint16_t unsigned 16 bit integer 2574 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 2575 */ 2577 #ifndef _FNV_ErrCodes_ 2578 #define _FNV_ErrCodes_ 2579 /********************************************************************* 2580 * All FNV functions provided return as integer as follows: 2581 * 0 -> success 2582 * >0 -> error as listed below 2583 */ 2584 enum { /* success and errors */ 2585 fnvSuccess = 0, 2586 fnvNull, /* Null pointer parameter */ 2587 fnvStateError, /* called Input after Result or before Init */ 2588 fnvBadParam /* passed a bad parameter */ 2589 }; 2590 #endif /* _FNV_ErrCodes_ */ 2592 /* 2593 * This structure holds context information for an FNV512 hash 2594 */ 2595 #ifdef FNV_64bitIntegers 2596 /* version if 64 bit integers supported */ 2597 typedef struct FNV512context_s { 2598 int Computed; /* state */ 2599 uint32_t Hash[FNV512size/4]; 2600 } FNV512context; 2602 #else 2603 /* version if 64 bit integers NOT supported */ 2605 typedef struct FNV512context_s { 2606 int Computed; /* state */ 2607 uint16_t Hash[FNV512size/2]; 2608 } FNV512context; 2610 #endif /* FNV_64bitIntegers */ 2612 /* 2613 * Function Prototypes 2614 * FNV512string: hash a zero terminated string not including 2615 * the terminating zero 2616 * FNV512block: FNV512 hash a specified length byte vector 2617 * FNV512init: initializes an FNV512 context 2618 * FNV512initBasis: initializes an FNV512 context with a 2619 * provided basis 2620 * FNV512blockin: hash in a specified length byte vector 2621 * FNV512stringin: hash in a zero terminated string not 2622 * including the zero 2623 * FNV512result: returns the hash value 2624 * 2625 * Hash is returned as an array of 8-bit integers 2626 */ 2628 /* FNV512 */ 2629 extern int FNV512string ( const char *in, 2630 uint8_t out[FNV512size] ); 2631 extern int FNV512block ( const unsigned char *in, 2632 long int length, 2633 uint8_t out[FNV512size] ); 2634 extern int FNV512init ( FNV512context *); 2635 extern int FNV512initBasis ( FNV512context * const, 2636 const uint8_t basis[FNV512size] ); 2637 extern int FNV512blockin ( FNV512context *, 2638 const unsigned char *in, 2639 long int length ); 2640 extern int FNV512stringin ( FNV512context *, 2641 const char *in ); 2642 extern int FNV512result ( FNV512context *, 2643 uint8_t out[FNV512size] ); 2645 #endif /* _FNV512_H_ */ 2646 2648 2649 /***************************** FNV512.c ****************************/ 2650 /******************** See RFC NNNN for details *********************/ 2651 /* Copyright (c) 2015 IETF Trust and the persons identified as 2652 * authors of the code. All rights 2653 * See fnv-private.h for terms of use and redistribution. 2654 */ 2656 /* This file implements the FNV (Fowler, Noll, Vo) non-cryptographic 2657 * hash function FNV-1a for 512-bit hashes. 2658 */ 2660 #ifndef _FNV512_C_ 2661 #define _FNV512_C_ 2663 #include "fnv-private.h" 2664 #include "FNV512.h" 2666 /* common code for 64 and 32 bit modes */ 2668 /* FNV512 hash a null terminated string (64/32 bit) 2669 ********************************************************************/ 2670 int FNV512string ( const char *in, uint8_t out[FNV512size] ) 2671 { 2672 FNV512context ctx; 2673 int err; 2675 if ( (err = FNV512init ( &ctx )) ) 2676 return err; 2677 if ( (err = FNV512stringin ( &ctx, in )) ) 2678 return err; 2679 return FNV512result ( &ctx, out ); 2680 } /* end FNV512string */ 2682 /* FNV512 hash a counted block (64/32 bit) 2683 ********************************************************************/ 2684 int FNV512block ( const unsigned char *in, 2685 long int length, 2686 uint8_t out[FNV512size] ) 2687 { 2688 FNV512context ctx; 2689 int err; 2691 if ( (err = FNV512init ( &ctx )) ) 2692 return err; 2693 if ( (err = FNV512blockin ( &ctx, in, length)) ) 2694 return err; 2695 return FNV512result ( &ctx, out ); 2696 } /* end FNV512block */ 2698 /******************************************************************** 2699 * START VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2700 ********************************************************************/ 2701 #ifdef Have64bitIntegers 2703 /* 0x0000000000000000 0000000000000000 2704 0000000001000000 0000000000000000 2705 0000000000000000 0000000000000000 2706 0000000000000000 0000000000000157 */ 2707 #define FNV512primeX 0x0157 2708 #define FNV512shift 24 2710 /* 0xB86DB0B1171F4416 DCA1E50F309990AC 2711 AC87D059C9000000 0000000000000D21 2712 E948F68A34C192F6 2EA79BC942DBE7CE 2713 182036415F56E34B AC982AAC4AFE9FD9 */ 2714 uint32_t FNV512basis[FNV512size/4] = { 2715 0xB86DB0B1, 0x171F4416, 0xDCA1E50F, 0x209990AC, 2716 0xAC87D059, 0x9C000000, 0x00000000, 0x00000D21, 2717 0xE948F68A, 0x34C192F6, 0x2EA79BC9, 0x42DBE7CE, 2718 0x18203641, 0x5F56E34B, 0xAC982AAC, 0x4AFE9FD9 }; 2720 /******************************************************************** 2721 * Set of init, input, and output functions below * 2722 * to incrementally compute FNV512 * 2723 ********************************************************************/ 2725 /* initialize context (64 bit) 2726 ********************************************************************/ 2728 int FNV512init ( FNV512context *ctx ) 2729 { 2730 if ( ctx ) 2731 { 2732 for ( i=0; iHash[i] = FNV512basis[i]; 2734 ctx->Computed = FNVinited+FNV512state; 2735 return fnvSuccess; 2736 } 2737 return fnvNull; 2738 } /* end FNV512init */ 2740 /* initialize context with a provided basis (64 bit) 2741 ********************************************************************/ 2742 int FNV512initBasis ( FNV512context* const ctx, 2743 const uint8_t basis[FNV512size] ) 2744 { 2745 int i; 2746 uint8_t *ui8p; 2747 uint32_t temp; 2749 if ( ctx ) 2750 { 2751 #ifdef FNV_BigEndian 2752 ui8p = basis; 2753 for ( i=0; i < FNV512size/4; ++i ) 2754 { 2755 temp = (*ui8p++)<<8; 2756 temp = (temp + *ui8p++)<<8; 2757 temp = (temp + *ui8p++)<<8; 2758 ctx->Hash[i] = temp + *ui8p; 2759 } 2760 #else 2761 ui8p = basis + (FNV512size/4 - 1); 2762 for ( i=0; i < FNV512size/4; ++i ) 2763 { 2764 temp = (*ui8p--)<<8; 2765 temp = (temp + *ui8p--)<<8; 2766 temp = (temp + *ui8p--)<<8; 2767 ctx->Hash[i] = temp + *ui8p; 2768 } 2769 #endif 2770 ctx->Computed = FNVinited+FNV512state; 2771 return fnvSuccess; 2772 } 2773 return fnvNull; 2774 } /* end FNV512initBasis */ 2776 /* hash in a counted block (64 bit) 2777 ********************************************************************/ 2779 int FNV512blockin ( FNV512context *ctx, 2780 const unsigned char *in, 2781 long int length ) 2782 { 2783 uint64_t temp[FNV512size/4]; 2784 uint64_t temp2[3]; 2786 if ( ctx && in ) 2787 { 2788 switch ( ctx->Computed ) 2789 { 2790 case FNVinited+FNV512state: 2791 ctx->Computed = FNVcomputed+FNV128state; 2792 case FNVcomputed+FNV512state: 2793 break; 2794 default: 2795 return fnvStateError; 2796 } 2797 if ( length < 0 ) 2798 return fnvBadParam; 2799 for ( i=0; iHash[i]; 2801 for ( ; length > 0; length-- ) 2802 { 2803 /* temp = FNV512prime * ( temp ^ *in++ ); */ 2804 temp[7] ^= *in++; 2805 temp2[2] = temp[7] << FNV512shift; 2806 temp2[1] = temp[6] << FNV512shift; 2807 temp2[0] = temp[5] << FNV512shift; 2808 for ( i=0; i0; --i ) 2814 { 2815 temp[i-1] += temp[i] >> 16; 2816 temp[i] &= 0xFFFF; 2817 } 2818 } 2819 for ( i=0; iHash[i] = temp[i]; 2821 return fnvSuccess; 2822 } 2823 return fnvNull; 2824 } /* end FNV512input */ 2826 /* hash in a string (64 bit) 2827 ********************************************************************/ 2828 inf FNV512stringin ( FNV512context *ctx, const char *in ) 2829 { 2830 uint64_t temp[FNV512size/4]; 2831 uint64_t temp2[2]; 2832 int i; 2833 uint8_t ch; 2835 if ( ctx && in ) 2836 { 2837 switch ( ctx->Computed ) 2838 { 2839 case FNVinited+FNV512state: 2840 ctx->Computed = FNVcomputed+FNV512state; 2841 case FNVcomputed+FNV512state: 2842 break; 2843 default: 2844 return fnvStateError; 2845 } 2846 for ( i=0; iHash[i]; 2848 while ( ch = (uint8_t)*in++ ) 2849 { 2850 /* temp = FNV512prime * ( temp ^ ch ); */ 2851 temp[7] ^= ch; 2852 temp2[2] = temp[7] << FNV128shift; 2853 temp2[1] = temp[6] << FNV128shift; 2854 temp2[0] = temp[5] << FNV128shift; 2855 for ( i=0; i0; --i ) 2861 { 2862 temp[i-1] += temp[i] >> 16; 2863 temp[i] &= 0xFFFF; 2864 } 2865 } 2866 for ( i=0; iHash[i] = temp[i]; 2868 return fnvSuccess; 2869 } 2870 return fnvNull; 2871 } /* end FNV512stringin */ 2873 /* return hash (64 bit) 2874 ********************************************************************/ 2875 int FNV512result ( FNV512context *ctx, uint8_t out[FNV512size] ) 2876 { 2877 if ( ctx && out ) 2878 { 2879 if ( ctx->Computed != FNVcomputed+FNV512state ) 2880 return fnvStateError; 2881 for ( i=0; iHash[i]; 2885 out[14-2*i] = ctx->Hash[i] >> 8; 2886 #else 2887 out[2*i] = ctx->Hash[i]; 2888 out[2*i+1] = ctx->Hash[i] >> 8; 2889 #endif 2890 ctx -> Hash[i] = 0; 2891 } 2892 ctx->Computed = FNVemptied+FNV512state; 2893 return fnvSuccess; 2894 } 2895 return fnvNull; 2896 } /* end FNV512result */ 2898 /****************************************************************** 2899 * END VERSION FOR WHEN YOU HAVE 64 BIT ARITHMETIC * 2900 ******************************************************************/ 2901 #else /* FNV_64bitIntegers */ 2902 /****************************************************************** 2903 * START VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 2904 ******************************************************************/ 2906 /* version for when you only have 32-bit arithmetic 2907 ********************************************************************/ 2909 /* 0x0000000000000000 0000000000000000 2910 0000000001000000 0000000000000000 2911 0000000000000000 0000000000000000 2912 0000000000000000 0000000000000157 */ 2913 #define FNV512primeX 0x0157 2914 #define FNV512shift 8 2916 /* 0xB86DB0B1171F4416 DCA1E50F309990AC 2917 AC87D059C9000000 0000000000000D21 2918 E948F68A34C192F6 2EA79BC942DBE7CE 2919 182036415F56E34B AC982AAC4AFE9FD9 */ 2920 uint16_t FNV512basis[FNV512size/2] = { 2921 0xB86D, 0xB0B1, 0x171F, 0x4416, 0xDCA1, 0xE50F, 0x3099, 0x90AC, 2922 0xAC87, 0xD059, 0xC900, 0x0000, 0x0000, 0x0000, 0x0000, 0x0D21, 2923 0xE948, 0xF68A, 0x34C1, 0x92F6, 0x2EA7, 0x9BC9, 0x42DB, 0xE7CE, 2924 0x1820, 0x3641, 0x5F56, 0xE34B, 0xAC98, 0x2AAC, 0x4AFE, 0x9FD9 }; 2926 /******************************************************************** 2927 * Set of init, input, and output functions bel ow * 2928 * to incrementally compute FNV512 * 2929 ********************************************************************/ 2931 /* initialize context (32 bit) 2932 ********************************************************************/ 2933 int FNV512init ( FNV512context *ctx ) 2934 { 2935 int i; 2937 if ( ctx ) 2938 { 2939 for ( i=0; iHash[i] = FNV512basis[i]; 2941 ctx->Computed = FNVinited+FNV512state; 2942 return fnvSuccess; 2943 } 2944 return fnvNull; 2945 } /* end FNV512init */ 2947 /* initialize context with a provided basis (32 bit) 2948 ********************************************************************/ 2949 int FNV512initBasis ( FNV512context *ctx, 2950 const uint8_t basis[FNV512size] ) 2951 { 2952 int i; 2953 uint8_t *ui8p; 2954 uint32_t temp; 2956 if ( ctx ) 2957 { 2958 #ifdef FNV_BigEndian 2959 ui8p = basis; 2960 for ( i=0; i < FNV512size/2; ++i ) 2961 { 2962 temp = *ui8p++; 2963 ctx->Hash[i] = temp<<8 + (*ui8p++); 2964 } 2965 #else 2966 ui8p = basis + ( FNV512size/2 - 1 ); 2967 for ( i=0; i < FNV512size/2; ++i ) 2968 { 2969 temp = *ui8p--; 2970 ctx->Hash[i] = ( temp<<8 ) + (*ui8p--); 2971 } 2972 #endif 2973 ctx->Computed = FNVinited+FNV512state; 2974 return fnvSuccess; 2975 } 2976 return fnvNull; 2977 } /* end FNV512initBasis */ 2978 /* hash in a counted block (32 bit) 2979 *******************************************************************/ 2980 int FNV512blockin ( FNV512context *ctx, 2981 const unsigned char *in, 2982 long int length ) 2983 { 2984 uint32_t temp[FNV512size/2]; 2985 uint32_t temp2[6]; 2986 int i; 2988 if ( ctx && in ) 2989 { 2990 switch ( ctx->Computed ) 2991 { 2992 case FNVinited+FNV512state: 2993 ctx->Computed = FNVcomputed+FNV512state; 2994 case FNVcomputed+FNV512state: 2995 break; 2996 default: 2997 return fnvStateError; 2998 } 2999 if ( length < 0 ) 3000 return fnvBadParam; 3001 for ( i=0; iHash[i]; 3003 for ( ; length > 0; length-- ) 3004 { 3005 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3006 temp[15] ^= *in++; 3007 for ( i=0; i<6; ++i ) 3008 temp2[i] = temp[10+i] << FNV512shift; 3009 for ( i=0; i0; --i ) 3014 { 3015 temp[i-1] += temp[i] >> 16; 3016 temp[i] &= 0xFFFF; 3017 } 3018 } 3019 for ( i=0; iHash[i] = temp[i]; 3021 return fnvSuccess; 3022 } 3023 return fnvNull; 3024 } /* end FNV512blockin */ 3026 /* hash in a string (32 bit) 3027 *******************************************************************/ 3029 int FNV512stringin ( FNV512context *ctx, const char *in ) 3030 { 3031 uint32_t temp[FNV512size/2]; 3032 uint32_t temp2[6]; 3033 int i; 3034 uint8_t ch; 3036 if ( ctx && in ) 3037 { 3038 switch ( ctx->Computed ) 3039 { 3040 case FNVinited+FNV512state: 3041 ctx->Computed = FNVcomputed+FNV512state; 3042 case FNVcomputed+FNV512state: 3043 break; 3044 default: 3045 return fnvStateError; 3046 } 3047 for ( i=0; iHash[i]; 3049 while ( (ch = (uint8_t)*in++) ) 3050 { 3051 /* temp = FNV512prime * ( temp ^ *in++ ); */ 3052 temp[15] ^= ch; 3053 for ( i=0; i<6; ++i ) 3054 temp2[i] = temp[10+i] << FNV512shift; 3055 for ( i=0; i0; --i ) 3060 { 3061 temp[i-1] += temp[i] >> 16; 3062 temp[i] &= 0xFFFF; 3063 } 3064 } 3065 for ( i=0; iHash[i] = temp[i]; 3067 return fnvSuccess; 3068 } 3069 return fnvNull; 3070 } /* end FNV512stringin */ 3072 /* return hash (32 bit) 3073 ********************************************************************/ 3074 int FNV512result ( FNV512context *ctx, unsigned char out[16] ) 3075 { 3076 int i; 3078 if ( ctx && out ) 3079 { 3080 if ( ctx->Computed != FNVcomputed+FNV512state ) 3081 return fnvStateError; 3082 for ( i=0; iHash[i]; 3086 out[30-2*i] = ctx->Hash[i] >> 8; 3087 #else 3088 out[2*i] = ctx->Hash[i]; 3089 out[2*i+1] = ctx->Hash[i] >> 8; 3090 #endif 3091 ctx->Hash[i] = 0; 3092 } 3093 ctx->Computed = FNVemptied+FNV512state; 3094 return fnvSuccess; 3095 } 3096 return fnvNull; 3097 } /* end FNV512result */ 3099 #endif /* Have64bitIntegers */ 3100 /******************************************************************** 3101 * END VERSION FOR WHEN YOU ONLY HAVE 32-BIT ARITHMETIC * 3102 ********************************************************************/ 3104 #endif /* _FNV512_C_ */ 3105 3107 6.1.6 FNV1024 C Code 3109 The header and C source for 1024-bit FNV-1a. 3111 3112 /*************************** FNV1024.h **************************/ 3113 /***************** See RFC NNNN for details. ********************/ 3114 /* 3115 * Copyright (c) 2015 IETF Trust and the persons identified as 3116 * authors of the code. All rights reserved. 3117 * See fnv-private.h for terms of use and redistribution. 3118 */ 3120 #ifndef _FNV1024_H_ 3121 #define _FNV1024_H_ 3123 /* 3124 * Description: 3125 * This file provides headers for the 1024-bit version of the 3126 * FNV-1a non-cryptographic hash algorithm. 3128 * 3129 * >>>>>>>> IMPORTANT CONFIGURATION ifdefs: <<<<<<<<<< */ 3131 #define FNV_64bitIntegers 3133 /* FNV_64bitIntegers - Define this if your system supports 64-bit 3134 * arithmetic including 32-bit x 32-bit multiplication 3135 * producing a 64-bit product. If undefined, it will be 3136 * assumed that 32-bit arithmetic is supported including 3137 * 16-bit x 16-bit multiplication producing a 32-bit result. 3138 * 3139 * FNV_BigEndian - Define this ONLY if your system uses big 3140 * endian representation AND your FNV hashes need to 3141 * interoperate with little endian systems. If you #define 3142 * this symbol when not needed, it will unnecessarily slow 3143 * down and increase the code size of the FNV functions. 3144 */ 3146 #include 3147 #define FNV1024size (1024/8) 3149 /* If you do not have the ISO standard stdint.h header file, then you 3150 * must typedef the following types: 3151 * 3152 * type meaning 3153 * uint64_t unsigned 64 bit integer (ifdef FNV_64bitIntegers) 3154 * uint32_t unsigned 32 bit integer 3155 * uint16_t unsigned 16 bit integer 3156 * uint8_t unsigned 8 bit integer (i.e., unsigned char) 3157 */ 3159 #ifndef _FNV_ErrCodes_ 3160 #define _FNV_ErrCodes_ 3161 /********************************************************************* 3162 * All FNV functions provided return as integer as follows: 3163 * 0 -> success 3164 * >0 -> error as listed below 3165 */ 3166 enum { /* success and errors */ 3167 fnvSuccess = 0, 3168 fnvNull, /* Null pointer parameter */ 3169 fnvStateError, /* called Input after Result or before Init */ 3170 fnvBadParam /* passed a bad parameter */ 3171 }; 3172 #endif /* _FNV_ErrCodes_ */ 3174 /* 3175 * This structure holds context information for an FNV1024 hash 3176 */ 3177 #ifdef FNV_64bitIntegers 3178 /* version if 64 bit integers supported */ 3179 typedef struct FNV1024context_s { 3180 int Computed; /* state */ 3181 uint32_t Hash[FNV1024size/4]; 3182 } FNV1024context; 3184 #else 3185 /* version if 64 bit integers NOT supported */ 3187 typedef struct FNV1024context_s { 3188 int Computed; /* state */ 3189 uint16_t Hash[FNV1024size/2]; 3190 } FNV1024context; 3192 #endif /* FNV_64bitIntegers */ 3194 /* 3195 * Function Prototypes 3196 * FNV1024string: hash a zero terminated string not including 3197 * the terminating zero 3198 * FNV1024block: FNV1024 hash a specified length byte vector 3199 * FNV1024init: initializes an FNV1024 context 3200 * FNV1024initBasis: initializes an FNV1024 context with a 3201 * provided basis 3202 * FNV1024blockin: hash in a specified length byte vector 3203 * FNV1024stringin: hash in a zero terminated string not 3204 * including the zero 3205 * FNV1024result: returns the hash value 3206 * 3207 * Hash is returned as an array of 8-bit integers 3208 */ 3210 /* FNV1024 */ 3211 extern int FNV1024string ( const char *in, 3212 unsigned char out[FNV1024size] ); 3213 extern int FNV1024block ( const unsigned char *in, 3214 unsigned long int length, 3215 unsigned char out[FNV1024size] ); 3216 extern int FNV1024init ( FNV1024context *); 3217 extern int FNV1024initBasis ( FNV128context * const, 3218 const uint8_t basis[FNV1024size] ); 3219 extern int FNV1024blockin ( FNV1024context *, 3220 const unsigned char *in, 3221 long int length ); 3222 extern int FNV1024stringin ( FNV1024context *, 3223 const char *in ); 3224 extern int FNV1024result ( FNV1024context *, 3225 unsigned char out[FNV1024size] ); 3227 #endif /* _FNV1024_H_ */ 3228 3230 3231 TBD 3232 3234 6.2 FNV Test Code 3236 Here is a test driver: 3238 3239 /**************************** MAIN.c ****************************/ 3240 /****************** See RFC NNNN for details. *******************/ 3241 /* 3242 * Copyright (c) 2015 IETF Trust and the persons identified as 3243 * authors of the code. All rights reserved. 3244 * See fnv-private.h for terms of use and redistribution. 3245 */ 3246 /* to do a thorough test you need to run will all four 3247 combinations of the following defined/undefined */ 3249 #define FNV_64bitIntegers 3250 // #define FNV_BigEndian 3252 #include 3253 #include 3255 #include "fnv-private.h" 3256 #include "FNV32.h" 3257 #include "FNV64.h" 3258 #include "FNV128.h" 3259 #include "FNV256.h" 3260 #include "FNV512.h" 3261 #include "FNV1024.h" 3263 /* global variables */ 3264 char *funcName; 3265 char *errteststring = "foo"; 3266 int Terr; /* Total errors */ 3267 #define NTestBytes 3 3268 uint8_t errtestbytes[NTestBytes] = { (uint8_t)1, 3269 (uint8_t)2, (uint8_t)3 }; 3271 #define NTstrings 3 3272 char *teststring[NTstrings] = { "", "a", "foobar" }; 3274 /***************************************************************** 3275 * local prototypes 3276 *****************************************************************/ 3277 int TestR ( char *, int should, int was ); 3278 void TestNValue ( char *subfunc, 3279 char *string, 3280 int N, 3281 uint8_t *should, 3282 uint8_t *was ); 3283 void HexPrint ( int i, unsigned char *p ); 3284 void Test32 (); 3285 void Test32Value ( char *subfunc, char *string, 3286 uint32_t was, uint32_t should ); 3287 void Test64 (); 3288 #ifdef FNV_64bitIntegers 3289 void Test64Value ( char *subfunc, char *string, 3290 uint64_t should, uint64_t was ); 3291 #endif /* FNB_64bitIntegers */ 3292 void Test128 (); 3293 void Test256 (); 3294 void Test512 (); 3295 void Test1024 (); 3297 void TestNValue ( char *subfunc, 3298 char *string, 3299 int N, 3300 uint8_t was[N], 3301 uint8_t should[N] ); 3303 /***************************************************************** 3304 * main 3305 *****************************************************************/ 3306 int main (int argc, const char * argv[]) 3307 { 3308 #ifdef FNV_64bitIntegers 3309 printf ("Have 64-bit Integers. "); 3310 #else 3311 printf ("Do not have 64-bit integers. "); 3312 #endif 3313 #ifdef FNV_BidgEndian 3314 printf ("Calculating for Big Endian.0); 3315 #else 3316 printf ("Not calculating for Big Endian.0); 3317 #endif 3318 funcName = "Testing TestR "; 3319 /* test the Test Return function */ 3320 TestR ( "should fail", 1, 2 ); 3321 TestR ( "should not have failed", 0, 0 ); 3323 Test32(); 3324 Test64(); 3325 Test128(); 3326 Test256(); 3328 printf ("Type return to exit.0); 3329 (void)getchar(); 3330 printf ("Goodbye!0); 3332 return 0; 3333 } /* end main */ 3335 /* Test status returns 3336 *****************************************************************/ 3337 int TestR ( char *name, int expect, int actual ) 3338 { 3339 if ( expect != actual ) 3340 { 3341 printf ( "%s%s returned %i instead of %i.0, 3342 funcName, name, actual, expect ); 3343 ++Terr; 3344 } 3345 return actual; 3346 } /* end TestR */ 3348 /* General byte vector return error test 3349 *****************************************************************/ 3350 void TestNValue ( char *subfunc, 3351 char *string, 3352 int N, 3353 uint8_t *was, 3354 uint8_t *should ) 3355 { 3356 if ( !memcmp ( was, should, N) ) 3357 { 3358 printf ( "%s %s of '%s' computed ", funcName, subfunc, string ); 3359 HexPrint ( N, was ); 3360 printf ( ", should have been " ); 3361 HexPrint ( N, should ); 3362 printf ( ".0 ); 3363 ++Terr; 3364 } 3365 } /* end TestNValue */ 3367 /* print some hex 3368 *****************************************************************/ 3369 void HexPrint ( int count, unsigned char *ptr ) 3370 { 3371 int i; 3373 for ( i = 0; i < count; ++i ) 3374 printf ( "%02X", ptr[i] ); 3375 } /* end HexPrint */ 3376 /***************************************************************** 3377 * FNV32 test 3378 *****************************************************************/ 3379 void Test32 () 3380 { 3381 int i, err; 3382 long int iLen; 3383 uint32_t eUint32; 3384 FNV32context eContext; 3385 uint32_t FNV32svalues[NTstrings] = { 3386 0x811c9dc5, 0xe40c292c, 0xbf9cf968 }; 3387 uint32_t FNV32bvalues[NTstrings] = { 3388 0x050c5d1f, 0x2b24d044, 0x0c1c9eb8 }; 3390 /* test Test32Value */ 3391 funcName = "Test32Value"; 3392 Test32Value ( "should fail", "test", FNV32svalues[1], FNV32svalues[2] ); 3394 funcName = "FNV32"; 3396 /* test error checks */ 3397 Terr = 0; 3398 TestR ( "init", fnvSuccess, FNV32init (&eContext) ); 3399 TestR ( "string", fnvNull, 3400 FNV32string ( (char *)0, &eUint32 ) ); 3401 TestR ( "string", fnvNull, 3402 FNV32string ( errteststring, (uint32_t *)0 ) ); 3403 TestR ( "block", fnvNull, 3404 FNV32block ( (uint8_t *)0, 1, &eUint32 ) ); 3405 TestR ( "block", fnvBadParam, 3406 FNV32block ( errtestbytes, -1, &eUint32 ) ); 3407 TestR ( "block", fnvNull, 3408 FNV32block ( errtestbytes, 1, (uint32_t *)0 ) ); 3409 TestR ( "init", fnvNull, 3410 FNV32init ( (FNV32context *)0 ) ); 3411 TestR ( "initBasis", fnvNull, 3412 FNV32initBasis ( (FNV32context *)0, 42 ) ); 3413 TestR ( "blockin", fnvNull, 3414 FNV32blockin ( (FNV32context *)0, 3415 errtestbytes, NTestBytes ) ); 3416 TestR ( "blockin", fnvNull, 3417 FNV32blockin ( &eContext, (uint8_t *)0, 3418 NTestBytes ) ); 3419 TestR ( "blockin", fnvBadParam, 3420 FNV32blockin ( &eContext, errtestbytes, -1 ) ); 3421 eContext.Computed = FNVclobber+FNV32state; 3422 TestR ( "blockin", fnvStateError, 3423 FNV32blockin ( &eContext, errtestbytes, 3424 NTestBytes ) ); 3425 TestR ( "stringin", fnvNull, 3426 FNV32stringin ( (FNV32context *)0, errteststring ) ); 3427 TestR ( "stringin", fnvNull, 3428 FNV32stringin ( &eContext, (char *)0 ) ); 3429 TestR ( "stringin", fnvStateError, 3430 FNV32stringin ( &eContext, errteststring ) ); 3431 TestR ( "result", fnvNull, 3432 FNV32result ( (FNV32context *)0, &eUint32 ) ); 3433 TestR ( "result", fnvNull, 3434 FNV32result ( &eContext, (uint32_t *)0 ) ); 3435 TestR ( "result", fnvStateError, 3436 FNV32result ( &eContext, &eUint32 ) ); 3437 if ( Terr ) 3438 printf ( "%s test of error checks failed %i times.0, 3439 funcName, Terr ); 3440 else 3441 printf ( "%s test of error checks passed0, funcName ); 3443 /* test actual results */ 3444 Terr = 0; 3445 for ( i = 0; i < NTstrings; ++i ) 3446 { 3447 err = TestR ( "string", fnvSuccess, 3448 FNV32string ( teststring[i], &eUint32 ) ); 3449 if ( err == fnvSuccess ) 3450 Test32Value ( "string", teststring[i], eUint32, 3451 FNV32svalues[i] ); 3452 err = TestR ( "block", fnvSuccess, 3453 FNV32block ( (uint8_t *)teststring[i], 3454 (unsigned long)(strlen(teststring[i])+1), 3455 &eUint32 ) ); 3456 if ( err == fnvSuccess ) 3457 Test32Value ( "block", teststring[i], eUint32, 3458 FNV32bvalues[i] ); 3459 /* now try testing the incremental stuff */ 3460 err = TestR ( "init", fnvSuccess, FNV32init ( &eContext ) ); 3461 if ( err ) break; 3462 iLen = strlen ( teststring[i] ); 3463 err = TestR ( "blockin", fnvSuccess, 3464 FNV32blockin ( &eContext, 3465 (uint8_t *)teststring[i], 3466 iLen/2 ) ); 3467 if ( err ) break; 3468 err = TestR ( "stringin", fnvSuccess, 3469 FNV32stringin ( &eContext, 3470 teststring[i] + iLen/2 ) ); 3471 err = TestR ( "result", fnvSuccess, 3472 FNV32result ( &eContext, &eUint32 ) ); 3473 if ( err ) break; 3474 Test32Value ( " incremental", teststring[i], eUint32, 3475 FNV32svalues[i] ); 3477 } 3478 if ( Terr ) 3479 printf ( "%s test of return values failed %i times.0, 3480 funcName, Terr ); 3481 else 3482 printf ( "%s test of return values passed.0, funcName ); 3483 } /* end Test32 */ 3485 /* start Test32Value 3486 *****************************************************************/ 3487 void Test32Value ( char *subfunc, 3488 char *string, 3489 uint32_t should, 3490 uint32_t was ) 3491 { 3492 if ( was != should) 3493 { 3494 printf ( "%s %s of '%s' computed 0x", 3495 funcName, subfunc, string ); 3496 HexPrint ( 4, (unsigned char *)&was ); 3497 printf ( " (%i), should have been 0x", was ); 3498 HexPrint ( 4, (unsigned char *)&should ); 3499 printf ( " (%i).0, should ); 3500 ++Terr; 3501 } 3502 } /* end Test32Value */ 3504 /***************************************************************** 3505 * Code for FNV64 using 64-bit integers 3506 *****************************************************************/ 3508 void Test64 () 3509 { 3510 int i, err; 3511 uint64_t eUint64 = 42; 3512 FNV64context eContext; 3513 uint64_t FNV64svalues[NTstrings] = { 3514 0xcbf29ce484222325, 0xaf63dc4c8601ec8c, 0x85944171f73967e8 }; 3515 uint64_t FNV64bvalues[NTstrings] = { 3516 0xaf63bd4c8601b7df, 0x089be207b544f1e4, 0x34531ca7168b8f38 }; 3518 funcName = "FNV64"; 3520 /* test error checks */ 3521 Terr = 0; 3522 TestR ( "init", fnvSuccess, FNV64init (&eContext) ); 3523 TestR ( "string", fnvNull, 3524 FNV64string ( (char *)0, &eUint64 ) ); 3525 TestR ( "string", fnvNull, 3526 FNV64string ( errteststring, (uint64_t *)0 ) ); 3527 TestR ( "block", fnvNull, 3528 FNV64block ( (uint8_t *)0, 1, &eUint64 ) ); 3529 TestR ( "block", fnvBadParam, 3530 FNV64block ( errtestbytes, -1, &eUint64 ) ); 3531 TestR ( "block", fnvNull, 3532 FNV64block ( errtestbytes, 1, (uint64_t *)0 ) ); 3533 TestR ( "init", fnvNull, 3534 FNV64init ( (FNV64context *)0 ) ); 3535 TestR ( "initBasis", fnvNull, 3536 FNV64initBasis ( (FNV64context *)0, 42 ) ); 3537 TestR ( "blockin", fnvNull, 3538 FNV64blockin ( (FNV64context *)0, 3539 errtestbytes, NTestBytes ) ); 3540 TestR ( "blockin", fnvNull, 3541 FNV64blockin ( &eContext, (uint8_t *)0, 3542 NTestBytes ) ); 3543 TestR ( "blockin", fnvBadParam, 3544 FNV64blockin ( &eContext, errtestbytes, -1 ) ); 3545 eContext.Computed = FNVclobber+FNV64state; 3546 TestR ( "blockin", fnvStateError, 3547 FNV64blockin ( &eContext, errtestbytes, 3548 NTestBytes ) ); 3549 TestR ( "stringin", fnvNull, 3550 FNV64stringin ( (FNV64context *)0, errteststring ) ); 3551 TestR ( "stringin", fnvNull, 3552 FNV64stringin ( &eContext, (char *)0 ) ); 3553 TestR ( "stringin", fnvStateError, 3554 FNV64stringin ( &eContext, errteststring ) ); 3555 TestR ( "result", fnvNull, 3556 FNV64result ( (FNV64context *)0, &eUint64 ) ); 3557 TestR ( "result", fnvNull, 3558 FNV64result ( &eContext, (uint64_t *)0 ) ); 3559 TestR ( "result", fnvStateError, 3560 FNV64result ( &eContext, &eUint64 ) ); 3561 if ( Terr ) 3562 printf ( "%s test of error checks failed %i times.0, 3563 funcName, Terr ); 3564 else 3565 printf ( "%s test of error checks passed0, funcName ); 3567 /* test actual results */ 3568 Terr = 0; 3569 for ( i = 0; i < NTstrings; ++i ) 3570 { 3571 err = TestR ( "string", fnvSuccess, 3572 FNV64string ( teststring[i], &eUint64 ) ); 3573 if ( err == fnvSuccess ) 3574 Test64Value ( "string", teststring[i], eUint64, 3575 FNV64svalues[i] ); 3577 err = TestR ( "block", fnvSuccess, 3578 FNV64block ( (uint8_t *)teststring[i], 3579 (unsigned long)(strlen(teststring[i])+1), 3580 &eUint64 ) ); 3581 if ( err == fnvSuccess ) 3582 Test64Value ( "block", teststring[i], eUint64, 3583 FNV64bvalues[i] ); 3584 /* now try testing the incremental stuff */ 3585 err = TestR ( "init", fnvSuccess, FNV64init ( &eContext ) ); 3587 } 3588 if ( Terr ) 3589 printf ( "%s test of return values failed %i times.0, 3590 funcName, Terr ); 3591 else 3592 printf ( "%s test of return values passed.0, funcName ); 3593 } /* end Test64 */ 3595 /* start Test64Value 3596 *****************************************************************/ 3597 void Test64Value ( char *subfunc, 3598 char *string, 3599 uint64_t should, 3600 uint64_t was ) 3601 { 3602 if ( was != should) 3603 { 3604 printf ( "%s%s of '%s' computed %llu, should have been %llu.0, 3605 funcName, subfunc, string, was, should ); 3606 ++Terr; 3607 } 3608 } /* end Test64Value */ 3610 /***************************************************************** 3611 * Code for FNV128 using 64-bit integers 3612 *****************************************************************/ 3614 void Test128 () 3615 { 3616 //int i, err; 3617 uint8_t eUint128[FNV128size]; 3618 FNV128context eContext; 3620 funcName = "FNV128"; 3622 /* test error checks */ 3623 Terr = 0; 3624 TestR ( "init", fnvSuccess, FNV128init (&eContext) ); 3625 TestR ( "string", fnvNull, 3626 FNV128string ( (char *)0, eUint128 ) ); 3627 TestR ( "string", fnvNull, 3628 FNV128string ( errteststring, (uint8_t *)0 ) ); 3629 TestR ( "block", fnvNull, 3630 FNV128block ( (uint8_t *)0, 1, eUint128 ) ); 3631 TestR ( "block", fnvBadParam, 3632 FNV128block ( errtestbytes, -1, eUint128 ) ); 3633 TestR ( "block", fnvNull, 3634 FNV128block ( errtestbytes, 1, (uint8_t *)0 ) ); 3635 TestR ( "init", fnvNull, 3636 FNV128init ( (FNV128context *)0 ) ); 3637 TestR ( "initBasis", fnvNull, 3638 FNV128initBasis ( (FNV128context *)0, eUint128 ) ); 3639 TestR ( "blockin", fnvNull, 3640 FNV128blockin ( (FNV128context *)0, 3641 errtestbytes, NTestBytes ) ); 3642 TestR ( "blockin", fnvNull, 3643 FNV128blockin ( &eContext, (uint8_t *)0, 3644 NTestBytes ) ); 3645 TestR ( "blockin", fnvBadParam, 3646 FNV128blockin ( &eContext, errtestbytes, -1 ) ); 3647 eContext.Computed = FNVclobber+FNV128state; 3648 TestR ( "blockin", fnvStateError, 3649 FNV128blockin ( &eContext, errtestbytes, 3650 NTestBytes ) ); 3651 TestR ( "stringin", fnvNull, 3652 FNV128stringin ( (FNV128context *)0, errteststring ) ); 3653 TestR ( "stringin", fnvNull, 3654 FNV128stringin ( &eContext, (char *)0 ) ); 3655 TestR ( "stringin", fnvStateError, 3656 FNV128stringin ( &eContext, errteststring ) ); 3657 TestR ( "result", fnvNull, 3658 FNV128result ( (FNV128context *)0, eUint128 ) ); 3659 TestR ( "result", fnvNull, 3660 FNV128result ( &eContext, (uint8_t *)0 ) ); 3661 TestR ( "result", fnvStateError, 3662 FNV128result ( &eContext, eUint128 ) ); 3663 if ( Terr ) 3664 printf ( "%s test of error checks failed %i times.0, 3665 funcName, Terr ); 3666 else 3667 printf ( "%s test of error checks passed0, funcName ); 3669 /* test actual results */ 3670 Terr = 0; 3671 /* tbd */ 3672 } /* end Test128 */ 3674 /***************************************************************** 3675 * Code for FNV256 using 64-bit integers 3676 *****************************************************************/ 3678 void Test256 () 3679 { 3680 //int i, err; 3681 uint8_t eUint256[FNV256size]; 3682 FNV256context eContext; 3684 funcName = "FNV256"; 3686 /* test error checks */ 3687 Terr = 0; 3688 TestR ( "init", fnvSuccess, FNV256init (&eContext) ); 3689 TestR ( "string", fnvNull, 3690 FNV256string ( (char *)0, eUint256 ) ); 3691 TestR ( "string", fnvNull, 3692 FNV256string ( errteststring, (uint8_t *)0 ) ); 3693 TestR ( "block", fnvNull, 3694 FNV256block ( (uint8_t *)0, 1, eUint256 ) ); 3695 TestR ( "block", fnvBadParam, 3696 FNV256block ( errtestbytes, -1, eUint256 ) ); 3697 TestR ( "block", fnvNull, 3698 FNV256block ( errtestbytes, 1, (uint8_t *)0 ) ); 3699 TestR ( "init", fnvNull, 3700 FNV256init ( (FNV256context *)0 ) ); 3701 TestR ( "initBasis", fnvNull, 3702 FNV256initBasis ( (FNV256context *)0, eUint256 ) ); 3703 TestR ( "blockin", fnvNull, 3704 FNV256blockin ( (FNV256context *)0, 3705 errtestbytes, NTestBytes ) ); 3706 TestR ( "blockin", fnvNull, 3707 FNV256blockin ( &eContext, (uint8_t *)0, 3708 NTestBytes ) ); 3709 TestR ( "blockin", fnvBadParam, 3710 FNV256blockin ( &eContext, errtestbytes, -1 ) ); 3711 eContext.Computed = FNVclobber+FNV256state; 3712 TestR ( "blockin", fnvStateError, 3713 FNV256blockin ( &eContext, errtestbytes, 3714 NTestBytes ) ); 3715 TestR ( "stringin", fnvNull, 3716 FNV256stringin ( (FNV256context *)0, errteststring ) ); 3717 TestR ( "stringin", fnvNull, 3718 FNV256stringin ( &eContext, (char *)0 ) ); 3719 TestR ( "stringin", fnvStateError, 3720 FNV256stringin ( &eContext, errteststring ) ); 3721 TestR ( "result", fnvNull, 3722 FNV256result ( (FNV256context *)0, eUint256 ) ); 3723 TestR ( "result", fnvNull, 3724 FNV256result ( &eContext, (uint8_t *)0 ) ); 3726 TestR ( "result", fnvStateError, 3727 FNV256result ( &eContext, eUint256 ) ); 3728 if ( Terr ) 3729 printf ( "%s test of error checks failed %i times.0, 3730 funcName, Terr ); 3731 else 3732 printf ( "%s test of error checks passed0, funcName ); 3734 /* test actual results */ 3735 Terr = 0; 3736 /* tbd */ 3737 } /* end Test256 */ 3739 3741 7. Security Considerations 3743 This document is intended to provide convenient open source access by 3744 the Internet community to the FNV non-cryptographic hash. No 3745 assertion of suitability for cryptographic applications is made for 3746 the FNV hash algorithms. 3748 7.1 Why is FNV Non-Cryptographic? 3750 A full discussion of cryptographic hash requirements and strength is 3751 beyond the scope of this document. However, here are three 3752 characteristics of FNV that would generally be considered to make it 3753 non-cryptographic: 3755 1. Sticky State - A cryptographic hash should not have a state in 3756 which it can stick for a plausible input pattern. But, in the very 3757 unlikely event that the FNV hash variable becomes zero and the 3758 input is a sequence of zeros, the hash variable will remain at 3759 zero until there is a non-zero input byte and the final hash value 3760 will be unaffected by the length of that sequence of zero input 3761 bytes. Of course, for the common case of fixed length input, this 3762 would usually not be significant because the number of non-zero 3763 bytes would vary inversely with the number of zero bytes and for 3764 some types of input, runs of zeros do not occur. Furthermore, the 3765 inclusion of even a little unpredictable input may be sufficient 3766 to stop an adversary from inducing a zero hash variable. 3768 2. Diffusion - Every output bit of a cryptographic hash should be an 3769 equally complex function of every input bit. But it is easy to see 3770 that the least significant bit of a direct FNV hash is the XOR of 3771 the least significant bits of every input byte and does not depend 3772 on any other input bit. While more complex, the second through 3773 seventh least significant bits of an FNV hash have a similar 3774 weakness; only the top bit of the bottom byte of output, and 3775 higher order bits, depend on all input bits. If these properties 3776 are considered a problem, they can be easily fixed by XOR folding 3777 (see Section 3). 3779 3. Work Factor - Depending on intended use, it is frequently 3780 desirable that a hash function should be computationally expensive 3781 for general purpose and graphics processors since these may be 3782 profusely available through elastic cloud services or botnets. 3783 This is to slow down testing of possible inputs if the output is 3784 known. But FNV is designed to be very inexpensive on a general- 3785 purpose processor. (See Appendix A.) 3787 Nevertheless, none of the above have proven to be a problem in actual 3788 practice for the many applications of FNV. 3790 8. IANA Considerations 3792 This document requires no IANA Actions. 3794 Normative References 3796 [RFC20] - Cerf, V., "ASCII format for network interchange", STD 80, 3797 RFC 20, October 1969, . 3799 Informative References 3801 [FNV] - FNV web site: 3802 http://www.isthe.com/chongo/tech/comp/fnv/index.html 3804 [IEEE] - http://www.ieee.org 3806 [IPv6flow] - https://researchspace.auckland.ac.nz/bitstream/handle/ 3807 2292/13240/flowhashRep.pdf 3809 [RFC2460] - Deering, S. and R. Hinden, "Internet Protocol, Version 6 3810 (IPv6) Specification", RFC 2460, December 1998, 3811 . 3813 [RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm 3814 1 (SHA1)", RFC 3174, September 2001. 3816 [RFC6194] - Polk, T., Chen, L., Turner, S., and P. Hoffman, "Security 3817 Considerations for the SHA-0 and SHA-1 Message-Digest 3818 Algorithms", RFC 6194, March 2011. 3820 [RFC6234] - Eastlake 3rd, D. and T. Hansen, "US Secure Hash 3821 Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 3822 2011. 3824 [RFC6437] - Amante, S., Carpenter, B., Jiang, S., and J. Rajahalme, 3825 "IPv6 Flow Label Specification", RFC 6437, November 2011, 3826 . 3828 Acknowledgements 3830 The contributions of the following are gratefully acknowledged: 3832 Frank Ellermann, Tony Finch, Bob Moskowitz, Gayle Noble, and 3833 Stefan Santesson. 3835 Appendix A: Work Comparison with SHA-1 3837 This section provides a simplistic rough comparison of the level of 3838 effort required per input byte to compute FNV-1a and SHA-1 [RFC3174]. 3840 Ignoring transfer of control and conditional tests and equating all 3841 logical and arithmetic operations, FNV requires 2 operations per 3842 byte, an XOR and a multiply. 3844 SHA-1 is a relatively weak cryptographic hash producing a 160-bit 3845 hash. It that has been partially broken [RFC6194]. It is actually 3846 designed to accept a bit vector input although almost all computer 3847 uses apply it to an integer number of bytes. It processes blocks of 3848 512 bits (64 bytes) and we estimate the effort involved in SHA-1 3849 processing a full block. Ignoring SHA-1 initial set up, transfer of 3850 control, and conditional tests, but counting all logical and 3851 arithmetic operations, including counting indexing as an addition, 3852 SHA-1 requires 1,744 operations per 64 bytes block or 27.25 3853 operations per byte. So by this rough measure, it is a little over 13 3854 times the effort of FNV for large amounts of data. However, FNV is 3855 commonly used for small inputs. Using the above method, for inputs of 3856 N bytes, where N is <= 55 so SHA-1 will take one block (SHA-1 3857 includes padding and an 8-byte length at the end of the data in the 3858 last block), the ratio of the effort for SHA-1 to the effort for FNV 3859 will be 872/N. For example, with an 8 byte input, SHA-1 will take 109 3860 times as much effort as FNV. 3862 Stronger cryptographic functions than SHA-1 generally have an even 3863 high work factor. 3865 Appendix B: Previous IETF Reference to FNV 3867 FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has 3868 since expired. It was later decided that it would be better to use a 3869 cryptographic hash for that application. 3871 Below is the Java code for FNV64 from that TLS draft include by the 3872 kind permission of the author: 3874 3875 /** 3876 * Java code sample, implementing 64 bit FNV-1a 3877 * By Stefan Santesson 3878 */ 3880 import java.math.BigInteger; 3882 public class FNV { 3884 static public BigInteger getFNV1aToByte(byte[] inp) { 3886 BigInteger m = new BigInteger("2").pow(64); 3887 BigInteger fnvPrime = new BigInteger("1099511628211"); 3888 BigInteger fnvOffsetBasis = 3889 new BigInteger("14695981039346656037"); 3891 BigInteger digest = fnvOffsetBasis; 3893 for (byte b : inp) { 3894 digest = digest.xor(BigInteger.valueOf((int) b & 255)); 3895 digest = digest.multiply(fnvPrime).mod(m); 3896 } 3897 return digest; 3899 } 3900 } 3901 3903 Appendix Z: Change Summary 3905 RFC Editor Note: Please delete this appendix on publication. 3907 From -00 to -01 3909 1. Add Security Considerations section on why FNV is non- 3910 cryptographic. 3912 2. Add Appendix A on a work factor comparison with SHA-1. 3914 3. Add Appendix B concerning previous IETF draft referenced to FNV. 3916 4. Minor editorial changes. 3918 From -01 to -02 3920 1. Correct FNV_Prime determination criteria and add note as to why s 3921 < 5 and s > 10 are not considered. 3923 2. Add acknowledgements list. 3925 3. Add a couple of references. 3927 4. Minor editorial changes. 3929 From -02 to -03 3931 1. Replace direct reference to US-ASCII standard with reference to 3932 RFC 20. 3934 2. Update dates and version number. 3936 3. Minor editing changes. 3938 From -03 to -04 3940 1. Change reference to RFC 20 back to a reference to the ANSI 1968 3941 ASCII standard. 3943 2. Minor addition to Section 6, point 3. 3945 3. Update dates and version number. 3947 4. Minor editing changes. 3949 From -04 to -05 3951 1. Add Twitter as a use example and IPv6 flow hash study reference. 3953 2. Update dates and version number. 3955 From -05 to -06 3957 1. Add code subsections. 3959 2. Update dates and version number. 3961 From -06 to -07 to -08 3963 1. Update Author info. 3965 2. Minor edits. 3967 From -08 to -09 3969 1. Change reference for ASCII to [RFC20]. 3971 2. Add more details on history of the string used to compute 3972 offset_basis. 3974 3. Re-write "Work Factor" part of Section 6 to be more precise. 3976 4. Minor editorial changes. 3978 From -09 to -10 3980 1. Inclusion of initial partial version of code and some 3981 documentation about the code, Section 6. 3983 2. Insertion of new Section 4 on hashing values. 3985 Author's Address 3987 Glenn Fowler 3988 Google 3990 Email: glenn.s.fowler@gmail.com 3992 Landon Curt Noll 3993 Cisco Systems 3994 170 West Tasman Drive 3995 San Jose, CA 95134 USA 3997 Telephone: +1-408-424-1102 3998 Email: fnv-ietf2-mail@asthe.com 3999 URL: http://www.isthe.com/chongo/index.html 4001 Kiem-Phong Vo 4002 Google 4004 Email: phongvo@gmail.com 4006 Donald Eastlake 4007 Huawei Technologies 4008 155 Beaver Street 4009 Milford, MA 01757 USA 4011 Telephone: +1-508-333-2270 4012 EMail: d3e3e3@gmail.com 4014 Copyright, Disclaimer, and Additional IPR Provisions 4016 Copyright (c) 2015 IETF Trust and the persons identified as the 4017 document authors. All rights reserved. 4019 This document is subject to BCP 78 and the IETF Trust's Legal 4020 Provisions Relating to IETF Documents 4021 (http://trustee.ietf.org/license-info) in effect on the date of 4022 publication of this document. Please review these documents 4023 carefully, as they describe your rights and restrictions with respect 4024 to this document. Code Components extracted from this document must 4025 include Simplified BSD License text as described in Section 4.e of 4026 the Trust Legal Provisions and are provided without warranty as 4027 described in the Simplified BSD License. This Internet-Draft is 4028 submitted to IETF in full conformance with the provisions of BCP 78 4029 and BCP 79.