Forum: Mikrocontroller und Digitale Elektronik Parity rechnen mit AVR


von Seph (Gast)


Lesenswert?

Wie rechnet man am Effizientesten die Parity eines Bytes ? Das Ziel ist 
zu wissen ob die Anzahl gesetzter Bits gerade oder ungerade ist. Leider 
kann der AVR das nicht in Hardware. Eine For Schleife mit compare leider 
ist zuviel Aufwand.

von DO (Gast)


Lesenswert?


von Marius S. (lupin) Benutzerseite


Lesenswert?

par = 0;
while(byte>0) {
par ^= (byte&1);
byte >>= 1;
}

denke ich...

von Marius S. (lupin) Benutzerseite


Lesenswert?

Dirks lösung ist natürlich viel besser, jetzt würde ich nur noch gerne 
den code im listing verstehen... :)

von Patrick (Gast)


Lesenswert?

Mir ist da grad ne lustige Lösung in asm eingefallen, frisst allerdings 
etwa 600 bytes:

Etwa so:
clr r17
;(parity byte mit 2 multiplizieren, wegen 2byte langem opcode)
lsl r16 ;low byte vo zu bestimmenden parity byte
rol r17 ;carry U.u in r17 reinrollen;
ldi r30 low(IP_vor_ijmp)
ldi r31 high(IP_vor_ijmp)
add r30,r16
adc r31,r17
IP_vor_ijmp:
ijmp
rjmp even parity;(0 hat gerade parität)
rjmp odd parity;(1 hat ungerade parität)
rjmp even parity;(2 hat gerade parität)
rjmp odd parity;(3 hat ungerade parität)
.
.
.
.
rjmp odd parity;(255 hat ungerade parität)
rjmp even parity;(256 hat gerade parität)

odd parity:
....
even parity:
......

11 CPU Cycles, who's faster, C is es sicher nicht :)

von Patrick (Gast)


Lesenswert?

noch eine kleiner fehler in programm:
2 hat ungerade parität
3 hat gerade parität
255 ungerade
Sorry kurz falsch gedacht

von Seph (Gast)


Lesenswert?

Patrick's code sollte noch einige symmetrien ausnutzen und etwas 
kompakter werden.

von Simon K. (simon) Benutzerseite


Lesenswert?

1
#include <avr/pgmspace.h>
2
#include <stdint.h>
3
4
#define PARITY_ODD 0
5
#define PARITY_EVEN 1
6
7
const uint8_t PROGMEM ParityTable[256] = 
8
{
9
    PARITY_EVEN,
10
    PARITY_ODD,
11
    PARITY_ODD,
12
    PARITY_EVEN,
13
    ...
14
};
15
16
main()
17
{
18
    uint8_t parity = pgm_read_byte(&ParityTable[133]); //Parity von 133
19
    
20
    if (parity == PARITY_EVEN)
21
    {
22
        ...
23
    }else
24
    {
25
        ...
26
    }
27
}

Da kommt sicher keiner dran ;) Sowohl von der Code-menge als auch von 
der Ausführungsgeschwindigkeit.

von Peter D. (peda)


Lesenswert?

Patrick wrote:
> Mir ist da grad ne lustige Lösung in asm eingefallen, frisst allerdings
> etwa 600 bytes:
> ...
> 11 CPU Cycles, who's faster, C is es sicher nicht :)

Du irrst, in C dauerts nur 10 Zyklen und braucht auch nur 20 Bytes.

Ist nämlich ein Assemblermacro in der "parity.h".


Peter

von Seph (Gast)


Lesenswert?

Wie schaut der ASM code denn aus ? Ich hab's nicht geschafft.

(__extension__({                                        \
        unsigned char __t;                              \
        _asm_ (                                       \
                "mov _tmp_reg_,%0" "\n\t"             \
                "swap %0" "\n\t"                        \
                "eor %0,__tmp_reg__" "\n\t"             \
                "mov _tmp_reg_,%0" "\n\t"             \
                "lsr %0" "\n\t"                         \
                "lsr %0" "\n\t"                         \
                "eor %0,__tmp_reg__"                    \
                : "=r" (__t)                            \
                : "0" ((unsigned char)(val))            \
                : "r0"                                  \
        );                                              \
        (((__t + 1) >> 1) & 1);                         \
 }))

macht :

 mov  R16, %0
 swap %0
 eor %0, R16
 mov R16, %0
 lsr %0
 lsr %0
 eor %0, R16

und weiter ?

von Εrnst B. (ernst)


Lesenswert?

Das spuckt der GCC für nen einfachen Aufruf des parity_even_bit Macros 
aus:
1
       mov __tmp_reg__,r24
2
        swap r24
3
        eor r24,__tmp_reg__
4
        mov __tmp_reg__,r24
5
        lsr r24
6
        lsr r24
7
        eor r24,__tmp_reg__
8
9
        subi r24,lo8(-(1))
10
        lsr r24
11
        andi r24,lo8(1)

C Code:
1
  unsigned char x;
2
  x=PINB;
3
  x=parity_even_bit(x);
4
  PORTB=x;

(Die PINB/PORTB Zugriffe verhindern nur, daß der Optimierer das ganze 
komplett verwirft...)

von Christian (Gast)


Lesenswert?

Auf so ein Makro muss man erst mal kommen. Falls jemand Schwierigkeiten 
hat, den Assembler-Code nachzuvollziehen:

Seien a bis h die Bits des untersuchenden Werts. a ist das MSB (oberstes 
Bit, Bit 7), h das LSB (unterstes Bit, Bit 0). R24 ist also zu Anfang 
abcdefgh.

Durch SWAP, EOR(=XOR), 2xLSR, EOR stehen schließlich in den untersten 
beiden Bits von R24 (die restlichen sind nicht relevant, "x"):
Bit 1: a XOR c XOR e XOR g = Parity von aceg
Bit 0: b XOR d XOR f XOR h = Parity von bdfh

Damit die Parity des Bytes gerade ist, müssen die Teil-Parities entweder 
beide gerade oder beide ungerade sein, d.h.
R24 = xxxxxx00 oder R24 = xxxxxx11.
Nach Addition von 1 (SUBI), gilt dann also
R24 = xxxxxx01 oder R24 = xxxxxx00. Durch ein weiteres LSR und die 
Maskierung mit AND wird selektiv das Bit 1 ausgewertet, was im Falle 
einer geraden Parity 0 ist und im Falle einer ungeraden Parity 1.

von Hagen R. (hagen)


Lesenswert?

8 Bit hat ein Byte, wir teilen in 2 Hälfen und xor'en 4 Bit, das 
Resultat in 2 Hälften und xor'en 2 Bits und das dann nochmal.

Gruß Hagen

von AVRFan (Gast)


Lesenswert?

>8 Bit hat ein Byte

Dachte immer, ein Byte hat 8 Bit ;-)

>wir teilen in 2 Hälfen und [...]

Jepp, das ist das Prinzip.  In diesem Code kann man es besser erkennen:
1
    mov   t, a    ; a = Input der Routine
2
    lsr   a
3
    lsr   a
4
    lsr   a
5
    lsr   a
6
    eor   a, t
7
8
    mov   t, a
9
    lsr   a
10
    lsr   a
11
    eor   a, t
12
13
    mov   t, a
14
    lsr   a
15
    eor   a, t
16
17
    andi  a, 1    ; Ergebnis: a = 0[1] wenn Parität even[odd]

Zuerst wird um 8/2 = 4 Stellen rechtsgeschoben, danach um 2 Stellen, und 
am Schluss um eine.  Dann enthält Bit 0 von a das Ergebnis.

Den "lsr"-Viererblock kann man durch ein "swap a" ersetzen, außerdem 
(wie man sich leicht klarmachen kann) die letzten vier Instruktionen 
durch diese drei:
1
    inc   a
2
    lsr   a
3
    andi  a, 1

Tut man dies, hat man genau Dirks Code reproduziert.

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.