Hallo, ich habe in einem Programm eine Variable (register). Ich möchte da möglichst effizient bestimmen wieviel Bits gesetzt sind, also: 0=>0 1=>1 2=>1 3=>2 ... 255=>8 Hintergrund: Die Variable benutze ich als Schieberegister, d.H. ich schiebe hinten immer meinen aktuellen Zustand hinein. Nun muss ich so eine Art Entprellung bauen. d.H. eine bestimmte Aktion soll ausgelöst werden wenn von den letztzen 8 gemessenen Zuständen mind 5 eins (bzw null) waren. Ich habe dafür sehr wenig Zeit und möchte möglichst wenig Takte dafür verwenden. Momentan spiele ich mit dem Gedanken eine Lookuptable zu verwenden welche grob geschätzt 10 Takte verbraucht, allerdings braucht die dann 256 Byte im Code. Plattform ist ein ATmega8 und avr-gcc (bzw. inline Assembler) Gruß Roland
Gast
#314017
ganz grob in pseudocode: tmp := Schieberegister sum := 0 clr carry *** - rotate tmp through carry - add sum, carry *** 8 mal if sum > 5 then do irgenwas müßt sich in assembler in etwa 25 takten ausgehen grüße leo
Gast
#314018
das wird auf jeden Fall die schnellste Variante sein, ein schlauer Algorithmus fällt mir dazu nicht ein (was nicht heisst, dass es den nicht gibt). Sollten die 256Byte flash ein Problem sein, kannst du die Tabelle ja auch in den EEPROM auslagern, der Zugriff ist zwar langsamer, mit 10 Takten solltest du da aber hinkommen. Noch ne Möglichkeit: beim Start eine Tabelle im RAM erstellen, da hast du ja Zeit und kannst die Daten mit Schieben berechnen.
Wenn die Bits eh einzeln reinkommen, dann zähl sie doch einfach dabei. Geht schneller und einfacher, als sie erst umständlich irgendwo reinzuschieben und dann erst zu testen.
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
Peter
Man könnte eventuell die Lookuptable auf nur 16 Einträge reduzieren, wenn man die Halbbytes separat verarbeitet und dann das Ergebnis addiert. Vermutlich wird der Aufwand zur Zerlegung und Verarbeitung aber größer sein, als das direkte 8malige addieren des C-Flags (leo9). Ich habs nicht probiert, ist nur eine Idee. Gruß Ingo
Gast
#314021
Mit noch weniger Takten gehts u.U. wenn man das Half-Carry-Flag mit einbezieht. Brauchst dann nur 4 mal zu schieben. Hab allerdings nicht ausprobiert, ob das wirklich weniger Takte braucht. Musst dann immerhin zwei Flags pro Schritt abfragen.
Gast
#314022
Hallo, ich versuche es mal schön primitiv und in ASM. clr R17 ldi R16,Schieberegister ;---- gesetzte Bits aufaddieren ------------- sbic R16,0 Inc R17 sbic R16,1 Inc R17 sbic R16,2 Inc R17 sbic R16,3 Inc R17 sbic R16,4 Inc R17 sbic R16,5 Inc R17 sbic R16,6 Inc R17 sbic R16,7 Inc R17 ;----------------------------------------- ;- Vergleich - cpi R17,5 breq irgendwohin Oder geht das am Problem völlig vorbei? Gruß Stevko
Gast
#314023
@Stevko: Ja, ich denke das ist tatsächlich die schnellste Methode. Aber Du musst den Befehl sbrc anstelle von sbic nehmen. r16 ist kein I/O-Register. Gruß Johnny
Gast
#314024
@stevko: GENIAL !! :-) ich glaube diese Variante kann an Effektivität nicht mehr überboten werden. grüße leo9
also ich würde beim Einlesen der Bits einfach 2 Zaähler mitlaufen lassen Bei 8051 würde ich über Carry einlesen und es gleich abfragen. zB. In Port X,C ( hast Du ja schon irgendwie ) If C=1 dann inc Zähler 1 If C =0 dann inc Zähler 2 Weiter mit Deinem Code. Nachdem alles eingelesen ist nur noch Zähler 1 und 2 =>5 Abfragen. Oder liege ich daneben, weil falsch verstanden.
......heißt natürlich MOV C,A .....woher der Akku auch immer kommt. Aber ich denke Du verstehst schon. Stephan
...uns wenn man den einen Zähler erhöht, sollte man den anderen Zähler löschen... Ich denke aber, dann man auch PeDa's (modifizierte) Eintastenentprellung (über WIKI und Entprellung zu finden) dazu geeignet ist, die muss ja nicht unbedingt in einer ISR laufen und einen Portpin abfragen. Das braucht vermutlich weniger Ressourcen. ...
Gast
#314028
... na mal sehen was Roland dazu sagt. @johnny.m: Hast natürlich recht mit dem sbrc. Muss hier nebenbei noch etwas arbeiten. Auf eine Schleife wollte ich verzichten, da Roland ja die Zeit knapp wird. Gruß Stevko
Gast
#314029
@Stevko: Möchte fast wetten, dass das Problem nicht besser lösbar ist als mit Deinem Vorschlag. Ne Schleife ist auf jeden Fall von der Bearbeitungszeit länger. Zwei Zyklen pro Bitüberprüfung ist das Minimum. Und leo9 wollte ja Zeitoptimierung und nicht Code-Size-Optimierung... Gruß Johnny
Gast
#314030
Benötigt denn "sbic R16,x" immer nur 1 Cycle? (Ein PIC-User)
Nein, im Fall des Überspringens 2 Zyklen. Da aber, falls nicht übersprungen wird, das "inc R17" (1 Zyklus) ausgeführt wird, ist das egal. Letzendlich werden pro Bit immer 2 Zyklen benötigt. Gruß Ingo
Gast
#314032
Nein, wenn die Bedingung erfüllt ist und ein Ein-Wort-Befehl (wie inc rXX) übersprungen werden muss, dann zwei Zyklen, aber dafür, dass der Befehl übersprungen wird, wird er ja nicht ausgeführt. Dadurch hat man wirklich pro Bitabfrage 2 Zyklen, egal ob das Bit gesetzt ist oder nicht! Gruß Johnny
Gast
#314033
Danke, und wann benötigt er 3 Zyklen (habe ich so im Datenblatt gelesen)???
Gast
#314034
Dann, wenn der zu überspringende Befehl ein 2-Wort- (also 32-Bit-) Befehl ist.
Gast
#314035
Wenn er einen Befehl überspringt, der zwei Worte groß ist, also lds, sts, jmp oder call.
Also erst mal danke für die Antworten, die Lösung von Stevko gefällt mir momentan am Besten. Und mit 16 Takten auch sehr flott. An das Zählen der Bits hab ich auch schon gedacht wie Peter vorgeschlagen hat, allerdings müssten die gesetzten Bits dann hintereinander kommen, ich denk man muss wirklich die letzten 8 Zustände speichern, weil bei dem Bitmuster 10101101 wäre z.B. count=2, sind aber 5 Einsen drin. Gruß Roland
Gast
#314037
>>ich glaube diese Variante kann an Effektivität nicht mehr überboten >>werden. mov ZL, r16 1 subi ZL, -Low(Table) 1 ldi ZH, High(Table) 1 lpm r16,Z 3 6 Takte wenn nur Geschwindikgeit zählt und man mit einer 256 Bytes Lookup Tabelle im FLASH leben kann die an 256 Bytes Grenze ausgerichtet wurde. 5 Takte wenn man diese Tabelle ins SRAM auslagert. Gruß Hagen
Hi, Hier Quersumme eines Bytes in 15 Takten ohne Tabelle; In C so kk= ((kk>>1)&0x55)+(kk&0x55); kk= ((kk>>2)&0x33)+(kk&0x33); kk= ((kk>>4)+kk)&0xf; und in Pseudo AVR-Assembler so: ;Wert in RX, RY ist Hilfsregister mov RY,RX asr RY andi RX,0x55 andi RY,0x55 add RX,RY ; das war die erste Zeile des C-Code mov RY,RX asr RY asr RY andi RX,0x33 andi RY,0x33 add RX,RY ; das war die zweite Zeile des C-Code mov RY,RX swap RY add RX,RY andi RX,0xf; fertig, Summe der gesetzten Bits in RX BTW: Roland will auf >= 5 vergleichen, da braucht man bei ner Tabellenlösung nur 256/8 Byte. Cheers Detlef
also wenn Du jedes reinkommende Bit zählst,dann wäre Zähler 1 bei 5 und Zähler 2 bei 3 und somit die Bedingung erfüllt. ( 5 Bits gerade ) Ergebnis gesichert und weiter gehts. wo ist das Problem ??
Gast
#314040
@Detlef: Spitze! Kleiner und schneller. Hast Du Dir das Verfahren selbst ausgedacht? Die bitweise Tabelle für den >=5 Test bringt übrigens nichts. Man verliert entweder die Takte beim Ausfiltern des richtigen Bits oder man bräuchte noch eine 8-Byte-Tabelle, mit dem das passende Bit ausgefiltert wird. Und dann ist es kleiner und schneller, zweimal eine 16-Byte-Tabelle zu nehmen (hier auf Seitengrenze im RAM gelegt): ldi ZH, High(Table) 1 mov ZL, r16 1 andi ZL, 0x0F 1 ld r17, Z 2 swap r16 1 mov ZL, r16 1 andi ZL, 0x0F 1 ld r16, Z 2 add r16, r17 1 11 Takte
Gast
#314041
Zur Abwechslung mal C - kurz und prägnant, auch wenn es die o.g.
Anforderungen nicht trifft.
uchar d,m,z; //Data, Maske, Zähler
d=0xaa;z=0; //aa als Beispiel
for(m=1;m;){m&d?z++:0;m*=2;}
oder
for(m=1;m;m&d?z++:0,m*=2){}
oder
uchar d,m,z;
d=0x55;m=1;z=0;
do m&d?z++:0;while(m*=2);
In der Kürze liegt die Würze.
Der Code von Detlef kommt mir bekannt vor...
Forum-Suche nach "Bits zählen" bringt etliche Treffer.
Leerzeichen, Einrückungen, Zeilenvorschübe, Variablennamen sind wohl nur was für Weicheier ? Es ging um die Kürze des ausführbaren Programms nicht um die Kürze des Quelltextes !!! Peter
Hallo Profi, Dein Code kommt mir auch bekannt vor, haste den nich mal für den "Obscure C contest " gepostet? Mein Code ist dagegen so einzigartig und bahnbrechend clever, daß Du den garnicht irgendwo gesehen haben kannst. Das is nurn Witz! kucks Du hier z.B.: http://de.wikipedia.org/wiki/Hamming-Abstand Cheers Detlef
gebt mal auf einem Unix-System mit fortune installiert folgendes ein:
> fortune -m "really weird C code"
Spuckt bei mir aus:
1 | |
2 | |
3 | |
4 | |
5 | |
dazu ein anderes passendes Zitat aus der fortune Datenbank: "The C Programming Language -- A language which combines the flexibility of assembly language with the power of assembly language." /Ernst
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.