Bitwise help!!!

[Malmer]

I have a problem. I have a value that I don't want to be bigger than 255. If it is higher than 255 then it should use 255. In other words<br><br>270: use 255<br>75: use 75<br><br>Now, I can do this easily using a conditional if statment or maybe even inline conditions (a > b ? a : b), but both of these operations are sloooow, so what I want is some way to make it using bitshifts and bitwise operators. I know you guys are programming minds so I know you can help me. Besides it would be a fun mini competition you guys could have or something. Simply showing who is the best "bitboy". I would also like to have the reverse, where if the value is below 0 it should be 0.<br><br>Both are appreciated.<br><br>Thanks!<br><br>- F

[Moose or Chuck]

if (a > b) {<br> int c;<br> a - b = c;<br> a << (c/2);<br>}<br><br>I just came up with quickly, so it's probably wrong, and I've never used bit shifters before. But that's my best guess. And I don't know what you're talking about, which thing is slow? The ":" or the ">" ? Cause if it's the ">" then I could come up with another way to use bitshifts too.

[Moose or Chuck]

if (a/255 = 1)<br>could work well too.<br>But .. whatever, I'm just guessing anyway.

[Moose or Chuck]

Se.. told you I had no clue what you were talking about Freddy Mauler.

[Dan East]

That can be done very easily and efficiently. Say i is the integer in question:<br><br>i&=0xff;<br><br>[edit] Just thought about that more. The result will never be greater than 255, but it may be less than that if i>255. Let me think on that one.<br><br>Dan East

[RICoder]

Is an int or short or what?<br><br>you could do<br>i&=0xff<br><br>Which is best and fastest, but has the problem stated by Dan East.<br><br>Why not (A>B?A:B) ?  Its gonna be faster than anything else I can think of.  I mean you'd have to get all the bits in the hiword to flip on if it is >0 and then OR it with the original anyway to do the test, so you have a comparisson no matter what, right?

[Digby]

What you wish to do is called Saturated Arithmetic.  I do this when mixing (summing) audio wave data because you don't want values rolling over/under as it results in a click or pop in the output.  I also do it clamping lighting values in my 3D code.  My stuff is done in ARM assembly and can't be translated to C/C++ easily, but basically is does a compare based on the Carry flag.<br><br>I haven't given a lot of thought to this sort of thing from a high-level language perspective, but why do you think the conditional is slow?  Have you measured it?  How many times are you calling this code per frame?<br><br>Dan, <br>The AND op you've posted is not the proper solution.  If the value is 256, your AND will give 0, when what he needs is 255.<br><br>Let me stew on this over lunch and if I come up with something I'll share it.<br><br>

[RICoder]

OK, you can try this. (Credit to The Broiler)<br><br>x = original value<br>L=lobyte of x<br>H=hibyte of x<br><br>L|=H; H<<;<br>L|=H; H<<;<br>L|=H; H<<;<br>L|=H; H<<;<br>L|=H; H<<;<br>L|=H; H<<;<br>L|=H; H<<;<br>L|=H;<br><br>Should produce the right value....but is it faster than a<b?a:b .... I don't know.

[RICoder]

Oops...can't use a normal shift....you have to use a wrap shift.....will find assm function and get back to you.

[RICoder]

Bad Fredrik!<br><br>You have occupied the minds of my office with this problem of yours!<br><br>I have an idea for you.  Use the register keyword when you define the variables for the comparison.  Then it'll be quick...<br><br>Bad Fredrik!<br><br>:)<br><br>Hey, is this for Argentum?  I thought you were shipping in a few weeks?  Hmmm.......

[Malmer]

It is for argentum. It is called for every semi-transparent pixel in a sprite each frame (which makes it quite many). I'd just thought I could do some optimizations. It works fine as it is, but if I managed to get this problem solved it would probably mean a lot to performance.<br><br>as for the i&=0xff; sollution I get the same results by just having it as a unsigned char so that doesn't help <br><br>Thanks for the effort. It appears noone has found the ultimate sollution so keep working on it lads. Who will be the first to "crack the nut"?

[Digby]

I came up with this for a 32-bit int:<br><br>    x &= (!(x >> 31))*0x7fffffff;<br>    x |= (!!(x >> 8 ))*255;<br>    x &= 255;<br><br>Obviously it's not all bit shifts as there are two multiplies used.  You could replace those with 2-entry lookup tables since the multiplicand will be either 1 or 0.  However fetching from a table in memory is probably going to be slower than doing the multiplication since x will most likely be in a register.<br><br>I still contend that doing the conditional test to perform the clamp will be faster, not to mention it's more readable.<br><br>   x = min(255, max(0, x));<br><br><br>

[Dan East]

Fredrik, I can't think of an efficient way to do it without conditional logic. What you want (not even counting negative integers) from a bitwise standpoint is if any bit 0xffffff00 is non zero, then the output should be 0x000000ff. Obviously the lowest 8 bits can be any value in that case, so we would have to set them explicitly. Only one of the upper 24 bits need be set, so we don't have a known set of bits to shift over or try and work with.<br>[pause]<br>I've thought about it some more, and I'm pretty sure it can't be done (more efficiently) without conditional statements. In some situations you want to leave the bits 0xff as-is, while in others you want to set them. That requires logic. <br><br>Like you suggested:<br>i>0xff ? 0xff : i;<br><br>I would recommend creating a lookup table. I assume you are performing math on two bytes and want the result to be a byte. Precalculate a lookup table, which will take 65k or RAM (which really is not much, PQ allocates at least 100 times more at startup). Not only will it save you the processing required to check for the overflow / underflow problem you stated above, but it will save the actual math required to do the sprite transparency.<br><br>Dan East

[Malmer]

You know what? I think I'm gonna leave it as it is with the conditional statement for now. In a later patch we might have an optimized version. Now that code is pretty fast anyways, so there shouldn't be any big troubles...but it is always fun to have the code FASTER!!!<br><br>THANKS FOR ALL YOUR HELP!!! You guys are great and this is the only forum where I can actually get some decent replies. In other forums I would just get "what is a bitwise operator?" and "Malmer, what kinda name is that, it sounds like Mauler" <br><br>-- F<br><br>

[Digby]

Before you revisit this you might want to comment out the alpha blending routine and profile the drawing code.  Then put it back in and note the difference.  If the performance increase is miniscule, then you might want to point your optimization efforts elsewhere.<br><br>I wish there was a decent profiler available for eVC.  I'd like to compare the speed of using a lookup table to perform alpha blending vs. using a multiply and a bit shift.<br><br>PQ allocates over 6.5M at startup?  Now that is sassy!<br><br>