AVR Arithmetik

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

Glossar

• LSB: Least Significant Byte, niedrigstwertiges Byte
• MSB: Most Significant Byte, höchstwertiges Byte

Vergleich

16 Bit

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

    cp    r16, r20
    cpc   r17, r21

32 Bit

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

Addition

16 Bit + 16 Bit

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

    add   r16, r20
    adc   r17, r21

32 Bit + 32 Bit

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

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

Subtraktion

16 Bit - 16 Bit

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

    sub   r16, r20
    sbc   r17, r21

32 Bit - 32 Bit

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

Division

32 Bit / 32 Bit

Ergebnis gerundet, und mit Restbildung.

.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 (Ganzzahldivision)
; b3..0 = a3..0 % b3..0 (Rest)

; 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

Eine Version, die je nach konkreten Zahlen Rechenzeit einspart

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

Multiplikation

32 Bit * 16 Bit

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

24 Bit * 24 Bit

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

Weiterführende Links

• Multiplikation in Assembler – enthält schon viele kleine Multiplikations-Include-Dateien für den AVR-Assembler

Wurzel

avr-gcc-Implementierung (32 Bit)

Quadratwurzel basierend auf einer Implementierung von Ruud v Gessel, 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

#ifndef SQRT32_H
#define SQRT32_H
#include <stdint.h>

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

#endif /* SQRT32_H */

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)

;-----------------------------------------------------------
; Fast and short 32 bits AVR sqrt routine, avr-gcc ABI compliant
; R25:R24 = SQRT (R25:R24:R23:R22) rounded to the
; nearest integer (0.5 rounds up)
; Destroys R18-R19,R22-R23,R26-R27
; Cycles incl call & ret = 265-310
; Stack incl call = 2-3
;-----------------------------------------------------------
.text
.global sqrt32_round
.type sqrt32_round, @function

sqrt32_round:
    ldi   R19, 0xc0
    clr   R18          ; rotation mask in R19:R18
    ldi   R27, 0x40
    sub   R26, R26     ; developing sqrt in R27:R26, C=0
1:  brcs  2f           ; C --> Bit is always 1
    cp    R24, R26
    cpc   R25, R27     ; Does test value fit?
    brcs  3f           ; C --> nope, bit is 0
2:  sub   R24, R26
    sbc   R25, R27     ; Adjust argument for next bit
    or    R26, R18
    or    R27, R19     ; Set bit to 1
3:  lsr   R19
    ror   R18          ; Shift right mask, C --> end loop
    eor   R27, R19
    eor   R26, R18     ; Shift right only test bit in result
    rol   R22          ; Bit 0 only set if end of loop
    rol   R23
    rol   R24
    rol   R25          ; Shift left remaining argument (C used at 1:)
    sbrs  R22, 0       ; Skip if 15 bits developed
    rjmp  1b           ; Develop 15 bits of the sqrt
    brcs  4f           ; C--> Last bits always 1
    cp    R26, R24
    cpc   R27, R25     ; Test for last bit 1
    brcc  5f           ; NC --> bit is 0
4:  sbc   R23, R19     ; Subtract C (any value from 1 to 0x7f will do)
    sbc   R24, R26
    sbc   R25, R27     ; Update argument for test
    inc   R26          ; Last bit is 1
5:  lsl   R23          ; Only bit 7 matters
    rol   R24
    rol   R25          ; Remainder * 2 + C
    brcs  6f           ; C --> Always round up
    cp    R26, R24
    cpc   R27, R25     ; C decides rounding
6:  adc   R26, R19
    adc   R27, R19     ; Round up if C (R19=0)
    mov   R25, R27     ; return in R25:R24 for avr-gcc ABI compliance
    mov   R24, R26
    ret

.size sqrt32_round, .-sqrt32_round

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)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;  Fast and short 32 bits AVR sqrt routine, avr-gcc ABI compliant
;  R25:R24 = SQRT (R25:R24:R23:R22)
;  rounded down to integer
;     Destroys R26,R27,R22,R23,R18,R19
;  Cycles incl call & ret = 260-300
;  Stack incl call = 2-3
.text
.global sqrt32_floor
.type sqrt32_floor, @function

sqrt32_floor:
    ldi   R19, 0xc0
    clr   R18               ; rotation mask in R19:R18
    ldi   R27, 0x40
    sub   R26, R26          ; developing sqrt in R27:R26, C=0
1:  brcs  2f                ; C --> Bit is always 1
    cp    R24, R26
    cpc   R25, R27          ; Does test value fit?
    brcs  3f                ; C --> nope, bit is 0
2:  sub   R24, R26
    sbc   R25, R27          ; Adjust argument for next bit
    or    R26, R18
    or    R27, R19          ; Set bit to 1
3:  lsr   R19
    ror   R18               ; Shift right mask, C --> end loop
    eor   R27, R19
    eor   R26, R18          ; Shift right only test bit in result
    rol   R22               ; Bit 0 only set if end of loop
    rol   R23
    rol   R24
    rol   R25               ; Shift left remaining argument (C used at 1:)
    sbrs  R22, 0            ; Skip if 15 bits developed
    rjmp  1b                ; Develop 15 bits of the sqrt

    brcs  4f                ; C--> Last bits always 1
    lsl   R23               ; Need bit 7 in C for cpc
    cpc   R26, R24
    cpc   R27, R25          ; After this C is last bit

4:  adc   R26, R19          ; Round up if C (R19=0)
    mov   R25, R27          ; return in R25:R24 as for avr-gcc ABI
    mov   R24, R26
    ret

.size sqrt32_floor, .-sqrt32_floor

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 einigermaßen 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)

#include <stdint.h>

#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;
}
#endif // __AVR_ENHANCED__

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

#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;
}

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:

• Application Note AVR204: BCD Arithmetics, 8-Bit Binary to 2-digit BCD Conversion

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

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

Beispiele:

• Bin2BCD == 16-bit Binary to BCD conversion in der Macrolibrary Math32 von Andre Birua
• oder auch hier zu finden

Addition von $33

Auch double-dabble genannt. 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 dienen dabei als BCD-Carry-Flag (Halbbyte-Übertrag). Das normale C-Flag wird durch die Additionen nicht beeinflußt, es dient nur dem Schiebevorgang.

Beispiele:

• Application Note AVR204: BCD Arithmetics, 16 Bit Binary to 5-digit BCD conversion
• The AVR Assembler Site: 32 Bit Math
• Der gleiche serielle Algorithmus für Xilinx CPLDs

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

• Part of the Arithmetic Tutorial Collection by Douglas W. Jones

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

• TTL74185 – VHDL-Nachbau des TTL 74185 6-Bit Binär-zu-BCD-Wandlers
• Tutorial Festkommaarithmetik
• AVR-Tutorial: 7-Segment-Anzeige

Sammlungen

• Datei:DataCast.zip (Data Castings) – Sammlung Include-Dateien zum Konvertieren von int zu ASCII-Char, ASCII-HEX oder ASCII-BIN (Assembler)

Diskussionsbeiträge im Forum

• Binär-zu-BCD in VHDL
• ebenfalls VHDL
• 32 Bit in C
• 16 und 32 Bit C und AVR-Assembler
• Assembler für AVR-GCC bis 256 Bit
• 2 hoch x , wenn x kein Integer ist
• schnelle dezimale Division auf AVR & Co.

Sinus und Cosinus

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

Saturierung

→ siehe AVR Arithmetik/Saturierung

Weblinks

• AVR201: Using the AVR Hardware Multiplier (Implementierung und Beispiele)
• AVR201: Using the 8-bit AVR Hardware Multiplier (Application Note, pdf, en)
• Wurzelfunktion
• Optimierte Division durch 10
• Optimierte Division durch 3
• Division durch reziproke Multiplikation, Tutorial
• Math32: Some Useful Assembler Multibyte Maths Subroutines & Macrocalls (oder hier)
• Elm-Chan's Bibliotheken u.a. Arithmetik
• Multiplication by a Fixed Point Constant, Embedded.com, 06/16/09
• M. Rosenblattl, A. Wolf: Fixed Point Library According to ISO/IEC Standard DTR 18037 for Atmel AVR Processors (pdf, engl., 133 S.)
• ISO/IEC DTR 18037 (pdf, engl., 101 S.) – Spezifikation einer Erweiterung von C99 zur Unterstützung von Embedded Systems
• A Different Kind of Multiplication