Multiplikation 16Bit (signiert) mit 8Bit (unsigniert) Assembler ATmega8 ATmega1284P

[Bernhard S. (bernhard)]

Geschätztes Forum,

es sollen 2 Zahlen miteinander multipliziert werden, die 16-Bit Zahl ist 
vorzeichenbehaftet, die 8-Bit zahl ist nicht vorzeichenbehaftet.


Momentan hab ich es durch eine Schleife realisiert:

        ldi R18,LOW (-12) ; TESTZAHL 1.Faktor
        ldi R19,High(-12)
        ldi R20, 5        ; Testzahl 2.Faktor
        clr XL
        clr XH
SCHLEIFE:
  add XL,18
  adc XH,19
  dec R20
  brne SCHLEIFE

Ich suche eine Lösung, die weniger Takte benötigt,

bitte helft mir.


Danke

Bernhard

[Dampfnilp (Gast)]

Die Megas haben glaub einen Hardware Multiplizierer ..

[Marc V. (Firma: Vescomp) (logarithmus)]

Bernhard S. schrieb:
> Ich suche eine Lösung, die weniger Takte benötigt,
>
> bitte helft mir.

 Also 16bit * 8bit passt schon mal nicht in ein Registerpaar (16bit).

 Versuche es hiermit:

.def Mul1 = r2
.def Mul2 = r3
.def Mul3 = r4

        ldi   r18, Low (-12)  ; TESTZAHL 1.Faktor
        ldi   r19, High(-12)
        ldi   r20, 5          ; Testzahl 2.Faktor

;*** Das kannst du als Routine aufrufen, mit RET am ende
mpy8x16:
        mul   r18, r20        ; Low Byte
        movw  Mul1, r0        ; Ergebnis in r2/r3 übernehmen
        mul   r19, r20        ; High Byte
        add   Mul2, r0        ; Addiere Low Byte zu HighByte von vorher
        mov   Mul3, r1        ; Highest Byte einfach übernehmen
        brcc  PC+2            ; Falls bei der vorherigen Addition Übertrag
        inc   Mul3            ; Highest Byte um eins erhohen
;* Wenn als Routine aufgerufen
;       ret

 12 bzw. 13Cycles fur alles, ist das schnell genug ?

 Übrigens, du solltest einzelne register mit Kleinbuchstaben schreiben,
 Registerpaare aber mit Grossbuchstaben, um es etwas lesbarer zu machen
 z.B.
 ldi  r14, 5     ; klein
 ld   r14, X+   ; X gross, weil X in diesem Fall ein Registerpaar ist

[Bernhard S. (bernhard)]

> 12 bzw. 13Cycles fur alles, ist das schnell genug ?


Toll, ich bin begeistert :-)


Was passiert eigentlich bei "brcc  PC+2" wie ist "PC+2" zu verstehen?


Jetzt muss ich ersteinmal über diese Routine nachdenken, was da genau 
passiert.

Danke

Bernhard

[BastiDerBastler (Gast)]

Da er zum Ret springen soll, falls das Carry Bit nicht gesetzt ist, wird 
sich "brcc" vielleicht als "branch carry complement" übersetzen lassen. 
PC+2 soll dann bestimmt Program-Counter+2 heißen und insgesamt springt 
die Instruktion zwei Zeilen vor zum Ret, falls das Carry-Bit nicht 
gesetzt ist.

Aber ist nur eine Theorie, kenne mich nicht aus mit den Teilen...

[Bernhard S. (bernhard)]

>Also 16bit * 8bit passt schon mal nicht in ein Registerpaar (16bit).

Korrekt, ich hätte noch dazu schreiben sollen, dass der Wertebereich des 
Ergebnisses die 16 Bit nicht überschreitet, sorry.

Bernhard

[Marc V. (Firma: Vescomp) (logarithmus)]

Bernhard S. schrieb:
> Was passiert eigentlich bei "brcc  PC+2" wie ist "PC+2" zu verstehen?


 PC ist Abkürzung für Program Counter.

 brcc ist "Branch Carry Clear", also wenn kein Übertrag vorhanden,
 überspringe den nächsten Befehl.

 Nächster Befehl ist 2 Byte breit, deswegen +2.

 Klarer ?

[Johann L. (gjlayde)]

Bernhard S. schrieb:
>>Also 16bit * 8bit passt schon mal nicht in ein Registerpaar (16bit).
>
> Korrekt, ich hätte noch dazu schreiben sollen, dass der Wertebereich des
> Ergebnisses die 16 Bit nicht überschreitet, sorry.

In dem Falle kannst du die letzten 3 Befehle (mov/brcc/inc) weglassen. 
...die sind ohnehin nicht korrekt :-)

[Marc V. (Firma: Vescomp) (logarithmus)]

Johann L. schrieb:
> In dem Falle kannst du die letzten 3 Befehle (mov/brcc/inc) weglassen.
> ...die sind ohnehin nicht korrekt :-)

 Die sind schon korrekt, nur nicht für negative Zahlen, aber:

   a) So hat er das auch in seinem Beispiel gemacht.
   b) Und da in seinem Beispiel das Vorzeichen ausser Acht gelassen
      wurde, habe ich es auch so gemacht.

 AVR kennt auch MULSU.

[Bernhard S. (bernhard)]

> Nächster Befehl ist 2 Byte breit, deswegen +2.

> Klarer ?


Ja, danke.

Möglich wäre natürlich auch:

      brcc mpy8x16_EXIT
      ...
      ...
      ...
mpy8x16_EXIT:
      ret

[c-hater (Gast)]

Bernhard S. schrieb:

> Korrekt, ich hätte noch dazu schreiben sollen, dass der Wertebereich des
> Ergebnisses die 16 Bit nicht überschreitet, sorry.

Dann ist die schnellste Lösung für 16Bit signed*8Bit unsigned:


;->R16:R17: Faktor 1 (16Bit signed)
;  R18    : Faktor 2 (8Bit unsigned)
;<-R17:R16: Produkt
;R2 zerstört, R18 unverändert

  mul R16,R18    ;2
  mov R16,R0     ;1
  mov R2,R1      ;1
  mulsu R17,R18  ;2
  mov R17,R0     ;1
  add R17,R2     ;1
                 ;-
                 ;6

Für die vollen 24Bit sind auch nur zwei Takte mehr erforderlich, dazu 
wären folgende zwei Instruktionen noch an die Routine anzuhängen:

  clr R18        ;1
  adc R18,R1     ;1

Das 24Bit-Ergebnis steht dann in R18::R16.

[Winfried J. (Firma: Nisch-Aufzüge) (winne)]

Last mich raten wenn, Faktor1 signed mit Faktor2 unsigned multipliziert 
wird, dann iat Signum des Produktes = dem Signum von Faktor1 --->

ergo (also)  Singnum von Faktor1  abtrennen  und im Ergebnsregister 
speichern, die absoluten Faktoren multiplizieren und anschließend zum 
Ergebnisregisteraddieren.

 Fertsch

[Maxx (Gast)]

Winfried J. schrieb:
> ergo (also)  Singnum von Faktor1  abtrennen  und im Ergebnsregister
> speichern, die absoluten Faktoren multiplizieren und anschließend zum
> Ergebnisregisteraddieren.

In welchem System hast du ein Signum-Bit und kannst das so 
abtrennen/addieren und welches System meinst du nutzt der TO?

[Winfried J. (Firma: Nisch-Aufzüge) (winne)]

üblicherweise ist das höchstwertige bit das Signum

also

bei einer 16bit integer  das bit 15 diese kann man durch And 0x8000 
bestimmen
um es zwischenzuspeischern, dann Maskieren mit or ox7fff  sodann kann 
man die integer multiplikation mit unsigned ausführen und schließlich 
signum und produkt wieder zusammenfügen mittels  signum OR 
absolutprodukt   da er noch schreibt der werteberieich von 16bit signed 
wird nicht überschritten mußß er nur das highest bit aufbewahren.

[Eric B. (beric)]

Winfried J. schrieb:
> üblicherweise ist das höchstwertige bit das Signum
>
> also
>
> bei einer 16bit integer  das bit 15 diese kann man durch And 0x8000
> bestimmen
> um es zwischenzuspeischern, dann Maskieren mit or ox7fff

Das wird aber nicht zum richtigen Ergebnis führen: 0x7FFF ist eben nicht 
0x0001 (0xFFFF == -1). Da fehlt also noch ein Schritt.

Oh, und maskieren macht man mit AND, nicht mit OR.

[Maxx (Gast)]

Winfried J. schrieb:
> üblicherweise ist das höchstwertige bit das Signum

Üblicherweise eben nicht.
Es gibt zwar bei einigen Systemen z.B. IEEE-754 das Signum aber bei den 
hier üblich diskutierten uCs insbesondere einem AVR greift man bei den 
Registern auf das Zweierkomplement zurück, indem das Vorzeichen in die 
gesammte Bitfolge eingeht.

zwar gilt hier
  signum(z) = -1 genau dann, wenn MSB = 1
  signum(z) = 1 sonst

aber für abs(z) gilt

  abs(z) = z, für signum(z) = 1
  abs(z) = (~z) -1 für signum(z) == -1

(~z) -1 ist offensichtlich nicht z &~ MSB

[Winfried J. (Firma: Nisch-Aufzüge) (winne)]

Es kommt darauf an was du wie maskieren willst. Das Signum mit filterst 
du mit and AND 0x8000, den absoltwert mit AND 0x7fff
Mit OR fügt man beides wieder zusammen. Sollte ich oben was anderes 
geschrieben haben so bitte ich um Verzeihung, bin krank und war in 
Eile...

Namaste

[Winfried J. (Firma: Nisch-Aufzüge) (winne)]

Maxx schrieb:
> aber bei den
> hier üblich diskutierten uCs insbesondere einem AVR greift man bei den
> Registern auf das Zweierkomplement zurück, indem das Vorzeichen in die
> gesammte Bitfolge eingeht.
>
> zwar gilt hier
>   signum(z) = -1 genau dann, wenn MSB = 1
>   signum(z) = 1 sonst
>

holla,

Darüber habe ich noch nie nachgedacht weil mir die bewährte Methode seit 
30 Jahren geläufig ist. Und ich damit seither nicht mehr befassen 
musste. In C denke ich darüber nicht nach, das soll der Compiler machen 
und in ASM benutze ich halt das Format welches mir seit dem 8bit ATARI 
in Fleisch und Blut übergegangen ist. Blöd  wirds wenn man importiert 
oder exportiert und das Format nich beachtet.

Danke dafür, das muss ich mir dann noch mal näher anschauen.

Namaste

[Johann L. (gjlayde)]

Winfried J. schrieb:
> Last mich raten wenn, Faktor1 signed mit Faktor2 unsigned multipliziert
> wird, dann iat Signum des Produktes = dem Signum von Faktor1 --->
>
> ergo (also)  Singnum von Faktor1  abtrennen  und im Ergebnsregister
> speichern, die absoluten Faktoren multiplizieren und anschließend zum
> Ergebnisregisteraddieren.
>
>  Fertsch

Und warum so kompliziert???

1) Bei 16 * 8 = 16 ist das Vorzeichen der 16-Bit Zahl Wurscht.

2) AVR hat wie gesagt dedizierte Befehle für Multiplikation von
  -  Signed * Signed
  -  Signed * Unsigned
  -  Unsigned * Unsigned

--> Kein Bit-Gefrickel erforderlich.

Andererseits ist Bit-Gefrickel für das richtige 
Assembler-Look-and-Feel natürlich unentbehrlich!

[Bernhard S. (bernhard)]

Allen danke ich für die sehr wertvollen Informationen.

Bei Atmel fand ich die AVR201 / AVR201.asm.


Was versteht man eigentlich unter "fractional multiply" ?



Bernhard

[Karl H. (kbuchegg)]

Bernhard S. schrieb:
> Allen danke ich für die sehr wertvollen Informationen.
>
> Bei Atmel fand ich die AVR201 / AVR201.asm.
>
>
> Was versteht man eigentlich unter "fractional multiply" ?

Im Zusammenhang mit der AppNote?

Wenn du im Wirtshaus bist und 7 halbe Bier trinkst, und jede Halbe 3 
Euro kostet, dann hast du 21 Euro für 7 Halbe, bzw. 21 Euro für 3.5 
Liter Bier ausgegeben.

Du willst keine Kommazahlen, weil das kompliziert zu rechnen ist. Also 
nimmst du ein geeignetes Vielfaches. Im Beispiel arbeitest du also nicht 
in ganzen Litern, sondern in halben, weil das die kleinste Einheit ist, 
die du noch berücksichtigen können musst.

[Bernhard S. (bernhard)]

Für die Division von zwei signierten / unsignierten 16-Bit Zahlen habe 
ich einen separaten Thread angelegt.

Beitrag "Division 16-BIT / 32-Bit (signiert) durch 16-Bit (signiert) Assembler ATmega8 ATmega1284P"

Bernhard

[Marc V. (Firma: Vescomp) (logarithmus)]

Karl Heinz schrieb:
> Wenn du im Wirtshaus bist und 7 halbe Bier trinkst, und jede Halbe 3
> Euro kostet, dann hast du 21 Euro für 7 Halbe, bzw. 21 Euro für 3.5
> Liter Bier ausgegeben.

Karl Heinz schrieb:
> Du willst keine Kommazahlen, weil das kompliziert zu rechnen ist.

 Klar, nach 7 Halben.