c - 在 C 中使用反射/位反转输入计算 CRC16

问题描述

我想用（嵌入式）C 以两种不同的方式0x1021从0xC6C6（末尾没有 XOR，也称为 CRC16-A 在此页面https://crccalc.com上）开始计算 CCITT 多项式的反射 CRC16。

对于这两种选择，我想使用从 (= ) 开始的0x1021多项式0xC6C6以及0x8408从0x6363(= reflect(0xC6C6)) 开始的反射多项式。

假设我有每个多项式的查找表：

static const UINT16 au16Table1021[256u]

和

static const UINT16 au16Table8408[256u]

和一个reflect反转字节位顺序的函数（例如，基于在 C/C++ 中，什么是最简单的反转字节中位顺序的方法？）

从如何配置 CRC 表计算wOldCRC = 0xC6C6的公认答案中，我希望通过反映输入、起始 CRC ( 但是，我尝试的第二个选项没有产生预期的结果。我究竟做错了什么？

选项 2 的 CRC 不正确的最小（或多或少）工作示例：

#include <stdio.h>
#include <stdlib.h>
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;

static const uint16_t crcTable1021[256u] = {
  0x0000u, 0x17CEu, 0x0FDFu, 0x1811u, 0x1FBEu, 0x0870u, 0x1061u, 0x07AFu,
  0x1F3Fu, 0x08F1u, 0x10E0u, 0x072Eu, 0x0081u, 0x174Fu, 0x0F5Eu, 0x1890u,
  0x1E3Du, 0x09F3u, 0x11E2u, 0x062Cu, 0x0183u, 0x164Du, 0x0E5Cu, 0x1992u,
  0x0102u, 0x16CCu, 0x0EDDu, 0x1913u, 0x1EBCu, 0x0972u, 0x1163u, 0x06ADu,
  0x1C39u, 0x0BF7u, 0x13E6u, 0x0428u, 0x0387u, 0x1449u, 0x0C58u, 0x1B96u,
  0x0306u, 0x14C8u, 0x0CD9u, 0x1B17u, 0x1CB8u, 0x0B76u, 0x1367u, 0x04A9u,
  0x0204u, 0x15CAu, 0x0DDBu, 0x1A15u, 0x1DBAu, 0x0A74u, 0x1265u, 0x05ABu,
  0x1D3Bu, 0x0AF5u, 0x12E4u, 0x052Au, 0x0285u, 0x154Bu, 0x0D5Au, 0x1A94u,
  0x1831u, 0x0FFFu, 0x17EEu, 0x0020u, 0x078Fu, 0x1041u, 0x0850u, 0x1F9Eu,
  0x070Eu, 0x10C0u, 0x08D1u, 0x1F1Fu, 0x18B0u, 0x0F7Eu, 0x176Fu, 0x00A1u,
  0x060Cu, 0x11C2u, 0x09D3u, 0x1E1Du, 0x19B2u, 0x0E7Cu, 0x166Du, 0x01A3u,
  0x1933u, 0x0EFDu, 0x16ECu, 0x0122u, 0x068Du, 0x1143u, 0x0952u, 0x1E9Cu,
  0x0408u, 0x13C6u, 0x0BD7u, 0x1C19u, 0x1BB6u, 0x0C78u, 0x1469u, 0x03A7u,
  0x1B37u, 0x0CF9u, 0x14E8u, 0x0326u, 0x0489u, 0x1347u, 0x0B56u, 0x1C98u,
  0x1A35u, 0x0DFBu, 0x15EAu, 0x0224u, 0x058Bu, 0x1245u, 0x0A54u, 0x1D9Au,
  0x050Au, 0x12C4u, 0x0AD5u, 0x1D1Bu, 0x1AB4u, 0x0D7Au, 0x156Bu, 0x02A5u,
  0x1021u, 0x07EFu, 0x1FFEu, 0x0830u, 0x0F9Fu, 0x1851u, 0x0040u, 0x178Eu,
  0x0F1Eu, 0x18D0u, 0x00C1u, 0x170Fu, 0x10A0u, 0x076Eu, 0x1F7Fu, 0x08B1u,
  0x0E1Cu, 0x19D2u, 0x01C3u, 0x160Du, 0x11A2u, 0x066Cu, 0x1E7Du, 0x09B3u,
  0x1123u, 0x06EDu, 0x1EFCu, 0x0932u, 0x0E9Du, 0x1953u, 0x0142u, 0x168Cu,
  0x0C18u, 0x1BD6u, 0x03C7u, 0x1409u, 0x13A6u, 0x0468u, 0x1C79u, 0x0BB7u,
  0x1327u, 0x04E9u, 0x1CF8u, 0x0B36u, 0x0C99u, 0x1B57u, 0x0346u, 0x1488u,
  0x1225u, 0x05EBu, 0x1DFAu, 0x0A34u, 0x0D9Bu, 0x1A55u, 0x0244u, 0x158Au,
  0x0D1Au, 0x1AD4u, 0x02C5u, 0x150Bu, 0x12A4u, 0x056Au, 0x1D7Bu, 0x0AB5u,
  0x0810u, 0x1FDEu, 0x07CFu, 0x1001u, 0x17AEu, 0x0060u, 0x1871u, 0x0FBFu,
  0x172Fu, 0x00E1u, 0x18F0u, 0x0F3Eu, 0x0891u, 0x1F5Fu, 0x074Eu, 0x1080u,
  0x162Du, 0x01E3u, 0x19F2u, 0x0E3Cu, 0x0993u, 0x1E5Du, 0x064Cu, 0x1182u,
  0x0912u, 0x1EDCu, 0x06CDu, 0x1103u, 0x16ACu, 0x0162u, 0x1973u, 0x0EBDu,
  0x1429u, 0x03E7u, 0x1BF6u, 0x0C38u, 0x0B97u, 0x1C59u, 0x0448u, 0x1386u,
  0x0B16u, 0x1CD8u, 0x04C9u, 0x1307u, 0x14A8u, 0x0366u, 0x1B77u, 0x0CB9u,
  0x0A14u, 0x1DDAu, 0x05CBu, 0x1205u, 0x15AAu, 0x0264u, 0x1A75u, 0x0DBBu,
  0x152Bu, 0x02E5u, 0x1AF4u, 0x0D3Au, 0x0A95u, 0x1D5Bu, 0x054Au, 0x1284u,
};

static const uint16_t crcTable8408[256u] = {
  0x0000u, 0x1189u, 0x2312u, 0x329Bu, 0x4624u, 0x57ADu, 0x6536u, 0x74BFu,
  0x8C48u, 0x9DC1u, 0xAF5Au, 0xBED3u, 0xCA6Cu, 0xDBE5u, 0xE97Eu, 0xF8F7u,
  0x1081u, 0x0108u, 0x3393u, 0x221Au, 0x56A5u, 0x472Cu, 0x75B7u, 0x643Eu,
  0x9CC9u, 0x8D40u, 0xBFDBu, 0xAE52u, 0xDAEDu, 0xCB64u, 0xF9FFu, 0xE876u,
  0x2102u, 0x308Bu, 0x0210u, 0x1399u, 0x6726u, 0x76AFu, 0x4434u, 0x55BDu,
  0xAD4Au, 0xBCC3u, 0x8E58u, 0x9FD1u, 0xEB6Eu, 0xFAE7u, 0xC87Cu, 0xD9F5u,
  0x3183u, 0x200Au, 0x1291u, 0x0318u, 0x77A7u, 0x662Eu, 0x54B5u, 0x453Cu,
  0xBDCBu, 0xAC42u, 0x9ED9u, 0x8F50u, 0xFBEFu, 0xEA66u, 0xD8FDu, 0xC974u,
  0x4204u, 0x538Du, 0x6116u, 0x709Fu, 0x0420u, 0x15A9u, 0x2732u, 0x36BBu,
  0xCE4Cu, 0xDFC5u, 0xED5Eu, 0xFCD7u, 0x8868u, 0x99E1u, 0xAB7Au, 0xBAF3u,
  0x5285u, 0x430Cu, 0x7197u, 0x601Eu, 0x14A1u, 0x0528u, 0x37B3u, 0x263Au,
  0xDECDu, 0xCF44u, 0xFDDFu, 0xEC56u, 0x98E9u, 0x8960u, 0xBBFBu, 0xAA72u,
  0x6306u, 0x728Fu, 0x4014u, 0x519Du, 0x2522u, 0x34ABu, 0x0630u, 0x17B9u,
  0xEF4Eu, 0xFEC7u, 0xCC5Cu, 0xDDD5u, 0xA96Au, 0xB8E3u, 0x8A78u, 0x9BF1u,
  0x7387u, 0x620Eu, 0x5095u, 0x411Cu, 0x35A3u, 0x242Au, 0x16B1u, 0x0738u,
  0xFFCFu, 0xEE46u, 0xDCDDu, 0xCD54u, 0xB9EBu, 0xA862u, 0x9AF9u, 0x8B70u,
  0x8408u, 0x9581u, 0xA71Au, 0xB693u, 0xC22Cu, 0xD3A5u, 0xE13Eu, 0xF0B7u,
  0x0840u, 0x19C9u, 0x2B52u, 0x3ADBu, 0x4E64u, 0x5FEDu, 0x6D76u, 0x7CFFu,
  0x9489u, 0x8500u, 0xB79Bu, 0xA612u, 0xD2ADu, 0xC324u, 0xF1BFu, 0xE036u,
  0x18C1u, 0x0948u, 0x3BD3u, 0x2A5Au, 0x5EE5u, 0x4F6Cu, 0x7DF7u, 0x6C7Eu,
  0xA50Au, 0xB483u, 0x8618u, 0x9791u, 0xE32Eu, 0xF2A7u, 0xC03Cu, 0xD1B5u,
  0x2942u, 0x38CBu, 0x0A50u, 0x1BD9u, 0x6F66u, 0x7EEFu, 0x4C74u, 0x5DFDu,
  0xB58Bu, 0xA402u, 0x9699u, 0x8710u, 0xF3AFu, 0xE226u, 0xD0BDu, 0xC134u,
  0x39C3u, 0x284Au, 0x1AD1u, 0x0B58u, 0x7FE7u, 0x6E6Eu, 0x5CF5u, 0x4D7Cu,
  0xC60Cu, 0xD785u, 0xE51Eu, 0xF497u, 0x8028u, 0x91A1u, 0xA33Au, 0xB2B3u,
  0x4A44u, 0x5BCDu, 0x6956u, 0x78DFu, 0x0C60u, 0x1DE9u, 0x2F72u, 0x3EFBu,
  0xD68Du, 0xC704u, 0xF59Fu, 0xE416u, 0x90A9u, 0x8120u, 0xB3BBu, 0xA232u,
  0x5AC5u, 0x4B4Cu, 0x79D7u, 0x685Eu, 0x1CE1u, 0x0D68u, 0x3FF3u, 0x2E7Au,
  0xE70Eu, 0xF687u, 0xC41Cu, 0xD595u, 0xA12Au, 0xB0A3u, 0x8238u, 0x93B1u,
  0x6B46u, 0x7ACFu, 0x4854u, 0x59DDu, 0x2D62u, 0x3CEBu, 0x0E70u, 0x1FF9u,
  0xF78Fu, 0xE606u, 0xD49Du, 0xC514u, 0xB1ABu, 0xA022u, 0x92B9u, 0x8330u,
  0x7BC7u, 0x6A4Eu, 0x58D5u, 0x495Cu, 0x3DE3u, 0x2C6Au, 0x1EF1u, 0x0F78u,
};

static uint8_t reverse(uint8_t n) {
   static uint8_t lookup[16] = {
            0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
            0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, };
   uint8_t result;
   result = lookup[n & 0xF] << 4 | lookup[n>>4];
   return result;
}

static uint16_t reverse16(uint16_t n) {
   return reverse(n & 0xFF) << 8 | reverse(n >> 8);
}

uint16_t Calculate(const uint8_t *message, int nBytes, uint16_t wOldCRC) {
    uint8_t data;
    uint16_t remainder = wOldCRC;
    for (int byte = 0; byte < nBytes; ++byte) {
        data = message[byte] ^ remainder;
        remainder = crcTable8408[data] ^ (remainder >> 8);
    }
    return remainder;
}

uint16_t CalculateInv(const uint8_t *message, int nBytes, uint16_t wOldCRC) {
    uint8_t data;
    uint16_t remainder = wOldCRC; //already reversed in function call
    for (int byte = nBytes; byte > 0; --byte) {
        data = reverse(message[byte-1]) ^ remainder;
        remainder = crcTable1021[data] ^ (remainder << 8);
    }
    return reverse16(remainder);
}

int main(void) {
   uint16_t expected = 0x4167;
   uint8_t pattern[] = "Hello World!";

   uint16_t result = Calculate(pattern, 12, 0x6363);
   printf("CRC option 1: 0x%04x, expected 0x%04x\n", result, expected);

   result = CalculateInv(pattern, 12, 0xC6C6);
   printf("CRC option 2: 0x%04X, expected 0x%04X\n", result, expected);

   return EXIT_SUCCESS;
}

输出：

CRC option 1: 0x4167, expected 0x4167
CRC option 2: 0x62FD, expected 0x4167

编辑：我通过稍微修改来自如何配置 CRC 表计算的已接受答案的代码来创建表，如下所示：

uint16_t  crcTable[256];
void Init(uint16_t polynomial) {
    uint16_t  remainder;
    for (int dividend = 0; dividend < 256; ++dividend) {
        remainder = dividend;
        for (uint8_t bit = 8; bit > 0; --bit) {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ polynomial;
            else
                remainder = (remainder >> 1);
        }
        crcTable[dividend] = remainder;
    }

    printf("static const uint_t crcTable[256u] = {");
    for (int i = 0; i<32; ++i) {
       printf("\n  ");
       for (int j=0; j<8; ++j) {
          printf("0x%04Xu, ",crcTable[i*8+j]);
       }
    }
    printf("\n};\n");
}

标签： ccrccrc16

c - 在 C 中使用反射/位反转输入计算 CRC16

问题描述

解决方案

推荐阅读