伝統的チェックサム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

プログラムを確認してみましょう。このプログラムのポイントは、CRCの8ビット分の繰り返し計算をあらかじめ行ったキャッシュデータのテーブルを用意しておくという部分です。

(＊1)ではキャッシュテーブルを作成する関数crc32_tableを定義します。ここで作るキャッシュテーブルは、1バイトずつ参照するものであるため、0-225までの8ビットの範囲です。(＊2)の繰り返しで256通りの値を用意します。作成するテーブルの1つの値は、(＊4)で各値が8回分の繰り返しで作成するものです。

(＊5)ではキャッシュテーブルを用いて、CRC-32を計算する関数crc32_updateを定義します。(＊6)ではXOR演算とキャッシュテーブルの値を利用して、CRC-32を計算します。(＊7)では、実際にb"hello"のCRC-32の計算値を表示します。

ちなみに、CRC-32のテーブルを計算する時間など、微々たるものですが、下記のように計算済みのCRC-32のテーブルを最初から配列に書き込んでおいて、それを利用するというアプローチも考えられるでしょう。

const CRC32_TABLE: [u32; 256] = [
    0x00000000,0x77073096,0xEE0E612C,0x990951BA,0x076DC419,0x706AF48F,0xE963A535,0x9E6495A3,
    0x0EDB8832,0x79DCB8A4,0xE0D5E91E,0x97D2D988,0x09B64C2B,0x7EB17CBD,0xE7B82D07,0x90BF1D91,
    0x1DB71064,0x6AB020F2,0xF3B97148,0x84BE41DE,0x1ADAD47D,0x6DDDE4EB,0xF4D4B551,0x83D385C7,
    0x136C9856,0x646BA8C0,0xFD62F97A,0x8A65C9EC,0x14015C4F,0x63066CD9,0xFA0F3D63,0x8D080DF5,
    0x3B6E20C8,0x4C69105E,0xD56041E4,0xA2677172,0x3C03E4D1,0x4B04D447,0xD20D85FD,0xA50AB56B,
    0x35B5A8FA,0x42B2986C,0xDBBBC9D6,0xACBCF940,0x32D86CE3,0x45DF5C75,0xDCD60DCF,0xABD13D59,
    ...
];

既に長くなってしまったので、プログラム全体が確認したい場合は、こちらのGitHubを確認してみてください。このテーブルを利用してCRC-32を計算します。

まとめ

以上、今回はCRC-32を計算するプログラムを作ってみました。キャッシュテーブルを使わない場合と使う場合で2つのパターンを作ってみました。C言語の実装と比べてみても、それほど代わりなく使えることが分かったことでしょう。また、関数呼び出しの際、C言語の実装ではポイント及び配列サイズの指定が必要となりますが、Rustのスライス(Slice)であればメモリサイズが分かっており、配列サイズの指定も不要で、安全に利用できることも分かったことでしょう。

自由型プログラマー。くじらはんどにて、プログラミングの楽しさを伝える活動をしている。代表作に、日本語プログラミング言語「なでしこ」 、テキスト音楽「サクラ」など。2001年オンラインソフト大賞入賞、2004年度未踏ユース スーパークリエータ認定、2010年 OSS貢献者章受賞。技術書も多く執筆している。直近では、「実践力をアップする Pythonによるアルゴリズムの教科書(マイナビ出版)」「シゴトがはかどる Python自動処理の教科書(マイナビ出版)」「すぐに使える!業務で実践できる! PythonによるAI・機械学習・深層学習アプリのつくり方 TensorFlow2対応(ソシム)」「マンガでざっくり学ぶPython(マイナビ出版)」など。