Overflow-immune timer

Hey

I was programming in arduino SDK and came across a problem. I noticed that arduino runtime provides a function called millis() to track how much time has passed since the board powered up. This is neat when you want to track time, but the timer seems to overflow every 50 days according to the documentation. So I was wondering…

Is there a way to create a timer that is immune to overflows, provided that you’re not interested in how much time has passed since the board startup, but rather how much time has passed since the last loop(). I have written a simple routine that does just that. This Delta() function has to be called at the very beginning of the loop() function. It returns the amount of milliseconds passed since last time it was called.

I’m a bit puzzled about what happens when the timer overflows, and how to detect it. I’ve used a very simple detection. So when the following is true: “time < prev_time” the timer has overflowed and the delta should be corrected. What do you think about this code?

unsigned long prev_time;

unsigned long Delta() {
      unsigned long time;
      unsigned long delta;
      
      time = millis();
      if (time < prev_time) { // Timer overflow
            delta = 0xffffffff - prev_time + time;
      } else {
            delta = time - prev_time;
      }
      
      prev_time = time;
      if (delta == time) return 0;
      return delta;
}

Thoughts, suggestions?

In your case, you can do in your function just:return millis() - delta;

If you want to check if a period has expired the correct way to do it is:

if (time - prev_time >= delta) {
  ...
}

Everything else either doesn't work or just adds complexity without any benefit. Just make sure as you did that you work with unsigned long.

Korman

Have a look at his thread for the explanation: http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1260223964/1

Perhaps I was not being clear enough with my question. I am fully aware of what happens on the binary level when a variable overflows. Consider the following structure:

struct bytes {
      char A;
      char B;
      char C;
      char D;
} __attribute__((__packed__));

Now let’s start incrementing variable B like this: “B += 17;”, and see what happens. The B will increment in the following way: 0, 21, 42, 63, 84, …, 210, 231, 252, 273 (17). When the value reaches 273, the variable overflows. This is because a byte (8 bits) can only hold values in range of 0 to 255. So what happens when the value is set to 273? If we convert 273 to binary we get 100010001 - that’s 9 bits!

Since a byte can only consist of 8 bits, we must discard the leftmost bit, and our variable really looks like this: 00010001 - that’s 17 in decimal. But what happened to the discarded bit? Well, technically it is still there, but it is outside the boundaries of variable B. It now resides in a piece of memory that belongs to another variable. Depending on whether the system is little endian or big endian, this means that one of the variables A or C will be set to 1 (assuming they’re both zero). This is called an (integer) overflow. I have some experience with integer overflows on x86 platforms. We’ve used this method to write remote code execution exploits for Windows (or rather software that runs on windows).

Although, I’m fairly new to AVR world, and I am just entering the phase of understanding the internals of AVR microprocessors. I have reviewed the arduino timer source code, but I’m not sure I fully understand it yet. So I am trying to create an overflow handling mechanism at the cost of sacrificing absolute_time and replacing it with delta_time. I’ve written a simple code to detect an overflow and compensate it. When an overflow occurs, the condition “time < prev_time” translates to “17 < 252”, which translates to “true”, and the “if” block is executed. Now we can correct the overflow by doing some math.

Here’s the overflow equation from my code above:
Note: I added “+1” to my equation because apparently I missed it in my original code which has an off-by-one bug.

delta = 0xffffffff - prev_time + time + 1;

And on the byte level:

delta = 0xff - prev_time + time + 1;

Having inserted the values from above, this translates to:

delta = 255 - 252 + 17 + 1;

And finally:

delta = 21;

Which is correct!

My question: Do you see any flaws in my logic?

Since a byte can only consist of 8 bits, we must discard the leftmost bit, and our variable really looks like this: 00010001 - that's 17 in decimal. But what happened to the discarded bit? Well, technically it is still there, but it is outside the boundaries of variable B. It now resides in a piece of memory that belongs to another variable.

No, the "extra" bit does not overflow into another memory location. The "extra" bit is called a "carry flag". It resides solely inside the ALU of the processor.

Depending on whether the system is little endian or big endian, this means that one of the variables A or C will be set to 1 (assuming they're both zero).

That's not what happens.

This is called an (integer) overflow.

Storing the "extra" bit into a surrounding memory location is not called anything because that isn't what happens.

"B += 17;" will only affect B for the simple reason that the compiler only generates machine instructions that manipulate B. It is simply impossible for that expression to have any effect on A or C.

So I am trying to create an overflow handling mechanism

You're wasting your time.

My question: Do you see any flaws in my logic?

Yes - you’re adding unnecessary complexity to an issue where a simple solution exists (delta = unsigned diference).

No, the "extra" bit does not overflow into another memory location. The "extra" bit is called a "carry flag". It resides solely inside the ALU of the processor.

Okay, apparently this clearly differs from what I've been doing on x86 platforms... at least on byte-level while working in x86 assembly with heaps.

Storing the "extra" bit into a surrounding memory location is not called anything because that isn't what happens.

"B += 17;" will only affect B for the simple reason that the compiler only generates machine instructions that manipulate B. It is simply impossible for that expression to have any effect on A or C.

On x86 you can overflow an adjacent memory location and thus increase its value by one by using this technique. Should the adjacent memory be used somehow, this can lead to "undefined behaviour", a crash, or in the worst case a code execution exploit. I've done this before and I know it's possible! Tho I am unsure how this goes on AVR architechure, hence I am asking on this forum.

You're wasting your time.

Thanks for the encouragement.

Yes - you're adding unnecessary complexity to an issue where a simple solution exists (delta = unsigned diference).

Let's see...
252 = 11111100
17 = 00010001

17 - 252 = -235

00010001 -
11111100 =
00010101 (21)

Yeah, I see it now. I was unaware of this solution, thanks for pointing it out.

So I am trying to create an overflow handling mechanism

You're wasting your time.

Thanks for the encouragement.

You want me to encourage you to spend time on something that's unnecessary?

Well no, but I got the impression that you were trying to tell me that I'm wasting my time here in the arduino community.

In that case, I apologize. That was not my intent. I was trying to say that you were wasting your time trying to deal with an overflow problem because there is no overflow problem. As far as I’m concerned, you are welcome here.