伝統的チェックサムCRC-32を実装してみよう

新しいプログラミング言語を覚えようと思ったとき、これまで何度か見たことのあるプログラムをその言語で作ってみるのがオススメです。今回は、今でもあらゆるところで使われている伝統的なチェックサムであるCRC-32をRustで実装してみましょう。

• RustでCRC-32のテーブルを作成してチェックサムを計算したところ

CRC-32って何だっけ？

CRC-32とはネットワークやファイルのデータ破損がないかを検出できる簡単な計算アルゴリズムです。CRCの名前は「Cyclic Redundancy Check(巡回冗長検査)」の略です。比較的アルゴリズムが容易でありながら、効率よくデータの誤り検出ができます。

1961年に公開されて以来、イーサネットや各種通信機器で広く利用されています。なお、圧縮形式のZIPや、画像ファイルのPNGなどで採用されています。そのため、私たちの生活に欠かせないアルゴリズムの一つと言えるでしょう。

C言語で書かれたお手本について

そもそも、CRCにはいろいろなバリエーションが存在しますが、ZIPやPNGでは「CRC-32」と呼ばれる方式が使われています。

それで、GZIPフォーマットを解説したRFC 1952や、PNGフォーマットを解説したRFC 2083には、C言語のソースコードが掲載されています。

次の画面は、RFC-2083の末尾で参照されているCRC-32を計算するC言語のコードです。このプログラムでは、最初にCRCを計算するためのテーブルを作成しておいて、そのテーブルを用いてCRC-32のチェックサムを求める仕組みのものとなっています。この点については、後ほど詳しく解説します。

• PNGのRFCにCRC-32の実装例が載せられている

Rustで実装してみよう

それでは、パッケージマネージャー兼ビルドシステムのCargoを利用してプロジェクトを作成しましょう。

mkdir program_crc32
cd program_crc32
cargo init

すると下記のようなディレクトリ構成のプロジェクトが作成されます。

.
├── Cargo.toml
└── src
    └── main.rs

この中にある、main.rsをテキストエディタで編集します。

CRC-32を最もシンプルに実装をしてみよう

それでは、CRC-32を最もシンプルに実装してみましょう。CRC-32の計算は以下の手順で行われます。

(1) CRCの初期値として0xFFFFFFFFを指定
(2) 対象データ列について、1バイトずつ下記の(2)から(6)の処理を行う
(3) CRCと対象バイトのXORを求めてCRCとする
(4) 8回以下(5)と(6)を繰り返す
(5) もしもCRCの下位1ビットが1ならば、CRC値を0xEDB88320でXOR演算
(6) CRCを右へ1ビットシフト
(7) CRCのビットを反転する

このように、ビットシフトとXOR演算を繰り返すだけで計算できます。とてもシンプルに求めることができます。

これをそのまま実装したのが以下のプログラムです。main.rsにプログラムを記述してみましょう。こちらにもアップしています。

// CRC-32を計算する関数
fn crc32(bin_data: &[u8]) -> u32 {
    let crc32poly:u32 = 0xEDB88320;
    // CRC-32の初期値 --- (*1)
    let mut crc:u32 = 0xFFFFFFFF;
    // バイト列の各バイトについて繰り返し計算を行う --- (*2)
    for byte in bin_data {
        // XORを行う --- (*3)
        crc ^= *byte as u32;
        // 8回(8ビット分)繰り返す --- (*4)
        for _ in 0..8 {
            // ただし下位ビットが1ならXORする --- (*5)
            if (crc & 1) == 1 {
                crc >>= 1;
                crc ^= crc32poly;
            } else {
                crc >>= 1;
            }
        }
    }
    // ビットを反転させる --- (*6)
    crc ^ 0xFFFFFFFF
}

fn main() {
    // b"hello"のCRC-32を計算する --- (*7)
    let bin_data = b"hello";
    let crc = crc32(bin_data);
    println!("CRC-32: {:08X}", crc);
}

プログラムを実行するには、下記のコマンドを実行します。

cargo run

すると、次の画面のように、答えである0x3610A686が表示されることでしょう。

• テストデータ「hello」のCRC-32の値を計算して出力したところ

プログラムを確認してみましょう。(＊1)ではCRC-32の初期値として0xFFFFFFFFを与えます。そして、(＊2)以降では調べたいバイト列に対して繰り返し(＊3)のようにXOR演算を行います。そして、(＊4)8回ビットシフトを行います。ただし、(＊5)のように下位ビットが1のときには、0xEDB88320をXOR演算します。そして、最後に(＊6)で各ビットを反転させます。

(＊7)では、テストでバイナリ文字列b"hello"のCRC-32の値を求めて画面に出力します。

キャッシュテーブルを利用して高速にCRC-32を計算しよう

PNGやGZIPのRFCに書かれていたC言語のプログラムでは、直接CRC-32を計算するのではなく、CRC-32を計算するためのキャッシュテーブルを用意して、これを使って高速にCRC-32を計算するようになっていました。

それでは、キャッシュテーブルを用意して計算するように、上記のプログラムを改良してみましょう。同じく「src/main.rs」に下記のプログラムを記述します。こちらにもアップしています。

// CRC-32のためのキャッシュテーブルを作成する関数 --- (*1)
fn crc32_table() -> [u32; 256] {
    // テーブルを0で初期化
    let mut table: [u32; 256] = [0; 256];
    let crc32poly:u32 = 0xEDB88320;
    // 0-255の各値について繰り返し計算を行う --- (*2)
    for i in 0..256 {
        let mut crc:u32 = i as u32; // 値を初期化
        // 8回(8ビット分)繰り返す --- (*4)
        for _ in 0..8 {
            if (crc & 1) == 1 {
                crc >>= 1;
                crc ^= crc32poly;
            } else {
                crc >>= 1;
            }
        }
        table[i] = crc;
        // キャッシュテーブルの内容を分かりやすく出力
        print!("0x{:08X},", table[i]);
        if i % 8 == 7 {
            println!("");
        }
    }
    table
}

// キャッシュテーブルを用いてCRC-32を計算する関数 --- (*5)
fn crc32_update(bin_data: &[u8], cache_table: &[u32; 256]) -> u32 {
    // CRC-32の初期値
    let mut crc:u32 = 0xFFFFFFFF;
    // バイト列の各バイトについて繰り返し計算を行う
    for byte in bin_data {
        // キャッシュテーブルを用いて計算する --- (*6)
        crc = (crc >> 8) ^ cache_table[((crc & 0xFF) ^ (*byte as u32)) as usize];
    }
    // ビットを反転させる
    crc ^ 0xFFFFFFFF
}

fn main() {
    // b"hello"のCRC-32を計算する --- (*7)
    let bin_data = b"hello";
    // キャッシュテーブルを作成
    let cache_table = crc32_table();
    // 計算
    let crc = crc32_update(bin_data, &cache_table);
    println!("CRC-32: {:08X}", crc);
    // 念のためテスト
    assert_eq!(crc32_update(b"test", &cache_table), 0xD87F7E0C);
    assert_eq!(crc32_update(b"hoge", &cache_table), 0x8B39E45A);
}

プログラムを実行するには、下記のコマンドを実行します。すると作成したハッシュテーブルの一覧を表示し、その後でプログラムの実行結果を表示します。

cargo run