I am unable to draw a circle using midpoint algorithm in 8086 Assembly with Direct Memory Access

I have an assignment in which I am supposed to make shapes move and change shapes with colors. I haven't been successful at drawing an octant of a circle in the first place. Supposed to use Intel 8086 Assembly Language using TASM in DMA mode. (mode 19) I was thinking if I could finish making a circle, I could animate it and change shapes. I could not figure out whether the Algorithm is wrong or the code.

.model small
.stack 256

.code 
startaddr   dw  0a000h  ;start of video memory   
color   db  3 
xc dw  160
yc dw 100
r dw  50 ; radius
x dw 0 
y dw 50 ;radius
pk dw 1
temp dw 1

plot macro r1, r2, r3 ;x,y,color
    mov ax, r2
    mov bx, 320
    mul bx
    add ax, r1
    mov di, ax
    mov al, r3
    mov es:[di], al
endm

start:    
  mov ax, yc
  add y, ax
  mov ah,00    
  mov al, 13h    
  int 10h           ;switch to 320x200 mode  
  mov es, startaddr
  mov dx, y
  mov ax, xc
  add x, ax
  plot x, dx, color
  mov bx, r
  mov pk, bx
  sub pk, 1
  neg pk
  cmp pk, 0
  jge pk1

drawc:
    mov bx, x
    sub bx, xc
    mov ax, y
    sub ax, yc
    mov temp, ax
    cmp bx, temp
    jge keypress

    mov dx, y
    plot x, dx, color

peekay:
    cmp pk, 0
    jg pk1
    mov ax, x
    mov bx, 2
    mul bx
    add ax, pk
    mov pk, ax
    inc x ;x+1
    jmp drawc

pk1:
    dec y
    mov ax, x
    sub ax, y
    mov bx, 2
    mul bx
    add ax, pk
    mov pk, ax
    inc x
    jmp drawc

keypress:    
  mov ah,00    
  int 16h           ;await keypress  

  mov ah,00    
  mov al,03    
  int 10h   

  mov ah,4ch    
  mov al,00         ;terminate program    
  int 21h 
end start

Output

Solution

The code you have so far is difficult to follow because it is so sparsely commented. When you're writing assembly, it's important to comment liberally, explaining what the code is supposed to be doing, because the language itself is not very expressive. Sure, I know what each instruction means, but it's hard for me as a human to keep track of all the enregistered values and their flow throughout. I also have no idea what your code is supposed to be doing at a high level.

Worse, your label names are also meaningless to me when I try to read the code. What is peekay? pk1? I would guess that drawc is DrawCircle, but why not call it that instead? Then you wouldn't even need a comment there because it would be obvious from the name.

As for your actual problem, it looks from the output like you've successfully drawn a line. But that's not really what you want to be drawing. You want to be using the midpoint algorithm to draw a circle. And you're in luck, because that Wikipedia article has sample code implementing this algorithm in C. If you're new to assembly, and struggling with this problem, my recommendation would be to write the code in C first and make sure that you have the algorithm working. Then, you can translate the working C code into assembly. Once you get more comfortable with assembly, you can start to skip steps and write directly in assembly, translating C-style algorithms into assembly instructions in your head. At least, that's what I do, and I still go back to C whenever I get stuck.

So let's steal some C code from Wikipedia:

void DrawCircle(int x0, int y0, int radius)
{
    int x   = radius;
    int y   = 0;
    int err = 0;

    while (x >= y)
    {
        PlotPixel(x0 + x, y0 + y);
        PlotPixel(x0 + y, y0 + x);
        PlotPixel(x0 - y, y0 + x);
        PlotPixel(x0 - x, y0 + y);
        PlotPixel(x0 - x, y0 - y);
        PlotPixel(x0 - y, y0 - x);
        PlotPixel(x0 + y, y0 - x);
        PlotPixel(x0 + x, y0 - y);

        if (err <= 0)
        {
            y   += 1;
            err += 2*y + 1;
        }
        if (err > 0)
        {
            x   -= 1;
            err -= 2*x + 1;
        }
    }
}

Normally, getting the algorithm invented, written, and tested would be the hard part, but we just kind of short-circuited that by ~~stealing from~~ building upon others' work. Now, all we need is the PlotPixel function. That's easy, though---your assembly code already has that part down, since you are successfully drawing a line!

Just so we're both on the same page, the easiest way to do this is to invoke BIOS interrupt 10h, function 0Ch, which plots a pixel in graphics mode. CX contains the x-coordinate of the point, DX contains the y-coordinate, AL contains the color attribute, and BH contains the video page. For simplicity reasons, we'll assume that the video page is 0 (the default). This can be wrapped up in a simple macro, like so:

PlotPixel MACRO x, y, color, videoPage
   mov  cx, x
   mov  dx, y
   mov  bh, videoPage
   mov  ax, (color | (0Ch << 8))   ; AL == color, AH == function 0Ch
   int  10h
ENDM

Phase two is translating the C function into assembly. Because of the repeated calls to the PlotPixel function, as well as the looping constructs, this translation is not going to be a trivial exercise. We're going to end up with a long listing of code. We also have another problem: there aren't enough registers to hold all of our temporary values! This is, of course, quite common on the x86 with its very limited number of general-purpose registers, so we'll do what we always have to do: use the stack. It's slower, but it works. (This code isn't going to be fast anyway.) Here's what I came up with:

; Draws a circle of the specified radius at the specified location
; using the midpoint algorithm.
; 
; Parameters:    DX == center, x
;                CX == center, y
;                BX == radius
;                AL == color
; Clobbers:      <none>
; Returns:       <none>
DrawCircle:
   push bp
   mov  bp, sp
   push dx                       ; xCenter [bp -  2]
   push cx                       ; yCenter [bp -  4]
   push bx                       ; x       [bp -  6]
   push 0                        ; y       [bp -  8]
   push 0                        ; err     [bp - 10]
   
   ; Prepare to plot pixels:
   mov  ah, 0Ch                  ; AH == function 0Ch (plot pixel in graphics mode)
   xor  bx, bx                   ; BH == video page 0       
   
DrawLoop:
   mov  dx, WORD [bp - 6]
   cmp  dx, WORD [bp - 8]
   jl   Finished                 ; (x < y) ? we're finished drawing : keep drawing
   
   ; Plot pixels:       
   mov  cx, WORD [bp - 2]
   mov  dx, WORD [bp - 4]
   add  cx, WORD [bp - 6]        ; CX = xCenter + x
   add  dx, WORD [bp - 8]        ; DX = yCenter + y
   int  10h
   
   mov  cx, WORD [bp - 2]
   sub  cx, WORD [bp - 6]        ; CX = xCenter - x
   int  10h
   
   mov  dx, WORD [bp - 4]
   sub  dx, WORD [bp - 8]        ; DX = yCenter - y
   int  10h
   
   mov  cx, WORD [bp - 2]
   add  cx, WORD [bp - 6]        ; CX = xCenter + x
   int  10h
   
   mov  cx, WORD [bp - 2]   
   mov  dx, WORD [bp - 4]
   add  cx, WORD [bp - 8]        ; CX = xCenter + y
   add  dx, WORD [bp - 6]        ; DX = yCenter + x
   int  10h
   
   mov  cx, WORD [bp - 2]
   sub  cx, WORD [bp - 8]        ; CX = xCenter - y
   int  10h
   
   mov  dx, WORD [bp - 4]
   sub  dx, WORD [bp - 6]        ; DX = yCenter - x
   int  10h
   
   mov  cx, WORD [bp - 2]
   add  cx, WORD [bp - 8]        ; CX = xCenter + y
   int  10h
   
   ; Update state values and check error:
   mov  dx, WORD [bp - 8]
   inc  dx
   mov  WORD [bp - 8], dx
   add  dx, dx                ; DX *= 2
   inc  dx
   add  dx, WORD [bp - 10]
   mov  WORD [bp - 10], dx
   sub  dx, WORD [bp - 6]
   add  dx, dx                ; DX *= 2
   js   DrawLoop              ; DX < 0 ? keep looping : fall through and check error
   inc  dx
   
   dec  cx
   mov  WORD [bp - 6], cx
   add  cx, cx                ; CX *= 2
   neg  cx
   inc  cx                    ; CX = (1 - CX)
   add  WORD [bp - 10], cx
   jmp  DrawLoop              ; keep looping
   
Finished:
   pop  bx                    ; (clean up the stack; no need to save this value)
   pop  bx                    ; (clean up the stack; no need to save this value)
   pop  bx
   pop  cx
   pop  dx
   pop  bp
   ret
END DrawCircle

You'll see that at the top of the function I allocated space on the stack for our temporary values. We will access each of them using an offset from the BP register, as noted in the inline comments.^*

The bulk of the function consists of the main drawing loop, DrawLoop. At the top, we do a comparison to see if we should keep looping. Then we start plotting pixels in earnest, doing the necessary manipulations, just like those shown in the C code from Wikipedia. After plotting, we do some more manipulations, store the results back in our temporary values on the stack, and run another couple of comparisons to see if we should keep looping (again, roughly analogous to the if blocks in the original C code). At the very end, once we're finished, I clean up the stack before returning.

Note that I "inlined" the code from the PlotPixel macro. That allows me to set up the AH and BH registers at the top, and reuse them for all of the calls. This shortens the code slightly, and speeds it up a bit, too. The parallel structure keeps it sufficiently readable (to my eyes, at least).

There's nothing especially tricky going on here, except a couple of my arithmetic manipulations. As should be obvious, adding a register to itself is the same as multiplying it by 2. And I subtract a register from 1 by negating the original value and then incrementing it by 1. These are commented in the code. The only other thing I see worth pointing out is that I use test reg, reg for simple comparisons, instead of cmp reg, 0. The former is shorter and faster.

Just set your video mode, put the parameters into the appropriate registers, and call it!

A yellow circle!

There are certainly ways to speed up this function, but they come at the serious expense of readability and understandability. Make sure that you understand what's going on here first, before reading on!

The big bottlenecks in this code are two-fold:

Using the stack.

There is probably a more creative way to write the code that would make more optimal use of the registers, shuffling values around as necessary to avoid hitting memory as much as possible. But this was too much for my feeble mind to keep track of. It shouldn't be terribly slow---all these values will fit in the cache, after all.

Using the BIOS pixel-plotting function.

This one is extremely slow, even on modern machines. It works well enough to draw a simple circle on the screen, especially on virtualized hardware, but isn't nearly fast enough for complex output of multiple circles. To work around this, you will have to resort to raw bit-twiddling of the video memory, which is not portable. I suppose this is what you mean by "DMA mode". If you do this, you will limit your code to running only on systems with VGA hardware that conforms to the standard specification. You also lose resolution/mode-independence.

Making the change is quite straightforward. I just added a PlotPixel function that does the heavy lifting, and changed the code inside of DrawCircle to call this function instead of the BIOS interrupt (and excised the leading mov ah, 0Ch and xor bx, bx lines):

    ; Plots a pixel by writing a BYTE-sized color value directly to memory,
    ; based on the formula:    0A000h + (Y * 320) + X
    ; 
    ; Parameters: DX == x-coordinate
    ;             CX == y-coordinate
    ;             AL == color
    ; Clobbers:   CX
    ; Returns:    <none>
    PlotPixel:
       push di
  
       mov  di, 0A000h
       mov  es, di            ; ES == video memory offset
  
       mov  di, cx
       add  cx, cx
       add  cx, cx
       add  di, cx
       shl  di, 6             ; Y *= 320
  
       add  di, dx            ; Y += X
  
       mov  BYTE es:[di], al  ; write the color byte to memory at (X, Y)
  
       pop  di
       ret
    END PlotPixel

I suppose you understand this part already, but the reason this works is because in mode 19 (13h), there are 320×200 pixels with 256 colors. Because 256 == 2⁸, the color value for each pixel is stored in exactly 1 byte (8 bits). Therefore, if you start at the beginning of the video memory (address A000h), the pixels are stored linearly and their color values can be written directly. The formula to write to the pixel (x, y) is: A000h + (y * 320) + x.

As you did in your original code, you could improve this further by hoisting the setting of ES out into the caller, and making ES == 0A000h a precondition of the PlotPixel function. But I did make a big change to your original code, replacing a slow multiplication (MUL) by a left-shift and a couple of additions. Your original multiplication-based code also had an overflow bug, which my rewrite fixed.

You can speed things up even further by writing multiple bytes at a time---on an 8086, that would be writing a WORD (two bytes). This would require "inlining" the pixel-plotting code directly in the DrawCircle function and doing some creative register allocation to ensure that the first pixel you wanted to plot was in, say, AL, and the second pixel was in AH. I'll leave this as an exercise.

_{^* I like to turn these offsets into constants using a macro, and then use that symbolic name throughout the function, instead of hardcoding the numeric value. Not only does that keep the code more readable, but it also makes it much easier to change, if you decide to change the order in which you push parameters or the number of parameters that you push. I didn't do it here, because I don't know what the proper syntax would be for TASM, and it bit me while debugging this code.

Speaking of which, I wrote the code in NASM and tried to translate on-the-fly to TASM, a syntax I'm not terribly familiar with. Sorry if there are any little syntactical issues you have to fix before you can assemble it!}