Needed: Wrappable Counter where < and > do "the right thing"

Question

I need the code to a couter that is allowed to overflow and where < > continue to tell earlier values from later values, for some defined interval.

To clarify, one possible implementation would be:

Consider two such counters cur and dut (device under test), consider two functions:

bool isEarlier(cur, dut)    // Is dut earlier than cur?
bool isLater(cur, dut)

cur and dut are 16 bit, cur has just overflowed, its current value is, let's say 5. Depending on the value of dut, the functions would return

• 0 to 16384: isEarlier -> (cur < dut), isLater -> (cur > dut)
• 16384 to 32768: isEarlier -> false, isLater -> true
• 32768 to 49152: invalid, log error
• 49152 to 65536: isEarlier -> true, isLater -> false

I can write the code myself, no problem. I'm just lazy. I know for fact that there is something like that in PostgreSQL (transaction ids wrap), I just couldn't locate the function that actually does it. I am pretty sure there is something like that in the Linux kernel, probably a macro. But neighther Google codesearch, nor grep over /usr/include/linux could turn it up. Any ideas where it is?

Clarified role of cur and dut. The "invalid" is there as a safeguard. As the differences between cur and dut become bigger, the function eventually complains.

Answer 1

I think you're talking about handling the wraparound of the number circle correctly. It's quite easy, actually.

This doesn't do precisely what you said (not sure why you have that "exception" interval), but:

typedef unsigned short uint16_t;
typedef signed short int16_t;
// abstract out 16-bit types in case "short" doesn't correspond to 16bits

bool isEarlier(uint16_t a, uint16_t b)
{
   int16_t diff = a-b;
   return diff < 0;
}
bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = a-b;
   return diff > 0;
}

edit: this has a "branch point" at diff=-32768, so that if a=5 and b=32772, diff=-32767 which is less than 0 and hence 5 is "earlier" than 32772. If a=5 and b=32774, diff=-32769=32767 which is greater than 0 and hence 5 is "later" than 32774. This defines "earlier" and "later" in the sense of (a) the simplest math, and (b) because wraparound counters can be interpreted as having multiple solutions mod 65536, it picks the solution of a and b that are "closest" to each other with respect to the number circle.

If a and b differ by 32768 then they are equally far apart and the simple math is used to pick easiest... this "violates" the antisymmetric property of "earlier" and "later" in the sense that isLater(5,32773) is true and isLater(32773,5) is also true. But how do you know whether "5" represents a count of 5, or "5" represents a count of 65541? (just as abs(-32768) == -32768 gives an odd nonsensical answer) If you wish to maintain antisymmetry e.g. isLater(b,a) == isEarlier(a,b), then you can always do this:

bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = b-a;
   return diff < 0;
}

If you wish to bias the branch point in one direction to happen at -32768+K, then use this instead:

bool isEarlier(uint16_t a, uint16_t b)
{
   int16_t diff = a-b-K;
   return diff < -K;
}
bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = b-a-K;
   return diff < -K;
}

This no longer uses closest; if, for example, K=12768, and a=5, then for b=6,7,8,9,... 20005, isEarlier(a,b) and isLater(b,a) will be true, and for b=20006, 20007, ... 65534, 65535, 0, 1, 2, 3, 4, 5 isEarlier(a,b) and isLater(b,a) will be false.

You have a particular choice of intervals which is different from the rationale I use with wraparound numbers. The functions defined here would not meet your needs as stated, but I find those choices of interval a little peculiar. Perhaps you could explain how you determined them?

Answer 2

Ok, for the record. Here is my solution, this is what I meant:

#include <stdint.h>


void increase_cyclic_counter (uint16_t *cnt)
{
#ifdef CYCLIC_COUNTER_EXPLICIT_WRAP
    if (*cnt < 2^16-1)
        *cnt++;
    else
        *cnt = 0;
#else
    *cnt++;
#endif
}


#define SAME 1
#define LATER 0
#define EARLIER 2
#define FORBIDDEN -1

/* dut (device under test) is tested against cur
 * returns:
 *    EARLIER (LATER) if dut happened earlier (later) in the sequence than cur
 *    SAME            if dut == cur
 *    FORBIDDEN       if dut and cur are that far away in the cyclic sequence
 *                    that no unambigious jugement is possible
 *
 * The basic idea is the same as with two-character year codes, where 
 * '97' stands for 1997 and '11' stands for 2011. '50' is regarded as 
 * too ambigous and therefore rejected.
 *
 * The implementation splits the short integer range 0-65535 into 4 parts:
 *   0-16383, 16384-32767, 32768-49151, 49152-65536
 * With cur and dut in the same range, normal arithmetics apply, else the 
 * ranges are compared to each other.
 */

int test_cyclic_counter (uint16_t cur, uint16_t dut)
{
    switch (((int)(cur>>14)) - ((int)(dut>>14)))
    {
        case 0:  // same range
            if (dut < cur) 
                return EARLIER;
            else if (dut == cur)
                return SAME;
            else 
                return LATER;

        case 1:
        case -3:
            return EARLIER;

        case 3:
        case -1:        
            return LATER;

        default: 
            return FORBIDDEN;
    }
}

Answer 3

First compute the difference, then check into which window it falls.

Since it is so simple and the sizes of the past/future/error windows vary, you have to do it yourself.

Answer 4

Bear in mind that you can't get ">" and "<" to do what you want in C. They apply to numbers only, and there is no operator overloading. The same thing applies to your exception; C does not have exceptions.

You could write some access functions that would treat unsigned integral types that way, and that wouldn't be difficult. (In C, overflow is undefined for signed integral types, although on most modern systems it wraps around.) It wouldn't be that difficult.

Answer 5

It seems to me you just wrote it :). Why not translate your post into some C code ?