今回取り上げるのは CRC-16-CCITT というもので、mruby のバイトコードファイルでファイルの整合性を確認するためにも使われています。

CRC-32 と比較してみると、ビット長、生成多項式、初期 CRC 値、出力 XOR マスク、入出力ビット順だけが異なるのではありません。

最大の違いは、CRC-32 は入力値の後ろに32ビットの 0 を置きますが、CRC-16-CCITT は入力値の前に16ビットの 0 を置きます。

CRC-32

          ____________________________________________
  [poly] ) [input] 00000000 00000000 00000000 00000000
                                    |
                                    |
                                    |
                            [32 bit remainder]

CRC-16-CCITT

          __________________________
  [poly] ) 00000000 00000000 [input]
                            |
                            |
                            |
                   [16 bit remainder]

今回はインテルが2006年に発表した Slicing-By-4 アルゴリズムを CRC-16-CCITT に適用するというのがテーマです。

ですが、説明がめんどいので実装したソースコードを示し、mruby から~~かっぱらってきた~~拝借した mruby/src/crc.c と結果を比較するだけで終わりとします。

当文書の内容はクリエイティブ・コモンズ・ゼロライセンス CC0 の下でご利用できます。

`crc16ccitt()` の実装

crc16ccitt.c

# include <stdlib.h>
# include <stdint.h>

# define POLYNOMIAL 0x1021u

enum {
  SLICING_SIZE = 4,
};

typedef uint16_t crc16ccitt_table_t[256];

const crc16ccitt_table_t *
crc16ccitt_table(void)
{
  static crc16ccitt_table_t table[SLICING_SIZE];

  if (table[0][1] != 0) {
    return table;
  }

  for (int i = 0; i < 256; i ++) {
    uint16_t r = i << 8;
    for (int j = 0; j < 8; j ++) {
      if ((r & 0x8000u) == 0) {
        r <<= 1;
      } else {
        r = (r << 1) ^ POLYNOMIAL;
      }
    }
    table[0][i] = r & 0xffffu;
  }

  for (int i = 0; i < 256; i ++) {
    for (int s = 1; s < SLICING_SIZE; s ++) {
      uint16_t r = table[s - 1][i];
      table[s][i] = table[0][(r >> 8) & 0xffu] ^ (r << 8);
    }
  }

  return table;
}

uint16_t
crc16ccitt(const void *ptr, size_t len, uint16_t prevcrc)
{
  uint16_t state = prevcrc;
  const uint8_t *p = (const uint8_t *)ptr;
  const uint8_t *end = p + len;

  const crc16ccitt_table_t *table = crc16ccitt_table();

  const uint8_t *end_slicing = p + len / SLICING_SIZE * SLICING_SIZE;
  for (; p < end_slicing; p += SLICING_SIZE) {
    state = table[3][(state >> 8) & 0xff] ^
            table[2][(state >> 0) & 0xff] ^
            table[1][          p[0]     ] ^
            table[0][          p[1]     ] ^
                    ((uint16_t)p[2] << 8) ^
                    ((uint16_t)p[3] << 0);
  }

  for (; p < end; p ++) {
    state = table[0][(state >> 8) & 0xff] ^ (state << 8) ^ *p;
  }

  return state;
}

テスト

crctest.c

# include <stdio.h>
# include <string.h>
# include <stdint.h>

extern uint16_t crc16ccitt(const void *, size_t, uint16_t);
extern uint16_t calc_crc_16_ccitt(const void *, size_t, uint16_t);

int
main(int argc, char *argv[])
{
    const char src[] = "123456789";

    for (int i = strlen(src); i >= 0; i --) {
        printf("0x%04X:0x%04X <= [%s]\n",
                crc16ccitt(&src[i], strlen(&src[i]), 0),
                calc_crc_16_ccitt(&src[i], strlen(&src[i]), 0),
                &src[i]);
    }

    return 0;
}

shell

$ git clone https://github.com/mruby/mruby.git
$ cc -o crctest crctest.c crc16ccitt.c mruby/src/crc.c
$ ./crctest
0x0000:0x0000 <= []
0x0039:0x0039 <= [9]
0x3839:0x3839 <= [89]
0x7E8D:0x7E8D <= [789]
0xD1BE:0xD1BE <= [6789]
0xFFEB:0xFFEB <= [56789]
0x19F3:0x19F3 <= [456789]
0xFBCF:0xFBCF <= [3456789]
0x5F03:0x5F03 <= [23456789]
0xBEEF:0xBEEF <= [123456789]

CRC-16-XMODEM との比較

CRC-16-XMODEM は、CRC-32 のように 0 を詰める位置が入力の後ろとなるだけで、他の要素が CRC-16-CCITT と同じ CRC です。

この CRC-16-XMODEM を Slicing-by-4 で実装した場合とのソースコードの差分を参考までに記します。

diff

--- crc16ccitt.c
+++ crc16xmodem.c
@@ -51,16 +51,14 @@
 
   const uint8_t *end_slicing = p + len / SLICING_SIZE * SLICING_SIZE;
   for (; p < end_slicing; p += SLICING_SIZE) {
-    state = table[3][(state >> 8) & 0xff] ^
-            table[2][(state >> 0) & 0xff] ^
-            table[1][          p[0]     ] ^
-            table[0][          p[1]     ] ^
-                    ((uint16_t)p[2] << 8) ^
-                    ((uint16_t)p[3] << 0);
+    state = table[3][((state >> 8) & 0xff) ^ p[0]] ^
+            table[2][((state >> 0) & 0xff) ^ p[1]] ^
+            table[1][                        p[2]] ^
+            table[0][                        p[3]];
   }
 
   for (; p < end; p ++) {
-    state = table[0][(state >> 8) & 0xff] ^ (state << 8) ^ *p;
+    state = table[0][((state >> 8) & 0xff) ^ *p] ^ (state << 8);
   }
 
   return state;

(おまけ) Slicing-By-7 の実装

ネタにしかならない Slicing-By-7 です。実用する場合は Slicing-By-8 にした方がいいでしょう。

crc16ccitt.c との差分のみです。

diff

--- crc16ccitt.c
+++ crc16ccitt_by7.c
@@ -4,7 +4,7 @@
 #define POLYNOMIAL 0x1021u
 
 enum {
-  SLICING_SIZE = 4,
+  SLICING_SIZE = 7,
 };
 
 typedef uint16_t crc16ccitt_table_t[256];
@@ -51,12 +51,15 @@
 
   const uint8_t *end_slicing = p + len / SLICING_SIZE * SLICING_SIZE;
   for (; p < end_slicing; p += SLICING_SIZE) {
-    state = table[3][(state >> 8) & 0xff] ^
-            table[2][(state >> 0) & 0xff] ^
-            table[1][(uint16_t)p[0]     ] ^
-            table[0][(uint16_t)p[1]     ] ^
-                    ((uint16_t)p[2] << 8) ^
-                    ((uint16_t)p[3] << 0);
+    state = table[6][(state >> 8) & 0xff] ^
+            table[5][(state >> 0) & 0xff] ^
+            table[4][(uint16_t)p[0]     ] ^
+            table[3][(uint16_t)p[1]     ] ^
+            table[2][(uint16_t)p[2]     ] ^
+            table[1][(uint16_t)p[3]     ] ^
+            table[0][(uint16_t)p[4]     ] ^
+                    ((uint16_t)p[5] << 8) ^
+                    ((uint16_t)p[6] << 0);
   }
 
   for (; p < end; p ++) {

To the extent possible under law, dearblue has waived all copyright and related or neighboring rights to this work.