Bresenham's line algorithm in MIPS

Question

I need to draw a line on a 32x32 white/black image using Bresenham's line algorithm. I have read_bmp and save_bmp functions, as well as function which sets color, function which draws a pixel and a function which draws a line. Unfortunately, when I complile my code, there is only pixel showing in a result.bmp file.

.eqv    pHeader 0
.eqv    filesize 4
.eqv    pImg    8
.eqv    width   12
.eqv    height  16
.eqv    linesbytes 20

.eqv    bi_imgoffset  10
.eqv    bi_imgwidth   18
.eqv    bi_imgheight  22

.eqv    max_file_size 2048

    .data
filename:   .asciiz "white32x32.bmp"
resultfile: .asciiz "result.bmp"
color_err:  .asciiz "Incorrect color - should be 0 or 1"

num_one:      .word 1
num_neg_one:  .word -1
mult2:  .word 2
loop:   .word 32
        .align  4
descriptor: .word   0, 0, 0, 0, 0, 0, 0, 0, 0

filebuf:    .space max_file_size

    .text
    
    
    move $t0, $zero 
    lw   $s0, loop 
main:
    la $a0, filename
    la $a1, descriptor
    la $t0, filebuf
    sw $t0, pHeader($a1)
    li $t0, max_file_size
    sw $t0, filesize($a1)
    jal read_bmp_file
    # check for errors
    
    
        la   $a0, descriptor
        li   $a1, 6  #cx
        li   $a2, 8  #cy
        li   $a3, 0  #color
        li $s0, 10   #x
        li $s1, 12   #y
        jal line_to
        addi $t0, $t0, 32
        j main
        
        move $t0, $zero 
    lw   $s0, loop 
    li $v0, 10
    syscall
    
line_to:
    

# |register|   variable  |
# | t0     |   cx        |   
# | t1     |   cy        |
# | t2     |    dx - dy  |   
# | t3     |   ai        |
# | t4     |   bi        |
# | s0     |   x         |
# | s1     |   y         |
# | s2     | dx = x-cx   |
# | s3     } dy = y-cy   |      
# | s4     |   xi        |
# | s5     |   yi        |


    sub $s3, $s0, $t0 #s3 = x - cx
    sub $s4, $s1, $t1 #s4 = y - cy

#if (dx < 0) { xi = 1 } else { xi = -1}
    slt $t0, $s0, $s1   #dx = -dx;
    beq $t0, $zero, if_1_else  
    if_1_then:
     lw $s4, num_one
         j if_1_exit
    if_1_else:
         lw $s4, num_neg_one
    if_1_exit:

#if (dy < 0) { yi = 1 } else { yi = -1}
    slt $t0, $s0, $s1   #dy = -dy;
    beq $t0, $zero, if_2_else  
    if_2_then:
        lw $s5, num_one
         j if_2_exit
    if_2_else:
         lw $s5, num_neg_one
    if_2_exit:

    sub $t2, $s2, $s3 #   dy - dx

    lw $t0, num_neg_one
    mult $t0, $s3
    mflo $s3 # s3 = -dy

    move $t0, $a0 # t0 = cx
    move $t1, $a1 # t1 = cy
    move $s1, $s0 # s0 = x
    move $s2, $s1 # s1 = y
    jal set_next_pixel

loop_cond:
    

    sub $t3, $s1, $t0 
    sub $t4, $s2, $t1 
    add $t3, $t3, $t4 
    beqz $t3, loop1_end
    
    lw $t3, mult2
        mult $t3, $t2
        mflo $t3
        
        slt $t4, $s3, $t3 
    beqz $t4, loop1_end
    
    lopp_if_1_then:
        add $t2, $t2, $s3 
        add $t0, $t0, $s4 
        loop1_end:
        
        slt $t4, $t3, $s2 
        beqz $t4, loop2_end
        loop_if_2_then:
        add $t2, $t2, $s2 
        add $t1, $t1, $s5 
        loop2_end:

        j loop_cond 
        
 #loop_cond_end:
         
        
    jr $ra
set_next_pixel:
    lw $t0, linesbytes($a0)
    mul $t0, $t0, $a2   # $t0 offset of the beginning of the row
    
    sra $t1, $a1, 3     # pixel byte offset within the row
    add $t0, $t0, $t1   # pixel byte offset within the image
    
    lw $t1, pImg($a0)
    add $t0, $t0, $t1   # address of the pixel byte
    
    lb $t1, 0($t0)
    
    and $a1, $a1, 0x7   # pixel offset within the byte
    li $t2, 0x80
    srlv $t2, $t2, $a1  # mask on the position of pixel
    
    jal set_color
#   sub $a3, $a3, 1
#   bnez $a3, set_next_pixel
    
    la $a0, resultfile
    la $a1, descriptor
    jal save_bmp_file
    
    li $v0, 10
    syscall
    
set_color:
    addi $v1, $zero, 1
    blt $a3, $zero, print_color_err     # if a3 < 0, then error
    bgt $a3, $v1, print_color_err   #if a3 > 1, then error
    beq $a3,$v1, white  # if a3 = 1, then white
        beq $a3,$zero, black    # if a3 = 0, then black
        jr $ra
black:
    xor $t1, $t1, $t2    # set proper pixel to 0 (black)
    sb $t1, 0($t0)
    jr $ra
white:
    or $t1, $t1, $t2    # set proper pixel to 1 (white)
    sb $t1, 0($t0)
    jr $ra
print_color_err:
    li $v0, 4
    la $a0, color_err
    syscall


read_bmp_file:
    # $a0 - file name 
    # $a1 - file descriptor
    #   pHeader - contains pointer to file buffer
    #   filesize - maximum file size allowed
    move $t0, $a1
    li $a1, 0
    li $a2, 0
    li $v0, 13 # open file
    syscall
    # check for errors: $v0 < 0
    
    move $a0, $v0
    lw $a1, pHeader($t0)
    lw $a2, filesize($t0)
    li $v0, 14
    syscall
    
    sw $v0, filesize($t0)  # actual size of bmp file

    li $v0, 16 # close file
    syscall

    lhu $t1, bi_imgoffset($a1)
    add $t1, $t1, $a1
    sw $t1, pImg($t0)
    
    lhu $t1, bi_imgwidth($a1)
    sw $t1, width($t0)
    
    lhu $t1, bi_imgheight($a1)
    sw $t1, height($t0)
    
    # number of words in a line: (width + 31) / 32
    # number of bytes in a line: ((width + 31) / 32) * 4
    lw $t1, width($t0)
    add $t1, $t1, 31
    sra $t1, $t1, 5 # t1 contains number of words
    sll $t1, $t1, 2
    sw $t1, linesbytes($t0)
    jr $ra
    


save_bmp_file:
    # $a0 - file name 
    # $a1 - file descriptor
    #   pHeader - contains pointer to file buffer
    #   filesize - maximum file size allowed
    move $t0, $a1
    li $a1, 1  # write
    li $a2, 0
    li $v0, 13 # open file
    syscall
    # check for errors: $v0 < 0
    
    move $a0, $v0
    lw $a1, pHeader($t0)
    lw $a2, filesize($t0)
    li $v0, 15
    syscall
    
    li $v0, 16 # close file
    syscall

Every function besides line_to works fine, but I do not know what causes a problem in line_to.

question from:https://stackoverflow.com/questions/65652039/bresenhams-line-algorithm-in-mips

Answer 1

You need a philosophy for debugging.

Static Debugging

• Make sure your C/pseudo code algorithm actually works, otherwise debugging design problems in assembly is hard, when you're still learning assembly.? (The best way to do this is to write your pseudo code in C and actually run it.)

• Read the code and verify that each register named in the instruction corresponds to the proper variable in the algorithm.? For example,

  # | s3     } dy = y-cy   |      
  # | s4     |   xi        |
  # | s5     |   yi        |
  
  sub $s3, $s0, $t0 #s3 = x - cx    # here s3 is dx, but comment above says s3 is dy
  sub $s4, $s1, $t1 #s4 = y - cy    # here s4 is dy, but comment above says s4 is xi
  
  

You can see that there is a mismatch between comments and code.

(btw, +1 for having a written register-variable map.)

Dynamic Debugging

• Check the parameters are passed properly at the beginning of each function
• Start with the simplest possible test cases, e.g. a horizontal line and/or a vertical line — maybe even a line of only 1 point in length.
• Single step and follow the effect of each instruction
  • After each instruction, verify that each register has the value you expect
  • After each instruction, verify the control flow is correct for branches
  • Verify that memory is updated as you expect for store instructions

---

Other Problems

• Your static call chain has main calling line_to and line_to calling set_next_pixel, set_next_pixel calling set_color.? Each time jal is used, it repurposes the $ra register, but each of these functions will need their own $ra value to get back to their caller.? Usually this is handled by creating a stack frame and storing $ra there, in the non-leaf routines, then reloading $ra prior to returning to caller.? (Leaf functions — functions that don't call other functions — don't need to do this.)

• set_next_pixel is incomplete, and missing the return to caller.

• The code at print_color_err simply falls into read_bmp_file.? It should return instead or maybe end the program.

Other Observations

• Don't use lw with a constant to put a +1 or -1 in a register — just use the li $t0, -1 (or addi $t0, $0, -1 if you don't want to use pseudo instructions.)

• The code at set_color is testing too many condition and should be simplified.? It is testing $a3 for < 0, > 1, = 1, = 0, and still has an else clause in case none of those tests succeeds.

• Negation is easier done via 0-x instead of using multiplication -1*i

• Doubling is easier done via shift of 1 (sll $trg, $src, 1) than using multiplication

• Your calling conventions are non-standard.? This is ok, but makes the code harder for others to read, and more error prone.