Non-recursive filter to smoothen saw tooth wave

Question

I'm currently writing some of my first assembly code for a new project, I am applying a small non-recursive filter algorithm to some saw tooth wave data held in memory, in order to blunt the edges.

Using thumb2 instruction set on a cortex m3.

The algorithm being used is:

y[0] = x[-2]/8 + x[-1]/8 + x[0]/4 + x[1]/8 + x[2]/8

I have spent a long time looking at my code but cannot seem to optimize it any further. The Assembly code I have written is in a loop for the length of data and I have applied the algorithm as so:

  LDMIA r0,{r5-r9}     ; get the next 5 data values to be filtered
  ADD r5,r5,r9         ; sum x[-2] with x[2]
  ADD r6,r6,r8         ; sum x[-1] with x[1]
  ADD r9,r5,r6         ; sum x[-2]+x[2] with x[-1]+x[1]
  ADD r7,r7,r9,LSR #1  ; sum x[0] with (x[-2]+x[2]+x[-1]+x[1])/2
  MOV r7,r7,LSR #2     ; form (x[0] + (x[-2]+x[-1]+x[1]+x[2])/2)/4
  STR r7,[r3],#4       ; save calculated filtered value
  ADD r0,r0,#4         ; move pointer address forward
  SUBS r4,r4,#1        ; decrement loop counter

Can any one see anywhere I could have better optimized this?

Full Code if needed

Answer 1

You need to realize that as you are passing over the input, you will be dividing each input by 8 four times and dividing each input by 4 once. You will also calculate the sum of each adjacent input twice. We can try to get rid of this redundancy.

First lets rewrite the filter:

y[0] = x[-2]/8 + x[-1]/8 + x[0]/4 + x[1]/8 + x[2]/8

like so:

y[0] = (x[-2] + x[-1] + x[0] + x[1] + x[2])/8 + x[0]/8 + (1 if x[0] odd, 0 otherwise)

Multiply both sides by 8:
8*y[0] = (x[-2] + x[-1] + x[0] + x[1] + x[2]) + x[0] + 8*(x[0]&1)

Assuming integers, if the input is floating point, just skipp the odd/even bit.

Notice how you now have a sliding sum? That's effective to compute.

I'm not well versed in assembly but I can give you pseudo C-code which you can translate to assembly:

void computeSample(int slidingSum, int midSample){
   return (slidingSum + midSample + (midSample & 1) * 8)/8;
}

void filter(int *input, int *output, int len) {
    const int width = 2;

    if (len < width*2 + 1) { return; }

    int slidingSum = 0;
    for (int i = 0; i < width*2 + 1; ++i) {
        slidingSum += input[i];
    }

    output[width] = computeSample(slidingSum, input[width]);
    for (int x0 = width + 1; x0 < len - width; ++x0) {
        slidingSum -= input[x0 - (width+1)];
        slidingSum += input[x0 + width];
        output[x0] = computeSample(slidingSum, input[x0]);
    }
}

You need to figure out how to handle the edges of the signal (repeating, zero extending, no-data etc).

Hope this helps!