Zweierkomplement bei Zahlen > 8Bit

[izaseba]

Hallo,
irgendwie steh ich auf dem Schlauch :-(

Meine Mision -> Vorzeichenbehaftetes Multiplizieren von zwei 24 Bit Zahlen.

Meine Lösung sieht so aus,daß ich zuerst beide Zahlen teste, ob da was negatives ist, wenn ja wird ein Zweierkomplement angewendet und entsprechend das Produkt positiv gelassen, oder aber wieder negativ gemacht.

Multipliziert wird dann nur im positivem Bereich.

Soweit klappt es auch sehr gut, ich frage mich aber, ob es nicht einfacher(kürzer) geht.
Vor allem der Zweierkomplement kostet mich zu viel.
bei einer 8 Bit Zahl nimmt man einfach neg und fertig.
Wie geht das bei >8 Bit ?
Eine Kombination aus neg bei LSB und com bei MSB wird ja nicht gehen, weil es ja bei neg ein Überlauf stattfinden könnte, der dann von com nicht mitberechnet wird, oder ?

Ich mache es im Moment so, daß ich alle Bytes mit com 'drehe' und 1 dazuaddiere, wie gesagt, es geht, aber glücklich bin ich damit nicht...

Naja, ich poste mal eben den Ausschnitt, vieleicht sieht jemand noch Optimierungsmöglichkeiten.
Kurze Erklärung zu Registern:
null = 0
full = 0xFF
one = 1
tmp1,tmp2 einfache Wegwerfregister.

Der rest ist eigentlich ausreichend dokumentiert



;************************************************* ******
;* Signedmul24 Bit *
;* Zahl1 MSB r2 r3 r4 LSB *
;* Zahl2 MSB r5 r6 r7 LSB *
;* Rueckgabe MSB r8 r9 r10 r11 LSB *
;************************************************* ******
s_mul24:
rcall vorzeichen_pruefen ;Vorzeichen pruefen und ev. Zahlen positiv machen
clr r8 ;Rueckgabe leeren
clr r9 ;Rueckgabe leeren
clr r10 ;Rueckgabe leeren
clr r11 ;Rueckgabe leeren
clr r12 ;Ueberlaufbyte leeren
s_mul24_1:
cp r7,null ;Testen, ob noch was zu tun ist
cpc r6,null
cpc r5,null
breq s_mul24_3 ;Wenn nicht, Schleife verlassen
lsr r5 ;Multiplikator rechts schieben
ror r6 ;Multiplikator rechts schieben
ror r7 ;Multiplikator rechts schieben
brcc s_mul24_2 ;wenn eine 0 rausgeschoben wurde den naechsten Schritt ueberspringen
add r11,r4 ;Multiplikanten zum Produkt addieren
adc r10,r3 ;Multiplikanten zum Produkt addieren
adc r9,r2 ;Multiplikanten zum Produkt addieren
adc r8,r12 ;Ueberlaufbyte zum Produkt addieren
s_mul24_2:
lsl r4 ;Multiplikanten links schieben
rol r3 ;Multiplikanten links schieben
rol r2 ;Multiplikanten links schieben
rol r12 ;Herausfallende Bits auffangen
rjmp s_mul24_1 ;Weiterrechnen
s_mul24_3:
brtc s_mul23_end;Wenn T Flag gesetzt ist muss das Produkt negativ werden
com r11 ;2-er Komplement
com r10 ;2-er Komplement
com r9 ;2-er Komplement
com r8 ;2-er Komplement
add r11,one ;2-er Komplement
adc r10,null ;2-er Komplement
adc r9,null ;2-er Komplement
adc r8,null ;2-er Komplement
s_mul23_end:
ret ;fertig


;************************************************* ************************
;* wandelt negative Zahlen in positive um *
;*T Flag signalisiert, ob das Ergebnis positiv (0) oder negativ(1) wird *
;************************************************* ************************
vorzeichen_pruefen:
clr tmp1
sbrs r2,7
rjmp vorzeichen_pruefen2 ;Zahl 1 positiv kein Komplement + Flag 0 in tmp1
;Zahl 1 negativ Komplement + Flag 1 in tmp1
com r2
com r3
com r4
add r4,one
adc r3,null
adc r2,null
ser tmp1
vorzeichen_pruefen2:
;Zahl 1 positiv,kein Komplement + Flag 0 in tmp1
clr tmp2
sbrs r5,7
rjmp vorzeichen_pruefen4 ;Zahl 2 positiv kein Komplement + Flag 0 in tmp2
vorzeichen_pruefen3:
;Zahl 2 negativ Komplement + Flag 1 in tmp2
com r5
com r6
com r7
add r7,one
adc r6,null
adc r5,null
ser tmp2
vorzeichen_pruefen4:
;Produkt bekommt positives Vorzeichen T Flag im Status loeschen
clt
eor tmp1,tmp2 ;Pruefe welches Vorzeichen das Produkt bekommt
breq vorzeichen_pruefen5 ;Produkt bekommt positives Vorzeichen
;Produkt bekommt negatives Vorzeichen T Flag im Status setzen
set
vorzeichen_pruefen5:
ret


Gruß Sebastian

P.S. Bevor jemand meint, warum nimmt er nicht mul,
es läuft auf einem Tiny...

[Gock]

Also prinzipiell bin ich recht sicher, dass die Bildung des 2er Kompl auf diese Weise die einfachste Lösung ist. Die Kombination neg und com funktioniert aus genanntem Grund nicht. Kann mir zwar gerade nicht erklären, warum neg nur bei 0x80 das V-Flag setzt, aber das erscheint mir ein Problem.
Deine Variante kann ich jetzt auch nicht weiter optimieren, bin aber auch kein Spezialist.
Gruß

[fumir]

ich hab mir mal nen alten professionellen z80 code angeschaut. die haben das auch so gemacht (erst vorzeichen behandeln, dann multiplizieren) also gehts wohl so am besten.

an den details kann man sicher noch etwas schrauben. z.b. ists nicht nötig immer r5,r6 und r7 gemeinsam zu shiften. nach 8 shifts hast du ja nur das eine register in ein anderes kopiert.
ich vermute, das 2er komplement könnte man einfacher berechnen, aber da müste ich mich jetzt richtig reinknien.

[Besserwessi]

Eventuell man Atmel Application Note 222 anschauen, da steht was über die Multiplicationen mit dem Hardware Multipier (Megaxxx). Wenn es auf Geschwindigkeit ankommt ist hier ein Tinyxx nicht die beste Wahl.

[PicNick]

Denke auch, dass zumindest mal das 2-er kompl so am besten ist.
Du könntest zwar auf die ADC's der oberen Register verzichten, wenn Bit 0 nach der 1-addition =1 ist (kein überlauf) aber ein if-jump sind ja auch 3-cycles, also bringt das nix (Erst, wenn die Zahlen deutlich länger werden zB 64 Bit).

Ich würde nur raten, die Zahlen mit Pointer anzusprechen, damit du nicht alle routinen mehrfach hast. Das kostet zwar im Moment, aber wenn du deine Mathe-Lib noch ausbaust, wirst du froh sein. (ein pointer auf einem Tiny is ja nur ein byte)

[Besserwessi]

Das 2 er Komplement geht noch etwas kürzer:
Für das Addieren von eins gibt es als Alternative das Abziehen von 0xFF. Dafür gibt es den SUBI bzw SBCI Befehl. Außerdem kann man für das low byte den NEG Befehl nehmen und nur noch die hoheren Bytes per SBCI 0xFF korrigieren. Bei einigen Prozessoren gibt es auch noch ein SBCWI um gleich 2 Register zusammen zu bearbeiten, spart aber nicht viel.

(Ist nicht auf meinem Mist gewachsen, war geraden eine Frage bei ARVFREAKS (englisch)):
http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&t=59526

[PicNick]

..für das low byte den NEG Befehl nehmen ..
Da ist aber die Sache mit 0x80, die stört in diesem Fall.

[Gock]

@Besserwessi
Du sparst aber nichts, wenn Du addierst statt subtrahierst.
Gruß

[izaseba]

Danke für Eure Antworten,

gut zu wissen, daß es doch nicht einfacher geht, bin doch nicht ganz bala bala ;.)



z.b. ists nicht nötig immer r5,r6 und r7 gemeinsam zu shiften. nach 8 shifts hast du ja nur das eine register in ein anderes kopiert.

Das ist zwar richtig, ich will aber wissen, was rechts aus dem Low Register rausfällt, oder verstehe ich Dich jetzt falsch ?



Wenn es auf Geschwindigkeit ankommt ist hier ein Tinyxx nicht die beste Wahl.

Ja ich weiß, es kommt aber nicht auf die Geschwindigkeit an sondern eher Speicherverbrauch und Tiny und kein Mega, wegen Platzmangel...



Ich würde nur raten, die Zahlen mit Pointer anzusprechen, damit du nicht alle routinen mehrfach hast. Das kostet zwar im Moment, aber wenn du deine Mathe-Lib noch ausbaust, wirst du froh sein. (ein pointer auf einem Tiny is ja nur ein byte)

Das hört sich nicht schlecht an...
Ich muß das mal überdenken, versteh nicht ganz :oops:
Könntest Du bitte etwas genauer werden ?

Gruß Sebastian

[PicNick]

etwas genauer
Gern.
Die Register kannst du genauso über XYZ Pointer addressieren wie den ganzen SRAM
z.b du hast eine Funktion "SignCheck" wie oben. du lädst X mit der Adresse vom R2 und rufst sie mit Call. Die Funktion verwurstelt immer die 4 Byte vom Pointer aufwärts. Das braucht mehr code, stimmt.
aaaaaber
Die gleiche Funktion kann aber sofort jedes beliebige 32-Bit Feld auf Vorzeichen prüfen (oder rotieren oder sonstwas)

Ein wenig System braucht man der der Registerverteilung natürlich schon. Beim TINY sind ja die ressourcen knapp

Man kann aber strukturierter arbeiten, objekt-orientierter Assembler++,
gewissermassen

Vielleicht sollt' ich an deinen funktionen ein konkretes Konzept darlegen, damit du besser weisst, was ich mein.

[izaseba]

Hallo PicNick,

Ich glaube ich verstehe Dich...

SignCheck bekommt in einem Pointerregister die Adresse von MSB in meinem Fall SRAM 0x01 für r2.

Weiter schaut sie,ob Bit 7 gesetzt ist, wenn ja macht sie ein komplement(hier muß sie aber wissen, wie Breit meine Zahl ist) und signalisiert z.B. mit dem T Flag, daß ein Vorzeichenwechsel stattgefunden hat und kehrt mit ret zurück.
Dann muß ich mir noch merken, ob T gesetzt ist und die SignCheck zum zweitem mal aufrufen diesmal mit der Adresse von r5 im Zeigerregister.
Nach dem Multiplizieren könnte ich dann nach Bedarf die Adresse vom Produkt an die Funktion übergeben um das Produkt umzudrehen.
Allerdings springe ich dann nicht in SignCheck, sondern ein paar Zeilen tiefer( nach dem Bit 7 test) rein.
Die Anzahl der Bytes könnte man mit einem Universalregister übergeben...

Hmmm, so in etwa ?

Am sonsten freue ich mich natürlich über jedes konkrete Konzept.

Gruß Sebastian

[PicNick]

Ja, genau so in der Art.
Überlegungen dazu:
Speicherst du Little-Endian, kannst du leicht die gleichen Funktionen für verschiedene Bit-Anzahlen verwenden,
Bei Big-Endian wiederum ist immer das Vorzeichen an der gleichen (relativen) Stelle
Soll das ganze richtig brummen, wär noch zu überlegen, die Variablen überhaupt "aligned" abzulegen, dann ist das byte-offset immer direkt in den zwei low-Bits der adresse (32-Bit)
Wiederum andererseits kannst du dir bei Floats ja auch das Format aussuchen, also die Mantissa vorn oder hinten, wie's besser passt

Ein bißchen auf einem Zettel rumhirnen vor dem Codieren zahlt sich sicher aus.

Noch eine böse Variante fällt mir ein: Die kannst die Bytes einer aktuellen Variablen einfach auf den Stack pushen, und die Funktion popt sie sich dort runter oder rechnet direkt im Stack, is ja auch nur Sram

[izaseba]

Hallo PicNick,

Danke für die Anregungen, es ist wirklich sehr interessant, sich die Möglichkeiten anzuschauen,
Die Sache mit Parameterübergabe über Stack ist auch ganz nett, ich glaub auf dem PC wird es ja so gemacht.
Bei einem gebe ich Dir vollkommen recht


Ein bißchen auf einem Zettel rumhirnen vor dem Codieren zahlt sich sicher aus.


Ich habe mir schon genug Gedanken zu der Funktion gemacht und immer geguckt, daß das Ergebnis, so von der Funktion zurückgeliefert wird, daß ich es direkt an die nächste Funktion reichen kann, ohne die Register umsortieren zu müssen.

So wird nur am Anfang was von Ram geholt durch mehrere Funktionen durchgejagt, und zum Schluß das Ergebnis wieder im Ram geschreiben.

Nicht gerade einfach zu lesen, spart aber Ram.

Gruß Sebastian

[Besserwessi]

@PicNick:
Das Problem it dem $80 tritt beim low byte selber nicht auf, den fast immer auftretenden Überlauf kriet man ja mit, man muß halt danach das Carry flag mitnehmen und nicht erst mit ADD anfangen.

NEG A
sollte in der Wirkung vollkommen identisch mit den beiden Befehlen
COM A
SUBI A,0xFF
sein, unabhängig in welchem Zusammenhang.
Außer es kommt eine schlechte ISR-routine dazwischen, aber das will ja keiner.


@Gock:
Man spart durch das Subtrahieren schon etwas, man braucht die register mit 0 und 1 nicht, wenn man mit den oberen Registern abbeitet. MIt den unteren registern spart man tatsächlich nichts.

[izaseba]

Hallo Besserwessi,


Man spart durch das Subtrahieren schon etwas, man braucht die register mit 0 und 1 nicht, wenn man mit den oberen Registern abbeitet. MIt den unteren registern spart man tatsächlich nichts.


Das Problem bei der Sache ist aber, daß Du bei subi register,-1 einen Überlauf bekommst(Carry), womit ein nachfolgender sbci ziemlich in die Hose geht.
Außerdem sind die oberen Register zu wertvoll um damit Bitbang in Massen zu machen :lol:

Gruß Sebastian

[Besserwessi]

Ob man lieber die oberen Register benutzt oder 2 zusätzliche von den unteren, hängt davon ab was man sonst noch im Programm macht. Da haben beiden Lösungen ihre Berechtigung. Dabei hat auch da das abzeihen von -1 wieder einen kleinen Vorteil, denn man braucht nur ein konstantes Register mit 255, statt 0 und 1.

Das mit dem Carry Flag ist kein Problem, sondern nötig, damit es funktioniert. Man muss nur für die Ganze Zahl -1 abziehen.
Um mit +1 zu arbeiten sollte das carry flag gerade falsch sein.

Die Methode mit subi / sbci wird übrigens auch von Atmel in der Aplication NOTE 200 benutzt. Die Abkürzung einmal com subi durch neg zu ersetzen allerdings noch nicht.