| 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 | 2 | ▶ | BEGIN { |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 25 | 2 | $VERSION = 0.02; | |
| 26 | 2 | @ISA = qw(Exporter); | |
| 27 | 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 | |||
| 29 | 2 | require Exporter; | |
| 30 | 2 | Exporter::export_ok_tags(keys %EXPORT_TAGS); | |
| 31 | |||
| 32 | 2 | require XSLoader; | |
| 33 | 2 | 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 | 2 | 1 | |
| 140 | |||