Recent

Author Topic: CRC16_mcrf4xx Algorithm  (Read 1826 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 ,.
thank you in advance.

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
    • J-Software
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 »
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  :D).

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 !!!) :P
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
    • J-Software
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

 

TinyPortal © 2005-2018