Array out of bounds access

[schugabe]

Hi!

I discovered an array out of bounds access in the file MultiWii.cpp

Code: Select all

rcCommand[THROTTLE] = lookupThrottleRC[tmp2] + (tmp-tmp2*100) * (lookupThrottleRC[tmp2+1]-lookupThrottleRC[tmp2]) / 100; // [0;1000] -> expo -> [conf.minthrottle;MAXTHROTTLE]

where lookupThrottleRC is declared as

Code: Select all

extern int16_t lookupThrottleRC[11];

As tmp2 can have the value 10 => lookupThrottleRC[tmp2+1] is invalid in this case.

I don't know if this has any unwanted consequences...

[Alexinparis]

Hi,
you're apparently right
when rcData[THROTTLE] reaches 2000, there is an overflow here.

[timecop]

It would be lovely if someone would explain the actual formula of what is being done there.

[sorenkuula]

It is a linear interpolation.
There is a throttle curve table lookupThrottleRC. This is used to transform throttle from RC to a different curve - but always such that more throttle in gets more throttle out. This is mostly something the heli pilots like to have, but maybe some multicopter people like it too. For example, to make it easier to fine tune throttle around the hover point.
The table is an array of out-values. tmp2 is calculated by taking the in-value and dividing it by something. If the division yields exactly an integer number n, then the outvalue is lookupThrottleRC[n]. If it is a non integer - consisting of an integer n plus a fraction f - then the above code will find the outvalue for n and the out value for n+1, and find the point on the line between them. That is (outvalue for n) + (outvalue for n+1 - outvalue for n) * f.
Well the * and / with 100 need some hmm investigation..
Regards Soren

[schugabe]

I did the same calculations as specified in the source code in a spreadsheet (see attachment). The basic implementation is correct but the missing last array element would be a problem when full throttle is the input. To solve this problem it is sufficient to increase the size of the array and fill it the same way as before.

expo graph

@timecop: If the cfg.thrExpo8 value can get larger than 100 (possible in baseflight cli config) the curve gets rather strange and starts to oscillate.

[itain]

a. Note that there is a redundant definition of MINCHECK and MAXCHECK:

Code: Select all

MultiWii.cpp:#define MINCHECK 1100
MultiWii.cpp:#define MAXCHECK 1900
MultiWii.h:#define MINCHECK 1100
MultiWii.h:#define MAXCHECK 1900

b. Those integer divisions by 100 are very inefficient. Please consider:

Code: Select all

  tmp = constrain(rcData[THROTTLE],MINCHECK,2000);
  tmp = (uint32_t)(tmp-MINCHECK)*2559/(2000-MINCHECK); // [MINCHECK;2000] -> [0;2559]
  tmp2 = tmp/256; // range [0;9]
  rcCommand[THROTTLE] = lookupThrottleRC[tmp2] + (tmp-tmp2*256) * (lookupThrottleRC[tmp2+1]-lookupThrottleRC[tmp2]) / 256; // [0;2559] -> expo -> [conf.minthrottle;MAXTHROTTLE]

The produced code is smaller. Not tested!

[schugabe]

With the suggested value of 2559 the resulting output is a bit different. With 2560 it is exactly the same.

Code: Select all

  tmp = (uint32_t)(tmp-MINCHECK)*2560/(2000-MINCHECK); // [MINCHECK;2000] -> [0;2560]

[itain]

@schugabe, are you comparing to SVN version r1591?
Ales changed the range from [0;1000] to [0;999] in order to fix the reported array out of bounds access. I'm following the same line by using a [0;2559] range.

[sismeiro]

a. Note that there is a redundant definition of MINCHECK and MAXCHECK:

Code: Select all

MultiWii.cpp:#define MINCHECK 1100
MultiWii.cpp:#define MAXCHECK 1900
MultiWii.h:#define MINCHECK 1100
MultiWii.h:#define MAXCHECK 1900

Hi,

One question. If we need to change one or both of this values, in which file the change will count?

Regards,
Luis Sismeiro

[itain]

These values should be defined only once and the right place is in MultiWii.h.

[schugabe]

@schugabe, are you comparing to SVN version r1591?
Ales changed the range from [0;1000] to [0;999] in order to fix the reported array out of bounds access. I'm following the same line by using a [0;2559] range.

No I was not comparing with r1591. I compared it with the old intended behavior. The maximum throttle output is reduced with this fix e.g. with the old version and expo=0 the output for full throttle (2000 input) was 5000. In r1591 the corresponding output is 4993. If expo=100 the old result was also 5000 with the new version it is 4983.

With your suggested optimization the result for expo=0 is 4997 and expo=1 yields 4993. So the difference is smaller.

I think that the expo function should not modify the endpoint so I would prefer to add the missing array entry... if the memory saving argument wins it should at least be documented in the source code.