Forum: Mikrocontroller und Digitale Elektronik Parity mit AVR-ASM: Stimmts, gehts schneller?


von Justav (Gast)


Lesenswert?

Hallo µC-Gemeinde,

bei den AVR-Megas und Tinys bleibt die Parity-Ermittlung
dem Programmierer überlassen.

Aus einigen Fundstellen im Forum und Internet habe ich mir folgende
Lösung zusammengepfriemelt. Ich hoffe, es ist kein Irrtum drin
und möchte euch fragen, ob ihr schnellere Lösungen kennt.
1
parity:        ; IN  = Tmp0, zu testendes Byte 
2
  push  Tmp1  ; OUT = Tmp0 = 0/1 für gerade/ungerade Anzahl von EINSen in IN
3
4
  mov  Tmp1, Tmp0
5
  swap Tmp0
6
  eor  Tmp0, Tmp1  ; EINS/NULL in  Bit 7..4 wird gegen EINS/NULL in Bit 3..0 reduziert 
7
  lsr  Tmp0    ; Unterschiede bleiben erhalten, danach ist Bit 7..4 uninteressant
8
  lsr  Tmp0
9
  eor  Tmp0, Tmp1  ; EINS/NULL in  Bit 3..2 wird gegen EINS/NULL in Bit 1..0 reduziert
10
  lsr  Tmp0    ; Unterschiede bleiben erhalten, danach ist Bit 7..2 uninteressant
11
  eor  Tmp0, Tmp1  ; EINS/NULL in  Bit 1 wird gegen EINS/NULL in Bit 0 reduziert 
12
  andi Tmp0, 1  ; Unterschiede sind in Tmp0 - Bit 0 konzentriert
13
  
14
  pop  Tmp1
15
  ret        ; OUT = Tmp0 = 1/0 für ungerade/gerade Zahl von EINSen in IN
16
17
          ; µC-Takte = 13 + 7 für RCALL/RET = 20, also 2,5 µs @ 8 MHz

20 Takte sind ja eine Menge Zeit, wenn es in Hardware
sozusagen SOFORT zur Vefügung steht...

von Falk B. (falk)


Lesenswert?

@Justav (Gast)

>und möchte euch fragen, ob ihr schnellere Lösungen kennt.

Vielleicht mit einer riesigen Sprungtabelle?

>20 Takte sind ja eine Menge Zeit, wenn es in Hardware
>sozusagen SOFORT zur Vefügung steht...

Ist halt so.

von H.Joachim S. (crazyhorse)


Lesenswert?

Ob es schneller geht weiss ich nicht. Vielleicht ja, vielleicht nein.
Die eigentliche Frage ist aber: Hast du die Zeit für die 20 Takte oder 
nicht?
Falls ja (wovon meist auszugehen ist) - denk nicht weiter drüber nach.
Falls nein: wo wäre die akzeptable Grenze? Dann könnte man drüber 
nachdenken, ob sich was optimieren lässt. Fehlen nur wenige Takte, geht 
vielleicht was.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Ja, geht schneller:

1) Mach's inline, d.h. kein Funktionsaufruf

2) Du wirst eine ABI verwenden, und in dieser wird es (hoffentlich)
   call-clobbered Register geben --> PUSH und POP können bei sinniger
   Wahl des entsprechenden tmp-Registers entfallen.

3) Dies spart dann auch die MOVes in und aus dem Parameter-Register

Falls das zu paritisierende Byte bitweise aufgebaut wird (z.B. bei DCF), 
dann berechne dessen Parity nebenbei in der entsprechenden Schleife.

von Carl D. (jcw2)


Lesenswert?

> bei den AVR-Megas und Tinys bleibt die Parity-Ermittlung
> dem Programmierer überlassen

Oder der avr-libc <util/parity.h>, falls man den GCC benutzt.
Die macht das mit inline Assembler und fast wie dein Beispiel.

von c-hater (Gast)


Lesenswert?

Justav schrieb:

> 20 Takte sind ja eine Menge Zeit, wenn es in Hardware
> sozusagen SOFORT zur Vefügung steht...

Ja, aber 11 davon gehören garnicht zum Algorithmus, rcall+ret und 
push+pop. Zuerst sollte man also mal dafür sorgen, dass die entfallen 
können.

Das geht leichter, wenn man die Sache als Makro formuliert, dann ist es 
kein Problem, sie zu "inlinen", was den call-Rahmen entsorgt und 
außerdem kann man die zu verwendenden Register für jede Instanz getrennt 
angeben, so dass man meist das push+pop sparen kann (und obendrein ggf. 
die Parameterübergabe). Es bleiben dann nur die neun wirklich nötigen 
Takte.

von Horst M. (horst)


Lesenswert?

Wenn im Flash ein bißchen Platz übrig ist:
1
init:
2
 ldi ZH,HIGH(parity_tbl*2)
3
4
;Parität ermitteln
5
;IN:  r30, zu testendes Byte
6
;OUT: r30, Paritätswert
7
parity:
8
 lpm r30,Z    ;3 Taktzyklen
9
10
11
 .org (PC+0x100) & 0xff00
12
;Tabelle mit den Paritätswerten für 0...255
13
parity_tbl: .db 0,1,1,0...

Wenn im RAM auch noch 256 Bytes Platz finden, kannst Du die Tabelle 
dorthin kopieren und bei der Paritätsermittlung nochmal einen Taktzyklus 
sparen. Außerdem geht's dann auch mit den anderen Indexregistern.

: Bearbeitet durch User
von H.Joachim S. (crazyhorse)


Lesenswert?

Horst M. schrieb:
> kannst Du die Tabelle dorthin kopieren

Dann lieber am Programmstart selbst im RAM erzeugen, braucht weniger 
flash.

von S. Landolt (Gast)


Lesenswert?

> .org (PC+0x100) & 0xff00
Wie wär's mit (pc+0xff), zumindest für avrasm2.

von S. Landolt (Gast)


Lesenswert?

Das war missverständlich, also komplett:
.org ((pc+0xff) & 0xff00)

von Horst M. (horst)


Lesenswert?

Ganz richtig wäre (PC+0x7f) & 0xff80. Damit wird die Tabelle auf eine 
256-Byte-Grenze (bzw. 128-Word-Grenze) ausgerichtet.

von S. Landolt (Gast)


Lesenswert?

Prima. Wobei - richtig ist alles, aber Ihr letzter Vorschlag ist unter 
allen Umständen am platzsparendsten.

von Justav (Gast)


Lesenswert?

Danke für die Antworten!

Eine 256 BYTE Tabelle wäre beim Tiny wohl Overkill.
Wenn man für die Adressregister noch push/pop braucht,
ist der Geschwindigkeitsvorteil dazu noch gering.
- Ah, klar! Wenn das halbe RAM des gößten Tiny verbraten
ist, reichen bestimmt die übrigen Adressregister. ;-)

Aber der Tipp mit Makro und einem, oder ein paar für
Makros reservierte Register gefällt mir: 9 Takte!

Die erste Idee und etliche Fundstellen machten es mit
einer Schleife, also > 40 Takte.

von S. Landolt (Gast)


Lesenswert?

> oder ein paar für Makros reservierte Register
In diesem Fall bräuchte man für das Sichern von ZH,L aber auch kein 
push/pop, es reichte movw.

von S. Landolt (Gast)


Lesenswert?

> Stimmts, gehts schneller?

Letzteres wurde jetzt ja ausgiebig diskutiert, aber Ersteres? Kann es 
sein, dass das gar nicht stimmt?:
00 00
01 01
02 01
03 00
04 00
05 01
06 01
07 00
08 01
09 00
0A 00
0B 01
0C 01
0D 00
0E 00
0F 01
10 00

von Justav (Gast)


Lesenswert?

Wenn ich richtig rechne, ist das ein 7 Takte Makro, falls
eine 256-BYTE-aligned Tabelle vorliegt. < 1µs @ 8 MHz
- Aber leider nur für größere MEGA-AVRs geeignet.

Da sind wir schon bei gut ein Drittel von anfangs 20 Takten!

von S. Landolt (Gast)


Lesenswert?

> Aber leider nur für größere MEGA-AVRs geeignet.
Warum dieses? Gerade in Assembler kann man doch so anordnen, dass es bei 
dem 1/4 KiB Flash bleibt, und so ein ATtiny85 z.B. hat 8 KiB.

von Justav (Gast)


Lesenswert?

@ S. Landolt (Gast)

Hey, gut aufgepasst!
Nach den ersten beiden "eor" muss ein "mov Tmp1, Tmp0"
folgen, da man ja mit dem Ergebnis (!) von "eor" weiter
rechnen muss.

Mist - das gibt 11 Takte für die Grundfunktion. :-(
1
  mov  Tmp1, Tmp0
2
  swap Tmp0
3
  eor  Tmp0, Tmp1    ; reduziert auf 4 Bit
4
  mov  Tmp1, Tmp0
5
  lsr  Tmp0
6
  lsr  Tmp0
7
  eor  Tmp0, Tmp1    ; reduziert auf 2 Bit
8
  mov  Tmp1, Tmp0
9
  lsr  Tmp0
10
  eor  Tmp0, Tmp1    ; reduziert auf 1 Bit
11
  andi Tmp0, 1       ; Tmp0 = 1 (0) für ungerade (gerade)

Jetzt habe ich mir das Parity-Macro im AVR Libc Reference
Manual mal genau angesehen.
Die sind (lange vor mir) auf den gleichen Weg gekommen,
haben aber doch noch einen Befehl einsparen können!
1
  mov  Tmp1, Tmp0
2
  swap Tmp0
3
  eor  Tmp0, Tmp1    ; reduziert auf 4 Bit
4
  mov  Tmp1, Tmp0
5
  lsr  Tmp0
6
  lsr  Tmp0
7
  eor  Tmp0, Tmp1    ; reduziert auf 2 Bit
8
  inc  Tmp0          ; Direkte Auswertung der 2 Bit 
9
  lsr  Tmp0          ; Genial!
10
  andi Tmp0, 1       ; Tmp0 = 1 (0) für ungerade (gerade)

Sind genau 10 Takte, aber auf diesen Trick um einen popligen
Takt einzusparen, muss man erst mal kommen!

2 Bit   gerade: 00, oder  11
2 Bit ungerade: 01, oder  10
um 1 erhöht
2 Bit   gerade: 01, oder ?00
2 Bit ungerade: 10, oder  11
nach rechts geschoben
2 Bit   gerade: ?0, oder  ?0
2 Bit ungerade: ?1, oder  ?1
AND 1
2 Bit   gerade:  0, oder   0
2 Bit ungerade:  1, oder   1

Immerhin kann ich mir jetzt vorstellen, dass gute
C-Programme nicht unbedingt langsamer, als wenig
optimierte ASM-Programme sein müssen!

von c-hater (Gast)


Lesenswert?

Justav schrieb:

> Immerhin kann ich mir jetzt vorstellen, dass gute
> C-Programme nicht unbedingt langsamer, als wenig
> optimierte ASM-Programme sein müssen!

Ja, das kann gut mal passieren. Allerdings eher nur bei sehr trivialen 
Problemen, wie man sieht, gehört schon eine simple 8-Bit-Parity nicht 
mehr zum Kreis dieser Probleme...

Das Problem ist nämlich: dass es in C doch geht, hat eigentlich nix mit 
C zu tun, denn es ist ja nur deshalb so, weil wiederum Asm-Einschübe 
verwendet werden. C als Sprache kann das eben einfach nicht leisten, 
gerade die Existenz dieser Asm-Optimierungen zeigt das überdeutlich.

Und natürlich würde auch niemals einer der C-Compilerbauer auf die Idee 
kommen, zu behaupten, C könnte jemals so effizient wie Asm sein kann 
oder gar auf die Idee zu behaupten, C wäre bereits jetzt so weit...

Das wäre genau dann der Fall, wenn man die Sache einfach mit den 
Sprachmitteln von C hinschreiben könnte und der Compiler selber die 
optimale Form für das Zielsystem finden würde.

Das ist aber blanke Utopie und wird auch immer eine Utopie bleiben, das 
ist nämlich eine Konsequenz der Komplexitätsbetrachtung der Sache. Die 
ergibt: Natürlich kann ein C-Compiler theoretisch immer die optimale 
Lösung finden, allerdings erst in unendlicher Zeit. Da niemand unendlich 
Zeit hat, wird eben in Kauf genommen, dass das Compilat suboptimal ist.

Menschliche Asm-Programmierer gehen interessanterweise eigentlich ganz 
ähnlich vor wie ein C-Compiler, haben aber diesem gegenüber drei riesige 
Vorteile:

Sie können erstens unkonventionelle Lösungen finden, an die der 
Programmierer des Compilers nie gedacht hat und die der Compiler 
deswegen auch niemals anwenden kann, denn der macht nur das, was ihm 
irgendwann mal ein Mensch gesagt hat, was man tuen oder ausprobieren 
könnte.

Sie haben zweitens einen Überblick über das Gesamtwerk und können 
deshalb nicht nur mit einer sehr lokalen Sicht der Dinge optimieren, 
sondern zielgerichtet dort, wo es wirklich lohnt, da aber besser als der 
Compiler, weil sie z.B. bewußt in Kauf nehmen können, das irgendwelches 
völlig unwichtige, nur alle Jubeljahre überhaupt mal durchlaufene Zeug 
dadurch langsamer läuft.

Und drittens sind Menschen sehr viel besser als stupide Compiler in der 
Lage, Muster und Symmetrien zu erkennen und deren Existenz dafür zu 
nutzen, das Programm zu vereinfachen und dadurch zu beschleunigen. Ihnen 
steht nämlich das gesamte Hintergrundwissen zum konkreten Problem zur 
Verfügung, was der Compiler einfach mal nicht haben kann, weil es schon 
der Compilerbauer nicht hatte und nicht haben konnte.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

avr-gcc verwendet in der libgcc Code, der den Weg zu einer 9-Tick 
Version zeigt:

http://gcc.gnu.org/viewcvs/gcc/trunk/libgcc/config/avr/lib1funcs.S?revision=219188&view=markup#l2976
1
;; r24 = parity8 (r24)
2
;; clobbers: __tmp_reg__
3
4
    ;; parity is in r24[0..7]
5
    mov  __tmp_reg__, r24
6
    swap __tmp_reg__
7
    eor  r24, __tmp_reg__
8
    ;; parity is in r24[0..3]
9
    subi r24, -4
10
    andi r24, -5
11
    subi r24, -6
12
    ;; parity is in r24[0,3]
13
    sbrc r24, 3
14
    inc  r24
15
    ;; parity is in r24[0]
16
    andi r24, 1

Je nach Kontext kann das letzte ANDI entfallen und an gegebener Stelle 
durch den Test auf R24.0 ersetzt werden (SBRC R24, 0).

von Leo C. (rapid)


Lesenswert?

c-hater schrieb:
> Das Problem ist nämlich: dass es in C doch geht, hat eigentlich nix mit
> C zu tun, denn es ist ja nur deshalb so, weil wiederum Asm-Einschübe
> verwendet werden. C als Sprache kann das eben einfach nicht leisten,
> gerade die Existenz dieser Asm-Optimierungen zeigt das überdeutlich.

Quark.

1
unsigned char parity8(unsigned char x)
2
{
3
      x = x ^ (x >> 4);
4
      x = x ^ (x >> 2);
5
      x = x ^ (x >> 1);
6
7
      return x & 1;
8
}
$ avr-gcc -S -Os parity.c
1
        .file   "parity.c"
2
__SP_H__ = 0x3e
3
__SP_L__ = 0x3d
4
__SREG__ = 0x3f
5
__tmp_reg__ = 0
6
__zero_reg__ = 1
7
        .text
8
.global parity8
9
        .type   parity8, @function
10
parity8:
11
/* prologue: function */
12
/* frame size = 0 */
13
/* stack size = 0 */
14
.L__stack_usage = 0
15
        mov r25,r24
16
        swap r25
17
        andi r25,lo8(15)
18
        eor r25,r24
19
        mov r18,r25
20
        lsr r18
21
        lsr r18
22
        eor r18,r25
23
        mov r24,r18
24
        lsr r24
25
        eor r24,r18
26
        andi r24,lo8(1)
27
        ret
28
        .size   parity8, .-parity8
29
        .ident  "GCC: (GNU) 4.8.1"

von Possetitjel (Gast)


Lesenswert?

Justav schrieb:

> Eine 256 BYTE Tabelle wäre beim Tiny wohl Overkill.

Man könnte ein hybrides Verfahren versuchen: Zunächst
mittels mov/swap/xor von 8 Bit auf 4 Bit reduzieren;
dann die 4 Bit direkt in einer 16-Byte-Tabelle nachschlagen.

Ich bezweifele allerdings, dass man die vorgelegten 9 Takte
damit unterbieten kann.

von Roland P. (pram)


Lesenswert?

@Leo C.

Ein bisschen geht noch. Das "andi r25,lo8(15)" kann man sich auf alle 
Fälle noch einsparen. Und über die Sprungtabelle (hybrides Verfahren) 
geht auch noch etwas. (wobei ich mir hier nicht wirklich sicher bin, ob 
das im Ergebnis schneller ist)
1
unsigned char parity8(unsigned char x)
2
{
3
  x = x ^ (x >> 4 | x << 4); // echter Swap
4
  x = x & 0x0f;
5
  
6
  switch(x) {
7
    case 0:
8
    case 3:
9
    case 5:
10
    case 6:
11
    case 9:
12
    case 10:
13
    case 12:
14
    case 15:
15
    return 0;
16
  }
17
  return 1;
18
}

avr-gcc.exe (AVR_8_bit_GNU_Toolchain_3.4.1_830) 4.6.2
1
0000006e <parity8>:
2
  6e:  98 2f         mov  r25, r24
3
  70:  92 95         swap  r25
4
  72:  98 27         eor  r25, r24
5
  74:  9f 70         andi  r25, 0x0F  ; 15
6
  76:  e0 e6         ldi  r30, 0x60  ; 96
7
  78:  f0 e0         ldi  r31, 0x00  ; 0
8
  7a:  e9 0f         add  r30, r25
9
  7c:  f1 1d         adc  r31, r1 ; da es nicht zu einem Overflow kommen sollte, wäre diese Zeile auch überflüssig
10
  7e:  80 81         ld  r24, Z
11
  80:  08 95         ret

: Bearbeitet durch User
von Peter D. (peda)


Lesenswert?


von Justav (Gast)


Lesenswert?

@ Johann L. (gjlayde):

Super! Als ASM-Makro: 9 Takte + 1 Temp-Register.
Wenn das funktioniert: - Hut ab vor dem ASM-Künstler!

Wäre ich nicht mal schnell drauf gekommen... Weshalb
add 4  -  ausblenden von Bit 2   -  add 6
weiterführt, ist mir so schnell nicht klar.

Bin mal gespannt, ob es hier Leute gibt, die das verstehen
UND AUCH NOCH mit wenigen Worten anderen verständlich machen
können!


@  Peter Dannegger (peda)
Schon 10 Jahre alt, aber gut: 10 Takte + 1 Temp-Register,
wenn ich es als Makro einsetze.

@  Leo C. (rapid)
Als Makro optimiert sind das 12 Takte + 2 Temp-Register.

@  Roland Praml (pram)
Ojeh, 4 Temp-Register! Wenn ich einige davon sichern muss,
kostet das 4 Takte pro Register...

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Justav schrieb:
> @ Johann L. (gjlayde):
>
> Super! Als ASM-Makro: 9 Takte + 1 Temp-Register.
> Wenn das funktioniert: - Hut ab vor dem ASM-Künstler!
>
> Wäre ich nicht mal schnell drauf gekommen... Weshalb
> add 4  -  ausblenden von Bit 2   -  add 6
> weiterführt, ist mir so schnell nicht klar.
>
> Bin mal gespannt, ob es hier Leute gibt, die das verstehen
> UND AUCH NOCH mit wenigen Worten anderen verständlich machen
> können!

Frag Moby, der kann das.

Oder den Autor fragen, das Patch ist da: https://gcc.gnu.org/r175097

von Justav (Gast)


Lesenswert?

@ Possetitjel (Gast)

9 Takte - Garnicht mal so schlecht:
Allerdings müssen 3 Register (temp, XL, XH) reserviert sein
und die Tabelle darf keine BYTE-Grenze überschreiten.
1
  mov temp, val
2
  swap val
3
  eor val, temp
4
  andi val, 0x0F
5
  ldi XL,  low(PARI_TAB16)
6
  ldi XH, high(PARI_TAB16)
7
  add XL, val
8
  ld val, X

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.