Digest-FNV-XS/XS.pm

=head1 NAME

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

=head1 SYNOPSIS

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

=head1 DESCRIPTION

This module is more or less a faster version of L<Digest::FNV>,
that additionally supports binary data, incremental hashing,
more FNV variants and more. The API isn't compatible (and
neither are the generated hash values. The hash values computed by
this module match the official FNV hash values as documented on
L<http://www.isthe.com/chongo/tech/comp/fnv/>).

=over 4

=cut

package Digest::FNV::XS;

BEGIN {
   $VERSION = 0.02;
   @ISA = qw(Exporter);
   @EXPORT_OK = qw(fnv0_32 fnv0_64 fnv1_32 fnv1a_32 fnv1_64 fnv1a_64 xorfold_32 xorfold_64 reduce_32 reduce_64);

   require Exporter;
   Exporter::export_ok_tags(keys %EXPORT_TAGS);

   require XSLoader;
   XSLoader::load Digest::FNV::XS, $VERSION;
}

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

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

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

C<$init> is the optional initialisation value, allowing incremental
hashing. If missing or C<undef> then the appropriate FNV constant is used.

The 64 bit variant is only available when perl was compiled with 64 bit support.

The FNV-1a algorithm is the preferred variant, as it has slightly higher
quality and speed then FNV-1.

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

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

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

C<$init> is the optional initialisation value, allowing incremental
hashing. If missing or C<undef> then the appropriate FNV constant is used.

The 64 bit variant is only available when perl was compiled with 64 bit support.

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

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

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

The obsolete FNV-0 algorithm. Same as calling the FNV1 variant with C<$init = 0>.

C<$init> is the optional initialisation value, allowing incremental
hashing. If missing or C<undef> then the appropriate FNV constant is used.

The 64 bit variant is only available when perl was compiled with 64 bit support.

=item $hash = Digest::FNV::XS::xorfold_32 $hash, $bits

=item $hash = Digest::FNV::XS::xorfold_64 $hash, $bits

XOR-folds the 32 (64) bit FNV hash to C<$bits> bits, which can be any
value between 1 and 32 (64) inclusive.

XOR-folding is a good method to reduce the FNV hash to a power of two range.

=item $hash = Digest::FNV::XS::reduce_32 $hash, $range

=item $hash = Digest::FNV::XS::reduce_64 $hash, $range

These two functions can be used to reduce a 32 (64) bit FNV hash to
an integer in the range 0 .. C<$range>, using the retry method, which
distributes any bias more evenly.

=back

=head2 INCREMENTAL HASHING

You can hash data incrementally by feeding the previous hahs value as
C<$init> argument for the next call, for example:

   $hash = fnv1a_32 $data1;
   $hash = fnv1a_32 $data2, $hash; # and so on

Or in a loop (relying on the fact that C<$hash> is C<undef> initially):

   my $hash;
   $hash = fnv1a_32 $_, $hash
      for ...;

=head2 REDUCIDNG THE HASH VALUE

A common problem is to reduce the 32 (64) bit FNV hash value to a smaller range,
0 .. C<$range>.

The easiest method to do that, is to mask (For power of two) or modulo
(for other values) the hash value, i.e.:

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

This is called the lazy mod mapping method, which creates small biases that rarely
cause any problems in practise.

Nevertheless, you can improve the distribution of the bias by using
I<XOR folding>, for power of two ranges (and 32 bit hashews, there is also
C<forfold_64>)

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

And, using the retry method, for generic ranges (and 32 bit hashes, there
is also C<reduce_64>):

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

=head1 AUTHOR

 Marc Lehmann <schmorp@schmorp.de>
 http://software.schmorp.de/pkg/Digest-FNV-XS.html

=cut

1

Revision:	1.3
Committed:	Wed Jun 28 01:09:04 2017 UTC (7 years, 2 months ago) by root
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.2:	+1 -1 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.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	root	1.2	more FNV variants and more. The API isn't compatible (and
14	root	1.1	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	root	1.2	$VERSION = 0.02;
26	root	1.1	@ISA = qw(Exporter);
27	root	1.2	@EXPORT_OK = qw(fnv0_32 fnv0_64 fnv1_32 fnv1a_32 fnv1_64 fnv1a_64 xorfold_32 xorfold_64 reduce_32 reduce_64);
28	root	1.1
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	root	1.2	XOR-folding is a good method to reduce the FNV hash to a power of two range.
82	root	1.1
83			=item $hash = Digest::FNV::XS::reduce_32 $hash, $range
84
85			=item $hash = Digest::FNV::XS::reduce_64 $hash, $range
86
87	root	1.3	These two functions can be used to reduce a 32 (64) bit FNV hash to
88	root	1.2	an integer in the range 0 .. C<$range>, using the retry method, which
89			distributes any bias more evenly.
90	root	1.1
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	root	1.2	=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	root	1.1	=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