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

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