I'm trying to translate the Bresenham line-drawing algorithm into MASM 16 bit code so I can use it to draw lines in Mode 13h.
This is the C# code I started out with (adapted from some pseudo code I found on Wiki)...
Code:
private void DrawLine( Bitmap dc, short x0, short y0, short x1, short y1, Color c )
{
bool steep = Math.Abs( y1 - y0 ) > Math.Abs( x1 - x0 );
if ( steep )
{
short temp = x0;
x0 = y0;
y0 = temp;
temp = x1;
x1 = y1;
y1 = temp;
dc.SetPixel( y0, x0, c );
}
else
dc.SetPixel( x0, y0, c );
short deltax = Math.Abs( (short)(x1 - x0) );
short deltay = Math.Abs( (short)(y1 - y0) );
short error = 0;
short x = x0;
short y = y0;
short xstep, ystep;
if ( x0 < x1 )
xstep = 1;
else
xstep = -1;
if ( y0 < y1 )
ystep = 1;
else
ystep = -1;
while ( x != x1 )
{
x += xstep;
error += deltay;
if ( (2 * error) > deltax )
{
y += ystep;
error -= deltax;
}
if ( steep )
dc.SetPixel( y, x, c );
else
dc.SetPixel( x, y, c );
}
}
First thing I did was to replace as many variables as I could with 16 bit registers. My version almost works but it tends to act strangely, drawing some lines bent or just at the wrong angle.
Here's my bad ASM code...
Code:
;---------------------------
DrawLine PROC,
x0:WORD,
y0:WORD,
x1:WORD,
y1:WORD,
color:BYTE
;
; An implementation of the Bresenham line-drawing algorithm
; Translated to ASM by Adam Ward, 01/12/05
;---------------------------
LOCAL deltax:WORD,
deltay:WORD,
error:WORD,
xstep:WORD,
ystep:WORD
pusha
; validate all the arguments (both coords are on screen)
mov ax, SCREEN_WIDTH
mov bx, SCREEN_HEIGHT
xor cx, cx ; = 0
cmp x0, cx
jl DONE
cmp x1, cx
jl DONE
cmp y0, cx
jl DONE
cmp y1, cx
jl DONE
cmp x0, ax
jge DONE
cmp x1, ax
jge DONE
cmp y0, bx
jge DONE
cmp y1, bx
jge DONE
;####################################
;### START OF BRESENHAM ALGORITHM ###
;####################################
; cx = abs(y1 - y0) > abs(x1 - x0) ####################
mov ax, y1
sub ax, y0
jns ABS_Y_DONE
neg ax ; number is negative, so make it positive
ABS_Y_DONE:
mov bx, x1
sub bx, x0
jns ABS_X_DONE
neg bx ; number is negative, so make it positive
ABS_X_DONE:
cmp ax, bx
jbe ELSE1
; ax > bx
mov cx, 1
jmp ENDIF1
ELSE1:
; ax <= bx
mov cx, 0
ENDIF1:
; if cx then ####################
bt cx, 0
jnc ELSE2
; swap(x0, y0)
mov ax, x0
xchg ax, y0
mov x0, ax
; swap(x1, y1)
mov ax, x1
xchg ax, y1
mov x1, ax
INVOKE PlotPixel, y0, x0, color
ELSE2:
INVOKE PlotPixel, x0, y0, color
ENDIF2:
; deltax = abs(x1 - x0) ###########
mov ax, x1
sub ax, x0
jns ABS_X2_DONE
neg ax ; number is negative, so make it positive
ABS_X2_DONE:
mov deltax, ax
; deltay = abs(y1 - y0) ###########
mov ax, y1
sub ax, y0
jns ABS_Y2_DONE
neg ax ; number is negative, so make it positive
ABS_Y2_DONE:
mov deltay, ax
; error = 0 ##########
mov error, 0
; bx = x0 #########
mov bx, x0
; dx = y0 #########
mov dx, y0
; if x0 < x1 then #########
cmp bx, x1
jae ELSE3
; xstep = 1
mov xstep, 1
jmp ENDIF3
ELSE3:
; xstep = -1
mov xstep, -1
ENDIF3:
; if y0 < y1 then #########
cmp dx, y1
jae ELSE4
; ystep = 1
mov ystep, 1
jmp ENDIF4
ELSE4:
; ystep = -1
mov ystep, -1
ENDIF4:
; while bx != x1 ###############
L1:
cmp bx, x1
je Done
; bx = bx + xstep
add bx, xstep
; error = error + deltay
mov ax, error
add ax, deltay
mov error, ax
; if 2 * error > deltax ##########
; (error value is still in ax...)
shl ax, 1 ;error * 2
cmp ax, deltax
jbe ENDIF5
; dx = dx + ystep
add dx, ystep
; error = error - deltax
mov ax, deltax
sub error, ax
ENDIF5:
; if cx then #############
bt cx, 0
jnc ELSE6
; plot(dx,bx)
INVOKE PlotPixel, dx, bx, color
jmp L1 ; SHORTCUT TO BEGINNING OF WHILE LOOP
ELSE6:
; plot(bx,dx)
INVOKE PlotPixel, bx, dx, color
jmp L1 ; continue the while loop
DONE:
popa
ret
DrawLine ENDP
Whats wrong with this algorithm? (PlotPixel is fine, I have checked that separately and its OK)
I'm not sure about the MASM but you might wanna optimise your base code and just redo hoping you don't make the same mistake...
here's some optimised from your code (I just optimised it for my program... but I'm passing in deltax and deltay instead of x1 and y1 so I had to convert back)
I just followed the two basic rules of optimisation: don't recompute anything (for instance, deltax and deltay) and take everything you can out of the loop (like the xstep > 0 determination)... I also changed it to use increment and decrement operators as much as possible, because on certain processors inc and dec can take zero clocks, and on earlier processors inc and dec take less time than add and sub
private void DrawLine( Bitmap dc, short x0, short y0, short x1, short y1, Color c )
{
short deltax = x1 < x0 ? x0 - x1 : x1 - x0;
short deltay = y1 < y0 ? y0 - y1 : y1 - y0;
bool steep = deltay > deltax;
if ( steep )
{
short temp = x0;
x0 = y0;
y0 = temp;
temp = x1;
x1 = y1;
y1 = temp;
dc.SetPixel( y0, x0, c );
}
else
dc.SetPixel( x0, y0, c );
short error = 0;
short x = x0;
short y = y0;
short xstep, ystep;
if(xstep > 0)
while ( x != x1 )
{
x ++;
error += deltay;
if ( (2 * error) > deltax )
{
y += ystep;
error -= deltax;
}
if ( steep )
dc.SetPixel( y, x, c );
else
dc.SetPixel( x, y, c );
}
} else {
while ( x != x1 )
{
x --;
error += deltay;
if ( (2 * error) > deltax )
{
y += ystep;
error -= deltax;
}
if ( steep )
dc.SetPixel( y, x, c );
else
dc.SetPixel( x, y, c );
}
}
}
Another handy optimisation if you're drawing to a byte array is to forgo the plot pixel altogether and only compute the y component of the address when it changes...
I'm drawing to an int array (32-bit AHSL color) and I just compute int yline = (y * width); everytime I update y... then my pixel operation looks like
could be just:
jcxz ELSE6 ;(Because you are using the cx register -- this actually could be problem of the algorithm because you are testing only 1 bit in the 16-bit register )
same again
bt cx, 0
jnc ELSE2
should be:
jcxz ELSE2
I think it should work now - but I've only read it off-screen - not tested it in action.
Btw ....why are you using POPA and PUSHA - they are kinda slow unless you really need to preserve all 7 registers - here you are only using a few - it'll be much faster if you use individual push and pops.
Last edited by Raedwulf; Dec 5th, 2005 at 03:17 AM.
because on certain processors inc and dec can take zero clocks
No can't be true - all instructions take clocks.
Unless you are referring to pairing - on older processors inc/dec is slightly faster than add/sub because there was less pairing and inc/dec was a shorter instruction
On newer processors, inc/dec don't pair so well and add/sub are faster than inc/dec - check pentopt.pdf on agner fog's site.
And in 64bit asm programming - inc/dec 1 byte opcodes are no longer valid - so their advantage of having a shorter instruction is gone as well - its being deprecated in favour for add/sub.
So unless you are programming for processors 486 and below- you can happily use add/sub because i believe from P1 to P3 the speed of the instructions are about the same and P4 add/sub are faster.
Thanks for checking my code out. I appreciate your help. Actually that bit of code you said is unecessary (actually I did think that too for a while until i realised the i could re-use ax without any extra code). check out the comment below it and it should become clear.
I have used the jcxz's though.
Sadly the alg still doesnt work. i'll keep you posted.
How do you debug an ASM in Visual Studio? I can't figure it out. I can do it if the ASM crashes but this program isn't crashing its just doing the wrong thing.
Debugging in Visual Studio is a pain unless its in vb/vc#.
For assembly code i use ollydbg (http://www.ollydbg.de/)
But if you really want to do it in Visual Studio - you insert user breakpoints i.e.
int 3 ;User Breakpoint
;Code
mov ax, [blahblah]
This will actually cause the program to crash :P because windows considers int 3 as a problem with your program. Int 3 is the official way of putting a breakpoint to crash your program but in a debugger , you can step over it easily unlike other crashes because its just a breakpoint.
If you are thinking of step by step debugging - you can load a exe in visual studio i think and start by stepping in - then you probably can highlight areas you want to breakpoint. However, I find Visual Studio too slow to load for my liking so i use Ollydbg.
Cheers.
Last edited by Raedwulf; Dec 9th, 2005 at 04:56 AM.
It won't assemble - either because I don't have AWFont.INC or maybe my masm command line is wrong or maybe because im using MASM 7.1
Could you give me your command line for assembling?
D:\masm32\Code\Lines>ml lines.asm /FeTestLine.exe
Microsoft (R) Macro Assembler Version 7.10.3077
Copyright (C) Microsoft Corporation. All rights reserved.
Assembling: lines.asm
awgrafix.inc(35) : error A2074: cannot access label through segment registers
awgrafix.inc(56) : error A2074: cannot access label through segment registers
lines.asm(31) : error A2006: undefined symbol : DGROUP
I've highlighted the correction I made (changed a jbe to a jle because I forgot it was a signed value.
Next I'm going to check for horizontal or vertical lines and treat them separately. For the horizontal lines I can write 4 pixels at once by filling eax with color bytes and then writing eax to VRAM repeatedly. I'll post the code once i've finished it and optimised it
Thanks for everyone's help.
Code:
PlotPixel PROC USES ax bx di dx,
x:WORD,
y:WORD,
color:BYTE
mov ax, y ; store y coord
mov bx, SCREEN_WIDTH
cwd ; empty dx ready for mul
mul bx ; y * screen width
add ax, x ; + x
mov di, ax ; pixel's VRAM address
mov al, color
mov BYTE PTR es:[di], al ; plot the pixel
ret
PlotPixel ENDP
;---------------------------
DrawLine PROC,
x0:WORD,
y0:WORD,
x1:WORD,
y1:WORD,
color:BYTE
;
; An implementation of the Bresenham line-drawing algorithm
; Translated to ASM by Adam Ward, 10/12/05
;---------------------------
LOCAL deltax:WORD,
deltay:WORD,
er:WORD,
xstep:WORD,
ystep:WORD
pusha
; validate all the arguments (both coords are on screen)
mov ax, SCREEN_WIDTH
mov bx, SCREEN_HEIGHT
xor cx, cx
cmp x0, ax
jae DONE
cmp x1, ax
jae DONE
cmp y0, bx
jae DONE
cmp y1, bx
jae DONE
;####################################
;### START OF BRESENHAM ALGORITHM ###
;####################################
; cx = abs(y1 - y0) > abs(x1 - x0) ####################
mov ax, y1
sub ax, y0
jns ABS_Y_DONE
neg ax ; number is negative, so make it positive
ABS_Y_DONE:
mov bx, x1
sub bx, x0
jns ABS_X_DONE
neg bx ; number is negative, so make it positive
ABS_X_DONE:
cmp ax, bx
jbe ELSE1
; ax > bx
mov cx, 1
jmp ENDIF1
ELSE1:
; ax <= bx
mov cx, 0
ENDIF1:
; if cx then ####################
jcxz ELSE2
; swap(x0, y0)
mov ax, x0
xchg ax, y0
mov x0, ax
; swap(x1, y1)
mov ax, x1
xchg ax, y1
mov x1, ax
INVOKE PlotPixel, y0, x0, color
jmp ENDIF2
ELSE2:
INVOKE PlotPixel, x0, y0, color
ENDIF2:
; deltax = abs(x1 - x0) ###########
mov ax, x1
sub ax, x0
jns ABS_X2_DONE
neg ax ; number is negative, so make it positive
ABS_X2_DONE:
mov deltax, ax
; deltay = abs(y1 - y0) ###########
mov ax, y1
sub ax, y0
jns ABS_Y2_DONE
neg ax ; number is negative, so make it positive
ABS_Y2_DONE:
mov deltay, ax
; er = 0 ##########
mov er, 0
; bx = x0 #########
mov bx, x0
; dx = y0 #########
mov dx, y0
; if x0 < x1 then #########
cmp bx, x1
jae ELSE3
; xstep = 1
mov xstep, 1
jmp ENDIF3
ELSE3:
; xstep = -1
mov xstep, -1
ENDIF3:
; if y0 < y1 then #########
cmp dx, y1
jae ELSE4
; ystep = 1
mov ystep, 1
jmp ENDIF4
ELSE4:
; ystep = -1
mov ystep, -1
ENDIF4:
; while bx != x1 ###############
L1:
cmp bx, x1
je DONE
; bx = bx + xstep
add bx, xstep
; er = er + deltay
mov ax, er
add ax, deltay
mov er, ax
; if 2 * er > deltax ##########
; (er value is still in ax...)
shl ax, 1 ; er * 2
cmp ax, deltax
jle ENDIF5
; dx = dx + ystep
add dx, ystep
; er = er - deltax
mov ax, deltax
sub er, ax
ENDIF5:
; if cx then #############
jcxz ELSE6
; plot(dx, bx)
INVOKE PlotPixel, dx, bx, color
jmp L1 ; SHORTCUT TO BEGINNING OF WHILE LOOP
ELSE6:
; plot(bx, dx)
INVOKE PlotPixel, bx, dx, color
jmp L1 ; continue the while loop
DONE:
popa
ret
DrawLine ENDP
;--------------------------------
PlotPixel PROC USES ax bx di dx,
x:WORD,
y:WORD,
color:BYTE
;
; Plots a single pixel at given coords in the given color
;--------------------------------
mov ax, y ; store y coord
mov bx, SCREEN_WIDTH
mul bx ; y * screen width
add ax, x ; + x
mov di, ax ; pixel's VRAM address
mov al, color
mov BYTE PTR es:[di], al ; plot the pixel
ret
PlotPixel ENDP
;---------------------------
DrawLine PROC USES eax bx cx dx di si,
x0:WORD,
y0:WORD,
x1:WORD,
y1:WORD,
color:BYTE
;
; An implementation of the Bresenham line-drawing algorithm
; Translated to ASM by Adam Ward, 10/12/05
;
; NOTES:
; - Treats horizontal and vertical lines separately for extra speed.
; - Horizontal lines with a length that is a multiple of 4 will be the most efficient.
; - Single pixels are the least efficient (Use PlotPixel instead)
;---------------------------
LOCAL deltax:WORD,
deltay:WORD,
xstep:WORD,
ystep:WORD
; validate all the arguments (both coords are on screen)
mov ax, SCREEN_WIDTH
mov bx, SCREEN_HEIGHT
xor cx, cx
cmp x0, ax
jae DONE
cmp x1, ax
jae DONE
cmp y0, bx
jae DONE
cmp y1, bx
jae DONE
mov ax, y0
cmp ax, y1
je LINE_IS_HORIZONTAL
mov ax, x0
cmp ax, x1
je LINE_IS_VERTICAL
;####################################
;### START OF BRESENHAM ALGORITHM ###
;####################################
; cx = abs(y1 - y0) > abs(x1 - x0) ####################
mov ax, y1
sub ax, y0
jns ABS_Y_DONE
neg ax ; number is negative, so make it positive
ABS_Y_DONE:
mov bx, x1
sub bx, x0
jns ABS_X_DONE
neg bx ; number is negative, so make it positive
ABS_X_DONE:
cmp ax, bx
jbe ELSE1
; ax > bx
mov cx, 1
jmp ENDIF1
ELSE1:
; ax <= bx
mov cx, 0
ENDIF1:
; if cx then ####################
jcxz ELSE2
; swap(x0, y0)
mov ax, x0
xchg ax, y0
mov x0, ax
; swap(x1, y1)
mov ax, x1
xchg ax, y1
mov x1, ax
INVOKE PlotPixel, y0, x0, color
jmp ENDIF2
ELSE2:
INVOKE PlotPixel, x0, y0, color
ENDIF2:
; deltax = abs(x1 - x0) ###########
mov ax, x1
sub ax, x0
jns ABS_X2_DONE
neg ax ; number is negative, so make it positive
ABS_X2_DONE:
mov deltax, ax
; deltay = abs(y1 - y0) ###########
mov ax, y1
sub ax, y0
jns ABS_Y2_DONE
neg ax ; number is negative, so make it positive
ABS_Y2_DONE:
mov deltay, ax
; si = 0 ##########
xor si, si
; bx = x0 #########
mov bx, x0
; dx = y0 #########
mov dx, y0
; if x0 < x1 then #########
cmp bx, x1
jae ELSE3
; xstep = 1
mov xstep, 1
jmp ENDIF3
ELSE3:
; xstep = -1
mov xstep, -1
ENDIF3:
; if y0 < y1 then #########
cmp dx, y1
jae ELSE4
; ystep = 1
mov ystep, 1
jmp ENDIF4
ELSE4:
; ystep = -1
mov ystep, -1
ENDIF4:
; while bx != x1 ###############
L1:
cmp bx, x1
je DONE
; bx = bx + xstep
add bx, xstep
; er = er + deltay
add si, deltay
; if 2 * er > deltax ##########
mov ax, si
shl ax, 1 ; er * 2
cmp ax, deltax
jle ENDIF5
; dx = dx + ystep
add dx, ystep
; er = er - deltax
sub si, deltax
ENDIF5:
; if cx then #############
jcxz ELSE6
; plot(dx, bx)
INVOKE PlotPixel, dx, bx, color
jmp L1 ; SHORTCUT TO BEGINNING OF WHILE LOOP
ELSE6:
; plot(bx, dx)
INVOKE PlotPixel, bx, dx, color
jmp L1 ; continue the while loop
;########################################
LINE_IS_HORIZONTAL:
; find the length of the line
mov ax, x1
sub ax, x0
jz LINE_IS_VERTICAL ; single-pixel lines are better handled by the vertical algorithm
jns LH_OK
LH_SWAP:
neg ax ; we can change the sign of ax without having to subtract again
mov bx, x0
xchg bx, x1
mov x0, bx
LH_OK:
; AX now contains the length of the line (pixels)
inc ax
mov bx, TYPE DWORD
div bx
push dx ; the remainder, which is used as the second loop number
push ax ; the quotient which is used as the first loop number
; calculate the left-hand end of the line
mov ax, y0
mov bx, SCREEN_WIDTH
mul bx
add ax, x0
mov di, ax
; fill eax with color bytes
mov bl, color
mov bh, bl
mov ax, bx
shl eax, 16
mov ax, bx
; draw chunks of 4 pixels at a time to accelerate horizontal lines
pop cx
mov bx, TYPE DWORD
jcxz LH_REMAINDER ; avoid cx=0 looping error
LH1:
mov DWORD PTR es:[di], eax
add di, bx
Loop LH1
; draw the remaining 1 - 3 bytes if required
LH_REMAINDER:
pop cx ; remainder (so 1 pixel at a time)
jcxz DONE ; avoid cx=0 looping error
LH2:
mov BYTE PTR es:[di], al
inc di
Loop LH2
jmp DONE
;########################################
LINE_IS_VERTICAL:
; find the length of the line
mov ax, y1
sub ax, y0
jns LV_OK
LV_SWAP:
neg ax ; we can change the sign of ax without having to subtract again
mov bx, y0
xchg bx, y1
mov y0, bx
LV_OK:
; AX now contains the length of the line (pixels)
inc ax ; add 1 because its zero-based
mov cx, ax
; calculate the top end of the line
mov ax, y0
mov bx, SCREEN_WIDTH
mul bx
add ax, x0
mov di, ax
mov al, color ; source byte
; draw chunks of 4 pixels at a time to accelerate horizontal lines
mov bx, SCREEN_WIDTH
LV1:
mov BYTE PTR es:[di], al ; draw the pixel
add di, bx
Loop LV1
;########################################
DONE:
ret
DrawLine ENDP