时间戳

首页 > 解决方案 > 如何使用尽可能少的数据将数据缓冲区计算为零校验和值

c++ - 如何使用尽可能少的数据将数据缓冲区计算为零校验和值

问题描述

给定 C++ 中的这个校验和计算函数

int calcCrcPartial(unsigned short* lpdwBlockData, unsigned short dwBlockSizeInBytes, int iInitialCrc)
{
    unsigned short dwBlocksSizeInWords;
    int bIsSigned;
    signed int j;
    signed int i;
    unsigned short dwDataItem;
    bool bIsNegative;

    // number of WORD blocks
    dwBlocksSizeInWords = dwBlockSizeInBytes >> 1;

    for (i = 0; ; ++i)
    {
        if (dwBlocksSizeInWords <= i)
        {
            break;
        }

        dwDataItem = lpdwBlockData[i];

        if (dwDataItem != 0)
        {
            bInvalidCrc = false;
        }

        for (j = 0; j <= 15; ++j)
        {
            bIsSigned = (dwDataItem & 0x8000u) != 0;

            dwDataItem <<= 1;

            bIsNegative = iInitialCrc < 0;

            iInitialCrc <<= 1;
            iInitialCrc += bIsSigned;

            if (bIsNegative)
            {
                iInitialCrc ^= 0x400007u;
            }
        }
    }

    return iInitialCrc;
}

任务：

如何编写一个函数来生成一个有效的数据块 lpdwBlockData（512 字节），这将使函数 calcCrcPartial() 为任何给定的 iInitialCrc 返回 0（根据之前对该函数的调用计算）？

CRC 不存储在块中。

生成的数据块（512 字节）可以包含任何数据。

我试图用随机数据填充缓冲区，希望它会在 CRC 计算后达到 0 校验和值，但我想这不是办法......

如何反转该算法并生成有效数据以使生成的缓冲区数据上的 calcCrcPartial() 并提供 iInitialCrc 返回值 0？

标签： c++crc

解决方案

这不是正常的 CRC。初始 CRC 循环左移 16 次，然后第一个短路与 CRC 的低 16 位异或，然后再次循环 16 次，下一个短路与 CRC 的低 16 位异或. 如果数据只是 2 个短路，则与循环初始 CRC 32 次相同，然后将 2 个短路与循环的 CRC 进行异或。要获得 CRC==0，只需将 2 个短路设置为循环 32 次的初始 CRC。下面的示例代码。

如何使用尽可能少的数据将数据缓冲区计算为零校验和值

只需要 2 条短裤即可。设置 2 个短路 = 0，计算 CRC，然后将 2 个短路设置为计算的 CRC。这将导致任何初始 CRC 的 CRC 为 0。

我切换到校验和函数的表驱动版本，但下面的代码还包括问题示例 CRC 函数的“清理”版本。

此代码比较问题代码、替代版本和表格驱动版本的 CRC 输出：

#include <iostream>
#include <iomanip>

typedef unsigned short uint16_t;
typedef unsigned int   uint32_t;

uint32_t crctbl[65536];

void gentbl()
{
uint32_t crc;
int i, j;
    for(j = 0; j < 0x10000; j++){
        crc = j<<16;
        for(i = 0; i < 16; i++)
            // assumes twos complement
            crc = (crc<<1)^((0-(crc>>31))&0x400007u);
        crctbl[j] = crc;
    }
}

int calcCrcPartial(unsigned short* lpdwBlockData, unsigned short dwBlockSizeInBytes, int iInitialCrc)
{
    unsigned short dwBlocksSizeInWords;
    int bIsSigned;
    signed int j;
    signed int i;
    unsigned short dwDataItem;
    bool bIsNegative;

    // number of WORD blocks
    dwBlocksSizeInWords = dwBlockSizeInBytes >> 1;

    for (i = 0; ; ++i)
    {
        if (dwBlocksSizeInWords <= i)
        {
            break;
        }

        dwDataItem = lpdwBlockData[i];

//      bInvalidCrc not delcared and not used
//      if (dwDataItem != 0)
//      {
//          bInvalidCrc = false;
//      }

        for (j = 0; j <= 15; ++j)
        {
            bIsSigned = (dwDataItem & 0x8000u) != 0;

            dwDataItem <<= 1;

            bIsNegative = iInitialCrc < 0;

            iInitialCrc <<= 1;
            iInitialCrc += bIsSigned;

            if (bIsNegative)
            {
                iInitialCrc ^= 0x400007u;
            }
        }
    }

    return iInitialCrc;
}

// alternate version of calcCrcPartial
uint32_t calcCrcPartiala(uint16_t* lpwBlockData, uint16_t wBlockSizeInBytes, uint32_t iInitialCrc)
{
int sz = wBlockSizeInBytes >> 1;
int i;
    while(sz--){
        for(i = 0; i < 16; i++)
            // assumes twos complement
            iInitialCrc = (iInitialCrc<<1)^((0-(iInitialCrc>>31))&0x400007u);
        iInitialCrc ^= *lpwBlockData++;
    }
    return iInitialCrc;
}

// table version of calcCrcPartial
uint32_t calcCrcPartialt(uint16_t* lpwBlockData, uint16_t wBlockSizeInBytes, uint32_t iInitialCrc)
{
int sz = wBlockSizeInBytes >> 1;
    while(sz--)
        iInitialCrc = (iInitialCrc<<16)^crctbl[iInitialCrc>>16]^*lpwBlockData++;
    return iInitialCrc;
}

int main()
{
uint16_t data[] = {0x0000, 0x0000};
uint32_t iCrc, oCrc, oCra, oCrt;
    gentbl();
    iCrc = 0x00000000u;
    do{
        oCrc = calcCrcPartial (data, sizeof(data), iCrc);
        oCra = calcCrcPartiala(data, sizeof(data), iCrc);
        oCrt = calcCrcPartiala(data, sizeof(data), iCrc);
        if(oCrc != oCra || oCrc != oCrt){
            std::cout << "mismatch" << std::endl;
            break;}
        if ((iCrc & 0x0ffffffu) == 0)
            std::cout << std::hex << iCrc << std::endl;
    }while(++iCrc != 0x10000000u);

    return 0;
}

此代码测试所有 40 亿个可能的初始 CRC。

#include <iostream>
#include <iomanip>

typedef unsigned short uint16_t;
typedef unsigned int   uint32_t;

uint32_t crctbl[65536];

void gentbl()
{
uint32_t crc;
int i, j;
    for(j = 0; j < 0x10000; j++){
        crc = j<<16;
        for(i = 0; i < 16; i++)
            // assumes twos complement
            crc = (crc<<1)^((0-(crc>>31))&0x400007u);
        crctbl[j] = crc;
    }
}

uint32_t calcCrcPartial(uint16_t* lpwBlockData, uint16_t wBlockSizeInBytes, uint32_t iInitialCrc)
{
int sz = wBlockSizeInBytes >> 1;
    while(sz--)
        iInitialCrc = (iInitialCrc<<16)^crctbl[iInitialCrc>>16]^*lpwBlockData++;
    return iInitialCrc;
}

// alternate version of questions code
uint32_t calcCrcPartialx(uint16_t* lpwBlockData, uint16_t wBlockSizeInBytes, uint32_t iInitialCrc)
{
int sz = wBlockSizeInBytes >> 1;
int i;
    while(sz--){
        for(i = 0; i < 16; i++)
            // assumes twos complement
            iInitialCrc = (iInitialCrc<<1)^((0-(iInitialCrc>>31))&0x400007u);
        iInitialCrc ^= *lpwBlockData++;
    }
    return iInitialCrc;
}

int main()
{
uint16_t data[] = {0x0000, 0x0000};
uint32_t iCrc, oCrc;
    gentbl();
    iCrc = 0x00000000u;
    do{
        // oCrc = iCrc cycled 32 times
        data[0] = 0x0000;
        data[1] = 0x0000;
        oCrc = calcCrcPartial(data, 4, iCrc);
        // store oCrc and verify new crc == 0
        data[0] = (oCrc>>16);
        data[1] = (oCrc>> 0);
        oCrc = calcCrcPartial(data, 4, iCrc);
        if (oCrc != 0) {
            std::cout << "error" << std::endl;
            break;
        }
        if ((iCrc & 0xfffffffu) == 0)
            std::cout << std::hex << iCrc << std::endl;
    }while(++iCrc != 0x00000000u);
    return 0;
}

如何使用尽可能少的数据将数据缓冲区计算为零校验和值

如果这意味着最小数量的错误位，那么在 34 个短路、全为零且初始 CRC = 0 的缓冲区中，需要切换特定位置的 6 位（基于 poly 和初始 CRC）以也产生 CRC = 0：

0x8000, 0x0000, 0x0000, 0x0000, 0x0000,0x0000,0x0000,0x0000,
0x0000, 0x0000, 0x8000, 0x0000, 0x0000,0x0000,0x0000,0x0000,
0x0000, 0x0000, 0x0000, 0x0000, 0x0000,0x0000,0x0000,0x0000,
0x0000, 0x0000, 0x0000, 0x0000, 0x0000,0x0000,0x0020,0x8003,
0x0000, 0x0000

或者简单地仍然使用只有 5 位 = 1 的 CRC 多项式，只需要 5 个字：

0x0100, 0x4000, 0x0700, 0x0000, 0x0000

这就是如何将此版本的 CRC 用于 512 字节的数据和 4 字节的 CRC：

#include <stdlib.h> // for rand()

// # of shorts in data, not including CRC
#define COUNT 256

int main()
{
uint16_t data[COUNT+2];
uint32_t iCrc, oCrc;
int i;
    gentbl();
    // fill data with psuedo random values
    for(i = 0; i < COUNT; i++)
        data[i] = ((rand()>>4)&0xff)|((rand()<<4)&0xff00);
    iCrc = 0x00000000u;
    do{
        // generate crc
        data[COUNT+0] = 0x0000u;
        data[COUNT+1] = 0x0000u;
        oCrc = calcCrcPartial(data, sizeof(data), iCrc);
        // append crc to data
        data[COUNT+0] = (oCrc>>16);
        data[COUNT+1] = (oCrc>> 0);
        // check crc
        oCrc = calcCrcPartial(data, sizeof(data), iCrc);
        if (oCrc != 0) {
            std::cout << "error" << std::endl;
            break;
        }
        if ((iCrc & 0xfffffu) == 0)
            std::cout << std::hex << iCrc << std::endl;
    }while(++iCrc != 0x01000000u);
    return 0;
}

推荐阅读