Question for the programmers (C)

[zahc]

I have a real noob question about variable overflow.

I'm writing a function to generate sinusoidal output via PWM. In my function, I have an 32-element array containing sinusoidal PWM duty cycle values, and I wish to move through the values of that array when the function is called. When I get to the 31th element of the array, I want to start over at the 0th element--the array values are 'circular'.

The way I'm doing this is that I have unsigned byte variable "index". I increment that by 1 when the function is called, and then copy the (index % N)th array element to the PWM output compare register. I believe that my index variable can overflow without any problem. The modulo will work correctly and everything, even through the overflow from 255 to 0.

I'm not sure exactly what happens going the other way, however. When I _decrement_ my index variable, eventually I'm going to get down to 0. When I decrement it again, does it "underflow" back to 255? And in this case, is the modulo operator going to work the "expected" way?

I have a feeling it will and everything will be alright, but I don't really know. I can use a signed variable, if that is necessary.

[Regolith]

I'm not much of a programmer, and it's been a LONG time since the last time I coded in C, so my answer may be hilariously wrong, but...

It seems to me that unless you have some bit of code* that specifically handles the possibility of decrementing the array index below zero, you're going to go out of range and throw an error.


*Something like

Code: [Select]

if (arrayIndex < 0);
   arrayIndex = 255; //sets array index to highest value
end if;


[zahc]

If I was using a signed variable, that would work. But with an unsigned variable, there is no sign bit, so there is no negative numbers, so I assume it auto-wraps back to 255 if you try to decrement it below 0. The the question is if the modulo operator will do what I want when that happens.

[Regolith]

If I was using a signed variable, that would work. But with an unsigned variable, there is no sign bit, so there is no negative numbers, so I assume it auto-wraps back to 255 if you try to decrement it below 0. The the question is if the modulo operator will do what I want when that happens.

Ah. Like I said, long time since I messed with C. 

There's one way to find out for sure: try it. Set up something simple, force it to decrement below zero, see what happens. If it continues to work correctly, then you're good to go.

[zahc]

Yeah, the thing is it's hard to debug microcontrollers; it's not like there's stdout.

I just wrote this on my PC, though, which seems to indicate the overflow will work. I assume that what gcc is compiling a char to on this  x86 pc is equivalent to a uint8_t on the 8-bit micro.

Code: [Select]

#include <stdio.h>

int main(){

    unsigned char index;

    for (int i =0;i<257;i++){
        printf("index %d\n", index);
        printf("index mod32 %d\n", index%32);
        index ++;
    }
    for (int i =0;i<257;i++){
        printf("index %d\n", index);
        printf("index mod32 %d\n", index%32);
        index --;
    }
}

Code: [Select]

index mod32 28
index 253
index mod32 29
index 254
index mod32 30
index 255
index mod32 31
index 0
index mod32 0
index 1
index mod32 1
index 0
index mod32 0
index 255
index mod32 31
index 254
index mod32 30
index 253
index mod32 29
index 252

[Tallpine]

index = ( (index + 1) & 0x1F )

[birdman]

index = ( (index + 1) & 0x1F )

If an increment on the unsigned overflows correctly, I was going to suggest this, logical ops on single bytes should be speedy and low overhead on an MCU.

[zahc]

I discovered that doing X mod N is the same as doing X & N-1, but only if N is a power of 2.

Is ( (index + 1) & 0x1F ) any faster than doing index++; index &0x1F?

I'm still trying to learn what all the operations mean in terms of machine instructions. Perl can really do a number on you that way.

[CNYCacher]

I have a real noob question about variable overflow.

I'm writing a function to generate sinusoidal output via PWM. In my function, I have an 32-element array containing sinusoidal PWM duty cycle values, and I wish to move through the values of that array when the function is called. When I get to the 31th element of the array, I want to start over at the 0th element--the array values are 'circular'.

The way I'm doing this is that I have unsigned byte variable "index". I increment that by 1 when the function is called, and then copy the (index % N)th array element to the PWM output compare register. I believe that my index variable can overflow without any problem. The modulo will work correctly and everything, even through the overflow from 255 to 0.

I'm not sure exactly what happens going the other way, however. When I _decrement_ my index variable, eventually I'm going to get down to 0. When I decrement it again, does it "underflow" back to 255? And in this case, is the modulo operator going to work the "expected" way?

I have a feeling it will and everything will be alright, but I don't really know. I can use a signed variable, if that is necessary.

In your example, N is 32, because you have 32 registers.  What you are doing by incrementing the index, and then retrieving the (index % N)th element in the array works to create your loop, but the only reason that your loop doesn't break when you overflow the index is the coincidence that 256%32=0.

So, you can go happily along, index++ing all day and as your 8-bit value loops from 0-255, index%N does 8 tidy loops from 0-32, and they match back up again at 0.

The issue comes up when index==0 and you want to index--, you are worried that the result mod32 might not be 31 and in truth I am not sure what happens when you decrement an 8-bit unsigned int from 0, but you don't need to know, and here's why:

Every time you increment index, just modN index itself, and then retrieve the indexth element in the array.  To decrement, don't -1, add N-1

Your current:

Code: [Select]

index = index+1;
value = array[index%N]
My suggestion:

Code: [Select]

index = (index+1)%N
value = array[index]


This will keep your index in a tight 0 to (N-1) loop, and isn't dependant upon a magic N which neatly divides the maximum value of index.

But, how to decrement?  Simple:

Current:

Code: [Select]

index = index -1:
Suggested:

Code: [Select]

index = (index + N -1) % N
Now, since adding multiples of N doesn't really matter to the outcome of the modulo, you could replace both equations with one, simple conglomeration:

Code: [Select]

if (we want to go up one) {
  delta = 1;
} else {
  delta = -1;
}

index = (index + N + delta) % N;
value = array[index];


[Tallpine]

I discovered that doing X mod N is the same as doing X & N-1, but only if N is a power of 2.

Is ( (index + 1) & 0x1F ) any faster than doing index++; index &0x1F?

I'm still trying to learn what all the operations mean in terms of machine instructions. Perl can really do a number on you that way.

I don't think in terms of speed it will matter that much.  I was just trying to give you a single simple statement that would always work.

It probably should have been: index = ++index & 0x1F, but I just don't like trusting to pre-fix/post-fix definitions, and it's often hard to figure out what the original intent was at some point in the future.

This sort of thing is done all the time for FIFO ring buffers in low level code such as I/O device drivers.

And just for the record, 0x00 - 0x01 = 0xFF :) 

(assuming 8-bit data size - actually that's what makes the bitwise logic so clean is that it would work the same even if you were using a 32 bit datatype:  0xFFFFFFFF & 0x1F = 0x1F)

[zahc]

This will keep your index in a tight 0 to (N-1) loop, and isn't dependant upon a magic N which neatly divides the maximum value of index.

This is a good technique and I'm glad you explained it, especially for cases where the size of my loop doesn't happen to be a power of 2.

I can't use it for this program though, because I'm actually using the most significant nybble of the index byte to track when and how the lower nybble over- or under-flows. I'm driving a unipolar stepper and have to switch the output pin state table every time the array loops through.

I also decompiled my code and avr-gcc is optimizing the % operation to a single ANDI instruction anyway, but I will still write it with a bitwise &.

[birdman]

If your loop isn't a nice power of two, it seems like you would be operating sub optimally anyway...