How to detect the difference between a wrapping counter and large negative value in C language

Question

Apologies for my imbecility as this is my first post on this forum. I am trying to detect the difference between a wrapping unsigned 32-bit counter and a large negative Jump with the help of following code but the compiler give me error:

error: comparison is always true due to limited range of data type [-Werror=type-limits]

Here is my code snippet:

#define MAX_BACKWARD_JUMP -4294959295 //UINT_MAX - 8000
#define MIN_BACKWARD_JUMP -3600
#define MAX_FORWARD_JUMP   4800000

signed int rtpDelta; //Signed 32-bit
unsigned int currRTPTs, prevRTPTs; //unsigned 32-bit

rtpDelta = currRTPTs - prevRTPTs;

  if ((rtpDelta > MAX_BACKWARD_JUMP && rtpDelta < MIN_BACKWARD_JUMP) 
        || (rtpDelta > MAX_FORWARD_JUMP))
        {
          printf("Delta in Timestamps too large\n",rtpDelta);
        }

The idea here is to catch the invalid large Deltas in RTP timestamps. We have a current TimeStamp and a previous Timestamp receiving from peer RTP client. The boundary limits for invalid values of RTP Timestamps are -4294959295 < rtpDelta < -3600 that is it should throw an Error if the Delta is less than -3600 and greater than -4294959295 because the values closer to UMAX_INT will be considered as roll-over. What am I doing wrong here?

Answer 1

In general, if you have two unsigned counters a and b, with values between 0 and LIMIT-1, inclusive, with the data type capable of representing 2*LIMIT-1, you can use modulo arithmetic with the split point in the middle:

difference = (a + LIMIT - b) % LIMIT;
if (difference <= LIMIT/2) {
    /* a = b + difference */
} else {
    /* b = a + (LIMIT - difference) */
}

It is common to have LIMIT be a power of two, in which case the modulo operator (% LIMIT) can be replaced with a binary AND (& (LIMIT-1)), which is much faster on current processors.

For C, unsigned integer types are defined in the standards as having modulo arithmetic (C99, C11 6.2.5p9), so a - b using any unsigned integer type for a and b will yield the correct results, with LIMIT being the corresponding Utype_MAX macro defined in "limits.h" header file. For example,

const unsigned int  d = (unsigned int)a - (unsigned int)b;
if (d <= UINT_MAX/2)
    /* a >= b, a = b + d */
else
    /* a < b,  b = a + UINT_MAX - (d - 1) */

Answer 2

Consider:

unsigned int LowerBound = -3600u, UpperBound = 4800000u;

unsigned int difference = currRTPTs - prevRTPTs;

Observe that, due to wrapping, the value of LowerBound, -3600u, will be a large positive integer. Now, when the mathematical difference (calculated without overflow) is less than -3600 by a reasonable amount, the value of difference will be a large integer, and it will be less than LowerBound. Additionally, if the difference does not become too great (in the negative direction), then difference will remain greater than UpperBound.

Similarly, if the difference is greater than 4,800,000 by a reasonable amount, the value of difference will be greater than UpperBound. If the difference does not become too much greater, then it will remain less than LowerBound.

Thus, in both cases, the value of difference when the mathematical difference is outside the desired bounds (but not by too much) is less than LowerBound and greater than UpperBound:

if (difference < LowerBound && difference > UpperBound)
    printf("Delta in timestamps is outside acceptable bounds.\n");

Observe that this will fail when the mathematical difference exceeds -3600u (which is 4,294,967,296 - 3600) or is less than 4,800,000 - 4,294,967,296. Thus, the test works when the difference is in [-4,290,167,296, 4,294,963,696].

Answer 3

It appears to me things are made complicated, unnecessarily:

#include <cstdio>
#include <cstdlib>
#include <limits>

#define COMPLICATED 0

#if COMPLICATED

int main()
{
    const unsigned MAX_BACKWARD_JUMP = std::numeric_limits<unsigned>::max() - 8000;
    const unsigned MIN_BACKWARD_JUMP = 3600;
    const unsigned MAX_FORWARD_JUMP = 4800000;
    unsigned prevRTPTs = 0;
    for(unsigned i = 0; i < 10; ++i) {
        unsigned currRTPTs = std::rand();
        std::printf("previous = %10d: ", prevRTPTs);
        std::printf(" current = %10d: ", currRTPTs);
        if(currRTPTs < prevRTPTs) {
            // Negative
            unsigned rtpDelta = prevRTPTs - currRTPTs;
            // Why a range and no threshold?
            if(MIN_BACKWARD_JUMP < rtpDelta && rtpDelta < MAX_BACKWARD_JUMP)    {
                std::printf("Invalid range: %10d\n", rtpDelta);
            }
            else {
                std::printf("           OK: %10d\n",rtpDelta);
            }

        }
        else {
            // Positive
            unsigned rtpDelta = currRTPTs - prevRTPTs;
            if(MAX_FORWARD_JUMP < rtpDelta) {
                std::printf("    Too large: %10d\n",rtpDelta);
            }
            else {
                std::printf("           OK: %10d\n",rtpDelta);
            }
        }
        prevRTPTs = currRTPTs;
    }
}

#else

int main()
{
    const unsigned MAX_JUMP = 4800000;
    unsigned prevRTPTs = 0;
    for(unsigned i = 0; i < 10; ++i) {
        unsigned currRTPTs = std::rand();
        std::printf("previous = %10d: ", prevRTPTs);
        std::printf(" current = %10d: ", currRTPTs);
        unsigned rtpDelta = currRTPTs - prevRTPTs;
        if(currRTPTs < rtpDelta) {
            // Negative (Underflow)
            rtpDelta = prevRTPTs - currRTPTs;

        }
        if(MAX_JUMP < rtpDelta) {
            std::printf("    Too large: %10d\n",rtpDelta);
        }
        else {
            std::printf("           OK: %10d\n",rtpDelta);
        }
        prevRTPTs = currRTPTs;
    }
}

Note: all RTPTs values are unsigned.

Answer 4

There is only one way to reliably check for overflow: Check before calculating the sum. Like this:

unsigned old = ..., delta = ...;
if((int)delta > 0) {    //cast to int, because we need to interprete negative numbers here.
    if(old > maxvalue - delta) printf("Overflow!\n");    //No signed arithmetic, so we don't trigger undefined behavior.
} else {
    if(old < minvalue - delta) printf("Underflow!\n");
}

It is important that the delta appears on the right side of the comparisons.

Now, what to do, if you don't have access to the delta before it gets added to the sum? Luckily, you can simply recover the delta:

unsigned old = ..., new = ...;
unsigned delta = new - old;
//Now you can proceed as above.

This works, because unsigned subtraction is truly the inverse of unsigned addition, there are no uninvertible cases or undefined behavior that could be triggered.