Hi folks,

I remember seeing somewhere an efficient algorithm for constraining an input value to a maxiumum or minimum bound. Of course, I've been unable to find it again so I thought I'd ask here about what I assume is a well known technique, at least to assembly experts. Given a lower and upper bound of 0 and 4 respectively, the input sequence -2, -1, 0, 1, 2, 3, 4, 5, 6 would produce the output 0, 0, 0, 1, 2, 3, 4, 4, 4.

I'm fairly sure that the algorithm included subtraction and subsequent use of the carry flag but crucially involved no conditional branching. My Googling skills have failed to turn up the original site and the closest I have got is this Code Gem.

If this rings a bell would you mind pointing me in the right direction?

Regards

Michael
Posted on 2011-09-28 08:11:10 by michaelg
I think you're already in the right direction: cmovcc is the easiest/fastest way to do this.
Perhaps what you meant was the use of bitmasking, but cmovcc made that mostly obsolete.
However, the idea of that is something like this...
Say you want to limit a value x between 0 and UPPER.
You subtract UPPER from x. If x is smaller than UPPER, then the carry flag will be set, else it will be clear.
Now you will use a trick to convert the carry flag to a bitmask. This can be done with subtract-with-borrow (sbb reg, reg on x86). Namely, it will first subtract the register from itself, making it 0. Then it will subtract the carry flag. If no carry, it will stay 0. If carry, you will get -1, or all bits set.
Now you can use this mask to turn x into UPPER if x was larger, or leave x otherwise.
For example:

x - UPPER ; Set carry
mask = sbb() ; generate 0 or -1 bitmask
x = x & mask
x = x + (UPPER & (NOT mask))


As you can see, if the mask is 0 (x >= UPPER), the following happens:

x = x & 0 => x = 0
x = x + (UPPER & (NOT mask)) => x = 0 + (UPPER & -1) => x = UPPER

And with the mask being -1 (x < UPPER), you get this:

x = x & -1 => x = x
x = x + (UPPER & (NOT mask)) => x = x + (UPPER & 0) => x = x


So there you have the expected behaviour. I'll leave the actual x86 implementation as an exercise to the reader.

If you want to limit to a lower AND an upper bound, you could 'rotate' the number so that the lower bound becomes 0, then limit to the new upper bound, then 'rotate' it back up.
Something like this:

x = x - LOW
x = clamp(x, (HIGH-LOW)) ; (Same clamping beteen 0 and UPPER as described above)
x = x + LOW


Note: if the bounds are (power-of-two)-1, then the clamping can be done more easily (how?)
Posted on 2011-09-28 08:57:09 by Scali
Scali, you're a gem. I'll be able to spend some time understanding the technique when I'm not meant to be doing the day job ;)

Thanks very much,

Michael
Posted on 2011-09-28 09:28:01 by michaelg
PMAXUD/PMINUD may also be an option.
Posted on 2011-10-09 07:28:23 by ti_mo_n