1 |
=head1 NAME |
2 |
|
3 |
Digest::FNV::XS - Fowler/Noll/Vo (FNV) hashes |
4 |
|
5 |
=head1 SYNOPSIS |
6 |
|
7 |
use Digest::FNV::XS; # nothing exported by default |
8 |
|
9 |
=head1 DESCRIPTION |
10 |
|
11 |
This module is more or less a faster version of L<Digest::FNV>, |
12 |
that additionally supports binary data, incremental hashing, |
13 |
more FNV variants and more. The API isn't compatible (and |
14 |
neither are the generated hash values. The hash values computed by |
15 |
this module match the official FNV hash values as documented on |
16 |
L<http://www.isthe.com/chongo/tech/comp/fnv/>). |
17 |
|
18 |
=over 4 |
19 |
|
20 |
=cut |
21 |
|
22 |
package Digest::FNV::XS; |
23 |
|
24 |
BEGIN { |
25 |
$VERSION = 0.02; |
26 |
@ISA = qw(Exporter); |
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 |
|
29 |
require Exporter; |
30 |
Exporter::export_ok_tags(keys %EXPORT_TAGS); |
31 |
|
32 |
require XSLoader; |
33 |
XSLoader::load Digest::FNV::XS, $VERSION; |
34 |
} |
35 |
|
36 |
=item $hash = Digest::FNV::XS::fnv1a_32 $data[, $init] |
37 |
|
38 |
=item $hash = Digest::FNV::XS::fnv1a_64 $data[, $init] |
39 |
|
40 |
Compute the 32 or 64 bit FNV-1a hash of the given string. |
41 |
|
42 |
C<$init> is the optional initialisation value, allowing incremental |
43 |
hashing. If missing or C<undef> then the appropriate FNV constant is used. |
44 |
|
45 |
The 64 bit variant is only available when perl was compiled with 64 bit support. |
46 |
|
47 |
The FNV-1a algorithm is the preferred variant, as it has slightly higher |
48 |
quality and speed then FNV-1. |
49 |
|
50 |
=item $hash = Digest::FNV::XS::fnv1_32 $data[, $init] |
51 |
|
52 |
=item $hash = Digest::FNV::XS::fnv1_64 $data[, $init] |
53 |
|
54 |
Compute the 32 or 64 bit FNV-1 hash of the given string. |
55 |
|
56 |
C<$init> is the optional initialisation value, allowing incremental |
57 |
hashing. If missing or C<undef> then the appropriate FNV constant is used. |
58 |
|
59 |
The 64 bit variant is only available when perl was compiled with 64 bit support. |
60 |
|
61 |
The FNV-1a variant is preferable if you can choose. |
62 |
|
63 |
=item $hash = Digest::FNV::XS::fnv0_32 $data[, $init] |
64 |
|
65 |
=item $hash = Digest::FNV::XS::fnv0_64 $data[, $init] |
66 |
|
67 |
The obsolete FNV-0 algorithm. Same as calling the FNV1 variant with C<$init = 0>. |
68 |
|
69 |
C<$init> is the optional initialisation value, allowing incremental |
70 |
hashing. If missing or C<undef> then the appropriate FNV constant is used. |
71 |
|
72 |
The 64 bit variant is only available when perl was compiled with 64 bit support. |
73 |
|
74 |
=item $hash = Digest::FNV::XS::xorfold_32 $hash, $bits |
75 |
|
76 |
=item $hash = Digest::FNV::XS::xorfold_64 $hash, $bits |
77 |
|
78 |
XOR-folds the 32 (64) bit FNV hash to C<$bits> bits, which can be any |
79 |
value between 1 and 32 (64) inclusive. |
80 |
|
81 |
XOR-folding is a good method to reduce the FNV hash to a power of two range. |
82 |
|
83 |
=item $hash = Digest::FNV::XS::reduce_32 $hash, $range |
84 |
|
85 |
=item $hash = Digest::FNV::XS::reduce_64 $hash, $range |
86 |
|
87 |
These two functions can be used to reduce a 32 (64) but FNV hash to |
88 |
an integer in the range 0 .. C<$range>, using the retry method, which |
89 |
distributes any bias more evenly. |
90 |
|
91 |
=back |
92 |
|
93 |
=head2 INCREMENTAL HASHING |
94 |
|
95 |
You can hash data incrementally by feeding the previous hahs value as |
96 |
C<$init> argument for the next call, for example: |
97 |
|
98 |
$hash = fnv1a_32 $data1; |
99 |
$hash = fnv1a_32 $data2, $hash; # and so on |
100 |
|
101 |
Or in a loop (relying on the fact that C<$hash> is C<undef> initially): |
102 |
|
103 |
my $hash; |
104 |
$hash = fnv1a_32 $_, $hash |
105 |
for ...; |
106 |
|
107 |
=head2 REDUCIDNG THE HASH VALUE |
108 |
|
109 |
A common problem is to reduce the 32 (64) bit FNV hash value to a smaller range, |
110 |
0 .. C<$range>. |
111 |
|
112 |
The 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 |
|
118 |
This is called the lazy mod mapping method, which creates small biases that rarely |
119 |
cause any problems in practise. |
120 |
|
121 |
Nevertheless, you can improve the distribution of the bias by using |
122 |
I<XOR folding>, for power of two ranges (and 32 bit hashews, there is also |
123 |
C<forfold_64>) |
124 |
|
125 |
$inrage = Digest::FNV::XS::xorfold_32 $hash, $log2_of_range |
126 |
|
127 |
And, using the retry method, for generic ranges (and 32 bit hashes, there |
128 |
is also C<reduce_64>): |
129 |
|
130 |
$inrange = Digest::FNX::XS::reduce_32 $hash, $range |
131 |
|
132 |
=head1 AUTHOR |
133 |
|
134 |
Marc Lehmann <schmorp@schmorp.de> |
135 |
http://software.schmorp.de/pkg/Digest-FNV-XS.html |
136 |
|
137 |
=cut |
138 |
|
139 |
1 |
140 |
|