Remix.run Logo
nayuki 8 hours ago

True. A most basic CRC implementation is about 7 lines of code: (presented in Java to avoid some C/C++ footguns)

    int crc32(byte[] data) {
        int crc = ~0;
        for (byte b : data) {
            crc ^= b & 0xFF;
            for (int i = 0; i < 8; i++)
                crc = (crc >>> 1) ^ ((crc & 1) * 0xEDB88320);
        }
        return ~crc;
    }
Or smooshed down slightly (with caveats):

    int crc32(byte[] data) {
        int crc = ~0;
        for (int i = 0; i < data.length * 8; i++) {
            crc ^= (data[i / 8] >> (i % 8)) & 1;
            crc = (crc >>> 1) ^ ((crc & 1) * 0xEDB88320);
        }
        return ~crc;
    }
But one reason that many CRC implementations are large is because they include a pre-computed table of 256× 32-bit constants so that one byte can processed at a time. For example: https://github.com/madler/zlib/blob/7cdaaa09095e9266dee21314...
xxs 8 hours ago | parent | next [-]

That's java code, though... bit weird, esp. i % 8 (which is just i & 7). The compiler should be able to optimize it since 'i' is guaranteed to be non-negative, still awkward.

Java CRC32 nowadays uses intrinsics and avx128 for crc32.

kevin_thibedeau 3 hours ago | parent | prev [-]

With C++20 you can use consteval to compute the table(s) at compile time from template parameters.