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

Question

给出这个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 字节），这将使给定 iInitialCrc 的 any 的函数 calcCrcPartial() 变为 return 0 （根据之前对该函数的调用计算得出）?

CRC 未存储在块中。

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

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

如何反转此算法并生成有效数据，使生成的缓冲区数据上的 calcCrcPartial() 和提供的 iInitialCrc 为 return 值 0？

Answer 1

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

How to calculate data buffer to zero checksum value with as little data as possible

只需要 2 条短裤就可以做到这一点。设置 2 short = 0，计算 CRC，然后将 2 short 设置为计算出的 CRC。这将导致任何初始 CRC 的 CRC 为 0。

我切换到 table 驱动版本的校验和函数，但下面的代码还包含 "cleaned up" 版本的问题示例 CRC 函数。

此代码比较问题代码、替代版本和 table 驱动版本的 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;
}

How to calculate data buffer to zero checksum value with as little data as possible

如果这意味着最小错误位数，则在 34 个短裤缓冲区中，全零且初始 CRC = 0，需要将特定位置的 6 位（基于多边形和初始 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;
}

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

How to calculate data buffer to zero checksum value with as little data as it's possible

c++

crc