Timing using Bresenham's Algorithm

There are loads of reasons to time things, or wait for a specific time. If you want to wait for a specific time you can loop, doing nothing, until that time has elapsed. This can be useful, but it assumes the MCU is only doing one job. A better way it to count a time unit (such as a millisecond) in the background. Then you can get the current count, add the wait period and store the stop value, then keep checking in the main loop until the current count has exceeded the stored stop value. You will probably overshoot a little, but often this is OK. If you are trying to see if a button is pressed for, say, more than two seconds to respond to a long press, if you overshoot by a few micro seconds it makes no difference. If you are processing something regularly, such as displaying a timer, you can use the actual count time to check when the display should change. The nice thing is that you can use the count to test multiple wait or timer events independently. The snag is, how to build a reliable counter.

The PIC range have multiple timers, some of which get pressed into service for various jobs. Timer0 is always an 8 bit timer. It can either count external pulses (on a specific input pin) or increment each time the instruction cycle ticks. If an external crystal is used the instruction cycle runs at one quarter the crystal's frequency, so a 4MHz crystal means each instruction takes one one-millionth of a second and Timer0 will also increment at 1MHz. If the Timer0 is set running from zero, it will quickly reach 255 (in 255µs). At the next tick it will roll over to 0, so counting beyond 255 seems hard and 255µs is not that useful a length of time. The key is that as the timer rolls from 255 to 0, it can generate an interrupt.

An interrupt is a useful concept, when an interrupt is triggered the instruction the MCU is executing is finished, the address that the next instruction is at is stored (on the stack) and execution jumps to the interrupt address and continues there. When the interrupt code is complete it returns with a particular instruction which recovers the next address from the stack and jumps there to continue as if nothing has happened. Interrupt code must be short so as not to make everything else grind to a halt and it must not change the status registers so the original code really does continue unaffected. The XC-8 compiler for PICs handles the interrupt routine by letting you declare a function with the prefix interrupt. The function must be void and have no parameters and it shouldn't be called by anything else. XC-8 handles the saving and restoring of the status registers for you.

Now we have the means to use the Timer0 to generate ticks every 256µs (we need to set it up to do that) and that could be the basis of our count. Triggering an interrupt every 256µs is OK, if the code is very short, but it could be better if it was called less often - we are not going to be interested in approximately ¼ millisecond timing usually. Timer0 has a prescaler that is used as a divider to slowdown the rate at which the timer increments. If we use a prescaler of 4, the interrupt will fire every 1.024 milliseconds. We could use this as an approximation to a millisecond, and sometimes that is good enough. It would be possible to reset the Timer0 to count from a different number than 0, so counting from 250, four times gives exactly 1000, not 1024. This is fraught with problems, not least it adds a significant overhead to every interrupt routine, something to be avoided.

It would be acceptable to use a counter that is the number of 1024 ticks that have passed, but it is tempting to try to make a count in milliseconds. The counter and prescaler works in binary, so some sort of conversion is needed and a very neat one called Bresenham's Algorithm helps. This allows any difference between the counter and the target to be carried over and eventually smoothed out. To make the most of the prescaler we need to decide the resolution we want to count in. To count in 1ms units we need to use a prescaler that triggers the interrupt every 512µs, if we are happy to count in 2ms units we can use a prescaler that triggers every 1024µs.

The logic goes something like this:

volatile int millis;
millis=0;

...

// interrupt routine
interrupt void intrtn() {
    static int icount=0;
  
    icount+=512;
    if (icount>1000) {
        icount-=1000;
        ++millis;
    }
    // cleanup the interrupt stuff
}

So much for the theory, now lets see if I can make an LED flash at a reliable beat using this method ...