[Code Review] DIY C Buffer Filter/Analysis Function

Go To Last Post
13 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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;
    uint8_t ready;
};

static struct motionReadProto buffer[MOTION_BUFFER_COUNT];
static struct motionReadProto *currentBuffer = &buffer[0];
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;
}

void MOTION_Task (void) {

    if (! TIMER_INT_FLAG) {
        return;
    }

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

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

    uint8_t i;
    uint8_t reads = 0;

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

    // 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;
        }
    }
    delta /= reads;

    // 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;
    reads = 0;
    for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
        if (! buffer[i].outlier) {
            mean += buffer[i].value;
            ++reads;
        }
    }
    motion.mean = mean / reads;

    // 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;
        }
    }
    delta /= reads;

    // 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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 3

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"!

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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 cheeky

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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;
}

void MOTION_Task (void) {
    
    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[0];
        motion.ready = 1;
    } else {
        currentBuffer++;
        if (!motion.ready) {
            return;
        }
    }
    
    uint8_t i;
    uint8_t reads = 0;

    // mean
    uint32_t mean = 0;
    for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
        if (buffer[i].value) {
            mean += buffer[i].value;
            ++reads;  
        }
    }
    mean /= reads;
    
    // 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;
        }
    }
    delta /= reads;
    
    // 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;
    reads = 0;
    for (i=0; i < MOTION_BUFFER_COUNT; ++i) {
        if (! buffer[i].outlier) {
            mean += buffer[i].value;
            ++reads;  
        }
    }
    motion.mean = mean / reads;
    
    // 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;
        }
    }
    
    delta /= reads;
     
    // 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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
    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[0];
        motion.ready = 1;
    } 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;
        motion.ready = 1;
    } else {
        idx++;
    }
    currentBuffer = buffer[idx];

YMMV.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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. wink

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.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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)

...

Fixed-point fractional library routines:

...

TR 18037: Embedded C | Project status and milestones

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

Composition of Arithmetic Types (C++)
 

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

In the outlier calculations it is probably prudent to check for reads=0 before the divide and handle it in a reasonable way.

C: i = "told you so";