MIPS 中的 Bresenham 直线算法
Bresenham's line algorithm in MIPS
我需要使用 Bresenham 的线算法在 32x32 white/black 图像上画一条线。我有 read_bmp
和 save_bmp 函数，以及设置颜色的函数、绘制像素的函数和绘制线条的函数。不幸的是，当我编译代码时，result.bmp 文件中只显示像素。
.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
除了 line_to 之外的每个函数都可以正常工作，但我不知道是什么导致了 line_to 中的问题。
你需要一种调试哲学。
静态调试
确保您的 C/pseudo 代码算法确实有效，否则在您仍在学习汇编时很难调试汇编中的设计问题。 （最好的方法是用 C 编写你的伪代码，实际上 运行 它。）
阅读代码并验证指令中命名的每个寄存器是否对应于算法中的适当变量。例如，
# | 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
可以看到注释和代码不匹配。
（顺便说一句，+1 因为有一个书面的寄存器变量映射。）
动态调试
- 检查每个函数开头的参数是否正确传递
- 从尽可能简单的测试用例开始，例如水平线 and/or 垂直线 — 甚至可能只有 1 磅长的线。
- 单步跟踪每条指令的效果
- 在每条指令之后，验证每个寄存器是否具有您期望的值
- 在每条指令之后，验证分支的控制流是否正确
- 验证内存是否按照您对存储指令的预期进行了更新
其他问题
您的静态调用链有 main 调用 line_to 和 line_to 调用 set_next_pixel，set_next_pixel 调用 set_color .每次使用 jal 时，它都会重新调整 $ra 寄存器的用途，但是这些函数中的每一个都需要自己的 $ra 值才能返回给调用者。通常这是通过在非叶例程中创建堆栈帧并将 $ra 存储在那里，然后在 returning 之前重新加载 $ra 来处理的。 （叶函数——不调用其他函数的函数——不需要这样做。）
set_next_pixel 不完整，缺少 return 给来电者。
print_color_err 处的代码完全属于 read_bmp_file。它应该 return 代替或者结束程序。
其他观察结果
不要将 lw 与常量一起使用以将 +1 或 -1 放入寄存器中 — 只需使用 li $t0, -1（或 addi $t0, [=27=], -1 如果你不想使用伪指令。）
set_color 处的代码测试了太多条件，应予以简化。它正在为 < 0、> 1、= 1、= 0 测试 $a3，并且仍然有一个 else 子句以防 none 这些测试成功。
通过 0-x 而不是乘法 -1*i
可以更容易地求反
通过移位 1 (sll $trg, $src, 1) 比使用乘法更容易实现加倍
您的调用约定不标准。这没问题，但是会使代码更难被其他人阅读，并且更容易出错。
我需要使用 Bresenham 的线算法在 32x32 white/black 图像上画一条线。我有 read_bmp 和 save_bmp 函数，以及设置颜色的函数、绘制像素的函数和绘制线条的函数。不幸的是，当我编译代码时，result.bmp 文件中只显示像素。
.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
除了 line_to 之外的每个函数都可以正常工作，但我不知道是什么导致了 line_to 中的问题。
你需要一种调试哲学。
静态调试
确保您的 C/pseudo 代码算法确实有效，否则在您仍在学习汇编时很难调试汇编中的设计问题。 （最好的方法是用 C 编写你的伪代码，实际上 运行 它。）
阅读代码并验证指令中命名的每个寄存器是否对应于算法中的适当变量。例如，
# | 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
可以看到注释和代码不匹配。
（顺便说一句，+1 因为有一个书面的寄存器变量映射。）
动态调试
- 检查每个函数开头的参数是否正确传递
- 从尽可能简单的测试用例开始，例如水平线 and/or 垂直线 — 甚至可能只有 1 磅长的线。
- 单步跟踪每条指令的效果
- 在每条指令之后，验证每个寄存器是否具有您期望的值
- 在每条指令之后，验证分支的控制流是否正确
- 验证内存是否按照您对存储指令的预期进行了更新
其他问题
您的静态调用链有
main调用line_to和line_to调用set_next_pixel，set_next_pixel调用set_color.每次使用jal时，它都会重新调整$ra寄存器的用途，但是这些函数中的每一个都需要自己的$ra值才能返回给调用者。通常这是通过在非叶例程中创建堆栈帧并将$ra存储在那里，然后在 returning 之前重新加载$ra来处理的。 （叶函数——不调用其他函数的函数——不需要这样做。）set_next_pixel不完整，缺少 return 给来电者。print_color_err处的代码完全属于read_bmp_file。它应该 return 代替或者结束程序。
其他观察结果
不要将
lw与常量一起使用以将 +1 或 -1 放入寄存器中 — 只需使用li $t0, -1（或addi $t0, [=27=], -1如果你不想使用伪指令。）set_color处的代码测试了太多条件，应予以简化。它正在为 < 0、> 1、= 1、= 0 测试$a3，并且仍然有一个else子句以防 none 这些测试成功。通过
可以更容易地求反0-x而不是乘法-1*i通过移位 1 (
sll $trg, $src, 1) 比使用乘法更容易实现加倍您的调用约定不标准。这没问题，但是会使代码更难被其他人阅读，并且更容易出错。