cpan

Digest::SipHash というモジュールをリリースしたのでおしらせします。

なにこれ?

SipHashというハッシュ関数を実装したものです。

SipHash: a fast short-input PRF
SipHash is a family of pseudorandom functions (a.k.a. keyed hash functions) optimized for speed on short messages. Target applications include network traffic authentication and defense against hash-flooding DoS attacks.
Users of SipHash already include OpenDNS, Perl 5, Ruby, or Rust.

見ての通り、「Perl 5でも使っている」とあります。

厳密には、perl-currentでかつ64-bitの場合です。

perl5.git.perl.org Git - perl.git/commit
Switch default hash to SIPHASH on 64 bit builds and ONE_AT_A_TIME on 32 bit builds

ソースを見たところ、現時点では hv.h をちょっと修正して #define PERL_HASH_FUNC_SIPHASH しなければならないみたいでしたが、とにもかくにもそうして build したperl-current はこんな感じになります。

% env PERL_HASH_SEED=0 PERL_HASH_SEED_DEBUG=1 \
  ~/perl-current/bin/perl5.17.9 \
  -Mblib -MDigest::SipHash=siphash \
  -MHash::Util=hash_seed,hash_value \
  -E 'my $str=shift; my $hv=hash_value($str);' \
  -E 'my $ds=siphash($str,hash_seed()); say sprintf "0x%08x",$_ for $hv,$ds' \
  dankogai
HASH_FUNCTION = SIPHASH HASH_SEED = 0x00000000000000000000000000000000
0xf02f628b
0xf02f628b
%

で、ハッシュ関数だけ抜き出したので、それより前のPerlでも試せるというわけです。

use v5.14;
use Digest::SipHash qw/:all/;
my $str = 'dankogai';
for my $seed ($Digest::SipHash::DEFAULT_SEED, "\x0" x 16) {
    my $u32 = siphash32($str, $seed);
    my $u64 = siphash64($str, $seed);
    say "seed = 0x", map { sprintf "%02x", $_ } unpack 'C*', $seed;
    say sprintf "    siphash32 = %08x", $u32;
    say sprintf "    siphash64 = %016x", $u64;
}

で、共著者の言い分。

http://cr.yp.to/talks/2012.12.12/slides.pdf
My favorite solution: switch from hash tables to crit-bit trees. Guaranteed high speed + extra lookup features such as "find next entry after x."
But hash tables are perceived as being smaller, faster, simpler than other data structures. Can we protect hash tables?

「ハッシュテーブルやめて crit-bit tree 使えばいいのに。でも相変わらずハッシュテーブルの方が小さくて高速で簡素だと思われてる。ハッシュテーブルを魔の手から救えるか?」

djbぶれねえ。

確かにPerlのハッシュテーブルを crit-bit tree にとっかえるのはおおごとだけど、ハッシュ関数とっかえるだけならずっと楽ではあります(perl-currentの実装なんとhv.h内のマクロ)。

現状XSのみです。しかもmajek/csiphash ・ GitHubからC成分をまるっと持って来てます。64bitなPerlのみで動くようにするのは「直訳」でよいのですが、32bit互換となるとちちょっとめんどいので。

Enjoy!

P.S. Pure Perl 版も追加したので、胴元に報告したところ本家ページにも掲載。

Dan the Perl Monger