LoginSignup
10
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@Toraja

CRCを計算してみた

Posted at

何で？

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

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

参考資料

目指すところ

  • wikipediaにある様に、諸々の形式があるのでそこら辺を網羅したいなぁ
    8・16・32ビットのCRCを計算できる様にね

  • しかもCRCクラス一発でそいつらを使い分けられると嬉しいかな

  • 右送りとか左送りとかも何のことやら

  • InitialマスクとかFinalマスクとかも選択可

  • で、忘れてはならないのは、CRCの検算ですね
    と云うのも、検算できないと自分の実装が正しいか分からないじゃないですか

  • 実装はkadzusさんとこのを踏襲して、HashAlgorithmのサブクラスとします！

  • 検算系は七誌さんの資料を参考に手探ってみました！

実装～

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

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

定義部分
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に対応している事が分かるかと思います。

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

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

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

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

で使い方。

使い方
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

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

検算！

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

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

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

検算①
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

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

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

検算②
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

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

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


じゃ、ここを起点に色々考えてみましょう。

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

検算③
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

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

検算④
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

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

検算⑤
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

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

検算⑥
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

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

検算⑦
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

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

心残り

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

image

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

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

と云うような辺りが心残ってしまいました。


最後にCRC長を変えたパターンのテスト結果を載せて締め括りたいと思います。

image

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

10
11
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?