CRCを計算してみた


# 何で？

ん～～
ハッシュコードが欲しかったんです。
でも、MD5とかSHA1とか、そこまで長いのはちょっとねー
もっと手軽なハッシュコード…
あー、CRC！
って訳

一応断っておくと、C#の`GetHashCode()`はダメっすよ。
物凄く偏ったコードを返すので。

# 参考資料

* [wikipediaの奴とか](https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB)
* [七誌さんのSlideShareとか](http://www.slideshare.net/7shi/crc32)
* [kadzusさんちの実装とか](http://d.hatena.ne.jp/kadzus/20100523/1274625686)

# 目指すところ

* wikipediaにある様に、諸々の形式があるのでそこら辺を網羅したいなぁ<br/>8・16・32ビットのCRCを計算できる様にね
* しかも`CRC`クラス一発でそいつらを使い分けられると嬉しいかな
* 右送りとか左送りとかも何のことやら
* InitialマスクとかFinalマスクとかも選択可
* で、忘れてはならないのは、CRCの検算ですね<br/>と云うのも、検算できないと自分の実装が正しいか分からないじゃないですか


* 実装はkadzusさんとこのを踏襲して、`HashAlgorithm`のサブクラスとします！
* 検算系は七誌さんの資料を参考に手探ってみました！

# 実装～

えーと、多項式に詳しい訳でもないので解説は他の方にお願いせざるを得ません…
とか思ったら、もうソースを載せるくらいしかないですね。

てな訳で、まずは定義部分

```csharp:定義部分
public enum CRCbitFeed {
	Left,
	Right,
}

public enum CRCpolynomial : uint {
	CRC8 = 1 << 7 | 1 << 6 | 1 << 4 | 1 << 2 | 1,
	CRC8_ATM = 1 << 2 | 1 << 1 | 1,
	CRC8_CCITT = 1 << 7 | 1 << 3 | 1 << 2 | 1 << 1 | 1,
	CRC8_Dallas = 1 << 5 | 1 << 4 | 1 << 1 | 1,
	CRC8_SEA = 1 << 4 | 1 << 3 | 1 << 2 | 1,
	CRC16 = 1 << 15 | 1 << 2 | 1,
	CRC16_CCITT = 1 << 12 | 1 << 5 | 1,
	CRC16_IBM = CRC16,
	CRC32 = 1 << 26 | 1 << 23 | 1 << 22 | 1 << 16 | 1 << 12 | 1 << 11 | 1 << 10 | 1 << 8 | 1 << 7 | 1 << 5 | 1 << 4 | 1 << 2 | 1 << 1 | 1,
	CRC32_C = 1 << 28 | 1 << 27 | 1 << 26 | 1 << 25 | 1 << 23 | 1 << 22 | 1 << 20 | 1 << 19 | 1 << 18 | 1 << 14 | 1 << 13 | 1 << 11 | 1 << 10 | 1 << 9 | 1 << 8 | 1 << 6 | 1,
	CRC32_K = 1 << 30 | 1 << 29 | 1 << 28 | 1 << 26 | 1 << 20 | 1 << 19 | 1 << 17 | 1 << 16 | 1 << 15 | 1 << 11 | 1 << 10 | 1 << 7 | 1 << 6 | 1 << 4 | 1 << 2 | 1 << 1 | 1,
}
```

`CRCpolynomial`の定義が、`wikipedia`の主な標準CRCに対応している事が分かるかと思います。

で、これをこんな形で使えると良いかなぁ、と…

```csharp:利用方法
using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	byte[] c = crc.ComputeHash(Encoding.Default.GetBytes("abcd"));
	Console.WriteLine(BitConverter.ToString(c));
}
```

そんなこんなでこうなりました。
ざっくり説明すると—

* 割り当てられた多項式をもとにして、`CRC`のサイズを自動判定して変換テーブルを作っちゃう仕様です
* その関係で、ビット送り方向もコンストラクタに与える必要があります<br/>省略時は右送りとなります
* `InitialMask`と`FinalMask`はインスタンス化した後で変更できます<br/>取り敢えず既定値は両方とも`true`です
* `InitialValue`は実装しませんでした
* 検算メソッドについても下のソースに入っていますが、後でちょっと解説しようと思います

```csharp:CRC.cs
public class CRC : HashAlgorithm {
	public CRC(CRCpolynomial poly, CRCbitFeed feed = CRCbitFeed.Right) {
		InitialMask = true;
		FinalMask = true;
		Polynomial = (uint)poly;
		BitFeed = feed;

		base.HashSizeValue = (int)Math.Floor(Math.Log(Polynomial) / Math.Log(2F) / 8 + 1) * 8;
		CRCmask = (uint)Math.Pow(2, base.HashSizeValue) - 1;

		CRCtable = new uint[256];

		if(BitFeed == CRCbitFeed.Left) {
			CRCpoly = Polynomial;
			uint msb = (uint)(1 << (base.HashSizeValue - 1));

			for(uint i = 0; i < 256; i++) {
				uint c = i << (base.HashSizeValue - 8);
				for(int j = 0; j < 8; j++)
					c = (uint)((c << 1) ^ (((c & msb) != 0) ? CRCpoly : 0));
				CRCtable[i] = c & CRCmask;
			}
		} else {
			for(int i = 0; i < base.HashSizeValue; i += 4)
				CRCpoly = (CRCpoly << 4) | Rtbl[(Polynomial >> i) & 0xf];

			for(uint i = 0; i < 256; i++) {
				uint c = i;
				for(int j = 0; j < 8; j++)
					c = (c & 1) != 0 ? (CRCpoly ^ (c >> 1)) : (c >> 1);
				CRCtable[i] = c;
			}
		}

		Initialize();
	}

	uint[] Rtbl = { 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf };

    bool _InitialMask = false;
    public bool InitialMask {
    	get {
    		return _InitialMask;
    	}
    	set {
    		_InitialMask = value;
    		Initialize();
    	}
    }
	public bool FinalMask { get; set; }
	public uint Polynomial { get; private set; }
	public CRCbitFeed BitFeed { get; private set; }

	public int CRCsize {
		get { return base.HashSizeValue / 8; }
	}

	byte[] CRCcrc;
	uint LSTvalue;

	uint CRCmask;
	uint CRCvalue;
	uint CRCpoly;
	uint[] CRCtable;

	protected override void HashCore(byte[] array, int ibStart, int cbSize) {
		unchecked {
			while(--cbSize >= 0)
				CRCvalue = CRCtable[(CRCvalue ^ array[ibStart++]) & 0xff] ^ (CRCvalue >> 8);
		}
		LSTvalue = CRCvalue;
	}

	protected override byte[] HashFinal() {
		HashValue = new byte[CRCsize];

		for(uint i = (uint)HashValue.Length, temp = CRCvalue ^ (FinalMask ? CRCmask : 0); i > 0; temp >>= 8)
			HashValue[--i] = (byte)(temp & 0xff);

		return HashValue;
	}

	public override void Initialize() {
		CRCvalue = InitialMask ? CRCmask : 0;
	}

	public bool ConsistencyCheck(byte[] crc, byte[] buffer) {
		CRCcrc = crc.Reverse().ToArray();
		uint CRCuint = 0;



		CRCvalue = CRCmask;
		ComputeHash(buffer);
		CRCuint = LSTvalue;

		CRCvalue = CRCuint;
		HashCore(CRCcrc, 0, CRCcrc.Length);
		if(CRCvalue == 0)
			return true;

		CRCcrc = CRCcrc.Select(e => (byte)(e ^ 0xff)).ToArray();

		CRCvalue = CRCuint;
		HashCore(CRCcrc, 0, CRCcrc.Length);
		if(CRCvalue == 0)
			return true;



		CRCvalue = 0;
		ComputeHash(buffer);
		CRCuint = LSTvalue;

		CRCvalue = CRCuint;
		HashCore(CRCcrc, 0, CRCcrc.Length);
		if(CRCvalue == 0)
			return true;

		CRCcrc = CRCcrc.Select(e => (byte)(e ^ 0xff)).ToArray();

		CRCvalue = CRCuint;
		HashCore(CRCcrc, 0, CRCcrc.Length);
		if(CRCvalue == 0)
			return true;



		return false;
	}
}
```

で使い方。

```csharp:使い方
byte[] s = Encoding.Default.GetBytes("abcd");
byte[] c;

using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = true;
	crc.FinalMask = true;

	c = crc.ComputeHash(s);
	Console.WriteLine("CRC BitFeed\t= {0}", crc.BitFeed);
	Console.WriteLine("InitialMask\t= {0}", crc.InitialMask);
	Console.WriteLine("FinalMask\t= {0}", crc.FinalMask);
	Console.WriteLine();
	Console.WriteLine(BitConverter.ToString(c));
}

using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = true;
	crc.FinalMask = true;

	Console.WriteLine();
	Console.WriteLine("CRC Check\t: {0}", crc.ConsistencyCheck(c, s));
}
```

実行すると、こんな感じ。

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/8f09d6f7-ced2-568e-189e-f14b2654a382.png)

実は、最初の`using`内でマスクの値をどう変えても、検算メソッドはきちんと判断してくれます。
と云うか、そういう風に作ってみました。

# 検算！

元データにCRCを合体させた全体でCRC計算を行うと、一定値になりまっせー
と云う事らしいです。この一定値をマジックナンバーと呼ぶ、と…

ここで気を付ける点は、CRCは内部的には`uint`で表されていたものをバイト反転して配列として返しているので、合体させるときにもう一回反転してあげないといけないところですね。

で、検算！
確かに、`21-44-DF-1C`ってなってますね。

```csharp:検算①
using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = true;
	crc.FinalMask = true;

	c = crc.ComputeHash(s);
	Console.WriteLine("CRC BitFeed\t= {0}", crc.BitFeed);
	Console.WriteLine("InitialMask\t= {0}", crc.InitialMask);
	Console.WriteLine("FinalMask\t= {0}", crc.FinalMask);
	Console.WriteLine();
	Console.WriteLine(BitConverter.ToString(c));

	Console.WriteLine();
	byte[] d = crc.ComputeHash(s.Concat(c.Reverse()).ToArray());    <== ここね
	Console.WriteLine(BitConverter.ToString(d));
}
```

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/824e4862-c5ad-083c-127a-8a78d699a59a.png)

でも、このマジックナンバーが一定であるとは限らないすよね。
何ちゃらマスクが二つあるので、少なくとも４パターンのマジックナンバーがある筈。

で、剣山！
何とかマスクは両方とも`false`にしてみましょう。

```csharp:検算②
using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = false;
	crc.FinalMask = false;

	c = crc.ComputeHash(s);
	Console.WriteLine("CRC BitFeed\t= {0}", crc.BitFeed);
	Console.WriteLine("InitialMask\t= {0}", crc.InitialMask);
	Console.WriteLine("FinalMask\t= {0}", crc.FinalMask);
	Console.WriteLine();
	Console.WriteLine(BitConverter.ToString(c));

	Console.WriteLine();
	byte[] d = crc.ComputeHash(s.Concat(c.Reverse()).ToArray());
	Console.WriteLine(BitConverter.ToString(d));
}
```

おや？
マジックナンバーがゼロだ。

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/dcc361e0-7f59-e98d-1da4-17b7f4d9d225.png)

そういえば、どこかの記事で`crc`くっつけて新たな`crc`を計算するとそれはゼロになりまーす、と云う記事を見た記憶もあるなぁ…

じゃぁ、さっきのマジックナンバーはどこから来た？
って、そりゃーマスクの関係でしょう。どう繋がってくるかは良く分からないけど、計算過程が異なるから結果も変わってくるんでしょうね。
<br/>
じゃ、ここを起点に色々考えてみましょう。

まず手始めに`InitialMask`が`true`で`FinalMask`が`false`の場合。

```csharp:検算③
using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = true;
	crc.FinalMask = false;

	c = crc.ComputeHash(s);
	Console.WriteLine("CRC BitFeed\t= {0}", crc.BitFeed);
	Console.WriteLine("InitialMask\t= {0}", crc.InitialMask);
	Console.WriteLine("FinalMask\t= {0}", crc.FinalMask);
	Console.WriteLine();
	Console.WriteLine(BitConverter.ToString(c));

	Console.WriteLine();
	byte[] d = crc.ComputeHash(s.Concat(c.Reverse()).ToArray());
	Console.WriteLine(BitConverter.ToString(d));
}
```

問題なし、ゼロになりました。

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/92884bf2-8a40-17a2-b01a-5b13a928ad0f.png)

お次は`InitialMask`が`false`で`FinalMask`が`true`の場合。

```csharp:検算④
using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = false;
	crc.FinalMask = true;

	c = crc.ComputeHash(s);
	Console.WriteLine("CRC BitFeed\t= {0}", crc.BitFeed);
	Console.WriteLine("InitialMask\t= {0}", crc.InitialMask);
	Console.WriteLine("FinalMask\t= {0}", crc.FinalMask);
	Console.WriteLine();
	Console.WriteLine(BitConverter.ToString(c));

	Console.WriteLine();
	byte[] d = crc.ComputeHash(s.Concat(c.Reverse()).ToArray());
	Console.WriteLine(BitConverter.ToString(d));
}
```

ありゃ？
所謂マジックナンバー…

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/86a481ab-9582-fa45-9285-c608801e6e51.png)

んんんー…
お！
`crc`が`FinalMask`でビット逆転しているので、そいつを元に戻せばいいのでは？
よし、じゃぁ見参！

```csharp:検算⑤
using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = false;
	crc.FinalMask = true;

	c = crc.ComputeHash(s);
	Console.WriteLine("CRC BitFeed\t= {0}", crc.BitFeed);
	Console.WriteLine("InitialMask\t= {0}", crc.InitialMask);
	Console.WriteLine("FinalMask\t= {0}", crc.FinalMask);
	Console.WriteLine();
	Console.WriteLine(BitConverter.ToString(c));

	Console.WriteLine();
	byte[] d = crc.ComputeHash(s.Concat(c.Reverse().Select(e => (byte)(e ^ 0xff))).ToArray());    <== そいつ
	Console.WriteLine(BitConverter.ToString(d));
}
```

ん？
微妙…

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/7b306e89-624f-b198-514b-0dc67e7dc6e3.png)

あー、結果の方も`FinalMask`でビット反転してるからだ。
じゃぁ、こう。

```csharp:検算⑥
using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = false;
	crc.FinalMask = true;

	c = crc.ComputeHash(s);
	Console.WriteLine("CRC BitFeed\t= {0}", crc.BitFeed);
	Console.WriteLine("InitialMask\t= {0}", crc.InitialMask);
	Console.WriteLine("FinalMask\t= {0}", crc.FinalMask);
	Console.WriteLine();
	Console.WriteLine(BitConverter.ToString(c));

	Console.WriteLine();
	crc.FinalMask = false;        <==　こう
	byte[] d = crc.ComputeHash(s.Concat(c.Reverse().Select(e => (byte)(e ^ 0xff))).ToArray());
	Console.WriteLine(BitConverter.ToString(d));
}
```

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/77cf75b9-94cb-516a-f928-144618377fac.png)

では最後に`InitialMask`・`FinalMask`ともに`true`の場合。

```csharp:検算⑦
using(CRC crc = new CRC(CRCpolynomial.CRC32)) {
	crc.InitialMask = true;
	crc.FinalMask = true;

	c = crc.ComputeHash(s);
	Console.WriteLine("CRC BitFeed\t= {0}", crc.BitFeed);
	Console.WriteLine("InitialMask\t= {0}", crc.InitialMask);
	Console.WriteLine("FinalMask\t= {0}", crc.FinalMask);
	Console.WriteLine();
	Console.WriteLine(BitConverter.ToString(c));

	Console.WriteLine();
	crc.FinalMask = false;
	byte[] d = crc.ComputeHash(s.Concat(c.Reverse().Select(e => (byte)(e ^ 0xff))).ToArray());
	Console.WriteLine(BitConverter.ToString(d));
}
```

よし！
これで、全パターンの検算結果をゼロで取得することができました。

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/ebe8dcf1-6bcd-ab7a-da74-615508ad7aa2.png)

で、この４パターンの検算を一気に詰め込んだのが`ConsistencyCheck()`メソッドです。
与えられた`crc値`がどんなマスク指定で作成されたものであっても、全パターンのチェックを若干効率的に行ってくれると云う…

# 心残り

と、此処にきて思っちゃったんですが、ビット送り方向指定によっても`crc`値は変わるなぁ。
例えば—

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/e0d02492-dc88-0f62-dbac-5e43c952c2ef.png)

`crc値`は異なりますね。
でも、検算結果はゼロになっているので実装上の問題はなさそうですが、`CRC`クラスをインスタンス化する際の`BitFeed`方向の選択を間違えると、正しく判定できないって事になっちゃうかぁ…

そこまでの自動判定を実現させるなら`CRC`クラスに`ConsistencyCheck()`を実装するんじゃなくて、`CRCconsistencyCheck`クラスにするとかが必要っぽいですね。

と云うような辺りが心残ってしまいました。
<br/>
最後に`CRC`長を変えたパターンのテスト結果を載せて締め括りたいと思います。

![image](https://qiita-image-store.s3.amazonaws.com/0/136132/3dd1e104-ced7-0f0b-1fa0-33a5e604bec3.png)

よしよし、検算結果もゼロなので、実装に問題はないと云う事で良いですね。
では。