8086 ASM Bresenham's Line Algorithm

Question

As part of a first year university course in computer architecture some time ago we were tasked with learning 8086 ASM. The final course work required creating a small animation of shapes moving around the screen changing colours and the like.

As I would not expect anyone to review 720 lines of assembler I'm just going to provide my implementation of Bresenham's Line Algorithm.

Note that this is not the entire program but a single macro from the working program.

Also note that at the time of writing I had little to no experience with 8086 ASM (I still don't in fact), but I'm very interested in knowing how I did and how it could have been improved upon.

If anyone is interested in reviewing the rest of the project as well (it can be done in small parts) then let me know.

;=========================================================================================================
;                       BRESENHAM LINE ALGORITHM (lx1,ly1)-(lx2,ly2)
;=========================================================================================================
line macro lx1, ly1, lx2, ly2
    local ldxsetup1, ldxsetup2, ldysetup1, ldysetup2
    local lxisetup1, lxisetup2, lxisetupexit, lyisetup1, lyisetup2, lyisetupexit
    local numsetup1, numsetup2, numsetupexit
    local lloopstart, lloopif, lloopifexit, lloopend
    pushall
    mov ax, lx2
    sub ax, lx1
    cmp ax, 0
    jge ldxsetup2
ldxsetup1:
    mov bx, -1
    mul bx
ldxsetup2:
    mov ldx, ax
    mov ax, ly2
    sub ax, ly1
    cmp ax, 0
    jge ldysetup2
ldysetup1:
    mov bx, -1
    mul bx
ldysetup2:
    mov ldy, ax
    mov ax, lx1
    mov lx, ax
    mov ax, ly1
    mov ly, ax
    mov ax, lx2
    cmp ax, lx1
    jge lxisetup1
    jmp lxisetup2
lxisetup1:
    mov ax, 1
    jmp lxisetupexit
lxisetup2:
    mov ax, -1
lxisetupexit:
    mov lxi1, ax
    mov lxi2, ax
    mov ax, ly2
    cmp ax, ly1
    jge lyisetup1
    jmp lyisetup2
lyisetup1:
    mov ax, 1
    jmp lyisetupexit
lyisetup2:
    mov ax, -1
lyisetupexit:
    mov lyi1, ax
    mov lyi2, ax
    mov ax, ldx
    mov bx, ldy
    cmp ax, bx
    jge numsetup1
    jmp numsetup2
numsetup1:
    mov ax, 0
    mov lxi1, ax
    mov lyi2, ax
    mov ax, ldx
    mov lden, ax
    mov lnumpix, ax
    shr ax, 1
    mov lnum, ax
    mov ax, ldy
    mov lnumadd, ax
    jmp numsetupexit
numsetup2:
    mov ax, 0
    mov lxi2, ax
    mov lyi1, ax
    mov ax, ldy
    mov lden, ax
    mov lnumpix, ax
    shr ax, 1
    mov lnum, ax
    mov ax, ldx
    mov lnumadd, ax
numsetupexit:
    mov ax, lnum
    mov dx, 0
lloopstart:
    cmp dx, lnumpix
    jg lloopend
    plot lx, ly
    add ax, lnumadd
    cmp ax, lden
    jge lloopif
    jmp lloopifexit
lloopif:
    sub ax, lden
    mov bx, lx
    add bx, lxi1
    mov lx, bx
    mov bx, ly
    add bx, lyi1
    mov ly, bx
lloopifexit:
    mov bx, lx
    add bx, lxi2
    mov lx, bx
    mov bx, ly
    add bx, lyi2
    mov ly, bx
    inc dx
    jmp lloopstart
lloopend:
    popall
endm
;=========================================================================================================

Here's the definitions of pushall and popall:

;=========================================================================================================
;                       PUSH ALL DATA TO STACK
;=========================================================================================================
pushall macro
    push ax
    push bx
    push cx
    push dx
endm
;=========================================================================================================
;=========================================================================================================
;                       POP ALL DATA FROM STACK
;=========================================================================================================
popall macro
    pop dx
    pop cx
    pop bx
    pop ax
endm
;=========================================================================================================

Answer 1

A few quick remarks

• Because it was written as a macro, this lengthy code will be inserted everywhere that you need to draw a line. This is wasteful. Better write this kind of code as a procedure that gets called.
• You definitely need to add comments to the code. The names used for the labels don't make up for the lack of comments!
• Because a lowercase "l" and the digit "1" are so resemblant, I found it hard at times to easily read all those variable names that start with an 'l'.

Analysis

mov ax, lx2
sub ax, lx1
cmp ax, 0
jge ldxsetup2

In code like this there's no need for an explicit cmp ax, 0 as the preceding sub ax, lx1 already defines all the necessary processor flags for correct operation of the following jge ldxsetup2.

---

ldxsetup1:
  mov bx, -1
  mul bx

This part is essentially calculating the opposite of the number in the AX register. Why not use the neg ax instruction? It's well suited for the task. It gives smaller code and doesn't clobber the BX and DX registers.
Also note that the ldxsetup1 label isn't really needed in this program. It's noise.

---

  mov ax, lx2
  cmp ax, lx1
  jge lxisetup1
  jmp lxisetup2
lxisetup1:
  mov ax, 1
  jmp lxisetupexit
lxisetup2:
  mov ax, -1
lxisetupexit:
  mov lxi1, ax
  mov lxi2, ax

In this code there's a lot to optimize.

Step 1, remove a redundant jmp and the now unnecessary label lxisetup1:

  mov  ax, lx2
  cmp  ax, lx1
  jl   lxisetup2      ;Opposite conditional jump and fall through
  mov  ax, 1
  jmp  lxisetupexit
lxisetup2:
  mov  ax, -1
lxisetupexit:
  mov  lxi1, ax
  mov  lxi2, ax

Step 2, simplify even more by using an extra register and less jumping around:

  mov  bx, -1      ;BX=-1 Increment if x2 < x1
  mov  ax, lx2
  cmp  ax, lx1
  jl   lxisetupexit
  neg  bx          ;BX=1  Increment if x2 >= x1
lxisetupexit:
  mov  lxi1, bx
  mov  lxi2, bx

Step 3, combine the calculation of the increments with the calculation of the delta's:

  mov  bx, 1       ;BX=1  Increment if x2 >= x1
  mov  ax, lx2
  sub  ax, lx1
  jge  ldxsetup2
  neg  bx          ;BX=-1 Increment if x2 < x1
  neg  ax          ;Abs(x2-x1)
ldxsetup:
  mov  ldx, ax
  mov  lxi1, bx
  mov  lxi2, bx

The resulting code is much smaller and the number of local labels is halved.

---

  cmp ax, bx
  jge numsetup1
  jmp numsetup2
numsetup1:

Here once again, use the opposite conditional jump and otherwise fall through:

cmp  ax, bx
jl   numsetup2

---

numsetup1:
  mov ax, 0
  mov lxi1, ax
  mov lyi2, ax
  ...
numsetup2:
  mov ax, 0
  mov lxi2, ax
  mov lyi1, ax

This is the most bizarre part of your program. These 4 variables are zeroed, never again re-assigned, yet happily used in lots of additions that as a consequence don't really add anything! That is unless the plot lx, ly macro call changes them. It would have been great to see how plot is defined because now it's next to impossible to verify that this program actually draws a line or just a single dot.

---

If anyone is interested in reviewing the rest of the project as well (it can be done in small parts) then let me know.

I would love to see the rest. I don't find 720 lines of code much. As you'll see from my profile I tend to turn in long papers myself.

Answer 2

These are just some quick thoughts, not a detailed analysis.

• Comments. Enough said.
• If a conditional jump (like jge) is not taken, execution just continues with the next instruction. So this seems redundant (likewise with numsetup1):

---

    jge lxisetup1
    jmp lxisetup2
lxisetup1:

---

could be written as:

---

    jl lxisetup2

---

• You are repeatedly moving -1 into registers and using it in other ways. Why not make use of an additional register (say si)? Set it to -1 at the top of this routine (remember to push/pop it if your calling convention requires it) and use it as needed: mul si, mov ax, si.
• A common shortcut for zeroing registers is xor ax, ax. Produces slightly smaller code.
• Looking at your final loop, you have:

---

lloopstart:
    cmp dx, lnumpix
    jg lloopend
    inc dx
    jmp lloopstart
lloopend:

This means that you will be doing 2 jumps in a row (jmp lloopstart, jg lloopend). An alternative might be:

---

    cmp dx, lnumpix
    jg lloopend
lloopstart:
    inc dx
    cmp dx, lnumpix
    jle lloopstart
lloopend:

Instead of having your loop count up (for x=0 to 10), sometimes having your loop count down to zero (for x=10 to 0) can produce (slightly) more efficient code (not sure it would work in this case):

---

mov dx, lnumpix
lloopstart:
    dec dx
    jnz lloopstart