Routinensammlung und Gewusst-wie für Mikrocontroller

Multiplikation bei Mikrocontrollern

Betrachtet wird hier nur die Ganzzahlmultiplikation.

Grundlagen

Bei der Ganzzahlmultiplikation gilt folgende Regel der Bitbreiten:

Faktor1 * Faktor2 = Produkt
m bit * n bit = (m+n) bit

Im Gegensatz zur Strichrechnung expandiert also stets die Bitbreite.
Hochsprachen verdecken (=verschenken!) diese innewohnende Eigenschaft!

Eine direkte Verarbeitung von Zweierkomplementzahlen ist unzweckmäßig und deshalb selten implementiert (außer bei neueren Controllern); deshalb vorher in Vorzeichen+Betrag umrechnen!

Multiplikation mit [(kleinen) Potenzen von] Zwei

Diese werden durch Linksschieben erledigt. — 1x Linksschieben = Multiplikation mit 2 = Addition mit sich selbst.
Bei neueren Mikrocontrollern ist der Geschwindigkeitsvorteil gegenüber eingebauten Multiplikationsbefehlen bei mehr als einem Bit oftmals dahin!

Vorher ist ggf. ein Byte vorzeichenrichtig „vorn“ anzuhängen. Solange nichts überläuft, braucht ansonsten das Vorzeichen nicht beachtet zu werden, alles bleibt richtig!

µCNeues höchstwertiges Byte/Word bei Zweierkomplement
8051
	mov	C,ACC.7	;a=altes MSB
	subb	a,ACC	;neues MSB
PIC
	clrf	R	;neues MSB
	btfsc	R,7	;R=altes MSB
	 decf	R,f	;neues MSB (0FFh)
ATtiny
ATmega
	add	R,R	;R=altes MSB (wird zerstört)
	sbc	R,R	;neues MSB (0 oder 0FFh)
C166
	movbs	R16,R8	;von 8 auf 16 Bits erweitern
	bmov	C,R16.15	;altes HI-Word MSB nach PSW.1
	subc	R16,R16	;neues HI-Word (0 oder 0FFFFh)
R bezeichnet das jeweilige (MSB- oder NSB-) Register

An der niederwertigsten Bitposition ist eine Null einzuschieben, bei den höherwertigen ist das Übertragsbit einzuschieben. Anstelle von Schiebebefehlen eignet sich auch der Additionsbefehl. Wenn auch nur, um Verwirrung beim blutjungen Kodeleser zu stiften.

µCniedrigstes Bytehöhere Bytes
8051
	clr	C
	rlc	a
	rlc	a
	add	a,ACC
	addc	a,ACC
PIC
	bcf	STATUS,C
	rlf	R,f
	rlf	R,f
ATtiny
ATmega
	lsl	R
	rol	R
	add	R,R
	adc	R,R
C166
	add	R,R
	addc	R,R
	shl	R,#1
R bezeichnet das jeweilige Register

Bei Potenzen von Zwei müssen die o.g. Befehle in einer Schleife ausgeführt werden.

Beachte: Bei Überlauf kommt schlichtweg eine falsche Zahl heraus. Bei Zweierkomplement ist auch das Vorzeichen Glückssache.

Multiplikation mit [Potenzen von] 256 (=28!)

Die Lösung dazu ist derartig trivial, dass sie oft nicht für voll genommen wird: Es wird byteweise „uminterpretiert“, bei gleich bleibender Bitbreite muss hinten ein Null-Byte hinzugesetzt (oder hinzugedacht) werden.

Multiplikation (oder auch Division) mit Wertetabelle

Bei hinreichend kleinem Umfang der infrage kommenden Faktoren (Faustregel: £256) kann eine sog. Look-Up-Table („Schlag-Nach-Tabelle“) Verwendung finden. Der zweite Faktor ist zweckdienlich eine Konstante; somit ist die Tabelle eindimensional. Der Speicherverbrauch: Alle denkbaren Faktoren mal Byte-Breite des Ergebnisses.

Wegen der Verfügbarkeit eingebauter Multiplikationsbefehle und der akzeptablen Geschwindigkeit selbstgeschriebener Routinen kommt die Tabelle für Mikrocontroller so gut wie nie in Betracht!

Für höhere Funktionen, wie Sinus-, insbesondere steil anwachsende Funktionen, wie Quadrat-, Potenz- und Exponentialfunktion, sind Wertetabellen das Mittel der Wahl.

Quadrate lassen sich auch per Multiplikation ermitteln, jedoch sind Wertetabellen für Quadrate oft klein genug.

Hinweis: Lassen Sie sich Tabellen aller Art nach Möglichkeit vom Assembler mittels Wiederholungsanweisungen berechnen! Konstante Tabellen gehören ins Kodesegment.

Multiplikation mit eingebautem Multiplikationsbefehl

Dieser Fall erfordert ggf. das Umwandeln einer Zweierkomplement-Zahl in eine Vorzeichen-Betrags-Darstellung.
Voraussetzung für die Anwendbarkeit des eingebauten Befehls ist seine ausreichende Bitbreite:

µCVerfügbarer MultiplikationsbefehlOperationBitbreiten, Vorzeichen
8051
	mul	ab	
a:b = a * b8*8=16 vorzeichenlos
PIC16nicht vorhanden
PIC17
	mullw	k
PH:PL = w * k8*8=16 vorzeichenlos
	mulwf	f
PH:PL = w * f
ATtinynicht vorhanden
ATmega
	mul	Rd,Rr
R1:R0 = Rd * Rr8*8=16 vorzeichenlos
	muls	Rd,Rr
8*8=16 Zweierkomplement
	mulsu	Rd,Rr
8*8=16 Zweierkomplement (Rd) und vorzeichenlos (Rr)
Weiterhin stehen diese 3 Typen mit anschließendem Linksschieben (*2, fmul, fmuls, fmulsu) zur Verfügung
C166
	mulu	R1,R2
MD = MDH:MDL= R1 * R216*16=32 vorzeichenlos
	mul	R1,R2
16*16=32 Zweierkomplement

Multiplikation breiterer Zahlen mit eingebautem Multiplikationsbefehl

Dieser Fall der Kaskadierung ist bei Mikrocontrollern mit Multiplikationsbefehl dringend anzuraten! Dabei können beide Faktoren beliebig lang sein.

Bitbreiten-Verdopplung

Beispiel (allgemein gehalten, in C-ähnlicher Syntax) für 32-bit-Produkt aus 2 16-bit-Faktoren eines 8-bit-Mikrocontrollers:

Faktor1 * Faktor2 = Produkt
16 bit * 16 bit = 32 bit
a:b * c:d = ((a*c * 256) + a*d + b*c)* 256 + b*d
	p:q=a*c  r:s=b*d
	X:Y=a*d  r+=Y  q+=X+C  p+=C
	X:Y=b*c  r+=Y  q+=X+C  p+=C
a:b, c:d = Faktoren, p:q:r:s = Produkt, X:Y=Zwischen-Produkt, C=Übertrags-Flag

Der angegebene Pseudokode funktioniert auf 16-bit-Mikrocontrollern und PCs ebenso für 64-bit-Produkte.

Bitbreiten-Verdreifachung

24-bit-Register (48-bit-Ergebnisse) sind in Hochsprachen unüblich, jedoch in Assembler vorteilhaft anwendbar.

Faktor1 * Faktor2 = Produkt
24 bit * 24 bit = 48 bit
a:b:c * d:e:f = (((((a*d * 256) + a*e + b*d)* 256) + a*f + b*e + c*d)*256 + b*f + c*e)*256 + c*f
	p:q=a*d  r:s=b*e  t:u=c*f
	X:Y=a*e                r+=Y    q+=X+C  p+=C
	X:Y=b*d                r+=Y    q+=X+C  p+=C
	X:Y=a*f        s+=Y    r+=X+C  q+=C    p+=C
	X:Y=c*d        s+=Y    r+=X+C  q+=C    p+=C
	X:Y=b*f  t+=Y  s+=X+C  r+=C    q+=C    p+=C
	X:Y=c*e  t+=Y  s+=X+C  r+=C    q+=C    p+=C
a:b:c, d:e:f = Faktoren, p:q:r:s:t:u = Produkt, X:Y=Zwischen-Produkt, C=Übertrags-Flag

Um das Durchreichen des Übertragsflags bei der Addition kommt man nicht sinnvoll herum. Insgesamt werden 9 (3x3) Multiplikationen ausgeführt.

Bitbreiten-Vervierfachung

Bei den nun folgenden 16 Multiplikationsbefehlen ist eine Ausführung in Schleifen durchaus naheliegend. Für maximale Geschwindigkeit dennoch hier die „lineare“ Form:

Faktor1 * Faktor2 = Produkt
32 bit * 32 bit = 64 bit
a:b:c:d * e:f:g:h = p:q:r:s:t:u:v:w
p:q=a*e  r:s=b*f  t:u=c*g  v:w=d*h
X:Y=c*h	v+=Y	u+=X+C	Z=C
X:Y=d*g	v+=Y	u+=X+C	Z+=C
			t+=Z	Z=C
X:Y=b*h		u+=Y	t+=X+C	Z+=C
X:Y=d*f		u+=Y	t+=X+C	Z+=C
				s+=Z	Z=C
X:Y=a*h			t+=Y	s+=X+C	Z+=C
X:Y=b*g			t+=Y	s+=X+C	Z+=C
X:Y=c*f			t+=Y	s+=X+C	Z+=C
X:Y=d*e			t+=Y	s+=X+C	Z+=C
					r+=Z	Z=C
X:Y=a*g				s+=Y	r+=X+C	Z+=C
X:Y=c*e				s+=Y	r+=X+C	Z+=C
						q+=Z    Z=C
X:Y=a*f					r+=Y    q+=X+C  Z+=C
X:Y=b*e					r+=Y    q+=X+C  Z+=C
							p+=Z

a:b:c:d, e:f:g:h = Faktoren, p:q:r:s:t:u:v:w = Produkt, X:Y=Zwischen-Produkt, C=Übertrags-Flag, Z=Zwischenregister

Das Zwischenregister Z erspart lange Carry-Propagates und ist insbesondere bei Mikrocontrollern mit wenigen Registern (bspw. 8051) vorteilhaft.

Beim ATmega8 ist das Zwischenregister wenig von Vorteil, man kann es partiell einsetzen, bspw. nur in der Spalte für r, das ergäbe dann:

p:q=a*e  r:s=b*f  t:u=c*g  v:w=d*h
X:Y=c*h	v+=Y	u+=X+C	t+=C	s+=C	Z=C
X:Y=d*g	v+=Y	u+=X+C	t+=C	s+=C	Z+=C
X:Y=b*h		u+=Y	t+=X+C	s+=C	Z+=C
X:Y=d*f		u+=Y	t+=X+C	s+=C	Z+=C
X:Y=a*h			t+=Y	s+=X+C	Z+=C
X:Y=b*g			t+=Y	s+=X+C	Z+=C
X:Y=c*f			t+=Y	s+=X+C	Z+=C
X:Y=d*e			t+=Y	s+=X+C	Z+=C
					r+=Z	q+=C	p+=C
X:Y=a*g				s+=Y	r+=X+C	q+=C	p+=C
X:Y=c*e				s+=Y	r+=X+C	q+=C	p+=C
X:Y=a*f					r+=Y    q+=X+C  p+=C
X:Y=b*e					r+=Y    q+=X+C  p+=C

Das Zwischenregister spart hierbei 12 Takte Ausführungszeit (von 96 Takten).

Multiplikation vorzeichenbehafteter Zahlen

Der übliche Weg ist es, die vorzeichenbehafteten Operanden vorzeichenlos zu machen und das Ergebnis bei Bedarf wieder zu negieren. Aber es geht auch anders, je nach Fall:
  1. Nutzung eines eingebauten vorzeichenbehafteten Multiplikationsbefehls
  2. bei nur einem vzb. Faktor Sonderfall anwenden: a*b = (a+80h)*b - b*80h, (siehe Tabelle)
    hier ist die Unterscheidung zwischen Multiplikand und Multiplikator wichtig, d.h. die Multiplikationsroutine ist nicht kommutativ!
    Es lohnt sich aber nur bei konstanten Faktoren.
  3. Trick (für "vzb lang * vzb lang") siehe unten.
    Lange Faktoren lassen sich nicht mit vzb. Einzeloperationen verarbeiten!

µCvzb * vzlvzb * vzbvzb lang * vzb lang
8051
	add	a,#80h
	mov	B,#k
	mul	ab
	xch	a,B
	sub	a,#k*128
	xch	a,B
	subb	a,#k/2
PIC16
PIC17
	addlw	80h
	mullw	k*2
	movfw	PH
	sublw	k
	movwf	PH
ATtiny
ATmega
	mulsu	Rd,Rr
	muls	Rd,Rr
siehe unten
C166
	add	R1,#8000h
	mov	R2,#k
	mulu	R1,R2
	sub	MPL,#k*8000h
	sbc	MPH,#k/2
	mul	R1,R2

Trick: Getesteter Quelltext für ATmega für Multiplikation "vzb lang * vzb lang"
;Clevere vzb. Multiplikationsroutine:
;PE: r17:r16 = vzb. Faktor 1
;    r19:r18 = vzb. Faktor 2
;    YH = 0
;PA: r5:r4:r3:r2 = vzb. Produkt (30 bit + Vorzeichen)
;VR: r0-r5, r16-r17
;(a+8000h)(b+8000h) = a*b + a*8000h + b*8000h + 40000000h
;		    = a*b + (a+8000h+b)*8000h
;also:
;a*b = (a+8000h)*(b+8000h) - (a+8000h+b)*8000h
imul16x16:	;(getestet)
;Faktor 1 positiv machen
	subi	r17,0x80
;Faktor 2 positiv machen
	subi	r19,0x80
;vzl. multiplizieren (a+8000h)(b+8000h), evtl. Unterprogramm "mul16x16"
	mul	r16,r18
	movw	r3:r2,r1:r0
	mul	r17,r19
	movw	r5:r4,r1:r0
	mul	r17,r18
	add	r3,r0
	adc	r4,r1
	adc	r5,YH
	mul	r16,r19
	add	r3,r0
	adc	r4,r1
	adc	r5,YH
;Ergebnis korrigieren
	clr	r0
	subi	r19,0x80	;"b" zurückwandeln
	add	r16,r18
	adc	r17,r19		;"a+8000h+b"
	sbrc	r19,7		;Wenn "b" positiv,...
	 clc
	ror	r17		;...Überlaufbit einschieben
	ror	r16
	ror	r0		;()*8000h
	sub	r3,r0
	sbc	r4,r16
	sbc	r5,r17		;subtrahieren
;fertig
	ret
Quadrieren ist etwas leichter, u.a. weil das Ergebnis stets positiv ist:
;PE: r17:r16 = vzb. Zahl
;PA: r5:r4:r3:r2 = Quadrat (30 bit)
;VR: r0-r5, r17,r18
;(a+8000h)² = a² + a*10000h + 40000000h
;also:
;a² = (a+8000h)² - a*10000h - 40000000h
iQuadrat16x16:
;man kommt um Betragsbildung doch herum!
	subi	r17,0x80
	ldi	r18,(0x80-0x40)/2
;Quadrieren der vzl. Zahl, evtl. Unterprogramm (für vzl. mit r18=0!)
	mul	r16,r16
	movw	r3:r2,r1:r0
	mul	r17,r17
	movw	r5:r4,r1:r0
	fmul	r17,r16
	rol	r18		;CY retten
	add	r3,r0
	adc	r4,r1
	adc	r5,r18
;Korrektur
	sub	r4,r16
	sbc	r5,r17
;fertig
	ret

Multiplikation mit selbstgeschriebener Routine

Hierbei sind beliebige Bitbreiten realisierbar. Die einfachste Routine multipliziert 8 bit * 8 bit = 16 bit. Selbstgeschriebene Routinen kommen nur für PIC16 und ATtiny, AT90Sxxxx in Betracht!

Die binäre Multiplikation erfolgt genauso wie die schriftliche Multiplikation; durch (bedingte) Addition des (0-oder 1fachen des) linken Faktors und Fortfahren zur nächsten Ziffer von links nach rechts.

Zweierkomplement-Zahlen müssen vorher nichtnegativ gemacht werden; das Vorzeichen des Quotienten ergibt sich aus der XOR-Verknüpfung der höchstwertigen Bits der Faktoren.

Baustelle!

Geplant sind downloadbare Makros für o. g. Mikrocontroller für alle Multiplikationen mit 8-bit- und 16-bit-Faktoren.
8051PICAVRC166
n.v. mult.a16
(universelles Makro für alle Bitbreiten)
n.v.-

Zur Anwendung kommt die Multiplikation zur Skalierung von Messwerten und ähnlicher Aufbereitung von Zahlen.