It looks to me more complicated than it should be. By the way, I think modulo for negative numbers has weird behavior.

This is a problem with other counters as well, for example how many bytes or packets were transferred. If you know that the counter can only go up then it is easy to detect when it wraps around and figure out the difference, though you have to have a separate check to see if the device has not restarted (since those counters are reset on reboot).

However, it leaves the problem of the counter overflowing multiple times between checks. For example, a 32bit counter of bytes transferred will overflow every ~34 seconds when the transfer rate is 1gbps. If you check it every minute, you'll get nonsense data because while it is possible to detect that the counter has overflowed, there is no way to know how many times it has overflowed (or even if it has overflowed if the new value if bigger than the old value).

Newer switches and such just use 64bit counters.

@Pentium100 Have you any idea how to "path up" modulo? I have seen and used a programming technique for a while, but while it works, I is not the solution I am looking for at the moment.
Like patching modulo by adding a bias to make the value go above minus, and then subtracting that bias later, seem to be one idea, but eventually you just try to do an emulation of two's complement on a value that already has two's complement, so you will overflow earlier. Also, I use wrapping mainly on values that have been subtracted, making them relative in any direction, negative and positive. That is where I get in trouble using modulo, but not if using bitwise AND (only works on power-of-two values).

34 seconds is a very small timing window for networking. Overflowing multiple times has always been a problem in digital electronics. Thankfully, larger registers, like 64-bit (which is ridiculously large) solves many of those problems. Same goes with delta times with 64-bit values, which are like in the 5 nanoseconds range and don't overflow for over 100 years or so.

Maybe @Metal Brony 42 has any ideas? Hopefully he sees this blog at some point.

2 hours ago, Splashee said:

34 seconds is a very small timing window for networking.

Definitely, though that specification was made at a time when 10mbps was really fast.

3 hours ago, Splashee said:

Have you any idea how to "path up" modulo?

What is wrong with changing what you are subtracting based on which value is bigger? I somehow don't think that it would be slower than a mod operation, then again, maybe for modern CPUs mod is faster.

On 2021-07-29 at 9:07 PM, Pentium100 said:

What is wrong with changing what you are subtracting based on which value is bigger? I somehow don't think that it would be slower than a mod operation, then again, maybe for modern CPUs mod is faster.

Okay, so let's go back to the analog clock example. Since we only have 60 minutes before it overflows/underflows, that might not be too much to add/subtract a bias value so that negative values can be completely ruled out.

This time, let's do it in binary with logical AND. Since this will work for every value. Problem is, we need to have 64 minutes on the clock to make this work (since we can only do wrapping on power-of-two values).

If we have the minutes of 9605951 (hexadecimal 0x92933F), you can see where this is going? Subtracting a full hour of the clock + 1 minute (0x41) from this value, should result in the same example as the 59 to 58 minutes on the previous example (using modulo) in my post above:
 

Quote

(9605951 - 65) = 9605886

9605886 AND 63 = 62

We went from 63 minutes to 62, with a full hour rewind (where an hour is 64 minutes).

Now let's do the same thing but being on 63 minutes. We are going into the negative values now. But logical AND always works correctly:

Quote

(63 - 65) = -2

-2 AND 63 = 62

int wrapped_value = (9605951 - 65); // wrapped_value == 9605886
wrapped_value %= 64; // Just remember, AND 63 and MOD 64 has the same effect on positive numbers!    wrapped_value == 62

if (wrapped_value < 0) wrapped_value += 64; // This is my fix for negative numbers. This is also why I am using code, since we need an if statement

The post above bugged out, so I am continuing here:

And now for the negative values. This also works with modulo because of the if statement I introduced:

int wrapped_value = (63 - 65); // wrapped_value == -2
wrapped_value %= 64; // wrapped_value == -2

if (wrapped_value < 0) wrapped_value += 64; // wrapped_value == 62

So everything is cool! We now use a divide operation which is slower, than the logical AND, for the exact same result. But things are not so fun when we start introducing values that are also wrapped with the same formula as before.... Yes, we just happen to be on minute 62. That is still in the range of being wrapped at 64. So this math always work as well:

Quote

((9605951 AND 63) - (65 AND 63)) = 62

This works with modulo as well if all the modulo operations do that if statement.

BUT, what do we need modulo for? We need it when we don't use power-of-two values, such as when the clock has 60 minutes. Now we introduce the wrapping problem that I cannot solve:

Quote

(59 MOD 60) - (61 MOD 60) = 58

Okay, I have no idea why that worked....? I never thought of using MOD on the arguments to the subtraction before. I will need some time to think about this. My examples are very basic compared to what I use wrapping for, so this might still not solve my problems just because this worked.

What I was going for is the fact that CPU register values still wrap on power-of-two values, and we introduce two wrapping points incompatible with each other, one for modulo, and one for all the bits of the CPU register we are using.

The wrapping point of 60 will not wrap perfectly subtracting below 0, because we also had an automatic AND of the register size, like for 32-bit (0xFFFFFFFF).

4294967296 / 60 = 71582788,266666666666666666666667

If the register wrapped at (71582788 * 60) == 4294967280 (0xFFFFFFF0), and going below that value would be -1, -2, and so on, then all my problems would be solved.

So, what you are trying to do is not just ignore when the counter wraps around (so the difference always stays positive), but you are actually interested in the modulo of the difference and not the difference itself? Did I understand this correctly? 

Can you have a 64bit temporary variable? IF so, you could do something like this to always get a positive diffference.

if ( newts < oldts ) { //assuming that if both values are equal it means the counter wrapped around.
                 dif=newts-oldts;
                  } else {
                    dif=(newts+(((uint64_t)1) << 32))-oldts;
                  }

7 minutes ago, Pentium100 said:

but you are actually interested in the modulo of the difference and not the difference itself? Did I understand this correctly?

Yes! Because it has a very useful attribute to it, bit I don't want to introduce that yet, since it is slightly over complicated.

Currently I am working with JavaScript that doesn't support 64 bit values
But for my C++ projects, I will see if a 64 bit temporary variable can solve my problem. Not a bad idea!

I used this for my mpegts segmenter (one value behaves like a counter, but is 33 bits, so I had to use a 64bit variable to hold it anyway).

If you cannot use 64bit variables, you can probably do something like this:

if (newts < oldts) {
			dif=UINT_MAX - oldts;
  			dif=dif + newts + 1;
} else {
  dif=newts-oldts;

I'm gonna do some tests today, and see if these 64-bit fixes can be used. I will also try to pinpoint the "real problem" with the wrapping that I am using, which I haven't correctly analyzed yet. That modulo on each absolute value before subtraction into a relative value had an effect, but I know it doesn't work for my task, so I better look into why that is.