Yet another CRC32 Code

[Detlef _. (detlef_a)]

Ich habe unten funktionierenden C-Code angehängt, der den CRC32 mit dem 
Polynom 0x04c11db7 berechnet. Es kommt dasselbe raus wie bei der CRC32 
Berechnung auf dieser site:

http://www.lammertbies.nl/comm/info/crc-calculation.html

Diese Implementierung entspricht der Vorgabe in angehängtem PDF (hab ich 
auf meiner Platte gefunden, keine Ahnung wo das herkommt). Der Testcode 
macht den CRC32 von 0x20000770 , das war mal im Forum Thema. Dessen 
CRC32 lautet 0x61cd6826, wenn man den bytegedreht reinschickt, kommt 0x0 
raus, wie das auch sein muß. Getestet ist unter gcc/x86, denke aber, das 
läuft auch aufn AVR.

> Dieses Ding hat mich an den Rand des Wahnsinns getrieben, weder hier noch 
irgendwo anders habe ich funktionierendes Zeug gefunden, das Wikipedia Beispiel 
ging auch nicht.

Aber jetzt ist alles gut!
Cheers
Detlef

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/*******************************************************************/
uint32_t crc32(uint32_t crc, uint8_t byte)
/*******************************************************************/
{
int8_t i;
  crc = crc ^ byte;
  for(i=7; i>=0; i--)
    crc=(crc>>1)^(0xedb88320ul & (-(crc&1)));
  return(crc);
}


/*******************************************************************/
int main(int  argc , char ** argv)
/*******************************************************************/
{
uint32_t reg = 0xffffffff;

//reg=crc32(reg,(uint8_t) '1');

reg=crc32(reg,(uint8_t)0x20);
reg=crc32(reg,(uint8_t)0x00);
reg=crc32(reg,(uint8_t)0x07);
reg=crc32(reg,(uint8_t)0x70);
/*
reg=crc32(reg,(uint8_t)0x26);
reg=crc32(reg,(uint8_t)0x68);
reg=crc32(reg,(uint8_t)0xcd);
reg=crc32(reg,(uint8_t)0x61);
*/
printf("%08x  %08x  \n",reg,reg^0xffffffff);

return;

}

[Hanno (Gast)]

Ich habe den Code von Detlef selbst auf dem AVR verwendet und mir dann 
die Freiheit genommen, ein bisschen mit dem AVR-GCC Inline-Assembler zu 
optimieren.
Vor allem aus dem "(0xedb88320ul & (-(crc&1)))" erzeugt der GCC 
unheimlich viel Code, der eben Speicher und Zyklen frisst.

Vielleicht sollte man auch erwähnen, dass der o.g. Algorithmus bereits 
die optimierte Variante von CRC ist, die nach rechts shiftet anstatt 
nach links. Das bewirkt aber, dass im CRC-Polynom die Bitfolge komplett 
umgekehrt werden muss. Das Standard-Polynom "0x04C11DB7" steht deshalb 
als "0xEDB88320" im Code. Jedes andere Polynom funktioniert natürlich 
auch, man muss es halt nur bitweise "rückwärtsschreiben".

Interessantes Lesewerk zum Thema "verschiedene CRC-Parameter" ist auch 
dieses:
http://regregex.bbcmicro.net/crc-catalogue.htm
Dem ist z.B. auch zu entnehmen, dass der "Standard"-CRC32 mit crc = 
0xffffffff initialisiert und abschließend nochmal bitweise invertiert 
wird (crc = crc ^ 0xffffffff).

/*******************************************************************/
uint32_t crc32b(uint32_t crc, const uint8_t byte)
/*******************************************************************/
{
  // crc = crc ^ byte;
  asm(
    "eor %A[crc],%[byte] \r\n"
    : [crc] "+r" (crc)
    : [byte] "r" (byte)
    :);
  
  
  for(uint8_t i=8; i!=0; i--) {
    
    uint8_t tmp;
    
    asm (
      // crc = crc >> 1
      "lsr %D[crc] \r\n"
      "ror %C[crc] \r\n"
      "ror %B[crc] \r\n"
      "ror %A[crc] \r\n"
    
      "brcc next_%= \r\n"
    
      // crc ^= 0xedb88320
      "ldi %[tmp], hhi8(%[polynom]) \r\n"
      "eor %D[crc], %[tmp] \r\n"
      "ldi %[tmp], hlo8(%[polynom]) \r\n"
      "eor %C[crc], %[tmp] \r\n"
      "ldi %[tmp], hi8(%[polynom]) \r\n"    
      "eor %B[crc], %[tmp] \r\n"
      "ldi %[tmp], lo8(%[polynom]) \r\n"
      "eor %A[crc], %[tmp] \r\n"
    
      "next_%=:"
    
      : [crc] "+r" (crc),
        [tmp] "=&a" (tmp)
      : [polynom] "i" (0xEDB88320)
      : );

  }  
  return crc;
}

(Für die Statistik: Der reine C-Code braucht bei mir pro Byte im 
Worst-Case 271 Zyklen, der mit Inline-Assembler 159 (jeweils 
einschließlich Initialisierung bzw. Finalisierung der CRC) -> fast 42% 
Zeit gespart (und dazu noch etliche Code-Words.))

Viele Grüße
 Hanno

[Johann L. (gjlayde)]

Hanno schrieb:

> Vor allem aus dem "(0xedb88320ul & (-(crc&1)))" erzeugt der GCC
> unheimlich viel Code, der eben Speicher und Zyklen frisst.
>
> Vielleicht sollte man auch erwähnen, dass der o.g. Algorithmus bereits
> die optimierte Variante von CRC ist, ...

Optimiert vielleicht für eine PC wo Sprünge teuer sind um die Schleife 
aufgerollt werden soll. Taschenspielertricks wie "& (-(crc&1)))", die 
auf einem Rechner mit ausladendem Instruktionssatz nur ein paar 
Instrultionen kosten, sind auf einem Hänfling wie AVR sehr ungeschickt.

Stattdessen schreibt man besser hin, was wiklich passiert:

uint32_t crc32 (uint32_t crc, uint8_t byte)
{
    int8_t i;
    crc = crc ^ byte;

    for (i = 7; i >= 0; i--)
    {
        uint8_t bit0 = crc & 1;
        crc >>= 1;
        if (bit0)
            crc ^= POLY;
    }

    return crc;
}

Damit schrumpf der Code schon mal um 21% (von 86 auf 68 Bytes).

crc32:
  push r16
  push r17
  mov r16,r20
  ldi r17,0
  ldi r18,0
  ldi r19,0
  eor r16,r22
  eor r17,r23
  eor r18,r24
  eor r19,r25
  ldi r24,lo8(7)
.L6:
  mov r25,r16
  andi r25,lo8(1)
  lsr r19
  ror r18
  ror r17
  ror r16
  tst r25
  breq .L5
  ldi r25,32
  eor r16,r25
  ldi r25,131
  eor r17,r25
  ldi r25,184
  eor r18,r25
  ldi r25,237
  eor r19,r25
.L5:
  subi r24,1
  brcc .L6
  movw r22,r16
  movw r24,r18
  pop r17
  pop r16
  ret

Klar, mit (inline) Assembler geht's immer besser...

>       : [crc] "+r" (crc),
>         [tmp] "=&a" (tmp)
>       : [polynom] "i" (0xEDB88320)
>       : );

Für tmp genügt Constraint "=d" anstatt "=&a":

       : [crc] "+r" (crc),
         [tmp] "=d" (tmp)
       : [polynom] "n" (0xEDB88320));

"next_%=" als Label ist eher unüblich; eine Funktion könnte genauso 
heissen. Besser einfach ein Wegwerf-Label wie "1f".

[Detlef _. (detlef_a)]

>>>was wiklich passiert:
:)) beides passiert wirklich

>>>Taschenspielertricks wie "& (-(crc&1)))"

Das ist kein Taschenspielertrick, sondern diese Implementierung läßt Dir 
die instruction pipe heil (falls vorhanden), wie Du ja auch richtig 
sagst. Das 'if' ist auf fetten Proz. und auch DSPs fast immer sehr 
ungeschickt. Außerdem sieht der Code sch* aus. Aber für den AVR gibts 
besseres, natürlich.

Danke für das Interesse, die links und die Code Mods.
Gute Nacht
Detlef.

[Hanno (Gast)]

Johann L. schrieb:

> Optimiert vielleicht für eine PC...

Nein, optimiert für jedes System - im Vergleich mit der "naiven" 
Implementierung mit links Shifts. Lies mal im o.g. PDF nach, Seiten 
9+10.
Der eigentliche Punkt ist aber, dass dadurch das Polynom halt 
"rückwärts" sein muss und deshalb nicht unbedingt ersichtlich ist, woher 
es kommt oder welchen Wert es hat.

> "next_%=" als Label ist eher unüblich; eine Funktion könnte genauso heissen.

Das stimmt beides nicht. Nachlesen: 
http://www.rn-wissen.de/index.php/Inline-Assembler_in_avr-gcc#Labels_und_Schleifen 
!

> Besser einfach ein Wegwerf-Label wie "1f".

... und das ist der größte Unsinn, den ich in letzter Zeit gesehen habe. 
Wenn man seinen Code möglichst undurchdringlich und unwartbar machen 
möchte, dann ist das genau der Weg dahin.

> Für tmp genügt Constraint "=d" anstatt "=&a"

... was wiederum überhaupt keinen Unterschied macht, weil der AVR-GCC 
die anderen oberen Register eh für andere Zwecke verwendet.

> Klar, mit (inline) Assembler geht's immer besser...

Meistens ja :)

Ansonsten schön, dass du dich so konstruktiv mit dem Thema 
auseinandersetzt ;-)

Viele Grüße
 Hanno

[Hanno (Gast)]

>> Für tmp genügt Constraint "=d" anstatt "=&a"
>
>... was wiederum überhaupt keinen Unterschied macht, weil der AVR-GCC die anderen 
oberen Register eh für andere Zwecke verwendet.

Achja, macht doch einen Unterschied: "=&" kennzeichnet einen 
Nur-Output-Parameter, so dass der Compiler nicht erst einen Wert in das 
Register kopiert, der sowieso nicht benutzt würde, was bei "=" wiederum 
2 unnütze Instruktionen mehr produziert.

[Johann L. (gjlayde)]

Hanno schrieb:

>> "next_%=" als Label ist eher unüblich; eine Funktion könnte genauso heissen.
>
> Das stimmt beides nicht. Nachlesen:
> 
http://www.rn-wissen.de/index.php/Inline-Assembler_in_avr-gcc#Labels_und_Schleifen

Nimm einfach folgendes:

void next_21 (void){}

void foo (void)
{
    __asm ("rjmp next_%=\nnext_%=:":);
}

Was bei mir zu folgendem Fehler führt:
>> lab.s: Assembler messages:
>> lab.s:38: Error: symbol `next_21' is already defined

Und wenn das bei dir keinen Fehler gibt, dann schau den Assembler an und 
nenne next_21 entsprechend um. Genau deshalb sollte man für Label auch 
Label-Bezeichner verwenden. Wegwerf-Label, und wenn die dir nicht zu 
pass sind, zB .mein.tolles.spezial.label.A.%=

Also nochmals die Doku lesen!

%= erzeugt eine für die Compilation-Unit und das asm (nach Inlining on 
Klonung) eindeutige Zahl, aber dies stellt nicht sicher, daß das daraus 
erzeugte Label eindeutig ist. Dazu muss man einen Label bauen, der weder 
heissen kann wie vom Compiler erzeugte Label noch wie Symbole.

Man mag einwenden, eine Funktion wird sowieso nie next_1234 heissen, 
aber warum Annahmen machen, wenn sie nicht nötig sind?

Inline-Assembler ist eine der häufigsten Fehlerquellen. Es wird ein asm 
geschrieben, geschaut wie es übersetzt, und wenn das richtig ist wird 
oft fälschlicherweise daraus geschlossen, daß auch das asm korrekt sei.

>> Besser einfach ein Wegwerf-Label wie "1f".
>
> ... und das ist der größte Unsinn, den ich in letzter Zeit gesehen habe.

Es ist kein Unsinn, es ist ein Vorschlag und eine Möglichkeit, die die 
Werzeugkiste bietet.

Wenn du diese nicht nutzen willst — warum auch immer — bitte.

>> Für tmp genügt Constraint "=d" anstatt "=&a"
>
> ... was wiederum überhaupt keinen Unterschied macht, weil der AVR-GCC
> die anderen oberen Register eh für andere Zwecke verwendet.

Vielleicht in obigem Kontext — der sich aber ganz fix ändern kann:
• andere Compiler-Version
• andere Compiler-Schalter
• anderer Kontext, zB indem die Funktion geinlinet oder geklont wird

[Hanno (Gast)]

Ok, ich diskutiere jetzt mal nicht mehr weiter. Das mit dem Label ist 
mir letztlich egal, Hauptsache ist, es ist gut verständlich, was das 
Label (für den Sprung) bedeutet.

Und bzgl. der Register-Constraints einigen wir uns einfach darauf, dass 
"=&d" wohl das Beste ist, was man an dieser Stelle rausholen kann :)

Eine Sache ist mir noch eingefallen:

"crc = crc ^ byte" wird vom GCC als 32-Bit-Berechnung übersetzt, obwohl 
das nicht nötig ist bei XOR oder OR. Darauf sollte man auch achten, wenn 
es um Optmierung von C-Code geht.

[Johann L. (gjlayde)]

Hanno schrieb:

> Eine Sache ist mir noch eingefallen:
>
> "crc = crc ^ byte" wird vom GCC als 32-Bit-Berechnung übersetzt, obwohl
> das nicht nötig ist bei XOR oder OR. Darauf sollte man auch achten, wenn
> es um Optmierung von C-Code geht.

Was wiederum nicht in Stein gemeisselt ist. Man kann entweder mit der 
Gießkanne Inline-Assembler Hacks verteilen, oder das Übel an der Wurzel 
packen. In letzterem Fall geht's hier weiter:

http://gcc.gnu.org/contribute.html

[Johann L. (gjlayde)]

Johann L. schrieb:
> Hanno schrieb:
>
>> Eine Sache ist mir noch eingefallen:
>>
>> "crc = crc ^ byte" wird vom GCC als 32-Bit-Berechnung übersetzt, obwohl
>> das nicht nötig ist bei XOR oder OR. Darauf sollte man auch achten, wenn
>> es um Optmierung von C-Code geht.
>
> Was wiederum nicht in Stein gemeisselt ist. Man kann entweder mit der
> Gießkanne Inline-Assembler Hacks verteilen, oder das Übel an der Wurzel
> packen.

Inzwischen verfügt GCC über die entsprechende Optimierung, die übrigens 
Änderungen an ganzen 4 Codezeilen erforderte.

Den Code von 
Beitrag "Re: Yet another CRC32 Code" 
übersetzt avr-gcc damit zu:

crc32:
  eor r22,r20   ;  crc, byte
  ldi r18,lo8(8)   ;
.L3:
  mov r19,r22   ;  bit0,
  andi r19,lo8(1)   ;  bit0,
  lsr r25   ;  crc
  ror r24   ;  crc
  ror r23   ;  crc
  ror r22   ;  crc
  tst r19   ;  bit0
  breq .L2
  ldi r19,32
  eor r22,r19   ;  crc,
  ldi r19,131
  eor r23,r19   ;  crc,
  ldi r19,184
  eor r24,r19   ;  crc,
  ldi r19,237
  eor r25,r19   ;  crc,
.L2:
  subi r18,lo8(-(-1))
  brne .L3
  ret

[Hanno (Gast)]

> Inzwischen verfügt GCC ...

Hast du noch eine Versionsnummer dazu?
Ist diese Version schon im aktuellen AVRStudio enthalten?

[Johann L. (gjlayde)]

Die Optimierung ging upstream als SVN 184509 von 2012-02-23
GCC-Version ist 4.7.0 (experimental)

Über den Atmel-Fork kann ich nichts sage; da musst du Atmel fragen.

[Detlef _. (detlef_a)]

Hallo,

hier zusätzlich der CRC16 Code.

Kommt immer noch dasgleiche raus wie bei:

http://www.lammertbies.nl/comm/info/crc-calculation.html

Man muss das Polynom spiegeln, dann gehts!

math rulez!
Cheers
Detlef

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdint.h>

/*******************************************************************/
uint32_t crc32(uint32_t crc, uint8_t byte)
/*******************************************************************/
{
int8_t i;
  crc = crc ^ byte;
  for(i=7; i>=0; i--)
    crc=(crc>>1)^(0xedb88320ul & (-(crc&1)));
  return(crc);
}

/*******************************************************************/
uint32_t crc16(uint16_t crc, uint8_t byte)
/*******************************************************************/
{
int8_t i;
  crc = crc ^ byte;
  for(i=7; i>=0; i--)
    crc=(crc>>1)^(0xa001u & (-(crc&1)));
  return(crc);
}


/*******************************************************************/
int main(int  argc , char ** argv)
/*******************************************************************/
{
uint32_t reg = 0xffffffff;
uint32_t reg16 = 0x0000;

int16_t y[2];
int16_t n,k,m;
int16_t yalt[2];


reg16=crc16(reg16,'0');
reg16=crc16(reg16,'1');
reg16=crc16(reg16,'2');
reg16=crc16(reg16,'3');


printf("%04x  %04x  \n",reg16,reg16^0xffff);

return;
}

[Johann L. (gjlayde)]

Detlef _. schrieb:
>     crc=(crc>>1)^(0xa001u & (-(crc&1)));

Für AVR gilt das gleiche wie im 23-Bit Fall:  Sprung abhängig von crc 
Bit 0 ist da besser als solche Arithmetik-Tricks.

Mit Trick hätte man in der Schleife bestenfalls (z.B. per Assebmler):
 

;; In der Schleife
lsr  r25       $ ror  r24
sbc  r23, r23  $ sbc  r22, r22
andi r23, 0xa0 $ andi r22, 0x01
eor  r25, r23  $ eor  r24, r22

 
Mit Sprung hingegen:
 

;; Vor der Schleife
ldi r23, 0xa0 $ ldi r22, 0x01

;; in der Schleife
lsr  r25       $ ror  r24
brcc 1f
eor  r25, r23  $ eor  r24, r22

 
Mit Arithmetik hat mal also 1 Instruktion mehr und 8 Ticks anstatt zu 
erwartender 4.5 Ticks in der Schleife (wobei in beiden Fällen 
Loop-Overhead hinzukommt).  Und wird das "-" wirklich als Negation 
umgesetzt, wird der Unterschied noch größer.

[Detlef _. (detlef_a)]

Johann, auf Dich ist wirklich Verlass, auch nach Jahren ;)))

schönen Gruß
Cheers
Detlef

[Detlef _. (detlef_a)]

Hallo,

hier zusätzlich der CRC-Code für beliebige Polynome, CRC7, CRC16, CRC32 
sind explizit gecoded. Die geschützten Eingangsdaten sind jetzt eine 
beliebige Anzahl von Bits, nicht mehr Bytes. Der C-Code ist das Muster 
für eine FPGA Implementation. Der Test in der main zeigt wie man 9Bit 
mit einem CRC7 schützen kann, was die sichere Übertragung der 9 Bits bei 
16Bit Datenwortbreite über einen sehr stark gestörten Kanal ermöglicht, 
hoffentlich :).

math rulez!
Cheers
Detlef

[Purzel H. (hacky)]

So ganz nebenbei, wenn Geschwindigkeit sehr wichtig ist, kann man Code 
Groesse gegen Geschwindigkeit tauschen und mit Tabellen arbeiten.