c++ - 为什么将 xor 与文字而不是反转一起使用(按位不是)

Question

我接触过this CRC32 code，很好奇作者为什么会选择使用

crc = crc ^ ~0U;

代替

crc = ~crc;

据我所知，它们是等价的。

我什至在 Visual Studio 2010 中反汇编了这两个版本。

未优化构建:

    crc = crc ^ ~0U;
009D13F4  mov         eax,dword ptr [crc]  
009D13F7  xor         eax,0FFFFFFFFh  
009D13FA  mov         dword ptr [crc],eax 

    crc = ~crc;
011C13F4  mov         eax,dword ptr [crc]  
011C13F7  not         eax  
011C13F9  mov         dword ptr [crc],eax  

我也无法通过考虑每条指令所花费的周期数来证明代码的合理性，因为两条指令都应该花费 1 个周期来完成。事实上，xor 可能会因为必须从某处加载文字而受到惩罚，尽管我不确定这一点。

所以我认为这可能只是一种描述算法的首选方式，而不是一种优化...这样说对吗？

编辑 1:

因为我刚刚意识到 crc 变量的类型可能很重要，所以我在这里包含了整个代码(少了查找表，太大了)所以你不必点击链接。

uint32_t crc32(uint32_t crc, const void *buf, size_t size)
{
    const uint8_t *p;

    p = buf;
    crc = crc ^ ~0U;

    while (size--)
    {
        crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
    }

    return crc ^ ~0U;
}

编辑 2:

由于有人提出优化构建会很有趣，我做了一个并将其包含在下面。

优化构建:

请注意，整个函数(包括在下面的最后一次编辑中)是内联的。

// crc = crc ^ ~0U;
    zeroCrc = 0;
    zeroCrc = crc32(zeroCrc, zeroBufferSmall, sizeof(zeroBufferSmall));
00971148  mov         ecx,14h  
0097114D  lea         edx,[ebp-40h]  
00971150  or          eax,0FFFFFFFFh  
00971153  movzx       esi,byte ptr [edx]  
00971156  xor         esi,eax  
00971158  and         esi,0FFh  
0097115E  shr         eax,8  
00971161  xor         eax,dword ptr ___defaultmatherr+4 (973018h)[esi*4]  
00971168  add         edx,ebx  
0097116A  sub         ecx,ebx  
0097116C  jne         main+153h (971153h)  
0097116E  not         eax  
00971170  mov         ebx,eax  

// crc = ~crc;
    zeroCrc = 0;
    zeroCrc = crc32(zeroCrc, zeroBufferSmall, sizeof(zeroBufferSmall));
01251148  mov         ecx,14h  
0125114D  lea         edx,[ebp-40h]  
01251150  or          eax,0FFFFFFFFh  
01251153  movzx       esi,byte ptr [edx]  
01251156  xor         esi,eax  
01251158  and         esi,0FFh  
0125115E  shr         eax,8  
01251161  xor         eax,dword ptr ___defaultmatherr+4 (1253018h)[esi*4]  
01251168  add         edx,ebx  
0125116A  sub         ecx,ebx  
0125116C  jne         main+153h (1251153h)  
0125116E  not         eax  
01251170  mov         ebx,eax  

Answer 1

还没有人提到；如果此代码是在具有 16 位 unsigned int 的机器上编译的，那么这两个代码片段是不同的。

crc 被指定为 32 位无符号整数类型。 ~crc 将反转所有位，但如果 unsigned int 是 16 位，则 crc = crc ^ ~0U 将仅反转低 16 位。

我对CRC算法了解不够，不知道这是故意的还是bug，也许hivert可以说明一下；尽管查看 OP 发布的示例代码，它确实对后面的循环产生了影响。

注意。很抱歉将其发布为“答案”，因为它不是答案，但它太大而无法放入评论 :)