クラウドMacで検証するiOSのCRC-32逐次計算

同じファイルでも、一括でチェックサムを計算すると検証に通るのに、分割して読み込むと失敗することがあります。その原因はたいてい、クラウドMacのネットワークではなく、ブロックを読み込むたびにCRCの状態をリセットしていることです。地域をまたぐチームでファイル処理を継続的なテストに組み込むなら、入力ファイルだけでなく、アルゴリズムの種類、分割方法、結果の表現形式も固定する必要があります。ここでは、クラウドMac上でそのまま実行できる受け入れテストをSwiftで作成し、同じ検証をiOSプロジェクトにも組み込みます。

まずCRC-32の計算仕様を固定する

この記事ではCRC-32/ISO-HDLCを使用します。通常表現の多項式は 0x04C11DB7、反射実装で使用する多項式は 0xEDB88320、初期値と最終XOR値はいずれも 0xFFFFFFFF で、入力と出力には反射の規約を適用します。インターフェースの仕様に単に「CRC32」とだけ書くと、送信側と受信側で異なる種類を選んでしまうおそれがあります。

標準テスト文字列 123456789 の結果は CBF43926、空の入力の結果は 00000000 になる必要があります。ここでは文字列をUTF-8のバイト列に変換し、改行は含めません。ターミナルでサンプルを用意する場合、出力コマンドによっては末尾に改行が自動で付くので注意してください。

CRC-32は偶発的なデータ破損を検出するためのもので、改ざんを検知できる保証はありません。ファイルの出所を確認するには、信頼できるデジタル署名を検証してください。ファイルに添えられたCRC値を、安全性の証明として扱ってはいけません。

転送仕様では、結果を8桁の16進数テキストで渡すのか、4バイトの整数で渡すのかも明確にします。整数で渡す場合は、バイトオーダーも別途定めてください。アルゴリズムの「反射」は、ネットワーク転送でリトルエンディアンを使うという意味ではありません。

内部状態を保持する実装を書く

次のコードを crc-check.swift として保存します。この例はパラメーターを確認しやすいように1ビットずつ処理します。正しさを確認するための基準実装であり、高スループット向けの実装ではありません。本番用にテーブル参照方式へ最適化した場合も、後述のテストを引き続き使用してください。

import Foundation

struct CRC32 {
    private var register: UInt32 = 0xFFFFFFFF

    mutating func update<S: Sequence>(_ bytes: S)
    where S.Element == UInt8 {
        for byte in bytes {
            register ^= UInt32(byte)
            for _ in 0..<8 {
                let lowBit = register & 1
                register >>= 1
                if lowBit != 0 {
                    register ^= 0xEDB88320
                }
            }
        }
    }

    var value: UInt32 {
        register ^ 0xFFFFFFFF
    }
}

func checksum(_ bytes: [UInt8]) -> UInt32 {
    var crc = CRC32()
    crc.update(bytes)
    return crc.value
}

func require(_ condition: Bool, _ name: String) {
    if !condition {
        fatalError(name)
    }
}

let vector = Array("123456789".utf8)
require(checksum(vector) == 0xCBF43926, "reference-vector")
require(checksum([]) == 0, "empty-input")

for split in 0...vector.count {
    var crc = CRC32()
    crc.update(vector[..<split])
    let interim = crc.value
    require(interim == checksum(Array(vector[..<split])),
            "intermediate-value")
    crc.update([])
    crc.update(vector[split...])
    require(crc.value == 0xCBF43926, "split-invariance")
}

value は内部レジスターから算出した値を読み取り専用で返すだけなので、途中の結果を取得しても、その後の計算には影響しません。このプロパティ内でレジスターを変更したり、最終XOR後の結果を次のブロックの初期状態にしたりしないでください。誤用しやすいリセット用インターフェースを設けるより、ファイルごとに新しいインスタンスを作るほうがわかりやすくなります。

固定ベクトルから分割テストへ広げる

9バイトのベクトルで確認できる動作はごく一部です。次に、バイトが取り得るすべての値を含む決定的な入力を追加し、最上位ビットが立ったバイト、ゼロバイト、端数の最終ブロックもテスト対象にします。

let payload = (0..<4097).map {
    UInt8(truncatingIfNeeded: $0)
}
let expected = checksum(payload)

for size in [1, 7, 64, 1024, 4096, 8192] {
    var crc = CRC32()
    var offset = 0
    while offset < payload.count {
        let end = min(offset + size, payload.count)
        crc.update(payload[offset..<end])
        offset = end
    }
    require(crc.value == expected, "chunk-size-\(size)")
}

var first = CRC32()
first.update(vector)
var second = CRC32()
second.update(payload)
require(first.value == 0xCBF43926, "independent-state")
require(second.value == expected, "second-stream")

ここで確認しているのは、「同じ実装が、分割方法を変えても同じ結果を返すこと」です。この比較だけでアルゴリズムの正しさを証明することはできません。そのため、標準ベクトルのテストも必ず残してください。実際のプロトコルに組み込む際は、独立した実装で生成し、結果を照合済みのバイナリーサンプルも追加します。

異なる2つの入力ならCRCも必ず異なる、というアサーションを書いてはいけません。チェックサムが取り得る値は有限なので、衝突は存在します。ランダムなファイルで衝突が起きなかったとしても、実装の信頼性を証明したことにはなりません。

ファイル読み込みでエラー経路を検証する

同じファイルに、続けて読み込み関数を追加します。FileHandle でブロックを順に読み取り、その都度、読み取ったデータだけを同じインスタンスへ渡すことで、ファイル全体をメモリに読み込まずに処理できます。

func checksumFile(_ url: URL) throws -> UInt32 {
    let handle = try FileHandle(forReadingFrom: url)
    defer { try? handle.close() }

    var crc = CRC32()
    while true {
        let data = try handle.read(upToCount: 64 * 1024) ?? Data()
        if data.isEmpty {
            break
        }
        crc.update(data)
    }
    return crc.value
}

if CommandLine.arguments.count == 2 {
    let url = URL(fileURLWithPath: CommandLine.arguments[1])
    let result = try checksumFile(url)
    Swift.print(String(format: "%08X", result))
}

xcrun swift crc-check.swift を実行すると、ここまでのアサーションが実行されます。読み取り可能なファイルのパスを引数に追加すると、そのファイルのチェックサムも出力されます。読み込みエラーは呼び出し元へ伝播し、空のファイルと誤認されることはありません。ファイルを開けない場合、読み込みに失敗した場合、結果が一致しない場合は、アプリケーションの処理層でそれぞれ区別して記録してください。

読み込み対象には、書き込みが完了して閉じられた、内容の変わらないコピーを使います。ダウンロード中に同じパスのファイルを書き換えながら、別途開いて計算すると、複数の版が混ざった内容を読み込む可能性があります。また、計算が完了しても、その後に書き込まれていないことの証明にはなりません。受け入れテストでは、先に入力を変更されない状態で確定し、その後で長さとCRCを比較します。

プロジェクトへの組み込み時に状態の所有関係を確認する

実装はユニットテストからアクセスできるモジュールに配置し、標準ベクトル、分割不変性、インスタンス間の状態分離、ファイルエラーの伝播という4種類の検証を維持します。ファイルのテストには専用の一時ディレクトリを使い、空のファイルとバイナリーファイルをそれぞれ作成し、テスト終了後に削除します。

iOSの画面では進捗と結果だけを表示し、ファイルの読み込みでメインスレッドを占有しないようにします。転送タスクごとに専用のCRCインスタンスを持たせてください。同じタスクのブロックは必ずファイル内の順序どおりに処理し、並行して実行されるコールバックからレジスターを直接変更してはいけません。

タスクが途中でキャンセルされたら、そのインスタンスは破棄します。中断した処理を再開する場合、最終チェックサムだけでは、そのまま計算を続けることはできません。保存済みの先頭部分を読み直すか、バージョン上の制約を設けた内部状態のチェックポイントを設計する必要があります。後者では、整数を1つ保存するだけでなく、オフセットとファイルの同一性も確認しなければなりません。

最後に、ツールチェーンのバージョン、サンプルの長さ、分割方法、失敗したアサーション名をテスト成果物に残します。そうすれば、次にノードを変更したりアルゴリズムを最適化したりするときに、パラメーターの変更、ブロックの処理漏れ、状態の混用を切り分けられます。原因がわからないまま、ファイルの再転送を繰り返す必要はありません。

よくある質問