c++ - CRC32 C++ 实现使用 bool 数组并逐位手动异或

Question

我无法理解 CRC32 应该如何以正常方式工作。
我已经从 wiki 和其他网站实现了机制:https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Computation在这里你一点一点地异或元素。
对于 CRC32，我使用了来自 wiki 的 Polynomial，它也无处不在:

x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
with binary representation: 1 0000 0100 1100 0001 0001 1101 1011 0111

我计算输入字符串“1234”的 CRC32 只是为了测试。这是程序的输出:
/image/tG4wk.png
如您所见，xor 计算正确且 CRC32 为“619119D1”。
当我使用在线计算器甚至 C++ boost 库计算它时，答案是“9BE3E0A3”。
正常的 XORing 逐位输入字符串有什么问题？我应该在最后添加一些东西还是什么？我不想使用库和任何其他魔术代码来计算它，因为我必须以这种方式为我的研究项目实现它。我也尝试过不带 x^32 的多项式，最后取反位，从 1s 而不是 0s 开始(你必须添加 32 个零)，答案也不同。我不知道我现在该怎么做才能解决这个问题。这是代码的一部分(有点改变)，我有 buffor 3parts * 32bits，我从文件加载 4 个字符到中间部分，从开始到中间部分异或，最后我对中间部分和结束 -> 结束是 CRC32。

My pseudo schema:
1) Load 8 chars
2) | First part | Middle Part | CRC32 = 0 |
3) XOR
4) | 0 0 0 0 | XXXXXXX | 0 0 0 0 |
5) memcpy - middle part to first part
6) | XXXXXXX | XXXXXXX | 0 0 0 0  |
7) Load 4 chars
8) | XXXXXXX | loaded 4chars | 0 0 0 0 |
9) repeat from point 4 to the end of file
10) now we have: | 0 0 0 0 | XXXXXX | 0 0 0 0 |
11) last xor from middle part to end
12) Result: | 0 0 0 0 |  0 0 0 0 | CRC32 |

可能带输出的屏幕会更有帮助。
稍后我将使用智能指针等；)

bool xorBuffer(unsigned char *buffer) {
    bool * binaryTab = nullptr;
    try {
        // CRC-32
        // 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
        //  1  0  0  0  0  0  1  0  0  1  1  0  0  0  0  0  1  0  0  0  1  1  1  0  1  1  0  1  1  0  1  1  1
        const int dividerSizeBits = 33;
        const bool binaryDivider[dividerSizeBits] = { 1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1 };

        const int dividerLength = countLength(binaryDivider, dividerSizeBits);
        const int dividerOffset = dividerSizeBits - dividerLength;  // when divider < 33 bits

        bool * binaryTab = charTabToBits(buffer);

        // check tab if first part = 0
        while (!checkTabIfEmpty(binaryTab)) {
            // set the beginnning
            int start = 0;
            for (start = 0; start < 32; start++)
                if (binaryTab[start] == true)
                    break;
            for (int i = 0; i < dividerLength; i++)
                binaryTab[i + start] = binaryTab[i + start] ^ binaryDivider[i + dividerOffset];    
        }
        // binaryTab -> charTab
        convertBinaryTabToCharTab(binaryTab, buffer);
    }
    catch (exception e) {
        delete[] binaryTab;
        return false;
    }
    delete[] binaryTab;
    return true;
}

std::string CRC::countCRC(std::string fileName){
    // create variables
    int bufferOnePartSize = 4;
    int bufferSize = bufferOnePartSize * 3;
    bool EOFFlag = false;
    unsigned char *buffer = new unsigned char[bufferSize];

    for (int i = 0; i < 3 * bufferOnePartSize; i++)
        buffer[i] = 0;

    // open file
    ifstream fin;
    fin.open(fileName.c_str(), ios_base::in | ios_base::binary);

    int position = 0;
    int count = 0;
    // while -> EOF
    if (fin.is_open()) {
        // TODO check if file <= 4 -> another solution
        char ch;
        int multiply = 2;
        bool skipNormalXor = false;
        while (true) {
            count = 0;
            if (multiply == 2)
                position = 0;
            else
                position = bufferOnePartSize;
            // copy part form file to tab
            while (count < bufferOnePartSize * multiply && fin.get(ch)) {
                buffer[position] = (unsigned char)ch;
                ++count;
                ++position;
            }
            cout << endl;
            // if EOF write zeros to end of tab
            if (count == 0) {
                cout << "TODO: end of file" << endl;
                EOFFlag = true;
                skipNormalXor = true;
            }
            else if (count != bufferOnePartSize * multiply) {
                for (int i = count; i < bufferOnePartSize * multiply; i++) {
                    buffer[position] = 0;
                    position++;
                }
                EOFFlag = true;
            }

            if (!skipNormalXor) {
                // -- first part
                multiply = 1;
                // xor the buffer
                xorBuffer(buffer);
            }

            if (EOFFlag) {  // xor to the end
                xorBuffer(buffer + bufferOnePartSize);
                break;
            }
            else {
                // copy memory
                for (int i = 0; i < bufferOnePartSize; i++)
                    buffer[i] = buffer[i + bufferOnePartSize];
            }
        }
        cout << "\n End\n";
        fin.close();
    }

    stringstream crcSum;
    for (int i = 2 * bufferOnePartSize; i < bufferSize; i++) {
        //buffer[i] = ~buffer[i];
        crcSum << std::hex << (unsigned int)buffer[i];
    }
    cout << endl << "CRC: " << crcSum.str() << endl;
    delete[] buffer;
    return crcSum.str();
}

Answer 1

CRC 不仅仅由多项式定义。您需要定义位顺序、CRC 寄存器的初始值以及 CRC 的最终异或。对于标准的 CRC-32，它为“1234”给出 0x9be3e0a3，这些位从最低有效位开始处理，寄存器的初始值为 0xffffffff，并且您异或最终结果使用 0xffffffff。