問題タブ [crc32]

TeraSort Hadoop ジョブで最も多くの時間を消費する関数をプロファイリングしようとしています。私のテスト システムでは、基本的な 1 ノードの疑似分散セットアップを使用しています。これは、NameNode、DataNode、Tasktracker、および Jobtracker JVM がすべて同じマシンで実行されることを意味します。

最初に TeraGen を使用して ~9GB のデータを生成し、次に TeraSort を実行します。JVM が実行されている間、VisualVM を使用してその実行をサンプリングします。これが最も正確なプロファイラーではないことはわかっていますが、無料で使いやすいです! 私は最新バージョンの Apache Hadoop ディストリビューションを使用しており、私の実験は Intel Atom ベースのシステムで実行されています。

VisualVM のホット スポット メソッドのセルフ タイム (CPU) を見ると、java.util.zip.CRC32.update() 関数が合計時間の約 40% を占めていることがわかります。コール ツリーでこの関数を見ると、特に IdentityMapper.map() が HDFS から入力ファイルを読み取っているときに、マッパーの main() 関数によって呼び出されます。CRC32.update() 関数を実際に呼び出す関数は、org.apache.hadoop.fs.FSInputChecker.readChecksumChunk() です。

これに関して 3 つの質問があります。

1. HDFS から読み取られるブロックの CRC32 チェックサムが更新されるのはなぜですか? 私が正しく理解している場合、ブロックが読み取られると、ブロックのCRC値を生成および更新するのではなく、ディスクから読み取られたデータとブロックのCRCとの単純な比較が唯一の操作になるはずです。

2. update 関数のソースを調べたところ、java.util.zip.CRC32.java ファイルによって実装されています。呼び出される特定の関数は、3 つの引数を持つオーバーロードされた update() メソッドです。この関数は Java で実装されているため、複数の抽象化レイヤー (Hadoop、JVM、CPU 命令) が CRC 計算のネイティブ効率を低下させている可能性はありますか?

3. 最後に、私の VisualVM 計測方法、またはサンプリング結果の解釈に重大な問題がありますか?

ありがとう、

32 ビットの CRC を使用する場合、データ ワードのサイズは 2 の 32 乗 (2**32) に CRC の 32 ビットを加えたものになります....そうではないでしょうか? 何か不足していますか？

32 ビット CRC を実装するために Microsoft Visual C++ でコードを書きたい場合、使用できるデータ型は何ですか? 多分私は要点を逃しており、くだらない話をしています。

基本的に、32 ビット CRC を実装するのは私の課題であり、どうすればよいか完全に途方に暮れています。

質問があいまいな場合は申し訳ありません。実装、ロジック、または基本的な基礎に関するヘルプは大歓迎です。

入力メッセージに基づいて基本的に値を作成するCRCチェックのアルゴリズムを実装しようとしています。したがって、16 進メッセージ 3F214365876616AB15387D5D59 があり、メッセージの CRC24Q 値を取得したいとします。これを行うために私が見つけたアルゴリズムは次のとおりです。

ここで、*input=3F214365876616AB15387D5D59。問題は、 ((*octets++) << 16) は、文字自体ではなく、16 進文字の ascii 値を 16 ビットシフトすることです。そこで、16進数を文字に変換する関数を作りました。実装が奇妙に見えることはわかっていますが、それが間違っていたとしても驚かないでしょう。これは変換関数です:

それで：

ご提案いただきありがとうございます。

私は毎日約100万のURLを追加/更新する必要があるプロジェクトに取り組んでいます。ある日はほとんど更新され、ある日はほとんど追加され、ある日は混合されます。

したがって、すべてのクエリで、URLテーブルでURLの一意性を検索する必要があります。

現時点ではインデックスがurl列に設定されており、正常に機能するため、URLの検索方法は非常に高速ですが、インデックスが同じ列に保持され、新しいレコードが数百万単位で追加される場合、RAMは今後数週間で十分ではなくなります。

だから私は解決策を探しているので、合計で1億5000万以上のURLがある場合、その検索は高速になるはずです。md5でインデックスを作成することを考えていますが、衝突の可能性が心配です。友人から、crc32ハッシュも計算し、md5と連結して衝突の可能性をゼロにし、binary（20）に格納するように言われました。これにより、現在url列データとして設定されている255ではなく20バイトのみがインデックスとして使用されます。タイプ。

現在、合計で約5,000万のURLがあり、8GBのRAMで正常に動作しています。

昨日、同じプロジェクトに関連するURLテキストの圧縮（短縮ではない）とmysqlへの保存について質問しました。

[編集] 検索を高速化するために、crc32ハッシュを10進形式でのみ配置する別の解決策を考えました。また、アプリケーションレベルの移植では、返されるレコードの数を確認します。複数のレコードが返される場合は、正確なURLも一致する必要があります。そうすれば、20バイト（md5 + crc32）ではなく各行に4バイトを格納することで、RAMとディスクスペースの負荷を低く抑えながら、衝突を回避することもできます。あなたが言うこと？

UNIX の cksum コマンドと一致する方法で、バイト ストリームの 32 ビット CRC を計算する Java のライブラリ/コードはありますか?

I was looking for a CRC32 implementation I could use on the .Net Micro framework. I found this implementation, but the micro framework has not yet implemented the HashAlgorithm. What would be the best way to get this working ?

現在、C++ に Boost を使用しており、CRC32 を使用して順序付けされていないマップ (別名ハッシュ テーブル) を実装しようとしています。私の知る限りでは、文字列を初期キーとして取得し、それをハッシュして、バケットの数に収まるように別の操作を適用します。

私の状況では、事前に文字列キーをハッシュし (Boost で別の CRC 関数を使用)、その ID を使用してテーブルのインデックスを作成したいと考えています。私が助けを必要としている問題は、CRC32 ハッシュには 2^32 の潜在的な値があり、2^32 の要素を持つテーブルが必要になるとは思えないことです。この状況で私は何をすべきですか？

ここで助けてくれてありがとう！

CRC32またはCheckedInputStreamクラスのいずれかを使用して、最新の入力で継続的に更新することによってチェックサムを計算することを誤解していますか? 入力が <= 128KiB の場合、有効な CRC32 が生成されます。128KiB を超えると、チェックサムが失敗します。以下は私が作業しているコードです（CRC32オブジェクトを使用していますが、CRC32を追跡するためにBufferedInputStreamaを使用すると同じ問題が発生します）。CheckedInputStream

アドバイスやコメントをいただければ幸いです。

RAR回復レコードのヘッダーにある crc32 フィールドがどのデータに基づいているかを調べようとしています。以前の RAR ボリュームと抽出した内容に基づいて RAR ボリュームを再作成しようとしています。正しい/元のボリュームとは 12 バイトしか違わないところまで来ています。

名前はunrar ソース コード(arcread.cpp) またはRAR 技術情報に基づいています。

RAR ファイルはブロックで構成されています。ヘッダーと本文があります。

ヘッダーには、本文を説明するメタデータが含まれています。これらのブロックの 1 つが HEAD_TYPE=0x74ファイル ヘッダー(アーカイブ内のファイル) です。

フィールド FILE_CRC (4 バイト) は、保存または圧縮されたファイルである [本体] で使用可能なすべてのデータで計算されます。

Recovery Recordのブロック(HEAD_TYPE=0x7a サブブロック) はファイル ブロックに非常に似ていますが、ヘッダーに 3 つの追加フィールドが含まれています。

このブロックの FILE_CRC は、ファイル ブロックと同じように本体のデータに基づいていると思われるかもしれませんが、そうではありません。（他の人によって個別に検証されました）私の質問は、このcrc32を計算するためにどのデータが使用されるのですか?

私がすでに試したいくつかのこと：

• Protect+ ectから始めます。続いて体
• RR サブブロックの開始前のすべて
• 小さなRARファイルで可能なすべての範囲をブルートフォースしました。

基本的に私はグーグルテストでいくつかのユニットテストを開始しようとしていますが、それをどうやって行うのかわかりません。試してテストするためのコードがいくつか与えられましたが、これを行う方法がわかりません。これは私がテストする必要があるコードの一部ですか？どこから始めればいいですか？助けてくれてありがとう。