Implementing basic arithmetic in C

[Nobody]

The following code attempts to implement the four basic arithmetic
operations (+,-,*,/) for signed integers, avoiding any undefined behaviour.

Does it achieve this goal (i.e. have I overlooked any potential for UB)?
And is it portable?

The general idea is to convert signed integers to their absolute value as
an unsigned integer plus their sign, perform arithmetic using unsigned
integers (thus avoiding UB), detect overflow, then construct the result if
it is representable as a signed integer.

#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <setjmp.h>

static void fatal(void);

static const unsigned neg_max =
(unsigned)INT_MAX + (unsigned)(-(INT_MAX+INT_MIN));

static unsigned uabs(int x)
{
if (x >= 0)
return (unsigned) x;
if (x == -INT_MAX-1)
return neg_max;
return (unsigned) -x;
}

int add(int x, int y)
{
int nx = x < 0;
int ny = y < 0;
int nr;
unsigned ax = uabs(x);
unsigned ay = uabs(y);
unsigned ar;
if (nx && ny) {
/* -|x| + -|y| = -(|x|+|y|) */
nr = 1;
ar = ax + ay;
if (ar < ax)
fatal();
}
else if (nx) {
/* -|x| + |y| = |y|-|x| */
nr = ax > ay;
ar = nr ? ax - ay : ay - ax;
}
else if (ny) {
/* |x| + -|y| = |x|-|y| */
nr = ay > ax;
ar = nr ? ay - ax : ax - ay;
}
else {
/* |x| + |y| */
nr = 0;
ar = ax + ay;
}

if (nr) {
if (ar > neg_max)
fatal();
if (ar == neg_max)
return INT_MIN;
return -(int)ar;
}
else {
if (ar > INT_MAX)
fatal();
return (int)ar;
}
}

int subtract(int x, int y)
{
int nx = x < 0;
int ny = y < 0;
int nr;
unsigned ax = uabs(x);
unsigned ay = uabs(y);
unsigned ar;
if (nx && ny) {
/* -|x| - -|y| = |y|-|x| */
nr = ax > ay;
ar = nr ? ax - ay : ay - ax;
}
else if (nx) {
/* -|x| - |y| = -(|x|+|y|) */
nr = 1;
ar = ax + ay;
if (ar < ax)
fatal();
}
else if (ny) {
/* |x| - -|y| = |x|+|y| */
nr = 0;
ar = ax + ay;
}
else {
/* |x| - |y| */
nr = ay > ax;
ar = nr ? ay - ax : ax - ay;
}

if (nr) {
if (ar > neg_max)
fatal();
if (ar == neg_max)
return INT_MIN;
return -(int)ar;
}
else {
if (ar > INT_MAX)
fatal();
return (int)ar;
}
}

int multiply(int x, int y)
{
static const unsigned bits = sizeof(unsigned) * CHAR_BIT;
const unsigned half = bits / 2;
const unsigned twice = half * 2;
const unsigned mask = (1U << half) - 1U;
int nx = x < 0;
int ny = y < 0;
int nr = nx != ny;
unsigned ax = uabs(x);
unsigned ay = uabs(y);
unsigned ar;

unsigned xl = ax & mask;
unsigned xh = (ax >> half) & mask;
unsigned xt = bits == twice ? 0 : (ax >> twice) & mask;

unsigned yl = ay & mask;
unsigned yh = (ay >> half) & mask;
unsigned yt = bits == twice ? 0 : (ay >> twice) & mask;

unsigned k0 = xl*yl;
unsigned k1a = xl*yh;
unsigned k1b = xh*yl;
unsigned k1 = k1a + k1b;
unsigned k2a = xh*yh;
unsigned k2b = xl*yt;
unsigned k2c = xt*yl;
unsigned k2 = k2a + k2b + k2c;
unsigned k3a = xt*yh;
unsigned k3b = xh*yt;
unsigned k3 = k3a + k3b;
unsigned k4 = xt * yt;

if (k1 & (~0 << (bits-half)))
fatal();
k1 <<= half;

if (k2 & (~0 << (bits-twice)))
fatal();
k2 <<= twice;

if (k3 || k4)
fatal();

ar = k0 + k1;
if (ar < k0)
fatal();

ar += k2;
if (ar < k2)
fatal();

if (ar > (nr ? neg_max : INT_MAX))
fatal();

return nr ? (ar == neg_max ? INT_MIN : -(int)ar) : (int)ar;
}

int divide(int x, int y)
{
if (x == INT_MIN && y == -1 && INT_MIN < -INT_MAX)
fatal();
return x / y;
}

/* ************************************************************ */

static jmp_buf jbuf;

static void fatal(void)
{
longjmp(jbuf, 1);
}

static void error(void)
{
fprintf(stderr, "usage: arith <int> [+-*/] <int>\n");
exit(EXIT_FAILURE);
}

static int doit(int x, int y, char op, int *p)
{
if (setjmp(jbuf) == 0) {
switch (op) {
case '+':
*p = add(x, y);
break;
case '-':
*p = subtract(x, y);
break;
case '*':
*p = multiply(x, y);
break;
case '/':
*p = divide(x, y);
break;
default:
error();
break;
}
return 0;
}
else
return -1;
}

int main(int argc, char **argv)
{
char c;
int x, y, r;
if (argc != 4)
error();
c = argv[2][0];
if (!strchr("+-*/", c))
error();
if (argv[2][1] != '\0')
error();
x = atoi(argv[1]);
y = atoi(argv[3]);

if (doit(x, y, c, &r) < 0) {
printf("%d %c %d = <overflow>\n", x, c, y);
return 1;
}
else
printf("%d %c %d = %d\n", x, c, y, r);

return 0;
}

[Barry Schwarz]

On Tue, 16 Dec 2014 05:07:58 +0000, Nobody <nob...@nowhere.invalid>
wrote:

>
>The following code attempts to implement the four basic arithmetic
>operations (+,-,*,/) for signed integers, avoiding any undefined behaviour.
>
>Does it achieve this goal (i.e. have I overlooked any potential for UB)?
>And is it portable?
>
>The general idea is to convert signed integers to their absolute value as
>an unsigned integer plus their sign, perform arithmetic using unsigned
>integers (thus avoiding UB), detect overflow, then construct the result if
>it is representable as a signed integer.
>
>#include <limits.h>
>#include <stdlib.h>
>#include <stdio.h>
>#include <string.h>
>#include <setjmp.h>
>
>static void fatal(void);
>
>static const unsigned neg_max =
> (unsigned)INT_MAX + (unsigned)(-(INT_MAX+INT_MIN));
>
>static unsigned uabs(int x)
>{
> if (x >= 0)
> return (unsigned) x;

The cast is unnecessary.

> if (x == -INT_MAX-1)

The right hand side is evaluated as signed int. If your system uses
signed magnitude (or if INT_MIN == -INT_MAX for any other reason), the
result is outside the range of a signed int. This would be UB.

> return neg_max;
> return (unsigned) -x;

The cast is unnecessary.

>}

--
Remove del for email

[Ian Collins]

Nobody wrote:
>
> The following code attempts to implement the four basic arithmetic
> operations (+,-,*,/) for signed integers, avoiding any undefined behaviour.
>
> Does it achieve this goal (i.e. have I overlooked any potential for UB)?
> And is it portable?
>
> The general idea is to convert signed integers to their absolute value as
> an unsigned integer plus their sign, perform arithmetic using unsigned
> integers (thus avoiding UB), detect overflow, then construct the result if
> it is representable as a signed integer.

Couldn't you just do the arithmetic using long long and check the result?

--
Ian Collins

[Nobody]

On Tue, 16 Dec 2014 19:19:01 +1300, Ian Collins wrote:

> Couldn't you just do the arithmetic using long long and check the result?

a) what if you don't have long long (the code is intended to conform to
C89)?

b) how do you write the long long versions of the functions (or just
the long versions on platforms where those two are the same size)?

IOW, using a larger integer type only works if you're not already working
with the largest available integer type.

[Ian Collins]

Fair enough.

--
Ian Collins

[Ian Collins]

Nobody wrote:
>
> The following code attempts to implement the four basic arithmetic
> operations (+,-,*,/) for signed integers, avoiding any undefined behaviour.
>
> Does it achieve this goal (i.e. have I overlooked any potential for UB)?
> And is it portable?
>
> The general idea is to convert signed integers to their absolute value as
> an unsigned integer plus their sign, perform arithmetic using unsigned
> integers (thus avoiding UB), detect overflow, then construct the result if
> it is representable as a signed integer.

<snip>

> int subtract(int x, int y)
> {

Can't you just implement this as

return add( x, -y );

?

--
Ian Collins

[glen herrmannsfeldt]

Ian Collins <ian-...@hotmail.com> wrote:
> Nobody wrote:

>> The following code attempts to implement the four basic arithmetic
>> operations (+,-,*,/) for signed integers, avoiding any undefined behaviour.

(snip)

>> int subtract(int x, int y)

> Can't you just implement this as

> return add( x, -y );

Undefined behavior for the most negative twos complement value.

-- glen

[Ian Collins]

Good spot. But that case only requires one additional if().

--
Ian Collins

[Rosario193]

On Tue, 16 Dec 2014 05:07:58 +0000, Nobody wrote:

>
>The following code attempts to implement the four basic arithmetic
>operations (+,-,*,/) for signed integers, avoiding any undefined behaviour.

why so long routines?
if i would be i... write them in the assembly of each cpu the code has
to be ported

[Richard Heathfield]

Rosario193 wrote:

> On Tue, 16 Dec 2014 05:07:58 +0000, Nobody wrote:
>
>>
>>The following code attempts to implement the four basic arithmetic
>>operations (+,-,*,/) for signed integers, avoiding any undefined
>>behaviour.
>
> why so long routines?

So that he won't have to write them in the assembly of each cpu the code has
to be ported.

> if i would be i... write them in the assembly of each cpu the code has
> to be ported

Remember to put an elephant in Cairo, or you'll wear out your trouser-knees.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[Rosario193]

On Tue, 16 Dec 2014 10:17:19 +0000, Richard Heathfield wrote:
>Rosario193 wrote:
>> On Tue, 16 Dec 2014 05:07:58 +0000, Nobody wrote:
>>
>>>The following code attempts to implement the four basic arithmetic
>>>operations (+,-,*,/) for signed integers, avoiding any undefined
>>>behaviour.
>>
>> why so long routines?
>
>So that he won't have to write them in the assembly of each cpu the code has
>to be ported.

in language operator +,-,*,/ are the most critical one [these
operations one has to use always in the language and programs]

so if these operation has to be use hevly:
the priority is do it the most fast one can obtain

>> if i would be i... write them in the assembly of each cpu the code has
>> to be ported
>
>Remember to put an elephant in Cairo, or you'll wear out your trouser-knees.

if the OP is as u, don't like to see assembly...

the way is easy: write them in C less operation possible
means
break all cpu in sets, that has the same UBs
and write the C code for each set of CPU in C

for example all the cpu that are 1 complement or 2 complement or cpu
has the same UB in the border of [-intmax... intmax] etc and for each
write the C code

but this speach would be not i to write

[BartC]

On 16/12/2014 10:54, Rosario193 wrote:
> On Tue, 16 Dec 2014 10:17:19 +0000, Richard Heathfield wrote:
>> Rosario193 wrote:
>>> On Tue, 16 Dec 2014 05:07:58 +0000, Nobody wrote:
>>>
>>>> The following code attempts to implement the four basic arithmetic
>>>> operations (+,-,*,/) for signed integers, avoiding any undefined
>>>> behaviour.
>>>
>>> why so long routines?
>>
>> So that he won't have to write them in the assembly of each cpu the code has
>> to be ported.
>
> in language operator +,-,*,/ are the most critical one [these
> operations one has to use always in the language and programs]
>
> so if these operation has to be use hevly:
> the priority is do it the most fast one can obtain
>

I don't think the OP is interested in making them fast! Just in
detecting errors in the results.

--
Bartc

[Ike Naar]

This has undefined behaviour if twice equals the size of k2 in bits.

[Nobody]

On Fri, 26 Dec 2014 17:09:39 +0000, Ike Naar wrote:

>> k2 <<= twice;
>
> This has undefined behaviour if twice equals the size of k2 in bits.

Good catch.

Although from a practical perspective, it would make more sense to split
that function into two versions: one for the simple (and common) case
where the number of bits is even, another for the harder (and uncommon,
possibly even non-existent case) where the number of bits is odd.

That line wouldn't exist in the even-width case, and wouldn't be UB in the
odd-width case (where twice will be one less than the number of bits in an
unsigned int).