Gesetzte Bits zählen

[Roland P. (pram)]

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

[leo9 (Gast)]

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

[crazy horse (Gast)]

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.

[Peter D. (peda)]

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.

unsigned char countbit( unsigned char bit )
{
  static unsigned char count;

  if( bit ){
    if( count < 8 )
      count++;
  }else{
    if( count )
      count--;
  }
  if( count >= 5 )
    return 1;                   // >= 5 einsen
  if( count <= 3 )
    return 0;                   // >= 5 nullen
  return 2;                     // 4 einsen
}

Peter

[Ingo H. (putzlowitsch)]

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

[johnny.m (Gast)]

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.

[Stevko (Gast)]

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

[johnny.m (Gast)]

@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

[leo9 (Gast)]

@stevko: GENIAL !! :-)
ich glaube diese Variante kann an Effektivität nicht mehr überboten
werden.
grüße leo9

[Stephan H. (stephan-)]

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.

[Stephan H. (stephan-)]

......heißt natürlich
MOV C,A .....woher der Akku auch immer kommt.
Aber ich denke Du verstehst schon.

Stephan

[Hannes L. (hannes)]

...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.

...

[Stevko (Gast)]

... 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

[johnny.m (Gast)]

@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

[sackgesicht (Gast)]

Benötigt denn "sbic R16,x" immer nur 1 Cycle?

(Ein PIC-User)

[Ingo H. (putzlowitsch)]

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

[johnny.m (Gast)]

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

[sackgesicht (Gast)]

Danke, und wann benötigt er 3 Zyklen (habe ich so im Datenblatt
gelesen)???

[johnny.m (Gast)]

Dann, wenn der zu überspringende Befehl ein 2-Wort- (also 32-Bit-)
Befehl ist.

[Rolf Magnus (Gast)]

Wenn er einen Befehl überspringt, der zwei Worte groß ist, also lds,
sts, jmp oder call.

[Roland P. (pram)]

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

[Hagen (Gast)]

>>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

[Detlef _. (detlef_a)]

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

[Stephan H. (stephan-)]

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 ??

[Philipp Sªsse (Gast)]

@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

[Profi (Gast)]

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.

[Peter D. (peda)]

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

[Detlef _. (detlef_a)]

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

[Εrnst B. (ernst)]

gebt mal auf einem Unix-System mit fortune installiert folgendes ein:

> fortune -m "really weird C code"

Spuckt bei mir aus:

#define BITCOUNT(x)     (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define  BX_(x)         ((x) - (((x)>>1)&0x77777777)   \
                        - (((x)>>2)&0x33333333)        \
                        - (((x)>>3)&0x11111111))
    -- really weird C code to count the number of bits in a word

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