[OPINION needed] Mixer arithmetic overflow prevention?

[openFsguruh]

I noticed in the mixer calculation in open9x and the same for thus er9x there is a internally calculation partly based on 16bits integer partly 32bits integer.
As all resources are very limited on the stock board the calculation must be limited.
What I am interested is the behaviour expected in case of arithmetic overflow.
So internally open9x currently works with a 32x reserve factor. That means when you have a mixer line defined which output is 100% and add with 32x other output lines 100% the output value is still OK and stays at 100% because it is clipped on output.
Because we allow more than 100% and there is the possibilty to add offset as well the output for one mixer line may be above 200% If we use GVARS it could be even more.
If this output is added or even multiplied with further mixer lines the result may exceed 32x 100% which would result in a arithmetic overflow. This would cause a immediate jump from +100% to -100% for the overflowed output channel.

How important is it to prevent such situations?
How should it be prevented?
To give an example: The easiest internal coding just clipps at 100% but would introduce arithmetic faults if somebody needs such high internal values before downscaling.

[MikeB]

For er9x, and I believe for open9x, the calculated channel values are kept in 32-bit integers. I also believe 16-bit values are only used when it is known the values used fit. Many of the calculations are performed on 32-bit values.
If you can see an area where values can overflow we would, of course, like to know, but you need to look very carefully at the operations actually performed, and what size the parameters are.

Mike.

[openFsguruh]

Hi Mike,
yes I am involved in the development shortly and I know it will overflow and I know it is partly done 32-bit but also 16bits.
The 32x limit is actually based on the 16bit values. Still good enough I think, if overflows are handled.
Or may be not good enough?
We tested it and it will actually overflow. So what is your opinion?

[MikeB]

I'm curious to know when you get an overflow. I'm looking at the er9x code. It uses a 16-bit int to calculate the value for a single mix, then converts to a 32-bit value before adding/multiplying to the actual channel value that is also 32-bits.

Mike.

[openFsguruh]

Hi Mike,
I give a short description here, but you can read details in change tracking of open9x for branch. See links below.
I am involved in this mix optimizations and flash savings change Bertrand mentioned.
The overflow can be simply reached by adding mixline by mixline 125% offset and 125% weight multiplying each line.
As you mentioned it is half way done 16bit and then 32bit. The problem arise when we go from one line to the next one, because we fall back to 16bits again. You will not generate an overflow in one mixline, but it could be combined and that's used a lot.

I can do a change to prevent the overflow and truncate the calculation above 100%. This will cause a steady 100% output, but of course the internal value is then wrong and if used in further mix lines will result in wrong calculaiton. But it would be wrong anyway. Not sure how important this is and if it should be handled or not. That's the reason of the question.


Here are the links for details.
Gabriel was very nice and did some testing. I would really appriciate if you join.

http://code.google.com/p/open9x/source/detail?r=2007
and also
http://code.google.com/p/open9x/source/detail?r=2027

[openFsguruh]

No more opinions... Topic too complicated?

[MikeB]

The following is an even worse situation:
CH05: +125% THR offset(125)
CH05: * CH05 switch(ELE)

Every time through the mixer, channel 5 is multiplied by itself resulting continuous end to end switching due to overflow. This is true on both open9x and er9x, I just tried it in C9X and eepe.

I would think that a simple test on the calculated channel value to make sure it is reasonable, say no more than +/- 500% would do. Given there are not reports from users saying this is a problem I don't think it really is a problem anyway.

Mike.

[openFsguruh]

Hi Mike,

good point. I think similar. No much complaints till now. So we can assume a reserve about 32x of 100%, that means we actually have +/- 3200% should be good enough.
Your example is kind of recursive use and will increase mix time as well, because it will try to resolve it, which couldn't be done.
I am totally confused by myself on this topic. I can find a solution to stop overflow but cost about 100 - 120 bytes flash. But calculation is wrong anyway just it hangs on 100% instead jumping to -100%.

So your opinion is, it is not worth bothering?

[MikeB]

I'm not sure it is worth bothering, maybe just a simple check is needed, I'll give it a little thought.

Mike.

[pmackenzie]

The following is an even worse situation:
CH05: +125% THR offset(125)
CH05: * CH05 switch(ELE)

Every time through the mixer, channel 5 is multiplied by itself resulting continuous end to end switching due to overflow. This is true on both open9x and er9x, I just tried it in C9X and eepe.

I would think that a simple test on the calculated channel value to make sure it is reasonable, say no more than +/- 500% would do. Given there are not reports from users saying this is a problem I don't think it really is a problem anyway.

Mike.

Interesting mix - totally useless, but interesting

Put the stick all the way up an in eePe at least it bounces back and forth. Closer to the middle and it ends up at zero eventually. Does the same on the radio.

Good news is that it does not seem to affect any of the other channels as far as I can tell. That would be the real danger of such an overflow.

[Kilrah]

I haven't looked deep enough in the code to be sure of what I'm saying, but:
If I understand well, mixer line results within a channel are stored in 32 bits. The problem is that once all mixers for that channel are processed, the result gets truncated to 16 bits. So, if this channel is reused and the whole operation repeated we could get an overflow. So you're suggesting to check for overflow, when exactly? When truncating, or during mixer calculation?

Another idea I would probably favor is to keep the result stored as 32bit until later, when passing the result to the limits. So instead of truncating a channel once all its mixers have been processed, keep the 32bit results until all mixers of all channels have been processed, then truncate it with an "y = x>0 ? max(x, 32767) : min(y,-32768)" or equivalent. This should cost 30 bytes of RAM and very little flash if I'm not mistaken, but at least would make things consistent.

But I'd be just as tempted to say "why bother" as I just can't find any real world use where the 16-bit values could overflow.

Your example is kind of recursive use and will increase mix time as well, because it will try to resolve it, which couldn't be done.

Don't forget we work in cycles, so while the value will evolve each cycle (what Mike says will run away) this won't hang the calculation. Using CH5 doesn't "call" the CH5 mixer again, it simply uses the previous value of CH5 (from the previous mixer run).

[MikeB]

As far as I can tell open9x and er9x both work the same way. An individual mix is calculated using a 16-bit integer (v). Finally, when applying the weight, it is converted to a 32-bit integer so we can multiply by the weight and divide by 100 without overflow.

Having obtained the value for that single mix, it is combined (+. * or =) with the 32-bit channel value, stored in the array chane[], still as 32 bits.
All we need to know is if the 32 bit result is too large.
In er9x, I calculated this result in dv, and have a single line:
*ptr = dv;
to store it in chans[].

The following is a simple test on dv to prevent overflow:

int8_t test ;
test = dv >> 24 ;
if ( ( test != -1) && ( test != 0 ) )
{
dv >>= 8 ;
}
*ptr = dv;

Just uses 20 bytes flash.

The code test = dv >> 24 ;
causes the top byte of dv to be copied.
The if statement check for overflow from 24 bits. If an overflow has occured, divide by 256 (done by just copying bytes). The result will still exceed a 16-bit integer, but will not be made too large later when more mixes are combined.

Finally store the (limited) value.

This should safely guard against overflow, and I don't really care whether the result is 15000 of 100000, it's just BIG (but now, not too BIG).

Mike.

[openFsguruh]

Hi Kilrah,

About 32bit change. I thought about this as well. Unfortunately the code cost is a lot more. The memory is mainly OK, because the mixline results are already stored in 32bit. It's just the beginning of the calculation.
Can check if you want. I have played a little bit with it. It would also increase the accuracy.
When exactly? Your guess is correct. When truncating to 16bits of course.
About the cycles, it's very confusing. The mixer has a dirty flag check. So if it needs input from a channel calculated later, it repeats the whole calculation. I have not understood all if else statements, but there is code to repeat the mixlines in case. All this counts for one mix calculation time, so you would see a higher value in Debug screen.

I am still confused by this check thing. Would you see a benefit at all, if it stays at 100% instead jumping to -100%. As far as I have seen from statements here, it is not really worth to bother?

[openFsguruh]

Hi Mike,

we should concentrate on the original question. It's may be confusing to code here.
So will you introduce something like that in Er9x?

Greetings!

Andreas

[MikeB]

On er9x, I don't do the looping looking for dirty channels, just a single pass through the mixers. This may increas latency if you refer to a later channel, but I call the mixer more frequently, waiting for 10mS to have passed when I call the menu code.
I have also just added in a 'start ppm channel' option that allows the user to choose which channel output is the first in the PPM stream. This allows the user to use the first few channels as virtual channels, then it should not be necessary to refer to later channels.

Mike.

[openFsguruh]

Up to now this is not much needed. Maybe just a warning if values gets too high is enough?
What about this? But I fear the code cost if even more.