How to convert uint to int in C with minimal loss of result range

6

I want the difference between two unbounded integers, each represented by a uint32_t value which is the unbounded integer taken modulo 2^32. As in, for example, TCP sequence numbers. Note that the modulo 2^32 representation can wrap around 0, unlike more restricted questions that do not allow wrapping around 0.

Assume that the difference between the underlying unbounded integers are in the range of a normal int. I want this signed difference value. In other words, return a value within the normal int range that is equivalent to the difference of the two uint32_t inputs modulo 2^32.

For example, 0 - 0xffffffff = 1 because we assume that the underlying unbounded integers are in int range. Proof: if A mod 2^32 = 0 and B mod 2^32 = 0xffffffff, then (A=0, B=-1) (mod 2^32) and therefore (A-B=1) (mod 2^32) and in the int range this modulo class has the single representative 1.

I have used the following code:

static inline int sub_tcp_sn(uint32_t a, uint32_t b)
{
    uint32_t delta = a - b;

    // this would work on most systems
    return delta;

    // what is the language-safe way to do this?
}

This works on most systems because they use modulo-2^32 representations for both uint and int, and a normal modulo-2^32 subtraction is the only reasonable assembly code to generate here.

However, I believe that the C standard only defines the result of the above code if delta>=0. For example on this question one answer says:

If we assign an out-of-range value to an object of signed type, the result is undefined. The program might appear to work, it might crash, or it might produce garbage values.

How should a modulo-2^32 conversion from uint to int be done according to the C standard?

Note: I would prefer the answer code not to involve conditional expressions, unless you can prove it's required. (case analysis in the explanation of the code is OK).

c
math
language-lawyer
asked on Stack Overflow Nov 5, 2019 by personal_cloud • edited Nov 7, 2019 by personal_cloud

1 Answer

0

There must be a standard function that does this... but in the meantime:

#include <stdint.h>  // uint32_t
#include <limits.h>  // INT_MAX
#include <assert.h>  // assert

static inline int sub_tcp_sn(uint32_t a, uint32_t b)
{
    uint32_t delta = a - b;
    return delta <= INT_MAX ? delta : -(int)~delta - 1;
}

Note that it is UB in the case that the result is not representable, but the question said that was OK.

If the system has a 64-bit long long type, then the range can easily be customized and checked as well:

typedef long long sint64_t;

static inline sint64_t sub_tcp_sn_custom_range(uint32_t a, uint32_t b,
                             sint64_t out_min, sint64_t out_max)
{
    assert(sizeof(sint64_t) == 8);
    uint32_t delta = a - b;
    sint64_t result = delta <= out_max ? delta : -(sint64_t)-delta;
    assert(result >= out_min && result <= out_max);
    return result;
}

For example, sub_tcp_sn_custom_range(0x10000000, 0, -0xf0000000LL, 0x0fffffffLL) == -0xf00000000.

With the range customization, this solution minimizes range loss in all situations, assuming timestamps behave linearly (for example, no special meaning to wrapping around 0) and a singed 64-bit type is available.

answered on Stack Overflow Nov 5, 2019 by personal_cloud • edited Nov 8, 2019 by personal_cloud

User contributions licensed under CC BY-SA 3.0