CRC32 pitfall

crc32.cpp

// Pretty standard CRC-32 implementation. See any problems with this?
void AddToCRC32(uint32 &CRC, size_t Count, void const *UInt8sInit)
{
    uint8_t const *UInt8s = (uint8_t const *)UInt8sInit;

    while(Count--)
    {
        CRC = CRC32Table[(CRC ^ (*UInt8s++)) & 0xFF] ^ (CRC >> 8);
    }
}

// Sure, there's faster CRC32 algorithms than byte-at-a-time, but this
// looks reasonable, right? Well, turns out there's a giant pitfall here:
// "CRC" is passed by reference, and even under strict aliasing rules,
// "UInt8s" and "CRC" are allowed to alias, so this code needs to write
// "CRC" to memory on every iteration!
//
// Even without switching to a faster algorithm, we get much better code
// when keeping the current CRC in a local variable instead:

void AddToCRC32(uint32 &CRCRef, size_t Count, void const *UInt8sInit)
{
    uint8_t const *UInt8s = (uint8_t const *)UInt8sInit;
    uint32_t CRC = CRCRef;
    
    while(Count--)
    {
        CRC = CRC32Table[(CRC ^ (*UInt8s++)) & 0xFF] ^ (CRC >> 8);
    }
    
    CRCRef = CRC;
}

// When using VC++ 2012 and on my Core i7 (IVB) at work, this came out
// about 25% faster than the above. This is because VC++ does not just
// write CRC to memory every loop iteration (which it needs to do to
// preserve the semantics of the original C++ code), but also reloads
// it (which is unnecessary since there are no other stores in the loop
// that might alias).