can someone explain this code - rtc roll over with bitwise (in c)?

Question

can anyone explain this ((~(preRtcInseconds <<1)+1)>>1)

unsigned long preInseconds;
unsigned long curInSeconds;
unsigned long elapsedInSeconds;

if(curInSeconds>=preInseconds)
{
   elapsedInSeconds = curInSeconds - preInseconds;//does easy thing. no needs roll over
}
else{ //rollover
  preInseconds = ((~(preInseconds <<1)+1)>>1);
  elapsedInSeconds = curInSeconds + preInseconds;
}

Answer 1

It looks like buggy rollover code written by someone who doesn't understand that C unsigned arithmetic is mod 2^n (or doesn't understand mod 2^n arithmetic.) It is in fact exactly equivalent to:

elapsedInSeconds = curInSeconds - preInseconds;
if (curInSeconds < UNLONG_MAX/2 && preInseconds < ULONG_MAX/2)
    elapsedInSeconds &= ULONG_MAX/2;

That is, it does a mod 2^n subtraction, but in a few cases (that were probably never hit in any test case), it gets to top bit wrong (clear instead of set).

It is vaguely possible that this is intentional, since what is going on here is that it does a mod 2^n-1 subtraction if both numbers are <2^n-1 and a mod 2^n subtraction if either number is >= 2^n-1 (where n is the size of an unsigned long in bits). If the times are coming from some hardware device which might be always clearing the top bit or might not, this might make sense.

Answer 2

First of all, everything in my discussion below assumes that your unsigned long type is 32 bits wide. If it's not, that's OK; it doesn't really matter how wide it is, but all my examples assume it's 32 bits wide. And I simply use uint32 to denote that, knowing that uint32 isn't actually a standard type like uint32_t, please don't bother telling me that.

Daniel Fischer has done a fine job of explaining each low-level operation in detail, and I won't repeat that here. But I think what you're interested in isn't so much the meaning of each of the low-level operations as much as the necessity of all of those operations applied as a group. Which as I'll explain below, aren't necessary anyway. In fact, they're slightly wrong, but only in the case that the "current" counter reading is more than halfway back around the circle to the "previous" reading.

Before I get to the "meaning" behind the mathematics of your implementation, let's first just look at a trivial example of how it computes elapsedInSeconds in the case of the smallest rollover possible:

If preInseconds = 0xffffffff and curInSeconds = 0x00000000, elapsedInSeconds should be 1.

preInseconds = preInseconds<<1;     // 0xfffffffe
preInseconds = ~preInseconds;       // 0x00000001
preInseconds = preInseconds+1       // 0x00000002
preInseconds = preInseconds>>1;     // 0x00000001
elapsedInSeconds = curInSeconds + preInseconds;
             ... =  0x00000000  +  0x00000001    = 1

...which is exactly what we expect. Great.

However, the interesting thing is that none of the rollover handling logic is necessary. At all. Every time I've ever seen someone try to calculate the difference between a 'current' and 'previous' counter value, I always see them jumping through hoops to handle the rollover case, and more often than not they do it wrong. The shame of the situation is that handling the rollover with a special case is never necessary for power-of-2-sized counters. If the counter's full scale (point at which it rolls over) is smaller than the size of your data type, you'd need to mask the result back to the number of bits in the counter, but that's the only rollover handling you really ever need, and in that case you'd just do the masking every time without worrying whether it rolled over or not (which also avoids branch instructions so it's faster). Since your rollover point is the full-scale value of a uint32, you don't even need to mask the result.

Here's why:

Assume, as above, that preInseconds=0xffffffff and curInSeconds=0. Again, the result should be 1. If you weren't concerned about rollover, you'd just take curInSeconds-preInseconds as the result. But in the case of rollover, the subtract operation will produce an underflow. What does that mean? It means that if you had more bits that you were dealing with (i.e. another uint32 being used as the high word of a 64-bit compound counter), then you'd need to borrow 1 from the high word (just like grade-school subtraction with decimal numbers). But in your case, there's no higher word to borrow from. That's OK. Really. You don't care about those bits anyway. You still get the difference value you were looking for:

elapsedInSeconds = curInSeconds - preInseconds;
             ... =  0x00000000  -  0xffffffff     = 1

...which gives the expected result without any special rollover handling logic at all.

And so you may be thinking, "Sure, that works for your trivial example, but what if the rollover is HUGE?" OK, well, let's explore that possibility. Assume then that preInseconds=0xffffffff and curInSeconds=0xfffffffe. In this example, we've ALMOST wrapped completely back around from the previous sample; in fact, we're only one count away from it. In this case, our result should be 0xffffffff (i.e. one less count than the number of values that can be represented by a uint32):

elapsedInSeconds = curInSeconds - preInseconds;
             ... =  0xfffffffe  -  0xffffffff     = 0xffffffff

Don't believe me? Try this:

#include <stdio.h>
typedef unsigned long uint32;
int main()
{
    uint32 prev = 0xffffffff;
    uint32 cur  = 0xfffffffe;
    uint32 result = cur - prev;
    printf("0x%08x - 0x%08x = 0x%08x\n", cur, prev, result);
}

NOW, let's get back to the math behind your implementation:

That computation "sort of" computes the two's complement of preInseconds and assigns the result back to preInseconds. And if you know anything about computer representations of numbers and two's complement addition and subtraction, you know that computing the difference A-B is the same as computing the sum of A and the two's complement of B, i.e. A+(-B). If you've never investigated it before, look up on Wikipedia or wherever about how two's complement makes a computer's ALU able to re-use their addition circuitry for subtraction.

Now on to what's actually "wrong" with the code you've shown:

To compute the two's complement of a number, you invert the number (change all of its 0 bits to 1, and all of its 1 bits to 0), and then add one. It's that simple. And that's "sort of" what your code is doing, but not quite.

preInseconds = preInseconds<<1;     // oops, here we lose the top bit
preInseconds = ~preInseconds;       // do the 2's complement inversion step*
preInseconds = preInseconds+1       // do the 2's complement addition step*
preInseconds = preInseconds>>1;     // shift back to where it ought to be,
                                    // but without that top bit we wish we kept

*NOTE: The +1 above only works here because the low bit is
 guaranteed to be 1 after the ~ operation, which carries a 1
 up into the 2nd bit, where it matters.

So we see here that essentially what the math is doing is manually negating the value of preInseconds by performing a "nearly" two's complement conversion of it. Unfortunately it's also losing the top bit in the process, which makes the rollover logic only work up to a maximum of elapsedInSeconds = 0x7fffffff, not what should really be its full scale limit of 0xffffffff.

You could convert it to the following, and eliminate the loss of the top bit:

preInseconds = ~preInseconds;       // do the 2's complement inversion step
preInseconds = preInseconds+1       // do the 2's complement addition step

So now you've computed the two's complement directly, and you can compute the result:

elapsedInSeconds = curInSeconds + preInseconds; // (preInseconds is the 2's compl of its original value)

But the silly thing is that this is computationally equivalent to simply doing this...

elapsedInSeconds = curInSeconds - preInseconds; // (preInseconds is its unconverted original value)

And once you realize that, your code example becomes:

if(curInSeconds>=preInseconds)
{
    elapsedInSeconds = curInSeconds - preInseconds;
}
else // rollover
{
    elapsedInSeconds = curInSeconds - preInseconds;
}

...which should make it clear that there's no need to handle rollover as a special case in the first place.

Answer 3

Let the width of unsigned long be w. Then the maximal value an unsigned long can hold is

ULONG_MAX = 2^w - 1

Let preInseconds = a + b, where

a = preInseconds & (1ul << (w-1))
b = preInseconds & ((1ul << (w-1)) - 1)

a is either 0 or 2^(w-1), depending on whether preInseconds >= 2^(w-1). Then the initial left shift annihilates a, so

preInseconds << 1

gives b << 1 or 2*b.

Then the bitwise complement is taken,

~(b << 1)

gives ULONG_MAX - (b << 1).

If b == 0, adding 1 to ULONG_MAX - (b << 1) results in 0, otherwise

~(b << 1) + 1

gives

2^w - (b << 1)

Then shifting one bit to the right produces 0 if b == 0 and

2^(w-1) - b

otherwise. Hence

preInseconds = ((~(preInseconds <<1)+1)>>1);

sets preInseconds to

2^(w-1) - b

if b != 0, and to 0 if b == 0.

Finally,

elapsedInSeconds = curInSeconds + preInseconds;

therefore sets elapsedInSeconds to the value of curInSeconds if preInseconds was 2^(w-1) [if the else branch is taken, preInseconds > curInSeconds, so it's not 0] and to

curInSeconds - (preInseconds & (ULONG_MAX >> 1)) + 2^(w-1)

otherwise.

I'm not sure what the purpose of that operation is. For preInseconds > curInSeconds, the computation

curInSeconds - preInseconds

would result in

(2^w - preInseconds) + curInSeconds

which is the same as (mathematically)

(2^w + curInSeconds) - preInseconds

which would be the elapsed time if the curInSeconds counter rolled over once since the last time preInseconds was taken, which presumably happened if the current counter value is smaller than the previous. That would make sense.

With the gymnastics done in the else branch,

• if preInseconds <= 2^(w-1), elapsedInSeconds becomes curInSeconds - preInseconds + 2^(w-1), the difference between the rolled-over current counter and the previous counter minus 2^(w-1)
• if preInseconds > 2^(w-1), since x - 2^(w-1) == x + 2^(w-1) in unsigned arithmetic, we obtain the same result as with curInSeconds - preInSeconds.

So, assuming curInSeconds rolled over once, it calculates the elapsed seconds between the previous and current event, unless the roll-over took place 2^(w-1) or more seconds after the previous event, in which case 2^(w-1) seconds are subtracted from the actual elapsed time.