CODEWITHSUNDEEP
cmathbinaryoverflow
PICyourBrain
PICyourBrain

Reputation: 10284

fastest c arithmetic method for ints

I am writing a c program. I have an unsigned integer (16bit) whose value could be anything at any time and I have a signed char (8bit) whose value could be anything at any time, within the obvious limits of the data types. I need to add the signed char to the unsigned int, the result being an unsigned int, and if the value overflows either past 0xFFFF or below 0x00, i need the result to equal the limit (either 0x00 or 0xFFFF). I want to know what would be the fastest approach to doing this? My approach is shown below but it uses a long data type and thus long binary arithmetic so I am guessing that there is a faster way...

long i;
unsigned int result;

i = someUINT + someCHAR;

if(i <= 0) 
{
    result = 0;
}
else if(i >= 0xFFFF)
{
    result = 0xFFFF;
}
else 
{
    result = (unsigned int)i;
}

EDIT: I am using a 16bit MCU (PIC24HJ series) and the Microchip C30 compiler.

Upvotes: 4

Views: 487

Answers (7)

supercat
supercat

Reputation: 81153

I would guess the fastest would be something like:

  UInt16 uival;
  Int8 sbval;
  UInt16 result;

  result = uival + sbval;
  if (uival & 0x8000)  /* Only worry about max-val overflow */
  {
    if (result = 65280) /* Underflow */
      result = 0;
  }

Things are a little simplified because any overflows can only happen into a small portion of the numeric range. If the addend were 16 bits, it would be necessary to test the difference between the original uint16 and the result to see if there was overflow; since the addend is only 8 bits, that's not needed. I've not used the PIC24xx parts, so I don't know if testing for 256 or 65280 is faster than other values, but on 8-bit parts it certainly should be.

Upvotes: 0

mocj
mocj

Reputation: 1486

result = someUINT + someCHAR;
if (someCHAR > 0)
{
   if (result < someCHAR)
   {
      result = 0xFFFF;
   }
}
else if (result > someUINT)
{
   result = 0;
}

Upvotes: 0

Stephen Canon
Stephen Canon

Reputation: 106127

The fastest way will almost always be to take advantage of processor-specific features that you cannot describe in portable C code. Write manifestly correct portable code that works, and let the compiler do what it will do. If you have specific benchmark data that shows that this specifically must be faster, implement an additional tuned version that is processor-specific.

Many processors (including, I believe, the PIC24) have "saturating add" instructions that perform exactly this operation. The fastest thing is typically to write assembly that uses that instruction specifically, but there's no reason to do so unless you have evidence that the function needs to be faster.

Upvotes: 0

dko
dko

Reputation: 894

Wow I love stuff like this. Here is my stab assuming that most of the time it will fall in between the boundaries try this

    long i;
    i= char + int;
    if((i & 0xFFFF) == i){
      return (int)i;
    }
    else if(i < 0)
    {
      return 0;
    }
    else
    {
      return 0xFFFF;
    }

Upvotes: 0

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85986

Almost certainly, the correct answer is

if(i <= 0) 
{
    result = 0;
}
else if(i >= 0xFFFF)
{
    result = 0xFFFF;
}
else 
{
    result = (unsigned int)i;
}

Profile the application, and if this turns out to be a bottle-neck (which I highly, highly doubt), then rewrite it.

Modern compilers are very good at writing branchless-conditionals for code like this, so just write it the way that makes the most sense and let the compiler do its job. Don't confuse both the compiler and whatever poor person has to read this code in the future by using some convoluted bit-fiddling hack.

Upvotes: 3

Neil
Neil

Reputation: 55392

This algorithm only works in 2's complement.

When checking a signed addition for overflow, the result must have the same sign as at least one of the operands. This case turns out to be only slightly different; if the result flips the "sign" bit then it's OK if both operands have the same "sign" bit. And of course the computation of the unsigned limits is easier!

uint16_t UIntPlusChar(uint16_t u, char ch)
{
  int16_t i = (int16_t)u;
  int16_t p = i + ch;
  if ((ch ^ i) < 0 && (p ^ i) < 0)
    p = i >> 15;
  return (uint16_t)p;
}

Upvotes: 0

Lundberg
Lundberg

Reputation: 404

You can avoid the long checking before adding:

if(0xFFFF - someUINT < someCHAR) {
  return 0xFFFF;
} else {
  return someUINT + someCHAR;
}

Of course, if you REALLY need this to be FAST, turn this into an inline function or macro and go assembly.

Upvotes: 0

Related Questions