CRC-CCITTの計算の高速化

ずいぶん前の話だが、CRC-CCITTの計算という記事を書いて、とてつもなくシンプルなソースを出していたのだが、もう少し使えそうな方法として、テーブルを使って計算を高速化する方法を書いてみる。

そのときの記事のソースコードを見てもらえればおわかりになると思うが、計算されるCRCの値は、入力されたデーターのビットとXORして、その結果から多項式のビットとXORをしているというものである。
CRCの値は、XORの計算のみであるため、結合則（(A xor B) xor C = A xor (B xor C)）が成り立つので事前に計算しておくことができる。実際には、初期値0で8ビット分(0～0xFF)の多項式の計算しておき、その結果をテーブルに入れておいて、データーと現在のCRC値の下位8ビットからテーブルのインデックスを割り出し、その結果とCRC値の上位8bitを下位にシフトしたものとXORすればよい。

といった、説明をされても、ピンと来るとは到底思えないので、実際のコードをあげてみる。今回はJavaのクラスにしてみたが、Javaのjava.util.zipというパッケージの中にCRC32というクラスがある。ZIPの仕様はよく知らないのでわからないが、なんだかの初期値と多項式で32ビットのCRCを計算していると思われる。
このパッケージには、checksumというインターフェースがあるので、これを実装することにする。

import java.util.zip.Checksum;

/**
 * Compute CRC16(CRC-CCITT) for a data stream.
 * 
 * @author finky
 * @version 1.0
 * @see java.util.zip.Checksum
 */
public class CRC16 implements Checksum {
 static final int INITIAL_VALUE = 0xffff;
 static final int POLYNOMIAL = 0x8408;
 static final int table[] = new int[256];
 static {
  for (int i=0; i < 256; i++) {
   table[i] = calculate(i, 0);
  }
 }
 private int value;
 /**
  * Creates a new CRC16 object.
  */
 public CRC16() {
  value = INITIAL_VALUE;
 }
 /**
  * Calculate CRC16 for simple algorithm.
  * @param data effective 8bits.
  * @param value CRC value.
  * @return updated CRC16 value.
  */
 private static int calculate(int data, int value) {
  for (int i = 0; i < 8; i++) {
   boolean flag = ((value ^ data) & 0x0001) != 0;
   value >>= 1;
   if (flag) value ^= POLYNOMIAL;
   data >>= 1;
  }
  return value;
 }
 /**
  * Returns CRC16 value.
  * @see java.util.zip.Checksum#getValue()
  */
 public long getValue() {
  // TODO Auto-generated method stub
  return value;
 }

 /**
  * Resets CRC16 to initial value.
  * @see java.util.zip.Checksum#reset()
  */
 public void reset() {
  // TODO Auto-generated method stub
  value = INITIAL_VALUE;
 }

 /**
  * Updates checksum with specified array of bytes.
  * @see java.util.zip.Checksum#update(int)
  */
 public void update(int b) {
  // TODO Auto-generated method stub
  int index = (value ^ b) & 0x00ff;
  value = table[index] ^ (value >> 8);
 }

 /**
  * Updates CRC16 with specified array of bytes.
  * @see java.util.zip.Checksum#update(byte[], int, int)
  */
 public void update(byte[] b, int off, int len) {
  // TODO Auto-generated method stub
  for (int i = 0; i < len; i++) {
   update(b[off + i]);
  }
 }
}

javadoc用のコメントの一部が、JDKのドキュメントのパクリっぽくなっていますが、そのへんはご愛嬌ということでお願いしますw。サンプルソースのつもりなので、適当に使いまわしてもらってかまいませんが、確実に動作するか否かは保障できません（自分的にはちゃんと動いていると思うけど）。