Wer kann meinen Code (Bitpopelei) vereinfachen?

Frank N. Stein Gast #4990386
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. ;)
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Matthias Gast #4990417
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 :-(
Antwort Zitieren Bearbeiten Löschen Beitrag melden
holger Gast #4990463
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
A. S. Gast #4990530
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Johann L. Persönliche Seite #4990583
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]
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Frank N. Stein Gast #4990596
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. :/
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Beitrag #4993115 wurde von einem Moderator gelöscht.
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren