mdbtxt1
mdbtxt2
Proceed to Safety

# A Collection of 32-bit CRC Tables and Algorithms

## Introduction

This page gives a small list of CRC "polynomials" expressed as n-bit binary constants, for n=16 and n=32, corresponding to some widely-used 16-bit and 32-bit CRC checksums.

Following that is the excellent "makecrc" program adapted from code by Mark G. Mendel. It is a C program that prints out valid C code for performing a CRC checksum calculation with each of the CRC "polynomials" listed in the table.

## Table of CRC "polynomials"

A polynomial, of course, is not a binary number. However the CRC algorithm is based on properties of finite field arithmetic, in which addition and multiplication modulo a prime p (or a power of a prime, etc.) has properties that are very useful for error detection. The "polynomials" here are in a single variable, evaluated in modulo-2 arithmetic (i.e. using the finite field GF(2), which means that the "coefficients" are all either 0 or 1, and addition and subtraction are simply a 1-bit XOR. That means that the coefficients of an nth order polynomial consist of only n+1 binary digits, and can be stored efficiently as a binary number in a computer; and polynomial "multiplication" and "division" can be performed with shifts and XORs of n+1-bit binary numbers.

 name bits coefficients reversed CCITT 16 0x1021 n/a KERMIT 16 0x8408 0x1021 ARC 16 0xA001 0x8005 BINHEX 16 0x1021 n/a CCITT32 32 0x04c11db7 n/a ZIP 32 0xedb88320 0x04c11db7

A much more complete list (and also some source code, and many links) is on Wikipedia here.

### datatypes

typedef unsigned char uint8_t; typedef unsigned short uint16_t; typedef unsigned int uint32_t;

## makecrc

This is from the Harvest project, developed by the Internet Research Task Force Research Group on Resource Discovery (IRTF-RD) and hosted for some time at University of Colorado, Boulder.

I got this code from version 1.3.pl3 of Harvest, dated Wed 25th October 1995. It was mirrored at MIT (at the URL web.mit.edu/wwwdev/src/harvest-1.3.pl3/components/gatherer/standard/unbinhex/crc/makecrc.c)

The copyright and terms of use for the main part of Harvest are here. Notice that it says that "components" have their own copyright notices, however there is none for the particular component and subdirectory containing this code. A README in the components/gatherer/standard/unbinhex directory credits Mark G. Mendel with creating a predecessor to this code.

This code outputs the tables and CRC calculation routines in the CCITT32 and zip sections below. It also outputs four types of 16-bit CRC tables and code, which are not included on this webpage.

/* This program will write six C routines for the calculation of * the following CRC's. */    /* The CRC polynomial. * These 4 values define the crc-polynomial. * If you change them, you must change crctab[]'s initial value to what is * printed by initcrctab() [see 'compile with -DMAKETAB' above]. */    /* This tables assumes CCITT is MSB first. Swapped means LSB first. In that * case the polynomial is also swapped */    /* 16 bit crc's */ /* Value used by: CCITT KERMIT ARC BINHEX */ /* the poly: 0x1021 0x8408 0xA001 0x1021 */ /* original: 0x1021 0x1021 0x8005 0x1021 */ /* init value: -1 0 0 0 */ /* swapped: no yes yes no */ /* bits in CRC: 16 16 16 16 */ /* ARC used by LHARC, ZOO, STUFFIT */ /* BINHEX used by XMODEM, PACKIT */    /* 32 bit crc's */ /* Value used by: CCITT32 ZIP */ /* the poly: 0x04c11db7 0xedb88320 */ /* original: 0x04c11db7 0x04c11db7 */ /* init value: -1 -1 */ /* swapped no yes */ /* bits in CRC: 32 32 */ /* ZIP used by COMPACTOR */    #include <stdio.h>    extern void exit(); extern char *strcat();    static void initcrctab();    main() { initcrctab("ccitt", 0x1021, 0xffff, 0, 16); initcrctab("kermit", 0x8408, 0, 1, 16); initcrctab("arc", 0xa001, 0, 1, 16); initcrctab("binhex", 0x1021, 0, 0, 16); initcrctab("ccitt32",0x04c11db7,0xffffffff,0,32); initcrctab("zip",0xedb88320,0xffffffff,1,32); exit(0); /*NOTREACHED*/ }    static void initcrctab(name, poly, init, swapped, bits) char *name; int poly, init, swapped, bits; { register int b, i; uint16_t v; uint32_t vv; FILE *fd; char buf[20];    buf[0] = 0; (void)strcat(buf, name); (void)strcat(buf, ".c"); if((fd = fopen(buf, "w")) == NULL) { (void)fprintf(stderr, "Cannot open %s for writing\n", buf); exit(1); } (void)fprintf(fd, "uint32_t %s_crcinit = %d;\n", name, init); (void)fprintf(fd, "\n"); if(bits == 16) { (void)fprintf(fd, "static uint16_t crctab[256] = {\n"); } else { (void)fprintf(fd, "static uint32_t crctab[256] = {\n"); } (void)fprintf(fd, " "); if(bits == 16) { for(b = 0; b < 256; ++b) { if(swapped) { for(v = b, i = 8; --i >= 0;) v = v & 1 ? (v>>1)^poly : v>>1; } else { for(v = b<<8, i = 8; --i >= 0;) v = v & 0x8000 ? (v<<1)^poly : v<<1; } (void)fprintf(fd, "0x%.4x,", v & 0xffff); if((b&7) == 7) { (void)fprintf(fd, "\n"); if(b != 255) (void)fprintf(fd, " "); } else { (void)fprintf(fd, " "); } } } else { for(b = 0; b < 256; ++b) { if(swapped) { for(vv = b, i = 8; --i >= 0;) vv = vv & 1 ? (vv>>1)^poly : vv>>1; } else { for(vv = b<<24, i = 8; --i >= 0;) vv = vv & 0x80000000 ? (vv<<1)^poly : vv<<1; } (void)fprintf(fd, "0x%.8x,", vv & 0xffffffff); if((b&3) == 3) { (void)fprintf(fd, "\n"); if(b != 255) (void)fprintf(fd, " "); } else { (void)fprintf(fd, " "); } } } (void)fprintf(fd, "};\n"); (void)fprintf(fd, "\n"); (void)fprintf(fd, "uint32_t %s_updcrc(icrc, icp, icnt)\n", name); (void)fprintf(fd, " uint32_t icrc;\n"); (void)fprintf(fd, " uint8_t *icp;\n"); (void)fprintf(fd, " int icnt;\n"); (void)fprintf(fd, "{\n"); if(bits == 16) { (void)fprintf(fd, "#define M1 0xff\n"); (void)fprintf(fd, "#define M2 0xff00\n"); } else { (void)fprintf(fd, "#define M1 0xffffff\n"); (void)fprintf(fd, "#define M2 0xffffff00\n"); } (void)fprintf(fd, " register uint32_t crc = icrc;\n"); (void)fprintf(fd, " register uint8_t *cp = icp;\n"); (void)fprintf(fd, " register int cnt = icnt;\n"); (void)fprintf(fd, "\n"); (void)fprintf(fd, " while(cnt--) {\n");    if(bits == 16) { if (swapped) { (void)fprintf(fd, "\tcrc=((crc>>8)&M1)^crctab[(crc&0xff)^*cp++];\n"); } else { (void)fprintf(fd, "\tcrc=((crc<<8)&M2)^crctab[((crc>>8)&0xff)^*cp++];\n"); } } else { if(swapped) { (void)fprintf(fd, "\tcrc=((crc>>8)&M1)^crctab[(crc&0xff)^*cp++];\n"); } else { (void)fprintf(fd, "\tcrc=((crc<<8)&M2)^crctab[((crc>>24)&0xff)^*cp++];\n"); } } (void)fprintf(fd, " }\n"); (void)fprintf(fd, "\n"); (void)fprintf(fd, " return(crc);\n"); (void)fprintf(fd, "}\n"); (void)fprintf(fd, "\n"); (void)fclose(fd); }

## CCITT32

Source : web.mit.edu/wwwdev/src/harvest-1.3.pl3/components/gatherer/standard/unbinhex/crc/ccitt32.c

This table and the CRC calculation function are both output by the above "makecrc" code.

This is not the Adler-32 checksum (follow that link to find out what it is), but is a CRC-like operation using a reversed form of the more common 0x04c11db7 (i.e. 0xedb88320). Like other CRC operations it starts with all 1's (i.e. 0xFFFFFFFF), but the functions also provide the ability to pass a "crc" as input, which enables the CRC of a long amount of data by calling the routine on pieces of the data. This requires reversing all bits at the beginning and end (i.e. when done it XORs the result with 0xFFFFFFFF) which means that the final answer is different from a normal CRC.

Sources :

The table of 256 values "crc32_table" is the same as that seen in code from Gary S. Brown, at web.mit.edu/freebsd/head/sys/libkern/crc32.c

## zip

Source : web.mit.edu/wwwdev/src/harvest-1.3.pl3/components/gatherer/standard/unbinhex/crc/zip.c

This table and the CRC calculation function are both output by the above "makecrc" code.

uint32_t zip_crcinit = -1; static uint32_t crctab[256] = { 0x00000000, 0x09073096, 0x120e612c, 0x1b0951ba, 0xff6dc419, 0xf66af48f, 0xed63a535, 0xe46495a3, 0xfedb8832, 0xf7dcb8a4, 0xecd5e91e, 0xe5d2d988, 0x01b64c2b, 0x08b17cbd, 0x13b82d07, 0x1abf1d91, 0xfdb71064, 0xf4b020f2, 0xefb97148, 0xe6be41de, 0x02dad47d, 0x0bdde4eb, 0x10d4b551, 0x19d385c7, 0x036c9856, 0x0a6ba8c0, 0x1162f97a, 0x1865c9ec, 0xfc015c4f, 0xf5066cd9, 0xee0f3d63, 0xe7080df5, 0xfb6e20c8, 0xf269105e, 0xe96041e4, 0xe0677172, 0x0403e4d1, 0x0d04d447, 0x160d85fd, 0x1f0ab56b, 0x05b5a8fa, 0x0cb2986c, 0x17bbc9d6, 0x1ebcf940, 0xfad86ce3, 0xf3df5c75, 0xe8d60dcf, 0xe1d13d59, 0x06d930ac, 0x0fde003a, 0x14d75180, 0x1dd06116, 0xf9b4f4b5, 0xf0b3c423, 0xebba9599, 0xe2bda50f, 0xf802b89e, 0xf1058808, 0xea0cd9b2, 0xe30be924, 0x076f7c87, 0x0e684c11, 0x15611dab, 0x1c662d3d, 0xf6dc4190, 0xffdb7106, 0xe4d220bc, 0xedd5102a, 0x09b18589, 0x00b6b51f, 0x1bbfe4a5, 0x12b8d433, 0x0807c9a2, 0x0100f934, 0x1a09a88e, 0x130e9818, 0xf76a0dbb, 0xfe6d3d2d, 0xe5646c97, 0xec635c01, 0x0b6b51f4, 0x026c6162, 0x196530d8, 0x1062004e, 0xf40695ed, 0xfd01a57b, 0xe608f4c1, 0xef0fc457, 0xf5b0d9c6, 0xfcb7e950, 0xe7beb8ea, 0xeeb9887c, 0x0add1ddf, 0x03da2d49, 0x18d37cf3, 0x11d44c65, 0x0db26158, 0x04b551ce, 0x1fbc0074, 0x16bb30e2, 0xf2dfa541, 0xfbd895d7, 0xe0d1c46d, 0xe9d6f4fb, 0xf369e96a, 0xfa6ed9fc, 0xe1678846, 0xe860b8d0, 0x0c042d73, 0x05031de5, 0x1e0a4c5f, 0x170d7cc9, 0xf005713c, 0xf90241aa, 0xe20b1010, 0xeb0c2086, 0x0f68b525, 0x066f85b3, 0x1d66d409, 0x1461e49f, 0x0edef90e, 0x07d9c998, 0x1cd09822, 0x15d7a8b4, 0xf1b33d17, 0xf8b40d81, 0xe3bd5c3b, 0xeaba6cad, 0xedb88320, 0xe4bfb3b6, 0xffb6e20c, 0xf6b1d29a, 0x12d54739, 0x1bd277af, 0x00db2615, 0x09dc1683, 0x13630b12, 0x1a643b84, 0x016d6a3e, 0x086a5aa8, 0xec0ecf0b, 0xe509ff9d, 0xfe00ae27, 0xf7079eb1, 0x100f9344, 0x1908a3d2, 0x0201f268, 0x0b06c2fe, 0xef62575d, 0xe66567cb, 0xfd6c3671, 0xf46b06e7, 0xeed41b76, 0xe7d32be0, 0xfcda7a5a, 0xf5dd4acc, 0x11b9df6f, 0x18beeff9, 0x03b7be43, 0x0ab08ed5, 0x16d6a3e8, 0x1fd1937e, 0x04d8c2c4, 0x0ddff252, 0xe9bb67f1, 0xe0bc5767, 0xfbb506dd, 0xf2b2364b, 0xe80d2bda, 0xe10a1b4c, 0xfa034af6, 0xf3047a60, 0x1760efc3, 0x1e67df55, 0x056e8eef, 0x0c69be79, 0xeb61b38c, 0xe266831a, 0xf96fd2a0, 0xf068e236, 0x140c7795, 0x1d0b4703, 0x060216b9, 0x0f05262f, 0x15ba3bbe, 0x1cbd0b28, 0x07b45a92, 0x0eb36a04, 0xead7ffa7, 0xe3d0cf31, 0xf8d99e8b, 0xf1deae1d, 0x1b64c2b0, 0x1263f226, 0x096aa39c, 0x006d930a, 0xe40906a9, 0xed0e363f, 0xf6076785, 0xff005713, 0xe5bf4a82, 0xecb87a14, 0xf7b12bae, 0xfeb61b38, 0x1ad28e9b, 0x13d5be0d, 0x08dcefb7, 0x01dbdf21, 0xe6d3d2d4, 0xefd4e242, 0xf4ddb3f8, 0xfdda836e, 0x19be16cd, 0x10b9265b, 0x0bb077e1, 0x02b74777, 0x18085ae6, 0x110f6a70, 0x0a063bca, 0x03010b5c, 0xe7659eff, 0xee62ae69, 0xf56bffd3, 0xfc6ccf45, 0xe00ae278, 0xe90dd2ee, 0xf2048354, 0xfb03b3c2, 0x1f672661, 0x166016f7, 0x0d69474d, 0x046e77db, 0x1ed16a4a, 0x17d65adc, 0x0cdf0b66, 0x05d83bf0, 0xe1bcae53, 0xe8bb9ec5, 0xf3b2cf7f, 0xfab5ffe9, 0x1dbdf21c, 0x14bac28a, 0x0fb39330, 0x06b4a3a6, 0xe2d03605, 0xebd70693, 0xf0de5729, 0xf9d967bf, 0xe3667a2e, 0xea614ab8, 0xf1681b02, 0xf86f2b94, 0x1c0bbe37, 0x150c8ea1, 0x0e05df1b, 0x0702ef8d, };    uint32_t zip_updcrc(icrc, icp, icnt) uint32_t icrc; uint8_t *icp; int icnt; { #define M1 0xffffff #define M2 0xffffff00 register uint32_t crc = icrc; register uint8_t *cp = icp; register int cnt = icnt;    while(cnt--) { crc=((crc>>8)&M1)^crctab[(crc&0xff)^*cp++]; }    return(crc); }

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2022 May 23. s.27