:)

Hey, everybody!

here's a cheap trick I came up with to test if a value is in range
[0,upper] with only one jump. (actually, I was trying to come up
with a one jump test for the general case but
the result is much better if we assume lower=0)

anyways, assume eax=value to test

lea edx,
xor edx,eax
jns out_of_bounds

or, if upper is not constant

mov edx,eax
sub edx,upper
xor edx,eax
jns out_of_bounds

Hehe... probably useless, or everybody knows this trick already, but hey! I got nothing else to post... :)


--Chorus
Posted on 2002-03-17 22:58:29 by chorus
Still can't make the generic as fast as I would like. Anybody got some suggestions? Here's what I'm using:

mov edx,lower
mov ecx,upper
sub edx,value
sub ecx,value
xor edx,ecx
jns out_of_bounds

of course, the most obvious way is to do

cmp value,lower
jl out_of_bounds
cmp value,higher
jg out_of_bounds

but I'm trying to stay away from the jumps :)
One thing I like about my version is that lower and upper don't have to necessarily satisfy lower<upper. It'll work regardless. Also, I often check 2 values at a time to the bounds. They interleave pretty well if I wanna wipe out some registers :)

Talk to you later

--Chorus
Posted on 2002-03-18 08:10:43 by chorus
You should check out this thread :)
Posted on 2002-03-18 11:06:17 by Eóin
heh.. didn't see that :)
but very nice... thanks Eoin!
Posted on 2002-03-18 13:55:19 by chorus

:)

Hey, everybody!

here's a cheap trick I came up with to test if a value is in range
[0,upper] with only one jump. (actually, I was trying to come up
with a one jump test for the general case but
the result is much better if we assume lower=0)

anyways, assume eax=value to test

lea edx,
xor edx,eax
jns out_of_bounds
--Chorus
Hmm.. I don't get why the above should be better than a simple:

cmp eax,upper
jae out_of_bounds

?
Posted on 2002-03-22 17:18:12 by Maverick
Meveric, in your code you check only if it >= high bound, and don't
check low bound. Following code checks
.IF eax >=39h or eax <=30h



lea ecx,[eax-30h]
cmp ecx,9
ja @notdigit
Posted on 2002-03-23 00:32:13 by The Svin
Yes, I was wondering what that XOR trick had to offer.. I guess nothing important. LEA is a wonderful instruction, also because lets you do also a very limited multiplication for free, if necessary.
Posted on 2002-03-23 04:51:39 by Maverick
I was wondering what that XOR trick had to offer

it supposed to set SF if the number in eax is in boundries.
code needs to be like that for (30h<=x<=39h) not to spoil value:

lea ecx,[-39h]
lea edx,
xor ecx,edx
jns @notinrange
Posted on 2002-03-23 05:53:41 by The Svin


it supposed to set SF if the number in eax is in boundries.
code needs to be like that for (30h<=x<=39h) not to spoil value:

lea ecx,[-39h]
lea edx,
xor ecx,edx
jns @notinrange


Yes, but I mean.. what does the above offer that the following doesn't?



lea ecx,[eax-30h]
cmp ecx,9
ja @notdigit
Posted on 2002-03-23 06:54:24 by Maverick
Yes, but I mean.. what does the above offer that the following doesn't?

Nothing, of course. :)
Posted on 2002-03-23 07:17:16 by The Svin
okee dokee...

Maverick: I've got a very simple answer to your questions: I goofed. In trying to find a generic test I came up with the xor test which still needed some work. But I was looking at it and was like "Hey, if I let lower=0 then there's only 3 instructions". At the time it seemed like a reasonably good improvement over cmp value,0/jl out_of_bounds/cmp value,upper/jg out_of_bounds. Needless to say, I completely overlooked the jae instruction which ignores signed values, and hence will treat numbers less than 0 as numbers greater than upper allowing the all-in-one test :) My method seemed an improvement over the straight-forward calculation, and furthermore since I was actually calculating two bounds checks at once (checking two indices into an array), it seemed to pair up alright saving me that o so precious one clock cycle :)

As for how the method works, it's pretty simple. For a number to be between two values (lower,upper) then it must simultaneously be above one and below the other. Hence, when you calc value-upper and value-lower one *must* be signed and one *must* not be. The xor simply verifies that this is true.

To be honest, I've changed my code to your cmp/jae that you mentioned above. And for the generic case I'll be using the version that Eoin first pointed me towards (the lea/cmp/jae).

But I'll be going back to the drawing board to see if I can come up with something that tests two bounds checks as quickly as possible. Although I think it'll be hard to beat cmp value1,upper1/jae out_of_bounds/cmp value2,upper2/jae out_of_bounds :)

Thanks everybody for the input! I think I would have ended up leaving my code with my original bit and that would have been dumb... :)

Thanks to Svin too for defending my xor method. Maverick is right though.. the cmp/jae is better :D

talk to everybody later

--Chorus
Posted on 2002-03-23 07:22:25 by chorus
Thanks to Svin too for defending my xor method.


I didn't defend your method.
I showed Meveric error in his code, and explain him why xor operation was involved.
Posted on 2002-03-23 09:31:53 by The Svin
Well, thanks for whatever you did, then :)

--Chorus
Posted on 2002-03-23 09:50:53 by chorus



I didn't defend your method.
I showed Meveric error in his code, and explain him why xor operation was involved.
Hmm.. what error? What code? ;)
Posted on 2002-03-23 15:54:50 by Maverick
Posted on 2002-03-24 13:12:31 by Nexo
Wrong, The Svin: if valid bounds are, as is often the case (and always in C/C++ language, for example), from 0 (included) to upper (excluded), then "jae out_of_bounds" will work perfectly. You know, jae means unsigned arithmetic, so FFFFFFFFh will automatically be out of bounds.
Posted on 2002-03-24 16:02:57 by Maverick
Could you tell me, please, what we are talking about.
I'm complitely lost.
In your post (to wich I first replyed) you showed code that checked one boundry but doesn't another.
The only thing I wished to say - to point out to it.
Is that what we are talking about or anything else?
If array is uninterrupted you may check just one boudry, it's obvious.

Why this d**m English became an international language? :)
I'd better learn Italian, at least it is closer to logical Latin.

Vale!
Posted on 2002-03-24 17:44:57 by The Svin
Hi The Svin :)
Well, my original post was just this:

---


lea edx,
xor edx,eax
jns out_of_bounds


Hmm.. I don't get why the above should be better than a simple:

cmp eax,upper
jae out_of_bounds

?

---

I just wondered what advantages (I'd bet none, but wanted to ask anyway) would the chorus' method offer.. expecially in the resulting flags set.

Anyway.. have a nice day ;)
Posted on 2002-03-25 05:17:55 by Maverick
PS: if you look carefully (maybe that's what made the misunderstanding arise), the chorus' code I mentioned doesn't check for lower bounds anyway.. so my question was specifically about the XOR method. (XOR instructions can be really nice and tricky sometimes.. to count bits, to swap vars, etc..).
Posted on 2002-03-25 05:19:55 by Maverick
Actually,... if you look closely, my code *does* test for lower bounds. Only, in this case, lower bounds must be zero.
Here's how it works (but again, the other ideas presented here
by you, the Svin, and Nexo are preferable)

if you have bounds and a number c. Then c is between a and b if and only if (c-a) is of *different* sign then (c-b). In essence, what I'm testing is xor (c-b),(c-a). But since I let a=0 I just test xor (c-b),c or in the code xor edx,eax.

The reasoning behind the different signs method is that if both (c-b) and (c-a) are positive, then c is above both values. The opposite is true for negatives. The xor simply ensures that the result is only signed if (c-b) and (c-a) differ in signs

This *does* work. I've already tried it, it's what I was using in the first place.

Oh, and the other thing that I did find kinda useful is that there is no stipulation that a<b. You can choose the bounds in any order. For my particular application, that didn't matter, but I could see it coming in handy in the future.

See you all later :)

--Chorus
Posted on 2002-03-25 08:45:34 by chorus