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

  • Finally, you can manage your Google Docs, uploads, and email attachments (plus Dropbox and Slack files) in one convenient place. Claim a free account, and in less than 2 minutes, Dokkio (from the makers of PBworks) can automatically organize your content for you.

View
 

Saturated Addition

Page history last edited by Kenneth Finnegan 12 years, 3 months 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.