Drehroutine: Trigonometrie in Assembler

Trigonometrische Funktionen in einer höheren Programmiersprache, wiez.B. BASIC oder PASCAL, einzusetzen, ist relativ einfach. Schwierigerwird es, wenn man sich auf der untersten Ebene der Programmierkunst bewegt, da, wo man wirklich alles selber machen muß, in Assembler. Aber ist es wirklich so schwierig?

Dr. Michael Schütz

Nein, sonst gäbe es vermutlich diesen Artikel nicht. Die Programmierung in Assembler unterscheidet sich deutlich von höheren Sprachen. Hierbei überlegt man sich mindestens zweimal, ob für eine Rechnung wirklich Realzahlen erforderlich sind, oder ob vielleicht ein quadratisches Ergebnis nicht ebensogut für die Länge eines Vektors zu gebrauchen sei wie (mathematisch korrekt) die Wurzel daraus.

Wozu Trigonometrie in Assembler?

Wer selber programmiert, weiß, wie langsam Interpreter, aber auch Compiler, mit dem „Sinus“ und „Cosinus“ fertigwerden. Sicherlich, die Werte mit acht bis zehn Stellen hinter dem Komma auszurechnen, braucht eine gewisse Zeit (immerhin muß eine Potenzreihe mit fünf bis zehn Gliedern ausgerechnet werden), aber für die meisten Anwendungen, wie z.B. für eine Drehroutine, reicht ein gerundeter Wert im Integerformat auch. Daß dabei faszinierende Geschwindigkeiten erreicht werden können, zeigen Grafikprogramme wie STAD oder SHORTY. Aber nicht nur die Geschwindigkeit, die Funktionen wie das Drehen eines Ausschnittes um beliebige Winkel erst erträglich macht, nein auch die Programmlänge sollte im Zeitalter der 4-MB-Rechner nicht außer acht gelassen werden. Das im folgenden beschriebene und abgedruckte Programm ist 760 Byte lang und vermag einen Ausschnitt um beliebige ganzzahlige Winkel zu drehen.

Von der Theorie ...

Die Theorie der Drehung eines Vektors um einen Winkel Alpha beschränkt sich auf zwei Gleichungen:

py = xcos(a) + ysin(a)
px = ycos(a) - xsin(a)

Bild 1: Sin/Cos-Verlauf im Bereich von 0-360°

Und schon hat der Vektor mit den Koordinaten x, y die neue Position px, py. Die einzige Schwierigkeit dabei: Wie komme ich an die SIN- und COS-Werte? Da wir einen Vektor oder einen Ausschnitt nur um ganzzahlige Winkel drehen wollen, brauchen wir maximal 360 Sinus- und ebensoviel Cosinus-Werte. Das hört sich doch recht wenig an .... 720 Werte, da könnte man doch eine Tabelle.... richtig, nichts geht schneller, als die gewünschten Werte einfach aus einer im Programm befindlichen Tabelle zu holen. Bei 720 Daten im 2-Byte-Integerformat ergibt sich eine Tabellenlänge von 1440 Byte. Unter der Berücksichtigung, daß gilt:

cos(a) = sin(a+90)

kann die Hälfte der Tabelle eingespart werden, indem für den Cosinus- der Sinus-Wert des Winkels+90° berechnet wird. Es gibt noch eine weitere Vereinfachung. Es reicht nämlich aus, die Sinus-Funktion im Bereich von 0 bis 90° zu tabellieren, da der Bereich von 90 bis 180° einfach an der 90°-Senkrechten gespiegelt ist (vgl. Bild 1). Beispiel:

sin(110°) = sin(180-110°) = sin(70°)
cos(110°) = sin(110+90°) = -sin(20°)

... zur Praxis

Mit dieser Theorie bewaffnet, schreiten wir zur Tat. Das Programm ist in mehrere Teile gegliedert:

drehen: Start der Routine
mitte: Mittelpunkt berechnen
block: dreht einen Ausschnitt
npos: berechnet neue Koordinaten
up-dreh: die eigentliche Drehroutine
cosi: berechnet sin/cos

Als erstes stellt die cos/-Routine sicher, daß der Drehwinkel 360° nicht überschreitet, bevor die sin/cos-Werte ermittelt werden. In den Zeilen 25-47 folgen dann die Berechnung des Mittelpunktes, um den gedreht wird, und eine kurze Löschrou-tine, da die Ausschnittroutine {block) nur gesetzte Punkte dreht (der Zielbildschirm muß deshalb weiß sein). Ab Zeile 49 kann man sagen: es geht rund. Die Hauptschleifen (rd0-rd2) werden mit Parametern gefüttert {dx, dy, Quelle, Ziel) und jedes „gedrehte“ Bit wird ab Zeile 69 (plot) wieder gesetzt.

Beendet wird die Rotation durch die Berechnung der neuen Ausschnittgrenzen (px1, py1, px2, py2) ab Zeile 105.

GEM und die Auflösung

Wie an vielen Stellen zu sehen ist, unterstützt das Programm die Auflösung 640*400. Wird eine variable Auflösung gewünscht, müssen entsprechend die Grenzen (640,400 bzw. 639, 399) und die Zeilenbreite (80) angepaßt werden. Aus Geschwindigkeitsgründen empfehle ich den Bereich zu pat-chen (direktes Ändern der Zahlen im laufenden Programm, durch das Programm).


;               Variabel Drehen
;            von Dr. Michael Schütz
;
;          (c) 1992 MAXON Computer
;
;
;   INPUT:  d0  Drehwinkel
;           dx  Breite des Ausschnittes
;           dy  Höhe des Ausschnittes
;           px1 Position zum drehen
;           py1 Position zum drehen
;
;   OUTPUT: Koordinaten des gedrehten
;           Ausschnittes
;           px1 Ecke oben links x
;           py1 Ecke oben links y
;           px2 Ecke unten rechts x
;           py2 Ecke unten rechts y
;
;--------------------------------------------

drehen: bsr     cosi        ; Winkel berechnen
        lea     mx,a1       ; Mittelpunkt x
        lea     my,a5       ; Mittelpunkt y
        move.w  dx,d7       ; breite x
        move.w  dy,d6       ; Breite y
        ext.l   d7          ; als .l
        ext.l   d6          ; als .l
        asr.w   #1,d6       ; /2
        asr.w   #1,d7       ; /2
        move.w  d7,(a1)     ; Mittelpunkt x
        move.w  d6,(a5)     ; Mittelpunkt y
        bsr     up_dreh     ; um Winkel drehen
        sub.w   d6,(a1)     ;
        sub.w   d7,(a5)     ;
        move.w  px1,d0      ; Plus Start x
        add.w   d0,(a1)     ;
        move.w  py1,d0      ; Plus Start y
        add.w   d0,(a5)     ;

block:  movea.l ziel,a0     ; Zielbildschirm
        movea.l a0,a4       ; auch nach a4
        move.l  #7999,d0    ; 32000 Byte
.0:     clr.l   (a0)+       ; löschen
        dbra    d0,.0       ; loop

        move.w  dx,d5       ; breite x
        addi.w  #1,d5       ; +1
        movea.l #guelle,a0  ; Quelle start
        clr.w   d3          ; y Zähler
        movea.l a0,a2       ; Quelle
        suba.w  #80,a2      ; -80 (eine Zeile)
.rd0:   clr.w   d1          ; x Zähler
        adda.w  #80,a2      ; +80 (eine Zeile)
        movea.l a2,a0       ; Pointer sichern
.rd1:   move.b  (a0)+,d4    ; Byte holen
        beq     .re         ; =0 ? ==> .re
        move.w  #7,d2       ; 7 Bits

.rd2:   btst    d2,d4       ; Bit gesetzt ?
        beq     .bit        ; nein --> .bit
        move.w  d1,d7       ; ja X
        move.w  d3,d6       ;    Y
        bsr     up_dreh     ; errechnen
        add.w   (a1),d6     ; Plus Mitte x
        add.w   (a5),d7     ; Plus Mitte y
.plot:  addq.w  #1,d6       ; x+1
        cmpi.w  #399,d7     ; max. y=399
        bgt     .bit        ; zu groß
        tst.w   d7          ; <0?
        blt     .bit        ; zu klein
        cmpi.w  #639,d6     ; max. x=639
        bgt     .bit        ; zu groß
        tst.w   d6          ; <0?
        blt     .bit        ; zu klein
        addi.w  #1,d7       ; y+1
        mulu.w  #80,d7      ; *80 Zeilen
        subi.w  #640,d6     ; x=640-x
        neg.w   d6          ;
        ext.l   d6          ; und als .l
        divu.w  #8,d6       ; d6=d6/8
        sub.w   d6,d7       ; Spalte
        subq.l  #1,d7       ; -1
        swap.w  d6          ; das Bit
        bset    d6,0(a4,d7.w) ; und setzen
.bit:   addq.w  #1;dl       ; Zähler erhöhen
        dbra    d2,.rd2     ; weiter --> .rd2

.ree:   cmp.w   d5,d1       ; Breite x ?
        blt     .rd1        ; nein --> .rd1
        cmp.w   dy,d3       ; Höhe y ?
        bgt     .npos       ; ja --> .npos
        addq.w  #1,d3       ; sonst Y+1
        bra     .rd0        ; und --> .rd0
.re:    addq.w  #8,d1       ; + 8 Bit
        bra     .ree        ; und weiter

; -------------------------------------------
; Neue Position berechnen
; -------------------------------------------

.npos:  move.w  #639,d0     ; max. x
        move.w  #399,d1     ; max. y
        clr.w   d2          ; min. x
        clr.w   d3          ; min. y
        clr.w   d7          ; Pos 0,0
        clr.w   d6          ;
        bsr     dreh        ; errechnen
        move.w  dx,d7       ; Pos dx, 0
        clr.w   d6          ;
        bsr     dreh        ; errechnen
        move.w  dx,d7       ; Pos dx,dy
        move.w  dy,d6       ;
        bsr     dreh        ; errechnen
        clr.w   d7          ; Pos 0,dy
        move.w  dy,d6       ;
        bsr     dreh        ; errechnen

        tst.w   d0          ; Test x1
        bgt     .n1         ; >0 --> .n1
        clr.w   d0          ; sonst =0
.n1:    tst.w   d2          ; Test x2
        bgt     .n2         ; >0 --> .n2
        clr.w   d2          ; sonst =0
.n2:    tst.w   d1          ; Test y1
        bgt     .n3         ; >0 .n3
        clr.w   d1          ; sonst =0
.n3:    tst.w   d3          ; Test y2
        bgt     .n4         ; >0 --> .n4
        clr.w   d3          ; sonst =0
.n4:    move.w  d0,px1      ; neue Position
        move.w  d1,py1      ; des gedrehten
        move.w  d2,px2      ; Ausschnittes auf
        move.w  d3,py2      ; Bildschirm ziel
        rts                 ; ende

dreh:   bsr     up_dreh     ; drehen
        add.w   (a1),d6     ; Mittelpunkt x
        add.w   (a5),d7     ; Mittelpunkt y
        cmp.w   d6,d0       ; Der größte
        blt     .lo1        ; und der
        move.w  d6,d0       ; kleinste Wert

.lo1:   cmp.w   d7,d1       ; der neuen
        blt     .lo2        ; Koordinaten
        move.w  d7,d1       ; steht in :
.lo2:   cmp.w   d6,d2       ; d0=x1 klein
        bgt     .lo3        ; d1=y1 klein
        move.w  d6,d2       ; d2=x2 groß
.lo3:   cmp.w   d7,d3       ; d3=y2 groß
        bgt     .lo4        ;
        move.w  d7,d3       ;
.lo4:   rts                 ;

;------------------------------------
; Daten
;------------------------------------

quelle: .DC.l   0           ; Adresse des Quellbildes
ziel:   .DC.l   0           ; Adresse der Zielbildes

mx:     .DC.w 0             ; Mittelpunkt x
my:     .DC.w 0             ; Mittelpunkt y

dx:     .DC.w 0             ; Breite x
dy:     .DC.w 0             ; Breite y

px1:    .DC.w 0             ; Position x1
py1:    .DC.w 0             ; Position y1
px2:    .DC.w 0             ; Position x2
py2:    .DC.w 0             ; Position y2

;------------------------------------
; Die eigentliche Drehroutine
;------------------------------------

up_dreh: movem.l d0-d4,-(sp)    ; Reg. retten
        move.w  #10000,d2       ; Multiplikator
        move.w  sinx,d3         ; d3=sin(w)
        move.w  cosx,d4         ; d4=cos(w)
        move.w  d3,d0           ; d0=sin(w)
        move.w  d4,d1           ; d1=cos(w)
        muls.w  d6,d4           ; d4=x*cos(wj
        muls.w  d7,d3           ; d3=y*sin(w)
        add.l   d4,d3           ; d3=d3+d4
        divs.w  d2,d3           ; d3=d3/10000
        muls.w  d7,d1           ; d1=y*cos(w)
        muls.w  d6,d0           ; d0=x*sin(w)
        sub.l   d0,d1           ; d1=d1-d0
        divs.w  d2,d1           ; d1=d1/10000
        ext.l   d1              ; neuer x-Wert
        move.l  d1,d6           ; nach d6
        ext.l   d3              ; neuer y-Wert
        move.l  d1,d7           ; nach d7
        movem.l (sp)+,d0-d4     ; Reg. zurück
        rts                     ; und ende

;------------------------------------
; Sinus und Cosinuswerte berechnen
;------------------------------------

cosi:   cmpi.w  #360,d0         ; Winkel Test
        ble     .0              ; <=360 Grad
        subi.w  #360,d0         ; sonst -360
        bra     cosi            ; und loop
.0:     add.w   d0,d0           ; 2 Byte Integer
        move.w  d0,winkel       ; als Winkel
        cmpi.w  #181,d0         ; <90 Grad
        blt     .3              ; ja --> .0
        cmpi.w  #361,d0         ; <180 Grad
        blt     .1              ; ja -->.1
        cmpi.w  #540,d0         ; >270 Grad
        bgt     .2              ; ja —> .2
        subi.w  #360,d0         ; -360
        bsr     .3              ;
.r:     neg.w   sinx            ; sinx=-sinx
        neg.w   cosx            ; cosx=-cosx
        rts                     ; und ende
.1:     subi.w  #180,d0         ; -180 (90)
        lea     sin,a0          ; für <=180 Grad
        move.w  0(a0,d0.w),cosx ; cosx=sin(x-90)
        neg.w   cosx            ; cosx=-cosx
        lea     cos,a0          ;
        neg.w   d0              ;
        move.w  0(a0,d0.w),sinx ; sinx=cos(x-90)
        rts                     ;
.2:     subi.w  #360,d0         ; -360 (180)
        bsr     .1              ; <360
        bra     .r              ;
.3:     lea     sin,a0          ; für <= 90 Grad
        move.w  0(a0,d0.w),sinx ; sinx=sin(d0)
        lea     cos,a0          ;
        neg.w   d0              ;
        move.w  0(a0,d0.w),cosx ; cosx=cos(d0) 
        rts ;

sinx:   .DC.w   0               ; Sinuswert sin(winkel)
cosx:   .DC.w   0               ; Cosinuswert ccs(winkel)
winkel: .DC.w   0               ; Winkel zum Drehen

;------------------------------------
; Sinuswerte / sin(x)*1000
;------------------------------------

sin:    .DC.w 0000,0174,0348,0523,0697,0871,1045
        .DC.w 1218,1391,1564,1736,1908,2079,2249 
        .DC.w 2419,2588,2756,2923,3090,3255,3420 
        .DC.w 3583,3746,3907,4067,4226,4383,4539 
        .DC.w 4694,4848,5000,5150,5299,5446,5591 
        .DC.w 5735,5877,6018,6156,6293,6427,6560 
        .DC.w 6691,6819,6946,7071,7193,7313,7431 
        .DC.w 7547,7660,7771,7880,7986,8090,8191 
        .DC.w 8290,8386,8480,8571,8660,8746,8829 
        .DC.w 8910,8987,9063,9135,9205,9271,9335 
        .DC.w 9396,9455,9510,9563,9612,9659,9702 
        .DC.w 9743,9781,9816,9848,9876,9902,9925 
        .DC.w 9945,9961,3975,9986,9993,9998 
cos:    .DC.w 10000


Aus: ST-Computer 01 / 1993, Seite 67

Links

Copyright-Bestimmungen: siehe Über diese Seite