7

Are there any branch-less or similar hacks for clamping an integer to the interval of 0 to 255, or a double to the interval of 0.0 to 1.0? (Both ranges are meant to be closed, i.e. endpoints are inclusive.)

I'm using the obvious minimum-maximum check:

int value = (value < 0? 0 : value > 255? 255 : value);

but is there a way to get this faster -- similar to the "modulo" clamp value & 255? And is there a way to do similar things with floating points?

I'm looking for a portable solution, so preferably no CPU/GPU-specific stuff please.

1
  • 3
    Your compiler may do the work for you if you use value = min (value, 255), especially if the hardware incorporates an integer MIN operation. Branchless sequences for min/max are well known and often have been incorporated into compilers.
    – njuffa
    Jul 25, 2015 at 22:37

5 Answers 5

7

This is a trick I use for clamping an int to a 0 to 255 range:

/**
 * Clamps the input to a 0 to 255 range.
 * @param v any int value
 * @return {@code v < 0 ? 0 : v > 255 ? 255 : v}
 */
public static int clampTo8Bit(int v) {
    // if out of range
    if ((v & ~0xFF) != 0) {
        // invert sign bit, shift to fill, then mask (generates 0 or 255)
        v = ((~v) >> 31) & 0xFF;
    }
    return v;
}

That still has one branch, but a handy thing about it is that you can test whether any of several ints are out of range in one go by ORing them together, which makes things faster in the common case that all of them are in range. For example:

/** Packs four 8-bit values into a 32-bit value, with clamping. */
public static int ARGBclamped(int a, int r, int g, int b) {
    if (((a | r | g | b) & ~0xFF) != 0) {
        a = clampTo8Bit(a);
        r = clampTo8Bit(r);
        g = clampTo8Bit(g);
        b = clampTo8Bit(b);
    }
    return (a << 24) + (r << 16) + (g << 8) + (b << 0);
}
7
  • Nice! Especially the combined OR hack. Indeed, handling RGB components was the starting point of this question.
    – Franz D.
    Jul 26, 2015 at 7:23
  • Some quick performance test showed that this is about 4 times faster (Java 1.6) than my method if 50% of some random inputs are out of range 0-255. My test indicates that it gets even MUCH faster (up to 12x!) if more of the inputs lie within the clamped range -- I would have thought the difference would become less significant due to better branch prediction, but this may just be an artefact of my sloppy performance test.
    – Franz D.
    Jul 26, 2015 at 7:37
  • @FranzD. I've personally found the advantage of the technique to be quite marginal, but the relative advantage of it depends of course on how much computation is involved in generating the values to be clamped in the first place.
    – Boann
    Jul 26, 2015 at 11:40
  • Of course -- my performance test just measured the clamping speed itself, and it was just meant for a quick'n'dirty first check. You would need to profile this in your production code to see the real difference.
    – Franz D.
    Jul 26, 2015 at 12:38
  • Is there any way to give this an arbitrary maximum value, such as 45 or 79? Jan 25, 2020 at 1:28
6

Note that your compiler may already give you what you want if you code value = min (value, 255). This may be translated into a MIN instruction if it exists, or into a comparison followed by conditional move, such as the CMOVcc instruction on x86.

The following code assumes two's complement representation of integers, which is usually a given today. The conversion from Boolean to integer should not involve branching under the hood, as modern architectures either provide instructions that can directly be used to form the mask (e.g. SETcc on x86 and ISETcc on NVIDIA GPUs), or can apply predication or conditional moves. If all of those are lacking, the compiler may emit a branchless instruction sequence based on arithmetic right shift to construct a mask, along the lines of Boann's answer. However, there is some residual risk that the compiler could do the wrong thing, so when in doubt, it would be best to disassemble the generated binary to check.

int value, mask;

mask = 0 - (value > 255);  // mask = all 1s if value > 255, all 0s otherwise
value = (255 & mask) | (value & ~mask);

On many architectures, use of the ternary operator ?: can also result in a branchless instruction sequences. The hardware may support select-type instructions which are essentially the hardware equivalent of the ternary operator, such as ICMP on NVIDIA GPUs. Or it provides CMOV (conditional move) as in x86, or predication as on ARM, both of which can be used to implement branch-less code for ternary operators. As in the previous case, one would want to examine the disassembled binary code to be absolutely sure the resulting code is without branches.

int value;

value = (value > 255) ? 255 : value;

In case of floating-point operands, modern floating-point units typically provide FMIN and FMAX instructions which map straight to the C/C++ standard math functions fmin() and fmax(). Alternatively fmin() and fmax() may be translated into a comparison followed by a conditional move. Again, it would be prudent to examine the generated code to make sure it is branchless.

double value;

value = fmax (fmin (value, 1.0), 0.0);
2
  • Does the conversion of a relational expression to an integer involve a conditional branch? Jul 26, 2015 at 4:41
  • @PatriciaShanahan Good point. I guess there is some risk that one is at the mercy of the compiler. Branches should not be involved on the most common architectures, such as ARM, which can form the mask through predication, and x86 which has SETcc. The compilers for PowerPC also emit branchless sequences as far as I know. NVIDIA GPUs have an ISETcc instruction which directly returns the mask as a result of the comparison. I'll update the answer pointing out that there is residual risk due to the compiler.
    – njuffa
    Jul 26, 2015 at 7:16
1

I use this thing, 100% branchless.

int clampU8(int val)
{
    val &= (val<0)-1;  // clamp < 0
    val |= -(val>255); // clamp > 255
    return val & 0xFF; // mask out
}
1
  • Very neat :) Although the branchlessity probably depends on compiler and system.
    – Franz D.
    May 13, 2021 at 16:16
1

For those using C#, Kotlin or Java this is the best I could do, it's nice and succinct if somewhat cryptic:

(x & ~(x >> 31) | 255 - x >> 31) & 255

It only works on signed integers so that might be a blocker for some.

3
  • Thanks Jean, pretty awesome first-time contribution :) My stupid brain has difficulties to completely understand it, but I see a clever use of the fact that 0 and 255 are just one apart (module 256). Haven't considered that before, but as I said -- my brain is stupid. (I'm allowed to say that, we're living together.)
    – Franz D.
    Dec 22, 2021 at 17:47
  • @FranzD. I created a small benchmark project over at github.com/jdarc/branchless if you're interested, it uses Kotlin but in theory the VM should be able to do the magic and figure out the optimal instructions. What's interesting is that the minmax version performs just as good as the one liner above, maybe it is using intrinsics of some kind?
    – user17722965
    Dec 23, 2021 at 19:31
  • Nice :) Yes, the performance of minmax() was surprising. It must be some compiler magic. Which goes to show that once more, good old Knuth is right with his root of all evil -- just do it the dumbest way possible to give the compiler the best chance of optimizing. Still, I'd be interested how minmax() compares to that nice OR-trick of the accepted solution.
    – Franz D.
    Dec 24, 2021 at 23:39
0

For clamping doubles, I'm afraid there's no language/platform agnostic solution.

The problem with floating point that they have options from fastest operations (MSVC /fp:fast, gcc -funsafe-math-optimizations) to fully precise and safe (MSVC /fp:strict, gcc -frounding-math -fsignaling-nans). In fully precise mode the compiler does not try to use any bit hacks, even if they could.

A solution that manipulates double bits cannot be portable. There may be different endianness, also there may be no (efficient) way to get double bits, double is not necessarily IEEE 754 binary64 after all. Plus direct manipulations will not cause signals for signaling NANs, when they are expected.


For integers most likely the compiler will do it right anyway, otherwise there are already good answers given.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.