Linear Interpolation. How to implement this algorithm in C ? (Python version is given)
Question: There exists one very good linear interpolation method. It performs linear
interpolation requiring **at most one multiply per output sample**. I found
its description in a third edition of Understanding DSP by Lyons. This method
involves a special hold buffer. Given a number of samples to be inserted
between any two input samples, it produces output points using linear
interpolation. Here, I have rewritten this algorithm using Python:

    
    
    temp1, temp2 = 0, 0
    iL = 1.0 / L
    for i in x:
       hold = [i-temp1] * L
       temp1 = i
       for j in hold:
          temp2 += j
          y.append(temp2 *iL)
    

where x contains input samples, L is a number of points to be inserted, y will
contain output samples.

My question is **how to implement such algorithm in ANSI C in a most effective
way** , e.g. is it possible to avoid the second loop?

NOTE: presented Python code is just to understand how this algorithm works.

UPDATE: here is an example how it works in Python:

    
    
    x=[]
    y=[]
    hold=[]
    num_points=20
    points_inbetween = 2
    
    temp1,temp2=0,0
    
    for i in range(num_points):
       x.append( sin(i*2.0*pi * 0.1) )
    
    L = points_inbetween
    iL = 1.0/L
    for i in x:
       hold = [i-temp1] * L
       temp1 = i
       for j in hold:
          temp2 += j
          y.append(temp2 * iL)
    

Let's say x=[.... 10, 20, 30 ....]. Then, if L=1, it will produce [... 10, 15,
20, 25, 30 ...]


Answer: ## Interpolation in the sense of "signal sample rate increase"

... or i call it, "upsampling" (wrong term, probably. disclaimer: i have not
read Lyons'). I just had to understand what the code does and then re-write it
for readability. As given it has couple of problems:

a) it is inefficient - two loops is ok but it does multiplication for every
single output item; also it uses intermediary lists(`hold`), generates result
with `append` (small beer)

b) it interpolates wrong the first interval; it generates fake data in front
of the first element. Say we have multiplier=5 and seq=[20,30] - it will
generate [0,4,8,12,16,20,22,24,28,30] instead of [20,22,24,26,28,30].

So here is the algorithm in form of a generator:

    
    
    def upsampler(seq, multiplier):
        if seq:
            step = 1.0 / multiplier
            y0 = seq[0];
            yield y0
            for y in seq[1:]:
                dY = (y-y0) * step
                for i in range(multiplier-1):
                    y0 += dY;
                    yield y0
                y0 = y;
                yield y0
    

Ok and now for some tests:

    
    
    >>> list(upsampler([], 3))  # this is just the same as [Y for Y in upsampler([], 3)]
    []
    >>> list(upsampler([1], 3))
    [1]
    >>> list(upsampler([1,2], 3))
    [1, 1.3333333333333333, 1.6666666666666665, 2]
    >>> from math import sin, pi
    >>> seq = [sin(2.0*pi * i/10) for i in range(20)]
    >>> seq
    [0.0, 0.58778525229247314, 0.95105651629515353, 0.95105651629515364, 0.58778525229247325, 1.2246063538223773e-016, -0.58778525229247303, -0.95105651629515353, -0.95105651629515364, -0.58778525229247336, -2.4492127076447545e-016, 0.58778525229247214, 0.95105651629515353, 0.95105651629515364, 0.58778525229247336, 3.6738190614671318e-016, -0.5877852522924728, -0.95105651629515342, -0.95105651629515375, -0.58778525229247347]
    >>> list(upsampler(seq, 2))
    [0.0, 0.29389262614623657, 0.58778525229247314, 0.76942088429381328, 0.95105651629515353, 0.95105651629515364, 0.95105651629515364, 0.7694208842938135, 0.58778525229247325, 0.29389262614623668, 1.2246063538223773e-016, -0.29389262614623646, -0.58778525229247303, -0.76942088429381328, -0.95105651629515353, -0.95105651629515364, -0.95105651629515364, -0.7694208842938135, -0.58778525229247336, -0.29389262614623679, -2.4492127076447545e-016, 0.29389262614623596, 0.58778525229247214, 0.76942088429381283, 0.95105651629515353, 0.95105651629515364, 0.95105651629515364, 0.7694208842938135, 0.58778525229247336, 0.29389262614623685, 3.6738190614671318e-016, -0.29389262614623618, -0.5877852522924728, -0.76942088429381306, -0.95105651629515342, -0.95105651629515364, -0.95105651629515375, -0.76942088429381361, -0.58778525229247347]
    

And here is my translation to C, fit into Kratz's fn template:

    
    
    /**
     *
     * @param src caller supplied array with data
     * @param src_len len of src
     * @param steps to interpolate
     * @param dst output param will be filled with (src_len - 1) * steps + 1 samples
     */
    float* linearInterpolation(float* src, int src_len, int steps, float* dst)
    {
        float step, y0, dy;
        float *src_end;
        if (src_len > 0) {
            step = 1.0 / steps;
            for (src_end = src+src_len; *dst++ = y0 = *src++, src < src_end; ) {
                dY = (*src - y0) * step;
                for (int i=steps; i>0; i--) {
                    *dst++ = y0 += dY;
                }
            }
        }
    }
    

Please note the C snippet is "typed but never compiled or run", so there might
be syntax errors, off-by-1 errors etc. But overall the idea is there.

