Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Nothing happens.


programming / comp.lang.asm.x86 / Re: Assembly contest idea

SubjectAuthor
* Assembly contest ideaRick C. Hodgin
`* Re: Assembly contest ideaMelzzzzz
 +* Re: Assembly contest ideaRick C. Hodgin
 |+- Re: Assembly contest ideaTerje Mathisen
 |`* Re: Assembly contest ideaTerje Mathisen
 | `- Re: Assembly contest ideaRick C. Hodgin
 `- Re: Assembly contest ideawolfgang kern

1
Subject: Assembly contest idea
From: Rick C. Hodgin
Newsgroups: comp.lang.asm.x86
Organization: Liberty Software Foundation
Date: Tue, 13 Oct 2020 19:47 UTC
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: rick.c.h...@nospicedham.gmail.com (Rick C. Hodgin)
Newsgroups: comp.lang.asm.x86
Subject: Assembly contest idea
Date: Tue, 13 Oct 2020 15:47:32 -0400
Organization: Liberty Software Foundation
Lines: 23
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rm508m$vpl$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="5f794658e9ed57752ce83029fca811b5";
logging-data="1647"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19fG4FDq6UWHUUVDjPY3fc0BL4W6VbaInA="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
Thunderbird/68.10.0
Cancel-Lock: sha1:HX58/0sqUwsrB3PviNCwcc8LS+I=
View all headers
I was thinking if we could come up with a way to optimize a real-world problem I have right now.

I have two rectangles r1 and r2.  I need to determine if r1 is 1) fully inside, 2) partially inside, or 3) not inside r2.

The coordinates are all signed integers ranging from -32768 to +32767.

What do you think?

-----
BTW, the reason I haven't been here for our last competition is because I've been pursuing an idea that occurred to me about ten years ago. I've been working on an Open GL simulation bringing the idea to a visualization.  This theory answers a lot of unanswered questions about our solar system:

     Perspective:   https://www.youtube.com/watch?v=vf6cLeQcOVI
     Orthographic:  https://www.youtube.com/watch?v=FqpPFArfD7c

--
Rick C. Hodgin



Subject: Re: Assembly contest idea
From: Melzzzzz
Newsgroups: comp.lang.asm.x86
Organization: usenet-news.net
Date: Thu, 15 Oct 2020 02:00 UTC
References: 1
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Melzz...@nospicedham.zzzzz.com (Melzzzzz)
Newsgroups: comp.lang.asm.x86
Subject: Re: Assembly contest idea
Date: Thu, 15 Oct 2020 02:00:52 GMT
Organization: usenet-news.net
Lines: 27
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <o3OhH.2677854$1Eh.171218@fx46.ams4>
References: <rm508m$vpl$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="2840e3dfafc78e797ff0a83c2c332450";
logging-data="19689"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+FwC3ut44E56SO6x4hM14+aHtnBn8pn40="
User-Agent: slrn/1.0.3 (Linux)
Cancel-Lock: sha1:nEnpsb4BI3XPMx6mXkJrJFIMOZQ=
View all headers
On 2020-10-13, Rick C. Hodgin <rick.c.hodgin@nospicedham.gmail.com> wrote:
I was thinking if we could come up with a way to optimize a real-world
problem I have right now.

I have two rectangles r1 and r2.  I need to determine if r1 is 1) fully
inside, 2) partially inside, or 3) not inside r2.

The coordinates are all signed integers ranging from -32768 to +32767.

Too old for this ;)

I think that I solved this problem some 30 years ago :P


What do you think?


--
current job title: senior software engineer
skills: c++,c,rust,go,nim,haskell...

press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi --  Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi
bili naoruzani. -- Mladen Gogala



Subject: Re: Assembly contest idea
From: Rick C. Hodgin
Newsgroups: comp.lang.asm.x86
Organization: Liberty Software Foundation
Date: Thu, 15 Oct 2020 04:11 UTC
References: 1 2
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: rick.c.h...@nospicedham.gmail.com (Rick C. Hodgin)
Newsgroups: comp.lang.asm.x86
Subject: Re: Assembly contest idea
Date: Thu, 15 Oct 2020 00:11:41 -0400
Organization: Liberty Software Foundation
Lines: 23
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rm8i5t$j6v$1@dont-email.me>
References: <rm508m$vpl$1@dont-email.me> <o3OhH.2677854$1Eh.171218@fx46.ams4>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="2840e3dfafc78e797ff0a83c2c332450";
logging-data="23407"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18Rmzq0FtcOjBIaoaH/67ymlXKKriY5o8g="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
Thunderbird/68.10.0
Cancel-Lock: sha1:uJotrbqxZKx+e6j8bk+MIO9r594=
View all headers
On 10/14/20 10:00 PM, Melzzzzz wrote:
On 2020-10-13, Rick C. Hodgin <rick.c.hodgin@nospicedham.gmail.com> wrote:
I have two rectangles r1 and r2.  I need to determine if r1 is 1) fully
inside, 2) partially inside, or 3) not inside r2.
The coordinates are all signed integers ranging from -32768 to +32767.

Too old for this ;)

I think that I solved this problem some 30 years ago :P

I spent some time searching online for branchless compares to see if I could find some optimizations that would be useful.

I remember coming across a page that showed all kinds of optimizations for adding certain values, subtracting certain values, etc.

I'm thinking there is a way to take the values and perform only ADD, SUB, INC, DEC, OR, and XOR to get a result.  If it could be done for a type of between() function, the rest becomes academic.

--
Rick C. Hodgin



Subject: Re: Assembly contest idea
From: Terje Mathisen
Newsgroups: comp.lang.asm.x86
Organization: Aioe.org NNTP Server
Date: Thu, 15 Oct 2020 06:22 UTC
References: 1 2 3
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: terje.ma...@nospicedham.tmsw.no (Terje Mathisen)
Newsgroups: comp.lang.asm.x86
Subject: Re: Assembly contest idea
Date: Thu, 15 Oct 2020 08:22:31 +0200
Organization: Aioe.org NNTP Server
Lines: 32
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rm8pr9$1c9d$1@gioia.aioe.org>
References: <rm508m$vpl$1@dont-email.me> <o3OhH.2677854$1Eh.171218@fx46.ams4>
<rm8i5t$j6v$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="2840e3dfafc78e797ff0a83c2c332450";
logging-data="24597"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+OGG1scUSb6cSPxO40KnybA5ldCGKXZMc="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.4
Cancel-Lock: sha1:Y7ERAfPmnb8Xd7bNkL0sjIVv8yg=
View all headers
Rick C. Hodgin wrote:
On 10/14/20 10:00 PM, Melzzzzz wrote:
On 2020-10-13, Rick C. Hodgin <rick.c.hodgin@nospicedham.gmail.com> wrote:
I have two rectangles r1 and r2.  I need to determine if r1 is 1) fully
inside, 2) partially inside, or 3) not inside r2.
The coordinates are all signed integers ranging from -32768 to +32767.

Too old for this ;)

I think that I solved this problem some 30 years ago :P

I spent some time searching online for branchless compares to see if I could find some optimizations that would be useful.

I remember coming across a page that showed all kinds of optimizations for adding certain values, subtracting certain values, etc.

I'm thinking there is a way to take the values and perform only ADD, SUB, INC, DEC, OR, and XOR to get a result.  If it could be done for a type of between() function, the rest becomes academic.

You can obviously do a bunch of parallel compares, using SIMD opcodes:

Each AVX-512 register would hold 32 16-bit ints, so you can splat the ll/ur corners (4 values) of both rectangles (8 total) across up to 8 locations:

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"



Subject: Re: Assembly contest idea
From: Terje Mathisen
Newsgroups: comp.lang.asm.x86
Organization: Aioe.org NNTP Server
Date: Thu, 15 Oct 2020 06:40 UTC
References: 1 2 3
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: terje.ma...@nospicedham.tmsw.no (Terje Mathisen)
Newsgroups: comp.lang.asm.x86
Subject: Re: Assembly contest idea
Date: Thu, 15 Oct 2020 08:40:41 +0200
Organization: Aioe.org NNTP Server
Lines: 58
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rm8qtb$1ong$1@gioia.aioe.org>
References: <rm508m$vpl$1@dont-email.me> <o3OhH.2677854$1Eh.171218@fx46.ams4>
<rm8i5t$j6v$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="2840e3dfafc78e797ff0a83c2c332450";
logging-data="1211"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ZtU2NCB2vVgTIemyhi59unucRMqYevfc="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.4
Cancel-Lock: sha1:laH8NlAnm+pCzV7IFJxKoSljV60=
View all headers
Rick C. Hodgin wrote:
On 10/14/20 10:00 PM, Melzzzzz wrote:
On 2020-10-13, Rick C. Hodgin <rick.c.hodgin@nospicedham.gmail.com> wrote:
I have two rectangles r1 and r2.  I need to determine if r1 is 1) fully
inside, 2) partially inside, or 3) not inside r2.
The coordinates are all signed integers ranging from -32768 to +32767.

Too old for this ;)

I think that I solved this problem some 30 years ago :P

I spent some time searching online for branchless compares to see if I could find some optimizations that would be useful.

I remember coming across a page that showed all kinds of optimizations for adding certain values, subtracting certain values, etc.

I'm thinking there is a way to take the values and perform only ADD, SUB, INC, DEC, OR, and XOR to get a result.  If it could be done for a type of between() function, the rest becomes academic.

Did not finish my previous post:

The idea is that we need to compare the left edge of rectangle one against both the left and right edge of rectangle2, and the same for the right edge, so this is 8 compares for the vertical lines. Add the same for the horizontal and you need 16 compares which would fit in a much more common AVX register.

R2 totally inside R1 becomes

   (R2.l >= R1.l) AND (R2.r <= R1.r) AND
   (R2.b >= R1.b) AND (R2.a <= R1.a)

i.e. relatively simple, while zero overlap is much harder, and related to the clipping question from last week: It requires all of R2 to be either to the left, right, above or below, so there are 4 different masks that give the same result and you have to OR those together:

  (R2.r < R1.l) OR (R2.a < R1.b) OR (R2.l >= R1.r) OR (R2.b >= R1.a)

All that remains is to setup all those values in the correct spot so that these 8 compares can be done (some of them needs to be inverted after the fact obviously!) with a single compare_greater_or_equal() instruction. Seems doable by duplicating the R1 values so that each occur twice, then use a permute on the R2 values to put them in the right spots, do the compare, flip half the results and then the slowest part: Horizontally combine them with and AND for the inside result, with OR for outside, and then all partial overlaps fall out by being neither of these.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"



Subject: Re: Assembly contest idea
From: wolfgang kern
Newsgroups: comp.lang.asm.x86
Organization: KESYS-development
Date: Thu, 15 Oct 2020 07:10 UTC
References: 1 2
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: nowh...@nospicedham.never.at (wolfgang kern)
Newsgroups: comp.lang.asm.x86
Subject: Re: Assembly contest idea
Date: Thu, 15 Oct 2020 09:10:45 +0200
Organization: KESYS-development
Lines: 18
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rm8sr6$i13$1@gioia.aioe.org>
References: <rm508m$vpl$1@dont-email.me> <o3OhH.2677854$1Eh.171218@fx46.ams4>
Reply-To: nowhere@never.at
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="2840e3dfafc78e797ff0a83c2c332450";
logging-data="10958"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18ong6A9obB0WWnKuSopiM+6x86Zvosq38="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.3.2
Cancel-Lock: sha1:8psuRtlNIJaayHifz/Mq54w7jaU=
View all headers
On 15.10.2020 04:00, Melzzzzz wrote:
On 2020-10-13, Rick C. Hodgin <rick.c.hodgin@nospicedham.gmail.com> wrote:
I was thinking if we could come up with a way to optimize a real-world
problem I have right now.

I have two rectangles r1 and r2.  I need to determine if r1 is 1) fully
inside, 2) partially inside, or 3) not inside r2.

The coordinates are all signed integers ranging from -32768 to +32767.

Too old for this ;)

I think that I solved this problem some 30 years ago :P

:) me too, it was main part of mouse-rectangle's focus hierarchy.
__
wolfgang



Subject: Re: Assembly contest idea
From: Rick C. Hodgin
Newsgroups: comp.lang.asm.x86
Organization: Liberty Software Foundation
Date: Thu, 15 Oct 2020 16:31 UTC
References: 1 2 3 4
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: rick.c.h...@nospicedham.gmail.com (Rick C. Hodgin)
Newsgroups: comp.lang.asm.x86
Subject: Re: Assembly contest idea
Date: Thu, 15 Oct 2020 12:31:29 -0400
Organization: Liberty Software Foundation
Lines: 65
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <rm9th3$f79$1@dont-email.me>
References: <rm508m$vpl$1@dont-email.me> <o3OhH.2677854$1Eh.171218@fx46.ams4>
<rm8i5t$j6v$1@dont-email.me> <rm8qtb$1ong$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="2840e3dfafc78e797ff0a83c2c332450";
logging-data="19078"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18CxJalyE9dBIft7sQbd9kFW7dR2EBjeCw="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
Thunderbird/68.10.0
Cancel-Lock: sha1:xBSj9PwkklFXt9fYGXKw4AETiu8=
View all headers
On 10/15/20 2:40 AM, Terje Mathisen wrote:
The idea is that we need to compare the left edge of rectangle one against both the left and right edge of rectangle2, and the same for the right edge, so this is 8 compares for the vertical lines. Add the same for the horizontal and you need 16 compares which would fit in a much more common AVX register.

R2 totally inside R1 becomes

   (R2.l >= R1.l) AND (R2.r <= R1.r) AND
   (R2.b >= R1.b) AND (R2.a <= R1.a)

i.e. relatively simple, while zero overlap is much harder, and related to the clipping question from last week: It requires all of R2 to be either to the left, right, above or below, so there are 4 different masks that give the same result and you have to OR those together:

  (R2.r < R1.l) OR (R2.a < R1.b) OR (R2.l >= R1.r) OR (R2.b >= R1.a)

All that remains is to setup all those values in the correct spot so that these 8 compares can be done (some of them needs to be inverted after the fact obviously!) with a single compare_greater_or_equal() instruction. Seems doable by duplicating the R1 values so that each occur twice, then use a permute on the R2 values to put them in the right spots, do the compare, flip half the results and then the slowest part: Horizontally combine them with and AND for the inside result, with OR for outside, and then all partial overlaps fall out by being neither of these.

I'm thinking there's a relationship between the various values, such that for an inside test we will know:

         t
        ___
     l |   | r     // left, right, top, bottom
       |___|

         b

     r2.l is between r1.l and r1.r
     r2.r is between r1.l and r1.r

And the same will be true for r2.top and r2.bottom:

     r2.t is between r1.t and r1.b
     r2.b is between r1.t and r1.b

And if we assert that each l is less than r, and each t is less than b, is there some mathematical formula we can conclude?

     if     r2.r - r1.l - r2.l > x
        and r2.r - r1.r - r2.l > x
        and r2.b - r1.t - r2.t > y
        and r2.t - r1.t - r2.t > y

then we know the relationship is true?  It would be determining x and y, which surely are proportional to the rectangles and/or their relationships.  And once determined, we could possibly simplify the expressions to their minimums.

Something like that?  I don't know.  My mind is hazy on all this.

--
Rick C. Hodgin



1
rocksolid light 0.7.2
clearneti2ptor