0

I've been trying to implement Bresenham's line algorithm for a few days but keep facing strange issues. I am able to draw some lines, but others just seem to not work and result in an infinite loop. I have spent hours trying to get Qemu to work and tried a few simulators but can't seem to sort the problem out. Below is the code I have that is supposed to draw the line itself.

drawline:
; r0 = screen_address
; r1 = x0
; r2 = y0
; r3 = x1
; r4 = y1
; r5 = colour

push {r6-r10}   ; store the registers we will alter, thoughtful, right?
cmp r1,r3       ; compare x0 and x1
subgt r6,r1,r3  ; deltax = x0 - x1
movgt r7,#-1    ; stepx = -1
suble r6,r3,r1  ; deltax = x1 - x0
movle r7,#1     ; stepx = 1

cmp r2, r4      ; compare y1 and y0
subgt r8,r4,r2  ; deltay = y1 - y0
movgt r9,#-1    ; stepy = -1
suble r8,r2,r4  ; deltay = y0 - y1
movle r9,#1     ; stepy = 1

add r10,r6,r8   ; error = deltax - deltay

line_pixel_loop:
    teq r1,r3
    teqeq r2,r4
    popeq {r6-r10}
    bxeq lr

    push {r3, lr}   ; store registers which we will alter
    ; the following are inferred:
    ; r0 = screen address
    ; r1 = x, current
    ; r2 = y, current
    mov r3,r5       ; colour
    bl drawpixel    ; draw the pixel
    pop {r3, lr}    ; restore the altered registers

    cmp r8,r10, lsl#1   ; compare deltay (now negative) with 2 * error
    addle r10, r8       ; if less than: error += deltay
    addle r1, r7        ; if less than: x0 += stepx

    cmp r6,r10, lsl #1  ; compare deltax with 2 * error
    addge r10, r6       ; if greater than: error += stepx
    addge r2, r9        ; if greater than: y0 += stepy

    ; cmp r1,r3         ; compare x0 and x1
    ; cmpeq r2,r4   ; if equal: compare y0 and y1
    ; bne line_pixel_loop   ; if not equal, continue the loop
    b line_pixel_loop


pop {r6-r10} ; clean up

bx lr ; return

These two lines draw without issue:

push {r0-r5}
mov r0,r7     ;screen
mov r1,#300   ;x0
mov r2,#100   ;y0
mov r3,#200   ;x1
mov r4,#200   ;y1
mov r5,r6     ;colour
bl drawline
pop {r0-r5}

push {r0-r5}
mov r0,r7     ;screen
mov r1,#300   ;x0
mov r2,#100   ;y0
mov r3,#400   ;x1
mov r4,#200   ;y1
mov r5,r6     ;colour
bl drawline
pop {r0-r5}

This line does not draw and prevents the program from executing further:

push {r0-r5}
mov r0,r7     ;screen
mov r1,#350   ;x0
mov r2,#265   ;y0
mov r3,#353   ;x1
mov r4,#266   ;y1
mov r5,r6     ;colour
bl drawline
pop {r0-r5}
Terry
  • 616
  • 6
  • 16
  • 1
    [How to debug ARM asm in QEMU on an x86 Linux desktop](http://stackoverflow.com/a/39504457/224132) – Peter Cordes Oct 23 '16 at 10:37
  • So what exactly does happen in your code with the line that doesn't work? When you single-step it in a debugger, or ^c to get a debugger prompt while it's running, what values are in registers? See [ask] / [mcve] for tips on what to include when asking for debugging help. – Peter Cordes Oct 23 '16 at 10:40
  • Well, I just stepped through that with the 'problematic' input in a simulator and it looked fine - the problem must be related to `drawpixel` or the calling code. I assume those are also handwritten assembly (as you're not using standard calling conventions)? – Notlikethat Oct 23 '16 at 11:41
  • Using `eq` for the termination condition means if you overstep you will continue until integer wrap around. Your problematic input seems to be small deltaX=3, deltaY=1. If you step past a point your termination will never happen. Also r10 (error) is only added to. Shouldn't it alternate between positive and negative? According to [Wiki breshnam algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Algorithm) you need to add/sub the error (as capital 'D' there). Are you only intending to draw one quadrant or is this suppose to handle all of them? – artless noise Oct 23 '16 at 15:26
  • https://godbolt.org/g/tpyeyo is a 'C' compiled example. – artless noise Oct 23 '16 at 15:54
  • @artlessnoise deltay is always negative. deltay is assigned assigned to the smaller y minus the larger one. Thus when delta y is added to error it is adding a negative number. – Terry Oct 24 '16 at 07:00

0 Answers0