flat assembler
Message board for the users of flat assembler.

Index > Main > Bresenham's linedrawing algorithm in ASM [SOLVED]

Goto page Previous  1, 2
Author
Thread Post new topic Reply to topic
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
BTW, currently I'm doing the most horrible task - hand-debugging some
values throughout the code. Like (100,100)-(200,89) that actually draws
the line from 100,100 to 0,111 Very Happy

...and sorry - I should have mentioned the order in which the register are
initialized: rax, rbx, rcx, rdx are X1, Y1, X2, Y2 respectively

About the mixing of registers: every way I swap them, even x1<>y2 and
x1<>y1 the result is the same - only 7th octant is "different" meaning if
I swap the two endpoints actually the 7th is the correct line Very Happy Sad thing
is that all others are in the opposite direction...
Post 03 Aug 2006, 10:25
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
AAAAAAAAAAAAAAAAHHHHHHHHHHH Very Happy so sweeet http://enos.itcollege.ee/~mkalme/PAHN/MenuetOS/untitled.PNG
every SINGLE blue line is in its place (A) nothing's off...

and I think you want to know what was wrong:
Code:
    lea         rdx,[rix+rdi]
    test        rdx,rdx
    jne         @f
    neg         rdi
    neg         rix
  @@:
    


This was missing from the part where dx>dy
I had to put a name to the jump because the new code introduced a jump
Look why @@s are bad Very Happy
Code:
    cmp         rex,rfx
    jc          .ver2
    xor         rsi,rsi ; xinc1 = 0
    xor         rjx,rjx ; yinc2 = 0

;=>RIGHT HERE

    mov         rkx,rex ; den = deltax
    mov         rlx,rex
    shr         rlx,1   ; num = deltax/2
    mov         rbp,rfx ; numadd = deltay
    mov         rdx,rex ; numpixels = deltax
    jmp         .endloc
  .ver2:
    



THANKs for eberybody who contributed! You got me closer to the answer and
finally its here...now I'll try to make this code fragment more transparent
and fit it somewhere in the code...meaning - I will optimize a bit Wink


Last edited by Madis731 on 03 Aug 2006, 11:37; edited 2 times in total
Post 03 Aug 2006, 11:26
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1605
Location: Ukraine
shoorick
Smile
Post 03 Aug 2006, 11:33
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
ARGH you won't believe how angry I am with MYSELF !!!! Evil or Very Mad Evil or Very Mad Evil or Very Mad

I wrote down RSI, RDI for Xs and RIX, RJX for Ys, but EVERYWHERE else I used
them as RSI, RIX for Xs and RDI, RJX for Ys. I wondered why this fragment of
code fitted everywhere and then I finally just optimized it to:
Code:
xchg rdi,rix
    

C'mon - everyone can only DREAM about this kind of optimization. THEN I
remembered what Shoorick said and Voila! there it was - rsi and rdi standing
as if they where Xs Razz

Okay - the WORKING unoptimized, but small and fast code Very Happy
Code:
    mov         rex,rcx ;rbx=x2
    sub         rex,rax ;rax=x1
    sbb         rhx,rhx
    xor         rex,rhx
    sub         rex,rhx ;rex=abs(rcx-rax)
    mov         rfx,rdx ;rdx=y2
    sub         rfx,rbx ;rcx=y1
    sbb         rhx,rhx
    xor         rfx,rhx
    sub         rfx,rhx ;rfx=abs(rdx-rbx)

    or          rsi,-1
    or          rix,-1
    cmp         rcx,rax
    jc          .X2notlessthanX1
    neg         rsi
    neg         rix
  .X2notlessthanX1:
    or          rdi,-1
    or          rjx,-1
    cmp         rdx,rbx
    jc          .Y2notlessthanY1
    neg         rdi
    neg         rjx
  .Y2notlessthanY1:

    cmp         rex,rfx
    jc          .moreYthanX
    xor         rsi,rsi ; xinc1 = 0
    xor         rjx,rjx ; yinc2 = 0

    mov         rkx,rex ; den = deltax
    mov         rlx,rex
    shr         rlx,1   ; num = deltax/2
    mov         rbp,rfx ; numadd = deltay
    mov         rdx,rex ; numpixels = deltax
    jmp         .endadjust
  .moreYthanX:

    xor         rdi,rdi ; xinc2 = 0
    xor         rix,rix ; yinc1 = 0
    mov         rkx,rfx ; den=deltay
    mov         rlx,rfx
    shr         rlx,1   ; num=deltay/2
    mov         rbp,rex ; numadd = deltax
    mov         rdx,rfx ; numpixels = deltay
  .endadjust:

  .linedraw:
    push        rax rbx rcx rdx rex rfx rsi rdi rix rjx
    mov         rex,rbx
    add         rex,1
    mov         rdx,rax
    mov         rcx,rbx
    mov         rbx,rax
    mov         rax,38
    mov         rfx,255
    int         60h
    pop         rjx rix rdi rsi rfx rex rdx rcx rbx rax
    add         rlx,rbp ; num += numadd
    cmp         rlx,rkx ; num >= den
    jc          @f
    sub         rlx,rkx ; num -= den
    add         rax,rsi
    add         rbx,rdi
  @@:
    add         rax,rix
    add         rbx,rjx
    sub         rdx,1
    jnc         .linedraw
    


Talk about Optimized to death Razz (http://board.flatassembler.net/topic.php?t=5584)

_________________
My updated idol Very Happy http://www.agner.org/optimize/
Post 03 Aug 2006, 11:59
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
Slightly faster absolute value using compare and move instruction
Code:
mov reg2, reg1
neg reg1
cmovl reg1, reg2 ;;;; cmovb if using UNsigned integers
    
Post 03 Aug 2006, 21:51
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7725
Location: Kraków, Poland
Tomasz Grysztar
r22 wrote:
Code:
mov reg2, reg1
neg reg1
cmovl reg1, reg2 ;;;; cmovb if using UNsigned integers
    

But the absolute value doesn't make much sense with the UNsinged integers, does it? Wink
Post 04 Aug 2006, 04:04
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Smile Not the UNsigned integers themself, but the difference of two unsigned ones...

@r22: Did you test it on AMD/Intel? I've heard that on AMD the conditional
move is slow and cmp/jcc is faster :S
Post 04 Aug 2006, 07:20
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7725
Location: Kraków, Poland
Tomasz Grysztar
Madis731 wrote:
Smile Not the UNsigned integers themself, but the difference of two unsigned ones...

For difference it doesn't really matter whether it is of signed or unsigned values.
Post 04 Aug 2006, 08:54
View user's profile Send private message Visit poster's website Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
Very true, BUT the comment would be valid IF it was used for a min/max function. That's exactly why I don't comment code, half the time I just type nonsense after ;'s.

The AMD64 optimization guide shows the cmov reg,reg as having a 1 clock latency and I've tested it on my AMD64 x2 3800+ and it's shown to be slightly faster than the carry method.
Post 04 Aug 2006, 12:10
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
@Tomasz: Of course - you are right - I wasn't thinking clearly. It does NOT matter! And more importantly you can even use it on signed values (i.e. if one or both of the source operands are negative in this sence).
Post 05 Aug 2006, 14:48
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.