| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Dokkio Sidebar (from the makers of PBworks) is a Chrome extension that eliminates the need for endless browser tabs. You can search all your online stuff without any extra effort. And Sidebar was #1 on Product Hunt! Check out what people are saying by clicking here.

View
 

Saturated Addition

Page history last edited by Kenneth Finnegan 14 years ago

These functions can be used when you're adding numbers together and don't want the total to overflow.  Normally, when an addition overflows, it just drops back down to 0 and you're left with however much is left over after the overflow. 

 

If you were doing something like calculating the distance between two points, and it overflowed, they would appear to be very close to each other.  Using these functions, you still won't know how far apart they are, but you'll be able to see that the points are very far apart (at least 0xFFFFFFFF, in the case of 32 bits).

 

Code:

#include <stdint.t>

uint16_t saturateadd16(uint16_t a, uint16_t b) {
    return (a > 0xFFFF - b) ? 0xFFFF : a + b;
}

uint32_t saturateadd32(uint32_t a, uint32_t b) {
    return (a > 0xFFFFFFFF - b) ? 0xFFFFFFFF : a + b;
}

  

Usage: 

uint32_t x=14, y=15, sum;
sum = saturateadd32(x, y);


Extensions:

The functions can easily be adapted to 8 or 64 bit operations at well.

 

There is significant overhead in function calls, so consider inlining the functions or changing them to macros instead.

 

A similar approach can be used for subtraction, multiplication, and division as well.  Multiplication and division will be more difficult than subtraction due to more edge cases.

 

This one is a little out of my league, but on an x86, if performance is key, you can use inline assembly...

uint32_t add(uint32_t a, uint32_t b) {
  #ifdef IA32
  __asm  {
    mov eax,a
    xor edx,edx
    add eax,b
    setnc dl
    dec edx
    or eax,edx
  }
  #else
  // Portable version
  return sum;
  #endif 
}

Sources:

http://stackoverflow.com/questions/121240/saturating-addition-in-c

Comments (0)

You don't have permission to comment on this page.