Hi, die Maske für das niedrigste gesetze Bits eines Werts ungleich 0
kann man bekanntlich so ausrechnen:
> mask_lobit (x) = x EOR (x AND (x-1))
Beispiel: Für den 8-Bit Wert 010110 ergibt sich
> mask_lobit (010110) = 000010
Weiß jemand ein entsprechendes, effizientes Verfahren für mask_hibit?
Die Eingabe kann als ungleich 0 vorausgesetzt werden. Für das Beispiel
ist
> mask_hibit (010110) = 010000
Steh leider grad aufm Schlauch :-(
Mike Mike schrieb:> Ganzzahliger zweierlogarithmus?
Ok, und wie geht der effizient, d.h. ohne Schleife?
Zudem, selbst wenn man den kennt muss man noch 1 um die entsprechende
Anzahl nach links schieben, und das ist teuer ohen Barrel-Shifter.
"Billige" Operationen sind: AND, OR, XOR, PLUS, MINUS, Bit-Test, Shift
um 1, und Komplement, evtl. auch Multiplikation.
Wenn ich das richtig sehe, willst du alle Bits die niedrigwertiger sind,
auf 1 Setzten, und danach eins Addieren und um eins wieder nach links
shiften?
Sieht gut aus, aber ich nehme an, dass führt zu Problemen, wenn man nur
8 Bit Speicherplatz hat? Da dürfte man doch, wenn das höchste Bit
gesetzt ist, 0 rauskommen?
Mike Mike schrieb:> Sieht gut aus, aber ich nehme an, dass führt zu Problemen, wenn man nur> 8 Bit Speicherplatz hat? Da dürfte man doch, wenn das höchste Bit> gesetzt ist, 0 rauskommen?
Kein Problem in Assembler. Überlaufen kann nur ++i und dessen Carry kann
man gleich danach wieder reinschieben. Aus
++i;
i >>= 1;
wird daher sowas wie
adc r, #1
rcr r -- rotate thru carry
In C klappt das weniger gut, da braucht man ein Bit mehr.
Hacker's Delight (ISBN 0201914654) enthält zumindest einige Algorithmen
für "nlz" (number of leading zeros), würde dir das was helfen?
Eine Möglichkeit ist:
A. K. schrieb:> Vielleicht bei 8 Bits nicht besser, aber immerhin ohne Schleife:
1
if(i&(i-1)){
2
--i;
3
i|=i>>1;
4
i|=i>>2;
5
i|=i>>4;
6
++i;
7
i>>=1;
8
}
Das sieht schon mal seht gut aus :-)
Tatsächlich geht's um avr-gas Code. Momentan hab ich
1
ldi MASK, 1 << 0
2
sbrc VAL, 1 $ ldi MASK, 1 << 1
3
sbrc VAL, 2 $ ldi MASK, 1 << 2
4
sbrc VAL, 3 $ ldi MASK, 1 << 3
5
sbrc VAL, 4 $ ldi MASK, 1 << 4
6
sbrc VAL, 5 $ ldi MASK, 1 << 5
7
sbrc VAL, 6 $ ldi MASK, 1 << 6
8
sbrc VAL, 7 $ ldi MASK, 1 << 7
Nach obiger Methode werden aus den 15 Ticks/Instruktionen 13:
1
mov MASK, VAL
2
lsr MASK
3
or MASK, VAL
4
5
mov TMP, MASK
6
lsr MASK
7
lsr MASK
8
or MASK, TMP
9
10
mov TMP, MASK
11
swap MASK
12
andi MASK, 0xf
13
or MASK, TMP
14
15
lsr MASK
16
adc MASK, ZERO
Zumindest siehts beeindruckender aus :-)
Oder doch den Logarithmus? 1 << n braucht 7 Ticks auf AVR, der log
müsste also in weniger als 6 Ticks gehen, um besser zu sein...
Folgende Routine braucht 10 Zyklen (der Vergleichbarkeit halber ohne die
RETs):
1
val = 16
2
msk = 17
3
4
; input: val
5
; output: msk
6
; destroys: -
7
mask_hibit:
8
mov msk, val
9
andi msk, 0xf0
10
brne 2f
11
mov msk, val
12
andi msk, 0x0c
13
brne 1f
14
mov msk, val
15
andi msk, 0x02
16
brne 4f
17
ldi msk, 0x01
18
ret
19
1: andi msk, 0x08
20
brne 4f
21
ldi msk, 0x04
22
ret
23
2: andi msk, 0xc0
24
brne 3f
25
mov msk, val
26
andi msk, 0x20
27
brne 4f
28
ldi msk, 0x10
29
ret
30
3: andi msk, 0x80
31
brne 4f
32
ldi msk, 0x40
33
4: ret
Falls der Algorithmus nicht als Unterprogramm, sondern inline ausgeführt
werden soll, entfällt der letzte RET, und alle anderen müssen durch
einen RJMP ans Ende ersetzt werden. Wenn der Algorithmus über einen der
RMPs beendet wird, braucht er 2 Zyklen mehr, also 12 Zyklen. In diesem
Fall ist folgende Routine günstiger, da sie keine Ausstiegspunkte in der
Mitte hat. Sie braucht 11 Zyklen ohne den RET ist auch deutlich
kürzer und vor allem cooler:
1
val = 16
2
tmp = 17
3
4
; input: val
5
; output: val
6
; destroys: tmp
7
mask_hibit:
8
cpi val, 0x10
9
brcs 1f
10
andi val, 0xf0
11
1: mov tmp, val
12
andi tmp, 0xcc
13
brne 2f
14
mov tmp, val
15
2: mov val, tmp
16
andi val, 0xaa
17
brne 3f
18
mov val, tmp
19
3: ret
Zu beachten ist allerdings, dass das Input-Register mit dem Ergebnis
überschrieben wird. Will man das vermeiden, kostet das einen zusätzlich
Zyklus, so dass man wieder bei den 12 ist.
Übrigens sollte die mask_lobit-Routine nicht in der naheliegenden Weise
so implementiert werden (4 Zyklen):
1
val = 16
2
msk = 17
3
4
; input: val
5
; output: msk
6
; destroys: -
7
mask_lobit:
8
mov msk, val
9
dec msk
10
and msk, val
11
eor msk, val
12
ret
Scheller (3 Zyklen) und kürzer geht es so:
1
val = 16
2
msk = 17
3
4
; input: val
5
; output: msk
6
; destroys: -
7
mask_lobit:
8
mov msk, val
9
neg msk
10
and msk, val
11
ret
Es ist nicht auf den ersten Blick zu erkennen, dass beide Routinen exakt
dasselbe tun. Der GCC hat aber einen sehr scharfen Blick und übersetzt
x ^ (x & (x - 1));
entsprechend der zweiten Variante. Das haut mich total aus den Socken
und ist ein gutes Beispiel dafür, dass der GCC mitunter Optimierungen
vornimmt, auf die 99,9% der Assemblerprogrammierer nicht kommen würden.
Yalu schrob:
>....dass der GCC mitunter Optimierungen>vornimmt, auf die 99,9% der Assemblerprogrammierer nicht kommen würden.
Ich denke eher, daß die 0,1% in Deiner Rechnung fehlenden Leute zu 100%
hier im Forum vertreten sind.
;-)
MfG Paul
Johann L. schrieb:> Weiß jemand ein entsprechendes, effizientes Verfahren für mask_hibit?
Als "Joker-Verfahren", wenn man sonst kein ausreichend performantes
findet, gibt es immer die Lösung mit dem Array:
Markus W. schrieb:> Johann L. schrieb:>> Weiß jemand ein entsprechendes, effizientes Verfahren für mask_hibit?>> Als "Joker-Verfahren", wenn man sonst kein ausreichend performantes> findet, gibt es immer die Lösung mit dem Array: [...]>> Zwar braucht das etwas Speicherplatz, aber es ist sehr schnell...
Joker braucht 12 Ticks:
1
movw TMP, 30 ; 2
2
mov 30, MASK ; 1
3
clr 31 ; 1
4
subi 30, lo8(-(mask_hibit)) ; 1
5
sbci 31, hi8(-(mask_hibit)) ; 1
6
lpm MASK, Z ; 3
7
movw 30, TMP ; 2
8
clr ZERO ; 1
Die Zeiger-Register werden noch gebraucht und müssen daher gesichert
werden. Damit ist Joker langsamer und etwas spreicherfressender als
Yalus Vorschlag:
Yalu X. schrieb:> Folgende Routine braucht 10 Zyklen (der Vergleichbarkeit halber ohne> die RETs): [...]>> Falls der Algorithmus nicht als Unterprogramm, sondern inline ausgeführt> werden soll, [...] ist folgende Routine günstiger, da sie keine> Ausstiegspunkte in der Mitte hat. Sie braucht 11 Zyklen ohne den> RET ist auch deutlich kürzer und vor allem cooler:
Brain gegen Design-Pattern "Joker" = 1 : 0
Johann L. schrieb:>> Weiß jemand ein entsprechendes, effizientes Verfahren für mask_hibit?
Bleibt die Frag welchem kriterium das Verfahren entsprechen soll.
Laufzeit~ vs. Speichereffizienz
;-)
auf ein schönes WE
A. K. schrieb:> Nicht wenn man die Tabelle auf 256 Bytes aligned:>>
1
> movw TMP, 30 ; 2
2
> mov ZL, MASK ; 1
3
> mov ZH, hi8(mask_hibit) ; 1
4
> lpm MASK, Z ; 3
5
> movw 30, TMP ; 2
6
> clr ZERO ; 1
7
>
>> Nun sind es 10. Wenn TMP nicht 0 sein muss, dann 9.
Und wenn du jetzt noch lds statt lpm verwendest, sind es 7 Takte.
Natürlich muss man dann vorher das Feld im RAM aufgebaut haben.
Winfried J. schrieb:> Bleibt die Frag welchem kriterium das Verfahren entsprechen soll.>> Laufzeit~ vs. Speichereffizienz
Richtig! Nach beiden Kriterien gleichzeitig zu optimieren, gelingt
selten.
> auf ein schönes WE
Dem schließe ich mich an. :-)
Ihr kennt den Witz von dem Feuer im Hotel, dem Ingenieur und dem
Mathematiker?
Der Mathematiker reduziert das Problem auf eine bekannte Lösung. Bekannt
ist eine einfache Lösung für lobit. Um die auf hibit anzuwenden, muss
einfach das Byte gespiegelt werden:
1
lsl val
2
ror mval
3
lsl val
4
ror mval
5
lsl val
6
ror mval
7
lsl val
8
ror mval
9
lsl val
10
ror mval
11
lsl val
12
ror mval
13
lsl val
14
ror mval
15
lsl val
16
ror mval
17
18
mov mmsk, mval
19
neg mmsk
20
and mmsk, mval
21
22
lsl mmsk
23
ror msk
24
lsl mmsk
25
ror msk
26
lsl mmsk
27
ror msk
28
lsl mmsk
29
ror msk
30
lsl mmsk
31
ror msk
32
lsl mmsk
33
ror msk
34
lsl mmsk
35
ror msk
36
lsl mmsk
37
ror msk
Ok, das sieht jetzt noch nicht so effizient aus. Aber:
1
out PortB, val
2
in PortD, mval
3
4
mov mmsk, mval
5
neg mmsk
6
and mmsk, mval
7
8
out PortD, mmsk
9
in PortB, msk
Das sieht doch schon sehr schön aus, braucht nur 7 Takte und keinen
weiteren Flash oder Sram. Die korrekte Portinitialisierung muss sowieso
gemacht werden.
Ok, es hat einen kleinen Nachteil: PortB und D müssen gespiegelt
verbunden werden, also Pin 0 auf 7, 1 auf 6, 2 auf 5 usw.
Aber das ist dann Sache des Ings, der die Leiterplatte entwirft... ;-)
Ist doch eigentlich ein alltägliches Problem, ein Byte zu spiegeln
Das über 2 Ports HW zu verdrahten erscheint etwas spiky, aber im
Prozessor selbst? Gibt es da keinen Opcode?
Die Frage schwebt mir schon durch den Kopf seit ich den Titel des
Threads gelesen habe.
???
Datasheet ATmega16: "When reading back a software assigned pin value, a
nop instruction must be inserted as indicated in Figure 25. The out
instruction sets the “SYNC LATCH” signal at the positive edge of the
clock. In this case, the delay tpd through the synchronizer is one
system clock period."
Ergebnis:
Winfried J. schrieb:> Das über 2 Ports HW zu verdrahten erscheint etwas spiky, aber im> Prozessor selbst? Gibt es da keinen Opcode?
Beim AVR nicht. Der T800 von Inmos hatte einen Befehl, mit dem man die
Bitreihenfolge eines Wortes oder auch nur eines Teils davon umkehren
konnte. Dieser Befehl war vorgesehen für die Verwendung in
FFT-Implementierungen. Leider brauchte er für jedes zu bearbeitende Bit
einen Taktzyklus.
Frank M. schrieb:> Rate mal, was Beitrag "Re: Effizient Maske für höchstes gesetzes Bit berechnen?"
macht
Aber nicht so schön über externe Verdrahtung.
A. K. schrieb:> Datasheet ATmega16: "When reading back a software assigned pin value, a> nop instruction must be inserted
Musst ja keinen Mega16 nehmen, ein Tiny25 tuts auch... für 2 Bit.
Winfried J. schrieb:> Ist doch eigentlich ein alltägliches Problem, ein Byte zu spiegeln
Zum Beispiel, wenn man den Bus zwischen Controller und externen ADC
falschrum verbindet. Der betreffende Elektoniker hat dann die
Leiterbahnen weggekratzt und neu verbunden. Die Bits im AVR zu tauschen
erschien ihm wohl zu "quick and dirty". ;-)
Da wäre es ja noch einfach, aber mach den mal mit TX RX
atmega128<->max232
Da bist mit Skalpell und Brutzelstift schneller im Prototyp, weiß ich.
;-)
Namaste
Winfried J. schrieb:> Johann L. schrieb:>>>> Weiß jemand ein entsprechendes, effizientes Verfahren für mask_hibit?>> Bleibt die Frag welchem kriterium das Verfahren entsprechen soll.>> Laufzeit~ vs. Speichereffizienz
Natürlich allen :o)
• Laufzeit
• Speicherplatz (Flash, Stack, RAM)
• Eleganz
Der Fokus liegt eher auf Speed, aber für 1 oder 2 Ticks weniger würd ich
keine 256 Bytes oder noch mehr an RAM oder Flash verbraten. Das ist
einfach nicht mehr verhältnismässig.
Wie auch immer, eine schnellere Implementierung schlägt mit rund 0.2
Promille an Speedup zu Buche, so daß ich mich für eine einfach und
naheliegende Lösung entschieden habe anstatt eine schwer
nachvollziehbare zu nehmen.
Und da nach über 30 Posts noch nix gefunden wurde, das annähernd so
elegant ist wie x & -x for lomask, ist da wohl nix zu wollen...
@ Johann L. (gjlayde) Benutzerseite
>• Laufzeit>• Speicherplatz (Flash, Stack, RAM)>• Eleganz
Die Ansprüche steigen.
>Der Fokus liegt eher auf Speed, aber für 1 oder 2 Ticks weniger würd ich>keine 256 Bytes oder noch mehr an RAM oder Flash verbraten.
RAM sicher nicht, Flash kann man da schon eher verschmerzen. Eine
Schleife mit diversen Befehlen kostet auch Flash.
>Wie auch immer, eine schnellere Implementierung schlägt mit rund 0.2>Promille an Speedup zu Buche,
Da lohnt es sich nicht, auch nur ansatzweise drüber nachzudenken. Alles
rein philosophisch.
>Und da nach über 30 Posts noch nix gefunden wurde, das annähernd so>elegant ist wie x & -x for lomask, ist da wohl nix zu wollen...
Naja, man könnte ja ma spasseshalber die vollständige Logikgleichung in
einen KV-Diagramm eintragen und optimieren, vielleicht kommt da direkt
was sinnvolles raus?
Thread beobachten
Seitenaufteilung abschalten