MENU
  1. ホーム
  2. 技術情報
  3. CRCを付加してデータのやり取りを確実に行う

CRCを付加してデータのやり取りを確実に行う

技術情報

巡回冗長検査（じゅんかいじょうちょうけんさ、Cyclic Redundancy Check：CRC）は、取得したデータに異常がないことを確認するために用いる誤り検出符号です。主にデータ通信の分野でよく用いられていて、USBやBluetooth、TCP/IPからCANやModbusまで主要なプロトコルに採用されています。またデータ通信以外でも、不揮発性メモリーなどに記録するデータに付加したりもします。

あわせて読みたい
Modbus 通信プロトコル Modbusとは Modbus（モドバス）は、Modicon社が同社のPLC（ピーエルシー：Programmable Logic Controller）向けに策定した通信プロトコルです。仕様が公開されていてか…
目次

CRCの計算サイト

ちょっとお試しでCRCを計算したいときは、下記のウェブサイトがおすすめです。JavaScriptでCRCの計算を行ってくれます。またCRCテーブルも表示するので、ソースコードに埋め込むのに利用できます。

Sunshine's Homepage – Online CRC Calculator Javascript

CRCがあるとき、ないとき

それではCRCがあると、どういうメリットがあるのか見て行きましょう。

CRCがないとき

明日の集合は何時だっけ？

8時50分だよ

今8時50分って言ったかな？

もう1回お願い！

8時50分だよ

やっぱり8時50分だ

わかった、8時50分だね

通信途中のデータは、ノイズ等の影響を受けて崩れることがあります。このため正しくデータを受け取れたかを確認するためには、最低2回はデータを受け取って一致することを確認しないといけません。しかしデータの送受信を2往復するのはとても時間が掛かります。またトラフィックが増大するという問題もあります。

CRCがあるとき

明日の集合は何時だっけ？

8時50分 [CRC : ABCD] だよ

今8時50分って聞こえたけどあってるかな？
CRCを計算してみよう

CRCがABCDになった、一致してる！

わかった、8時50分だね

このようにデータにCRCを付加すると、受け取った側でデータの成否を判断できます。CRCを計算する処理時間は必要になりますが、データの送受信を2往復するのに比べればはるかに短い時間で済むのです。

CRCの設定

CRCにはいくつかの設定があります。これらを送信側と受信側で揃えることで、初めてCRCは機能します。

  1. ビット数
    まずは検査対象とする最大データ長に合わせて、ビット数を下記のとおり決定します。
    256バイト以下：CRC-8
    512バイト以下：CRC-16
    1024バイト以下：CRC-32
    2048バイト以下：CRC-64
  2. 生成多項式
    ビット数毎に代表的な多項式がすでにあるので、その中から選択するのが良いかと思います。Wikipediaにいくつか代表例があるので参考にしてください。
  3. その他
    代表例から選択すると基本的に考えるまでもなく決まりますが、下記の設定が必要です。
    ・初期値
    ・シフト方向
    ・出力XOR
    ・入力反転有無
    ・出力反転有無

サンプルコード

[crc.c]

/**
 * @file crc.c
 * @brief CRC
 */

//------------------------------------------------------------------------------
// include
//------------------------------------------------------------------------------
#include "crc.h"
#include "bitwise.h"

/** ----------------------------------------------------------------------------
 * @brief CRC-8テーブルの作成
 *
 * @param [in] param : 演算設定
 */
void Make_CRC8Table(const CRC8_PARAMETER *param)
{
  uint8_t  c, j;
  uint16_t i;

  if (param->shift_dir == ShiftLeft) {
    for (i = 0; i < 256; i++) {
      c = (uint8_t)i;
      for (j = 0; j < 8; j++) {
        if ((uint8_t)(c & 0x80) == 0U) {
          c <<= 1;
        } else {
          c = (uint8_t)(c << 1) ^ param->polynomial;
        }
      }
      param->ptable[i] = c;
    }
  } else {
    for (i = 0; i < 256; i++) {
      c = (uint8_t)i;
      for (j = 0; j < 8; j++) {
        if ((uint8_t)(c & 0x01) == 0U) {
          c >>= 1;
        } else {
          c = param->polynomial ^ (uint8_t)(c >> 1);
        }
      }
      param->ptable[i] = c;
    }
  }
}

/** ----------------------------------------------------------------------------
 * @brief CRC-16テーブルの作成
 *
 * @param [in] param : 演算設定
 */
void Make_CRC16Table(const CRC16_PARAMETER *param)
{
  uint8_t  j;
  uint16_t c;
  uint16_t i;

  if (param->shift_dir == ShiftLeft) {
    for (i = 0; i < 256; i++) {
      c = (uint16_t)(i << 8);
      for (j = 0; j < 8; j++) {
        if ((uint16_t)(c & 0x8000) == 0U) {
          c <<= 1;
        } else {
          c = (uint16_t)(c << 1) ^ param->polynomial;
        }
      }
      param->ptable[i] = c;
    }
  } else {
    for (i = 0; i < 256; i++) {
      c = i;
      for (j = 0; j < 8; j++) {
        if ((uint16_t)(c & 0x0001) == 0U) {
          c >>= 1;
        } else {
          c = param->polynomial ^ (uint16_t)(c >> 1);
        }
      }
      param->ptable[i] = c;
    }
  }
}

/** ----------------------------------------------------------------------------
 * @brief CRC-32テーブルの作成
 *
 * @param [in] param : 演算設定
 */
void Make_CRC32Table(const CRC32_PARAMETER *param)
{
  uint8_t  j;
  uint32_t c;
  uint32_t i;

  if (param->shift_dir == ShiftLeft) {
    for (i = 0; i < 256; i++) {
      c = (uint32_t)(i << 24);
      for (j = 0; j < 8; j++) {
        if ((uint32_t)(c & 0x80000000) == 0UL) {
          c <<= 1;
        } else {
          c = (uint32_t)(c << 1) ^ param->polynomial;
        }
      }
      param->ptable[i] = c;
    }
  } else {
    for (i = 0; i < 256; i++) {
      c = i;
      for (j = 0; j < 8; j++) {
        if ((uint32_t)(c & 0x00000001) == 0UL) {
          c >>= 1;
        } else {
          c = param->polynomial ^ (uint32_t)(c >> 1);
        }
      }
      param->ptable[i] = c;
    }
  }
}

/** ----------------------------------------------------------------------------
 * @brief CRC-8の計算
 *
 * @param [in] buf : データ
 * @param len : データ長
 * @param [in] param : 演算設定
 * @return CRC-8
 */
uint8_t Calc_CRC8(const uint8_t buf[], size_t len, const CRC8_PARAMETER *param)
{
  uint8_t c = param->initial_value;
  uint8_t tmp;
  size_t  i;

  if (param->shift_dir == ShiftLeft) {
    for (i = 0; i < len; i++) {
      tmp = buf[i];
      if (param->reflect_input == true) {
        tmp = Reverse_Bit8(tmp);
      }
      c = param->ptable[c ^ tmp];
    }
  } else {
    for (i = 0; i < len; i++) {
      tmp = buf[i];
      if (param->reflect_input == true) {
        tmp = Reverse_Bit8(tmp);
      }
      c = param->ptable[c ^ tmp] ^ c;
    }
  }

  c ^= param->final_xor;

  if (param->reflect_output == true) {
    c = Reverse_Bit8(c);
  }

  return c;
}

/** ----------------------------------------------------------------------------
 * @brief CRC-16の計算
 *
 * @param [in] buf : データ
 * @param len : データ長
 * @param [in] param : 演算設定
 * @return CRC-16
 */
uint16_t Calc_CRC16(const uint8_t buf[], size_t len, const CRC16_PARAMETER *param)
{
  uint8_t  adr, tmp;
  uint16_t c = param->initial_value;
  size_t   i;

  if (param->shift_dir == ShiftLeft) {
    for (i = 0; i < len; i++) {
      tmp = buf[i];
      if (param->reflect_input == true) {
        tmp = Reverse_Bit8(tmp);
      }
      adr = (uint8_t)((uint8_t)(c >> 8) ^ tmp) & 0xff;
      c   = (uint16_t)(c << 8) ^ param->ptable[adr];
    }
  } else {
    for (i = 0; i < len; i++) {
      tmp = buf[i];
      if (param->reflect_input == true) {
        tmp = Reverse_Bit8(tmp);
      }
      adr = (uint8_t)(c ^ tmp) & 0xFF;
      c   = param->ptable[adr] ^ (uint16_t)(c >> 8);
    }
  }

  c ^= param->final_xor;

  if (param->reflect_output == true) {
    c = Reverse_Bit16(c);
  }

  return c;
}

/** ----------------------------------------------------------------------------
 * @brief CRC-32の計算
 *
 * @param [in] buf : データ
 * @param len : データ長
 * @param [in] param : 演算設定
 * @return CRC-32
 */
uint32_t Calc_CRC32(const uint8_t buf[], size_t len, const CRC32_PARAMETER *param)
{
  uint8_t  adr, tmp;
  uint32_t c = param->initial_value;
  size_t   i;

  if (param->shift_dir == ShiftLeft) {
    for (i = 0; i < len; i++) {
      tmp = buf[i];
      if (param->reflect_input == true) {
        tmp = Reverse_Bit8(tmp);
      }
      adr = (uint8_t)((uint8_t)(c >> 24) ^ tmp) & 0xff;
      c   = (uint32_t)(c << 8) ^ param->ptable[adr];
    }
  } else {
    for (i = 0; i < len; i++) {
      tmp = buf[i];
      if (param->reflect_input == true) {
        tmp = Reverse_Bit8(tmp);
      }
      adr = (uint8_t)(c ^ tmp) & 0xFF;
      c   = param->ptable[adr] ^ (uint32_t)(c >> 8);
    }
  }

  c ^= param->final_xor;

  if (param->reflect_output == true) {
    c = Reverse_Bit32(c);
  }

  return c;
}

[crc.h]

#ifndef CRCH
#define CRCH

#ifdef __cplusplus
extern "C" {
#endif

//------------------------------------------------------------------------------
// include
//------------------------------------------------------------------------------
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

//------------------------------------------------------------------------------
// define
//------------------------------------------------------------------------------
//! シフト方向
typedef enum
{
  ShiftLeft,  //!< 左シフト
  ShiftRight  //!< 右シフト
} SHIFT_DIRECTION;

//! CRC-8の演算パラメーター
typedef struct
{
  bool     reflect_input;   //!< 入力反転 [true=Yes / false=No]
  bool     reflect_output;  //!< 出力反転 [true=Yes / false=No]
  uint8_t  polynomial;      //!< 多項式
  uint8_t  initial_value;   //!< 初期値
  uint8_t  final_xor;       //!< 出力XOR
  uint8_t *ptable;          //!< テーブルのポインター

  SHIFT_DIRECTION shift_dir;  //!< シフト方向
} CRC8_PARAMETER;

//! CRC-16の演算パラメーター
typedef struct
{
  bool      reflect_input;   //!< 入力反転 [true=Yes / false=No]
  bool      reflect_output;  //!< 出力反転 [true=Yes / false=No]
  uint16_t  polynomial;      //!< 多項式
  uint16_t  initial_value;   //!< 初期値
  uint16_t  final_xor;       //!< 出力XOR
  uint16_t *ptable;          //!< テーブルのポインター

  SHIFT_DIRECTION shift_dir;  //!< シフト方向
} CRC16_PARAMETER;

//! CRC-32の演算パラメーター
typedef struct
{
  bool      reflect_input;   //!< 入力反転 [true=Yes / false=No]
  bool      reflect_output;  //!< 出力反転 [true=Yes / false=No]
  uint32_t  polynomial;      //!< 多項式
  uint32_t  initial_value;   //!< 初期値
  uint32_t  final_xor;       //!< 出力XOR
  uint32_t *ptable;          //!< テーブルのポインター

  SHIFT_DIRECTION shift_dir;  //!< シフト方向
} CRC32_PARAMETER;

//------------------------------------------------------------------------------
// function
//------------------------------------------------------------------------------
void Make_CRC8Table(const CRC8_PARAMETER *param);
void Make_CRC16Table(const CRC16_PARAMETER *param);
void Make_CRC32Table(const CRC32_PARAMETER *param);

uint8_t  Calc_CRC8(const uint8_t buf[], size_t len, const CRC8_PARAMETER *param);
uint16_t Calc_CRC16(const uint8_t buf[], size_t len, const CRC16_PARAMETER *param);
uint32_t Calc_CRC32(const uint8_t buf[], size_t len, const CRC32_PARAMETER *param);

#ifdef __cplusplus
}
#endif

#endif

「bitwise.h」については下記ページを参照してください。

あわせて読みたい
ビット演算とその実践的な使い方 | C言語 C言語では、四則演算以外にビット単位での演算も行うことができます。そのとき用いるのがビット演算子で、デジタル回路のAND回路やOR回路と同じ働きをします。 演算子記…

サンプルコードの使用例

使用例代わりに、CppUTestによるテストコードを掲載しておきます。

CRCを計算する際には、処理速度を上げるために変換テーブルを用いるのが一般的です。この変換テーブルを作成するのが「Make_CRCxxTable」であり、CRC演算を行うまでに1度だけ実行しておく必要があります。

#include "CppUTest/TestHarness.h"

#include "crc.h"

// clang-format off
TEST_GROUP(crc){
  TEST_SETUP(){
  }

  TEST_TEARDOWN(){
  }
};
// clang-format on

TEST(crc, Test_CRC8_Maxim)
{
  uint8_t data[] = "123456789";
  uint8_t crc8;
  uint8_t table[256];

  CRC8_PARAMETER crc_param;
  crc_param.reflect_input  = true;
  crc_param.reflect_output = true;
  crc_param.polynomial     = 0x31;
  crc_param.initial_value  = 0x00;
  crc_param.final_xor      = 0x00;
  crc_param.ptable         = table;
  crc_param.shift_dir      = ShiftLeft;

  Make_CRC8Table(&crc_param);
  crc8 = Calc_CRC8(data, 9, &crc_param);
  UNSIGNED_LONGS_EQUAL(crc8, 0xA1);
}
TEST(crc, Test_CRC16_Modbus)
{
  uint8_t  data[] = "123456789";
  uint16_t crc16;
  uint16_t table[256];

  CRC16_PARAMETER crc_param;
  crc_param.reflect_input  = true;
  crc_param.reflect_output = true;
  crc_param.polynomial     = 0x8005;
  crc_param.initial_value  = 0xffff;
  crc_param.final_xor      = 0x0000;
  crc_param.ptable         = table;
  crc_param.shift_dir      = ShiftLeft;

  Make_CRC16Table(&crc_param);
  crc16 = Calc_CRC16(data, 9, &crc_param);
  UNSIGNED_LONGS_EQUAL(crc16, 0x4B37);
}
TEST(crc, Test_CRC32)
{
  uint8_t  data[] = "123456789";
  uint32_t crc32;
  uint32_t table[256];

  CRC32_PARAMETER crc_param;
  crc_param.reflect_input  = true;
  crc_param.reflect_output = true;
  crc_param.polynomial     = 0x04C11DB7;
  crc_param.initial_value  = 0xffffffff;
  crc_param.final_xor      = 0xffffffff;
  crc_param.ptable         = table;
  crc_param.shift_dir      = ShiftLeft;

  Make_CRC32Table(&crc_param);
  crc32 = Calc_CRC32(data, 9, &crc_param);
  UNSIGNED_LONGS_EQUAL(crc32, 0xCBF43926);
}
あわせて読みたい
CppUTestでC/C++コードをテストする CppUTestは、単体テストを自動化するためのフリーソフトウェアです。 C/C++は非常に自由度が高く何でもできる反面、ちょっとしたミスですぐに不具合を起こします。この…

CRCテーブルの保持先

上記使用例では、CRCテーブルを変数に格納しています。これがRAM容量の少ないマイコンでは大きな障害となります。CRC-32では、テーブルだけで1KBも消費してしまうのです。この対策として次の2つの手段があります。

変換テーブルをROMに格納する

テーブルをRAMで持つのではなく、ROMに持たせます。通常一製品内で使用するCRCの種類は1つか2つ程度で、かつ生成多項式は固定です。このため下記のように定数として定義することで、テーブルをROMに持たせることができます。

// CRC-16-Modbus
const uint16_t crc16_table[256] = {
  0x0000, 0x8005, 0x800F, 0x000A, 0x801B, 0x001E, 0x0014, 0x8011,
  0x8033, 0x0036, 0x003C, 0x8039, 0x0028, 0x802D, 0x8027, 0x0022,
  0x8063, 0x0066, 0x006C, 0x8069, 0x0078, 0x807D, 0x8077, 0x0072,
  0x0050, 0x8055, 0x805F, 0x005A, 0x804B, 0x004E, 0x0044, 0x8041,
  0x80C3, 0x00C6, 0x00CC, 0x80C9, 0x00D8, 0x80DD, 0x80D7, 0x00D2,
  0x00F0, 0x80F5, 0x80FF, 0x00FA, 0x80EB, 0x00EE, 0x00E4, 0x80E1,
  0x00A0, 0x80A5, 0x80AF, 0x00AA, 0x80BB, 0x00BE, 0x00B4, 0x80B1,
  0x8093, 0x0096, 0x009C, 0x8099, 0x0088, 0x808D, 0x8087, 0x0082,
  0x8183, 0x0186, 0x018C, 0x8189, 0x0198, 0x819D, 0x8197, 0x0192,
  0x01B0, 0x81B5, 0x81BF, 0x01BA, 0x81AB, 0x01AE, 0x01A4, 0x81A1,
  0x01E0, 0x81E5, 0x81EF, 0x01EA, 0x81FB, 0x01FE, 0x01F4, 0x81F1,
  0x81D3, 0x01D6, 0x01DC, 0x81D9, 0x01C8, 0x81CD, 0x81C7, 0x01C2,
  0x0140, 0x8145, 0x814F, 0x014A, 0x815B, 0x015E, 0x0154, 0x8151,
  0x8173, 0x0176, 0x017C, 0x8179, 0x0168, 0x816D, 0x8167, 0x0162,
  0x8123, 0x0126, 0x012C, 0x8129, 0x0138, 0x813D, 0x8137, 0x0132,
  0x0110, 0x8115, 0x811F, 0x011A, 0x810B, 0x010E, 0x0104, 0x8101,
  0x8303, 0x0306, 0x030C, 0x8309, 0x0318, 0x831D, 0x8317, 0x0312,
  0x0330, 0x8335, 0x833F, 0x033A, 0x832B, 0x032E, 0x0324, 0x8321,
  0x0360, 0x8365, 0x836F, 0x036A, 0x837B, 0x037E, 0x0374, 0x8371,
  0x8353, 0x0356, 0x035C, 0x8359, 0x0348, 0x834D, 0x8347, 0x0342,
  0x03C0, 0x83C5, 0x83CF, 0x03CA, 0x83DB, 0x03DE, 0x03D4, 0x83D1,
  0x83F3, 0x03F6, 0x03FC, 0x83F9, 0x03E8, 0x83ED, 0x83E7, 0x03E2,
  0x83A3, 0x03A6, 0x03AC, 0x83A9, 0x03B8, 0x83BD, 0x83B7, 0x03B2,
  0x0390, 0x8395, 0x839F, 0x039A, 0x838B, 0x038E, 0x0384, 0x8381,
  0x0280, 0x8285, 0x828F, 0x028A, 0x829B, 0x029E, 0x0294, 0x8291,
  0x82B3, 0x02B6, 0x02BC, 0x82B9, 0x02A8, 0x82AD, 0x82A7, 0x02A2,
  0x82E3, 0x02E6, 0x02EC, 0x82E9, 0x02F8, 0x82FD, 0x82F7, 0x02F2,
  0x02D0, 0x82D5, 0x82DF, 0x02DA, 0x82CB, 0x02CE, 0x02C4, 0x82C1,
  0x8243, 0x0246, 0x024C, 0x8249, 0x0258, 0x825D, 0x8257, 0x0252,
  0x0270, 0x8275, 0x827F, 0x027A, 0x826B, 0x026E, 0x0264, 0x8261,
  0x0220, 0x8225, 0x822F, 0x022A, 0x823B, 0x023E, 0x0234, 0x8231,
  0x8213, 0x0216, 0x021C, 0x8219, 0x0208, 0x820D, 0x8207, 0x0202,
};
テーブルを使用しない

ROMにもRAMにも余裕がない場合、テーブルを使用せずビット演算するという方法もあります。ここでは紹介しませんが、演算速度を犠牲にすることで取れる対策があることを、記憶の片隅に留めておくと良いでしょう。

技術情報
CppUTest Doxygen サンプルコード
目次