__collisionsTest__は、総当たり方式のハッシュ解析ツールです。数十億個のハッシュを生成し、その結果を「理想的な」目標と比較することで、64ビットハッシュアルゴリズムの衝突率を測定します。

このテストには非常に大量のメモリが必要です。既定では240億個の64ビットハッシュを生成し、その保存に__192 GBのRAM__を必要とします。ハッシュ数は--nbh=コマンドで変更できます。64ビットハッシュの衝突率を意味のある形で測定するには、非常に大量（数十億個）のハッシュが必要であることに注意してください。

RAM使用量を減らすには、任意指定のフィルターを--filterで有効にできます。解析する候補数を減らし、それに伴って必要なRAMも減らします。ただし、フィルター自体も大量のRAMを必要とします。既定では32 GBで、--filterlog=で変更できます。フィルターが小さすぎると効率が悪くなるため、ハッシュ1個当たり約2バイトを目安にしてください。また、フィルターの読み書きに相当量のCPU処理が必要となるため、この方法は遅くなります。大半のハッシュを破棄して保存しないので、一部のビットフィールドに対する高度な解析もできません。

フィルターを使う場合、必要なRAMはフィルターと候補一覧の分になります。候補一覧は、元のハッシュ一覧の一部です。既定の設定（240億個のハッシュ、32 GBのフィルター）では、潜在的な候補数は20億個未満に減り、保存に約14 GBを必要とするはずです。この結果はハッシュアルゴリズムの効率にも依存します。実際の候補数は約10億個とさらに少なくなる可能性がありますが、保存領域は上限に合わせて確保しなければなりません。

既定のテストで、64ビットハッシュ関数に期待される「最適な」衝突率は、衝突約18回です。

ビルド方法

make

注：コードにはC99とC++14が混在しており、C90だけに対応するコンパイラーでは使えません。

ビルドの調整

• SLAB5：弱いハッシュアルゴリズムに適した別のパターン生成器を使います。
• POOL_MT：=0の場合、マルチスレッドのコードを無効にします（既定では有効）。

任意のハッシュをテスターに組み込む方法

ビルドスクリプトは、./allcodecs内のファイルをコンパイルします。ソースコードをここに置いてください。ハッシュが単一の*.hファイルでも動作します。

接続処理はhashes.hで行います。このファイルには2つの部分があります。

• 必要な#include "header.h"を追加し、関数ポインターが求める形式に合わせたラッパーを作成します。
• hashes.h末尾の表に、ラッパーと名前、出力幅の情報を追加します。

makeでビルドします。./collisionsTest -hで、新しいハッシュが一覧に表示されることを確認してください。

使い方

usage: ./collisionsTest [hashName] [opt]

list of hashNames: (...)

Optional parameters:
  --nbh=NB       Select nb of hashes to generate (25769803776 by default)
  --filter       Enable the filter. Slower, but reduces memory usage for same nb of hashes.
  --threadlog=NB Use 2^NB threads
  --len=NB       Select length of input (255 bytes by default)

上のヘルプの日本語説明：実行時にハッシュ名とオプションを指定します。--nbh=NBは生成するハッシュ数を選び、既定値は25769803776です。--filterはフィルターを有効にします。同じハッシュ数でメモリ使用量を減らしますが、処理は遅くなります。--threadlog=NBは2^NB個のスレッドを使います。--len=NBは入力の長さを選び、既定値は255バイトです。

衝突テストの設定に関する助言

大半のテストは、主に利用可能なRAMの量によって決まります。テスト規模を決める方法を示します。

RAMに余裕がなく、この例では32 GBとすると、意味のある測定を行うには実際には--filterモードが必須です。メモリの50%、つまり16 GBをフィルターに割り当てることにします。これで、その大きさより約10%少ない個数のハッシュをフィルターにかけるには十分です。切り下げて14 Gとします。

14Gを指定すると、プログラムが自動的にフィルターを16 GBに設定し、約1G個の候補を保存すると見込めます。システムにも十分な余裕が残ります。

コマンドラインは次のようになります。

./collisionsTest --nbh=14G --filter NameOfHash

例

このテスターで得られた結果の例を示します。

小さい入力のテスト：