Wer kann meinen Code (Bitpopelei) vereinfachen?

[Frank N. Stein (Gast)]

Folgender Code (CRC32) basiert auf dem entsprechenden Wikipedia-Artikel 
und nun möchte ihn für den AVR möglichst platzsparend vereinfachen. Es 
soll einfach eine CRC32 über eine 32-Bit-Zahl berechnet werden.

uint32_t crc32(uint32_t x) {
  static const uint32_t CRC32MASK = 0x04C11DB7;
  uint32_t c = 0;
  for (uint8_t i = 0; i < 32; i++) {
    if ((c >> 31) ^ (x & 1)) c = (c << 1) ^ CRC32MASK;
    else c <<= 1;
    x >>= 1;
  }
  return c;
}

Leider habe ich so meine Probleme, zu erkennen, welche Umformung es dem 
Compiler einfacher macht... Erfahrungsgemäß ist das Ganze nämlich noch 
nicht optimal. ;)

[Frank N. Stein (Gast)]

Ah, Shit, im Vergleich ist sogar noch ein Fehler. :/

[fpga (Gast)]

Jede wette der Compiler kann das besser?

[Matthias (Gast)]

Zum Thema Bitschubsen:

https://graphics.stanford.edu/~seander/bithacks.html

Da gibt es einige interessante Tricks ;-)


Wenn Du Dir das Ganze Konstruk einzeln und in Blöcken ansiehtst, und
Erfahrung mit Assemblerprogrammierung hast, dann kannst Du
Dir iterativ die "Optimierung" selber erarbeiten. Dauert hat ne Weile.

Da für meinen Anwendungsfall die Rechenzeit kritisch war, ist meine 
eigene Implementierung auf Basis einer Look-Up-Table impelemtniert. Das 
braucht natürlich Flash-Speicher ohne Ende - Besonders wenn das in eine 
"Boot-Section" rein muss :-(

[Frank N. Stein (Gast)]

Erfahrungsgemäß nicht bei allzu verschachtelten Ausdrücken. c << 1 ist 
z.B. doppelt. Das sollte man sicher besser per Hand vereinfachen.

[holger (Gast)]

>Erfahrungsgemäß nicht bei allzu verschachtelten Ausdrücken. c << 1 ist
>z.B. doppelt. Das sollte man sicher besser per Hand vereinfachen.

Falsch gedacht. Das weiß der Compiler auch. Und der optimiert
besser als du das von Hand könntest.

[A. S. (Gast)]

Frank N. Stein schrieb:
> en AVR möglichst platzsparend vereinfachen.

measure twice, cut once: Wieviel Bytes verbraucht denn der Code?
20?
Und Du willst den Code jetzt kleiner machen oder leserlicher?

Mir ist nicht ganz klar, ob ein C-Compiler aus CRC32MASK ein Literal 
machen darf. Also ggf. den als Define oder direkt hinschreiben und 
probieren ob es weniger wird.

[Johann L. (gjlayde)]

Versuch mal die Rotation vor der Operation zu machen, nicht danach.

static inline uint32_t
rol32 (uint32_t x)
{
    return (x << 1) | (x >> 31);
}

uint32_t crc32 (uint32_t x)
{
    const uint32_t CRC32MASK = 0x04C11DB7;
    uint32_t c = 0;
    for (uint8_t i = 0; i < 32; i++)
    {
        c = rol32 (c);
        if (1 & (uint8_t) (c ^ x))
            c ^= CRC32MASK;
        x >>= 1;
    }
    return c;
}

Rotate wird vom Compiler erkannt.

crc32:
  movw r20,r22   ;  4  *movsi/1  [length = 2]
  movw r22,r24
  ldi r18,lo8(32)   ;  6  movqi_insn/2  [length = 1]
  ldi r24,0   ;  7  *movsi/2  [length = 3]
  ldi r25,0
  movw r26,r24
.L3:
  lsl r24   ;  11  *rotlsi2.1  [length = 5]
  rol r25
  rol r26
  rol r27
  adc r24,__zero_reg__
  mov r19,r24   ;  44  movqi_insn/1  [length = 1]
  eor r19,r20   ;  12  xorqi3  [length = 1]
  sbrs r19,0   ;  15  *sbrx_branchqi  [length = 2]
  rjmp .L2
  ldi r19,183   ;  17  xorsi3/3  [length = 8]
  eor r24,r19
  ldi r19,29
  eor r25,r19
  ldi r19,193
  eor r26,r19
  ldi r19,4
  eor r27,r19
.L2:
  lsr r23   ;  50  *lshrsi3_const/2  [length = 4]
  ror r22
  ror r21
  ror r20
  subi r18,lo8(-(-1))   ;  21  addqi3/2  [length = 1]
  brne .L3   ;  24  branch  [length = 1]
  movw r22,r24   ;  29  *movsi/1  [length = 2]
  movw r24,r26
  ret   ;  47  return  [length = 1]

[Frank N. Stein (Gast)]

Danke für die Mühe, Johann. Ich glaube aber, mein Code ist ohnehin 
Bullshit, weil falsch aus der Wikipedia übernommen. Ich muss mir dazu in 
den nächsten Tagen nochmal Gedanken machen. Erstmal ist ja der Vergleich 
mit ^ Quatsch und zum Zweiten geht man ja eigentlich byteweise vor und 
haut nicht die ganzen 32bit gleich rein. :/

[Max D. (max_d)]

http://www.nongnu.org/avr-libc/user-manual/group__util__crc.html ist 
bekannt ?
Hat zwar AFAIK keine 32-Bit Routinen, aber als Ausgangspunkt wie man das 
für den AVR optimiert ist es sicher nicht schlecht (irgendwo gab es da 
auch assembler schnipsel).

[Adib (Gast)]

Hallo,

Eleganter wäre sicher eine vorberechnete Tabelle.
Im Code-size größer aber sicher mehrfach schneller.

Hth, Adib.

[Martin O. (ossi-2)]

c >> 31 lässt sich bestimmt eliminieren, da einfach nur das Bit in 
Position 31 gebraucht wird (für das XOR mit Bit in position 0). 
Eventuell sowas:
(oder so ähnlich)
bit=x & 1 ;
if (c & 0x80000000UL) { bit = bit ^ 1 ; }

[Oliver S. (oliverso)]

Wie bereits schon öfter mal geschrieben wurde, sind Compilerbauer nicht 
von gestern.

Solche Optimierungen macht er Compiler selber, da muß Mann nicht mehr 
von Hand basteln.

Oliver

[Kolja (Gast)]

Oliver S. schrieb:
> Solche Optimierungen macht er Compiler selber, da muß Mann nicht mehr
> von Hand basteln.

Und wie ist das bei "Frau"?

[Oliver S. (oliverso)]

Frau weiß das sowieso...

Oliver