CRC32(32-bit buffer) is a bijective function

I've always been interested if this is true or not?

#define POLY 0xedb88320

#include <inttypes.h>
#include <stdio.h>
#include <string.h>

// copypasted from https://rosettacode.org/wiki/CRC-32#C 
uint32_t
rc_crc32(uint32_t crc, const char *buf, size_t len)
{
	static uint32_t table[256];
	static int have_table = 0;
	uint32_t rem;
	uint8_t octet;
	int i, j;
	const char *p, *q;
 
	/* This check is not thread safe; there is no mutex. */
	if (have_table == 0) {
		/* Calculate CRC table. */
		for (i = 0; i < 256; i++) {
			rem = i;  /* remainder from polynomial division */
			for (j = 0; j < 8; j++) {
				if (rem & 1) {
					rem >>= 1;
					rem ^= POLY;
				} else
					rem >>= 1;
			}
			table[i] = rem;
		}
		have_table = 1;
	}
 
	crc = ~crc;
	q = buf + len;
	for (p = buf; p < q; p++) {
		octet = *p;  /* Cast to unsigned octet. */
		crc = (crc >> 8) ^ table[(crc & 0xff) ^ octet];
	}
	return ~crc;
}

main()
{
        uint32_t tmp=0;

        while (1)
        {
                printf("%08x\n", rc_crc32(0, &tmp, sizeof(uint32_t)));
                if (tmp==0xffffffff)
                        break;
                tmp++;
        };

        return 0;
}

This program generates all possible $2^{32}-1$ values. I tried these known CRC-32 polynomials: 0xedb88320, 0x82F63B78, 0xEB31D82E, 0x80000000.

I tried even random polynomials, all works: 0xffffffff, 0x82345678.

So this is a a perfect hash function, with no collisions.

But this polynomial is faulty: 0x12345678.

Here is a simple explanation. If you divide all possible 32-bit numbers by a 32-bit constant, you'll get remainders between 0 and this 32-bit constant.

CRC is a calculation of remainder over GF(2): input message is a dividend, polynomial is a divisor, CRC output is a remainder. So no wonder that outputs are all possible 32-bit values if a polynomial has highest bit set (0x80000000).

This would generalize to all CRC polynomials of other widths.

The 'Mathematical recipes' book has a section devoted to explanation of CRC algorithm as a division.

List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.