crc8 und crc16: ohne Loop, ohne Table, sehr schnell

[eProfi (Gast)]

Manchmal frage ich mich, warum so mancher einen halben Roman dafür 
schreibt. Ich glaube, es geht nicht schneller oder kürzer.
Hier verschieden Varinten z.B. für 1-wire:

Es bleibt jedem frei, nach Geschmack Leerzeichen und Zeilenumbrücke 
einzufügen oder die Variablen umzubenennen. Ich mag's gern kompakt.
Ich sehe den Code als getestete Blackbox an,
deshalb kann und soll er kurz sein.

uint8_t crc8a(uint8_t c,uint8_t d){ //crc, data
  d^=c;c=0;
  if(d&  1)c^=0x5e;  if(d&  2)c^=0xbc;
  if(d&  4)c^=0x61;  if(d&  8)c^=0xc2;
  if(d& 16)c^=0x9d;  if(d& 32)c^=0x23;
  if(d& 64)c^=0x46;  if(d&128)c^=0x8c;
  return c;
}

uint8_t crc8b(uint8_t c,uint8_t d){d^=c;c=0; //crc, data
  if(d&128)c=140;if(d&64)c^=70;if(d&1)c^=94;if(d&2)c^=188;
  if(d&16)c^=157;if(d&32)c^=35;if(d&4)c^=97;if(d&8)c^=194;
  return c;
}

uint8_t crc=0;  //Version mit nicht-lokaler crc-Variable (langsam + lang)
void crc8c(uint8_t d){d^=crc;crc=0; //data
  if(d&128)crc=140;if(d&64)crc^=70;if(d&1)crc^=94;if(d&2)crc^=188;
  if(d&16)crc^=157;if(d&32)crc^=35;if(d&4)crc^=97;if(d&8)crc^=194;
}

uint16_t crc16a(uint16_t c,uint8_t d){ //mit Loop
  uint8_t i=8;do{c=(c^d)&1?c/2^40961:c/2;d/=2;}while(--i);
  return c;
}

uint16_t crc16b(uint16_t c,uint8_t d){
  c=(c^d)&1?c/2^40961:c/2;d/=2;  //loop unrolling
  c=(c^d)&1?c/2^40961:c/2;d/=2;
  c=(c^d)&1?c/2^40961:c/2;d/=2;
  c=(c^d)&1?c/2^40961:c/2;d/=2;
  c=(c^d)&1?c/2^40961:c/2;d/=2;
  c=(c^d)&1?c/2^40961:c/2;d/=2;
  c=(c^d)&1?c/2^40961:c/2;d/=2;
  c=(c^d)&1?c/2^40961:c/2;d/=2;
  return c;
}

uint16_t crc16c(uint16_t c,uint8_t d){
  c=(c^ d    )&1?c/2^40961:c/2;  //loop unrolling
  c=(c^(d/=2))&1?c/2^40961:c/2;
  c=(c^(d/=2))&1?c/2^40961:c/2;
  c=(c^(d/=2))&1?c/2^40961:c/2;
  c=(c^(d/=2))&1?c/2^40961:c/2;
  c=(c^(d/=2))&1?c/2^40961:c/2;
  c=(c^(d/=2))&1?c/2^40961:c/2;
  c=(c^(d/=2))&1?c/2^40961:c/2;
  return c;
}

uint16_t crc16d(uint16_t c,uint8_t d){uint8_t r=c>>8;d^=c;c=0;
  if(d&128)c=40961;if(d&32)c^=55297;if(d&8)c^=50689;if(d&2)c^=49537;
  if(d&64)c^=61441;if(d&16)c^=52225;if(d&4)c^=49921;if(d&1)c^=49345;
  return r^c;
}

uint16_t crc16e(uint16_t c,uint8_t d){d^=c;c>>=8;
  if(d&128)c^=40961;if(d&32)c^=55297;if(d&8)c^=50689;if(d&2)c^=49537;
  if(d& 64)c^=61441;if(d&16)c^=52225;if(d&4)c^=49921;if(d&1)c^=49345;
  return c;
}

uint16_t P[8]={40961,61441,55297,52225,50689,49921,49537,49345};
uint16_t crc16f(uint16_t c,uint8_t d){uint8_t m=128;uint16_t*p=P;
  d^=c;c>>=8;do{if(d&m)c^=*p;p++;}while(m>>=1);return c;
}

//Ab hier wird ein ganzes Array bearbeitet (noch ungetestet):

uint16_t crc16g(uint8_t*D,uint8_t l){uint16_t c=0;do{
    uint8_t d=*D++^c;c>>=8;
    if(d&128)c^=40961;if(d&32)c^=55297;if(d&8)c^=50689;if(d&2)c^=49537;
    if(d& 64)c^=61441;if(d&16)c^=52225;if(d&4)c^=49921;if(d&1)c^=49345;
    do{if(d&m)c^=*p;p++;}while(m>>=1);}while(--l);return c;
}

uint16_t P[8]={40961,61441,55297,52225,50689,49921,49537,49345};
uint16_t crc16h(uint8_t*D,uint8_t l){uint16_t c=0;do{     //mit Loop
    uint8_t m=128;uint16_t*p=P;uint8_t d=*D++^c;c>>=8;
    do{if(d&m)c^=*p;p++;}while(m>>=1);}while(--l);return c;
}

Vorschläge, Verbesserungen, andere Polynome ....    gern gesehen!

[Karlheinz (Gast)]

Hallo,

wo liegt der besondere Vorteil deiner Vorgehensweise ???

Du brauchst fast 8 (16) -mal soviel Code-Speicher wie die 
Schleifen-Methode und bist nur unerheblch schneller indem du alles 8 
(16) -mal hinschreibst.

Du brauchst 8-mal solange wie die Tabellen-Methode und bist deshalb 
absolut nicht der Schnellste.

Deine Methode ist nur eine Möglichkeit!!!

[Peter D. (peda)]

Danke für die super Formatierung. Wieder was gelernt, wie man 
unleserlich programmiert.

Peter

[eProfi (Gast)]

@Karlheinz:
Wahrscheinlich liegt es an meiner high-Density-Affinität, dass der Code 
so unverständlich ist.
Es handelt sich nicht um eine Methode, sondern um 11 (3 für crc8 und 
8 für crc16), d.h. jeder der Absätze ist der komplette Code.

> Du brauchst fast 8 (16) -mal soviel Code-Speicher wie die
> Schleifen-Methode und bist nur unerheblch schneller indem
> du alles 8 (16) -mal hinschreibst.
Sicher, es macht nicht viel aus und es kommt meist nicht darauf an.
LoopUnrolling kann aber auch positive Nebeneffekte haben, weil die 
Zählvariable wegfällt und der Compiler dadurch besser optimieren kann.

Außerdem: schau mal andere Schleifen-Konstukte an, die sind teilweise 
deutlich umständlicher als die hier vorgestellten.

> Du brauchst 8-mal solange wie die Tabellen-Methode und
> bist deshalb absolut nicht der Schnellste.
Naja, das gilt es erstmal zu beweisen. Ohne jetzt das Asm-Listing 
angeschaut zu haben, will ich mal  eine Lösung sehen, die um die 20-40 
Cycles benötigt (crc8a=crc8b und crc16e sind die schnellsten Varianten).


@Peter:
Von Dir hätte ich einen anderen Kommentar erwartet, etwas fachliches zum 
Thema.


Aber ich weiß, dass manche nicht die Herausforderung (Spaß, Sport), 
etwas möglichst kompakt zu formulieren, erkennen. Solche Kritik kenne 
ich schon:
Beitrag "Re: DS18S20 - extended resolution bei Temperaturen um 0°C"
>>in 10 Zeilen (ohne die Kommentare). Ich kann gar nicht verstehen, wie
>>man hierfür kilometerlangen Code schreiben kann.

> Weil es übersichtlicher ist und nicht so ein scheisse
> formatierter Schrott wie von dir.

Beim Entwickeln und Debuggen schreibe ich natürlich einen Befehl pro 
Zeile, danach schreibe ich oft das zusammen in eine Zeile, was 
zusammengehört.
Und ob ich c für crc, d für data, m für mask oder p für polynom schreibe 
- im Zusammenhang mit einer CRC sollte klar sein, was gemeint ist.

Ist reine Geschmacks-, Übungs- und Gewohnheitssache. Ich finde, man 
gewinnt den besseren Überblick, wenn möglichst viel Code auf den 
Bildschirm passt.

Auch weiß ich, dass ich gerne die Klammern unüblich hinschreibe, nach 
folgender einfachen Regel: die folgende Zeile ist um 2n Leerzeichen 
eingerückt, mit n=Differenz zwischen Anzahl der schließenden und 
öffnenden Klammern.
{ heißt: der nachfolgende Code ist eine Hierarchiestufe niedriger  und 
die nächste Zeile wird daher 2 Leerzeichen weiter eingerückt,
} bedeutet: der folgende Code ist eine Stufe höher  und die nächste 
Zeile wird 2 Leerzeichen weniger eingerückt.


Zum Code selbst: die Reihenfolge der Bitabfragen spielt keine Rolle, 
deshalb habe ich (in crc8b) die Folge so hingeschrieben, dass es am 
besten passt ("Ästhetik").

Meine erste crc16 hat übrigens so ausgesehen:
uint16_t crc16x(uint16_t c,uint16_t d){ // d mußte noch 16bit sein
  d^=c;c=0;
  if(d&    1)c^=49345;
  if(d&    2)c^=49537;
  if(d&    4)c^=49921;
  if(d&    8)c^=50689;
  if(d&   16)c^=52225;
  if(d&   32)c^=55297;
  if(d&   64)c^=61441;
  if(d&  128)c^=40961;
  if(d&  256)c^=    1;
  if(d&  512)c^=    2;
  if(d& 1024)c^=    4;
  if(d& 2048)c^=    8;
  if(d& 4096)c^=   16;
  if(d& 8192)c^=   32;
  if(d&16384)c^=   64;
  if(d&32768)c^=  128;
  return c;}

Die Konstanten erhielt ich, indem ich eine bekannte CRC16 mit
d=0 und c=1, 2, 4, 8, ... 32768 speiste.

Schon beim Testen fiel mir auf, dass die Werte  256 und größer  einfach 
durch einen >>8 zu errechnen sind:

uint16_t crc16y(uint16_t c,uint16_t d){
  d^=c;c=0;
  if(d&  1)c^=49345;
  if(d&  2)c^=49537;
  if(d&  4)c^=49921;
  if(d&  8)c^=50689;
  if(d& 16)c^=52225;
  if(d& 32)c^=55297;
  if(d& 64)c^=61441;
  if(d&128)c^=40961;
  return c^(d>>8);}

Da beim xor die Reihenfolge keine Rolle spielt, kann man den letzten xor 
nach ganz vorne verschieben. Da das upperByte von d gleich dem von c 
ist, shifte ich gleich c um 8 nach rechts, und für d reichen 8 Bits:

uint16_t crc16z(uint16_t c,uint8_t d){
  d^=c;c=>>8;
  if(d&  1)c^=49345;
  if(d&  2)c^=49537;
  if(d&  4)c^=49921;
  if(d&  8)c^=50689;
  if(d& 16)c^=52225;
  if(d& 32)c^=55297;
  if(d& 64)c^=61441;
  if(d&128)c^=40961;
  return c;}

[Karlheinz (Gast)]

Hallo,

eProfi schrieb:
> Wahrscheinlich liegt es an meiner high-Density-Affinität, dass ...

Nein, nicht an deiner "high-Density-Affinität"!
Ich will dich ja nicht verletzen, aber es liegt daran dass du momentan 
so stolz auf diese 8 Zeilen bist, dass du nicht sehen willst dass es 
jedesmal die gleiche Methode/das gleiche Prinzip ist das schon viele vor 
dir so machten.

Das Ganze 8 mal hinschreiben, fertig -- es ist nur eine Möglichkeit !!!

Momentan merkst du dir quasi 8 Werte im Code

>   if(d&  2)c^=49537;
>   if(d&  4)c^=49921;
>   if(d&  8)c^=50689;
>   if(d& 16)c^=52225;
>   if(d& 32)c^=55297;
>   if(d& 64)c^=61441;
>   if(d&128)c^=40961;

Du könntest Dir aber auch eine Tabelle (Tab[]) mit allen 256 möglichen 
Kombinationen vorbereiten dann bist du in einer Zeile fertig

>  c ^= Tab[ d & 0xff ];

was dann ???

[Läubi .. (laeubi)]

eProfi schrieb:
> Vorschläge, Verbesserungen, andere Polynome ....    gern gesehen!

Bitte benutzt doch die COde Tags, ich habe das mal nachgezogen.

[Peter D. (peda)]

eProfi schrieb:
> @Peter:
> Von Dir hätte ich einen anderen Kommentar erwartet, etwas fachliches zum
> Thema.

Da Du nichtmal die Postingregeln liest, war Dein Code für mich völlig 
unlesbar und somit konnte ich auch dazu nichts sagen.

Je länger man programmiert, umso mehr mag man Lesbarkeit und dazu 
gehören eben Leerzeichen und auch Zeilenumbrüche je Ausdruck.

Falls Dir das [ c][/c] zu aufwendig ist, häng das *.c doch einfach an.


Peter

[Frank M. (ukw) (Moderator)]

eProfi schrieb:
> Ich finde, man
> gewinnt den besseren Überblick, wenn möglichst viel Code auf den
> Bildschirm passt.

Kauf Dir doch einfach einen größeren ;-)

Nein, im Ernst: Ich brauche doppelt so lang wie normalerweise, Deinen 
"kompakten" Code mit den Augen wieder auseinanderzuklamüsern.

DasistgenausoschwierigwiediestenSatzzuverstehen.

[Simon K. (simon)]

Frank M. schrieb:
> DasistgenausoschwierigwiediestenSatzzuverstehen.
                               ^

Undfehlerfallennichtsoschnellauf. :-)

[Johann L. (gjlayde)]

Peter Dannegger schrieb:
> Danke für die super Formatierung. Wieder was gelernt, wie man
> unleserlich programmiert.

Das Progamm wurde wahrscheinlich vor Erfingung der Leertaste 
geschrieben.

Ausserdem belegen die ganzen Leerzeichen nur unnötig Platz auf dem 
Controller!

[Frank M. (ukw) (Moderator)]

Johann L. schrieb:
> Ausserdem belegen die ganzen Leerzeichen nur unnötig Platz auf dem
> Controller!

Im Flash oder im RAM? Kann man PROGMEM auf die Leerzeichen anwenden? 
Wenn ja, wie? ;-)