How to Calculate 32 Bit Crc in Ruby on Rails

How to calculate 32 bit CRC in Ruby on rails?

You could use Ruby's Zlib module.

require 'zlib'
crc32 = Zlib::crc32('input field value')

Fast CRC with PCLMULQDQ *NOT* reflected

I have 6 sets of code for 16, 32, 64 bit crc, non-reflected and reflected here. The code is setup for Visual Studio. Comments have been added to the constants which were missing from Intel's github site.

https://github.com/jeffareid/crc

32 bit non-relfected is here:

https://github.com/jeffareid/crc/tree/master/crc32f

You'll need to change the polynomial in crc32fg.cpp, which generates the constants. The polynomial you want is actually:

0x00000001000000afull

I made this change to crc32fg.cpp to generate the rk.. constants at the end of this answer.

what is x?

A CRC uses polynomials with 1 bit coefficients. For example 0x0B is really x^3 + x + 1.

The XMM registers can read|write 16 bytes | 128 bits at a time, but PCLMULQDQ can only carryless multiply two 64 bit operands to produce a 128 bit product. So the 128 bits are split up into two 64 bit operands, then each operand is multiplied by a constant to "fold" it forwards. Since the XMM registers can operate somewhat in parallel, 8 XMM registers are used to read | write 128 bytes | 1024 bits at a time. Each folding step "advances" 16 bytes | 128 bits of data forwards 128 bytes | 1024 bits, by multiplying it by constants. The lower 64 bits are multiplied by x^(1024) mod poly to create a 128 bit product that is "advanced" by 1024 bits. The upper 64 bits are multiplied by x^(1024+64) mod poly to create a 128 bit product that is advanced byte 1024+64 bits (the +64 is needed because the product is based on the upper 64 bits of 128 bits of data). The two 128 bit products are xor'ed together, and then later xor'red with data 128 bytes | 1024 bits later in the buffer.

Note that the example in the Intel document uses 4 XMM registers to advance data 64 bytes | 512 bits at a time, but the github examples I've seen and the examples I use in my github repository use 8 XMM registers and advance 128 bytes | 1024 bits at a time. For the relatively small number of processors that support AVX512 | ZMM registers, there are examples that advance 256 bytes | 2048 bits at a time. I don't own a computer with AVX512, so I don't have any code for that.

Since XMM read|writes are little endian, PSHUFB is used to reverse the bytes after each read.

The code is mostly based on 64 bit CRC that uses a 65 bit polynomial, but for a 32 bit CRC, this can be handled by setting the lower 32 bits to zero. For 32 bit CRC, most of the constants are only 32 bits, and shifted left 32 bits to simplify usage with PCLMULQDQ, and are adjusted to compensate for the shift, so instead of x^(a) mod poly, it's (x^(a-32) mod poly)<<32. The constants for the actual 33 bit polynomial and it's "inverse" x^64 / polynomial are 33 bits and are not shifted left, and the 64 bit value that uses these constants to create the actual CRC is shifted left 32 bits instead.

The folding process doesn't produce a CRC, it just transforms data to advance it. Once all the data is processed, the 8 XMM registers are folded into one 128 bit value using the constants rk09, rk10, ..., rk19, rk20, rk01, rk02. At this point (label _128_done:) there are 128 bits of data, and since the code is based on 64 bit CRC logic, 64 bit's of zeroes are logically appended, so in effect it's a 192 bit value where the imaginary lower 64 bits are all zero. The upper 64 bits are folded forward by 128 bits, resulting in a 128 bit value in XMM7 ready to calculate a 64 bit CRC, but since this is a 32 bit CRC, XMM7 has 96 bits of data shifted left 32 bits. The upper 32 bits are folded forwards by 64 bits (in this case the 96 bit value and rk06 are both shifted left by 32 bits, so rk06 in this case folds by 64 bits (x^64 mod poly) and shifts left by 32 bits. The result is a 64 bit value shifted left 32 bits in XMM7.

The quotient of a 64 bit number divided by a 33 bit polynomial only needs the upper 32 bits of the 64 bit number, so the left shifted 64 bit value has the upper 32 bits where it will be convenient to calculate a quotient. The divide is really a multiply by x^64 / polynomial, PCLMULQDQ will just specify to use the upper 64 bit part of XMM7 to use the upper 32 bits of the left shifted 64 bit number. The actual CRC calculation is based on this logic:

quotient = upper 32 bits of 64 bit value / polynomial
product  = quotient * polynomial
CRC      = 64 bit value XOR product

The division is done by multiplying by the inverse: x^64 / poly. Since the poly and it's inverse are 33 bits, they can't be shifted left 32 bits, so the code shifts the product left 4 bytes after each multiply. The CRC ends up in bits 32 to 63 of XMM7 and pextrd eax,xmm7,1 is used to get those 32 bits.

---

I modified crc32fg.cpp to use CRC polynomial 0x1000000af, and this is what I get. For this polynomial, rk07 == rk08, but for other polynomials, they will be different.

rk01    dq      000295f2300000000h      ; x^(32* 3) mod P(x) << 32
rk02    dq      0fafa517900000000h      ; x^(32* 5) mod P(x) << 32
rk03    dq      05cd86bb500000000h      ; x^(32*31) mod P(x) << 32
rk04    dq      0af6f37a300000000h      ; x^(32*33) mod P(x) << 32
rk05    dq      000295f2300000000h      ; x^(32* 3) mod P(x) << 32
rk06    dq      00000445500000000h      ; x^(32* 2) mod P(x) << 32
rk07    dq      000000001000000afh      ; floor(2^64/P(x))
rk08    dq      000000001000000afh      ; P(x)
rk09    dq      09bd57b5d00000000h      ; x^(32*27) mod P(x) << 32
rk10    dq      0b7a4d76400000000h      ; x^(32*29) mod P(x) << 32
rk11    dq      01ae0004200000000h      ; x^(32*23) mod P(x) << 32
rk12    dq      0e7720be600000000h      ; x^(32*25) mod P(x) << 32
rk13    dq      09c7fc8fe00000000h      ; x^(32*19) mod P(x) << 32
rk14    dq      03885faf800000000h      ; x^(32*21) mod P(x) << 32
rk15    dq      0b477ad7100000000h      ; x^(32*15) mod P(x) << 32
rk16    dq      00ac2ae3d00000000h      ; x^(32*17) mod P(x) << 32
rk17    dq      05eae9dbe00000000h      ; x^(32*11) mod P(x) << 32
rk18    dq      0784a483800000000h      ; x^(32*13) mod P(x) << 32
rk19    dq      07d21bf2000000000h      ; x^(32* 7) mod P(x) << 32
rk20    dq      0faebd3d300000000h      ; x^(32* 9) mod P(x) << 32

How to calculate the 6 Bit CRC using the c programming lanuguage?

Without an example, I can't be sure, but this will compute the CRC as described, assuming that the initial values of the flip flops are zero.

unsigned crc6biss(uint32_t data, unsigned bits) {
    while (bits--)
        data = data & 0x80000000 ? (data << 1) ^ 0x0c000000 : data << 1;
    return ~data >> 26;
}

Here data are your data bits, but, very importantly, shifted up in the 32-bit word so that the most significant bit of the data is the most significant bit of data. bits is how many bits are to be processed. So the data bits are the bits 32-bits..31 of data. The remaining bits are zeros. The 6-bit CRC is returned in the least significant six bits of the return value.

From your documentation, bits would be 18, 19, or 21.

CRC-32 values not matching

I was able to figure out the issues. I used this https://crccalc.com/?crc=C5&method=crc32&datatype=hex&outtype=0 to confirm CRC values that I was getting on microcontroller and RPi.

First issue was on microcontroller, where I was not even performing the CRC on the data, instead I was performing on the address where that data was stored.

Second issue was that MCU was performing CRC on the value which was stored in the little-endian form. On RPi also, CRC was being performed on values stored in little-endian form. Hence, since the endianness was same on both the devices, I did not have to reverse the bits or bytes.

After doing these changes, I was able to get correct and same CRC values on both RPi and microcontroller.

How do I convert a CRC function from C to Ruby?

It looks like you are using different values for your crc_init; the C version is 0x55555555 (8 5's) and the Ruby version is 0x555555 (6 5's). You should correct this first.

Also, I suspect you need to use & rather than && on this line:

cur = (cur >> 1) && 0xff  # only 8 bit

CRC-32 check fails with DEC 5.2

Your assertion is based on the following property holding:

CRC(arr + [CRC(arr)]) = 0

where I am using + to indicate array concatenation.

I believe that the particular CRC32 implementation that DEC exposes does not have this property. DEC offers three CRC32 variants, named CRC_32, CRC_32CCITT and CRC_32ZModem. Only CRC_32ZModem has the property that you assert.

Serg suggests that you should be asserting that:

not CRC(arr + [not CRC(arr)]) = 0

which holds for CRC_32 and CRC_32CCITT, but not for CRC_32ZModem.

---

Related Topics