DEC Attack: Die kleine Problem-Ecke

Es gibt 88 Antworten in diesem Thema, welches 11.662 mal aufgerufen wurde. Der letzte Beitrag (5. Mai 2024 um 22:32) ist von goloMAK.

  • Also wenn man 0 - 255 auf 0-39 ist das skaliert /256*40

    /256 ist ja in Fixpunktdarstellung <highbyte>.<lowbyte>

    Multipliziert man lowbyte mit 40 (= 5*8), hat man im highbyte das skalierte Ergebnis stehen.

    Erst wird mit 5 (%101) multipliziert (das ist Wert addieren bzw. erstmals übernehmen, shift ohne addieren und shift mit addieren).

    Mal 8 ist dann nur noch 3x Shift.

    In res+1 steht dann das Ergebnis.

    Das letzte "sta res" kann man sich freilich schenken, wenn man nur res+1 als ergebnis braucht.

  • Noch eine Idee war, den BIT-Befehl zu benutzen, um einen Takt in einem Fall zu sparen:
    12 Bytes und 14 bzw. 15 Zyklen

    Obwohl ich mit 6502 Opcodes wenig am Hut habe, habe ich intuitiv nach einem TEST BIT Opcode gesucht.

    Das ist wohl einer der wichtigsten Befehle auf einer CPU.

    Wem ein leeres EPROM fehlt, braucht ein EPROM-Lösch-Gerät

    Mein GitHub: Bitte melde dich an, um diesen Link zu sehen.
    EasyFlash3 DIY: Bitte melde dich an, um diesen Link zu sehen.

    Mein Discogs: Bitte melde dich an, um diesen Link zu sehen.

  • Man kann also sagen, dass der C64 ein 16bit-Word so schnell durch 256 teilen kann, dass ihn darin kein Super-, Quanten- und Hast-nicht-gesehen-Computer schlagen kann. 8)

    Was heißt eigtl. "DEC-Attack"? :gruebel

    Demnächst werde ich also das Problem haben, die Länge einer Zahl zu bestimmen:

    Es liegt eine 16bit-Zahl vor, sagen wir in A/X. In Y wird die entsprechende (Dezimal-ASCII-) Länge der Zahl gebraucht, also ab $0000 1, ab $000a 2, ab $0064 3, usw., d.h. ein Wert von 1 bis 5.

    Taktzyklen sind Wurscht, ROM-Routinen tabu, und die Anzahl Bytes soll minimal sein. Offenbar gibt es da ganz verschiedene Möglichkeiten.

  • Es liegt eine 16bit-Zahl vor, sagen wir in A/X. In Y wird die entsprechende (Dezimal-ASCII-) Länge der Zahl gebraucht, also ab $0000 1, ab $000a 2, ab $0064 3, usw., d.h. ein Wert von 1 bis 5.

    Taktzyklen sind Wurscht, ROM-Routinen tabu, und die Anzahl Bytes soll minimal sein. Offenbar gibt es da ganz verschiedene Möglichkeiten.


    Ein erster Ansatz:

    Größe: 13 +10 = 23 Bytes
    +2 Bytes, falls die Tabelle nicht in der Zero-Page liegen = 25 Bytes

  • Ein erster Ansatz:

    Der Ansatz ist gut - nur leider funktioniert der Code so noch nicht.

    Zum einen gibt es keinen cpx,y Befehl (und auch keinen für die Zeropage), zum anderen werden einstellige Zahlen nicht korrekt abgehandelt.

    Hier meine (mit 31 Bytes entsprechend längere) Version Deines Ansatzes:

  • Ein erster Ansatz:

    Der Ansatz ist gut - nur leider funktioniert der Code so noch nicht.

    Zum einen gibt es keinen cpx,y Befehl (und auch keinen für die Zeropage), zum anderen werden einstellige Zahlen nicht korrekt abgehandelt.


    ( Wieder ein peinlicher Fehler meinerseits ;)
    Den Fehler bzgl. einstelliger Zahlen, kann ich gerade nicht erkennen. )

    Zum ersten Punkt hätte ich selbstmodifizierenden Code genutzt:
    19 (bzw. 21, falls Code nicht in ZP) + 10 Bytes
    (+1 rts)

    Voraussetzung ist, dass tabhi nicht an einer page Grenze gebrochen wird, so dass zur Selbstmod. nur das lo-byte von addr berücksichtigt werden muss.


    edit: ich wollte eig. schreiben "kürzer", was aber nicht stimmt. Ich erkenne sogar, dass Deine Version anscheindend besser/kürzer ist.

  • Wow, 5ace und YPS, Ihr habt ja im Grunde schon die Lösung.

    Mir fällt dazu im Augenblick auch nichts anderes ein, außer einfach mal wieder zu schnorren und aufgrund eurer Vorarbeit das ganze minimal zu verkürzen:

  • wow, das sieht doch schon gut aus. btw .. A/X müsste es nicht unbedingt sein (sry :/). Die Zahl liegt real halt als 16bit-Zahl in $62/$63 ($62=Hi, $63=Lo, weil FAC). Zerstört werden dürfen die beiden Bytes auch. Mit Code oder Tabellen in der Zp ist es so eine Sache, denn das muss man ja da erst mal hinschicken, was auch wieder Code braucht.

  • Anbei mal eine Idee von mir, wie man es machen koennte.

    MfG

    Claus

    "Wer einen Fehler begangen hat und ihn nicht korrigiert, begeht einen weiteren Fehler."

    (aus den Lehren des Konfuzius)

    Mein GitHub: Bitte melde dich an, um diesen Link zu sehen.

  • Hier ist nochmal ein anderer Ansatz ohne Tabelle. Es wird immer durch 10 dividiert und y hochgezählt bis das Ergebnis 0 ist. Aber es ist etwas länger als die Tabellenversion:

  • Ich hatte parallel zu Mafiosino und 5ace meine Routine aufgebaut, im nachhinein habe ich gesehen, das sein Ansatz richtig ist.

    Hier nochmal eine Version, eingekuerzt basierend auf der Idee von Mafiosino und 5ace mit Tabelle.

    MfG

    Claus

    "Wer einen Fehler begangen hat und ihn nicht korrigiert, begeht einen weiteren Fehler."

    (aus den Lehren des Konfuzius)

    Mein GitHub: Bitte melde dich an, um diesen Link zu sehen.

  • Was heißt eigtl. "DEC-Attack"? :gruebel

    Ist das Pendant zu "Snack Attack", also quasi der kleine Assembler-Problemhappen für zwischendurch. :)

    Bitte melde dich an, um diesen Link zu sehen. - Ratespiel • Bitte melde dich an, um diesen Link zu sehen. - BASIC-Erweiterung • Bitte melde dich an, um diesen Link zu sehen. - Sprite-Editor • Bitte melde dich an, um diesen Link zu sehen. - Zeichensatz-Editor Bitte melde dich an, um diesen Link zu sehen. - 2048 Blöcke

  • hehe, mit ohne Tabelle hab ich gerade auch probiert, waren aber auch ein paar Bytes mehr als mit Tabelle.

    Ich hab mich also für die Tabellenversion entschieden und diese lediglich so geändert, dass ein Einstiegszustand von Y = 0 ausgenutzt wird. Der Grenzwert $0000 fällt weg; dafür kommt ein BEQ hinzu.

    Im BASIC-ROM gibt es eine ähnliche Tabelle, aber für dieses Problem eher unbrauchbar, würde ich sagen.

  • Alles sehr schöne Optimierungen, Lösungen und Ideen!

    Ich habe einwenig Zeit gebraucht, um die folgende Abfolge nachzuvollziehen:

    atomcode Jetzt verstehe ich auch, warum die Werte in der Tabelle bei Dir um eins verringert sind. Du hast die Vergleiche umgekehrt, d.h. die Tabelle wird gegen den Wert geprüft.

  • Ich hab mich also für die Tabellenversion entschieden und diese lediglich so geändert, dass ein Einstiegszustand von Y = 0 ausgenutzt wird. Der Grenzwert $0000 fällt weg; dafür kommt ein BEQ hinzu.

    Saubere Loesung!

    5ace ,

    gut erklaert, ich hatte auch ein bischen geraetselt wie das ganze funktioniert.


    MfG

    Claus

    "Wer einen Fehler begangen hat und ihn nicht korrigiert, begeht einen weiteren Fehler."

    (aus den Lehren des Konfuzius)

    Mein GitHub: Bitte melde dich an, um diesen Link zu sehen.

  • Nachfolgend noch eine sehr primitive Idee, weil es hieß, dass die Geschwindigkeit unwichtig ist.

    Die Idee ist:

    • Es gibt eine Schleife:
      • Die binäre 16-Bit Eingabezahl (Variablennamen lo/hi), wird heruntergezählt. Falls 0 erreicht wird, wird die Schleife abgebrochen
      • Eine BCD Zahl (Variablenname ist "digits"), welche sich über 3 Bytes erstreckt, wird in jedem Schritt der Schelife um 1 erhöht.
    • Sobald die Schleife verlassen wird, wird die Nutzung der einzelnen Nibbles geprüft und y (= das Resultat) entsprechend gesetzt.

    ----

    Hier ist nichts optimiert und evtl. muss noch eine Addition am Ende erfolgen (?).
    Optimieren kann man mit Sicherheit einige Stellen:

    1. Beim Herunterzählen die Register statt lo/hi nutzen.
    2. Die Schleife lässt sicherlich umformen.
    3. Das Ein-/Ausschalten des BCD Modus ist sehr wahrscheinlich überflüssig.
    4. Das Prüfen der genutzten Ziffern/Nibbles lässt sich bestimmt eleganter lösen.


    Noch zur Info:

    "16-Bit Decrement and test for zero" stammt von der Seite Bitte melde dich an, um diesen Link zu sehen.

  • Einige Ideen zur Optimierung bzw. andere Vorgehensweise beim Prüfen der genutzten Ziffern:

  • Danke! Aber sooo unwichtig ist die Geschwindigkeit dann doch wieder nicht. :D

    Weil man sonst ja auch wieder die lahmen ROM-Routinen dafür einsetzen könnte, was auf jeden Fall das kürzeste ist:

    Code
            ldx #$90             ; Wert für FACexp (Exp=16)
            sec                  ; C=1: Mantisse nicht invertieren
            jsr $bc49            ; Integer nach Fließkomma wandeln
            jsr $bdec            ; FAC nach ASCII wandeln => Zahl 0-terminiert ab $100
            tay                  ; Y auf 0
        -   lda $0100, y         ; Ziffern vom Stackboden auslesen
            beq +                ; Stringterminator: Länge der Zahl in Y
            iny
            bpl -                ; nächste Stelle (jmp)
        +
  • Der letzte Beitrag von 5ace hatte mich auf eine Idee gebracht, und zwar, die kurze und schnelle Lösung mit der Tabelle wieder zu verwerfen. :D Grundsätzlich ist die natürlich gut. Ich brauchte so was ja, weil die vorherige Methode (siehe Bitte melde dich an, um diesen Link zu sehen.) sehr langsam ist und ich (in Pass 1 vom Renumber) noch nicht die Zahl selbst, sondern nur ihre Länge brauchte.

    Bei dem Test-Listing von goloMAK hatte die Tab-Version 7 Sek. rausgehauen, was tatsächlich sehr viel ist (ganze 35%, wenn man die Zeilensuchschleife schon wegdenkt).

    Aber dann hatte ich mir eben überlegt, ob man die ROM-Routinen aus Bitte melde dich an, um diesen Link zu sehen. nicht ganz verwerfen könnte, indem man wieder jedes Mal (also auch in Pass 1) die Zahl berechnet, aber dies eben handgestrickt.

    Bilanz:

    Die Längen-Berechnung mit der Tabelle benötigte 24 Byte und brachte 7 Sek. Zeitersparnis.

    Die Zahlen-Berechnung mit den ROM-Routinen (Bitte melde dich an, um diesen Link zu sehen.) benötigt vollständig auch 24 Byte.

    Die neue Version, die die Zahlen und ihre Länge berechnet und somit wieder für beide Durchläufe reicht, ist so lang wie die anderen beiden zusammen (48 Byte), spart aber 10 Sek. (=50%).

    Die braucht zwar deutlich mehr Taktzyklen als die pure Längen-Berechnung mit der Tabelle, aber lange nicht so viel wie die ROM-Routinen. Das war damit gemeint, dass Tz keine Rolle spielen. Und so brachte mich 5ace auf die Idee, in diese Richtung weiter zu forschen. Den Algorithmus für 32bit gibt es auf codebase64. Das Prinzip ist aber ganz einfach: Es wird die Zahl durch 10 geteilt, das ganzzahlige Ergebnis behalten, und der Rest entspricht der kleinsten Stelle. Dann wird das Ergebnis wieder durch 10 geteilt; der Rest entspricht der nächsten Stelle, usw., bis man alle Dezimalstellen hat.

    btw sry for ":"

    Damit bin ich dann auch wirklich durch, und das Programm ist in seiner ersten Version (QUICKNUM-A) fertig. Danke @ all.

    Der nächste bitte. ^^


  • (((In meinem letzten Post sehe ich gerade, dass "digits testen auf 0" ab Zeile 49 besser mit "ora" statt "adc" umgesetzt werden sollte.)))

    atomcode Es gibt ein sehr gutes Erklärungsvideo zu dem von Dir geposteten Code/Algorithmus: Bitte melde dich an, um diesen Link zu sehen.