4. CRC查表法优化

任务目标

在ECU刷写场景中，CRC计算常位于时间关键路径上。本案例实现CRC-16/MODBUS的查表法版本，并与逐位计算版本进行速度对比，验证查表法在吞吐率上的提升。

实现方案

查表法核心思想：将8位数据的所有256种CRC中间结果预计算存入表，每处理1字节仅需1次查表与2次异或/移位操作，将逐位法的8次循环降为常数时间。两个版本共用相同的多项式0x8005（MSB-first，初始值0xFFFF），保证结果一致。

完整代码（crc_lut.c）

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

#define POLY 0x8005
#define INIT 0xFFFF

// 生成CRC-16/MODBUS查找表（MSB-first）
static uint16_t crc_table[256];
static void table_init(void) {
    for (int i = 0; i < 256; i++) {
        uint16_t crc = (uint16_t)(i << 8);
        for (int bit = 0; bit < 8; bit++) {
            crc = (crc & 0x8000) ? (uint16_t)((crc << 1) ^ POLY) : (uint16_t)(crc << 1);
        }
        crc_table[i] = crc;
    }
}

// 逐位计算版本
static uint16_t crc_bitwise(const uint8_t *data, size_t len) {
    uint16_t crc = INIT;
    for (size_t i = 0; i < len; i++) {
        crc ^= (uint16_t)(data[i] << 8);
        for (int bit = 0; bit < 8; bit++) {
            crc = (crc & 0x8000) ? (uint16_t)((crc << 1) ^ POLY) : (uint16_t)(crc << 1);
        }
    }
    return crc;
}

// 查表法版本
static uint16_t crc_lut(const uint8_t *data, size_t len) {
    uint16_t crc = INIT;
    for (size_t i = 0; i < len; i++) {
        uint8_t idx = (uint8_t)((crc >> 8) ^ data[i]);
        crc = (uint16_t)((crc << 8) ^ crc_table[idx]);
    }
    return crc;
}

// 速度对比测试
int main(void) {
    table_init();
    const size_t LEN = 100000;  // 100KB测试数据
    uint8_t data[LEN];
    for (size_t i = 0; i < LEN; i++) data[i] = (uint8_t)(i * 7 + 3);

    // 正确性验证
    uint16_t crc1 = crc_bitwise(data, LEN);
    uint16_t crc2 = crc_lut(data, LEN);
    printf("bitwise: 0x%04X\n", crc1);
    printf("lut:     0x%04X\n", crc2);
    printf("match:   %s\n", (crc1 == crc2) ? "PASS" : "FAIL");

    // 速度对比（各运行200次取平均）
    const int RUNS = 200;
    clock_t start, end;
    double t_bit = 0, t_lut = 0;

    start = clock();
    for (int r = 0; r < RUNS; r++) crc_bitwise(data, LEN);
    end = clock();
    t_bit = (double)(end - start) / CLOCKS_PER_SEC / RUNS;

    start = clock();
    for (int r = 0; r < RUNS; r++) crc_lut(data, LEN);
    end = clock();
    t_lut = (double)(end - start) / CLOCKS_PER_SEC / RUNS;

    printf("bitwise avg: %.6f s\n", t_bit);
    printf("lut avg:     %.6f s\n", t_lut);
    printf("speedup:     %.2fx\n", t_bit / t_lut);
    return 0;
}

编译与运行

gcc -O2 -o crc_lut crc_lut.c
./crc_lut

验证方法

• 正确性：程序输出match: PASS，且两个CRC值均为0x????格式（具体值由输入数据决定，此处为确定性输出）。
• 性能对比：观察speedup字段，查表法通常比逐位法快3～8倍（实际倍数取决于编译器优化与CPU架构）。
• 判定标准：match: PASS为功能通过；speedup > 1.0为性能提升有效。

关键说明

• 查表法以256×2字节（512B）ROM/RAM换速度，在ECU资源受限时需评估存储开销。
• 本实现为MSB-first（多项式0x8005），若刷写协议使用LSB-first（如CRC-16/CCITT），需重新生成表并调整移位方向。
• 测试数据为确定性伪随机序列，保证两次计算输入一致；实际刷写场景中数据长度通常为几KB到几MB，本测试取100KB代表典型块大小。