flat assembler
Message board for the users of flat assembler.

 Index > DOS > Line drawing
Author
me239

Joined: 06 Jan 2011
Posts: 200
me239 25 Mar 2011, 04:38
Hello, I recently came across a simple line drawing routine much shorter than Bresenham, but there is one part I don't quite understand. Here is the complete routine:
Code:
```les DI, Screen.Buffer
mov BX, Y1
add DI, WORD [BX+Screen.YTable]  { DI := Y1*320+X1 }

mov AX, X2   { DeltaX := X2-X1+1 }
mov BX, Y2   { DeltaY := Y2-Y1+1 }
sub AX, X1
sub BX, Y1
inc AX
inc BX

{ ShortLen := DeltaX DIV DeltaY
Rem := DeltaX MOD DeltaY }

xor DX, DX  { Clear upper word       }
div BX      { AX = ShortLen DX = Rem }
mov CX, AX   { CX = ShortLen }

xor AX, AX   { Rem is already SHL 16 }
div BX       { Incr := (LONGINT(Rem) SHL 16) DIV DeltaY }

mov SI, AX   { SI := Incr }

mov DX, CX             { DX = ShortLen                               }
mov AH, BL             { AH = DeltaY                                 }
mov AL, Color
xor CX, CX             { Initialize CX to zero                       }
mov BX, 32768          { BX = 0.5 SHL 16                             }
@InnerLoop:
add BX, SI             { Update our fraction...                      }
adc CX, DX             { If it overflows, then draw a long line!     }
rep stosb              { Draw the run (Sets CX to zero)              }
add DI, Screen.Width   { Next Y!                                     }

dec AH
jnz @InnerLoop         { Try again
```

And this is the part I don't understand
Code:
```mov BX, 32768          { BX = 0.5 SHL 16                             }
@InnerLoop:
add BX, SI             { Update our fraction...                      }
adc CX, DX             { If it overflows, then draw a long line!     }
```

I understand that is is a overflow catcher, but the part that makes no sense to me is the .5 shl 16. Why does shifting .5 right 16 times and then adding SI to it work?
Oh and one more problem. Why does this work and what does it produce?
Code:
```xor AX, AX   { Rem is already SHL 16 }
div BX       { Incr := (LONGINT(Rem) SHL 16) DIV DeltaY }
```
25 Mar 2011, 04:38
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20214
Location: In your JS exploiting you and your system
revolution 25 Mar 2011, 04:44
It is adding one half (0.5) using fixed point (16 bit integer and 16 bit fraction) arithmetic.
25 Mar 2011, 04:44
me239

Joined: 06 Jan 2011
Posts: 200
me239 25 Mar 2011, 21:13
revolution wrote:
It is adding one half (0.5) using fixed point (16 bit integer and 16 bit fraction) arithmetic.
Well could you explain how it works? Thanks
25 Mar 2011, 21:13
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20214
Location: In your JS exploiting you and your system
revolution 25 Mar 2011, 23:11
me239 wrote:
Well could you explain how it works? Thanks
http://en.wikipedia.org/wiki/Fixed-point_arithmetic
25 Mar 2011, 23:11
me239

Joined: 06 Jan 2011
Posts: 200
me239 26 Mar 2011, 02:07
revolution wrote:
me239 wrote:
Well could you explain how it works? Thanks
http://en.wikipedia.org/wiki/Fixed-point_arithmetic
Thanks one last thing though, why when AX is empty and DX has a value the DIV command returns a number in AX.
26 Mar 2011, 02:07
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20214
Location: In your JS exploiting you and your system
revolution 26 Mar 2011, 02:42
me239 wrote:
... one last thing though, why when AX is empty and DX has a value the DIV command returns a number in AX.
Weel as the Intel/AMD manual will tell you, DIV returns the quotient in AX and the remainder in DX.
26 Mar 2011, 02:42
me239

Joined: 06 Jan 2011
Posts: 200
me239 26 Mar 2011, 04:48
revolution wrote:
me239 wrote:
... one last thing though, why when AX is empty and DX has a value the DIV command returns a number in AX.
Weel as the Intel/AMD manual will tell you, DIV returns the quotient in AX and the remainder in DX.
Yes I know that, but AX is empty. So why does AX have a value AFTER the div command. Here is an example
Code:
```mov dx, 2 ; DX = 2
xor ax, ax ; AX = 0
mov bx, 10d ; BX = 0Ah
div bx ; Now AX hold 3333h?!?
int 20h
```
26 Mar 2011, 04:48
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20214
Location: In your JS exploiting you and your system
revolution 26 Mar 2011, 04:54
DX:AX == 0002:0000
BX == 000A

DX:AX / BX = 20000h / 0Ah = 3333h (in AX) + 2 remainder (in DX).
Same as: 131072 / 10 = 13107.2
26 Mar 2011, 04:54
me239

Joined: 06 Jan 2011
Posts: 200
me239 26 Mar 2011, 05:19
revolution wrote:
DX:AX == 0002:0000
BX == 000A

DX:AX / BX = 20000h / 0Ah = 3333h (in AX) + 2 remainder (in DX).
Same as: 131072 / 10 = 13107.2
Thanks man! I'm still trying to decipher what the .5 shl 16 is really for with respect to the code, but thanks anyway
26 Mar 2011, 05:19
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20214
Location: In your JS exploiting you and your system
revolution 26 Mar 2011, 12:26
me239 wrote:
I'm still trying to decipher what the .5 shl 16 is really for with respect to the code, but thanks anyway
To get good visual results one usually starts half way through the slope when rasterising the lines. Consider a long horizontal line that rises only one pixel vertically. If you start your rasterising at zero offset then you see the line as mostly being drawn on the lower horizontal and only get one pixel in the upper horizontal line at the very end. Whereas if you start at the halfway point then you get a half length lines in both the two horizontal pixel lines. Remember you are quantising a non-integer X/Y values into integer pixel display memory.

Anyhow, I suggest you try it with a zero value in BX instead of the 0.5 value and watch what happens to lines of various slopes. And then try with 3/4, or some other value, and see the results.
26 Mar 2011, 12:26
bitRAKE

Joined: 21 Jul 2003
Posts: 3977
Location: vpcmipstrm
bitRAKE 28 Mar 2011, 05:38
Think about it in binary.

0001 in binary is one. If you divide this number by two (i.e. shift right by one) the answer is one half. We can represent this as 0000.1000 -- requiring a fractional register with the high bit set. Each position to the right of the decimal represents negative powers of two: 2^-1, 2^-2, 2^-3, ... Work through smaller examples in binary until you are fully convinced as this is a very useful technique.
28 Mar 2011, 05:38
me239

Joined: 06 Jan 2011
Posts: 200
me239 28 Mar 2011, 23:05
bitRAKE wrote:
Think about it in binary.

0001 in binary is one. If you divide this number by two (i.e. shift right by one) the answer is one half. We can represent this as 0000.1000 -- requiring a fractional register with the high bit set. Each position to the right of the decimal represents negative powers of two: 2^-1, 2^-2, 2^-3, ... Work through smaller examples in binary until you are fully convinced as this is a very useful technique.
I'm understanding the fixed point math using DX:AX, but I'm still confused as to why adding 32768(.1) make an accurate line.
28 Mar 2011, 23:05
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20214
Location: In your JS exploiting you and your system
revolution 28 Mar 2011, 23:09
me239 wrote:
I'm understanding the fixed point math using DX:AX, but I'm still confused as to why adding 32768(.1) make an accurate line.
32768 is 1/2, not 0.1.

Did you try it with a zero value yet? When you see the results then you will understand why.
28 Mar 2011, 23:09
me239

Joined: 06 Jan 2011
Posts: 200
me239 29 Mar 2011, 01:37
revolution wrote:
me239 wrote:
I'm understanding the fixed point math using DX:AX, but I'm still confused as to why adding 32768(.1) make an accurate line.
32768 is 1/2, not 0.1.

Did you try it with a zero value yet? When you see the results then you will understand why.
Yes I tried it with a zero value and I understand that it works, but why it works is still beyond me. PS we are talking about xor'ing out BX right? Just wanted to make sure we're on the same page. Also I now see that it isn't .1. I had been looking at it from a binary viewpoint . Anyways thanks!
29 Mar 2011, 01:37
bitRAKE

Joined: 21 Jul 2003
Posts: 3977
Location: vpcmipstrm
bitRAKE 29 Mar 2011, 05:45
Adding 1/2 centers the overflow. Look at a steep/shallow line and compare different starting values for BX - the steps will move, 1/2 gives the most esthetically pleasing line - symmetric steps.
29 Mar 2011, 05:45
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum