ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/Digest-FNV-XS/XS.pm
(Generate patch)

Comparing Digest-FNV-XS/XS.pm (file contents):
Revision 1.1 by root, Thu Oct 29 10:56:00 2015 UTC vs.
Revision 1.2 by root, Thu Oct 29 11:06:39 2015 UTC

… …
8 8
9=head1 DESCRIPTION 9=head1 DESCRIPTION
10 10
11This module is more or less a faster version of L<Digest::FNV>, 11This module is more or less a faster version of L<Digest::FNV>,
12that additionally supports binary data, incremental hashing, 12that additionally supports binary data, incremental hashing,
13more FNV variants and xorfolding. The API isn't compatible (and 13more FNV variants and more. The API isn't compatible (and
14neither are the generated hash values. The hash values computed by 14neither are the generated hash values. The hash values computed by
15this module match the official FNV hash values as documented on 15this module match the official FNV hash values as documented on
16L<http://www.isthe.com/chongo/tech/comp/fnv/>). 16L<http://www.isthe.com/chongo/tech/comp/fnv/>).
17 17
18=over 4 18=over 4
… …
20=cut 20=cut
21 21
22package Digest::FNV::XS; 22package Digest::FNV::XS;
23 23
24BEGIN { 24BEGIN {
25 $VERSION = 0.01; 25 $VERSION = 0.02;
26 @ISA = qw(Exporter); 26 @ISA = qw(Exporter);
27 @EXPORT_OK = qw(fnv0_32 fnv0_64 fnv1_32 fnv1a_32 fnv1_64 fnv1a_64); 27 @EXPORT_OK = qw(fnv0_32 fnv0_64 fnv1_32 fnv1a_32 fnv1_64 fnv1a_64 xorfold_32 xorfold_64 reduce_32 reduce_64);
28 28
29 require Exporter; 29 require Exporter;
30 Exporter::export_ok_tags(keys %EXPORT_TAGS); 30 Exporter::export_ok_tags(keys %EXPORT_TAGS);
31 31
32 require XSLoader; 32 require XSLoader;
… …
76=item $hash = Digest::FNV::XS::xorfold_64 $hash, $bits 76=item $hash = Digest::FNV::XS::xorfold_64 $hash, $bits
77 77
78XOR-folds the 32 (64) bit FNV hash to C<$bits> bits, which can be any 78XOR-folds the 32 (64) bit FNV hash to C<$bits> bits, which can be any
79value between 1 and 32 (64) inclusive. 79value between 1 and 32 (64) inclusive.
80 80
81XOR-folding is a good method to reduce the FNV hash to a power of two. 81XOR-folding is a good method to reduce the FNV hash to a power of two range.
82 82
83=item $hash = Digest::FNV::XS::reduce_32 $hash, $range 83=item $hash = Digest::FNV::XS::reduce_32 $hash, $range
84 84
85=item $hash = Digest::FNV::XS::reduce_64 $hash, $range 85=item $hash = Digest::FNV::XS::reduce_64 $hash, $range
86 86
87When you want to reduce a FNV hash value to a rnage that is not a power of 87These two functions can be used to reduce a 32 (64) but FNV hash to
88two, you can simply calculate C<$hash % $range>, which creates slightly 88an integer in the range 0 .. C<$range>, using the retry method, which
89biased distribution which nevertheless is completely adequate for many 89distributes any bias more evenly.
90applications, especially for small C<$range>.
91
92When a bias is not acceptable, then these two functions can be used to
93reduce a 32 (64) but FNV hash to an integer in the range 0 .. C<$range>,
94with reduced or nonexistent bias.
95
96The disadvantage of these functions is that they are slower (and in fact,
97have unbounded runtime), although in practise the speed difference in a
98Perl program should be negligible.
99 90
100=back 91=back
101 92
102=head2 INCREMENTAL HASHING 93=head2 INCREMENTAL HASHING
103 94
… …
111 102
112 my $hash; 103 my $hash;
113 $hash = fnv1a_32 $_, $hash 104 $hash = fnv1a_32 $_, $hash
114 for ...; 105 for ...;
115 106
107=head2 REDUCIDNG THE HASH VALUE
108
109A common problem is to reduce the 32 (64) bit FNV hash value to a smaller range,
1100 .. C<$range>.
111
112The easiest method to do that, is to mask (For power of two) or modulo
113(for other values) the hash value, i.e.:
114
115 $inrage = $hash & ($range - 1) # for $range values that are power of two
116 $inrage = $hash % $range # for any range
117
118This is called the lazy mod mapping method, which creates small biases that rarely
119cause any problems in practise.
120
121Nevertheless, you can improve the distribution of the bias by using
122I<XOR folding>, for power of two ranges (and 32 bit hashews, there is also
123C<forfold_64>)
124
125 $inrage = Digest::FNV::XS::xorfold_32 $hash, $log2_of_range
126
127And, using the retry method, for generic ranges (and 32 bit hashes, there
128is also C<reduce_64>):
129
130 $inrange = Digest::FNX::XS::reduce_32 $hash, $range
131
116=head1 AUTHOR 132=head1 AUTHOR
117 133
118 Marc Lehmann <schmorp@schmorp.de> 134 Marc Lehmann <schmorp@schmorp.de>
119 http://software.schmorp.de/pkg/Digest-FNV-XS.html 135 http://software.schmorp.de/pkg/Digest-FNV-XS.html
120 136

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines