<![CDATA[How a Bug(?) in the Linux CRC-32 Checksum Turned out not to be a Bug]]>

Bonus: speaking about CRC

This is not for the first time I face some weird bit magic issues with CRC, for example, look at the following code:

	// For a fully compiled version look at https://gist.github.com/danlark1/69c9d5e1d356eaa32dbdfccb2e19f401
	#include <stdint.h>
	#include <stddef.h>
	#include <stdio.h>

	#define FNV32INIT 2166136261U
	#define FNV32PRIME 16777619U
	#define FNV64INIT 14695981039346656037ULL
	#define FNV64PRIME 1099511628211ULL

	// Any table
	extern unsigned long crc64table[256];

	unsigned long fnv64(const void *p, size_t len) {
	unsigned long init = FNV64INIT;
	const unsigned char _p = (const unsigned char )p;
	for (size_t i = 0; i < len; ++i) {
	init = (init * FNV64PRIME) ^ _p[i];
	}
	return init;
	}

	unsigned long crc64(unsigned long crc, const void *p, size_t len) {
	size_t i, t;
	const unsigned char _p = (const unsigned char )p;
	for (i = 0; i < len; i++) {
	t = ((crc >> 56) ^ (*_p++)) & 0xFF;
	crc = crc64table[t] ^ (crc << 8);
	}
	return crc;
	}

	int main() {
	const char* data1 = "l.im/8ca";
	const char* data2 = "l.im/8cf";
	size_t size = 8;
	unsigned long crc = crc64(fnv64(data1, size), data1, size);
	printf("%lu\n", crc); // 6193082687915471267
	crc = crc64(fnv64(data2, size), data2, size);
	printf("%lu\n", crc); // 6193082687915471267
	}

view raw crc_fnv_fiasco.c hosted with ❤ by GitHub

It seeds CRC64 hash with FNV hash and the results are the same. Though the last byte of the 8 word strings are different. I faced it once in URL hashing and it was failing for urls with very short domain and path. The proof is left as an exercise to the reader, try it out, really, it is some good bit twiddling. More hashing is sometimes bad hashing, be careful 🙂

Thanks to Nigel Tao who first suspected an issue with the Linux kernel and described it in the wuffs repository. I think no one should do anything as it perfectly works or at the very most fix the constants to better match the guideline.

	static const uint64_t zalign(16) poly[] = { 0x01db710641, 0x01f7011641 };
	// ^^^^^^^^^^^^
	// No use of poly
	// …
	// x0, x1, x2, x3 are 128 bit registers
	x3 = _mm_setr_epi32(~0, 0, ~0, 0); // Set reverse, i.e. bits from 0 to 31 are 1s, from 32 to 63 are zeros, etc
	// No reassignment of x3
	// …
	/*
	* Barret reduce to 32-bits.
	*/
	x0 = _mm_load_si128((__m128i*)poly); // Load 16 bytes

	x2 = _mm_and_si128(x1, x3); // Do logical AND with x3
	x2 = _mm_clmulepi64_si128(x2, x0, 0x10); // Do CLMUL with the high 8 bytes of poly
	x2 = _mm_and_si128(x2, x3); // Do logical AND with x3
	x2 = _mm_clmulepi64_si128(x2, x0, 0x00); // Do CLMUL with the low 8 bytes of poly
	x1 = _mm_xor_si128(x1, x2); // XOR x1 and x2

	/*
	* Return the crc32.
	*/
	return _mm_extract_epi32(x1, 1); // Return bytes from 4 to 8 of x1, i.e. extract the second 32 bit integer