軽量のチェックサムアルゴリズムに適していますか？
https://stackoverflow.com/questions/421419
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
一貫性を保つために、データ列のチェックサムを生成する必要があることに気付きました。大まかな考え方は、クライアントは受信したペイロードに基づいてチェックサムを再生成できるため、転送中に発生した破損を検出できるということです。私はこの種のことの背後にあらゆる種類の数学的原理があることを漠然と認識しています。そして、あなたがそれを転がそうとすると、微妙なエラーがアルゴリズム全体を無効にすることは非常に簡単です。
だから私は、次の基準を持つハッシュ/チェックサムアルゴリズムに関するアドバイスを探しています：
- Javascriptによって生成されるため、計算が比較的軽い必要があります。
- 検証はJavaによって行われます（実際、これが問題であることはわかりません）。
- 適度な長さのテキスト入力（URLエンコードされたUnicode、これはASCIIと考えられます）を取ります。通常は約200〜300文字で、すべての場合で2000未満です。
- 出力もASCIIテキストである必要があり、短いほど良い場合があります。
私は、衝突の可能性を極限まで小さくするよりも、主に軽量のものに興味があります。 8文字のハッシュがこれに適していると想像するのは簡単でしょうか？また、検証段階で破損が検出されなければ、世界の終わりではないことを明確にする必要があります（そして、これは100％の信頼性がないことを理解しています）。抜ける破損したエントリ。
編集-すべての貢献に感謝します。 Adler32オプションを使用し、Javaでネイティブにサポートされていて、Javascriptでの実装が非常に簡単で、両端で高速に計算され、8バイトの出力があるため、要件にぴったりでした。
（ネットワークトランスポートが破損エラーの原因となる可能性は低いことを認識しており、まだこの問題に腕を傾けることはないことに注意してください。ただし、チェックサム検証を追加すると、1つの障害点がなくなり、集中できることを意味します他のエリアでは、これが再発するはずです。）
解決
CRC32はどの言語でも実装するのにそれほど難しくありません。単純なデータ破損を検出するのに十分であり、良い方法で実装された場合、非常に高速です。ただし、CRC32とほぼ同等の優れたAdler32を試すこともできますが、実装はさらに簡単です（ほぼ同等に高速です）。
これら2つ（またはおそらく両方）は、そのままJavaで使用できます。
他のヒント
TCPとUDP（およびIPとイーサネットなど）の両方がすでに転送中のデータにチェックサム保護を提供していることを知っていますか？
本当におかしなことをしていない限り、破損が見られる場合、何かが非常に間違っています。 メモリテスターから始めることをお勧めします。
また、SSL / TLSを使用すると、強力なデータ整合性保護が提供されます。
MD4、MD5、およびSHA1のJavascript実装。 BSDライセンス。
他の人は既にCRC32について言及していますが、ここに CRCのW3C実装へのリンクがありますPNG用の-32 、参照CRC実装を備えた数少ない有名で評判のよいサイトの1つ。
（数年前、CRCアルゴリズムまたはそのアルゴリズムのソースを引用した少なくとも1つの有名なサイトを見つけようとしましたが、＆amp;はPNGページが見つかるまでほとんど髪を引き裂いていました）
[2013年5月30日更新：古いJS CRC32実装へのリンクが終了したため、別の実装にリンクしました。]
Google CRC32：高速で、MD5などよりもはるかに軽量です。 Javascript実装がありますこちら。
適切なチェックサムアルゴリズムのJavaScript実装の検索で、この質問に出会いました。 Andrzej Doyle は、Adler32をチェックサムとして正しく選択しました。これは、実際に実装が簡単で、いくつかの優れたプロパティがあるためです。その後、 DroidOS はJavaScriptの実際の実装を提供し、シンプルさを実証しました。
ただし、ウィキペディアのページに詳細があり、以下に実装されているように、アルゴリズムをさらに改善できます。秘Theは、各ステップでモジュロを決定する必要がないことです。むしろ、これを最後まで延期できます。これにより、実装の速度が大幅に向上し、ChromeおよびSafariで最大6倍高速になります。さらに、この最適化はコードの可読性に影響を与えず、Win-Winになります。そのため、計算量が少ないアルゴリズム/実装を使用することに関する元の質問に確実に適合します。
function adler32(data) {
var MOD_ADLER = 65521;
var a = 1, b = 0;
var len = data.length;
for (var i = 0; i < len; i++) {
a += data.charCodeAt(i);
b += a;
}
a %= MOD_ADLER;
b %= MOD_ADLER;
return (b << 16) | a;
}
編集： imaya はしばらくしてjsperf比較を作成し、 DroidOS で詳細に説明されているように、単純なバージョンの実行時の速度の違いを示しました。モジュロ演算を延期する最適化されたバージョンと比較して。上記の実装を full-length という名前で jsperfページは、上記の実装が imaya の実装よりも約25％高速であり、単純な実装よりも約570％高速であることを示しています（テストはChrome 30）： http://jsperf.com/adler-32-simple-vs -optimized / 6
edit2：大規模なファイルで作業する場合、最終的にaおよびb変数に関してJavaScript実装の制限に達することを忘れないでください。そのため、大きなデータソースを使用する場合は、中間モジュロ演算を実行して、確実に格納できる整数の最大値を超えないようにする必要があります。
SHA-1 JS実装を使用します。思ったほど遅くはありません（Core 2 Duo 2.4Ghz上のFirefox 3.0は毎秒100KB以上のハッシュを生成します）。
これは私が「発明」した比較的単純なものです。その背後には数学的研究はありませんが、非常に高速で実際に機能します。また、アルゴリズムをテストし、失敗の可能性が10,000,000分の1未満であることを示すJavaの同等物を含めました（実行に1〜2分かかります）。
JavaScript
function getCrc(s) {
var result = 0;
for(var i = 0; i < s.length; i++) {
var c = s.charCodeAt(i);
result = (result << 1) ^ c;
}
return result;
}
Java
package test;
import java.util.*;
public class SimpleCrc {
public static void main(String[] args) {
final Random randomGenerator = new Random();
int lastCrc = -1;
int dupes = 0;
for(int i = 0; i < 10000000; i++) {
final StringBuilder sb = new StringBuilder();
for(int j = 0; j < 1000; j++) {
final char c = (char)(randomGenerator.nextInt(128 - 32) + 32);
sb.append(c);
}
final int crc = crc(sb.toString());
if(lastCrc == crc) {
dupes++;
}
lastCrc = crc;
}
System.out.println("Dupes: " + dupes);
}
public static int crc(String string) {
int result = 0;
for(final char c : string.toCharArray()) {
result = (result << 1) ^ c;
}
return result;
}
}
これはかなり古いスレッドですが、まだ頻繁に表示されると思われます。必要なのは、短いが信頼性の高いコードで、チェックサムを生成する Adler32 ビットアルゴリズムを選択する必要があります。 JavaScriptコードは次のとおりです
function adler32(data)
{
var MOD_ADLER = 65521;
var a = 1, b = 0;
for (var i = 0;i < data.length;i++)
{
a = (a + data.charCodeAt(i)) % MOD_ADLER;
b = (b + a) % MOD_ADLER;
}
var adler = a | (b << 16);
return adler;
}
実行中のアルゴリズムを示す対応するフィドルは、こちらです。
