6

6 GB の bz2 ファイルの途中からデータを抽出する Python プログラムを作成しています。bzip2 ファイルは、個別に復号化可能なデータ ブロックで構成されているため、必要なのはブロック (マジック ビットで区切られている) を見つけて、そこから一時的な 1 ブロックの bzip2 ファイルをメモリに作成し、最後にそれをbz2.decompress 関数。簡単ですよね？

bzip2形式には、最後にファイルの crc32 チェックサムがあります。問題ありません。binascii.crc32 が役に立ちます。ちょっと待って。チェックサムを計算するデータは必ずしもバイト境界で終わるとは限らず、crc32 関数は整数バイトで動作します。

私の計画: binascii.crc32 関数を最後のバイト以外のすべてに使用し、独自の関数を使用して、計算された crc を最後の 1 ～ 7 ビットで更新します。しかし、何時間にもわたるコーディングとテストの結果、私は戸惑いました。私の困惑は、次の質問に要約できます。ウィキペディアの記事によると、そうすべきではありませんか?

0b00000000 で開始し、32 個の 0 でパディングしてから、最初の 8 ビットに 1 が残らなくなるまで、0x04C11DB7 で多項式除算を行います。最後の 32 ビットはチェックサムです。なぜそれがすべてゼロにならないのでしょうか?

私は答えを求めて Google を検索し、いくつかの CRC-32 実装のコードを調べましたが、その理由についての手がかりは見つかりませんでした。

4

2 に答える 2

10

crc32("\x00") が 0x00000000 ではないのはなぜですか?

基本的な CRC アルゴリズムは、入力メッセージを GF(2) の多項式として扱い、固定の CRC 多項式で割り、多項式の剰余を結果のハッシュとして使用することです。

CRC-32 は、基本アルゴリズムに多くの変更を加えています。

  1. メッセージの各バイトのビットが逆になります。たとえば、バイト 0x01 は、多項式 x^0 としてではなく、多項式 x^7 として扱われます。
  2. メッセージの右側に 32 個のゼロが埋め込まれます。
  3. この反転およびパディングされたメッセージの最初の 4 バイトは、0xFFFFFFFF で XOR されます。
  4. 剰余多項式が逆になります。
  5. 剰余多項式は 0xFFFFFFFF で XOR されます。
  6. また、CRC-32 多項式は非反転形式で 0x104C11DB7 であることを思い出してください。

1 バイト文字列 0x00 の CRC-32 を計算してみましょう:

  1. メッセージ: 0x00
  2. 反転: 0x00
  3. パディング: 0x00 00 00 00 00
  4. XOR: 0xFF FF FF FF 00
  5. 0x104C11DB7で割った余り：0x4E 08 BF B4
  6. 排他的論理和: 0xB1 F7 40 4B
  7. 逆: 0xD2 02 EF 8D

0x00 の CRC-32 は 0xD202EF8D です。
(これを確認する必要があります。)

于 2011-07-12T23:08:47.977 に答える
2

ワンショットdecompress関数に加えて、bz2 モジュールには、BZ2Decompressorデータが decompress メソッドに供給されるときにデータを解凍するクラスも含まれています。したがって、ファイルの終わりのチェックサムを気にせず、ブロックの終わりに到達すると必要なデータを提供します。

説明のために、ファイルから抽出したいブロックを見つけて、それをbitarray.bitarrayインスタンスに保存したと仮定します (他のビット操作モジュールもおそらく同様に機能します)。次に、この関数はそれをデコードします。

def bunzip2_block(block):
    from bz2 import BZ2Decompressor
    from bitarray import bitarray

    dummy_file = bitarray(endian="big")
    dummy_file.frombytes("BZh9")
    dummy_file += block

    decompressor = BZ2Decompressor()
    return decompressor.decompress(dummy_file.tobytes())

bitarrayのfrombytesおよびメソッドは、以前はおよび と呼ばれていたことに注意してください。tobytesfromstringtostring

于 2011-02-19T23:21:14.487 に答える