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

Question

I need code for a router that is allowed to overflow, and where <> continues to distinguish between earlier values ​​and later values ​​for some specific interval.

To clarify, one of the possible implementations 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 16 bits, cur just overflowed, its current value is, say, 5 . Depending on the dut value dut functions will return

• From 0 to 16384: isEarlier → (cur < dut) , isLater → (cur > dut)
• From 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 sure that there is something similar in PostgreSQL (transferring transaction identifiers), I just could not find a function that actually does this. I'm sure there is something similar in the Linux kernel, possibly a macro. But neither Google Codesearch nor grep over / usr / include / linux could enable it. Any ideas where this is?

Clarified the role of cur and dut. "Invalid" exists as a guarantee. As the differences between cur and dut get larger, the function eventually complains.

Answer 1

I think you are talking about the proper handling of a circle of numbers. This is actually quite simple.

This does not do what you said (you don’t know why you have this 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 = ab; return diff < 0; } bool isLater(uint16_t a, uint16_t b) { int16_t diff = ab; return diff > 0; } 

edit : it has a “branch point” with diff = -32768, so if a = 5 and b = 32772, diff = -32767, which is less than 0 and therefore 5 is “earlier” than 32772. If a = 5 and b = 32774, diff = -32769 = 32767, which is greater than 0 and, therefore, 5 is “later” than 32774. This defines “earlier” and “later” in the sense of (a) simple mathematics and (b) since walk counters can be interpreted as having many solutions mod 65536, he selects the solution a and b, which are the "closest" to each other with respect to the circle of numbers.

If a and b differ by 32768, then they are equally distant from each other, and simple mathematics is used for the simplest choice ... this “breaks” the antisymmetric property “earlier” and “later” in the sense that isLater (5, 32773 ) is true and isLater (32773.5) is also true. But how do you know if "5" means the number 5, or "5" means the number 65541? (just like abs (-32768) == -32768 gives an odd pointless answer). If you want to keep antisymmetry, for example. isLater (b, a) == isEarlier (a, b), then you can always do this:

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

If you want to shift the branch point in one direction by -32768 + K, use instead:

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

It is no longer used 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 certain choice of intervals, which is different from the reasoning that I use with enveloped numbers. The functions defined here will not meet your needs as indicated, but I find the interval selection a bit strange. Perhaps you could explain how you defined them?

Answer 2

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

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

Answer 3

Good for the record. Here is my solution, here is what I had in mind:

 #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 4

I think you just wrote it :). Why not transfer your post to some code?

Answer 5

Remember that you cannot get ">" and "<" to do what you want in C. They apply only to numbers, and operator overloading does not occur. The same applies to your exception; C has no exceptions.

You could write some access functions that handle unsigned integral types in this way, and that would not be easy. (In C, the overflow is undefined for signed integral types, although it wraps around most modern systems.) That would not be so difficult.