経緯
仕事上の都合で、データが破損しているかどうかの確認をする必要がありました。（ダウンロードしたデータが壊れていないかなど）
どのアルゴリズムを使うのが適当なのか、情報をまとめておきます。
自分は全然この手の専門家ではないので、間違いあればご指摘ください。
手法
調べると様々手法があるようですが、３つをピックアップ。（他にもパリティとかありますが、今回は除外）
誤り検出率（=信頼性）と処理負荷の面で、ざっくり並べるとこんな感じになりました。
| 手法 | 信頼性 | 処理負荷 | 出力ビット数 | 特徴 | |
|---|---|---|---|---|---|
| 1 | チェックサム | 低 | 低 | 8~64 | 高速処理が可能だが、誤り検出率が低い。 |
| 2 | 巡回助長検査 | 中 | 中 | 8~64 | チェックサムより誤り検出率が高い。CRC-32が一般的。 |
| 3 | ハッシュ関数 | 高 | 高 | 128~512 | 誤り検出率が一番高い。その分負荷が高い。改ざんチェックにも使われる。 |
いずれのケースでもデータ（ファイル）を入力し、得られた値を破損チェックに使用します。
手法１は信頼性の面で評価から除外。（どのアルゴリズムを使えばいいのかよくわからないし・・・）
手法３はSHA-3など1024ビット超えるアルゴリズムがありますが、データ破損チェックには重すぎると思うので、その辺も除外。
手法２と手法３の中から、代表的なアルゴリズムを選ぶことにします。
余談
手法２、３で得られた値のこともチェックサムと呼ばれるようですが、紛らわしいのでここでは手法１の出力のみをチェックサムと呼ぶことにします。
性能評価対象アルゴリズム
探すとアルゴリズムいっぱい出てきます。
RIPEMDというハッシュ関数もあるみたいですが、検索してもあまり情報が出てこないので除外。
仕事柄Unityを使うことが多いので、Unity(C#)で簡単に使える下記ハッシュ関数３つ（MD5/SHA-1/SHA-2)をチョイス。
プラス、AssetBundleでも使うCRC-32も追加。（C#にはCRC-32を求める関数がないので落ちてるコードで検証）
ということで以下の５ケースに絞りました。
- CRC-32 : 32bit
- MD5 : 128bit
- SHA-1: 160bit
- SHA-256: 256bit
- SHA-512: 512bit
SHA-2は256だけで本来十分ですが、処理負荷がどれぐらいか気になったので参考までに追加。
FNVという、ハッシュ関数もあるようですが、CRCと同じような処理内容かつ汎用性がないということで除外。
Unity上での実行結果
動作確認Unity
- Unity 5.4.0f3
検証内容
1KB、1MB、10MB、100MBのランダム生成したファイルを用意。
（中身がランダムデータである必要もないとは思いますが、一応。）
まずファイルをメモリに読み込み、読み込んだメモリに対してチェックサム・ハッシュ値を取得。
使用APIは、MD5/SHA1/SHA256/SHA512CryptoServiceProvider。CRC-32は独自実装。
データ読み込み時間は"I/O"として計測。各セルの単位はミリ秒。
Unity Editor/macOS (MacBook Air 1.8 GHz Intel Core i7)
| I/O | CRC32 | MD5 | SHA-1 | SHA-256 | SHA-512 | |
|---|---|---|---|---|---|---|
| 1KB | 2 | 0 | 2 | 1 | 1 | 1 |
| 1MB | 5 | 7 | 12 | 25 | 56 | 135 |
| 10MB | 42 | 82 | 154 | 244 | 577 | 1326 |
| 100MB | 482 | 868 | 1537 | 2432 | 5810 | 13491 |
参考値
md5コマンドを実行した場合、10MBで52ms。100MBで400ms。
shasum -a 256コマンドを実行した場合、10MBで231ms。100MBで1063ms。
shasum -a 512コマンドを実行した場合、10MBで143ms。100MBで1023ms。
rubyでDigest::MD5を使用した場合、10MBで251ms。100MBで730ms。
rubyでDigest::SHA256を使用した場合、10MBで429ms。100MBで1286ms。
rubyでDigest::SHA512を使用した場合、10MBで315ms。100MBで955ms。
iOS (iPhone 6s)
| I/O | CRC32 | MD5 | SHA-1 | SHA-256 | SHA-512 | |
|---|---|---|---|---|---|---|
| 1KB | 6 | 0 | 0 | 0 | 0 | 0 |
| 1MB | 4 | 12 | 12 | 12 | 22 | 17 |
| 10MB | 29 | 140 | 127 | 121 | 222 | 183 |
| 100MB | 234 | 1359 | 1255 | 1198 | 2206 | 1812 |
記載しませんでしたが、2MBでも1MBと同じような結果に。
データ量が比較的小さい場合は、想定よりもパフォーマンスが出るかもです。
Android (Nexus 5x)
Monoビルド
| I/O | CRC32 | MD5 | SHA-1 | SHA-256 | SHA-512 | |
|---|---|---|---|---|---|---|
| 1KB | 28 | 1 | 6 | 5 | 4 | 5 |
| 1MB | 31 | 10 | 13 | 26 | 40 | 221 |
| 10MB | 174 | 103 | 134 | 267 | 400 | 2214 |
| 100MB | 635 | 1050 | 1351 | 2621 | 4005 | 22188 |
IL2CPPビルド
| I/O | CRC32 | MD5 | SHA-1 | SHA-256 | SHA-512 | |
|---|---|---|---|---|---|---|
| 1KB | 2 | 0 | 0 | 0 | 0 | 0 |
| 1MB | 18 | 15 | 18 | 18 | 19 | 35 |
| 10MB | 175 | 102 | 145 | 169 | 192 | 349 |
| 100MB | 588 | 1045 | 1483 | 1722 | 1947 | 3662 |
※AndroidはSDカードからの読み込みで計測。
まとめ
計測結果からの考察
- MD5が一番バランス良さそう。
- CRC-32はC#実装のためか、MD5と処理負荷がほとんど変わらない結果に（iOSに至っては逆転）
- CRC-32をネイティブ実装すれば高速化可能？
- 計算負荷もファイル読み込み時間もファイルサイズに正比例。
- 1KB時にほとんどロード時間がかからないので、この３機種についてはファイル数よりも総ファイルサイズが支配的。
- SHA-256はMD5の2〜４倍の計算負荷。
- なぜかSHA-512の方がSHA-256より負荷が低いケースがある。（そういうもの？）
- C#のハッシュ関数APIではパフォーマンスが出し切れてない？機種固有APIを駆使するともっと高速化できるかも？
- IL2CPPビルドにすると、SHA-1/SHA-2の性能が上がった。
付録１：その他ハッシュの取得方法メモ
macOSでのCRCやハッシュ値の取得
crc32 /path/to/file
md5 /path/to/file
shasum -a 256 /path/to/file
Windows Powershellでのハッシュ値の取得
Get-FileHash /path/to/file -Algorithm MD5
Get-FileHash /path/to/file -Algorithm SHA256
Rubyでのハッシュ値の取得
require "digest/md5"
puts Digest::MD5.file(ARGV[0])
require 'digest/sha2'
puts Digest::SHA256.file(ARGV[0]).hexdigest
・・・案外CRC-32は標準機能で提供されないものなのでしょうか。
付録２：検証C#スクリプト（部分抜粋）
こんな感じでGameObjectに貼りました。(CRC32の実装は割愛）
※そのままではビルドできませんので注意。
あと、今回は読み込み時間は分けて考えたかったので、データのロードとハッシュ計算を別々に分けました。
ComputeHashにFileStreamを突っ込むと、オーバーラップで読み込み時間は消えるかもしれません。
public class Test : MonoBehaviour {
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch ();
void Start () {
var da = new Dictionary<string, string>() {
{"1KB", "random_0.dat"},
{"1MB", "random_1.dat"},
{"10MB", "random_10.dat"},
{"100MB", "random_100.dat"},
};
var ha = new Dictionary<string, HashAlgorithm>() {
{ "CRC32", new Hoge.CRC32() },
{ "MD5", new MD5CryptoServiceProvider() },
{ "SHA1", new SHA1CryptoServiceProvider() },
{ "SHA256", new SHA256CryptoServiceProvider() },
{ "SHA512", new SHA512CryptoServiceProvider() },
};
long[] ms = new long[ha.Count+1];
#if !UNITY_EDITOR && UNITY_ANDROID
string dataRoot = "/sdcard";
#else
string dataRoot = Application.streamingAssetsPath;
#endif
foreach (KeyValuePair<string, string> d in da) {
int i=0;
sw.Start(); /* 読み込み時間計測開始 */
byte[] bs = LoadFile(dataRoot+"/"+ d.Value);
sw.Stop(); /* 読み込み時間計測終了 */
ms[i++] = sw.ElapsedMilliseconds; sw.Reset();
foreach (KeyValuePair<string, HashAlgorithm> h in ha)
{
sw.Start(); /* ハッシュ・チェックサム計算計測開始 */
h.Value.ComputeHash(bs);
sw.Stop(); /* ハッシュ・チェックサム計算計測終了 */
ms[i++] = sw.ElapsedMilliseconds; sw.Reset();
}
UnityEngine.Debug.Log ("|" + d.Key + "|" + ms[0] + "|" + ms[1] + "|" + ms[2] + "|" + ms[3] + "|" + ms[4] + "|" + ms[5] + "|");
}
}
private byte[] LoadFile(string path) {
System.IO.FileStream fs = new System.IO.FileStream(
path,
System.IO.FileMode.Open,
System.IO.FileAccess.Read);
byte[] bs = new byte[fs.Length];
fs.Read(bs, 0, bs.Length);
fs.Close();
return bs;
}
}
SHA256CryptoServiceProviderクラスは、そのままだと見つからないので注意。@Unity5.4
Player Settignsで、API Compatibility Levelを「.NET 2.0」に変更する必要があります。
付録３：ランダムデータの作成
検証で使用したランダムデータは、macOSからddコマンドで作成しました。
こちらのページを参照させていただきました。
プロンプトから以下を複数行実行すると1MB/10MB/100MBのデータが出来上がります。(1KBは手打ちで・・・)
> for i in 1 10 100 do
dd if=/dev/urandom of=random_$i.dat count=$i bs=1048576
done
bsの引数に1Mと打ち込むと dd: bs: illegal numeric value と出てしまったので、バイトで指定しました。