Home > Enterprise >  Line drawing algorithm in assembly
Line drawing algorithm in assembly

Time:03-09

I'm trying to create a line-drawing algorithm in assembly (more specifically Bresenham's line algorithm). After trying an implementation of this algorithm, the algorithm fails to work properly even though I almost exactly replicated the plotLineLow() function from this Wikipedia page.

It should be drawing a line between 2 points, but when I test it, it draws points in random places in the window. I really don't know what could be going wrong because debugging in assembly is difficult.

I'm using NASM to convert the program to binary, and I run the binary in QEMU.

[bits 16]                                               ; 16-bit mode
[org 0x7c00]                                            ; memory origin

section .text                                           ; code segmant
    global _start                                       ; tells the kernal where to begin the program
_start:                                                 ; where to start the program

; main
call cls                                                ; clears the screen
update:                                                 ; main loop
    mov cx, 0x0101                                      ; line pos 1
    mov bx, 0x0115                                      ; line pos 2
    call line                                           ; draws the line

    jmp update                                          ; jumps to the start of the loop


; functions
cls:                                                    ; function to clear the screen
    mov ah, 0x00                                        ; set video mode
    mov al, 0x03                                        ; text mode (80x25 16 colours)
    int 0x10                                            ; BIOS interrupt
    ret                                                 ; returns to where it was called


point:                                                  ; function to draw a dot at a certain point (dx)
    mov bx, 0x00ff                                      ; clears the bx register and sets color
    mov cx, 0x0001                                      ; clears the cx register and sets print times
    mov ah, 0x02                                        ; set cursor position
    int 0x10                                            ; BIOS interrupt

    mov ah, 0x09                                        ; write character
    mov al, ' '                                         ; character to write
    int 0x10                                            ; BIOS interrupt
    ret                                                 ; returns to where it was called


line:                                                   ; function to draw a line at two points (bx, cx)
    push cx                                             ; saves cx for later
    push bx                                             ; saves bx for later

    sub bh, ch                                          ; gets the value of dx
    mov [dx_L], bh                                      ; puts it into dx
    sub bl, cl                                          ; gets the value of dy
    mov [dy_L], bl                                      ; puts it into dy

    mov byte [yi_L], 1                                  ; puts 1 into yi (positive slope)

    cmp byte [dy_L], 0                                  ; checks if the slope is negative
    jl .negative_y                                      ; jumps to the corresponding sub-label
    jmp .after_negative_y                               ; if not, jump to after the if

    .negative_y:                                        ; if statement destination
        mov byte [yi_L], -1                             ; sets yi to -1 (negative slope)
        neg byte [dy_L]                                 ; makes dy negative as well
    .after_negative_y:                                  ; else statement destination

    mov ah, [dy_L]                                      ; moves dy_L into a temporary register
    add ah, ah                                          ; multiplies it by 2
    sub ah, [dx_L]                                      ; subtracts dx from that
    mov [D_L], ah                                       ; moves the value into D

    pop bx                                              ; pops bx to take a value off
    mov [y_L], bh                                       ; moves the variable into the output
    
    pop cx                                              ; pops the stack back into cx
    mov ah, bh                                          ; moves x0 into ah
    mov al, ch                                          ; moves x1 into al

    .loop_x:                                            ; loop to go through every x iteration
        mov dh, ah                                      ; moves the iteration count into dh
        mov dl, [y_L]                                   ; moves the y value into dl to be plotted
        call point                                      ; calls the point function

        cmp byte [D_L], 0                               ; compares d to 0
        jg .greater_y                                   ; if greater, jumps to the if statement
        jmp .else_greater_y                             ; if less, jumps to the else statement

        mov bh, [dy_L]                                  ; moves dy into a temporary register
        .greater_y:                                     ; if label
            mov bl, [yi_L]                              ; moves yi into a temporary register
            add [y_L], bl                               ; increments y by the slope
            sub bh, [dx_L]                              ; dy and dx
            add bh, bh                                  ; multiplies bh by 2
            add [D_L], bh                               ; adds bh to D
            jmp .after_greater_y                        ; jumps to after the if statement
        .else_greater_y:                                ; else label
            add bh, bh                                  ; multiplies bh by 2
            add [D_L], bh                               ; adds bh to D
        .after_greater_y:                               ; after teh if statement

        inc ah                                          ; increments the loop variable
        cmp ah, al                                      ; checks to see if the loop should end
        je .end_loop_x                                  ; if it ended jump to the end of teh loop
        jmp .loop_x                                     ; if not, jump back to the start of the loop

    .end_loop_x:                                        ; place to send the program when the loop ends

    ret                                                 ; returns to where it was called


section .data                                           ; data segmant
dx_L: db 0                                              ; used for drawing lines
dy_L: db 0                                              ; ^
yi_L: db 0                                              ; ^
xi_L: db 0                                              ; ^
D_L: db 0                                               ; ^
y_L: db 0                                               ; ^
x_L: db 0                                               ; ^


section .text                                           ; code segmant
; boot the OS
times 510-($-$$) db 0                                   ; fills up bootloader space with empty bytess
db 0x55, 0xaa                                           ; defines the bootloader bytes

CodePudding user response:

  1. I see no video mode

    just 80x25 text VGA mode (mode = 3) you set at start with cls so how can you render points? You should set the video mode you want assuming VGA or VESA/VBE see the link above.

  2. why to heck use VGA BIOS for point rendering?

    that will be slooooooooow and I have no idea what it does when no gfx mode is present. You can render points by direct access to VRAM (at segment A000h) Ideal use 8/16/24/32bit video modes as they have pixels aligned to BYTEs ... my favorite is 320x200x256c (mode = 19) as it fits into 64K segment so no paging is needed and pixels are Bytes.

    In case you are using characters instead of pixels then you still can use access to VRAM in the same way just use segment B800h and chars are 16 bit (color and ASCII).

  3. integer DDA is faster then Bresenham on x86 CPUs since 80386

    I do not code in NASM for around 2 decades and closest thing to line I found in my archive is this:

     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     line:   pusha       ;ax=x0,bx=x1,dl=y0,dh=y1,cl=col
         push    ax
         mov si,bx
         sub si,ax
         sub ah,ah
         mov al,dl
         mov bx,ax
         mov al,dh
         sub ax,bx
         mov di,ax
         mov ax,320
         sub dh,dh
         mul dx
         pop bx
         add ax,bx
         mov bp,ax
         mov ax,1
         mov bx,320
         cmp si,32768
         jb  .r0
         neg si
         neg ax
     .r0:    cmp di,32768
         jb  .r1
         neg di
         neg bx
     .r1:    cmp si,di
         ja  .r2
         xchg    ax,bx
         xchg    si,di
     .r2:    mov [.ct],si
     .l0:    mov [es:bp],cl
         add bp,ax
         sub dx,di
         jnc .r3
         add dx,si
         add bp,bx
     .r3:    dec word [.ct]
         jnz .l0
         popa
         ret
     .ct:    dw  0
     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    

    So you have something to cross check (took me a while to find it in my archives as I coded whole 3D polygonal engines with textures at that time so I do not have much 2D code in NASM...)

    The example expects 320x200x256c VGA video mode

  4. If you were writing a DOS .com file, things would be a bit simpler: segment registers would all be set the same, with your code/data at offset 100 from them. And you could end with ret.

    [BITS 16]
    [ORG 100h]
    
    [SEGMENT .text]
        ret
    

As @bitRAKE and @PeterCoders pointed out in case You run this in BOOT SECTOR the org is ok. However in such case there is no OS present so if you were going to do more with the stack or any other block of memory outside your 512 bytes, you'd want to point the stack to somewhere known. (It does start out valid, though, because interrupts are enabled.)

More importantly, you need to initialize DS to match your ORG setting, so ds:org reaches a linear address of 7C00. With org 0x7c00, that means you want DS=0. Otherwise instructions like mov [dx_L], bh would be using memory at some unknown location.

    [BITS 16]
    [ORG 7C00h]
    
    [SEGMENT .text]
        mov ax,0000h
        mov ds,ax          ; DS=0 to match ORG
        mov ss,ax          ; if you set SS:SP at all, do it back-to-back
        mov sp,7C00h       ; so an interrupt can't fire half way through.
        ; here do your stuff
    l0: 
      hlt      ; save power
      jmp l0  
  1. Hope you are using VC or NC configured as IDE for NASM and not compiling/linking manually

    This one is usable in MS-DOS so if you are running BOT SECTOR you out of luck. Still You can create a *.com executable debug and once its working in dos change to BOOT SECTOR...

    see Is there a way to link object files for DOS from Linux? on how to setup MS-DOS Volkov commander to automatically compile and link your asm source code just by hitting enter on it ... You can also run it just by adding line to the vc.ext line ... but I prefer not to so you can inspect error log first

  2. Convenient debugging

    You can try to use MS-DOS (DOSBox) with ancient Borland Turbo C/C or Pascal and use their inline asm { .... } code which can be traced and stepped directly in the IDE. However it uses TASM (different syntax to NASM) and have some restrictions ...

    Sadly I never saw any decent IDE for asm on x86 platform. The best IDE for asm I worked with was Herkules on ZX Spectrum ... was possible to done things even modern C IDEs doesnt have.

  • Related