Forum > Suggestions

CRC16_mcrf4xx Algorithm

(1/2) > >>

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 ,.

--- 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;
}

--- End quote ---

Laksen:

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---program test; function crc16_mcrf4xx(crc: word; data: pbyte; len: sizeint): word;var  i: SizeInt;begin  if len < 0 then exit(crc);   while len > 0 do  begin    crc := crc xor data^;    inc(data);     dec(len);     for i:=0 to 7 do    begin      if odd(crc) then        crc:=(crc shr 1) xor \$8408      else        crc:=(crc shr 1);    end;  end;      crc16_mcrf4xx:=crc;end; const  CRC_INIT = \$FFFF; var  inputData: pchar = '123456789';  crc: word;begin  crc:=CRC_INIT;  crc:=crc16_mcrf4xx(crc, pbyte(inputData), length(inputData));   writeln(hexstr(crc, 4));end.

MathMan:

--- Quote from: Laksen on May 28, 2021, 01:28:06 pm ---
--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---    for i:=0 to 7 do    begin      if odd(crc) then        crc:=(crc shr 1) xor \$8408      else        crc:=(crc shr 1);    end;
--- End quote ---

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

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---    for i:=0 to 7 do    begin      crc:=(crc shr 1) xor ( \$8408 and word( -( crc and \$1 ) ) );    end;
Above given also allows for complete roll-out of the tight loop (if one would be really crazy about speed  :D).

Cheers,
MathMan

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

MarkMLl

lucamar:

--- Quote from: MarkMLl 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?
--- End quote ---

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 ... :-[