Hallo Besucher, der Thread wurde 8,6k mal aufgerufen und enthält 27 Antworten

letzter Beitrag von JeeK am

Dividieren in Assembler

    Aus aktuellem Anlass hier ein paar Routinen zum Unsigned-Integer-Dividieren in Assembler. Wer sie gebrauchen kann, soll glücklich damit werden.


    Zitat von Endurion

    Schon heftig, was man unter heutigen Prozessoren mit einem DIV erschlägt.


    Naja, schon der MC-68k hatte den DIV Befehl, aber man ist ihn, wenn möglich, umgangen, weil er sehr viele Taktzyklen verbrauchte, die woanders besser aufgehoben waren.

    Zitat von Mac Bacon

    Aus aktuellem Anlass hier ein paar Routinen zum Unsigned-Integer-Dividieren in Assembler. Wer sie gebrauchen kann, soll glücklich damit werden.


    Was war der "aktuelle" Anlass? - Das ist mir irgendwie entgangen :zzz:


    In der 16/16-Variante ist die Initialisierung des Remainders ziemlich geschickt gelöst. Da kann man dann auch mit der 17-Durchlauf-Lösung (welche etwas unschön wirkt) leben. ;)

    Zitat von Endurion

    Schon heftig, was man unter heutigen Prozessoren mit einem DIV erschlägt

    Naja, in Hardware sind natürlich gewisse Optimierungen möglich, so könnte man z.B. bei geeigneten Zahlen die Anzahl der Durchläufe verringern. Außerdem wird intern gerne ein doppelt langes Register zum Shiften benutzt.

    Zitat von JeeK

    Was war der "aktuelle" Anlass? - Das ist mir irgendwie entgangen :zzz:

    Der aktuelle Anlass zum Posten war ein Gespräch in der Shoutbox. ;) Aber die Routinen (bzw. ähnliche) liegen schon seit Ewigkeiten herum - und hätten eigentlich schon längst in die ACME-Lib wandern sollen.

    Zitat von JeeK

    In der 16/16-Variante ist die Initialisierung des Remainders ziemlich geschickt gelöst. Da kann man dann auch mit der 17-Durchlauf-Lösung (welche etwas unschön wirkt) leben. ;)

    Danke. Durch den Einsprung an das Ende der Schleife (eine meiner Lieblings-Optimierungen) zählt der erste Durchgang ja eh gar nicht richtig. ;)


    Übrigens, eine recht einfache Optimierung dieser Routinen besteht darin, die SBC-Befehle mit Immediate-Adressierung zu benutzen, den Nenner also direkt im Argument zu speichern. Für die anderen Variablen empfehle ich aus Geschwindigkeitsgründen ZP-Adressen, z.B. im FAC1 oder FAC2.


    Hausaufgabe: Findet heraus, was beim Teilen durch Null passiert. :D

    Im Idealfall kommt bei Teilung durch 0 eben eine 0 heraus (Compiler und Interpreter warnen noch davor...). Zumindest möchte ich als Techniker das so sehen.
    Dummerweise habe ich in der Praxis irgendeinen Wert als Ergebnis.


    Und so kam es.
    Man fährt ne Papiermaschine herunter bis zum Stillstand. Für die genaue Geschwindigkeit sind in den Antrieben noch ein paar Berechnungen definiert (Walzendurchmesser, Getriebeübersetzungen, ratio...).
    Kurz vorm Stillstand gibt das Obersieb noch mal vollgas...Division by Zero.
    Hat das Obersieb natürlich nicht überlebt. 16k Euro Schaden.

    Mir ging es eigentlich eher darum, was die obigen Routinen bei Nenner = 0 ausgeben, denn dieser Fall wird ja nicht abgefragt. Der Grund: Oftmals braucht man keine allgemeine Divisions-Routine, sondern eine mit festem Nenner (z.B. 10 für Dezimalausgaben, oder 60 für Minuten/Sekunden-Umrechnungen) - da ist der Test dann eh unnötig. Benutzt man die Routinen wirklich für allgemeine Zwecke, sollte man natürlich vor der Rechnung auf Nenner = 0 prüfen und dann das Passende tun... :whistling:

    Zitat von Fröhn

    Hätten die Entwickler damals ein "division by zero" Flag in die CPUs reingebaut, und keine Exception dafür :)


    Da wär so mancher Unfall nicht passiert.


    Das kann man glaub ich generell so nicht sagen. Selbst wenn es so etwas gegeben hätte, wäre dadurch ja auch nicht garantiert, dass die Entwickler dann damit eine Anlage korrekt weiter steuern (Exception Routine wird zwar angesprungen, aber z.B. ein Antrieb läuft weiter und halt dann irgendwo dagegen). Will sagen, dass der gleiche Programmierer die korrekte Exceptionbehandlung oder das Db0-Flag genauso "übersehen" hätte, wie er die 0-Division als solche übersehen hat ...


    Egal wie viel tolle "Unterstützung" eine Prozessor-Architektur auch haben mag, um den Programmierer zu unterstützen, es werden dann eben andere Fehler auf einer anderen "Ebene" gemacht. Es verlagert sich nur irgendwie. Ein Teil des Problems ist, dass Echtzeit- und Embedded-System-Programmierung mit gänzlich anderen Anforderungen und Methoden manchmal (das ist dann schon zuviel) von Entwickler und Software-Ingenieuren für "kommerzielle" und GUI-Software betrieben wird. :(

    Zitat von Mac Bacon

    Mir ging es eigentlich eher darum, was die obigen Routinen bei Nenner = 0 ausgeben, denn dieser Fall wird ja nicht abgefragt. Der Grund: Oftmals braucht man keine allgemeine Divisions-Routine, sondern eine mit festem Nenner (z.B. 10 für Dezimalausgaben, oder 60 für Minuten/Sekunden-Umrechnungen) - da ist der Test dann eh unnötig. Benutzt man die Routinen wirklich für allgemeine Zwecke, sollte man natürlich vor der Rechnung auf Nenner = 0 prüfen und dann das Passende tun... :whistling:


    Für solche "Spezialfälle" verwendet man dann aber auch nicht eine allgemeine Divisionsroutine, sondern versucht das dann möglichst auf eine feste Abfolge von Schiebeoperationen und Subtraktionen zu reduzieren ... ;)


    Wenn so eine Routine in eine Library aufgenommen soll, dann muss aber schon der gesamte Zahlenumfang in einer definierten Weise abgedeckt sein und es muss dokumentiert sein, was in Extremsituationen passiert. Nicht unüblich ist bei Integer-Arithmetiken, dass bei /0 das Ergebnis und der Rest (im unsigned Fall) jeweils auf $FFFF gesetzt sind.

    Zitat von Mac Bacon

    Aus aktuellem Anlass hier ein paar Routinen zum Unsigned-Integer-Dividieren in Assembler. Wer sie gebrauchen kann, soll glücklich damit werden.

    [..]



    Mit dieser 16u/8u-Routine von den beiden wird man eher nicht glücklich, denn sie einen Bug. Ich beschäftige mich schon länger, aber erst nach meinem letzten Post intensiver mit Divisionsroutinen (speziell in Forth-Implementierungen) und da ist mir das erst jetzt aufgefallen bzw. hatte die Muße, mich da durchzuarbeiten und ein umfängliches Posting zu erstellen (das hoffentlich nicht selbst wieder Fehler aufweist).


    Beispiel, wo es nicht funktioniert:


    $8765 : $C0


    Siehe dazu das Trace aus einer VICE-Sitzung bis zu jener Stelle, wo der Fehler auftritt.

    trace.txt


    Bei $c0ef hat der Remainder bereits den Wert $87, wo beim vorigen Durchlauf Denominator ($C0) noch nicht hineingepasst hat. Dadurch, dass das höchstwertige Bit nun herausgeschoben wird und das 9. Bit verloren geht, kann hier nicht vom eigentlichen Wert, nämlich $10E, nicht abgezogen werden. Das hätte nur funktioniert, wenn im vorigen Durchlauf ein Wert im Bereich von $60 bis $7F gekommen wäre, denn dieser würd nach dem Verschieben größer gleich $C0 werden und innerhalb der 8 Bits bleiben.


    Ab hier stimmt es dann nicht mehr, der Quotient wird zu klein und Rest stimmt auch nicht mehr.




    Behebung:


    1. Beim Verschieben des Remainders muss das Carry-Flag überprüft werden. Dann ist der Remainder-Wert auf jeden Fall größer und kann ohne Vergleich direkt um den Denominator reduziert werden.
    2. Die Subtraktion im Remainder passiert dann nicht vor der Denominatorabfrage, sondern nachher, damit dies in beiden Fällen verwendet werden kann.
      Aber Achtung: je nach Einsprung, ist hier nicht mehr sichergestellt, dass das Carry-Flag 1 ist. Daher nach dem SBC das überflüssig aussehende SEC. Im Überlauffall, wenn also von einem 9-Bit-Wert subtrahiert werden müsste, kann man auf das 9. Bit allerdings verzichten und die Subtraktion einfach bei 8 Bit belassen, da ja das Ergebnis immer kleiner $100 wird. In diesem Fall ist allerdings dann auch das Carry-Flag gelöscht (d.h. von dieser Annahme kann im folgenden nicht mehr ausgegangen werden).


    Nebenbei wurde auch insofern optimiert, dass der Remainder nicht relativ aufwendig im X-Register gehalten wird, nur weil man den Wert der Subtraktion erhalten will. Da ist es billiger, gleich den Akku zu nehmen und die Denominator-Subtraktion nur mit einem CMP zu machen, ohne den Akku zu ändern und dann erst mit einem SBC den Remainder zu bereichnen. Das ist in allen Fällen schneller, da man im Hauptpfad 3 Befehle (6 Zyklen) spart und das zusätzliche SBC (bei der Zeropage) 3 Zyklen kostet.

    Man spart sogar ein Byte des Codes ein, obwohl die Sonderbehandlung hinzu gekommen ist.



    Eine Variante ist auch das Dividieren von 16 Bit durch 8 Bit mit "kurzem" Ergebnis in nur 8 Bit.

    Das hat allerdings den Nachteil, dass hier ein Überlauf eintritt, sobald das High-Byte des Nominators größer als der Denominator ist.

    Hier ein Beispiel:


    Ein Overflow wird abgefragt und verlässt die Routine sofort (man könnte hier auch bestimmte Werte setzen, um den Zustand dem Aufrufer erkennbar zu machen.


    Hier wird der wird das höhere Byte des Nominators gleich als Remainder verwendet (und im Akku gehalten, wird aber nicht zurückgespeichert). Da das Ergebnis auch nur 8 Bit hat, braucht man auch nur 8 Durchläufe (ein 9. "halber" Durchlauf erspart man sich hier mit dem vorgezogenen "asl" zu Beginn, da ja der Remainder nur aus einem Byte besteht und ein "bne ..." genau so viel Platz brauchen würde.


    Möge der 6502 mit euch sein! ;)

    Zitat von daybyter

    Machst Du nur Forth auf dem 6502 ? Oder bist Du auch an anderen CPUs interessiert?

    Auch auf

    Da ich immer gerne die Implementierungen Vergleiche, kenn ich auch die eine oder andere Implementierung von 6800, 68K. Von Z80 oder 8080 eher nur die Grundlagen (also wie dort der innere Interpreter aufgebaut ist).

    Sorry fürs offtopic.:/

    Zitat von JeeK

    Da ich immer gerne die Implementierungen Vergleiche, kenn ich auch die eine oder andere Implementierung von 6800, 68K. Von Z80 oder 8080 eher nur die Grundlagen (also wie dort der innere Interpreter aufgebaut ist).

    Kennst Du zufällig einen guten, kompakten und ausreichend kommentierten Sourcecode für einen 68000-Forth-Interpreter? Sowas könnte ich für meine CPU als Grundlage gut gebrauchen (68000 kommt dieser am nächsten).