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


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Frank N. Stein (Gast)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht lesenswert
Ah, Shit, im Vergleich ist sogar noch ein Fehler. :/

von fpga (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Jede wette der Compiler kann das besser?

von Matthias (Gast)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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. (achs)


Bewertung
0 lesenswert
nicht 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


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
1 lesenswert
nicht lesenswert
Frau weiß das sowieso...

Oliver

Beitrag #4993115 wurde vom Autor gelöscht.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.