Slicing-By-19 で実装した CRC-32 (32ビット長の巡回冗長検査)

これは2006年にインテルが発表した Slicing-By-4、Slicing-By-8 アルゴリズムの変わり種となるものです。

Slicing-By-19 です。16の誤植ではありません。16進数表記だと 0x13 であり、2進数表記だと 0b10011 です。

バイトオーダに依存しない設計となっており、ミドルエンディアンの機種でもそのまま安心してご利用いただけます。

C99 対応コンパイラでお試しください。

ソースコードの解説はありません。アルゴリズムの解説については、Slicing-By-4 や Slicing-By-8 についてお調べ下さい。

crc32.c

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

#define POLYNOMIAL 0x04C11DB7ul
#define REFLECTED_POLYNOMIAL 0xEDB88320ul

enum {
  SLICING_SIZE = 19,
};

typedef uint32_t crc32_table_t[256];

const crc32_table_t *
crc32_table(void)
{
  static crc32_table_t table[SLICING_SIZE];

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

  for (int i = 0; i < 256; i ++) {
    uint32_t r = i;
    for (int j = 0; j < 8; j ++) {
      if ((r & 1) == 0) {
        r >>= 1;
      } else {
        r = (r >> 1) ^ REFLECTED_POLYNOMIAL;
      }
    }
    table[0][i] = r;
  }

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

  return table;
}

uint32_t
crc32(const void *ptr, size_t len, uint32_t prevcrc)
{
  uint32_t state = ~prevcrc;
  const uint8_t *p = (const uint8_t *)ptr;
  const uint8_t *end = p + len;

  const crc32_table_t *table = crc32_table();

  const uint8_t *end_slicing = p + len / SLICING_SIZE * SLICING_SIZE;
  for (; p < end_slicing; p += SLICING_SIZE) {
    state = table[18][p[ 0] ^ ((state >>  0) & 0xff)] ^
            table[17][p[ 1] ^ ((state >>  8) & 0xff)] ^
            table[16][p[ 2] ^ ((state >> 16) & 0xff)] ^
            table[15][p[ 3] ^ ((state >> 24) & 0xff)] ^
            table[14][p[ 4]                         ] ^
            table[13][p[ 5]                         ] ^
            table[12][p[ 6]                         ] ^
            table[11][p[ 7]                         ] ^
            table[10][p[ 8]                         ] ^
            table[ 9][p[ 9]                         ] ^
            table[ 8][p[10]                         ] ^
            table[ 7][p[11]                         ] ^
            table[ 6][p[12]                         ] ^
            table[ 5][p[13]                         ] ^
            table[ 4][p[14]                         ] ^
            table[ 3][p[15]                         ] ^
            table[ 2][p[16]                         ] ^
            table[ 1][p[17]                         ] ^
            table[ 0][p[18]                         ];
  }

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

  return ~state;
}

お遊びで Slicing-By-99 に改造してみるのもいいかもしれません。

(おまけ) Slicing-By-2 と Slicing-By-3 による実装

前述した crc32.c との差分です。

Slicing-By-2

diff

--- crc32.c
+++ crc32by2.c
@@ -5,7 +5,7 @@
 #define REFLECTED_POLYNOMIAL 0xEDB88320ul

 enum {
-  SLICING_SIZE = 19,
+  SLICING_SIZE = 2,
 };

 typedef uint32_t crc32_table_t[256];
@@ -52,25 +52,9 @@

   const uint8_t *end_slicing = p + len / SLICING_SIZE * SLICING_SIZE;
   for (; p < end_slicing; p += SLICING_SIZE) {
-    state = table[18][p[ 0] ^ ((state >>  0) & 0xff)] ^
-            table[17][p[ 1] ^ ((state >>  8) & 0xff)] ^
-            table[16][p[ 2] ^ ((state >> 16) & 0xff)] ^
-            table[15][p[ 3] ^ ((state >> 24) & 0xff)] ^
-            table[14][p[ 4]                         ] ^
-            table[13][p[ 5]                         ] ^
-            table[12][p[ 6]                         ] ^
-            table[11][p[ 7]                         ] ^
-            table[10][p[ 8]                         ] ^
-            table[ 9][p[ 9]                         ] ^
-            table[ 8][p[10]                         ] ^
-            table[ 7][p[11]                         ] ^
-            table[ 6][p[12]                         ] ^
-            table[ 5][p[13]                         ] ^
-            table[ 4][p[14]                         ] ^
-            table[ 3][p[15]                         ] ^
-            table[ 2][p[16]                         ] ^
-            table[ 1][p[17]                         ] ^
-            table[ 0][p[18]                         ];
+    state = table[ 1][p[ 0] ^ ((state >>  0) & 0xff)] ^
+            table[ 0][p[ 1] ^ ((state >>  8) & 0xff)] ^
+            (state >> 16);
   }

   for (; p < end; p ++) {

Slicing-By-3

diff

--- crc32.c
+++ crc32by3.c
@@ -5,7 +5,7 @@
 #define REFLECTED_POLYNOMIAL 0xEDB88320ul

 enum {
-  SLICING_SIZE = 19,
+  SLICING_SIZE = 3,
 };

 typedef uint32_t crc32_table_t[256];
@@ -52,25 +52,10 @@

   const uint8_t *end_slicing = p + len / SLICING_SIZE * SLICING_SIZE;
   for (; p < end_slicing; p += SLICING_SIZE) {
-    state = table[18][p[ 0] ^ ((state >>  0) & 0xff)] ^
-            table[17][p[ 1] ^ ((state >>  8) & 0xff)] ^
-            table[16][p[ 2] ^ ((state >> 16) & 0xff)] ^
-            table[15][p[ 3] ^ ((state >> 24) & 0xff)] ^
-            table[14][p[ 4]                         ] ^
-            table[13][p[ 5]                         ] ^
-            table[12][p[ 6]                         ] ^
-            table[11][p[ 7]                         ] ^
-            table[10][p[ 8]                         ] ^
-            table[ 9][p[ 9]                         ] ^
-            table[ 8][p[10]                         ] ^
-            table[ 7][p[11]                         ] ^
-            table[ 6][p[12]                         ] ^
-            table[ 5][p[13]                         ] ^
-            table[ 4][p[14]                         ] ^
-            table[ 3][p[15]                         ] ^
-            table[ 2][p[16]                         ] ^
-            table[ 1][p[17]                         ] ^
-            table[ 0][p[18]                         ];
+    state = table[ 2][p[ 0] ^ ((state >>  0) & 0xff)] ^
+            table[ 1][p[ 1] ^ ((state >>  8) & 0xff)] ^
+            table[ 0][p[ 2] ^ ((state >> 16) & 0xff)] ^
+            (state >> 24);
   }

   for (; p < end; p ++) {

---

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