Линейный алгоритм Брезенхэма в MIPS

Мне нужно нарисовать линию на бело-черном изображении 32x32, используя алгоритм линии Брезенхэма. У меня есть функции 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.


person michael    schedule 10.01.2021    source источник


Ответы (1)


Вам нужна философия для отладки.

Статическая отладка

  • Убедитесь, что ваш алгоритм C/псевдокода действительно работает, иначе отладка проблем проектирования в ассемблере будет затруднена, когда вы все еще изучаете ассемблер. (Лучший способ сделать это — написать свой псевдокод на 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 за наличие письменной карты переменных регистров.)

Динамическая отладка

  • Проверьте правильность передачи параметров в начале каждой функции.
  • Начните с самых простых возможных тестов, например. горизонтальная линия и/или вертикальная линия — может быть, даже линия длиной всего в 1 точку.
  • Single step and follow the effect of each instruction
    • After each instruction, verify that each register has the value you expect
    • После каждой инструкции проверяйте правильность потока управления для ветвей.
    • Убедитесь, что память обновлена ​​так, как вы ожидаете, для инструкций по хранению

Другие проблемы

  • В вашей статической цепочке вызовов есть main, вызывающий line_to, и line_to, вызывающий set_next_pixel, set_next_pixel, вызывающий set_color. Каждый раз, когда используется jal, он переназначает регистр $ra, но каждой из этих функций потребуется свое собственное значение $ra, чтобы вернуться к вызывающей стороне. Обычно это обрабатывается созданием кадра стека и сохранением $ra в неконечных подпрограммах, а затем повторной загрузкой $ra перед возвратом к вызывающему. (Функции-листья — функции, которые не вызывают другие функции — не должны этого делать.)

  • set_next_pixel является неполным и отсутствует возврат к вызывающему абоненту.

  • Код в print_color_err просто попадает в read_bmp_file. Вместо этого он должен вернуться или, возможно, завершить программу.

Другие наблюдения

  • Не используйте lw с константой для добавления +1 или -1 в регистр — просто используйте li $t0, -1 (или addi $t0, $0, -1, если вы не хотите использовать псевдоинструкции).

  • Код в set_color проверяет слишком много условий и должен быть упрощен. Он проверяет $a3 на ‹ 0, › 1, = 1, = 0, и все еще имеет предложение else на случай, если ни один из этих тестов не пройдет успешно.

  • Отрицание проще сделать с помощью 0-x вместо использования умножения -1*i

  • Удвоение легче выполнить с помощью сдвига на 1 (sll $trg, $src, 1), чем с помощью умножения.

  • Ваши соглашения о вызовах нестандартны. Это нормально, но делает код более трудным для чтения и более подверженным ошибкам.

person Erik Eidt    schedule 10.01.2021
comment
Пока я сделал все, кроме динамической отладки, и у меня есть вопрос: как быть со статической цепочкой вызовов? - person michael; 10.01.2021
comment
Обычно это обрабатывается путем создания кадра стека и сохранения $ra в неконечных подпрограммах, а затем перезагрузки $ra перед возвратом к вызывающей программе. (Функции-листья — функции, которые не вызывают другие функции — не должны этого делать.) - person Erik Eidt; 10.01.2021
comment
Также я не знаю, что еще должно быть в функции line_to (например, в loop_cond_end:). Насколько я понимаю, один только алгоритм в порядке (проверено на C). - person michael; 10.01.2021
comment
Функции, которые вызывают другие функции, должны сохранять свой параметр $ra, чтобы они могли использовать это значение в конце при возврате к вызывающей программе. Найдите вызовы функций MIPS и кадры стека. - person Erik Eidt; 11.01.2021