Bresenham line routine for the linear framebuffer with 8 bpp

Diskussion zum Thema Programmierung unter DOS (Intel x86)
Antworten
freecrac
DOS-Guru
Beiträge: 861
Registriert: Mi 21. Apr 2010, 11:44
Wohnort: Hamburg Horn

Bresenham line routine for the linear framebuffer with 8 bpp

Beitrag von freecrac »

Moin.
Ich habe meine Linien-Routine überarbeitet und hier ist das Ergebniss:

Code: Alles auswählen

;--------------------------------------------------------
;  This is a Bresenham line subroutine for videomodes
:  with 255 colors using the linear framebuffer(LFB).
;
;  This routine need an address table of startaddresses
;  of each scanline of the LFB placed in the beginning
;  of a data segment at OFFSET 0000.
;
;  The first entry of this address table have to be
;  the address of the LFB itself. And for all next
;  entries we have to add the bytes of the scanline
;  of the used resolution, so that every entry in
;  this address table represent the startaddress
;  of each line on the screen.
;
;  The start- and end-coordinates + the color of the
;  Line have to be placed in the following registers
;  Startpoint:EBX,ESI  Endpoint:ECX,EDI  Color:AL
;--------------------------------------------------------
LINE:     mov      edx, edi
          sub      ecx, ebx
          jl  T0
          add      ebx, [esi*4]
          sub      edx, esi
          jl  T1
          mov      esi, DWORD PTR[XMP1]
          cmp      ecx, edx
          jl  T2
          lea      edx, [edx+edx]
          mov      ebp, edx
          sub      edx, ecx
          mov      edi, edx
          sub      edx, ecx
;-------------------------------------
M00:      mov      [ebx], al
          and      edi, edi
          jge short M01
          lea      ebx, [ebx+1]
          lea      edi, [edi+ebp]
          dec      ecx
          jnz M00
          ret
;-------------------------------------
M01:      lea      ebx, [ebx+esi]
          lea      edi, [edi+edx]
          dec      ecx
          jnz M00
          ret
;-----------------------------------------------------
T0:       neg      ecx
          add      ebx, [esi*4]
          sub      edx, esi
          mov      esi, DWORD PTR[XMP1]
          jl  T01
          mov      esi, DWORD PTR[XMM1]
          cmp      ecx, edx
          jl  short T21
          lea      edx, [edx+edx]
          mov      ebp, edx
          sub      edx, ecx
          mov      edi, edx
          sub      edx, ecx
;-------------------------------------
M02:      mov      [ebx], al
          and      edi, edi
          jge short M03
          lea      ebx, [ebx-1]
          lea      edi, [edi+ebp]
          dec      ecx
          jnz M02
          ret
;-------------------------------------
M03:      lea      ebx, [ebx+esi]
          lea      edi, [edi+edx]
          dec      ecx
          jnz M02
          ret
;-----------------------------------------------------
T21:      lea      ecx, [ecx+ecx]
          mov      ebp, ecx
          sub      ecx, edx
          mov      edi, ecx
          sub      ecx, edx
;-------------------------------------
M04:      mov      [ebx], al
          and      edi, edi
          jge short M05
          add      ebx, DWORD PTR[XMAX]
          lea      edi, [edi+ebp]
          dec      edx
          jnz M04
          ret
;-------------------------------------
M05:      lea      ebx, [ebx+esi]
          lea      edi, [edi+ecx]
          dec      edx
          jnz M04
          ret
;-----------------------------------------------------
T01:      neg      edx
          cmp      ecx, edx
          jl  short T22
          lea      edx, [edx+edx]
          mov      ebp, edx
          sub      edx, ecx
          mov      edi, edx
          sub      edx, ecx
;-------------------------------------
M06:      mov      [ebx], al
          and      edi, edi
          jge short M07
          lea      ebx, [ebx-1]
          lea      edi, [edi+ebp]
          dec      ecx
          jnz M06
          ret
;-------------------------------------
M07:      sub      ebx, esi
          lea      edi, [edi+edx]
          dec      ecx
          jnz M06
          ret
;-----------------------------------------------------
T22:      lea      ecx, [ecx+ecx]
          mov      ebp, ecx
          sub      ecx, edx
          mov      edi, ecx
          sub      ecx, edx
;-------------------------------------
M08:      mov      [ebx], al
          and      edi, edi
          jge short M09
          sub      ebx, DWORD PTR[XMAX]
          lea      edi, [edi+ebp]
          dec      edx
          jnz M08
          ret
;-------------------------------------
M09:      sub      ebx, esi
          lea      edi, [edi+ecx]
          dec      edx
          jnz M08
          ret
;-----------------------------------------------------
T1:       neg      edx
          mov      esi, DWORD PTR[XMM1]
          cmp      ecx, edx
          jl  T12
          lea      edx, [edx+edx]
          mov      ebp, edx
          sub      edx, ecx
          mov      edi, edx
          sub      edx, ecx
;-------------------------------------
M10:      mov      [ebx], al
          and      edi, edi
          jge short M11
          lea      ebx, [ebx+1]
          lea      edi, [edi+ebp]
          dec      ecx
          jnz M10
          ret
;-------------------------------------
M11:      sub      ebx, esi
          lea      edi, [edi+edx]
          dec      ecx
          jnz M10
          ret
;-----------------------------------------------------
T12:      lea      ecx, [ecx+ecx]
          mov      ebp, ecx
          sub      ecx, edx
          mov      edi, ecx
          sub      ecx, edx
;-------------------------------------
M12:      mov      [ebx], al
          and      edi, edi
          jge short M13
          sub      ebx, DWORD PTR[XMAX]
          lea      edi, [edi+ebp]
          dec      edx
          jnz M12
          ret
;-------------------------------------
M13:      sub      ebx, esi
          lea      edi, [edi+ecx]
          dec      edx
          jnz M12
          ret
;-----------------------------------------------------
T2:       lea      ecx, [ecx+ecx]
          mov      ebp, ecx
          sub      ecx, edx
          mov      edi, ecx
          sub      ecx, edx
;-------------------------------------
M14:      mov      [ebx], al
          and      edi, edi
          jge short M15
          add      ebx, DWORD PTR[XMAX]
          lea      edi, [edi+ebp]
          dec      edx
          jnz M14
          ret
;-------------------------------------
M15:      lea      ebx, [ebx+esi]
          lea      edi, [edi+ecx]
          dec      edx
          jnz M14
          ret
;-----------------------------------------------------
;    Copyfree for all humans on planet earth
;-----------------------------------------------------
Im Anschluss zeige ich wohl besser auch mal wie man die Linen-Routine verwenden kann:

Code: Alles auswählen

;----------------------------
; Example for to draw a line using a VBE videomode with a horizontal resolution
; of 1920 and a vertical resolution of 1200 with 255 colors and 8 bit per pixel.
; (Hint: This example shows only wich instruction and data is needed for to use
; the line routine and the code have to be placed inside of a working application.)
;----------------------------
     RES_X =  1920           ; horizontal resolution
     RES_Y =  1200           ; vertical resolution
     Color =  0Eh
;----------------------------
.DATA
;----
; This following table of LFB startaddresses of each line
; have to be placed at offset 0000 in the data segment
;----
PIXTAB    DD RES_Y dup (0)   ; table of startaddresses (for to draw the line)
XMAX      DD 0               ; ScanLine (for to draw the line)
XMP1      DD 0               ; ScanLine + 1 (for to draw the line)
XMM1      DD 0               ; ScanLine - 1 (for to draw the line)
;----
VBEINFO   DB 512 dup (0)     ; Buffer for VBE 4F00 Vbe Info Block
MODEINFO  DB 256 dup (0)     ; Buffer for VBE 4F01 Mode Info Block
;----------------------------
.code
          mov      ax, @DATA           ; segment address of the data segment
          mov      ds, ax
          mov      es, ax

          mov      di, OFFSET VBEINFO  ; get the Vbe Info Block
          mov      ax, 4F00h           ; es:di 512 byte
     	  int    10h                   : Function 00h - Return VBE Controller Information
     	  cmp      ax, 4Fh
     	  jnz ERROR       ; need instructions for output an Error message + terminate program

     	  mov      dl, [di+5]          ; major version number of VBE
     	  cmp      dl, 2               ; version 2?
     	  jb  ERROR

; Get the VBE modenumber from the VBE modetable

          lfs      si, [di+0Eh]        ; VbeFarPtr to VideoModeList
GETMode:  mov      cx, fs:[si]         ; get the mode number
          lea      si, [si+2]
          cmp      cx, 0FFFFh          ; end of modelist ?
          jz  ERROR

          add      cx, 4000h           ; mode number + linear acess
          mov      di, OFFSET MODEINFO
          mov      ax, 4F01h           ; get the Mode Info Block
          int    10h                   ; Function 01h - Return VBE Mode Information
          cmp      ax, 4Fh
          jnz ERROR

; Now we have to find the mode number wich operate with our desired resolution

          cmp     WORD PTR[di+12h], RES_X ; horizontal resolution in pixels
          jnz GETMode
          cmp     WORD PTR[di+14h], RES_Y ; vertical resolution in pixels
          jnz GETMode
          cmp     BYTE PTR[di+19h], 8     ; bits per pixel
          jnz GETMode
          test    WORD PTR[di], 80h       ; Linear frame buffer mode
          jz  GETMode
          cmp     DWORD PTR[di+28h], 0    ; physical address for flat memory frame buffer
          jz  GETMode

; Set the VBE mode

          mov      ax, 4F02h
          mov      bx, cx               ; modenumber             
          int    10h
          cmp      ax, 4Fh
          jnz ERROR

; create a table of start addresses of each line on the screen

          mov      si, OFFSET MODEINFO
          xor      ebx, ebx
          mov      bx, ds
          mov      eax, [si+28h]        ; Address of the LFB
          shl      ebx, 4
          sub      eax, ebx             ; LFB = ds:reg32

          xor      edx, edx
          mov      dx, [si+32h]         ; LinBytesPerScanLine
          mov     DWORD PTR[XMAX], edx
          mov      ebx, edx
          inc      ebx
          mov     DWORD PTR[XMP1], ebx  ; LinBytesPerScanLine + 1
          sub      ebx, 2
          mov     DWORD PTR[XMM1], ebx  ; LinBytesPerScanLine - 1

          xor      ecx, ecx
          mov      cx, [si+14h]         ; vertical resolution in pixels
          shl      ecx, 2               ; vertical resolution in pixels * 4

          xor      edi, edi             ; OFFSET 0000
AGAIN:    mov      [di], eax            ; fill the address table
          add      edi, 4
          add      eax, edx             ; plus scanline
          cmp      edi, ecx             ; vertical resolution in pixels * 4 ?
          jb  AGAIN

;-----------
;     ----  Switching to the BIG-REALMODE  ----
; enhance "DS"-segment up to 4 GB + enable A20 address line

          call BIGREALMODE   ; this subroutine is not a part of this example

;-----------

; Drawing a line from the upper left corner to the lower right corner
; of the screen using a resolution of 1920 x 1200 with 8 bit color.

; Make sure that the coordinates of the start and end parameter for the
; line routine do not exceed the size of the horizontal and vertical
; resolution minus one. The maximum x/y coordinates have to be one times
; lower as the resolution size. For the resolution of 1920x1200 the highest
; coordinates are X=1919 Y=1199.

          mov      ebx, 0      ; X1-Position
          mov      esi, 0      ; Y1-Position
          mov      ecx, 1919   ; X2-Position
          mov      edi, 1199   ; Y2-Position
          mov      al, Color
          call LINE
;-----------
Die Linien-Routine sollte ersatzweise auch für den 32 Bit-Mode verwendet werden könnnen. (Noch nicht getestet.)
In diesem Fall wird der Operationscode der Linien-Routine noch um einige Bytes weniger gross werden, weil die Operandsize- und Adresssize-Prefixe dann nicht benötigt beim Assemblieren vom Assembler weggelassen werden.

Weitere Geschwindigkeits-Optimierung:
Je nachdem ob die Routine für den 16 Bitmode, oder den 32 Bitmode assembliert wird ändern sich innerhalb der Routine auch die Sprungadresse der bedingten Verzweigungsbefehle(conditional jumps). Damit die jeweilige Sprungadresse der dortigen Sprungbefehle bestenfalls auf eine durch 16 teilbare Adresse zielt und um Abhängigkeiten zwischen den Befehlen untereinander zu minimieren, könnte man für eine Geschwindigkeit-Optimierung einige NOP-Befehle zwischen den Befehlen einfügen. Jede Sprungadresse sollte dann dadurch auf eine durch 16 teilbare Adresse ausgerichtet sein.

Um Abhängigkeiten unter den Befehlen zu minimieren ist darauf zu achten das Befehle bei denen beispielsweise zuerst ein Register mit einem Wert beschrieben wurde, das dieses Register danach nicht gleich wieder ausgelesen wird. Weil sonst kommt es zu einer Ausführungsverzögerung der Befehle. Ein Schreibzugriff auf ein Registers nach einem Lesezugriff auf ein Registers macht keine Probleme, sondern nur Lesezugriffe nach dem vorherigen Schreibzugriff auf ein Register.

Beispiele:

Code: Alles auswählen

          mov      edi, edx         ; Zuerst: Lesezugriff auf EDX
          sub      edx, ecx         ; unmittelbar danach: Schreibzugriff auf EDX  = keine Verzögerung

Code: Alles auswählen

          lea      edx, [edx+edx]   ; Zuerst: Schreibzugriff auf EDX
          mov      ebp, edx         ; unmittelbar danach: Lesezugriff auf EDX = Verzögerung
Optimierung:

Code: Alles auswählen

          lea      edx, [edx+edx]  ; Schreibzugriff auf EDX
          nop
          mov      ebp, edx        ; Lesezugriff auf EDX = keine (oder geringere) Verzögerung
Dirk
Benutzeravatar
zatzen
DOS-Guru
Beiträge: 518
Registriert: Di 17. Apr 2012, 05:10
Wohnort: bei Köln
Kontaktdaten:

Re: Bresenham line routine for the linear framebuffer with 8

Beitrag von zatzen »

Ist das wirklich so, dass ein "NOP" die ganze Sache beschleunigt, oder wäre es vielmehr so, dass ein Register
generell eine gewisse Zeit braucht, um wieder lesbar zu werden, so dass es mit oder ohne NOP gleich langsam
wäre? Immherhin dauert NOP ja auch einen Takt... Eigentlich.
mov ax, 13h
int 10h

while vorne_frei do vor;
freecrac
DOS-Guru
Beiträge: 861
Registriert: Mi 21. Apr 2010, 11:44
Wohnort: Hamburg Horn

Re: Bresenham line routine for the linear framebuffer with 8

Beitrag von freecrac »

zatzen hat geschrieben:Ist das wirklich so, dass ein "NOP" die ganze Sache beschleunigt, oder wäre es vielmehr so, dass ein Register
generell eine gewisse Zeit braucht, um wieder lesbar zu werden, so dass es mit oder ohne NOP gleich langsam
wäre? Immherhin dauert NOP ja auch einen Takt... Eigentlich.
Ja so kann man es sagen. Ich glaube bis zum 80486 wird jeder einzelne Befehl erst vollständig berarbeitet und beeendet bis der nächste Befehl zur Ausführung kommt.

Sonst muss man, um die Abhängigkeiten der Befehle unteinander vollständig weg zu bekommen, für unterschiedliche CPUs auch unterschiedlich viele Befehle dazwischen bekommen. Das richtet sich nach den Stufen die innerhalb der Befehlspipeline von jedem Befehl durchlaufen werden müssen und auch nach der Anzahl der Befehlspipelines. Bis zum 80486er wurde nur eine Pipeline verwendet und ab Pentium gibt es zwei fünfstufige Integer-Pipelines, ein Athlon kann drei und eine Intel core2-CPU kann vier Integerbefehle gleichzeitig ausführen, aber nur im günstigsten Fall und wenn eine bestimmte Anzahl von Befehle richtig zusammengesetzt und plaziert wurde. So gibt es z.B. einfache und es gibt komplexere Befehle. Zwei solcher komplexen Befehle können zb. mit einem Pentium nicht auf beide Pipielines verteilt werden, sondern nur ein komplexer Befehl in der ersten Pipeline zusammen mit einem einfachen Befehl in der zweiten Pipiline, oder zwei einfacher Befehle in beiden Pipilines. Allerdings müssen sich die beiden Befehlspipelines mit Befehlen erst einmal vollständig füllen, damit eine paralelle Ausführung möglich wird und dafür werden hintereinander plaziert mehr als nur zwei Befehle die sich paaren lassen benötigt, bis alle Stufen mit Befehlen gefüllt sind.

Über die Paarungsregeln findet man auch hier etwas:
http://www.addison-wesley.de/service/me ... ap1102.htm

..

Wenn die Zieladdresse von Sprungbefehlen auf eine durch 16 teilbare Adresse zielt, dann profitieren davon alle x86er, egal wie man das hinbekommt, ob nun mit NOP-Befehlen, oder auch mit sinnvolleren anderen Befehlen aufgefüllt.
So ist es sinnvoll hierauf zu aller erst unsere Aufmerksamkeit zu richten.

Bei den Befehlsabhängigkeiten stossen wir aber auf ein anderes Problem, welches für unterschiedliche CPUs auch jeweils anders gelöst werden muss. Aber selbst wenn wir es nicht vollständig hinbekommen die Abhängigkeiten vollständig zu berücksichtigen, so können die NOP-Befehle (zum Ausrichten der Zieladresse) doch zumindest das Problem mit der Abhängigkeit schon etwas abmildern, wenn wir die NOP-Befehle dort zwischen plazieren wo es Abhängikeiten gibt.

Auch gibt es nicht nur den einen NOP-Befehl, sondern auch noch equivalente Befehle, die man als Alternative zum NOP-Befehl verwenden kann.

Code: Alles auswählen

Table 4-12. Recommended Multi-Byte Sequence of NOP Instruction

Length   Assembly                                   Byte Sequence
2 bytes  66 NOP                                     66 90H
3 bytes  NOP DWORD ptr [EAX]                        0F 1F 00H
4 bytes  NOP DWORD ptr [EAX + 00H]                  0F 1F 40 00H
5 bytes  NOP DWORD ptr [EAX + EAX*1 + 00H]          0F 1F 44 00 00H
6 bytes  66 NOP DWORD ptr [EAX + EAX*1 + 00H]       66 0F 1F 44 00 00H
7 bytes  NOP DWORD ptr [EAX + 00000000H]            0F 1F 80 00 00 00 00H
8 bytes  NOP DWORD ptr [EAX + EAX*1 + 00000000H]    0F 1F 84 00 00 00 00 00H
9 bytes  66 NOP DWORD ptr [EAX + EAX*1 + 00000000H] 66 0F 1F 84 00 00 00 00 00H
Dirk
Antworten