且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

为什么要使用XOR用文字而不是反转(按位NOT)

更新时间:2022-10-16 09:04:36

东西没有人没有提到;如果code被编译的机器上16位 unsigned int类型那么这两个code片段是的不同的

CRC 指定为32位无符号整型。 〜CRC 将反转所有位,但如果 unsigned int类型是16bit那么 CRC = CRC ^ 〜0U 只会反转低16位。

我不知道有足够的了解了CRC算法知道这是否是有意还是一个bug,或许可以HIVERT澄清;虽然看着张贴OP样品code,它的确做出后面的循环中的差异。

NB。对不起张贴这是一个答案,因为它不是一个答案,但它太大只适合评论:)

I have come across this CRC32 code and was curious why the author would choose to use

crc = crc ^ ~0U;

instead of

crc = ~crc;

As far as I can tell, they are equivalent.

I have even disassembled the two versions in Visual Studio 2010.

Not optimized build:

    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  

I also cannot justify the code by thinking about the number of cycles that each instruction takes since both should be taking 1 cycle to complete. In fact, the xor might have a penalty by having to load the literal from somewhere, though I am not certain of this.

So I'm left thinking that it is possibly just a preferred way to describe the algorithm, rather than an optimization... Would that be correct?

Edit 1:

Since I just realized that the type of the crc variable is probably important to mention I am including the whole code (less the lookup table, way too big) here so you don't have to follow the link.

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;
}

Edit 2:

Since someone has brought up the fact that an optimized build would be of interest, I have made one and included it below.

Optimized build:

Do note that the whole function (included in the last edit below) was inlined.

// 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  

Something nobody's mentioned yet; if this code is being compiled on a machine with 16 bit unsigned int then these two code snippets are different.

crc is specified as a 32-bit unsigned integral type. ~crc will invert all bits, but if unsigned int is 16bit then crc = crc ^ ~0U will only invert the lower 16 bits.

I don't know enough about the CRC algorithm to know whether this is intentional or a bug, perhaps hivert can clarify; although looking at the sample code posted by OP, it certainly does make a difference to the loop that follows.

NB. Sorry for posting this as an "answer" because it isn't an answer, but it's too big to just fit in a comment :)