Forum: Compiler & IDEs Wer kann meinen Code (Bitpopelei) vereinfachen?


von Frank N. Stein (Gast)


Lesenswert?

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.
1
uint32_t crc32(uint32_t x) {
2
  static const uint32_t CRC32MASK = 0x04C11DB7;
3
  uint32_t c = 0;
4
  for (uint8_t i = 0; i < 32; i++) {
5
    if ((c >> 31) ^ (x & 1)) c = (c << 1) ^ CRC32MASK;
6
    else c <<= 1;
7
    x >>= 1;
8
  }
9
  return c;
10
}

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

von Frank N. Stein (Gast)


Lesenswert?

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

von fpga (Gast)


Lesenswert?

Jede wette der Compiler kann das besser?

von Matthias (Gast)


Lesenswert?

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 :-(

von Frank N. Stein (Gast)


Lesenswert?

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

von holger (Gast)


Lesenswert?

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

von A. S. (Gast)


Lesenswert?

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.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Versuch mal die Rotation vor der Operation zu machen, nicht danach.
1
static inline uint32_t
2
rol32 (uint32_t x)
3
{
4
    return (x << 1) | (x >> 31);
5
}
6
7
uint32_t crc32 (uint32_t x)
8
{
9
    const uint32_t CRC32MASK = 0x04C11DB7;
10
    uint32_t c = 0;
11
    for (uint8_t i = 0; i < 32; i++)
12
    {
13
        c = rol32 (c);
14
        if (1 & (uint8_t) (c ^ x))
15
            c ^= CRC32MASK;
16
        x >>= 1;
17
    }
18
    return c;
19
}

Rotate wird vom Compiler erkannt.
1
crc32:
2
  movw r20,r22   ;  4  *movsi/1  [length = 2]
3
  movw r22,r24
4
  ldi r18,lo8(32)   ;  6  movqi_insn/2  [length = 1]
5
  ldi r24,0   ;  7  *movsi/2  [length = 3]
6
  ldi r25,0
7
  movw r26,r24
8
.L3:
9
  lsl r24   ;  11  *rotlsi2.1  [length = 5]
10
  rol r25
11
  rol r26
12
  rol r27
13
  adc r24,__zero_reg__
14
  mov r19,r24   ;  44  movqi_insn/1  [length = 1]
15
  eor r19,r20   ;  12  xorqi3  [length = 1]
16
  sbrs r19,0   ;  15  *sbrx_branchqi  [length = 2]
17
  rjmp .L2
18
  ldi r19,183   ;  17  xorsi3/3  [length = 8]
19
  eor r24,r19
20
  ldi r19,29
21
  eor r25,r19
22
  ldi r19,193
23
  eor r26,r19
24
  ldi r19,4
25
  eor r27,r19
26
.L2:
27
  lsr r23   ;  50  *lshrsi3_const/2  [length = 4]
28
  ror r22
29
  ror r21
30
  ror r20
31
  subi r18,lo8(-(-1))   ;  21  addqi3/2  [length = 1]
32
  brne .L3   ;  24  branch  [length = 1]
33
  movw r22,r24   ;  29  *movsi/1  [length = 2]
34
  movw r24,r26
35
  ret   ;  47  return  [length = 1]

: Bearbeitet durch User
von Frank N. Stein (Gast)


Lesenswert?

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

von Max D. (max_d)


Lesenswert?

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

von Adib (Gast)


Lesenswert?

Hallo,

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

Hth, Adib.

von Martin O. (ossi-2)


Lesenswert?

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

: Bearbeitet durch User
von Oliver S. (oliverso)


Lesenswert?

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

von Kolja (Gast)


Lesenswert?

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

Und wie ist das bei "Frau"?

von Oliver S. (oliverso)


Lesenswert?

Frau weiß das sowieso...

Oliver

Beitrag #4993115 wurde vom Autor gelöscht.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.