Schneller Drawline-Algorithmus

Basierend auf der Pascal-Routine aus dem Artikel "Schneller Drawline-Algorithmus" habe ich diese umgesetzt in eine Routine für Assembler. An dieser Stelle möchte ich die Entwicklung von Pascal (Version 3.01) auf eine optimierte Assembler-Routine beschreiben.

Schritt 1: TURBO-Pascal Quelle

PROGRAM BRESENHAM;
(* Berechnung einer Geraden nach dem Bresenham-Algorithmus *)

procedure plot(x, y, modus: INTEGER);
begin
end;

Procedure Line (x1, y1, x2, y2, farbe : INTEGER);
{ Die Prozedur verbindet die Punkte P1(x1,y1) und P2(x2,y2) mit der in   }
{ 'farbe' spezifizierten Zeichenfarbe.                                   }

VAR xl, yl, x, y,                             { Hilfsvariablen           }
    dx, dy,
     a,  b, e,
    help,                                     { Variablentausch          }
    ende                 : INTEGER;           { Kennzeichnung Linienende }
    winkelhalbierende    : BOOLEAN;

BEGIN { Prozedur 'Line' Anfang }

   { Defaultwerte für Variablen }
   xl   :=  1; yl :=  1;
   x    := x1;  y := y1;
   ende := x2;
   dx   := x2 - x1;
   dy   := y2 - y1;
   winkelhalbierende := False;

   { Spiegelung an y-Achse }
   IF dx < 0 THEN
      BEGIN
         dx := -dx;
         xl := -1;
      END;

   { Spiegelung an x-Achse }
   IF dy < 0 THEN
      BEGIN
         dy :=  -dy;
         yl :=  -1;
      END;

   { Spiegelung an Winkelhalbierender des 1. Quadranten }
   IF dx < dy THEN
      BEGIN
         help :=  x;  x :=  y;  y := help;
         help := dx; dx := dy; dy := help;
         help := xl; xl := yl; yl := help;
         ende := y2;
         winkelhalbierende := True;
      END;

   { Hilfsvariablen }
   a := dy shl 1;
   b := dx shl 1 - a;
   e := a - dx;

  { Zeichnen der Geraden }
  IF winkelhalbierende THEN
     BEGIN
        Plot (y, x, farbe);
        WHILE x <> ende DO
           BEGIN
              x := x + xl;
              IF e > 0 THEN
                 BEGIN
                    y := y + yl;
                    e := e -  b;
                 END
              ELSE
                 e := e + a;
              Plot (y, x, farbe);
           END
     END
  ELSE
     BEGIN

         Plot (x, y, farbe);
         WHILE x <> ende DO
            BEGIN
               x := x + xl;
               IF e > 0 THEN
                  BEGIN
                     y := y + yl;
                     e := e -  b;
                  END
               ELSE
                  e := e + a;
               Plot (x, y, farbe);
            END
     END;
END; { Prozedur 'Line' Ende }

BEGIN
  line(100,10,200,20,1);
END.

[Listing des verwendeten TURBO-Pascal Programms]

Das Programm zeichnet eine Gerade von X=100 bis 200 und Y=10 bis 20. Die Routine plot ist nicht implementiert, da diese speziell von der Videodarstellung der verwendeten Maschine abhängig ist.

Schritt 2: Disassemblierter Hauptteil

	title	Gerade nach Bresenham-Algorithmus
	name	('BRESHAM')

; Berechnung einer Geraden nach dem Bresenham-Algorithmus

; Dies ist die diassemblierte Version eines TURBO-PASCAL Programms

	.z80
	aseg
	.phase	20e2h

FALSE	equ	0
TRUE	equ	1

TPA	equ	0100h
;
; Laufzeitroutinen
;
RTL$IN1	equ	0364h		; Initialisierung der Geraete
RTL$IN2	equ	04d4h		; Initialisierung des Speichers
.NE.	equ	0692h		; Integer <>
.GT.	equ	06cch		; Integer >
.LT.	equ	06e0h		; Integer <
.SHL.	equ	074eh		; Shift left
RTL$END	equ	20d4h		; Programmende
;
winkhalb equ	0ef40h		; winkelhalbierende : boolean
ende	equ	0ef41h		; ende : integer
help	equ	0ef43h		; help : integer
v.e	equ	0ef45h		; e : integer
v.b	equ	0ef47h		; b : integer
v.a	equ	0ef49h		; a : integer
dy	equ	0ef4bh		; dy : integer
dx	equ	0ef4dh		; dx : integer
v.y	equ	0ef4fh		; y : integer
v.x	equ	0ef51h		; x : integer
yl	equ	0ef53h		; yl : integer
xl	equ	0ef55h		; xl : integer
farbe	equ	0ef5fh		; farbe : integer
y2	equ	0ef61h		; y2 : integer
x2	equ	0ef63h		; x2 : integer
y1	equ	0ef65h		; y1 : integer
x1	equ	0ef67h		; x1 : integer
;
p.modus	equ	0ef71h		; modus : integer
p.y	equ	0ef73h		; y : integer
p.x	equ	0ef75h		; x : integer
;
TOP$MEM	equ	0ef7fh
;
BREAK	equ	0ff00h

	ld	sp,TPA
	ld	hl,TOP$MEM
	ld	bc,BREAK
	call	RTL$IN1
	ld	hl,HEAP
	ld	de,winkhalb
	ld	bc,TOP$MEM+128
	ld	a,1
	call	RTL$IN2
	jp	MAIN
;
; procedure plot(x, y, modus: integer);	DUMMY
;
plot:
	pop	iy
	pop	hl
	ld	(p.modus),hl
	pop	hl
	ld	(p.y),hl
	pop	hl
	ld	(p.x),hl
	push	iy
	ret
;
; Procedure Line (x1, y1, x2, y2, farbe : integer);
;
Line:
	pop	iy
	pop	hl
	ld	(farbe),hl	; farbe
	pop	hl
	ld	(y2),hl		; y2
	pop	hl
	ld	(x2),hl		; x2
	pop	hl
	ld	(y1),hl		; y1
	pop	hl
	ld	(x1),hl		; x1
	push	iy
	ld	hl,1
	ld	(xl),hl		; Initialisierung xl
	ld	hl,1
	ld	(yl),hl		; Initialisierung yl
	ld	hl,(x1)		; Laden x1
	ld	(v.x),hl	; Speichern x
	ld	hl,(y1)		; Laden y1
	ld	(v.y),hl	; Speichern y
	ld	hl,(x2)		; Laden x2
	ld	(ende),hl	; Speichern ende
	ld	hl,(x2)		; Laden x2
	push	hl
	ld	hl,(x1)		; Laden x1
	pop	de
	ex	de,hl
	or	a
	sbc	hl,de
	ld	(dx),hl		; dx=x2-x1
	ld	hl,(y2)		; Laden y2
	push	hl
	ld	hl,(y1)		; Laden y1
	pop	de
	ex	de,hl
	or	a
	sbc	hl,de
	ld	(dy),hl		; dy=y2-y1
	ld	hl,FALSE
	ld	a,l
	ld	(winkhalb),a	; winkelhalbierende=false
;
;  Spiegelung an y-Achse
;
	ld	hl,(dx)		; Laden dx
	push	hl
	ld	hl,0
	pop	de
	call	.LT.		; Test dx < 0
	bit	0,l
	jp	z,spiegelX	; dx >= 0
	ld	hl,(dx)		; Laden dx
	ld	a,l
	cpl
	ld	l,a
	ld	a,h
	cpl
	ld	h,a
	inc	hl
	ld	(dx),hl		; Negieren dx
	ld	hl,-1
	ld	(xl),hl		; Aendern xl
;
; Spiegelung an x-Achse
;
spiegelX:
	ld	hl,(dy)		; Laden dy
	push	hl
	ld	hl,0
	pop	de
	call	.LT.		; Test dy < 0
	bit	0,l
	jp	z,spiegel1	; dy >= 0
	ld	hl,(dy)		; Laden dy
	ld	a,l
	cpl
	ld	l,a
	ld	a,h
	cpl
	ld	h,a
	inc	hl
	ld	(dy),hl		; Negieren dy
	ld	hl,-1
	ld	(yl),hl		; Aendern yl
;
; Spiegelung an Winkelhalbierender des 1. Quadranten
;
spiegel1:
	ld	hl,(dx)		; Laden dx
	push	hl
	ld	hl,(dy)		; Laden dy
	pop	de
	call	.LT.		; Test dx < dy
	bit	0,l
	jp	z,keintausch	; dx >= dy
;
; Austausch von Variablen
;
	ld	hl,(v.x)	; Austausch x,y
	ld	(help),hl
	ld	hl,(v.y)
	ld	(v.x),hl
	ld	hl,(help)
	ld	(v.y),hl
;
	ld	hl,(dx)		; Austausch dx,dy
	ld	(help),hl
	ld	hl,(dy)
	ld	(dx),hl
	ld	hl,(help)
	ld	(dy),hl
;
	ld	hl,(xl)		; Austausch xl,yl
	ld	(help),hl
	ld	hl,(yl)
	ld	(xl),hl
	ld	hl,(help)
	ld	(yl),hl

	ld	hl,(y2)
	ld	(ende),hl	; Aendern ende
	ld	hl,TRUE
	ld	a,l
	ld	(winkhalb),a	; winkelhalbierende=true
;
; Hilfsvariablen
;
keintausch:
	ld	hl,(dy)		; Laden dy
	push	hl
	ld	hl,1
	pop	de
	call	.SHL.
	ld	(v.a),hl	; a=dy * 2
;
	ld	hl,(dx)		; Laden dx
	push	hl
	ld	hl,1
	pop	de
	call	.SHL.
	push	hl
	ld	hl,(v.a)	; Laden a
	pop	de
	ex	de,hl
	or	a
	sbc	hl,de
	ld	(v.b),hl	; b=dx * 2 - 1
;
	ld	hl,(v.a)	; Laden a
	push	hl
	ld	hl,(dx)		; Laden dx
	pop	de
	ex	de,hl
	or	a
	sbc	hl,de
	ld	(v.e),hl	; e=a - dx
;
; Zeichnen der Geraden
;
	ld	hl,(winkhalb)	; Laden winkelhalbierende
	ld	h,0
	bit	0,l
	jp	z,Gerade2beg
	ld	hl,(v.y)	; Laden y
	push	hl
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(farbe)	; Laden farbe
	push	hl
	call	plot		; plot()
Gerade1:
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(ende)	; Laden ende
	pop	de
	call	.NE.		; Test x <> ende
	bit	0,l
	jp	z,_EndeGerade	; x = ende
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(xl)		; Laden xl
	pop	de
	add	hl,de
	ld	(v.x),hl	; Speichern x
	ld	hl,(v.e)	; Laden e
	push	hl
	ld	hl,0
	pop	de
	call	.GT.		; Test e > 0
	bit	0,l
	jp	z,Gerade1add	; e <= 0
	ld	hl,(v.y)	; Laden y
	push	hl
	ld	hl,(yl)		; Laden yl
	pop	de
	add	hl,de
	ld	(v.y),hl	; Speichern y
	ld	hl,(v.e)	; Laden e
	push	hl
	ld	hl,(v.b)	; Laden b
	pop	de
	ex	de,hl
	or	a
	sbc	hl,de
	ld	(v.e),hl	; Speichern e
	jp	Gerade1e
Gerade1add:
	ld	hl,(v.e)	; Laden e
	push	hl
	ld	hl,(v.a)	; Laden a
	pop	de
	add	hl,de
	ld	(v.e),hl	; Speichern e
Gerade1e:
	ld	hl,(v.y)	; Laden y
	push	hl
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(farbe)	; Laden farbe
	push	hl
	call	plot		; plot()
	jp	Gerade1
_EndeGerade:
	jp	EndeGerade
;
Gerade2beg:
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(v.y)	; Laden y
	push	hl
	ld	hl,(farbe)	; Laden farbe
	push	hl
	call	plot		; plot()
Gerade2:
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(ende)	; Laden ende
	pop	de
	call	.NE.		; Test x <> ende
	bit	0,l
	jp	z,EndeGerade	; x = ende
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(xl)		; Laden xl
	pop	de
	add	hl,de
	ld	(v.x),hl	; Speichern x
	ld	hl,(v.e)	; Laden e
	push	hl
	ld	hl,0
	pop	de
	call	.GT.		; Test e > 0
	bit	0,l
	jp	z,Gerade2add	; e <= 0
	ld	hl,(v.y)	; Laden y
	push	hl
	ld	hl,(yl)		; Laden yl
	pop	de
	add	hl,de
	ld	(v.y),hl	; Speichern y
	ld	hl,(v.e)	; Laden e
	push	hl
	ld	hl,(v.b)	; Laden b
	pop	de
	ex	de,hl
	or	a
	sbc	hl,de
	ld	(v.e),hl	; Speichern e
	jp	Gerade2e
Gerade2add:
	ld	hl,(v.e)	; Laden e
	push	hl
	ld	hl,(v.a)	; Laden a
	pop	de
	add	hl,de
	ld	(v.e),hl	; Speichern e
Gerade2e:
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(v.y)	; Laden y
	push	hl
	ld	hl,(farbe)	; Laden farbe
	push	hl
	call	plot		; plot()
	jp	Gerade2
EndeGerade:
	ret
;
; MAIN
;
MAIN:
	ld	hl,100
	push	hl
	ld	hl,10
	push	hl
	ld	hl,200
	push	hl
	ld	hl,20
	push	hl
	ld	hl,1
	push	hl
	call	Line
	jp	RTL$END
HEAP:

	.dephase

	end

[Listing des disassemblierten TURBO-Pascal Programms]

Der Quelltext ist dargestellt ohne die Laufzeitbibliothek, also ab Adresse 20E2h. Der erste freie Speicherplatz liegt bei 234Eh (Symbol HEAP). Die eigentliche Routine beginnt bei 2110h (Symbol Line) und endet bei 2334h (Symbol MAIN). Das ergibt eine Länge der Routine von 548 Bytes.

Schritt 3: Optimierte Quelle

	title	Gerade nach Bresenham-Algorithmus
	name	('BRESOPT')

; Berechnung einer Geraden nach dem Bresenham-Algorithmus

; Dies ist die optimierte diassemblierte Version
; eines TURBO-PASCAL Programms. Die Run-Time Routinen
; sind in direkten Code uebertragen worden.

	.z80
	aseg
	.phase	20e2h

FALSE	equ	0
TRUE	equ	1

TPA	equ	0100h
;
; Laufzeitroutinen
;
RTL$IN1	equ	0364h		; Initialisierung der Geraete
RTL$IN2	equ	04d4h		; Initialisierung des Speichers
RTL$END	equ	20d4h		; Programmende

winkhalb equ	0ef40h		; winkelhalbierende : boolean
ende	equ	0ef41h		; ende : integer
v.e	equ	0ef45h		; e : integer
v.b	equ	0ef47h		; b : integer
v.a	equ	0ef49h		; a : integer
dy	equ	0ef4bh		; dy : integer
dx	equ	0ef4dh		; dx : integer
v.y	equ	0ef4fh		; y : integer
v.x	equ	0ef51h		; x : integer
yl	equ	0ef53h		; yl : integer
xl	equ	0ef55h		; xl : integer
farbe	equ	0ef5fh		; farbe : integer
y2	equ	0ef61h		; y2 : integer
x2	equ	0ef63h		; x2 : integer
y1	equ	0ef65h		; y1 : integer
x1	equ	0ef67h		; x1 : integer
;
p.modus	equ	0ef71h		; modus : integer
p.y	equ	0ef73h		; y : integer
p.x	equ	0ef75h		; x : integer
;
TOP$MEM	equ	0ef7fh
;
BREAK	equ	0ff00h

	ld	sp,TPA
	ld	hl,TOP$MEM
	ld	bc,BREAK
	call	RTL$IN1
	ld	hl,HEAP
	ld	de,winkhalb
	ld	bc,TOP$MEM+128
	ld	a,1
	call	RTL$IN2
	jp	MAIN
;
; procedure plot(x, y, modus: integer);	DUMMY
;
plot:
	pop	iy
	pop	hl
	ld	(p.modus),hl
	pop	hl
	ld	(p.y),hl
	pop	hl
	ld	(p.x),hl
	push	iy
	ret
;
; Procedure Line (x1, y1, x2, y2, farbe : integer);
;
Line:
	pop	iy
	pop	hl
	ld	(farbe),hl	; farbe
	pop	hl
	ld	(y2),hl		; y2
	pop	hl
	ld	(x2),hl		; x2
	pop	hl
	ld	(y1),hl		; y1
	pop	hl
	ld	(x1),hl		; x1
	push	iy
	ld	hl,1
	ld	(xl),hl		; Initialisierung xl
	ld	(yl),hl		; Initialisierung yl
	ld	hl,(x1)		; Laden x1
	ld	(v.x),hl	; Speichern x
	ld	hl,(y1)		; Laden y1
	ld	(v.y),hl	; Speichern y
	ld	hl,(x2)		; Laden x2
	ld	(ende),hl	; Speichern ende
	ld	hl,(x2)		; Laden x2
	ld	de,(x1)		; Laden x1
	or	a
	sbc	hl,de
	ld	(dx),hl		; dx=x2-x1
	ld	hl,(y2)		; Laden y2
	ld	de,(y1)		; Laden y1
	or	a
	sbc	hl,de
	ld	(dy),hl		; dy=y2-y1
	xor	a
	ld	(winkhalb),a	; winkelhalbierende=false
;
;  Spiegelung an y-Achse
;
	ld	de,(dx)		; Laden dx
	bit	7,d
	jr	z,spiegelX
	ld	hl,0
	or	a
	sbc	hl,de		; Negieren dx
	ld	(dx),hl
	ld	hl,-1
	ld	(xl),hl		; Aendern xl
;
; Spiegelung an x-Achse
;
spiegelX:
	ld	de,(dy)		; Laden dy
	bit	7,d		; Test dy < 0
	jr	z,spiegel1
	ld	hl,0
	or	a
	sbc	hl,de
	ld	(dy),hl		; Negieren dy
	ld	hl,-1
	ld	(yl),hl		; Aendern yl
;
; Spiegelung an Winkelhalbierender des 1. Quadranten
;
spiegel1:
	ld	hl,(dx)		; Laden dx
	ld	de,(dy)		; Laden dy
	or	a
	sbc	hl,de		; Test dx < dy
	jr	nc,keintausch	; dx >= dy
;
; Austausch von Variablen
;
	ld	hl,(v.x)	; Austausch x,y
	exx
	ld	hl,(v.y)
	ld	(v.x),hl
	exx
	ld	(v.y),hl
;
	ld	hl,(dx)		; Austausch dx,dy
	exx
	ld	hl,(dy)
	ld	(dx),hl
	exx
	ld	(dy),hl
;
	ld	hl,(xl)		; Austausch xl,yl
	exx
	ld	hl,(yl)
	ld	(xl),hl
	exx
	ld	(yl),hl

	ld	hl,(y2)
	ld	(ende),hl	; Aendern ende
	ld	a,TRUE
	ld	(winkhalb),a	; winkelhalbierende=true
;
; Hilfsvariablen
;
keintausch:
	ld	hl,(dy)		; Laden dy
	add	hl,hl
	ld	(v.a),hl	; a=dy * 2
	ex	de,hl
;
	ld	hl,(dx)		; Laden dx
	add	hl,hl
	or	a
	sbc	hl,de
	ld	(v.b),hl	; b=dx * 2 - a
;
	ld	hl,(v.a)	; Laden a
	ld	de,(dx)		; Laden dx
	or	a
	sbc	hl,de
	ld	(v.e),hl	; e=a - dx
;
; Zeichnen der Geraden
;
	ld	a,(winkhalb)	; Laden winkelhalbierende
	rra
	jr	nc,Gerade2
Gerade1:
	ld	hl,(v.y)	; Laden y
	push	hl
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(farbe)	; Laden farbe
	push	hl
	call	plot		; plot()
	ld	hl,(v.x)	; Laden x
	ld	de,(ende)	; Laden ende
	or	a
	sbc	hl,de		; Test x <> ende
	ret	z		; x = ende
	ld	hl,(v.x)	; Laden x
	ld	de,(xl)		; Laden xl
	add	hl,de
	ld	(v.x),hl	; Speichern x
	ld	hl,(v.e)	; Laden e
	dec	hl
	rl	h		; Test e > 0
	jr	c,Gerade1add	; e < 0
	ld	hl,(v.y)	; Laden y
	ld	de,(yl)		; Laden yl
	add	hl,de
	ld	(v.y),hl	; Speichern y
	ld	hl,(v.e)	; Laden e
	ld	de,(v.b)	; Laden b
	or	a
	sbc	hl,de
	jr	Gerade1e	; Speichern e
Gerade1add:
	ld	hl,(v.e)	; Laden e
	ld	de,(v.a)	; Laden a
	add	hl,de
Gerade1e:
	ld	(v.e),hl	; Speichern e
	jr	Gerade1
;
Gerade2:
	ld	hl,(v.x)	; Laden x
	push	hl
	ld	hl,(v.y)	; Laden y
	push	hl
	ld	hl,(farbe)	; Laden farbe
	push	hl
	call	plot		; plot()
	ld	hl,(v.x)	; Laden x
	ld	de,(ende)	; Laden ende
	or	a
	sbc	hl,de		; Test x <> ende
	ret	z		; x = ende
	ld	hl,(v.x)	; Laden x
	ld	de,(xl)		; Laden xl
	add	hl,de
	ld	(v.x),hl	; Speichern x
	ld	hl,(v.e)	; Laden e
	dec	hl
	rl	h		; Test e > 0
	jr	c,Gerade2add	; e <= 0
	ld	hl,(v.y)	; Laden y
	ld	de,(yl)		; Laden yl
	add	hl,de
	ld	(v.y),hl	; Speichern y
	ld	hl,(v.e)	; Laden e
	ld	de,(v.b)	; Laden b
	or	a
	sbc	hl,de
	jr	Gerade2e	; Speichern e
Gerade2add:
	ld	hl,(v.e)	; Laden e
	ld	de,(v.a)	; Laden a
	add	hl,de
Gerade2e:
	ld	(v.e),hl	; Speichern e
	jr	Gerade2
;
; MAIN
;
MAIN:
	ld	hl,100
	push	hl
	ld	hl,10
	push	hl
	ld	hl,200
	push	hl
	ld	hl,20
	push	hl
	ld	hl,1
	push	hl
	call	Line
	jp	RTL$END
HEAP:

	.dephase

	end

[Listing des optimierten Assembler-Programms]

Die Optimierung bezog sich im Wesentlichen auf das Umgehen der folgenden Laufzeitroutinen:

Laufzeitroutine	Originalcode	Optimierter Code
Integervergleich <>	ld hl,(v.x) ; Laden x push hl ld hl,(ende) ; Laden ende pop de call .NE. ; Test x <> ende bit 0,l jp z,EndeGerade ; x = ende	ld hl,(v.x) ; Laden x ld de,(ende) ; Laden ende or a sbc hl,de ; Test x <> ende ret z ; x = ende
Integervergleich >	ld hl,(v.e) ; Laden e push hl ld hl,0 pop de call .GT. ; Test e > 0 bit 0,l jp z,Gerade1add ; e <= 0	ld hl,(v.e) ; Laden e dec hl rl h ; Test e > 0 jr c,Gerade1add ; e <= 0
Integervergleich <	ld hl,(dx) ; Laden dx push hl ld hl,0 pop de call .LT. ; Test dx < 0 bit 0,l jp z,spiegelX ; dx >= 0	ld de,(dx) ; Laden dx bit 7,d ; Test dx < 0 jr z,spiegelX ; dx >= 0
Integervergleich <	ld hl,(dx) ; Laden dx push hl ld hl,(dy) ; Laden dy pop de call .LT. ; Test dx < dy bit 0,l jp z,keintausch ; dx >= dy	ld hl,(dx) ; Laden dx ld de,(dy) ; Laden dy or a sbc hl,de ; Test dx < dy jr nc,keintausch; dx >= dy
Integer nach links schieben	ld hl,(dy) ; Laden dy push hl ld hl,1 pop de call .SHL. ld (v.a),hl ; a=dy * 2	ld hl,(dy) ; Laden dy add hl,hl ld (v.a),hl ; a=dy * 2

Weitere Optimierungen sind z.B.:

Originalcode	Optimierter Code
ld hl,(x2) ; Laden x2 push hl ld hl,(x1) ; Laden x1 pop de ex de,hl or a sbc hl,de ld (dx),hl ; dx=x2-x1	ld hl,(x2) ; Laden x2 ld de,(x1) ; Laden x1 or a sbc hl,de ld (dx),hl ; dx=x2-x1
ld hl,(dx) ; Laden dx ld a,l cpl ld l,a ld a,h cpl ld h,a inc hl ld (dx),hl ; Negieren dx	ld de,(dx) ; Laden dx ld hl,0 or a sbc hl,de ; Negieren dx ld (dx),hl

Originalcode

Optimierter Code

ld      hl,(x2)      ; Laden x2
push    hl
ld      hl,(x1)      ; Laden x1
pop     de
ex      de,hl
or      a
sbc     hl,de
ld      (dx),hl      ; dx=x2-x1

ld      hl,(x2)      ; Laden x2
ld      de,(x1)      ; Laden x1
or      a
sbc     hl,de
ld      (dx),hl      ; dx=x2-x1

ld      hl,(dx)      ; Laden dx
ld      a,l
cpl
ld      l,a
ld      a,h
cpl
ld      h,a
inc     hl
ld      (dx),hl      ; Negieren dx

ld      de,(dx)      ; Laden dx
ld      hl,0
or      a
sbc     hl,de        ; Negieren dx
ld      (dx),hl

Die eigentliche Routine beginnt hier ebenfalls bei 2110h (Symbol Line) und endet nun bei 2297h (Symbol MAIN). Das ergibt eine verkürzte Länge der Routine von 391 Bytes, also etwa 29 % weniger Code.

Schritt 4: Assembler-Modul

	title	Gerade nach Bresenham-Algorithmus
	name	('BRESREL')
	.z80

; Berechnung einer Geraden nach dem Bresenham-Algorithmus

; Dies ist die optimierte diassemblierte Version
; eines TURBO-PASCAL Programms. Die Run-Time Routinen
; sind in direkten Code uebertragen worden.
; Das Programm ist nun als Modul umgeschrien.
; Der Aufruf erfolgt ueber die Routine "Line".
; Die extern Routine "plot" ist die Plot-Routine
; und muss an die jeweilige Maschine angepasst werden.

; Anders als beim Original werden Parameter wie folgt uebergeben:

; (Im Original erfolgt die Uebergabe ueber den Stack
; x1	: HL
; y1	: DE
; x2	: HL'
; y2	: DE'
; farbe	: Akku

; Fuer die externe Routine 'plot':
; x	: HL
; y	: DE
; modus	: Akku

	entry	Line

	ext	plot

FALSE	equ	0
TRUE	equ	1

;
; Procedure Line (x1, y1, x2, y2, farbe : integer);
;
Line:
	ld	(farbe),a	; farbe
	ld	(x1),hl		; x1
	ld	(y1),de		; y1
	exx
	ld	(x2),hl		; x2
	ld	(y2),de		; y2
	ld	(ende),hl	; Speichern ende
	ld	ix,x1
	call	Richtung
	ld	(xl),hl		; Initialisierung xl
	ld	ix,y1
	call	Richtung
	ld	(yl),hl		; Initialisierung yl
	xor	a
	ld	(winkhalb),a	; winkelhalbierende=false
;
; Spiegelung an Winkelhalbierender des 1. Quadranten
;
spiegel1:
	ld	hl,(dx)		; Laden dx
	ld	de,(dy)		; Laden dy
	or	a
	sbc	hl,de
	jr	nc,keintausch	; Test dx < dy
;
; Austausch von Variablen
;
	ld	hl,(v.x)	; Austausch x,y
	exx
	ld	hl,(v.y)
	ld	(v.x),hl
	exx
	ld	(v.y),hl
;
	ld	hl,(dx)		; Austausch dx,dy
	exx
	ld	hl,(dy)
	ld	(dx),hl
	exx
	ld	(dy),hl
;
	ld	hl,(xl)		; Austausch xl,yl
	exx
	ld	hl,(yl)
	ld	(xl),hl
	exx
	ld	(yl),hl

	ld	hl,(y2)
	ld	(ende),hl	; Aendern ende
	ld	a,TRUE
	ld	(winkhalb),a	; winkelhalbierende=true
;
; Hilfsvariablen
;
keintausch:
	ld	hl,(dy)		; Laden dy
	add	hl,hl
	ld	(v.a),hl	; a=dy * 2
	ex	de,hl
;
	ld	hl,(dx)		; Laden dx
	add	hl,hl
	or	a
	sbc	hl,de
	ld	(v.b),hl	; b=dx * 2 - a
;
	ex	de,hl		; Laden a
	ld	de,(dx)		; Laden dx
	or	a
	sbc	hl,de
	ld	(v.e),hl	; e=a - dx
;
; Zeichnen der Geraden
;
	ld	a,(winkhalb)	; Laden winkelhalbierende
	or	a
	jr	z,Gerade2
Gerade1:
	ld	hl,(v.y)	; Laden y
	ld	de,(v.x)	; Laden x
	ld	a,(farbe)	; Laden farbe
	call	plot		; plot()
	ld	hl,(v.x)	; Laden x
	ld	de,(ende)	; Laden ende
	or	a
	sbc	hl,de		; Test x <> ende
	ret	z
	ld	hl,(v.x)	; Laden x
	ld	de,(xl)		; Laden xl
	add	hl,de
	ld	(v.x),hl	; Speichern x
	ld	hl,(v.e)	; Laden e
	dec	hl
	rl	h		; Test e > 0
	jr	c,Gerade1add
	ld	hl,(v.y)	; Laden y
	ld	de,(yl)		; Laden yl
	add	hl,de
	ld	(v.y),hl	; Speichern y
	ld	hl,(v.e)	; Laden e
	ld	de,(v.b)	; Laden b
	or	a
	sbc	hl,de
	jr	Gerade1e	; Speichern e
Gerade1add:
	ld	hl,(v.e)	; Laden e
	ld	de,(v.a)	; Laden a
	add	hl,de
Gerade1e:
	ld	(v.e),hl	; Speichern e
	jr	Gerade1
;
Gerade2:
	ld	hl,(v.x)	; Laden x
	ld	de,(v.y)	; Laden y
	ld	a,(farbe)	; Laden farbe
	call	plot		; plot()
	ld	hl,(v.x)	; Laden x
	ld	de,(ende)	; Laden ende
	or	a
	sbc	hl,de
	ret	z
	ld	hl,(v.x)	; Laden x
	ld	de,(xl)		; Laden xl
	add	hl,de
	ld	(v.x),hl	; Speichern x
	ld	hl,(v.e)	; Laden e
	dec	hl
	rl	h		; Test e > 0
	jr	c,Gerade2add
	ld	hl,(v.y)	; Laden y
	ld	de,(yl)		; Laden yl
	add	hl,de
	ld	(v.y),hl	; Speichern y
	ld	hl,(v.e)	; Laden e
	ld	de,(v.b)	; Laden b
	or	a
	sbc	hl,de
	jr	Gerade2e	; Speichern e
Gerade2add:
	ld	hl,(v.e)	; Laden e
	ld	de,(v.a)	; Laden a
	add	hl,de
Gerade2e:
	ld	(v.e),hl	; Speichern e
	jr	Gerade2
;
; Richtung fuer Gerade festlegen 
;
Richtung:
	ld	e,(ix+0)	; Laden x1/y1
	ld	d,(ix+1)
	ld	(ix+4),e	; Speichern x/y
	ld	(ix+5),d
	ld	l,(ix+2)	; Laden x2/y2
	ld	h,(ix+3)
	or	a
	sbc	hl,de
	ld	(ix+6),l	; dx/dy=x2/y2-x1/y2
	ld	(ix+7),h
	ex	de,hl
	ld	hl,1
	ret	nc		; Delta > 0
	ld	hl,0
	or	a
	sbc	hl,de		; Delta negieren
	ld	(ix+6),l
	ld	(ix+7),h
	ld	hl,-1
	ret

	dseg

winkhalb:
	ds	1		; winkelhalbierende : boolean
ende:
	ds	2		; ende : integer
v.e:
	ds	2		; e : integer
v.b:
	ds	2		; b : integer
v.a:
	ds	2		; a : integer
yl:
	ds	2		; yl : integer
xl:
	ds	2		; xl : integer
farbe:
	ds	1		; farbe : byte
;
x1:
	ds	2		; x1 : integer	\
x2:				;		|
	ds	2		; x2 : integer	|
v.x:				;		|
	ds	2		; x : integer	|
dx:				;		|
	ds	2		; dx : integer	/
;
y1:
	ds	2		; y1 : integer	\
y2:				;		|
	ds	2		; y2 : integer	|
v.y:				;		|
	ds	2		; y : integer	|
dy:				;		|
	ds	2		; dy : integer	/


	end

[Listing des modularen Assembler-Programms]

Das Modul weist eine nochmals verkürzte Code-Länge von 351 Bytes aus, das ist 36 % weniger gegenüber dem Originalcode.
Bei TURBO-Pascal erfolgt die Übergabe der Parameter bekanntlich über den Stack. Die Routine "plot" ist maschinenabhägig und kann nicht generell implementiert werden. Für das Modul habe ich den Aufruf für die Routinen wie folgt definiert:

Entry "Line"	Extern "plot"
X-Startwert in Register `HL` Y-Startwert in Register `DE` X-Endwert in Register `HL'` Y-Endwert in Register `DE'` Farbe im `Akku`	X-Punktwert im Register `HL` Y-Punktwert im Register `DE` Modus im `Akku`

Die Routine "plot" für den JOYCE wird grundsätzlich besprochen z.B. in Turbo-Grafik für den JOYCE. Dort ist der Bereich für X=0..719 und Y=0..255. Modus ist 0, wenn der Bildpunkt gesetzt, 1, wenn er gelöscht, 2, wenn er umgeschaltet und 3, wenn er getestet werden soll. Im Testfall ist bei gesetztem Bit der Akku 0FFh und die Carry-Flag ebenfalls gesetzt. Bei nicht gesetztem Bit ist der Akku 000h und die Carry-Flag nicht gesetzt. Ich habe diese Routine entsprechend angepasst.

;************************
;  PLOT  - MCode
;  Basiert auf
;  Turbo Pascal Version
;  1987 by M.A. & E. W.
;  Vers. 10/8/87
;    (excl. DotColor)
;    (excl. Scr_Access)
;************************
;
	.z80
	cseg

	entry	plot
;
proc	equ	0c000h		; Start der Plotroutine
XBIOS	equ	0fc5ah		; Einsprungadresse fuer XBIOS
SCREEN	equ	000e9h		; Nummer der XBIOS-Funktion
				; SCR_RUN_ROUTINE
ROLLER	equ	0b600h		; Anfangsadresse des Roller-RAM
;
;####################################################################
;# x-Koordinate in HL, y-Koordinate in (D)E und MODUS im Akku       #
;# Vorspann testet, ob Routine schon im Common Speicher liegt.      #
;# Falls nicht, dann Routine verschieben                            #
;####################################################################
;
plot:
	ex	de,hl		; x in DE; y in L
	ld	h,a		; MODUS retten
	ld	a,(plotflg)	; Plot-Flag laden
	or	a		; Test, ob Routine schon im Speicher
	call	z,moveplot	; Nein, Routine verschieben
	ld	bc,routine	; Adresse des Unterprogramms
	call	XBIOS		; Aufruf des XBIOS
	dw	SCREEN		; XBIOS-Funktion
	ret
;
;####################################################################
;# Video-Routine verschieben                                        #
;####################################################################
;
moveplot:
	push	bc
	push	de
	push	hl
	ld	hl,hiplot	; Quelle laden
	ld	de,proc		; Ziel laden
	ld	bc,prcln
	ldir			; Routine in den Speichre verschieben
	ld	a,-1
	ld	(plotflg),a	; Anzeigen, dass Routine im Speicher liegt
	pop	hl
	pop	de
	pop	bc
	ret
;
plotflg:
	db	0

hiplot:
	.phase proc

;####################################################################
;#  Unterprogramm Punkt setzen, ruecksetzen, umschalten, testen.    #
;#  Was gemacht werden soll, wird ueber MODUS bekannt gegeben:      #
;#  0 =setzen, 1 =ruecksetzen                                       #
;#  2 =umschalten, 3 =testen                                        #
;#  Im Fall 3 ist der Akku 0FFh und die Carry Flag gesetzt, falls   #
;#  auch das zu testende Bit gesetzt ist.                           #
;#                                                                  #
;#  Parameter fuer Unterprogramme wurden in                         #
;#  Turbo ueber den Stack uebergeben                                #
;#                                                                  #
;#  Im Assembler-Module wird das ueber Register abgewickelt:        #
;#  x-Koordinate in DE, y-Koordinate in L und MODUS in H            #
;####################################################################
;
routine:
	push	hl		; MODUS sichern
	ld	h,0		; y auf 16 Bit
	add	hl,hl		; y*2
	ld	bc,ROLLER
	add	hl,bc		; In ROLLER RAM positionieren
	ld	c,(hl)		; Adresse aus ROLLER RAM laden
	inc	hl
	ld	b,(hl)
	ld	a,c
	and	11111000b
	ld	l,a
	ld	h,b
	add	hl,hl		; Adresse korrigieren
	ld	a,00000011b
	and	d		; x begrenzen 0..3FF
	ld	d,a
	add	hl,de		; Adresse der Spalte
	ld	a,l
	and	11111000b
	ld	l,a		; Adresse korrigieren
	ld	a,c
	and	00000111b
	or	l
	ld	l,a
	ld	a,e		; x laden
	and	00000111b	; Spalte isolieren
	inc	a		; Bitposition 0..7 -> 1..8
	ld	b,a
	xor	a		; Maske einstellen
	scf			; Mit gesetztem Bit beginnen
loop:
	rra			; Bit in Maske positionieren
	djnz	loop
	pop	bc		; MODUS laden
	inc	b
	dec	b		; Test 0 = setzen
	jr	nz,clear
	or	(hl)		; Bit setzen
	ld	(hl),a
	ret
clear:
	dec	b		; Test 1 = ruecksetzen
	jr	nz,reverse
	cpl			; Maske invertieren
	and	(hl)		; Bit 0 setzen
	ld	(hl),a
	ret
reverse:
	dec	b		; Test 2 = umschalten
	jr	nz,status
	xor	(hl)		; Bit umschalten
	ld	(hl),a
	ret
status:
	dec	b		; Test 3 = testen
	ret	nz
	and	(hl)		; Bit maskieren
	ld	a,-1		; Ergebnis setzen
	scf
	ret	nz		; Akku = 0FFh, C - Bit gesetzt
	xor	a		; Akku = 00h, NC - Bit nicht gesetzt
	ret
;
prcln	equ	$-proc

	.dephase

	end

[Listing des maschinenabhängigen Assembler-Programms]

Mit dem folgenden Testprogramm wird eine Linie von oben links nach unten rechts über den Bildschirm gezeichnet.

	title	Testprogramm zur Ausgabe einer Linie
	name	('TEST')

; Diese kleine Testprogramm loescht den Bildschirm und
; zeichnet eine Linie von oben links (x,y)=(0,0)
; nach unten rechts (x,y)=(719,255)

; Die externe Routine "line" ist enthalten in der Datei BRES-REL.MAC.
; Diese externe Rotine wiederum ruft eine weitere externe Routine
; aus der Datei PLOT.MAC auf.

; Damit alles zusammenspielt, sind folgende Anweisungen noetig:

; M80 =TEST
; M80 =BRES-REL
; M80 =PLOT
; LINK TEST,BRES-REL,PLOT

	ext	line

OS	equ	0000h
BDOS	equ	0005h
TPATOP	equ	BDOS+1

.condir	equ	6

esc	equ	1bh

	ld	sp,(TPATOP)	; Stack laden
;
	ld	a,'H'
	call	escout		; Cursor nach 0,0
	ld	a,'E'
	call	escout		; Bildschirm loeschen
;
	ld	hl,719		; x2
	ld	de,255		; y2
	exx
	ld	hl,0		; x1
	ld	de,0		; y1
	ld	a,0		; Bit anschalten
	call	line		; Linie zeichnen
;
	jp	OS		; Ende
;
; Zeichen mit Praefix ESCape ausgeben
;
escout:
	push	af
	ld	a,esc
	call	conout		; ESCape ausgeben
	pop	af
;
; Zeichen auf Konsole ausgeben
;
conout:
	push	bc
	push	de
	push	hl
	ld	e,a
	ld	c,.condir
	call	BDOS		; Ausgabe
	pop	hl
	pop	de
	pop	bc
	ret

	end

[Listing des Testprogramms]