0

I'll make examples in Python, since I use Python, but the question is not about Python. Lets say I want to increment a variable by specific value so that it stays in given boundaries.

So for increment and decrement I have these two functions:

def up (a, s, Bmax):
    r = a + s
    if r > Bmax : return Bmax
    else : return r

def down (a, s, Bmin):
    r = a - s
    if r < Bmin : return Bmin
    else : return r

Note: it is supposed that initial value of the variable "a" is already in boundaries (min <= a <= max) so additional initial checking does not belong to this function. What makes me curious, almost every program I made needs these functions.

The question is:

  • are those classified as some typical operations and have they specific names?
  • if yes, is there some correspondence to intrinsic processor functionality so it is optimised in some compilers?

Reason why I ask is pure curiousity, of course I cannot optimise it in Python and I know little about CPU architecture.

To be more specific, on a lower level for an unsigned 8-bit integer the increment would look I suppose like this:

def up (a, s, Bmax):
    counter = 0
    while True:
        if counter == s : break
        if a == Bmax : break
        if a == 255 : break 
        a += 1
        counter += 1

I know the latter would not make any sense in Python so treat it as my naive attempt to imagine low level code which adds the value in place. There are some nuances, e.g. signed, unsigned, but I was interested merely about unsigned integers since I came across it more often.

Mikhail V
  • 1,416
  • 1
  • 14
  • 23
  • 1
    Interesting question, made me dig, still couldn't find the exact answer. In http://ptgmedia.pearsoncmg.com/images/0321335724/samplechapter/seacord_ch05.pdf , Page 170 inwards discuss how to detect overflow, with IA-32 instructions (jc and inc). With GCC you could use -ftrapv to issue a SIGABRT and register a handler and sort out the overflow. – Isuru H Jan 19 '17 at 08:36
  • I get your question, but just to be clear, you cannot detect if the result of the addition is greater than the maximum value it can represent with the way you coded up the UP function. Think of a signed int and if your current value is 0x7FFFFFFE which is one less than the MAX, and you want to add 2, it will overflow and result in -2,147,483,648 which is less than the max value it can represent. So you will never see your UP function returning MAX – Isuru H Jan 19 '17 at 09:32

1 Answers1

2

It is called saturation arithmetic, it has native support on DSPs and GPUs (not a random pair: both deals with signals).

For example the NVIDIA PTX ISA let the programmer chose if an addition is saturated or not

add.type       d, a, b;
add{.sat}.s32  d, a, b;     // .sat applies only to .s32

.sat limits result to MININT..MAXINT (no overflow) for the size of the operation.

The TI TMS320C64x/C64x+ DSP has support for

Dual 16-bit saturated arithmetic operations

and instruction like sadd to perform a saturated add and even a whole register (Saturation Status Register) dedicated to collecting precise information about saturation while executing a sequence of instructions.

Even the mainstream x86 has support for saturation with instructions like vpaddsb and similar (including conversions).

Another example is the GLSL clamp function, used to make sure color values are not outside the range [0, 1].

In general if the architecture must be optimized for signal/media processing it has support for saturation arithmetic.

Much more rare is the support for saturation with arbitrary bounds, e.g. asymmetrical bounds, non power of two bounds, non word sized bounds.

However, saturation can be implemented easily as min(max(v, b), B) where v is the result of the unsaturated (and not overflowed) operation, b the lower bound and B the upper bound.
So any architecture that support finding the minimum and the maximum without a branch, can implement any form of saturation efficiently.

See also this question for a more real example of how saturated addition is implemented.

As a side note the default behavior is wrap around: for 8-bit quantities the sum 255 + 1 equals 0 (i.e. operations are modulo 28).

Margaret Bloom
  • 41,768
  • 5
  • 78
  • 124