Previous Table of Contents Next


LISTING 35.3 L35-3.ASM

; Fast assembler implementation of Bresenham’s line-drawing algorithm
; for the EGA and VGA. Works in modes 0Eh, 0Fh, 10h, and 12h.
; Borland C++ near-callable.
; Bit mask accumulation technique when |DeltaX| >= |DeltaY|
;  suggested by Jim Mackraz.
;
; Assembled with TASM
;
; By Michael Abrash
;
;****************************************************************
; C-compatible line-drawing entry point at _EVGALine.           *
; Near C-callable as:                                           *
;       EVGALine(X0, Y0, X1, Y1, Color);                        *
;****************************************************************
;

       model small
       .code

;
; Equates.
;
EVGA_SCREEN_WIDTH_IN_BYTES  equ  80        ;memory offset from start of
                                           ; one row to start of next
                                           ; in display memory
EVGA_SCREEN_SEGMENT         equ  0a000h    ;display memory segment
GC_INDEX                    equ  3ceh      ;Graphics Controller
                                           ; Index register port
SET_RESET_INDEX             equ  0         ;indexes of needed
ENABLE_SET_RESET_INDEX      equ  1         ; Graphics Controller
BIT_MASK_INDEX              equ  8         ; registers

;
; Stack frame.
;
EVGALineParms   struc
                dw      ?               ;pushed BP
                dw      ?               ;pushed return address (make double
                                        ; word for far call)
X0              dw      ?               ;starting X coordinate of line
Y0              dw      ?               ;starting Y coordinate of line
X1              dw      ?               ;ending X coordinate of line
Y1              dw      ?               ;ending Y coordinate of line
Color           db      ?               ;color of line
                db      ?               ;dummy to pad to word size
EVGALineParms   ends

;****************************************************************
; Line drawing macros.                                          *
;****************************************************************

;
; Macro to loop through length of line, drawing each pixel in turn.
; Used for case of |DeltaX| >= |DeltaY|.
; Input:
;       MOVE_LEFT: 1 if DeltaX < 0, 0 else
;       AL: pixel mask for initial pixel
;       BX: |DeltaX|
;       DX: address of GC data register, with index register set to
;               index of Bit Mask register
;       SI: DeltaY
;       ES:DI: display memory address of byte containing initial
;               pixel
;
LINE1   macro   MOVE_LEFT
        local   LineLoop, MoveXCoord, NextPixel, Line1End
        local   MoveToNextByte, ResetBitMaskAccumulator
        mov     cx,bx                   ;# of pixels in line
        jcxz    Line1End                ;done if there are no more pixels
                                        ; (there’s always at least the one pixel
                                        ; at the start location)
        shl     si,1                    ;DeltaY * 2
        mov     bp,si                   ;error term
        sub     bp,bx                   ;error term starts at DeltaY * 2 - DeltaX
        shl     bx,1                    ;DeltaX * 2
        sub     si,bx                   ;DeltaY * 2 - DeltaX * 2 (used in loop)
        add     bx,si                   ;DeltaY * 2 (used in loop)
        mov     ah,al                   ;set aside pixel mask for initial pixel
                                        ; with AL (the pixel mask accumulator) set
                                        ; for the initial pixel
LineLoop:
;
; See if it’s time to advance the Y coordinate yet.
;
        and     bp,bp                   ;see if error term is negative
        js      MoveXCoord              ;yes, stay at the same Y coordinate
;
; Advance the Y coordinate, first writing all pixels in the current
; byte, then move the pixel mask either left or right, depending
; on MOVE_LEFT.
;
        out     dx,al                   ;set up bit mask for pixels in this byte
        xchg    byte ptr [di],al
                                        ;load latches and write pixels, with bit mask
                                        ; preserving other latched bits. Because
                                        ; set/reset is enabled for all planes, the
                                        ; value written actually doesn’t matter
        add     di,EVGA_SCREEN_WIDTH_IN_BYTES   ;increment Y coordinate
        add     bp,si                   ;adjust error term back down
;
; Move pixel mask one pixel (either right or left, depending
; on MOVE_LEFT), adjusting display memory address when pixel mask wraps.
;
if MOVE_LEFT
        rol     ah,1                    ;move pixel mask 1 pixel to the left
else
        ror     ah,1                    ;move pixel mask 1 pixel to the right
endif
        jnc     ResetBitMaskAccumulator ;didn’t wrap to next byte
        jmp     short MoveToNextByte    ;did wrap to next byte
;
; Move pixel mask one pixel (either right or left, depending
; on MOVE_LEFT), adjusting display memory address and writing pixels
; in this byte when pixel mask wraps.
;
MoveXCoord:
        add     bp,bx                   ;increment error term & keep same
if MOVE_LEFT
        rol     ah,1                    ;move pixel mask 1 pixel to the left
else
        ror     ah,1                    ;move pixel mask 1 pixel to the right
endif
        jnc     NextPixel               ;if still in same byte, no need to
                                        ; modify display memory yet
        out     dx,al                   ;set up bit mask for pixels in this byte.
        xchg    byte ptr [di],al
                                        ;load latches and write pixels, with bit mask
                                        ; preserving other latched bits. Because
                                        ; set/reset is enabled for all planes, the
                                        ; value written actually doesn’t matter
MoveToNextByte:
if MOVE_LEFT
        dec     di                      ;next pixel is in byte to left
else
        inc     di                      ;next pixel is in byte to right
endif
ResetBitMaskAccumulator:
        sub     al,al                   ;reset pixel mask accumulator
NextPixel:
        or      al,ah                   ;add the next pixel to the pixel mask
                                        ; accumulator
        loop    LineLoop
;
; Write the pixels in the final byte.
;
Line1End:
        out     dx,al                   ;set up bit mask for pixels in this byte
        xchg    byte ptr [di],al
                                        ;load latches and write pixels, with bit mask
                                        ; preserving other latched bits. Because
                                        ; set/reset is enabled for all planes, the
                                        ; value written actually doesn’t matter
        endm

;
; Macro to loop through length of line, drawing each pixel in turn.
; Used for case of DeltaX < DeltaY.
; Input:
;       MOVE_LEFT: 1 if DeltaX < 0, 0 else
;       AL: pixel mask for initial pixel
;       BX: |DeltaX|
;       DX: address of GC data register, with index register set to
;               index of Bit Mask register
;       SI: DeltaY
;       ES:DI: display memory address of byte containing initial
;               pixel
;
LINE2   macro   MOVE_LEFT
        local   LineLoop, MoveYCoord, ETermAction, Line2End
        mov     cx,si                  ;# of pixels in line
        jcxz    Line2End               ;done if there are no more pixels
        shl     bx,1                   ;DeltaX * 2
        mov     bp,bx                  ;error term
        sub     bp,si                  ;error term starts at DeltaX * 2 - DeltaY
        shl     si,1                   ;DeltaY * 2
        sub     bx,si                  ;DeltaX * 2 - DeltaY * 2 (used in loop)
        add     si,bx                  ;DeltaX * 2 (used in loop)
;
; Set up initial bit mask & write initial pixel.
;
        out     dx,al
        xchg    byte ptr [di],ah
                                       ;load latches and write pixel, with bit mask
                                       ; preserving other latched bits. Because
                                       ; set/reset is enabled for all planes, the
                                       ; value written actually doesn’t matter
LineLoop:
;
; See if it’s time to advance the X coordinate yet.
;
        and     bp,bp                  ;see if error term is negative
        jns     ETermAction            ;no, advance X coordinate
        add     bp,si                  ;increment error term & keep same
        jmp     short MoveYCoord       ; X coordinate
ETermAction:
;
; Move pixel mask one pixel (either right or left, depending
; on MOVE_LEFT), adjusting display memory address when pixel mask wraps.
;
if MOVE_LEFT
        rol     al,1
        sbb     di,0
else
        ror     al,1
        adc     di,0
endif
        out     dx,al                  ;set new bit mask
        add     bp,bx                  ;adjust error term back down
;
; Advance Y coordinate.
;
MoveYCoord:
        add     di,EVGA_SCREEN_WIDTH_IN_BYTES
;
; Write the next pixel.
;
        xchg    byte ptr [di],ah
                                       ;load latches and write pixel, with bit mask
                                       ; preserving other latched bits. Because
                                       ; set/reset is enabled for all planes, the
                                       ; value written actually doesn’t matter
;
        loop    LineLoop
Line2End:
        endm

;****************************************************************
; Line drawing routine.                                         *
;****************************************************************

        public  _EVGALine
_EVGALine       proc    near
        push    bp
        mov     bp,sp
        push    si                     ;preserve register variables
        push    di
        push    ds
;
; Point DS to display memory.
;
        mov     ax,EVGA_SCREEN_SEGMENT
        mov     ds,ax
;
; Set the Set/Reset and Set/Reset Enable registers for
; the selected color.
;
        mov     dx,GC_INDEX
        mov     al,SET_RESET_INDEX
        out     dx,al
        inc     dx
        mov     al,[bp+Color]
        out     dx,al
        dec     dx
        mov     al,ENABLE_SET_RESET_INDEX
        out     dx,al
        inc     dx
        mov     al,0ffh
        out     dx,al
;
; Get DeltaY.
;
        mov     si,[bp+Y1]                 ;line Y start
        mov     ax,[bp+Y0]                 ;line Y end, used later in
                                               ;calculating the start address
        sub     si,ax                          ;calculate DeltaY
        jns     CalcStartAddress               ;if positive, we’re set
;
; DeltaY is negative — swap coordinates so we’re always working
; with a positive DeltaY.
;
        mov     ax,[bp+Y1]                 ;set line start to Y1, for use
                                               ; in calculating the start address
        mov     dx,[bp+X0]
        xchg    dx,[bp+X1]
        mov     [bp+X0],dx                 ;swap X coordinates
        neg     si                             ;convert to positive DeltaY
;
; Calculate the starting address in display memory of the line.
; Hardwired for a screen width of 80 bytes.
;
CalcStartAddress:
        shl     ax,1                   ;Y0 * 2 ;Y0 is already in AX
        shl     ax,1                   ;Y0 * 4
        shl     ax,1                   ;Y0 * 8
        shl     ax,1                   ;Y0 * 16
        mov     di,ax
        shl     ax,1                   ;Y0 * 32
        shl     ax,1                   ;Y0 * 64
        add     di,ax                  ;Y0 * 80
        mov     dx,[bp+X0]
        mov     cl,dl                  ;set aside lower 3 bits of column for
        and     cl,7                   ; pixel masking
        shr     dx,1
        shr     dx,1
        shr     dx,1                   ;get byte address of column (X0/8)
        add     di,dx                  ;offset of line start in display segment
;
; Set up GC Index register to point to the Bit Mask register.
;
        mov     dx,GC_INDEX
        mov     al,BIT_MASK_INDEX
        out     dx,al
        inc     dx                     ;leave DX pointing to the GC Data register
;
; Set up pixel mask (in-byte pixel address).
;
        mov     al,80h
        shr     al,cl
;
; Calculate DeltaX.
;
        mov     bx,[bp+X1]
        sub     bx,[bp+X0]
;
; Handle correct one of four octants.
;
        js      NegDeltaX
        cmp     bx,si
        jb      Octant1
;
; DeltaX >= DeltaY >= 0.
;
        LINE1   0
        jmp     EVGALineDone
;
; DeltaY > DeltaX >= 0.
;
Octant1:
        LINE2   0
        jmp     short EVGALineDone
;
NegDeltaX:
        neg     bx      ;|DeltaX|
        cmp     bx,si
        jb      Octant2
;
; |DeltaX| >= DeltaY and DeltaX < 0.
;
        LINE1   1
        jmp     short EVGALineDone
;
; |DeltaX| < DeltaY and DeltaX < 0.
;
Octant2:
        LINE2   1
;
EVGALineDone:
;
; Restore EVGA state.
;
        mov     al,0ffh
        out     dx,al                  ;set Bit Mask register to 0ffh
        dec     dx
        mov     al,ENABLE_SET_RESET_INDEX
        out     dx,al
        inc     dx
        sub     al,al
        out     dx,al                  ;set Enable Set/Reset register to 0
;
        pop     ds
        pop     di
        pop     si
        pop     bp
        ret
_EVGALine       endp

        end

An explanation of the workings of the code in Listing 35.3 would be a lengthy one, and would be redundant since the basic operation of the code in Listing 35.3 is no different from that of the code in Listing 35.1, although the implementation is much changed due to the nature of assembly language and also due to designing for speed rather than for clarity. Given that you thoroughly understand the C implementation in Listing 35.1, the assembly language implementation in Listing 35.3, which is well-commented, should speak for itself.

One point I do want to make is that Listing 35.3 incorporates a clever notion for which credit is due Jim Mackraz, who described the notion in a letter written in response to an article I wrote long ago in the late and lamented Programmer’s Journal. Jim’s suggestion was that when drawing lines for which |DeltaX| is greater than |DeltaY|, bits set to 1 for each of the pixels controlled by a given byte can be accumulated in a register, rather than drawing each pixel individually. All the pixels controlled by that byte can then be drawn at once, with a single access to display memory, when all pixel processing associated with that byte has been completed. This approach can save many OUTs and many display memory reads and writes when drawing nearly-horizontal lines, and that’s important because EGAs and VGAs hold the CPU up for a considerable period of time on each I/O operation and display memory access.

All too many PC programmers fall into the high-level-language trap of thinking that a good algorithm guarantees good performance. Not so: As our two implementations of Bresenham’s algorithm graphically illustrate (pun not originally intended, but allowed to stand once recognized), truly great PC code requires both a good algorithm and a good assembly implementation. In Listing 35.3, we’ve got y-oh-my, isn’t it fun?


Previous Table of Contents Next

Graphics Programming Black Book © 2001 Michael Abrash