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