AVR Arithmetik

Aus der Mikrocontroller.net Artikelsammlung, mit Beiträgen verschiedener Autoren (siehe Versionsgeschichte)
Version vom 23. Juni 2013, 21:07 Uhr von Andreas (Diskussion | Beiträge) (Textersetzung - „</c>“ durch „</syntaxhighlight>“)
Wechseln zu: Navigation, Suche

Dieser Artikel beschäftigt sich mit 16- und 32-Bit Arithmetik auf AVR-Controllern. Für detailierte Ausführungen zur 8-Bit Arithmetik auf AVR gibt es eine Seite im AVR-Tutorial.

Glossar

MSB: Most Significant Byte, Höchstwertiges Byte

LSB: Least Significant Byte, Niedrigstwertiges Byte

Vergleich

16 Bit

<avrasm> 

   ;
   ;              LSB  MSB         LSB  MSB
   ; Vergleiche < r16, r17 > mit < r20, r21 >
   ;

   cp    r16, r20
   cpc   r17, r21

</avrasm>

32 Bit

<avrasm> 

   ;
   ;              LSB            MSB         LSB            MSB
   ; Vergleiche < r16, r17, r18, r19 > mit < r20, r21, r22, r23 >
   ;

   cp    r16, r20
   cpc   r17, r21
   cpc   r18, r22
   cpc   r19, r23

</avrasm>

Addition

16 Bit + 16 Bit

<avrasm> 

   ;
   ; < r16, r17 > = < r16, r17 > + < r20, r21 >
   ;

   add   r16, r20
   adc   r17, r21

</avrasm>

32 Bit + 32 Bit

<avrasm> 

   ;
   ; < r16, r17, r18, r19 > = < r16, r17, r18, r19 > + < r20, r21, r22, r23 >
   ;

   add   r16, r20
   adc   r17, r21
   adc   r18, r22
   adc   r19, r23

</avrasm>

Subtraktion

16 Bit - 16 Bit

<avrasm> 

   ;
   ; < r16, r17 > = < r16, r17 > - < r20, r21 >
   ;

   sub   r16, r20
   sbc   r17, r21

</avrasm>

32 Bit - 32 Bit

<avrasm> 

   ;
   ;   LSB            MSB       LSB            MSB       LSB            MSB
   ; < r16, r17, r18, r19 > = < r16, r17, r18, r19 > - < r20, r21, r22, r23 >
   ;

   sub   r16, r20
   sbc   r17, r21
   sbc   r18, r22
   sbc   r19, r23

</avrasm>

Division

32 Bit / 32 Bit

Ergebnis gerundet, und mit Restbildung.

<avrasm> .def a0 = r16 .def a1 = r17 .def a2 = r18 .def a3 = r19

.def b0 = r20 .def b1 = r21 .def b2 = r22 .def b3 = r23

.def t0 = r24 .def t1 = r25 .def t2 = r26 .def t3 = r27 .def t4 = r28

  • *
  • unsigned rounded division 32 bit *
  • *

urdiv32: mov t0, b0 ;T = B mov t1, b1 mov t2, b2 mov t3, b3 lsr t3 ;B / 2 ror t2 ror t1 ror t0 add a0, t0 ;A = A + B / 2 adc a1, t1 adc a2, t2 adc a3, t3

  • *
  • unsigned division 32 bit *
  • *
a3..0 = a3..0 / b3..0
b3..0 = remainde
cycle
max 684

udiv32: clr t0 clr t1 clr t2 clr t3 ldi t4, 32 udi1: lsl a0 rol a1 rol a2 rol a3 rol t0 rol t1 rol t2 rol t3 cp t0, b0 cpc t1, b1 cpc t2, b2 cpc t3, b3 brcs udi2 sub t0, b0 sbc t1, b1 sbc t2, b2 sbc t3, b3 inc a0 udi2: dec t4 brne udi1 mov b0, t0 mov b1, t1 mov b2, t2 mov b3, t3 ret

</avrasm>

Eine Version, die je nach konkreten Zahlen Rechenzeit einspart

<avrasm> .def a0 = r16 .def a1 = r17 .def a2 = r18 .def a3 = r19

.def b0 = r20 .def b1 = r21 .def b2 = r22 .def b3 = r23

.def t0 = r24 .def t1 = r25 .def t2 = r26 .def t3 = r27

  • *
  • unsigned rounded division 32 bit *
  • *

urdiv32: mov t0, b0 ;T = B mov t1, b1 mov t2, b2 mov t3, b3 lsr t3 ;B / 2 ror t2 ror t1 ror t0 add a0, t0 ;A = A + B / 2 adc a1, t1 adc a2, t2 adc a3, t3

  • *
  • unsigned division 32 bit *
  • *
cycle
max 431 (63%) (684)

udiv32: clr t1 tst b3 breq udi10 ldi t0, 8 udi1: lsl a0 rol a1 rol a2 rol a3 rol t1 cp a1, b0 cpc a2, b1 cpc a3, b2 cpc t1, b3 brcs udi2 sub a1, b0 sbc a2, b1 sbc a3, b2 sbc t1, b3 inc a0 udi2: dec t0 brne udi1 mov b0, a1 clr a1 mov b1, a2 clr a2 mov b2, a3 clr a3 mov b3, t1 ret

udi10: tst b2 breq udi20 ldi t0, 16 udi11: lsl a0 rol a1 rol a2 rol a3 rol t1 brcs udi12 cp a2, b0 cpc a3, b1 cpc t1, b2 brcs udi13 udi12: sub a2, b0 sbc a3, b1 sbc t1, b2 inc a0 udi13: dec t0 brne udi11 mov b0, a2 clr a2 mov b1, a3 clr a3 mov b2, t1 ret

udi20: tst b1 breq udi30 ldi t0, 24 udi21: lsl a0 rol a1 rol a2 rol a3 rol t1 brcs udi22 cp a3, b0 cpc t1, b1 brcs udi23 udi22: sub a3, b0 sbc t1, b1 inc a0 udi23: dec t0 brne udi21 mov b0, a3 clr a3 mov b1, t1 ret

udi30: ldi t0, 32 udi31: lsl a0 rol a1 rol a2 rol a3 rol t1 brcs udi32 cp t1, b0 brcs udi33 udi32: sub t1, b0 inc a0 udi33: dec t0 brne udi31 mov b0, t1 ;store remainder ret

------------------------------------------------------------------------

</avrasm>

Multiplikation

32 Bit * 16 Bit

<avrasm> .def a0 = r16 .def a1 = r17 .def a2 = r18 .def a3 = r19

.def b0 = r20 .def b1 = r21 .def b2 = r22 .def b3 = r23

.def t0 = r24 .def t1 = r25 .def t2 = r26 .def t3 = r27 .def i0 = r28

  • *
  • unsigned multiplication 32 bit *
  • *
cycle
max 245

umul32: cpi a3, 0 cpc a3, a2 breq _umu1 ;one operand must be below 65536 mov t0, a0 ; swap A <-> B mov a0, b0 mov b0, t0 mov t0, a1 mov a1, b1 mov b1, t0 mov b2, a2 mov b3, a3 clr a2 clr a3

a3,2,1,0 = a1,0 * b3,2,1,0

_umu1: ldi i0, 16 clr t0 clr t1 ror a1 ror a0 _umu2: brcc _umu3 add a2, b0 adc a3, b1 adc t0, b2 adc t1, b3 _umu3: ror t1 ror t0 ror a3 ror a2 ror a1 ror a0 dec i0 brne _umu2 ret

------------------------------------------------------------------------

</avrasm>

24 Bit * 24 Bit

<avrasm>

muls24x24_48
Signed Multiply von 2 24Bit breiten Zahlen mit 48Bit ergebnis
x = a * b
R21
R20:R19:R18:R17:R16 = R27:R26:R25 * R24:R23:R22
hi lo hi lo hi lo

muls24x24_48: 

   clr    r2          ;Zero Register
   muls  r27,r24        ; (1) signed Multiply a(MSB) * b(MSB)
   movw   r20,r0

   mul    r26,r23        ; (2) unsigned
   movw   r18,r0

   mul    r25,r22        ; (3) unsigned multiply a(LSB) * b(LSB)
   movw   r16,r0

   mul    r26,r22        ;(4) unsigned
   add    r17,r0
   adc    r18,r1
   adc    r19,r2
   adc    r20,r2
   adc    r21,r2

   mul    r25,r23        ;(5) unsigned
   add    r17,r0
   adc    r18,r1
   adc    r19,r2
   adc    r20,r2
   adc    r21,r2

   push  r16
   push  r17

   mov    r16,r27
   mulsu  r16,r22        ;(6) unsigned * signed
   sbc    r20,r2
   sbc    r21,r2
   add    r18,r0
   adc    r19,r1
   adc    r20,r2
   adc    r21,r2

   mulsu  r16,r23        ;(7) unsigned * signed
   sbc    r21,r2
   add    r19,r0
   adc    r20,r1
   adc    r21,r2

   movw   r16,r24
   mulsu  r16,r17        ;(8) unsigned * signed
   sbc    r20,r2
   sbc    r21,r2
   add    r18,r0
   adc    r19,r1
   adc    r20,r2
   adc    r21,r2

   mov    r17,r26
   mulsu  r16,r17        ;(9) unsigned * signed
   sbc    r21,r2
   add    r19,r0
   adc    r20,r1
   adc    r21,r2

   pop    r17
   pop    r16
   ret

</avrasm>

Wurzel

avr-gcc Implementierung (32 Bit)

Quadratwurzel basierend auf einer Implementierung von Ruud v Gessel[1], die zusammen mit avr-gcc verwendet werden kann. Je nach Algorithmus wird das Ergebnis zum Nächsten gerundet oder abgerundet. Abrunden ist dann angesagt, wenn die Wurzel aus einer großen Eingabe wie 0xffffffff zu ziehen ist, da bei Aufrunden hier das Ergebnis zu 0 überläuft.

Die maximale Ausführungszeit ist höchstens 310 Ticks (inclusive CALL+RET):

sqrt32.h <c>

  1. ifndef SQRT32_H
  2. define SQRT32_H
  3. include <stdint.h>

extern uint16_t sqrt32_round (uint32_t); extern uint16_t sqrt32_floor (uint32_t);

  1. endif /* SQRT32_H */

</syntaxhighlight>

C-Module, welche die Wurzel benötigen, includen einfach diesen Header. Das Assembler-Modul wird assembliert und zum Projekt hinzugelinkt.

Rundung zum Nächsten

Ressourcen-Verbrauch, Rundung zum Nächsten
Flash 82 Bytes
RAM 2–3 Bytes dynamisch, 0 Bytes statisch
Laufzeit 265–310 Ticks (inclusive Zeiten für CALL+RET)

sqrt32.S (sqrt32_round)

{{{2}}}

Abrunden

Ressourcen-Verbrauch, Abrunden
Flash 60 Bytes
RAM 2–3 Bytes dynamisch, 0 Bytes statisch
Laufzeit 260–300 Ticks (inclusive Zeiten für CALL+RET)

sqrt32.S (sqrt32_floor)

{{{2}}}


avr-gcc Implementierung (16 Bit)

Falls eine MUL-Instruktion vorhanden ist, benötigt eine 16-Bit Implementierung der Quadratwurzel nur eine handvoll Instruktionen und kann einigermassen bequem in Inline-Assembler geschrieben werden. Der Assembler-Teil besteht lediglich aus 9 Instruktionen und dauert unabhängig vom Eingabewert 80 Ticks.

sqrt16_floor (Braucht MUL, Inline-Assembler und auf Größe optimiert) <c>

  1. include <stdint.h>
  1. if defined (__AVR_ENHANCED__)

static inline uint8_t sqrt16_floor (uint16_t q) { 

   uint8_t res = 0;
   uint8_t mask = 1 << 7;
   
   asm("0:	add  %[res], %[mask]"   "\n"
       "	mul  %[res], %[res]"    "\n"
       "	cp   %A[q], R0"         "\n"
       "	cpc  %B[q], R1"         "\n"
       "	brsh 1f"                "\n"
       "	sub  %[res], %[mask]"   "\n"
       "1:	lsr  %[mask]"           "\n"
       "	brne 0b"                "\n"
       "	clr  __zero_reg__"
       : [res] "+r" (res), [mask] "+r" (mask)
       : [q] "r" (q));
       
   return res;

}

  1. endif // __AVR_ENHANCED__

</syntaxhighlight>

Es handelt sich um eine größenoptimierte Version eines Algorithmus' von Marko Surup, siehe Forum: AVR: 16-Bit Quadratwurzel in 63 Takten.

C-Variante

Die C-Variante verbraucht auf einem ATmega etwa 25 Instruktionen und 120 Ticks inclusive Funktionsaufruf und Parameteraufbereitung (getestet mit avr-gcc 4.6 und auf Größe optimiert): <c>

  1. include <stdint.h>

uint8_t c_sqrt16 (uint16_t q) { 

   uint8_t r, mask;
   uint8_t i = 8*sizeof (r) -1;

   r = mask = 1 << i;
   
   for (; i > 0; i--)
   {
       mask >>= 1;
       
       if (q < (uint16_t) r*r)
           r -= mask;
       else
           r += mask;
   }
   
   if (q < (uint16_t) r*r)
       r -= 1;
   
   return r;

}</syntaxhighlight>

Binär zu BCD - Umwandlung

Zur Ausgabe einer Binärzahl auf ein Textdisplay oder zur seriellen ASCII-Übertragung an den PC ist diese Umwandlung nötig. Sie ist ähnlich aufwendig wie eine Division, zum Beispiel für eine 32-Bit-Zahl etwa 500-900 Taktzyklen und 10 Register. Mehrere Verfahren werden angeboten:

Division /10

Für eine Division pro Dezimalstelle ist nur ein Unterprogramm nötig. Der Divisionsrest, engl. remainder, bildet unmittelbar die BCD-codierte Dezimalziffer, von rechts nach links fortschreitend. Zur Ausgabe von links nach rechts kann man die Ziffern auf dem Stack zwischenlagern (LIFO-Register last-in first-out)

Beispiele:

Division /10000, /1000, /100, /10

ähnlich dem vorigen, aber die BCD-Ziffern erscheinen sofort von links nach rechts.

Beispiele:

Addition von $33

Hier wird die Binärzahl, mit der höchstwertigen Stelle voran, von rechts in die Ergebnisregister geschoben. Nach jedem Schiebevorgang wird eine Korrekturrechnung ausgeführt. Für 32 Bit bilden 4 Eingabe- und 5 Ausgaberegister ein 72 Bit Schieberegister, das 32 mal links geschoben wird. Durch die Korrekturrechnung wird die Binärzahl zur gepackten (2 Stellen pro Byte) BCD-Zahl "aufgebläht".

Eine Erklärung des Algorithmus soll hier versucht werden: Um die niederwertigste 4 Bit Binärziffer in BCD umzuwandeln, ist für $0...$9 keine Änderung nötig, für $A...$F wird "6" addiert. Diese Addition wird ersetzt durch eine Addition von "3" und anschließendes Linksschieben. Das führt man zunächst für beide Halbbytes gleichzeitig mit "subi Reg,-$33" aus. Anschließend werden die beiden Additionen einzeln für den Fall "0...9" rückgängig gemacht. Die Bits 4 und 7 des Registers dient dabei als BCD-Carry-Flag (Halbbyte-Übertrag). Das normale C-Flag wird durch die Additionen nicht beeinflußt, es dient nur dem Schiebevorgang.

Beispiele:

Tabelle

Für kleine Zahlen kann die gesuchte BCD-Zahl auch aus einer Tabelle entnommen werden.

Mischvarianten

Eine Mischung mehrerer Verfahren wird z. B. von Andre Birua in der ersten Variante von "Bin4BCD" verwendet. Die oberen 16 Bit werden nach "Div/10000" vorbearbeitet und anschließend alle 32 Bit nach "Add $33".

Tutorial

enthält C-Code und PIC-Code für schnelle 16 Bit Wandlung, Hardware-Multiplizierer möglich - auch für FPGA interessant

Diskussionsbeiträge im Forum

Sinus und Cosinus

→ siehe AVR Arithmetik/Sinus und Cosinus (CORDIC)
→ siehe AVR Arithmetik/Sinus und Cosinus (Lineare Interpolation)

Saturierung

→ siehe AVR Arithmetik/Saturierung

Fußnoten

  1. ↑ Ruud v Gessel: Quadratwurzeln

Weblinks

Abgerufen von „https://www.mikrocontroller.net/index.php?title=AVR_Arithmetik&oldid=76736“