[ViewVC] Annotation of: cvs/Digest-FNV-XS/README

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

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

DESCRIPTION
    This module is more or less a faster version of 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
    <http://www.isthe.com/chongo/tech/comp/fnv/>).

    $hash = Digest::FNV::XS::fnv1a_32 $data[, $init]
    $hash = Digest::FNV::XS::fnv1a_64 $data[, $init]
        Compute the 32 or 64 bit FNV-1a hash of the given string.

        $init is the optional initialisation value, allowing incremental
        hashing. If missing or "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.

    $hash = Digest::FNV::XS::fnv1_32 $data[, $init]
    $hash = Digest::FNV::XS::fnv1_64 $data[, $init]
        Compute the 32 or 64 bit FNV-1 hash of the given string.

        $init is the optional initialisation value, allowing incremental
        hashing. If missing or "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.

    $hash = Digest::FNV::XS::fnv0_32 $data[, $init]
    $hash = Digest::FNV::XS::fnv0_64 $data[, $init]
        The obsolete FNV-0 algorithm. Same as calling the FNV1 variant with
        "$init = 0".

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

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

    $hash = Digest::FNV::XS::xorfold_32 $hash, $bits
    $hash = Digest::FNV::XS::xorfold_64 $hash, $bits
        XOR-folds the 32 (64) bit FNV hash to $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.

    $hash = Digest::FNV::XS::reduce_32 $hash, $range
    $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 .. $range, using the retry method, which
        distributes any bias more evenly.

  INCREMENTAL HASHING
    You can hash data incrementally by feeding the previous hahs value as
    $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 $hash is "undef" initially):

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

  REDUCING THE HASH VALUE
    A common problem is to reduce the 32 (64) bit FNV hash value to a
    smaller range, 0 .. $range.

    The easiest method to do that, is to mask (for a 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 *XOR
    folding*, for power of two ranges (and 32 bit hashes - there is also
    "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 "reduce_64"):

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

  WHAT IS A 64-BIT PERL?
    What I call a 64-bit perl is a perl binary that was compiled to support
    64-bit integers as scalars. Practically every Perl interpreter you will
    use will be of this type, even on 32-bit machines, so you can use the
    64-bit functions without a second thought.

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

Revision:	1.2
Committed:	Tue Dec 24 09:51:22 2024 UTC (20 months, 2 weeks ago) by root
Branch:	MAIN
CVS Tags:	rel-1_0, HEAD
Changes since 1.1:	+11 -5 lines
Log Message:	1.0
#	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	root	1.2	These two functions can be used to reduce a 32 (64) bit FNV hash to
65	root	1.1	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	root	1.2	REDUCING THE HASH VALUE
82	root	1.1	A common problem is to reduce the 32 (64) bit FNV hash value to a
83			smaller range, 0 .. $range.
84
85	root	1.2	The easiest method to do that, is to mask (for a power of two) or modulo
86	root	1.1	(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	root	1.2	folding*, for power of two ranges (and 32 bit hashes - there is also
96	root	1.1	"forfold_64")
97
98			$inrage = Digest::FNV::XS::xorfold_32 $hash, $log2_of_range
99
100	root	1.2	And, using the retry method, for generic ranges (and 32 bit hashes -
101	root	1.1	there is also "reduce_64"):
102
103			$inrange = Digest::FNX::XS::reduce_32 $hash, $range
104
105	root	1.2	WHAT IS A 64-BIT PERL?
106			What I call a 64-bit perl is a perl binary that was compiled to support
107			64-bit integers as scalars. Practically every Perl interpreter you will
108			use will be of this type, even on 32-bit machines, so you can use the
109			64-bit functions without a second thought.
110
111	root	1.1	AUTHOR
112			Marc Lehmann <schmorp@schmorp.de>
113			http://software.schmorp.de/pkg/Digest-FNV-XS.html
114