karlward / filter Goto Github PK

median() calls _orderedValues() in order to get a pointer to a newly allocated sorted copy of the sample buffer. When it returns, it looses that pointer and never frees the memory.

This creates a huge memory leak. I did an experiment with an Arduino Uno and a filter of size 5. Repeatedly calling median() makes the heap grow by 64 bytes per call, eventually crashing the Arduino.

The following seems to seal the leak:

diff --git a/Filter.cpp b/Filter.cpp
index 73b85a6..c18e049 100755
--- a/Filter.cpp
+++ b/Filter.cpp
@@ -167,6 +167,8 @@ long Filter::median() const {
     median = ((medianValues->peek(midpoint) + medianValues->peek(midpoint+1)) * 10) / 2;
     median = _longRound(median, 10); 
   }
+  medianValues->flush();
+  free(medianValues);
   return(median); 
 }
 

This method looks like a misguided attempt to have the integer division round to nearest rather than round towards zero. It involves both a 32-bit division and a 32-bit modulo operation, both of which are very expensive on AVR. Furthermore, it is used with a multiplier of 10, which is arbitrary and does not guarantee correct rounding in all circumstances. Edit: it does guarantee correct rounding as long as the multiplier is even.

A simpler and cheaper method is to add half the denominator before the division, i.e. replace p/q with (p+q/2)/q. Note that, if q is unsigned, q/2 is optimized by the compiler into a bit shift, which is extremely cheap. For example, in the computation of the mean, the scaling factor can be removed and the lines:

long mean = sum / _values.available();
mean = _longRound(mean, 10);
return(mean);

can then be replaced with:

return (sum + _values.available() / 2) / _values.available();

The same applies to the median.

The standard deviation is more tricky, as it uses not only an integer division but also a float to long conversion, both of which involve rounding. The easiest solution is to carry the division in floating point and add 0.5 before converting to long, i.e. remove the scaling and replace:

long stDev = sqrt(sum / denominator);
stDev = _longRound(stDev, 10); // round and undo that multiplier of 10
return(stDev); 

with:

return sqrt((float) sum / denominator) + 0.5;

The program

#include <Filter.h>

void setup() {
    Filter filter(3);
    filter.write(-3);
    filter.write(-5);
    filter.write(-7);
    Serial.begin(9600);
    Serial.print("mean(-3, -5, -7) = ");
    Serial.println(filter.mean());
}

void loop(){}

outputs

mean(-3, -5, -7) = 143165572

This is due to the (scaled) mean being computed as

long mean = sum / _values.available();

where sum is of type long and _values.available() is unsigned long. According to the C++ rules on usual arithmetic conversions, evaluating the above expression involves an implicit cast of sum to unsigned long, hence the wrap around.

The obvious fix is to change _values.available() to be of any type among long, int, short or unsigned short.