C safely taking absolute value of integer

Question

Consider following program (C99):

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int main(void)
{
    printf("Enter int in range %jd .. %jd:\n > ", INTMAX_MIN, INTMAX_MAX);
    intmax_t i;
    if (scanf("%jd", &i) == 1)
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
}

Now as I understand it, this contains easily triggerable undefined behaviour, like this:

Enter int in range -9223372036854775808 .. 9223372036854775807:
 > -9223372036854775808
Result: |-9223372036854775808| = -9223372036854775808

Questions:

1. Is this really undefined behaviour, as in "code is allowed to trigger any code path, which any code that stroke compiler's fancy", when user enters the bad number? Or is it some other flavor of not-completely-defined?

2. How would a pedantic programmer go about guarding against this, without making any assumptions not guaranteed by standard?

(There are a few related questions, but I didn't find one which answers question 2 above, so if you suggest duplicate, please make sure it answers that.)

Answer 1

If the result of imaxabs cannot be represented, can happen if using two's complement, then the behavior is undefined.

7.8.2.1 The imaxabs function

2. The imaxabs function computes the absolute value of an integer j. If the result cannot be represented, the behavior is undefined. 221)

221) The absolute value of the most negative number cannot be represented in two’s complement.

The check that makes no assumptions and is always defined is:

intmax_t i = ... ;
if( i < -INTMAX_MAX )
{
    //handle error
}

(This if statement cannot be taken if using one's complement or sign-magnitude representation, so the compiler might give a unreachable code warning. The code itself is still defined and valid. )

Answer 2

How would a pedantic programmer go about guarding against this, without making any assumptions not guaranteed by standard?

One method is to use unsigned integers. The overflow behaviour of unsigned integers is well-defined as is the behaviour when converting from a signed to an unsigned integer.

So I think the following should be safe (turns out it's horriblly broken on some really obscure systems, see later in the post for an improved version)

uintmax_t j = i;
if (j > (uintmax_t)INTMAX_MAX) {
  j = -j;
}
printf("Result: |%jd| = %ju\n", i, j);

---

So how does this work?

uintmax_t j = i;

This converts the signed integer into an unsigned one. IF it's positive the value stays the same, if it's negative the value increases by 2ⁿ (where n is the number of bits). This converts it to a large number (larger than INTMAX_MAX)

if (j > (uintmax_t)INTMAX_MAX) {

If the original number was positive (and hence less than or equal to INTMAX_MAX) this does nothing. If the original number was negative the inside of the if block is run.

  j = -j;

The number is negated. The result of a negation is clearly negative and so cannot be represented as an unsigned integer. So it is increased by 2ⁿ.

So algebraically the result for negative i looks like

j = - (i + 2ⁿ) + 2ⁿ = -i

---

Clever, but this solution makes assumptions. This fails if INTMAX_MAX == UINTMAX_MAX, which is allowed by C Standard.

Hmm, lets look at this (i'm reading https://busybox.net/~landley/c99-draft.html which is apprarently the last C99 draft prior to standardisation, if anything changed in the final standard please do tell me.

When typedef names differing only in the absence or presence of the initial u are defined, they shall denote corresponding signed and unsigned types as described in 6.2.5; an implementation shall not provide a type without also providing its corresponding type.

In 6.2.5 I see

For each of the signed integer types, there is a corresponding (but different) unsigned integer type (designated with the keyword unsigned) that uses the same amount of storage (including sign information) and has the same alignment requirements.

In 6.2.6.2 I see

#1

For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2N-1, so that >objects of that type shall be capable of representing values from 0 to 2N-1 >using a pure binary representation; this shall be known as the value representation. The values of any padding bits are unspecified.39)

#2

For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. There need not be any padding bits; there shall be exactly one sign bit. Each bit that is a value bit shall have the same value as the same bit in the object representation of the corresponding unsigned type (if there are M value bits in the signed type and N in the unsigned type, then M<=N). If the sign bit is zero, it shall not affect the resulting value.

So yes it seems you are right, while the signed and unsigned types have to be the same size it does seem to be valid for the unsigned type to have one more padding bit than the signed type.

---

Ok, based on the analysis above revealing a flaw in my first attempt i've written a more paranoid variant. This has two changes from my first version.

I use i < 0 rather than j > (uintmax_t)INTMAX_MAX to check for negative numbers. This means that the algorithm proceduces correct results for numbers grater than or equal to -INTMAX_MAX even when INTMAX_MAX == UINTMAX_MAX.

I add handling for the error case where INTMAX_MAX == UINTMAX_MAX, INTMAX_MIN == -INTMAX_MAX -1 and i == INTMAX_MIN. This will result in j=0 inside the if condition which we can easilly test for.

It can be seen from the requirements in the C standard that INTMAX_MIN cannot be smaller than -INTMAX_MAX -1 since there is only one sign bit and the number of value bits must be the same or lower than in the corresponding unsigned type. There are simply no bit patterns left to represent smaller numbers.

uintmax_t j = i;
if (i < 0) {
  j = -j;
  if (j == 0) {
    printf("your platform sucks\n");
    exit(1);
  }
}
printf("Result: |%jd| = %ju\n", i, j);

---

@plugwash I think 2501 is correct. For example, -UINTMAX_MAX value becomes 1: (-UINTMAX_MAX + (UINTMAX_MAX + 1)), and is not caught by your if. – hyde 58 mins ago

Umm,

assuming INTMAX_MAX == UINTMAX_MAX and i = -INTMAX_MAX

uintmax_t j = i;

after this command j = -INTMAX_MAX + (UINTMAX_MAX + 1) = 1

if (i < 0) {

i is less than zero so we run the commands inside the if

j = -j;

after this command j = -1 + (UINTMAX_MAX + 1) = UINTMAX_MAX

which is the correct answer, so no need to trap it in an error case.

Answer 3

On two-complement systems getting the absolute number of the most negative value is indeed undefined behavior, as the absolute value would be out of range. And it's nothing the compiler can help you with, as the UB happens at run-time.

The only way to protect against that is to compare the input against the most negative value for the type (INTMAX_MIN in the code you show).

Answer 4

So calculating the absolute value of an integer invokes undefined behaviour in one single case. Actually, while the undefined behaviour can be avoided, it is impossible to give the correct result in one case.

Now consider multiplication of an integer by 3: Here we have a much more serious problem. This operation invokes undefined behaviour in 2/3rds of all cases! And for two thirds of all int values x, finding an int with the value 3x is just impossible. That's a much more serious problem than the absolute value problem.

Answer 5

You may want to use some bit hacks:

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

This works well when INT_MIN < v <= INT_MAX. In the case where v == INT_MIN, it remains INT_MIN , without causing undefined behavior.

You can also use bitwise operation to handle this on ones' complement and sign-magnitude systems.

Reference: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

Answer 6

according to this http://linux.die.net/man/3/imaxabs

Notes

Trying to take the absolute value of the most negative integer is not defined.

To handle the full range you could add something like this to your code

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd\n", i, -(i/10), -(i%10));
    }

edit: As abs(INTMAX_MIN) cannot be represented on a 2's complement machine, 2 values within respresentable range are concatenated on output as a string. Tested with gcc, though printf required %lld as %jd was not a supported format.

Answer 7

1. Is this really undefined behaviour, as in "code is allowed to trigger any code path, which any code that stroke compiler's fancy", when user enters the bad number? Or is it some other flavor of not-completely-defined?

The behaviour of the program is only undefined, when the bad number is successfully input-ed and passed to imaxabs(), which on a typical 2's complement system returns a -ve result as you observed.

That is the undefined behaviour in this case, the implementation would also be allowed to terminate the program with an over-flow error if the ALU set status flags.

The reason for "undefined behaviour" in C is so compiler writers don't have to guard against overflow, so programs can run more efficiently. Whilst it is within C standard for every C program using abs() to try to kill your first born, just because you call it with a too -ve value, writing such code into the object file would simply be perverse.

The real problem with these undefined behaviours, is that an optimising compiler, can reason away naive checks so code like :

r = (i < 0) ? -i : i;
if (r < 0) {   // This code may be pointless
    // Do overflow recovery
    doRecoveryProcessing();
} else {
    printf("%jd", r);
}

As a compiler optomiser can reason that negative values are negated, it could in principal determine that (r <0) is always false, so the attempt to trap the problem fails.

2. How would a pedantic programmer go about guarding against this, without making any assumptions not guaranteed by standard?

By far the best way, is simply to ensure that the program works on a valid range, so in this case validating the input suffices (disallow INTMAX_MIN). Programs printing tables of abs() ought to avoid INT*_MIN and so on.

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd\n", i, -(i/10), -(i%10));
    }

Appears to write out the abs( INTMAX_MIN) by fakery, allowing the program to live up to it's promise to the user.