Revision: | 1.1 |

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

Branch: | MAIN |

CVS Tags: | rel-0_02, HEAD |

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

# | Content |
---|---|

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 |