## [Code Review] DIY C Buffer Filter/Analysis Function

13 posts / 0 new
Author
Message

Hi,

I've a circular buffer presently holding up to 30 reads (period of a frequency). Occasionally some noise creeps in which I need to deal with prior to calculating the mean and co-efficient of variation, which in turn is used to mark whether the frequency is 'stable'. It would be great to have a few eyes go over what I came up with to see if there's any errors. The buffer fills at 10Hz.

```struct motionReadProto {
uint8_t outlier;
uint16_t value;
};

struct motionProto {
uint16_t mean;
uint8_t stable;
};

static struct motionReadProto *currentBuffer = &buffer;
volatile struct motionProto motion;

static uint32_t squareRootRounded(uint16_t op) {

uint32_t res = 0;
uint16_t one = 1u << 14; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type

// "one" starts at the highest power of four <= than the argument.
while (one > op) {
one >>= 2;
}

while (one != 0) {
if (op >= res + one) {
op = op - (res + one);
res = res +  2 * one;
}
res >>= 1;
one >>= 2;
}

/* Do arithmetic rounding to nearest integer */
if (op > res) {
res++;
}

return res;
}

if (! TIMER_INT_FLAG) {
return;
}

// move buffer
if (currentBuffer == &buffer[MOTION_BUFFER_COUNT-1]) {
currentBuffer = &buffer;
} else {
currentBuffer++;
}

// save result
currentBuffer->value = TIMER_CAPTURE_VALUE; // timer will clear int flag automatically

uint8_t i;

// mean
uint32_t mean = 0;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
if (buffer[i].value) {
mean += buffer[i].value;
}
}

// deltas
uint32_t delta = 0;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
if (buffer[i].value) {
uint16_t x = (buffer[i].value - (uint16_t) mean);
delta += x*x;
}
}

// standard deviation
uint16_t sd = squareRootRounded(delta);

// mark outliers
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
buffer[i].outlier = !buffer[i].value || (buffer[i].value < mean - 2*sd) || (buffer[i].value > mean + 2*sd)? 1:0;
}

// recompute mean and sd without outliers
mean = 0;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
if (! buffer[i].outlier) {
mean += buffer[i].value;
}
}

// deltas
delta = 0;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
if (! buffer[i].outlier) {
uint16_t x = (buffer[i].value - motion.mean);
delta += x*x;
}
}

// standard deviation
sd = squareRootRounded(delta);

// co-efficient of variation
uint8_t cov = motion.mean? ((sd*100) / motion.mean) : 0;

//outcome
motion.stable = motion.ready && cov < MOTION_STABILITY_MAX_COV? 1:0;
}```

Last Edited: Thu. Oct 15, 2020 - 06:35 PM

I don't know if you have to obey any coding standard, but regardless of this I have two comments.

1. I don't like the last line of code, this one under the comment //outcome. You should use parentheses to clearly indicate what is the condition in the conditional operator and to clearly indicate order of evaluation. The line above, this one under the comment // co-efficient of variation, is a good example of correct use of parentheses.

2. When you divide two integers, the result is always rounded down. In your code you probably need result rounded to the nearest integer. To get such result you need to add half of the divider to the divident prior to performing divide operation. For example, instead

` delta /= reads`

you should write:

` delta = (delta + reads / 2) / reads`

I would suggest starting with the source of the  "bad" data. Covering up bad data is a poor practice, at best. Better to figure WHY it is happening and how to correct it before it ever reaches the buffer,

Jim

Until Black Lives Matter, we do not have "All Lives Matter"!

snoopy33 wrote:
It would be great to have a few eyes go over what I came up with to see if there's any errors.
Failures?  (been tested?)

What I seek is defects in the sequence defect, fault, failure for I'm a creator of defects One defect stood out ... very near the bottom

`    uint8_t cov = motion.mean? ((sd*100) / motion.mean) : 0;`

has a sign issue.

There are several instances of precision loss that may or may not be an issue.

P.S.

Before posting, consider compile/interpret, a pass through your preferred linter, and, if one wants, a nominal test (the most frequent path though the code, sometimes nominal on one run-time isn't nominal on another run-time which is a hint of at least a lack of portability issue)

cling@GOREPL (Cling)

PC-lint Plus Online Demo - Gimpel Software - The Leader in Static Analysis for C and C++ with PC-lint Plus

"Dare to be naïve." - Buckminster Fuller

snoopy33 wrote:

`static uint32_t squareRootRounded(uint16_t op) {`

Why 32 bits for the square root of 16 bits? Surely the max it can be is 256 (if it's rounding up, or 255 if it isn't rounding up).

snoopy33 wrote:

`    motion.stable = motion.ready && cov < MOTION_STABILITY_MAX_COV? 1:0;`

You don't actually need the ternary op for this kind of thing, the result of the logical && can only be 0 or 1 (and is of type int).

So you can just say

motion.stable = motion.ready && cov < MOTION_STABILITY_MAX_COV;

But i expect it compiles to exactly the same code either way.

Could consider using bool for things like motion.stable and motion.ready assuming they are only ever 1 or 0 (true or false), more for making the intent of the code clearer than anything else.

gchapman wrote:
I don't see a sign issue, the value can only be between 0 and 100 (cov is a percentage of deviation from the mean).

I don't see a sign issue, the value can only be between 0 and 100 (cov is a percentage of deviation from the mean).

Last Edited: Fri. Oct 16, 2020 - 08:14 AM

MrKendo wrote:

snoopy33 wrote:

`static uint32_t squareRootRounded(uint16_t op) {`

Why 32 bits for the square root of 16 bits? Surely the max it can be is 256 (if it's rounding up, or 255 if it isn't rounding up).

snoopy33 wrote:

`    motion.stable = motion.ready && cov < MOTION_STABILITY_MAX_COV? 1:0;`

You don't actually need the ternary op for this kind of thing, the result of the logical && can only be 0 or 1 (and is of type int).

So you can just say

motion.stable = motion.ready && cov < MOTION_STABILITY_MAX_COV;

But i expect it compiles to exactly the same code either way.

Could consider using bool for things like motion.stable and motion.ready assuming they are only ever 1 or 0 (true or false), more for making the intent of the code clearer than anything else.

I didn't realise C would automatically infer a 1 or 0, excellent tip.

That squareRootRounded function was nicked from elsewhere, you're right though it should be a 32 bit input and a 16 bit return.

It's all been tested and working well. As stated the precision isn't perfect but it's a trade-off for speed or I'd be using floating points.

The CPU is running at 10MHz after prescaler, this code runs at 10Hz so one pass has 1MHz of processing available. It's the most expensive operation in the application but the lesser processing of the 1MHz it takes up the better.

Modified with improvements

```static uint16_t squareRootRounded(uint16_t op) {

uint32_t res = 0;
uint16_t one = 1u << 14; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type

// "one" starts at the highest power of four <= than the argument.
while (one > op) {
one >>= 2;
}

while (one != 0) {
if (op >= res + one) {
op -= res + one;
res +=  2 * one;
}
res >>= 1;
one >>= 2;
}

/* Do arithmetic rounding to nearest integer */
if (op > res) {
res++;
}

return res;
}

if (! TIMER_INT_FLAG) {
return;
}

// save result
currentBuffer->value = TIMER_CAPTURE_VALUE; // timer will clear int flag automatically

// move buffer
if (currentBuffer == &buffer[MOTION_BUFFER_COUNT-1]) {
currentBuffer = &buffer;
} else {
currentBuffer++;
return;
}
}

uint8_t i;

// mean
uint32_t mean = 0;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
if (buffer[i].value) {
mean += buffer[i].value;
}
}

// deltas
uint32_t delta = 0;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
if (buffer[i].value) {
uint16_t x = buffer[i].value - mean; // mean can't be greater than uint16_t at this point
delta += x*x;
}
}

// standard deviation
uint16_t sd = squareRootRounded(delta);

// mark outliers
sd *= 2;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
buffer[i].outlier = !buffer[i].value || buffer[i].value < (mean - sd) || buffer[i].value > (mean + sd);
}

// recompute mean and sd without outliers
mean = 0;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
if (! buffer[i].outlier) {
mean += buffer[i].value;
}
}

// deltas
delta = 0;
for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
if (! buffer[i].outlier) {
uint16_t x = buffer[i].value - motion.mean;
delta += x*x;
}
}

// standard deviation
sd = squareRootRounded(delta);

// co-efficient of variation
uint8_t cov = motion.mean? ((sd*100) / motion.mean) : 0;

//outcome
motion.stable = cov < MOTION_STABILITY_MAX_COV;
}```

Last Edited: Fri. Oct 16, 2020 - 09:07 AM
```    currentBuffer->value = TIMER_CAPTURE_VALUE; // timer will clear int flag automatically
```

The uppercase in this suggests a macro is being used and hence a fixed value but surely this is the variable input to the whole thing? If so then why are you using an all upper case name for a variable? Very misleading to the reader.

```    // move buffer
if (currentBuffer == &buffer[MOTION_BUFFER_COUNT-1]) {
currentBuffer = &buffer;
} else {
currentBuffer++;
}
```

It's probably just a personal thing but when doing circular buffers I would increment and wrap an array index not a pointer so it's more like:

```    // move buffer
if (idx == MOTION_BUFFER_COUNT-1) {
idx = 0;
} else {
idx++;
}
currentBuffer = buffer[idx];
```

YMMV.

snoopy33 wrote:

```    //outcome
motion.stable = motion.ready && cov < MOTION_STABILITY_MAX_COV? 1:0;
```

Wouldn't that be simpler & clearer as just

```    motion.stable = (cov < MOTION_STABILITY_MAX_COV) ? motion.ready : 0;
```

EDIT

and wouldn't you want some flag to say whether the value in motion.stable was valid ?

EDIT 2

Oh - is motion.stable supposed to be a bool ? (see #5)

This is where names such as is_stable, and is_ready could be clearer ...

Top Tips:

1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
Last Edited: Fri. Oct 16, 2020 - 08:57 AM

Sorry just to be clear not interested in any linting or personal preferences regarding brackets. I've been in the game too long to give a toss about such things. `TIMER_CAPTURE_VALUE`

Not a macro but a define for TMRB0 capture value.

`buffer[idx]`

Clawson, that's a more expensive as it has to be computed.

Original :

```    uint8_t cov = motion.mean? ((sd*100) / motion.mean) : 0;
```

Proposed :

```    uint8_t cov = motion.mean? ((sd*100U) / motion.mean) : 0;
```

"Dare to be naïve." - Buckminster Fuller

snoopy33 wrote:
...  or I'd be using floating points.
Fixed-point math may be available, is extended in C, may be a library for your preferred C compiler, can even be in C89, and is forthcoming for C++.

Libgcc (GNU Compiler Collection (GCC) Internals)

...

...

TR 18037: Embedded C | Project status and milestones

Is there a fixed-point implementation? | OpusFAQ - XiphWiki

"Dare to be naïve." - Buckminster Fuller