15

I want to calculate a 32-bit CRC lookup table. One way I tried is by using the following code from this website:

#include <iostream>
#include <stdint.h>

void make_crc_table()
{
    unsigned long POLYNOMIAL = 0x04c11db7;
    unsigned long WIDTH = 8 * sizeof(unsigned long);
    unsigned long TOPBIT = 1 << (WIDTH - 1);
    unsigned long crcTable[256];
    unsigned long remainder;
    // Compute the remainder of each possible dividend
    for (int dividend = 0; dividend < 256; ++dividend)
    {
        // Start with the dividend followed by zeros
        remainder = dividend << (WIDTH - 8);

        // Perform modulo-2 division, a bit at a time
        for (unsigned long bit = 8; bit > 0; --bit)
        {
            // Try to divide the current data bit
            if (remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = (remainder << 1);
            }
        }
        crcTable[dividend] = remainder;
    }

    // Print the CRC table
    for (int i = 0; i < 256; i++)
    {
        if (i % 4 == 0)
        {
            std::cout <<"\n";
        }
        std::cout << std::hex << crcTable[i];
        std::cout << ", ";
    }
}

int main()
{
    make_crc_table();
    return 0;
}

Another way I tried is by using the following code that I found from this StackOverflow question, and the code can be downloaded from here in a file called CRC Calculator.zip

#include <iostream>
#include <stdint.h>

#define POLYNOMIAL      0x04C11DB7
uint32_t A_crcLookupTable[256] = {0};
#define WIDTH    (8 * sizeof(uint32_t))
#define TOPBIT   (((uint32_t)1) << (WIDTH - 1))

#define FP_reflect_DATA(_DATO)                      (_DATO)
#define FP_reflect_CRCTableValue(_CRCTableValue)    (_CRCTableValue)

uint32_t F_CRC_ObtenValorDeTabla(uint8_t VP_Pos_Tabla)
{
    uint32_t VP_CRCTableValue = 0;
    uint8_t VP_Pos_bit = 0;

    VP_CRCTableValue = ((uint32_t) FP_reflect_DATA(VP_Pos_Tabla)) << (WIDTH - 8);

    for (VP_Pos_bit = 0; VP_Pos_bit < 8; VP_Pos_bit++)
    {
        if (VP_CRCTableValue & TOPBIT)
        {
            VP_CRCTableValue = (VP_CRCTableValue << 1) ^ POLYNOMIAL;
        }
        else
        {
            VP_CRCTableValue = (VP_CRCTableValue << 1);
        }
    }
    return (FP_reflect_CRCTableValue(VP_CRCTableValue));
}

void F_CRC_InicializaTabla(void)
{
    uint16_t VP_Pos_Array = 0;

    for (VP_Pos_Array = 0; VP_Pos_Array < 256; VP_Pos_Array++)
    {
        A_crcLookupTable[VP_Pos_Array] = F_CRC_ObtenValorDeTabla((uint8_t)(VP_Pos_Array &0xFF));

    }

}


void make_crc_table()
{
    F_CRC_InicializaTabla();

    // Print the CRC table
    for (int i = 0; i < 256; i++)
    {
        if (i % 4 == 0)
        {
            std::cout <<"\n";
        }
        std::cout << std::hex << A_crcLookupTable[i];
        std::cout << ", ";
    }
}

int main()
{
    make_crc_table();
    return 0;
}

Here is what the correct final table should be, based on this link:

// The constants here are for the CRC-32 generator 
// polynomial, as defined in the Microsoft 
// Systems Journal, March 1995, pp. 107-108
CONST
  table: ARRAY[0..255] OF DWORD =
 ($00000000, $77073096, $EE0E612C, $990951BA,
  $076DC419, $706AF48F, $E963A535, $9E6495A3,
  $0EDB8832, $79DCB8A4, $E0D5E91E, $97D2D988,
  $09B64C2B, $7EB17CBD, $E7B82D07, $90BF1D91,
  $1DB71064, $6AB020F2, $F3B97148, $84BE41DE,
  $1ADAD47D, $6DDDE4EB, $F4D4B551, $83D385C7,
  $136C9856, $646BA8C0, $FD62F97A, $8A65C9EC,
  $14015C4F, $63066CD9, $FA0F3D63, $8D080DF5,
  $3B6E20C8, $4C69105E, $D56041E4, $A2677172,
  $3C03E4D1, $4B04D447, $D20D85FD, $A50AB56B,
  $35B5A8FA, $42B2986C, $DBBBC9D6, $ACBCF940,
  $32D86CE3, $45DF5C75, $DCD60DCF, $ABD13D59,
  $26D930AC, $51DE003A, $C8D75180, $BFD06116,
  $21B4F4B5, $56B3C423, $CFBA9599, $B8BDA50F,
  $2802B89E, $5F058808, $C60CD9B2, $B10BE924,
  $2F6F7C87, $58684C11, $C1611DAB, $B6662D3D,

  $76DC4190, $01DB7106, $98D220BC, $EFD5102A,
  $71B18589, $06B6B51F, $9FBFE4A5, $E8B8D433,
  $7807C9A2, $0F00F934, $9609A88E, $E10E9818,
  $7F6A0DBB, $086D3D2D, $91646C97, $E6635C01,
  $6B6B51F4, $1C6C6162, $856530D8, $F262004E,
  $6C0695ED, $1B01A57B, $8208F4C1, $F50FC457,
  $65B0D9C6, $12B7E950, $8BBEB8EA, $FCB9887C,
  $62DD1DDF, $15DA2D49, $8CD37CF3, $FBD44C65,
  $4DB26158, $3AB551CE, $A3BC0074, $D4BB30E2,
  $4ADFA541, $3DD895D7, $A4D1C46D, $D3D6F4FB,
  $4369E96A, $346ED9FC, $AD678846, $DA60B8D0,
  $44042D73, $33031DE5, $AA0A4C5F, $DD0D7CC9,
  $5005713C, $270241AA, $BE0B1010, $C90C2086,
  $5768B525, $206F85B3, $B966D409, $CE61E49F,
  $5EDEF90E, $29D9C998, $B0D09822, $C7D7A8B4,
  $59B33D17, $2EB40D81, $B7BD5C3B, $C0BA6CAD,

  $EDB88320, $9ABFB3B6, $03B6E20C, $74B1D29A,
  $EAD54739, $9DD277AF, $04DB2615, $73DC1683,
  $E3630B12, $94643B84, $0D6D6A3E, $7A6A5AA8,
  $E40ECF0B, $9309FF9D, $0A00AE27, $7D079EB1,
  $F00F9344, $8708A3D2, $1E01F268, $6906C2FE,
  $F762575D, $806567CB, $196C3671, $6E6B06E7,
  $FED41B76, $89D32BE0, $10DA7A5A, $67DD4ACC,
  $F9B9DF6F, $8EBEEFF9, $17B7BE43, $60B08ED5,
  $D6D6A3E8, $A1D1937E, $38D8C2C4, $4FDFF252,
  $D1BB67F1, $A6BC5767, $3FB506DD, $48B2364B,
  $D80D2BDA, $AF0A1B4C, $36034AF6, $41047A60,
  $DF60EFC3, $A867DF55, $316E8EEF, $4669BE79,
  $CB61B38C, $BC66831A, $256FD2A0, $5268E236,
  $CC0C7795, $BB0B4703, $220216B9, $5505262F,
  $C5BA3BBE, $B2BD0B28, $2BB45A92, $5CB36A04,
  $C2D7FFA7, $B5D0CF31, $2CD99E8B, $5BDEAE1D,

  $9B64C2B0, $EC63F226, $756AA39C, $026D930A,
  $9C0906A9, $EB0E363F, $72076785, $05005713,
  $95BF4A82, $E2B87A14, $7BB12BAE, $0CB61B38,
  $92D28E9B, $E5D5BE0D, $7CDCEFB7, $0BDBDF21,
  $86D3D2D4, $F1D4E242, $68DDB3F8, $1FDA836E,
  $81BE16CD, $F6B9265B, $6FB077E1, $18B74777,
  $88085AE6, $FF0F6A70, $66063BCA, $11010B5C,
  $8F659EFF, $F862AE69, $616BFFD3, $166CCF45,
  $A00AE278, $D70DD2EE, $4E048354, $3903B3C2,
  $A7672661, $D06016F7, $4969474D, $3E6E77DB,
  $AED16A4A, $D9D65ADC, $40DF0B66, $37D83BF0,
  $A9BCAE53, $DEBB9EC5, $47B2CF7F, $30B5FFE9,
  $BDBDF21C, $CABAC28A, $53B39330, $24B4A3A6,
  $BAD03605, $CDD70693, $54DE5729, $23D967BF,
  $B3667A2E, $C4614AB8, $5D681B02, $2A6F2B94,
  $B40BBE37, $C30C8EA1, $5A05DF1B, $2D02EF8D);

However, this is what my output is from both programs (I diffed the output, and it's the same for both of them), and it's incorrect:

0, 4c11db7, 9823b6e, d4326d9, 
130476dc, 17c56b6b, 1a864db2, 1e475005, 
2608edb8, 22c9f00f, 2f8ad6d6, 2b4bcb61, 
350c9b64, 31cd86d3, 3c8ea00a, 384fbdbd, 
4c11db70, 48d0c6c7, 4593e01e, 4152fda9, 
5f15adac, 5bd4b01b, 569796c2, 52568b75, 
6a1936c8, 6ed82b7f, 639b0da6, 675a1011, 
791d4014, 7ddc5da3, 709f7b7a, 745e66cd, 
9823b6e0, 9ce2ab57, 91a18d8e, 95609039, 
8b27c03c, 8fe6dd8b, 82a5fb52, 8664e6e5, 
be2b5b58, baea46ef, b7a96036, b3687d81, 
ad2f2d84, a9ee3033, a4ad16ea, a06c0b5d, 
d4326d90, d0f37027, ddb056fe, d9714b49, 
c7361b4c, c3f706fb, ceb42022, ca753d95, 
f23a8028, f6fb9d9f, fbb8bb46, ff79a6f1, 
e13ef6f4, e5ffeb43, e8bccd9a, ec7dd02d, 
34867077, 30476dc0, 3d044b19, 39c556ae, 
278206ab, 23431b1c, 2e003dc5, 2ac12072, 
128e9dcf, 164f8078, 1b0ca6a1, 1fcdbb16, 
18aeb13, 54bf6a4, 808d07d, cc9cdca, 
7897ab07, 7c56b6b0, 71159069, 75d48dde, 
6b93dddb, 6f52c06c, 6211e6b5, 66d0fb02, 
5e9f46bf, 5a5e5b08, 571d7dd1, 53dc6066, 
4d9b3063, 495a2dd4, 44190b0d, 40d816ba, 
aca5c697, a864db20, a527fdf9, a1e6e04e, 
bfa1b04b, bb60adfc, b6238b25, b2e29692, 
8aad2b2f, 8e6c3698, 832f1041, 87ee0df6, 
99a95df3, 9d684044, 902b669d, 94ea7b2a, 
e0b41de7, e4750050, e9362689, edf73b3e, 
f3b06b3b, f771768c, fa325055, fef34de2, 
c6bcf05f, c27dede8, cf3ecb31, cbffd686, 
d5b88683, d1799b34, dc3abded, d8fba05a, 
690ce0ee, 6dcdfd59, 608edb80, 644fc637, 
7a089632, 7ec98b85, 738aad5c, 774bb0eb, 
4f040d56, 4bc510e1, 46863638, 42472b8f, 
5c007b8a, 58c1663d, 558240e4, 51435d53, 
251d3b9e, 21dc2629, 2c9f00f0, 285e1d47, 
36194d42, 32d850f5, 3f9b762c, 3b5a6b9b, 
315d626, 7d4cb91, a97ed48, e56f0ff, 
1011a0fa, 14d0bd4d, 19939b94, 1d528623, 
f12f560e, f5ee4bb9, f8ad6d60, fc6c70d7, 
e22b20d2, e6ea3d65, eba91bbc, ef68060b, 
d727bbb6, d3e6a601, dea580d8, da649d6f, 
c423cd6a, c0e2d0dd, cda1f604, c960ebb3, 
bd3e8d7e, b9ff90c9, b4bcb610, b07daba7, 
ae3afba2, aafbe615, a7b8c0cc, a379dd7b, 
9b3660c6, 9ff77d71, 92b45ba8, 9675461f, 
8832161a, 8cf30bad, 81b02d74, 857130c3, 
5d8a9099, 594b8d2e, 5408abf7, 50c9b640, 
4e8ee645, 4a4ffbf2, 470cdd2b, 43cdc09c, 
7b827d21, 7f436096, 7200464f, 76c15bf8, 
68860bfd, 6c47164a, 61043093, 65c52d24, 
119b4be9, 155a565e, 18197087, 1cd86d30, 
29f3d35, 65e2082, b1d065b, fdc1bec, 
3793a651, 3352bbe6, 3e119d3f, 3ad08088, 
2497d08d, 2056cd3a, 2d15ebe3, 29d4f654, 
c5a92679, c1683bce, cc2b1d17, c8ea00a0, 
d6ad50a5, d26c4d12, df2f6bcb, dbee767c, 
e3a1cbc1, e760d676, ea23f0af, eee2ed18, 
f0a5bd1d, f464a0aa, f9278673, fde69bc4, 
89b8fd09, 8d79e0be, 803ac667, 84fbdbd0, 
9abc8bd5, 9e7d9662, 933eb0bb, 97ffad0c, 
afb010b1, ab710d06, a6322bdf, a2f33668, 
bcb4666d, b8757bda, b5365d03, b1f740b4,
Community
  • 1
  • 1
Programmer_D
  • 601
  • 2
  • 15
  • 27
  • 1
    Are you using the same generator polynomial as the people you're checking your table against? – genisage Sep 25 '14 at 22:42
  • @genisage Yes, I am. I am using the CRC-32 polynomial that's used for Ethernet. Here it is, listed from the website where I got the output from: x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1 – Programmer_D Sep 25 '14 at 22:51
  • Printing five columns of output makes it *really hard* to find the interesting coefficients. Please use a power of two. – Ben Voigt Sep 25 '14 at 22:51
  • 1
    Is it possible that they represented it with the highest power as the most significant bit and you did it with the highest power as the least significant bit? – genisage Sep 25 '14 at 22:53
  • @genisage: I think that's the difference, both in the bit-order of the CRC values, and the bit-order of the array indexes. Can't construct one table from the other, though, because the bit shifts are effectively performed in the wrong direction as well. – Ben Voigt Sep 25 '14 at 22:54
  • As 64-bit `long` is prevelent these days as well as selected processors using 16-bit `int`, best to use _exact_ width integers for this sort of code. `uint32_t, uint16_t and uint8_t`. – chux - Reinstate Monica Sep 25 '14 at 23:09

2 Answers2

22

The bits are reversed. Note that the table entry for array[0x80] (0x80 is 0x01 reversed) = 0xEDB88320, which is 0x04C11DB7 reversed.

Example code:

#include <iostream>
#include <iomanip>

void make_crc_table(unsigned long crcTable[]) {
    unsigned long POLYNOMIAL = 0xEDB88320;
    unsigned long remainder;
    unsigned char b = 0;
    do {
        // Start with the data byte
        remainder = b;
        for (unsigned long bit = 8; bit > 0; --bit) {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ POLYNOMIAL;
            else
                remainder = (remainder >> 1);
        }
        crcTable[(size_t)b] = remainder;
    } while(0 != ++b);
}

unsigned long gen_crc(unsigned char *p, size_t n, unsigned long crcTable[]) {
    unsigned long crc = 0xfffffffful;
    size_t i;
    for(i = 0; i < n; i++)
        crc = crcTable[*p++ ^ (crc&0xff)] ^ (crc>>8);
    return(~crc);
}

int main() {
    unsigned long crcTable[256];
    make_crc_table(crcTable);
    // Print the CRC table
    for (size_t i = 0; i < 256; i++) {
        std::cout << std::setfill('0') << std::setw(8) << std::hex << crcTable[i];
        if (i % 4 == 3)
            std::cout << std::endl;
        else
            std::cout << ", ";
    }
    return 0;
}
rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • I see that value in the "correct" table, but I'm not sure how to correct the algorithms. Reversing the polynomial and using 0xEDB88320 didn't seem to work. Which bits should I reverse? – Programmer_D Sep 26 '14 at 03:57
  • @Programmer_D - I updated the answer with example code. – rcgldr Sep 26 '14 at 11:12
  • @Programmer_D - follow up, with the one's complement of crc (~crc), then if you append that crc to the data, (little endian, so on X86, *(unsigned long *)(array+n) = crc ), then if you reencode using gen_crc(array, n+4, crcTable), the crc will be 0x2144df1c if there are no errors in the data. After a reencode, you can use crc ^= 0x2144df1c; to remove the effect of ~crc used in gen_crc. – rcgldr Sep 27 '14 at 06:05
  • It seems like the gen_crc implementation is wrong. Looking at the wiki page (https://en.wikipedia.org/wiki/Cyclic_redundancy_check) the lookup value should be first ((CRC ^ byte) & 0xFF), not (byte ^ (CRC&0xFF)). – TypeKazt Jan 24 '18 at 19:51
  • 2
    @TypeKazt - in this case, the order of operations doesn't matter, since p is a pointer to a byte (unsigned char). In either case, ((CRC ^ byte)&0xff) or (byte ^ (CRC&0xff)), the result is the same, an 8 bit index that is promoted to a 32 bit index with leading zero bits since it is used as an index to the table (the xor operation also promotes to a 32 bit index with leading zero bits in the second case) – rcgldr Jan 25 '18 at 02:50
  • To calculate the CRC, (simple CRC calculation) is this enough? `CRC ^= 0x741B8CD7` or we need something more? – Arash Jan 08 '21 at 05:16
  • @Arash - where did you get the 741B8CD7 from? Sorry for the late response, I seem to missing some notifications. – rcgldr Jan 13 '21 at 20:07
  • @rcgldr Can I ask you a quick question, please? It might not be related. Which one is recommended, why? Encode data with two 32-bit CRCs (with different polynomials) or a 64-bit CRC? – Arash Jan 14 '21 at 00:12
  • 1
    @Arash - depends on the amount of data and the probability of bit errors. There is a 32 bit CRC guaranteed to detect up to 5 error bits with 32767 bits of data + crc. There is a 64 bit CRC guaranteed to detect up to 5 error bits with 65535 bits of data + crc. Finding a 64 bit CRC that handles 5 or more error bits takes a long time, so there aren't a lot of 64 bit CRC. If the data is larger, like 128k + bits, then it doesn't matter, the probability of not detecting an error is about 1 in 2^64 using two 32 bit CRC's or one 64 bit CRC. – rcgldr Jan 14 '21 at 00:50
  • @rcgldr Thank you. and for the last one, is calculating 64bit CRC more complex (or time-consuming) than 32bit CRC? (is there any computational benefit to use 64 over two 32bits?) – Arash Jan 15 '21 at 03:35
  • 1
    @Arash - for a processor with 64 bit registers, then a typical CRC calculation would be faster with one 64 bit CRC than two 32 bit CRCs. – rcgldr Jan 15 '21 at 15:23
  • @rcgldr Thank you so much for all your help. could you please give me some references? (I want to know why it's that way?) – Arash Jan 15 '21 at 17:25
  • 1
    @Arash - Here is a collection of 16, 32, and 64 bit [CRC examples](https://github.com/jeffareid/crc). Look at the ??????c.cpp source files for typical CRC implementations. The assembly (.asm) files are versions of [github Intel CRC examples](https://github.com/intel/isa-l/tree/master/crc) modified to run with Visual Studio, with comments added for the RK?? constants (the Intel files are missing some comments). The ??????g.cpp source files are used to generate the RK?? constants. – rcgldr Jan 15 '21 at 20:16
  • 1
    @Arash - the assembly files implementation is explained in [Intel - CRC using PCLMULQDQ pdf](https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf) . Note that my assembly examples do not include the variations with ZMM registers, as those are only available on some Intel processors with [AVX512](https://en.wikipedia.org/wiki/AVX-512), which I don't have. – rcgldr Jan 15 '21 at 20:28
3

If there is not enough Flash and RAM (embedded software), you can use this function:

uint32_t CRC32_function(uint8_t *buf, uint32_t len){

    uint32_t val, crc;
    uint8_t i;

    crc = 0xFFFFFFFF;
    while(len--){
        val=(crc^*buf++)&0xFF;
        for(i=0; i<8; i++){
            val = val & 1 ? (val>>1)^0xEDB88320 : val>>1;
        }
        crc = val^crc>>8;
    }
    return crc^0xFFFFFFFF;
}

But CRC calculation takes more time.

סטנלי גרונן
  • 2,917
  • 23
  • 46
  • 68
3r6
  • 31
  • 1