PNGで使うCRC32を計算する

# はじめに

この記事では、1バイト = 8ビットとします。

# CRCとは

CRCは巡回冗長検査(Cyclic Redundancy Check)とも呼ばれ、データの破損を検出するためのチェックディジットの一種です。
基本的には、以下の手順で計算できます。

1. 計算に使用するマジックナンバーを決める
2. CRCの値を格納する変数を0で初期化する
3. データのバイト列(ビット列)をCRCの値に下から順番にシフトし、流し込んでいく
4. シフトしたときに上からあふれたのが1ならCRCの値にマジックナンバーをXORし、0ならXORしない

参考 : [ContentsCRC](http://page.freett.com/seaside/vip/crc/CRC.htm)
[巡回冗長検査 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB)

```
初期化直後の状態

   CRCの値                            データ(ASCIIで「IEND」)
  +---------------+---------------+  +---------------+---------------+---------------+---------------+
  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|<-|0 1 0 0 1 0 0 1|0 1 0 0 0 1 0 1|0 1 0 0 1 1 1 0|0 1 0 0 0 1 0 0|
  +---------------+---------------+  +---------------+---------------+---------------+---------------+

   マジックナンバー 0x1021
  +---------------+---------------+
  |0 0 0 1 0 0 0 0|0 0 1 0 0 0 0 1|
  +---------------+---------------+

データを1ビットシフトする

   CRCの値                            データ
  +---------------+---------------+  +-------------+---------------+---------------+---------------+
  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|<-|1 0 0 1 0 0 1|0 1 0 0 0 1 0 1|0 1 0 0 1 1 1 0|0 1 0 0 0 1 0 0|
  +---------------+---------------+  +-------------+---------------+---------------+---------------+

データをもう1ビットシフトする

   CRCの値                            データ
  +---------------+---------------+  +-----------+---------------+---------------+---------------+
  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 1|<-|0 0 1 0 0 1|0 1 0 0 0 1 0 1|0 1 0 0 1 1 1 0|0 1 0 0 0 1 0 0|
  +---------------+---------------+  +-----------+---------------+---------------+---------------+

もう14ビットシフトする

   CRCの値                            データ
  +---------------+---------------+  +---------------+---------------+
  |0 1 0 0 1 0 0 1|0 1 0 0 0 1 0 1|<-|0 1 0 0 1 1 1 0|0 1 0 0 0 1 0 0|
  +---------------+---------------+  +---------------+---------------+

もう1ビットシフトする

   CRCの値                            データ
  +---------------+---------------+  +-------------+---------------+
  |1 0 0 1 0 0 1 0|1 0 0 0 1 0 1 0|<-|1 0 0 1 1 1 0|0 1 0 0 0 1 0 0|
  +---------------+---------------+  +-------------+---------------+

もう1ビットシフトすると、1があふれた

   CRCの値                            データ
  +---------------+---------------+  +-----------+---------------+
  |0 0 1 0 0 1 0 1|0 0 0 1 0 1 0 1|<-|0 0 1 1 1 0|0 1 0 0 0 1 0 0|
  +---------------+---------------+  +-----------+---------------+

   マジックナンバー 0x1021
  +---------------+---------------+
  |0 0 0 1 0 0 0 0|0 0 1 0 0 0 0 1|
  +---------------+---------------+

そこで、CRCの値にマジックナンバーをXORする

   CRCの値                            データ
  +---------------+---------------+  +-----------+---------------+
  |0 0 1 1 0 1 0 1|0 0 1 1 0 1 0 0|<-|0 0 1 1 1 0|0 1 0 0 0 1 0 0|
  +---------------+---------------+  +-----------+---------------+

このような「データの最後までシフトして1があふれたらXORする」をデータの最後まで繰り返すと、CRCが計算できる
```

# PNGで使うCRC32

[RFC2083 PNG (Portable Network Graphics) Specification Version 1.0](http://www.ietf.org/rfc/rfc2083.txt) を見てみましょう。

> 3.4. CRC algorithm
> 
>    Chunk CRCs are calculated using standard CRC methods with pre and
>    post conditioning, as defined by ISO 3309 [ISO-3309] or ITU-T V.42
>    [ITU-V42].  The CRC polynomial employed is
> 
>       x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1
> 
>    The 32-bit CRC register is initialized to all 1's, and then the
>    data from each byte is processed from the least significant bit
>    (1) to the most significant bit (128).  After all the data bytes
>    are processed, the CRC register is inverted (its ones complement
>    is taken).  This value is transmitted (stored in the file) MSB
>    first.  For the purpose of separating into bytes and ordering, the
>    least significant bit of the 32-bit CRC is defined to be the
>    coefficient of the x^31 term.
> 
>    Practical calculation of the CRC always employs a precalculated
>    table to greatly accelerate the computation. See Sample CRC Code
>    (Chapter 15).

どうやら0ではなく1に初期化して、各バイトはLSBから入れていくようです。
また、マジックナンバーのnビット目は多項式に`x^n`の項があれば1、なければ0とします。
すると、

```
 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
+---------------+---------------+---------------+---------------+
|0 0 0 0 0 1 0 0|1 1 0 0 0 0 0 1|0 0 0 1 1 1 0 1|1 0 1 1 0 1 1 1|
+---------------+---------------+---------------+---------------+
```

となり、マジックナンバーは`0x04C11DB7`となります。
また、CRCのLSBはなぜか最上位ビットと定義されているので、ひっくり返す処理を入れます。

ちなみに、PNGのチャンクのCRC32は長さ情報は入れず、チャンク名とチャンクのデータのCRC32を計算する
(RFC2083 3.2. Chunk layout)ので、「IEND」のCRC32を計算すると`AE426082`になるはずです。
![png-crc32-20160209.png](https://qiita-image-store.s3.amazonaws.com/0/99656/7eb30b5a-ba22-3355-fce9-a85cae5a5eb3.png)
(使用ソフト : [TSXBIN](http://www.vector.co.jp/soft/win95/util/se094825.html))

## 何も考えずに計算してみる (失敗)
何も考えずに上で説明したCRCの計算方法を実装してみましたが、`650A9A55`と出てきてしまい、うまくいきませんでした。

```c:crc32test0.c
#include <stdio.h>
#include <inttypes.h>

uint32_t reverse(uint32_t x) {
  int i;
  uint32_t res = 0;
  for (i = 0; i < 32; i++) {
    if ((x >> i) & 1) res |= UINT32_C(1) << (31 - i);
  }
  return res;
}

int main(void) {
  const char *d = "IEND";
  uint32_t crc = UINT32_C(0xFFFFFFFF);        /* CRCの値 */
  uint32_t magic = UINT32_C(0x04C11DB7);      /* マジックナンバー */
  int i, j;
  for (i = 0; d[i]; i++) {                    /* データを前から後ろに処理していく */
    for (j = 0; j < 8; j++) {                 /* 各バイトをLSBから順に入れる */
      int b = !!(crc & UINT32_C(0x80000000)); /* 1があふれるかをチェックする */
      crc <<= 1;                              /* シフトする */
      if ((d[i] >> j) & 1) crc |= 1;          /* データのビットを入れる */
      if (b) crc ^= magic;                    /* 1があふれたらマジックナンバーをXORする */
    }
  }
  printf("%08"PRIX32"\n", reverse(~crc));
  return 0;
}
```

## とりあえずまともに計算してみる

なぜ素直に計算しても値が合わなかったのでしょうか？
調べてみると、CRC32では

* 最初は素直に0で初期化する
* データの最初の4バイトをビット反転する
* データの最後に4バイトの0x00を入れる

ということをしないといけないようです。

参考 : [CRC-32](http://www.slideshare.net/7shi/crc32#31)

とりあえず、これをそのまま実装してみます。

```c:crc32test1.c
#include <stdio.h>
#include <inttypes.h>

/* このバイトを処理した後のCRC32の値を計算する */
uint32_t crcnext(uint32_t crc, unsigned char d, uint32_t magic) {
  int i;
  for (i = 0; i < 8; i++) {                 /* LSBから順に処理する */
    int b = !!(crc & UINT32_C(0x80000000)); /* 上から1があふれるかをチェックする */
    crc <<= 1;                              /* シフトする */
    if ((d >> i) & 1) crc |= 1;             /* データのビットを入れる */
    if (b) crc ^= magic;                    /* 上から1があふれたらマジックナンバーをXORする */
  }
  return crc;
}

/* ビットをひっくり返す */
uint32_t reverse(uint32_t x) {
  int i;
  uint32_t res = 0;
  for (i = 0; i < 32; i++) {
    if ((x >> i) & 1) res |= UINT32_C(1) << (31 - i);
  }
  return res;
}

int main(void) {
  const char *d = "IEND";
  uint32_t crc = 0; /* 0で初期化する */
  uint32_t magic = UINT32_C(0x04C11DB7);
  int i, j;
  for (i = 0; d[i]; i++) {
    crc = crcnext(crc, d[i] ^ (i < 4 ? 0xFF : 0), magic); /* 最初の4バイトはビット反転する */
  }
  /* データの最後に4バイトの0x00を入れる */
  for (j = 0; j < 4; j++) {
    crc = crcnext(crc, i + j < 4 ? 0xFF : 0, magic);
  }
  printf("%08"PRIX32"\n", reverse(~crc));
  return 0;
}
```

すると、正しい`AE426082`という値を得ることができました。

## `reverse()`関数を消す

とりあえず正しい値を求めることができましたが、`reverse()`関数の実装が適当なので、これをなんとかしたいです。
そもそも、こんな面倒くさいことをするのはやめてしまいましょう。
最後に反転するのではなく、計算の段階で反転させます。
マジックナンバーの値も反転させておきます。

```
反転前

   CRC32                                                              データ(LSBから先に入れる)
  +---------------+---------------+---------------+---------------+  +---------------+-
  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 1 1 0 1 1 0 1|<-|0 1 0 1 1 1 0 1|  ...
  +---------------+---------------+---------------+---------------+  +---------------+-

   マジックナンバー (0x04C11DB7)
  +---------------+---------------+---------------+---------------+
  |0 0 0 0 0 1 0 0|1 1 0 0 0 0 0 1|0 0 0 1 1 1 0 1|1 0 1 1 0 1 1 1|
  +---------------+---------------+---------------+---------------+

反転後

        データ             CRC
      -+---------------+  +---------------+---------------+---------------+---------------+
  ...  |1 0 1 1 1 0 1 0|->|1 0 1 1 0 1 1 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|
      -+---------------+  +---------------+---------------+---------------+---------------+

                           マジックナンバー (0xEDB88320)
                          +---------------+---------------+---------------+---------------+
                          |1 1 1 0 1 1 0 1|1 0 1 1 1 0 0 0|1 0 0 0 0 0 1 1|0 0 1 0 0 0 0 0|
                          +---------------+---------------+---------------+---------------+
```

この変更を加えても、変わらず正しい`AE426082`という値を得ることができました。

```c:crc32test2.c
#include <stdio.h>
#include <inttypes.h>

/* このバイトを処理した後のCRC32の値を計算する */
uint32_t crcnext(uint32_t crc, unsigned char d, uint32_t magic) {
  int i;
  for (i = 0; i < 8; i++) {                        /* LSBから順に処理する */
    int b = (crc & 1);                             /* 上(反転したので下)から1があふれるかをチェックする */
    crc >>= 1;                                     /* シフトする */
    if ((d >> i) & 1) crc |= UINT32_C(0x80000000); /* データのビットを入れる */
    if (b) crc ^= magic;                           /* 1があふれたらマジックナンバーをXORする */
  }
  return crc;
}

int main(void) {
  const char *d = "IEND";
  uint32_t crc = 0; /* 0で初期化する */
  uint32_t magic = UINT32_C(0xEDB88320); /* 反転したマジックナンバー */
  int i, j;
  for (i = 0; d[i]; i++) {
    crc = crcnext(crc, d[i] ^ (i < 4 ? 0xFF : 0), magic); /* 最初の4バイトはビット反転する */
  }
  /* データの最後に4バイトの0x00を入れる */
  for (j = 0; j < 4; j++) {
    crc = crcnext(crc, i + j < 4 ? 0xFF : 0, magic);
  }
  printf("%08"PRIX32"\n", ~crc);
  return 0;
}
```

## データのビット反転と0x00の追加を消す

`reverse()`の処理を消すことが出来ましたが、正直に言って後処理を消してもあまり嬉しくないです。
やはり計算中の処理を単純にしたいですね。
そこで、今度は「データの最初の4バイトを反転する」という仕様を消します。

まず、「データの最初の4バイトを反転する」という処理を、
「データに『最初の4バイトが0xFF、残りのバイトが全て0x00』というバイト列をXORしたものを投入する」と解釈しなおします。

さらに、バイト列の最初の4バイト、すなわち4バイトの0xFFの部分を最初からCRCの値に投入しておきます。
このとき、CRCの値の初期値は0なので、この投入ではマジックナンバーとのXORは発生しません。

これに対応するため、データのビットの投入の仕方を「CRCの値の最下位(反転後の最上位)に入れる」から
「CRCの値の最上位(反転後の最下位)にXORする」にします。
XORの計算には分配法則や交換法則が成り立つので、このようにしても問題ありません。
この変更では、「データを1ビット投入する→シフトする→1があふれたらマジックナンバーをXORする」という流れは変わりません。

さらに、このようにしておくと、データを最後まで投入するとデータの後ろに4バイトの0x00があるかのような状態になります。
なぜなら、データの後ろにバイト列があったとしても、その値は参照されず、XORされないので、0をXORするのと同じになります。
したがって、データの反転操作を消すついでに、「データの後ろに4バイトの0x00を追加する」という処理も消すことが出来ました。

```
順番を反転して計算を開始する状態

        データ                             CRC
      -+---------------+---------------+  +---------------+---------------+---------------+---------------+
  ...  |1 0 1 1 1 0 1 0|1 0 1 1 0 1 1 0|->|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|
      -+---------------+---------------+  +---------------+---------------+---------------+---------------+

データとビット反転を表すバイト列を分ける

        ビット反転を表すバイト列
      -+---------------+---------------+
  ...  |1 1 1 1 1 1 1 1|1 1 1 1 1 1 1 1|
      -+---------------+---------------+   CRC
                                      |   +---------------+---------------+---------------+---------------+
                                     (+)->|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|
                                      |   +---------------+---------------+---------------+---------------+
      -+---------------+---------------+
  ...  |0 1 0 0 0 1 0 1|0 1 0 0 1 0 0 1|
      -+---------------+---------------+
        データ

データの最初の4バイトをCRCの値に投入した状態

        ビット反転を表すバイト列
      -+---------------+---------------+
  ...  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|
      -+---------------+---------------+   CRC
                                      |   +---------------+---------------+---------------+---------------+
                                     (+)->|1 0 1 1 1 0 1 1|1 0 1 1 0 0 0 1|1 0 1 1 1 0 1 0|1 0 1 1 0 1 1 0|
                                      |   +---------------+---------------+---------------+---------------+
      -+---------------+---------------+
  ...  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|
      -+---------------+---------------+
        データ

データの位置をずらし、反転を表すバイト列の0xFFの部分をCRCの初期値にする

        (ビット反転を表すバイト列)         CRC
      -+---------------+---------------+  +---------------+---------------+---------------+---------------+
  ...  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|->|1 1 1 1 1 1 1 1|1 1 1 1 1 1 1 1|1 1 1 1 1 1 1 1|1 1 1 1 1 1 1 1|
      -+---------------+---------------+  +---------------+---------------+---------------+---------------+
                                                                                                         ^
                                                                                                        (+)
                                                                                                         |
         -+---------------+---------------+---------------+---------------+---------------+---------------+
     ...  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 1 0 0 0 1 0 0|0 1 0 0 1 1 1 0|0 1 0 0 0 1 0 1|0 1 0 0 1 0 0 1|
         -+---------------+---------------+---------------+---------------+---------------+---------------+
           データ

データを最後まで投入すると、ちょうどデータの後ろに4バイトの0x00が追加された状態になる

        (ビット反転を表すバイト列)         CRC
      -+---------------+---------------+  +---------------+---------------+---------------+---------------+
  ...  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|->|0 1 0 1 0 0 0 1|1 0 1 1 1 1 0 1|1 0 0 1 1 1 1 1|0 1 1 1 1 1 0 1|
      -+---------------+---------------+  +---------------+---------------+---------------+---------------+
                                                                                                         ^
                                                                                                        (+)
                                                                                                         |
                         -+---------------+---------------+---------------+---------------+---------------+
                     ...  |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|
                         -+---------------+---------------+---------------+---------------+---------------+
                           データの後ろに仮想的に存在する0x00の列
```

この変更を加えても、変わらず正しい`AE426082`という値を得ることができました。

```c:crc32test3.c
#include <stdio.h>
#include <inttypes.h>

/* このバイトを処理した後のCRC32の値を計算する */
uint32_t crcnext(uint32_t crc, unsigned char d, uint32_t magic) {
  int i;
  for (i = 0; i < 8; i++) {     /* LSBから順に処理する */
    int b;
    if ((d >> i) & 1) crc ^= 1; /* データのビットを最上位(反転したので最下位)にXORで入れる */
    b = (crc & 1);              /* 上(反転したので下)から1があふれるかをチェックする */
    crc >>= 1;                  /* シフトする */
    if (b) crc ^= magic;        /* 1があふれたらマジックナンバーをXORする */
  }
  return crc;
}

int main(void) {
  const char *d = "IEND";
  uint32_t crc = UINT32_C(0xFFFFFFFF);   /* 0xFFFFFFFFで初期化する */
  uint32_t magic = UINT32_C(0xEDB88320); /* 反転したマジックナンバー */
  int i;
  for (i = 0; d[i]; i++) {
    crc = crcnext(crc, d[i], magic); /* 1バイト投入して更新する */
  }
  printf("%08"PRIX32"\n", ~crc);
  return 0;
}
```

## テーブルを導入する

今の実装でも一応CRC32を求めることはできますが、データ1バイトの処理に多くのステップを使い、計算コストが大きくなってしまいます。
そこで、テーブルを利用することで計算コストを下げましょう。

まず、改良した処理の構造をもう一度よく観察してみます。

```
 CRC
+---------------+---------------+---------------+---------------+
|1 1 1 1 1 1 1 1|1 1 1 1 1 1 1 1|1 1 1 1 1 1 1 1|1 1 1 1 1 1 1 1|
+---------------+---------------+---------------+---------------+
                                                               ^
                                                              (+)
                                                               |
                                               -+---------------+
                                           ...  |0 1 0 0 1 0 0 1|
                                               -+---------------+
                                                 データ
```

すると、(反転した)CRCの下位8ビットはデータとXORされますが、
残りの上位24ビットは今扱っているデータの影響を直接受けず、下位8ビットとデータのXORによって決まる値がXORされることがわかります。
また、XOR演算には交換法則や結合法則が成り立つので、データのビットとマジックナンバーのXORの順番が入れ替わっても問題ありません。
したがって、(反転した)CRCの上位24ビットを固定すると、このデータのバイトを処理した後のCRCの値は、
今の(反転した)CRCの下位8ビットとこのデータのバイトのXORによって決まることがわかります。

そこで、上位24ビットを0に固定し、下位8ビットの値256通りそれぞれについて処理した後のCRCの値を計算し、テーブルに入れておきます。
データの処理では、(反転した)CRCの値の下位8ビットとデータのバイトをXORし、その添字でテーブルを引き、
さらに(反転した)CRCの値の上位24ビットとXORをとることで次のCRCの値が計算できます。
このとき、上位24ビットとのXORは、データの処理でCRCが8ビットシフトされているはずなので、
それに合わせてシフトしてからXORをとります。

この変更を加えても、変わらず正しい`AE426082`という値を得ることができました。

```c:crc32test4.c
#include <stdio.h>
#include <inttypes.h>

int main(void) {
  const char *d = "IEND";
  uint32_t crc = UINT32_C(0xFFFFFFFF);   /* 0xFFFFFFFFで初期化する */
  uint32_t magic = UINT32_C(0xEDB88320); /* 反転したマジックナンバー */
  uint32_t table[256];                   /* 下位8ビットに対応する値を入れるテーブル */
  int i, j;

  /* テーブルを作成する */
  for (i = 0; i < 256; i++) {      /* 下位8ビットそれぞれについて計算する */
    uint32_t table_value = i;      /* 下位8ビットを添え字に、上位24ビットを0に初期化する */
    for (j = 0; j < 8; j++) {
      int b = (table_value & 1);   /* 上(反転したので下)から1があふれるかをチェックする */
      table_value >>= 1;           /* シフトする */
      if (b) table_value ^= magic; /* 1があふれたらマジックナンバーをXORする */
    }
    table[i] = table_value;        /* 計算した値をテーブルに格納する */
  }

  /* テーブルを用いてCRC32を計算する */
  for (i = 0; d[i]; i++) {
    crc = table[(crc ^ d[i]) & 0xff] ^ (crc >> 8); /* 1バイト投入して更新する */
  }
  printf("%08"PRIX32"\n", ~crc);
  return 0;
}
```

# まとめ

CRCの基本的な計算方法、誤りをより検出しやすくするためのCRC32における工夫、
そして処理を減らして計算コストを下げる工夫をすることで、
多くのサイトで紹介されているようなテーブルを用いたCRC32の計算方法を導出することができました。