Gönderen Konu: CRC Hesaplama  (Okunma sayısı 12369 defa)

Çevrimdışı derwish

  • Üye
  • **
  • İleti: 29
CRC Hesaplama
« : 15 Aralık 2003, 11:30:11 »
Selam,

CRC(Cyclic Redundancy Check) hakkında bilgiye ihtiyacım var.

Ancak

aradıgım yuzeysel bilgi değil.

CRC nedir?  Nasıl kullanılır? Ornek kod bulmak (C code) mumkunmudur?

CRC8 -CRC16-CRC32 arasında ne fark vardır??

Bu konu

ile ilgili mumkunse Turkce değilse ingilizce kaynak arıyorum....



DerWish.

Çevrimdışı XNHCX

  • Profesyonel Üye
  • *****
  • İleti: 1583
CRC Hesaplama
« Yanıtla #1 : 15 Aralık 2003, 14:47:08 »

Çevrimdışı XNHCX

  • Profesyonel Üye
  • *****
  • İleti: 1583
CRC Hesaplama
« Yanıtla #2 : 15 Aralık 2003, 14:52:59 »

Çevrimdışı z

  • proje
  • Profesyonel Üye
  • *****
  • İleti: 4743
CRC Hesaplama
« Yanıtla #3 : 07 Ekim 2006, 14:15:53 »
http://www.miscel.dk/MiscEl/CRCcalculations.html

Yukaridaki siteyi yapanin ellerine saglik. Bilgiler acik ve guzel. Siteye ne olur ne olmaz dusuncesiyle icerigini buraya da aldim.

# General info
# Code for crc8 calculations
# - crc8 bit, normal
# - crc8 bit, inverted/reversed/reflected
# - crc8 byte, normal
# - crc8 byte, inverted/reversed/reflected
# Code for crc16 calculations
# - crc16 bit, normal
# - crc16 bit, inverted/reversed/reflected
# - crc16 byte normal
# - crc16 byte, inverted/reversed/reflected
# Code for crc32 calculations
# - crc32 bit, normal
# - crc32 bit, inverted/reversed/reflected
# - crc32 byte, normal
# - crc32 byte, inverted/reversed/reflected
# Notes
General info

This page shows how to code a crc calculation, both normal and reversed (reflected) code is shown. All coding examples are in Delphi pascal, I belive this is very readable code, and easy to translate to other languages.
Using the reverse version of the code, with the inverted polynom, will give same result as reversing the data, before calculating the crc and reversing the final result.
CRC code are usual made in two performance categories, the low performance algorithms with bit handling and the high performance table drive algorithm with byte handling. The table can either be pregenerated and saved together with the code or generated on the fly. On small microcontrollers with limited ram, it is usual best to pregenerate the table and save it in rom/flash memory.
The table will always be 256 word large, the word size depends on the crc algorithms used (crc8=8 bit, crc16=16 bit, crc32=32 bit), but sometimes it may be a good idea to use a larger size, to get word aligment on the processor used.

Both the bit and the byte based routines are show here.
The bit routines can be used directly, but the byte routines need to initialize the table first. This is done with the bit routine from the "GenerateTable..." routine.
I.e. to use the byte based routines your need to include a pregenerated table or the bit routine to generate the table. The Crc and Checksum page can be used to pregenerate the table.

If this code is implemented on small processors, it is recommended to reduce the variable and table size from 32 bits to 8 bits for crc8 and 16 bits for crc16. It will also improve performance to use pointers to data, and avoid copying data around.

Use Crc and Checksum page in MiscEl to verify your code.


CRC8
The following polynomial are used:
Normal   Inverted/reversed/reflected
$07   $e0
$31   $8C
CRC8 bit, normal

function crc8(Buffer:String;Polynom,Initial:Cardinal):Cardinal;
var
  i,j                   : Integer;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=Result xor ord(buffer);
  for j:=0 to 7 do begin
    if (Result and $80)<>0 then Result:=(Result shl 1) xor Polynom
    else Result:=Result shl 1;
    end;
  end;
Result:=Result and $ff;
end;

CRC8 bit, inverted/reversed/reflected
Remember to use corresponding polynomial values.

function crc8reverse(Buffer:String;Polynom,Initial:Cardinal):Cardinal;
var
  i,j                   : Integer;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=Result xor ord(buffer);
  for j:=0 to 7 do begin
    if (Result and $01)<>0 then Result:=(Result shr 1) xor Polynom
    else Result:=Result shr 1;
    end;
  end;
end;

CRC8 byte, normal

var
  CrcTable              : Array[0..255] of Cardinal;

function GenerateTableCrc8(Poly:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
for i:=0 to 255 do CrcTable:=Crc8(chr(i),Poly,0);
end;

function Crc8Byte(Buffer:String;Initial:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=(Result shl 8 ) xor CrcTable[(ord(Buffer) xor (Result)) and $ff];
  end;
Result:=Result and $ff;
end;

CRC8 byte, inverted/reversed/reflected

var
  CrcTable              : Array[0..255] of Cardinal;

function GenerateTableCrc8Reverse(Poly:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
for i:=0 to 255 do CrcTable:=Crc8Reverse(chr(i),Poly,0);
end;

function Crc8ByteReverse(Buffer:String;Initial:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=(Result shr 8 ) xor CrcTable[(ord(Buffer) xor Result) and $ff];
  end;
end;

CRC16
The following polynomial are used:
Normal   Inverted/reversed/reflected
$8005   $A001   Std.
$1021   $8408   CCITT, X24
$4003   $C002   
$0811   $8810   
CRC16 bit, normal

function crc16(Buffer:String;Polynom,Initial:Cardinal):Cardinal;
var
  i,j                   : Integer;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=Result xor (ord(buffer) shl 8 );
  for j:=0 to 7 do begin
    if (Result and $8000)<>0 then Result:=(Result shl 1) xor Polynom
    else Result:=Result shl 1;
    end;
  end;
Result:=Result and $ffff;
end;

CRC16 bit, inverted/reversed/reflected
Remember to use corresponding polynomial values.

function crc16reverse(Buffer:String;Polynom,Initial:Cardinal):Cardinal;
var
  i,j                   : Integer;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=Result xor ord(buffer);
  for j:=0 to 7 do begin
    if (Result and $0001)<>0 then Result:=(Result shr 1) xor Polynom
    else Result:=Result shr 1;
    end;
  end;
end;

CRC16 byte, normal

var
  CrcTable              : Array[0..255] of Cardinal;

function GenerateTableCrc16(Poly:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
for i:=0 to 255 do CrcTable:=Crc16(chr(i),Poly,0);
end;

function Crc16Byte(Buffer:String;Initial:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=(Result shl 8 ) xor CrcTable[(ord(Buffer) xor (Result shr 8 )) and $ff];
  end;
Result:=Result and $ffff;
end;

CRC16 byte, inverted/reversed/reflected

var
  CrcTable              : Array[0..255] of Cardinal;

function GenerateTableCrc16Reverse(Poly:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
for i:=0 to 255 do CrcTable:=Crc16Reverse(chr(i),Poly,0);
end;

function Crc16ByteReverse(Buffer:String;Initial:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=(Result shr 8 ) xor CrcTable[(ord(Buffer) xor Result) and $ff];
  end;
end;

CRC32
The following polynomial are used:
Normal   Inverted/reversed/reflected
$04C11DB7   $EDB88320   Std.
CRC32 bit, normal

function crc32(Buffer:String;Polynom,Initial:Cardinal):Cardinal;
var
  i,j                   : Integer;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=Result xor (ord(buffer) shl 24);
  for j:=0 to 7 do begin
    if (Result and $80000000)<>0 then Result:=(Result shl 1) xor Polynom
    else Result:=Result shl 1;
    end;
  end;
end;

CRC32 bit, inverted/reversed/reflected
Remember to use corresponding polynomial values.

function crc32reverse(Buffer:String;Polynom,Initial:Cardinal):Cardinal;
var
  i,j                   : Integer;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=Result xor ord(buffer);
  for j:=0 to 7 do begin
    if (Result and $00000001)<>0 then Result:=(Result shr 1) xor Polynom
    else Result:=Result shr 1;
    end;
  end;
end;

CRC32 byte, normal

var
  CrcTable              : Array[0..255] of Cardinal;

function GenerateTableCrc32(Poly:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
for i:=0 to 255 do CrcTable:=Crc32(chr(i),Poly,0);
end;

function Crc32Byte(Buffer:String;Initial:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=(Result shl 8 ) xor CrcTable[(ord(Buffer) xor (Result shr 24)) and $ff];
  end;
Result:=Result;
end;

CRC32 byte, inverted/reversed/reflected

var
  CrcTable              : Array[0..255] of Cardinal;

function GenerateTableCrc32Reverse(Poly:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
for i:=0 to 255 do CrcTable:=Crc32Reverse(chr(i),Poly,0);
end;

function Crc32ByteReverse(Buffer:String;Initial:Cardinal):Cardinal;
var
  i                     : Cardinal;
begin
Result:=Initial;
for i:=1 to Length(Buffer) do begin
  Result:=(Result shr 8 ) xor CrcTable[(ord(Buffer) xor Result) and $ff];
  end;
end;

Notes

    * Cardinal: 32 bit unsigned integer, but in crc8 and crc16 a shorter variable can be used
    * and: Same as & in C
    * xor: Same as ^ in C
    * shl: Same as << in C
    * shr: Same as >> in C
    * <>: Same as != in C
    * String: A string of byte size characters with dynamic length
    * ord: Type cast the value of a character to a integer
    * chr: Type cast the value of a integer to a character and in this case to a string with the length of 1
    * Remark: The code for all reverse algorithms are the same as long as calculation are done in 32 bits

Çevrimdışı M.s.d

  • Yeni Üye
  • *
  • İleti: 11
Ynt: CRC Hesaplama
« Yanıtla #4 : 31 Temmuz 2015, 00:43:16 »
35 bytelık bir datanın crc sini hesaplamak istiyorum. crc8 kullanmak mı yoksa crc32 kullanmak mı daha iyi olur hız için?

Çevrimdışı engerex

  • Profesyonel Üye
  • *****
  • İleti: 1404
Ynt: CRC Hesaplama
« Yanıtla #5 : 31 Temmuz 2015, 03:55:06 »
 Adler32 daha hızlı olacaktır.

Çevrimdışı z

  • proje
  • Profesyonel Üye
  • *****
  • İleti: 4743
Ynt: CRC Hesaplama
« Yanıtla #6 : 31 Temmuz 2015, 04:24:16 »
8 bit işlemci ile hesaplayacaksan 8 bit hesap daha kısa sürecektir.
Yok 32 bit işlemci ile hesaplayacaksan 32 bit hesaplamak daha kısa sürecektir.

Çevrimdışı fatih6761

  • Emektar
  • *****
  • İleti: 691
Ynt: CRC Hesaplama
« Yanıtla #7 : 31 Temmuz 2015, 05:43:04 »
8 bit işlemci ile hesaplayacaksan 8 bit hesap daha kısa sürecektir.
Yok 32 bit işlemci ile hesaplayacaksan 32 bit hesaplamak daha kısa sürecektir.

Hocam bu durum kısmen işlemciye de bağlı, değil mi? Basit yapılı işlemciler için doğru olsada bazı aritmetik uzantıları olan işlemcilerde durum değişebilir. SSE, SIMD, AVX...
Mesela STM32F4 lerde (CortexM4F) temel SIMD işlecleri var ve çekirdek 32-bit iken tek clock cycle'da 4 tane 8-bit veya 2 tane 16-bit ile temel aritmetik işlemleri yapabiliyor.
Hatta özel durumlar için saturated (sonuç sınırları aştıysa sınıra sabitle) veya halving (işlemin sonucunu ikiye böl, tabi bölme olarak değil kaydıma olarak yapılıyordur)
sonuçlar da verebiliyor ki bu tek cycle'da iki işleme yakın bir durum.
Eğer gerçekten çok performans-kritik bir işlem varsa bunlara göz atıp assembly'ye yanaşmakta fayda var :)

Çevrimdışı z

  • proje
  • Profesyonel Üye
  • *****
  • İleti: 4743
Ynt: CRC Hesaplama
« Yanıtla #8 : 31 Temmuz 2015, 11:10:14 »
Artistik komut seti olan işlemciler için değil de genel lojik esaslar dahilinde bu yorumu yaptım.

Kaldı ki  C'de bu kodlar başka platformlara taşınamayak.   :)


Çevrimdışı fatih6761

  • Emektar
  • *****
  • İleti: 691
Ynt: CRC Hesaplama
« Yanıtla #9 : 31 Temmuz 2015, 15:30:49 »
Artistik komut seti olan işlemciler için değil de genel lojik esaslar dahilinde bu yorumu yaptım.

Kaldı ki  C'de bu kodlar başka platformlara taşınamayak.   :)

Hocam o noktada şöyle bir çözüm var: Preprocessor komutları ile mevcut platformda hangi komut setinin mevcut olduğunu derleme esnasında anlayıp ona göre en optimize kodu derlemek.
Atıyorum ABC ve XYZ diye iki komut setimiz olsun.

Kod: [Seç]
...
/* Görevimiz p'nin her elemanından q'nun elemanlarını birebir çıkartmak */
uint8_t p[4] = {1,2,3,4};
uint8_t q[4] = {5,6,7,8};
#ifdef __ABC_KOMUT_SETI_VAR
/* Tek clock cycle'da çözüm ama sadece STM32 için */
   asm("abc.sub4 [%0] [%0] [%1]", p, q);
#elif defined __XYZ_KOMUT_SETI_VAR
/* Yine tek cycle'da çözüm ama sadece genel olarak ARM için */
   __XYZ_SUB_QUAD(p, q, p);
#else
/* Tam olarak her ortama uyan çözüm */
   register int i;
   for  (i=0; i<4; ++i)
        r[i] -= q[i];
#endif

Eğer taşınabilir bir kod yazacaksak bence bu daha yakışıklı duruyor hocam  ;D

He, tabi bu işi derleyici bizden daha iyi mi yapar, olabilir, deneyip görmek lazım...

Çevrimdışı TMrc

  • Yeni Üye
  • *
  • İleti: 3
Ynt: CRC Hesaplama
« Yanıtla #10 : 30 Eylül 2016, 18:37:45 »
yenı uye oldugum icin konu acamadim ve bit yazinca sadece burasi geldigi icin mecburen buraya yazıyorum
entegrelerde 8-12-14-16 bit gibi hesaplama ya da bilgilere nasıl ulaşabılırım.
bit nasil hesaplanir.
« Son Düzenleme: 01 Ekim 2016, 15:43:57 Gönderen: TMrc »

Çevrimdışı mehmet

  • Global Moderator
  • Profesyonel Üye
  • *****
  • İleti: 2868
  • Modlar da ölümlü...
    • El Feneri
Ynt: CRC Hesaplama
« Yanıtla #11 : 30 Eylül 2016, 23:46:52 »
@TMrc foruma hoşgeldiniz...

Mesajınızın daha okunaklı hale gelmesi için imla
kurallarına göre düzenlenmesi uygun olacaktır...

Kolaylıklar...
"Bir mum diğer mumu tutuşturmakla ışığından bir şey kaybetmez.''Mevlânâ
"Kendimiz için yaptıklarımız bizimle birlikte ölür. Dünya ve başkaları için yaptıklarımız ise sonsuza dek yaşar."Albert Pike"
"Kendi kurallarını koymazsan, başkalarının kurallarıyla yaşarsın."M
www.mehmetbilgi.net.tr

Çevrimdışı RaMu

  • Profesyonel Üye
  • *****
  • İleti: 2581
  • 1+1=0
Ynt: CRC Hesaplama
« Yanıtla #12 : 01 Ekim 2016, 03:50:36 »
Sorularınıza hızlı cevap alın: http://www.picproje.org/index.php/topic,57135.0.html

Çevrimdışı TMrc

  • Yeni Üye
  • *
  • İleti: 3
Ynt: CRC Hesaplama
« Yanıtla #13 : 01 Ekim 2016, 15:46:42 »
@RaMu
Sağol hocam teşekkür ettim.