### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: CRC16_mcrf4xx Algorithm  (Read 1825 times)

#### Sara_Lagro

• Newbie
• Posts: 1
##### CRC16_mcrf4xx Algorithm
« on: May 28, 2021, 01:13:58 pm »
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 ,.

Quote
#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

• Hero Member
• Posts: 684
##### Re: CRC16_mcrf4xx Algorithm
« Reply #1 on: May 28, 2021, 01:28:06 pm »
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

• Full Member
• Posts: 227
##### Re: CRC16_mcrf4xx Algorithm
« Reply #2 on: May 28, 2021, 03:24:51 pm »

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

• Hero Member
• Posts: 2875
##### Re: CRC16_mcrf4xx Algorithm
« Reply #3 on: May 28, 2021, 05:14:11 pm »
Can anybody comment on the relative efficiency of that type of algorithm and using a table lookup?

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

#### lucamar

• Hero Member
• Posts: 4165
##### Re: CRC16_mcrf4xx Algorithm
« Reply #4 on: May 28, 2021, 06:13:28 pm »
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 ...
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!)
Lazarus/FPC 2.0.8/3.0.4 & 2.0.12/3.2.0 - 32/64 bits on:
(K|L|X)Ubuntu 12..18, Windows XP, 7, 10 and various DOSes.

#### Laksen

• Hero Member
• Posts: 684
##### Re: CRC16_mcrf4xx Algorithm
« Reply #5 on: May 28, 2021, 06:25:18 pm »
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

• Hero Member
• Posts: 2875
##### Re: CRC16_mcrf4xx Algorithm
« Reply #6 on: May 28, 2021, 07:42:28 pm »
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
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

#### MathMan

• Full Member
• Posts: 227
##### Re: CRC16_mcrf4xx Algorithm
« Reply #7 on: May 29, 2021, 11:38:26 am »
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
« Last Edit: May 29, 2021, 12:11:49 pm by MathMan »

#### MarkMLl

• Hero Member
• Posts: 2875
##### Re: CRC16_mcrf4xx Algorithm
« Reply #8 on: May 29, 2021, 11:58:24 am »
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
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories