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).
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.
User contributions licensed under CC BY-SA 3.0