Revision: | 1.1 |

Committed: | Thu Oct 29 11:06:58 2015 UTC (8 years, 10 months ago) by root |

Branch: | MAIN |

CVS Tags: | rel-0_02, HEAD |

Log Message: | *** empty log message *** |

# | User | Rev | Content |
---|---|---|---|

1 | root | 1.1 | NAME |

2 | Digest::FNV::XS - Fowler/Noll/Vo (FNV) hashes | ||

3 | |||

4 | SYNOPSIS | ||

5 | use Digest::FNV::XS; # nothing exported by default | ||

6 | |||

7 | DESCRIPTION | ||

8 | This module is more or less a faster version of Digest::FNV, that | ||

9 | additionally supports binary data, incremental hashing, more FNV | ||

10 | variants and more. The API isn't compatible (and neither are the | ||

11 | generated hash values. The hash values computed by this module match the | ||

12 | official FNV hash values as documented on | ||

13 | <http://www.isthe.com/chongo/tech/comp/fnv/>). | ||

14 | |||

15 | $hash = Digest::FNV::XS::fnv1a_32 $data[, $init] | ||

16 | $hash = Digest::FNV::XS::fnv1a_64 $data[, $init] | ||

17 | Compute the 32 or 64 bit FNV-1a hash of the given string. | ||

18 | |||

19 | $init is the optional initialisation value, allowing incremental | ||

20 | hashing. If missing or "undef" then the appropriate FNV constant is | ||

21 | used. | ||

22 | |||

23 | The 64 bit variant is only available when perl was compiled with 64 | ||

24 | bit support. | ||

25 | |||

26 | The FNV-1a algorithm is the preferred variant, as it has slightly | ||

27 | higher quality and speed then FNV-1. | ||

28 | |||

29 | $hash = Digest::FNV::XS::fnv1_32 $data[, $init] | ||

30 | $hash = Digest::FNV::XS::fnv1_64 $data[, $init] | ||

31 | Compute the 32 or 64 bit FNV-1 hash of the given string. | ||

32 | |||

33 | $init is the optional initialisation value, allowing incremental | ||

34 | hashing. If missing or "undef" then the appropriate FNV constant is | ||

35 | used. | ||

36 | |||

37 | The 64 bit variant is only available when perl was compiled with 64 | ||

38 | bit support. | ||

39 | |||

40 | The FNV-1a variant is preferable if you can choose. | ||

41 | |||

42 | $hash = Digest::FNV::XS::fnv0_32 $data[, $init] | ||

43 | $hash = Digest::FNV::XS::fnv0_64 $data[, $init] | ||

44 | The obsolete FNV-0 algorithm. Same as calling the FNV1 variant with | ||

45 | "$init = 0". | ||

46 | |||

47 | $init is the optional initialisation value, allowing incremental | ||

48 | hashing. If missing or "undef" then the appropriate FNV constant is | ||

49 | used. | ||

50 | |||

51 | The 64 bit variant is only available when perl was compiled with 64 | ||

52 | bit support. | ||

53 | |||

54 | $hash = Digest::FNV::XS::xorfold_32 $hash, $bits | ||

55 | $hash = Digest::FNV::XS::xorfold_64 $hash, $bits | ||

56 | XOR-folds the 32 (64) bit FNV hash to $bits bits, which can be any | ||

57 | value between 1 and 32 (64) inclusive. | ||

58 | |||

59 | XOR-folding is a good method to reduce the FNV hash to a power of | ||

60 | two range. | ||

61 | |||

62 | $hash = Digest::FNV::XS::reduce_32 $hash, $range | ||

63 | $hash = Digest::FNV::XS::reduce_64 $hash, $range | ||

64 | These two functions can be used to reduce a 32 (64) but FNV hash to | ||

65 | an integer in the range 0 .. $range, using the retry method, which | ||

66 | distributes any bias more evenly. | ||

67 | |||

68 | INCREMENTAL HASHING | ||

69 | You can hash data incrementally by feeding the previous hahs value as | ||

70 | $init argument for the next call, for example: | ||

71 | |||

72 | $hash = fnv1a_32 $data1; | ||

73 | $hash = fnv1a_32 $data2, $hash; # and so on | ||

74 | |||

75 | Or in a loop (relying on the fact that $hash is "undef" initially): | ||

76 | |||

77 | my $hash; | ||

78 | $hash = fnv1a_32 $_, $hash | ||

79 | for ...; | ||

80 | |||

81 | REDUCIDNG THE HASH VALUE | ||

82 | A common problem is to reduce the 32 (64) bit FNV hash value to a | ||

83 | smaller range, 0 .. $range. | ||

84 | |||

85 | The easiest method to do that, is to mask (For power of two) or modulo | ||

86 | (for other values) the hash value, i.e.: | ||

87 | |||

88 | $inrage = $hash & ($range - 1) # for $range values that are power of two | ||

89 | $inrage = $hash % $range # for any range | ||

90 | |||

91 | This is called the lazy mod mapping method, which creates small biases | ||

92 | that rarely cause any problems in practise. | ||

93 | |||

94 | Nevertheless, you can improve the distribution of the bias by using *XOR | ||

95 | folding*, for power of two ranges (and 32 bit hashews, there is also | ||

96 | "forfold_64") | ||

97 | |||

98 | $inrage = Digest::FNV::XS::xorfold_32 $hash, $log2_of_range | ||

99 | |||

100 | And, using the retry method, for generic ranges (and 32 bit hashes, | ||

101 | there is also "reduce_64"): | ||

102 | |||

103 | $inrange = Digest::FNX::XS::reduce_32 $hash, $range | ||

104 | |||

105 | AUTHOR | ||

106 | Marc Lehmann <schmorp@schmorp.de> | ||

107 | http://software.schmorp.de/pkg/Digest-FNV-XS.html | ||

108 |