CRC16_mcrf4xx Algorithm

[Sara_Lagro]

Hello dear friends ,
I need to integrate in my delphi project a CRC calculation algorithm , I have to use an algo type CRC16_mcrf4xx

unfortunately I have not found articles that clearly explain this algo, on the other hand, I found an implementation in C,
tried to translate it with the help of a friend, but it didn't give a good result (I compared with ..     https://crccalc.com   .)

i hope to find someone who can help me understand this algo ,.
thank you in advance.

#include <stdint.h>
#include <stddef.h>

uint16_t crc16_mcrf4xx(uint16_t crc, uint8_t *data, size_t len)
{
    if (!data || len < 0)
        return crc;

    while (len--) {
        crc ^= *data++;
        for (int i=0; i<8; i++) {
            if (crc & 1)  crc = (crc >> 1) ^ 0x8408;
            else          crc = (crc >> 1);
        }
    }
    return crc;
}

[Laksen]

Code: Pascal  [Select][+][-]

1. program test;
2.  
3. function crc16_mcrf4xx(crc: word; data: pbyte; len: sizeint): word;
4. var
5.   i: SizeInt;
6. begin
7.   if len < 0 then exit(crc);
8.  
9.   while len > 0 do
10.   begin
11.     crc := crc xor data^;
12.     inc(data);
13.  
14.     dec(len);
15.  
16.     for i:=0 to 7 do
17.     begin
18.       if odd(crc) then
19.         crc:=(crc shr 1) xor $8408
20.       else
21.         crc:=(crc shr 1);
22.     end;
23.   end;
24.    
25.   crc16_mcrf4xx:=crc;
26. end;
27.  
28. const
29.   CRC_INIT = $FFFF;
30.  
31. var
32.   inputData: pchar = '123456789';
33.   crc: word;
34. begin
35.   crc:=CRC_INIT;
36.   crc:=crc16_mcrf4xx(crc, pbyte(inputData), length(inputData));
37.  
38.   writeln(hexstr(crc, 4));
39. end.
40.  

[MathMan]

Thread starter seems to be concerned about efficiency / speed. Maybe instead of

Code: Pascal  [Select][+][-]

1.     for i:=0 to 7 do
2.     begin
3.       if odd(crc) then
4.         crc:=(crc shr 1) xor $8408
5.       else
6.         crc:=(crc shr 1);
7.     end;
8.  

do the following (which avoids data dependant branching in a tight loop)

Code: Pascal  [Select][+][-]

1.     for i:=0 to 7 do
2.     begin
3.       crc:=(crc shr 1) xor ( $8408 and word( -( crc and $1 ) ) );
4.     end;
5.  

Above given also allows for complete roll-out of the tight loop (if one would be really crazy about speed  ).

Cheers,
MathMan

[MarkMLl]

Can anybody comment on the relative efficiency of that type of algorithm and using a table lookup?

MarkMLl

[lucamar]

Can anybody comment on the relative efficiency of that type of algorithm and using a table lookup?

For that kind of algorithm a carefully selected LUT will almost always be faster than calculating on-the-fly. However, it'll also waste quite a lot of space and, since it's a continuous function, there must nevertheless be some calculation done which can be easily optimized (no divisions, etc.) and the speed up won't be as much, so the speed vs. memory consumption trade-off argues against it.

IMHO, of course; I'm not really an expert on this so I might be woefully wrong ...

[Laksen]

Can anybody comment on the relative efficiency of that type of algorithm and using a table lookup?

With a pretty straightforward approach like the following it seems to be about 4 times faster (than with MathMan's branchfree suggestion) with a table:

Code: Pascal  [Select][+][-]

1. var
2.   LUT: array[0..$FFFF] of word;
3.  
4. procedure precalc;
5. var
6.   i,i2: SizeInt;
7.   crc: word;
8. begin
9.   for i:=0 to $FFFF do
10.   begin
11.     crc:=i;
12.     for i2:=0 to 7 do
13.     begin
14.       if odd(crc) then
15.         crc:=(crc shr 1) xor $8408
16.       else
17.         crc:=(crc shr 1);
18.     end;
19.     LUT[i]:=crc;
20.   end;
21. end;
22.  
23. function crc16_mcrf4xx_table(crc: word; data: pbyte; len: sizeint): word;
24. var
25.   i: SizeInt;
26. begin
27.   if len < 0 then exit(crc);
28.  
29.   while len > 0 do
30.   begin
31.     crc := LUT[crc xor data^];
32.     inc(data);
33.     dec(len);
34.   end;
35.    
36.   crc16_mcrf4xx_table:=crc;
37. end;
38.  

[MarkMLl]

Thanks both for the performance comments. It must be said though that for a 16-bit CRC the table size is pretty small by the standards of today's microcontrollers particularly if it can be put in ROM/Flash.

I had great fun a few years ago writing an interface to a piece of HP kit which could look at a captured packet and deduce the CRC type :-)

MarkMLl

[MathMan]

If my math doesn't leave me here the table size in Laksens example is much to large. It is enough to consider the least 8 bit for the calculation, that is the table size needs to be 256 word only. These 512 byte total memory will not degrade cache efficiency (like Lucamar assumed) with exception of the smallest MCU.

Forgot to mention that the approach with the reduced table then still requires one xor operation in addition to the table lookup - this might not have been clear from my explanation above. Nevertheless I think it might be the best compromise in terms of speed & density wrt the specific environment.

@Laksen - did you by any chance also compare the speed of the branch free with the branched version? It was a shot from the hip, to some degree.

Cheers,
MathMan

[MarkMLl]

Yes, I think 256x16 bits is canonical cor any of the CRC-16 family. Of course, getting them into any particular microcontroller's ROM or Flash is likely to be device-specific.

MarkMLl