装配中的画线算法

发布于 2025-01-12 09:55:06 字数 7366 浏览 2 评论 0原文

我正在尝试在汇编中创建一种画线算法(更具体地说是 Bresenham 的线条算法)。在尝试实现该算法后,即使我几乎完全复制了 此维基百科页面

它应该在两点之间画一条线,但是当我测试它时,它在窗口中的随机位置绘制点。我真的不知道会出什么问题,因为汇编调试很困难。

我使用 NASM 将程序转换为二进制文件,然后在 QEMU 中运行二进制文件。

[bits 16]                                               ; 16-bit mode
[org 0x7c00]                                            ; memory origin

section .text                                           ; code segmant
    global _start                                       ; tells the kernal where to begin the program
_start:                                                 ; where to start the program

; main
call cls                                                ; clears the screen
update:                                                 ; main loop
    mov cx, 0x0101                                      ; line pos 1
    mov bx, 0x0115                                      ; line pos 2
    call line                                           ; draws the line

    jmp update                                          ; jumps to the start of the loop


; functions
cls:                                                    ; function to clear the screen
    mov ah, 0x00                                        ; set video mode
    mov al, 0x03                                        ; text mode (80x25 16 colours)
    int 0x10                                            ; BIOS interrupt
    ret                                                 ; returns to where it was called


point:                                                  ; function to draw a dot at a certain point (dx)
    mov bx, 0x00ff                                      ; clears the bx register and sets color
    mov cx, 0x0001                                      ; clears the cx register and sets print times
    mov ah, 0x02                                        ; set cursor position
    int 0x10                                            ; BIOS interrupt

    mov ah, 0x09                                        ; write character
    mov al, ' '                                         ; character to write
    int 0x10                                            ; BIOS interrupt
    ret                                                 ; returns to where it was called


line:                                                   ; function to draw a line at two points (bx, cx)
    push cx                                             ; saves cx for later
    push bx                                             ; saves bx for later

    sub bh, ch                                          ; gets the value of dx
    mov [dx_L], bh                                      ; puts it into dx
    sub bl, cl                                          ; gets the value of dy
    mov [dy_L], bl                                      ; puts it into dy

    mov byte [yi_L], 1                                  ; puts 1 into yi (positive slope)

    cmp byte [dy_L], 0                                  ; checks if the slope is negative
    jl .negative_y                                      ; jumps to the corresponding sub-label
    jmp .after_negative_y                               ; if not, jump to after the if

    .negative_y:                                        ; if statement destination
        mov byte [yi_L], -1                             ; sets yi to -1 (negative slope)
        neg byte [dy_L]                                 ; makes dy negative as well
    .after_negative_y:                                  ; else statement destination

    mov ah, [dy_L]                                      ; moves dy_L into a temporary register
    add ah, ah                                          ; multiplies it by 2
    sub ah, [dx_L]                                      ; subtracts dx from that
    mov [D_L], ah                                       ; moves the value into D

    pop bx                                              ; pops bx to take a value off
    mov [y_L], bh                                       ; moves the variable into the output
    
    pop cx                                              ; pops the stack back into cx
    mov ah, bh                                          ; moves x0 into ah
    mov al, ch                                          ; moves x1 into al

    .loop_x:                                            ; loop to go through every x iteration
        mov dh, ah                                      ; moves the iteration count into dh
        mov dl, [y_L]                                   ; moves the y value into dl to be plotted
        call point                                      ; calls the point function

        cmp byte [D_L], 0                               ; compares d to 0
        jg .greater_y                                   ; if greater, jumps to the if statement
        jmp .else_greater_y                             ; if less, jumps to the else statement

        mov bh, [dy_L]                                  ; moves dy into a temporary register
        .greater_y:                                     ; if label
            mov bl, [yi_L]                              ; moves yi into a temporary register
            add [y_L], bl                               ; increments y by the slope
            sub bh, [dx_L]                              ; dy and dx
            add bh, bh                                  ; multiplies bh by 2
            add [D_L], bh                               ; adds bh to D
            jmp .after_greater_y                        ; jumps to after the if statement
        .else_greater_y:                                ; else label
            add bh, bh                                  ; multiplies bh by 2
            add [D_L], bh                               ; adds bh to D
        .after_greater_y:                               ; after teh if statement

        inc ah                                          ; increments the loop variable
        cmp ah, al                                      ; checks to see if the loop should end
        je .end_loop_x                                  ; if it ended jump to the end of teh loop
        jmp .loop_x                                     ; if not, jump back to the start of the loop

    .end_loop_x:                                        ; place to send the program when the loop ends

    ret                                                 ; returns to where it was called


section .data                                           ; data segmant
dx_L: db 0                                              ; used for drawing lines
dy_L: db 0                                              ; ^
yi_L: db 0                                              ; ^
xi_L: db 0                                              ; ^
D_L: db 0                                               ; ^
y_L: db 0                                               ; ^
x_L: db 0                                               ; ^


section .text                                           ; code segmant
; boot the OS
times 510-($-$$) db 0                                   ; fills up bootloader space with empty bytess
db 0x55, 0xaa                                           ; defines the bootloader bytes

I'm trying to create a line-drawing algorithm in assembly (more specifically Bresenham's line algorithm). After trying an implementation of this algorithm, the algorithm fails to work properly even though I almost exactly replicated the plotLineLow() function from this Wikipedia page.

It should be drawing a line between 2 points, but when I test it, it draws points in random places in the window. I really don't know what could be going wrong because debugging in assembly is difficult.

I'm using NASM to convert the program to binary, and I run the binary in QEMU.

[bits 16]                                               ; 16-bit mode
[org 0x7c00]                                            ; memory origin

section .text                                           ; code segmant
    global _start                                       ; tells the kernal where to begin the program
_start:                                                 ; where to start the program

; main
call cls                                                ; clears the screen
update:                                                 ; main loop
    mov cx, 0x0101                                      ; line pos 1
    mov bx, 0x0115                                      ; line pos 2
    call line                                           ; draws the line

    jmp update                                          ; jumps to the start of the loop


; functions
cls:                                                    ; function to clear the screen
    mov ah, 0x00                                        ; set video mode
    mov al, 0x03                                        ; text mode (80x25 16 colours)
    int 0x10                                            ; BIOS interrupt
    ret                                                 ; returns to where it was called


point:                                                  ; function to draw a dot at a certain point (dx)
    mov bx, 0x00ff                                      ; clears the bx register and sets color
    mov cx, 0x0001                                      ; clears the cx register and sets print times
    mov ah, 0x02                                        ; set cursor position
    int 0x10                                            ; BIOS interrupt

    mov ah, 0x09                                        ; write character
    mov al, ' '                                         ; character to write
    int 0x10                                            ; BIOS interrupt
    ret                                                 ; returns to where it was called


line:                                                   ; function to draw a line at two points (bx, cx)
    push cx                                             ; saves cx for later
    push bx                                             ; saves bx for later

    sub bh, ch                                          ; gets the value of dx
    mov [dx_L], bh                                      ; puts it into dx
    sub bl, cl                                          ; gets the value of dy
    mov [dy_L], bl                                      ; puts it into dy

    mov byte [yi_L], 1                                  ; puts 1 into yi (positive slope)

    cmp byte [dy_L], 0                                  ; checks if the slope is negative
    jl .negative_y                                      ; jumps to the corresponding sub-label
    jmp .after_negative_y                               ; if not, jump to after the if

    .negative_y:                                        ; if statement destination
        mov byte [yi_L], -1                             ; sets yi to -1 (negative slope)
        neg byte [dy_L]                                 ; makes dy negative as well
    .after_negative_y:                                  ; else statement destination

    mov ah, [dy_L]                                      ; moves dy_L into a temporary register
    add ah, ah                                          ; multiplies it by 2
    sub ah, [dx_L]                                      ; subtracts dx from that
    mov [D_L], ah                                       ; moves the value into D

    pop bx                                              ; pops bx to take a value off
    mov [y_L], bh                                       ; moves the variable into the output
    
    pop cx                                              ; pops the stack back into cx
    mov ah, bh                                          ; moves x0 into ah
    mov al, ch                                          ; moves x1 into al

    .loop_x:                                            ; loop to go through every x iteration
        mov dh, ah                                      ; moves the iteration count into dh
        mov dl, [y_L]                                   ; moves the y value into dl to be plotted
        call point                                      ; calls the point function

        cmp byte [D_L], 0                               ; compares d to 0
        jg .greater_y                                   ; if greater, jumps to the if statement
        jmp .else_greater_y                             ; if less, jumps to the else statement

        mov bh, [dy_L]                                  ; moves dy into a temporary register
        .greater_y:                                     ; if label
            mov bl, [yi_L]                              ; moves yi into a temporary register
            add [y_L], bl                               ; increments y by the slope
            sub bh, [dx_L]                              ; dy and dx
            add bh, bh                                  ; multiplies bh by 2
            add [D_L], bh                               ; adds bh to D
            jmp .after_greater_y                        ; jumps to after the if statement
        .else_greater_y:                                ; else label
            add bh, bh                                  ; multiplies bh by 2
            add [D_L], bh                               ; adds bh to D
        .after_greater_y:                               ; after teh if statement

        inc ah                                          ; increments the loop variable
        cmp ah, al                                      ; checks to see if the loop should end
        je .end_loop_x                                  ; if it ended jump to the end of teh loop
        jmp .loop_x                                     ; if not, jump back to the start of the loop

    .end_loop_x:                                        ; place to send the program when the loop ends

    ret                                                 ; returns to where it was called


section .data                                           ; data segmant
dx_L: db 0                                              ; used for drawing lines
dy_L: db 0                                              ; ^
yi_L: db 0                                              ; ^
xi_L: db 0                                              ; ^
D_L: db 0                                               ; ^
y_L: db 0                                               ; ^
x_L: db 0                                               ; ^


section .text                                           ; code segmant
; boot the OS
times 510-($-$) db 0                                   ; fills up bootloader space with empty bytess
db 0x55, 0xaa                                           ; defines the bootloader bytes

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

花辞树 2025-01-19 09:55:06
  1. 我没有看到视频模式

    您在开始时使用cls设置的只是80x25文本VGA模式(mode = 3),那么如何渲染点呢?您应该设置您想要的视频模式(假设 VGA 或 VESA/VBE 请参阅上面的链接)。

  2. 为什么要使用 VGA BIOS 进行点渲染?

    这将是 slooooooooow,我不知道当没有 gfx 模式时它会做什么。您可以通过直接访问 VRAM(在段 A000h 处)来渲染点。理想使用 8/16/24/32 位视频模式,因为它们的像素与字节对齐...我最喜欢的是 320x200x256c(模式 = 19) ),因为它适合 64K 段,因此不需要分页,并且像素为字节。

    如果您使用字符而不是像素,那么您仍然可以以相同的方式访问 VRAM,只需使用段 B800h 并且字符为 16 位(颜色和 ASCII)。

  3. 整数 DDA 自 80386 起在 x86 CPU 上比 Bresenham 更快

    我已经有大约 20 年没有在 NASM 中编写代码了,我在档案中找到的最接近的内容是:

    <预><代码>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    行: Pusha ;ax=x0,bx=x1,dl=y0,dh=y1,cl=col
    推斧头;期望 ES = A000h
    移动 si,bx
    亚硅轴
    子啊啊啊
    莫夫阿尔,dl
    移动 bx,ax
    莫夫阿尔,DH
    副轴,bx
    移动二轴
    移动斧头,320
    亚 dh,dh
    多 dx
    流行音乐
    添加斧头,bx
    移动 bp,ax
    移动斧头,1
    移动 bx,320
    CMP si,32768
    jb.r0
    内格西
    负斧头
    .r0:CMP di,32768
    jb.r1
    内格迪
    负bx
    .r1: cmp si,di
    ja.r2
    xchg 斧头,bx
    xchg si,di
    .r2: mov [.ct],si
    .l0: mov [es:bp],cl
    添加 bp,ax
    子 dx,di
    jnc.r3
    添加 dx,si
    添加 bp,bx
    .r3:十进制字 [.ct]
    jnz.l0
    波帕
    雷特
    .ct: dw 0
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

    所以你有一些东西需要交叉检查(我花了一段时间才在我的档案中找到它,因为当时我用纹理编写了整个 3D 多边形引擎,所以我在 NASM 中没有太多 2D 代码...)

    该示例需要 320x200x256c VGA 视频模式

  4. 如果您正在编写 DOS .com 文件,事情会更简单一些:段寄存器将全部设置为相同,代码/数据距它们的偏移量为 100。您可以以 ret 结尾。

    <前><代码>[位 16]
    [组织 100 小时]

    [段.文本]
    雷特

正如 @bitRAKE 和 @PeterCoders 指出的,如果您在引导扇区中运行它,org 就可以了。然而,在这种情况下,不存在操作系统,因此如果您要对堆栈或 512 字节之外的任何其他内存块执行更多操作,您需要将堆栈指向已知的位置。 (不过,它一开始确实有效,因为中断已启用。)

更重要的是,您需要初始化 DS 以匹配您的 ORG 设置,因此 ds:org 达到线性地址7C00。对于org 0x7c00,这意味着您需要 DS=0。否则像 mov [dx_L], bh 这样的指令将在某个未知位置使用内存。

    [BITS 16]
    [ORG 7C00h]
    
    [SEGMENT .text]
        mov ax,0000h
        mov ds,ax          ; DS=0 to match ORG
        mov ss,ax          ; if you set SS:SP at all, do it back-to-back
        mov sp,7C00h       ; so an interrupt can't fire half way through.
        ; here do your stuff
    l0: 
      hlt      ; save power
      jmp l0  
  1. 希望您使用配置为 NASM IDE 的 VC 或 NC,而不是手动编译/链接

    这个可以在 MS-DOS 中使用,所以如果您正在运行 BOT SECTOR,那么您就不走运了。您仍然可以创建一个 *.com 可执行文件调试,一旦它在 dos 中工作,就会更改为引导扇区...

    请参阅是否有办法从 Linux 链接 DOS 目标文件?了解如何设置 MS-DOS Volkov Commander 只需按一下 Enter 键即可自动编译和链接您的 asm 源代码...您也可以通过在 vc.ext 行中添加行来运行它...但我不喜欢这样做,这样您可以先检查错误日志

  2. 方便调试

    您可以尝试将 MS-DOS (DOSBox) 与古老的 Borland Turbo C/C++ 或 Pascal 一起使用,并使用它们的内联 asm { .... } 代码,该代码可以直接跟踪和单步执行IDE。然而它使用 TASM(与 NASM 不同的语法)并有一些限制......

    遗憾的是,我从未在 x86 平台上见过任何像样的 asm IDE。我使用过的最好的 asm IDE 是 ZX Spectrum 上的 Herkules ...可以完成现代 C++ IDE 无法完成的事情。

  1. I see no video mode

    just 80x25 text VGA mode (mode = 3) you set at start with cls so how can you render points? You should set the video mode you want assuming VGA or VESA/VBE see the link above.

  2. why to heck use VGA BIOS for point rendering?

    that will be slooooooooow and I have no idea what it does when no gfx mode is present. You can render points by direct access to VRAM (at segment A000h) Ideal use 8/16/24/32bit video modes as they have pixels aligned to BYTEs ... my favorite is 320x200x256c (mode = 19) as it fits into 64K segment so no paging is needed and pixels are Bytes.

    In case you are using characters instead of pixels then you still can use access to VRAM in the same way just use segment B800h and chars are 16 bit (color and ASCII).

  3. integer DDA is faster then Bresenham on x86 CPUs since 80386

    I do not code in NASM for around 2 decades and closest thing to line I found in my archive is this:

     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     line:   pusha       ;ax=x0,bx=x1,dl=y0,dh=y1,cl=col
         push    ax      ;expecting ES = A000h
         mov si,bx
         sub si,ax
         sub ah,ah
         mov al,dl
         mov bx,ax
         mov al,dh
         sub ax,bx
         mov di,ax
         mov ax,320
         sub dh,dh
         mul dx
         pop bx
         add ax,bx
         mov bp,ax
         mov ax,1
         mov bx,320
         cmp si,32768
         jb  .r0
         neg si
         neg ax
     .r0:    cmp di,32768
         jb  .r1
         neg di
         neg bx
     .r1:    cmp si,di
         ja  .r2
         xchg    ax,bx
         xchg    si,di
     .r2:    mov [.ct],si
     .l0:    mov [es:bp],cl
         add bp,ax
         sub dx,di
         jnc .r3
         add dx,si
         add bp,bx
     .r3:    dec word [.ct]
         jnz .l0
         popa
         ret
     .ct:    dw  0
     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    

    So you have something to cross check (took me a while to find it in my archives as I coded whole 3D polygonal engines with textures at that time so I do not have much 2D code in NASM...)

    The example expects 320x200x256c VGA video mode

  4. If you were writing a DOS .com file, things would be a bit simpler: segment registers would all be set the same, with your code/data at offset 100 from them. And you could end with ret.

    [BITS 16]
    [ORG 100h]
    
    [SEGMENT .text]
        ret
    

As @bitRAKE and @PeterCoders pointed out in case You run this in BOOT SECTOR the org is ok. However in such case there is no OS present so if you were going to do more with the stack or any other block of memory outside your 512 bytes, you'd want to point the stack to somewhere known. (It does start out valid, though, because interrupts are enabled.)

More importantly, you need to initialize DS to match your ORG setting, so ds:org reaches a linear address of 7C00. With org 0x7c00, that means you want DS=0. Otherwise instructions like mov [dx_L], bh would be using memory at some unknown location.

    [BITS 16]
    [ORG 7C00h]
    
    [SEGMENT .text]
        mov ax,0000h
        mov ds,ax          ; DS=0 to match ORG
        mov ss,ax          ; if you set SS:SP at all, do it back-to-back
        mov sp,7C00h       ; so an interrupt can't fire half way through.
        ; here do your stuff
    l0: 
      hlt      ; save power
      jmp l0  
  1. Hope you are using VC or NC configured as IDE for NASM and not compiling/linking manually

    This one is usable in MS-DOS so if you are running BOT SECTOR you out of luck. Still You can create a *.com executable debug and once its working in dos change to BOOT SECTOR...

    see Is there a way to link object files for DOS from Linux? on how to setup MS-DOS Volkov commander to automatically compile and link your asm source code just by hitting enter on it ... You can also run it just by adding line to the vc.ext line ... but I prefer not to so you can inspect error log first

  2. Convenient debugging

    You can try to use MS-DOS (DOSBox) with ancient Borland Turbo C/C++ or Pascal and use their inline asm { .... } code which can be traced and stepped directly in the IDE. However it uses TASM (different syntax to NASM) and have some restrictions ...

    Sadly I never saw any decent IDE for asm on x86 platform. The best IDE for asm I worked with was Herkules on ZX Spectrum ... was possible to done things even modern C++ IDEs doesnt have.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文