CRC32の再現方法を求めて

## 巡回冗長検査

[巡回冗長検査(Wikipedia)](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB)

ファイルの完全性検査などにはSHA256やMD5が使われますが、短いテキストのようなデータの場合、SHA256やMD5は結果が長すぎて使いにくいことがあります。

その点、CRC32は結果が32bitで、16進数表記でも8文字で済むため、元のテキストの代替として使うのに簡便です。

しかし、CRC32と一口に言っても実はいくつかの方式があり、異なる値を算出します。

## CRC32の種類

前掲のWikipediaのページを見ても、32bitのCRCには(厳密にはCRCでないAdler32も含めて)
- CRC-32Adler (厳密にはCRCではないがよく混同される)
- CRC-32
- CRC-32C
- CRC-32K

の4種類が掲載されています。CRC-32Adlerは計算方法が全く異なりますが、それ以外の3つは、Wikipedia記事中では生成多項式と呼んでいる定数が異なるのみです。

## 手軽なツールの利用(とその罠)

MD5やSHA256などの値は、元の値から完全に決定されるので、オンラインツールが多く存在しており、元の値に機密性がないならこういったツールを利用できます。

そうしてたまたま以下のようなサイト

- https://bfotool.com/crc32-hash-online
- https://www.paulschou.com/tools/xlate/

で生成した `crc32` の値を持ってくると、例えば `hoge` はこのようになります

- bfotool.com:
    ```text
    Crc32: 4b775151
    Crc32b: 8b39e45a
    ```
- www.paulschou.com:
    ```text
    crc32: 4b775151
    crc32b: 8b39e45a
    ```

`crc32` と `crc32b` があることを気にせずに `crc32` を使うこともあると思います。

ただ、同じ計算をほかのサイトでしてみるとちょっとおかしいことに気づきます。

:::note warn
「おかしい」というのは、「(このサイトを使う以外の)ほかの方法で再現方法がわからない」という意味で言っています。後述するようにこの結果は標準化された方法に基づいて算出されており、巡回冗長検査を目的とした結果としては変な結果ではありません。また、このような値を算出するのは(筆者が調べた限り)珍しいかもしれませんが、PHPをバックエンドの言語・ランタイムとして利用していれば自然だといえます。
:::

例えば以下のサイトで計算すると計算結果は `crc32b` の結果(`8b39e45a`)になります。
- https://crc32.online/
- https://crccalc.com/

また、例えばJavaの [CRC32](https://docs.oracle.com/javase/jp/17/docs/api/java.base/java/util/zip/CRC32.html) や Goの [hash/crc32](https://pkg.go.dev/hash/crc32) パッケージを使って計算しても同じ結果になります。

:::note info
ちなみにGoの場合は、Wikipediaにあった `CRC-32Adler` ([hash/adler32](https://pkg.go.dev/hash/adler32)パッケージを利用))、`CRC-32C`、`CRC-32K` のすべてが実装されていますがいずれで計算しても上記 `crc32` の結果とは一致しません)
:::

では先ほどの `crc32` の結果は何だったのでしょうか？

## 深まる謎

`crc32` や `crc32b` で調べると、どうもPHPに `hash` という関数があり、その引数としてハッシュアルゴリズムを指定するときの引数で `crc32`/`crc32b` という指定があるようです。

> 気づくのが遅かったのは筆者がPHP経験ゼロのためです

そしてこれらの違いは利用者にとっても不思議なもののようで、StackOverflowにも[質問](https://stackoverflow.com/questions/15861058/what-is-the-difference-between-crc32-and-crc32b)されていました。

ただ、回答は「それぞれ別のアルゴリズムだよ。詳細はそれぞれの標準を見に行ってね。」(意訳)といったもので、実用上はそれで困らないものの、何がどう違うのか(例えば生成多項式がどう違うのか)といったことは分かりませんでした。

この時点でPHPを使えば結果を再現できることは分かったものの、PHP経験ゼロの筆者としては「自分の使える道具立てで再現したい」と考え、調査を続行しました。

## ヒント

ヒントになったのは以下のサイトの計算結果でした。
- https://crccalc.com/

`CRC-32` という結果のほかに `CRC-32/BZIP2` という行があり、入力 `hoge` に対して `0x5151774B` という結果が出ています。バイト順序こそ逆ですが `4b775151` が出力されていたのです。

このサイトはアルゴリズムの違ういろいろなCRC32を計算してくれており、その詳細についても表形式でまとまっています。

CRC-32と CRC-32/BZIP2を取り出してみると(resultなどの列は入力 `hoge` に対するもの)


| Algorithm | Result | Check | Poly | Init | RefIn | RefOut | XorOut |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| CRC-32 | 0x8B39E45A | 0xCBF43926 | 0x04C11DB7 | 0xFFFFFFFF | **true** | **true** | 0xFFFFFFFF |
| CRC-32/BZIP2 | 0x5151774B | 0xFC891918 | 0x04C11DB7 | 0xFFFFFFFF | **false** | **false** | 0xFFFFFFFF |

となっていて、`RefIn`/`RefOut` が異なるのみのようです。

## 解決編

眠い目をこすりながら `crc refin` で検索して次のページにたどり着きました。

https://zhuanlan.zhihu.com/p/256487370

Google翻訳を使いながら読んでいくと、どうもGitHubに具体的なコードがあるようです。

https://github.com/whik/crc-lib-c/blob/master/crcLib.c

`crc32` と `crc32_mpeg_2` という関数が上記コードの最下部にあり、これらがそれぞれPHPの `crc32` と `crc32b` (のバイト順序が逆のもの)に相当するようです。

当該Webサイトがアクセスできなくなったあとも結果を再現できれば良い(←今決めた)のでGoでコードを書き直しておきます。

```go
func crc32(b []byte) uint32 {
	var crc uint32 = 0xffffffff
	for _, c := range in {
		crc = crc ^ ((uint32)(c) << 24)
		for i := 0; i < 8; i++ {
			if crc & 0x80000000 != 0 {
				crc = (crc << 1) ^ 0x04C11DB7
			} else {
				crc = (crc << 1)
			}
		}
	}
	return 0xffffffff ^ crc
}
func crc32b(in []byte) uint32 {
	var crc uint32 = 0xffffffff
	for _, c := range in {
		crc = crc ^ (uint32)(c)
		for i := 0; i < 8; i++ {
			if crc & 0x1 != 0 {
				crc = (crc >> 1) ^ 0xEDB88320
			} else {
				crc = (crc >> 1)
			}
		}　
	}
	return 0xffffffff ^ crc
}
```

基本はこれで `crc32(...)` を使えばPHPの `hash("crc32", ...)` 相当、 `crc32b(...)` を使えば `hash("crc32b", ...)` 相当の結果が得られます。

なお、前述の通りPHPの `crc32` の結果はバイト順序が逆になっているので、これを逆にするには `encoding/binary` パッケージのバイト順序関数を使って

```go
import (
    "encoding/binary"
    "fmt"
)

func main() {
    var b []byte = ([]byte)("hoge") // 入力
    // PHPのhash("crc32", ...) 関数に合わせるためにLittleEndianを使ってバイト順序を逆にしている
    fmt.Printf("crc32: %08X\n", binary.LittleEndian.AppendUvarint([]byte{}, crc32(b))
}
```
のようにすればよい。もしバイト配列ではなく `uint32` が欲しければ `binary.BigEndian.Uint32([]byte) uint32` で戻せばよい(この時はBigEndianにしておかないと順序が戻ってしまう)。

## 最後に

巡回冗長検査というのは抽象的な方式に名前が付けられているだけで、具体的なアルゴリズムではないことが分かった。

また、PHPのhash関数のような変種についてWikipediaにも

> 誤り検出符号としてのCRCの概念を実用システムでの実装に移すとき、実装者がそれを複雑化させることがある。以下では、そのような例を解説する。
>
> (中略)
>
> - ビット順序: ある種の方式では各バイトの最下位ビットを先頭とする。すると多項式除算での「左端」は通常の意味での最下位ビットになる。これはシリアルポートでの転送でハードウェアによるCRCチェックを行う場合に良く見られる。というのも、シリアルポートでは最下位ビットを先に転送するものが多いためである。
> - バイト順序: 多バイトCRCでは、バイトの転送順序に混乱が見られる。一部の16ビットCRCではCRCを構成する2バイトを入れ替えている。
> ---
> [巡回冗長検査 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB)より

という形で記載があった。