rollover issue with unsigned int while checking if a number is within a range

Question

I am trying to check if a received message number is in a given range. Everytime the message number gets incremented.So if I am expecting number 10, I accept any message with number 10+ 5. So sequence numbers 10 to 15. I am using an unsigned int. So when expected number is 65532,I can accept 65532 + 10(so min = 65532 and max = 5). How do I check if the number I received is in this range?

Answer 1

Simply subtract

unsigned message_number, expected_number;
unsigned range = 5;  // or 10,  OP’s post varies as to the desired range.
if ((message_number - expected_number) <= range) {
  ;  // accept;
}

Wrap-around of unsigned arithmetic is well defined.

[Edit]

The above solution works well if the message_number wraps around at the same place as unsigned. The following solutions do not make that assumption, neither do they assume message_number wraps around at unsigned short.

unsigned maxsequenceplus1_number = 65536LU;
if (((message_number - expected_number)%maxsequenceplus1_number) <= range) {
  ;  // accept;
}

const unsigned maxsequence_number = 65535U; // some power of 2 minus 1
if (((message_number - expected_number)&maxsequence_number) <= range) {
  ;  // accept;
}

Answer 2

If you use unsigned you get GF(2^k) arithmetic for some value k [Edit: addition and subtraction, doing full finite field is much more work; maybe I should adopt some other shorthand terminology?]. Typically for unsigned short k is 16, for unsigned int it is 32, and for unsigned long long it is 64, but in any case it is at least 16 (because UINT_MAX is at least 65535).

In this kind of finite field arithmetic you can simply subtract two numbers and compare the result against your limit. That is, if the range of "allowed values" is from x to x+5 and the actual value you received is y, then:

unsigned int x, y, diff;
...
diff = y - x;
if (diff <= 5) {
    the value is in range
} else {
    the value is out of range
}

This works fine as long as the "in range" window does not exceed 2^k-1, and since k >= 16 that means your window space is at least 32767.

If you wish to use unsigned short the one wrinkle in C is that unsigned short expands to (signed, plain) int instead of unsigned int in the usual case, when INT_MAX >= USHRT_MAX. So you have to cast to unsigned int to do the subtraction:

unsigned short x, y, diff;
....
diff = (unsigned int)y - (unsigned int)x;

The rest of the code is unchanged (note that assigning unsigned int back to unsigned short is well defined as it reduces the value mod 2^k).

Answer 3

To get the right result with 16 bit integers (ie range 0 to 65535), you can use unsigned short to store the values. Then the roll over will work just fine.

BUT you need to be careful. Just because you have all variables declared as unsigned short, the difference between 2 unsigned shorts can actually be automatically cast to int, which will will break your code.

For example,

void test(unsigned short incoming, unsigned short min, unsigned short range)
{
 if ((incoming - min) >= 0 && (incoming - min) <  range)
   printf("in range");       
 else
   printf("out of range");
}

This fails if you enter incoming=5 and min=0xFFFF and range=5. It will print "in range" even though it is not in range.

To fix this problem, you need to do

void test(unsigned short incoming, unsigned short min, unsigned short range)
{
 if ((unsigned short)(incoming - min) >= 0 &&
     (unsigned short)(incoming - min) <  range)
   printf("in range");       
 else
   printf("out of range");
}

This is a contentious point in the c language. The specification allows subtraction to be carried out in registers that are larger than the given data size (short). Most computers have 32 bit or 64 bit registers, so the subtraction is carried out by int registers which are signed. So 0x00000005 - 0x0000FFFF = 0xFFFF0006, which is negative (-65530) and not just 6. You need to recast back to the original data type (unsigned short) to get back the 6.

Please see In a C expression where unsigned int and signed int are present, which type will be promoted to what type? for a discussion on integer promotion.

You can also do this, which is probably the best answer. I took out the comparison for delta >= 0 since that is always true for unsigned integers. And also switched to using stdint.h

#include <stdint.h>

void test(uint16_t incoming, uint16_t  min, uint16_t  range)
{
 uint16_t  delta = incoming - min;
 if (delta <  range)
   printf("in range");       
 else
   printf("out of range");
}