libs/ardour/ardour/interpolation.h

   1 #include <math.h>
   2 #include <samplerate.h>
   3
   4 #include "ardour/types.h"
   5
   6 #ifndef __interpolation_h__
   7 #define __interpolation_h__
   8
   9 namespace ARDOUR {
  10
  11 class Interpolation {
  12  protected:
  13      double   _speed, _target_speed;
  14
  15      // the idea is that when the speed is not 1.0, we have to
  16      // interpolate between samples and then we have to store where we thought we were.
  17      // rather than being at sample N or N+1, we were at N+0.8792922
  18      std::vector<double> phase;
  19
  20
  21  public:
  22      Interpolation () { _speed = 1.0; _target_speed = 1.0; }
  23
  24      void set_speed (double new_speed)          { _speed = new_speed; _target_speed = new_speed; }
  25      void set_target_speed (double new_speed)   { _target_speed = new_speed; }
  26
  27      double target_speed()          const { return _target_speed; }
  28      double speed()                 const { return _speed; }
  29
  30      void add_channel_to (int input_buffer_size, int output_buffer_size) { phase.push_back (0.0); }
  31      void remove_channel_from () { phase.pop_back (); }
  32
  33      void reset () {
  34          for (size_t i = 0; i <= phase.size(); i++) {
  35               phase[i] = 0.0;
  36           }
  37      }
  38 };
  39
  40 // 40.24 fixpoint math
  41 #define FIXPOINT_ONE 0x1000000
  42
  43 class FixedPointLinearInterpolation : public Interpolation {
  44     protected:
  45     /// speed in fixed point math
  46     uint64_t      phi;
  47
  48     /// target speed in fixed point math
  49     uint64_t      target_phi;
  50
  51     std::vector<uint64_t> last_phase;
  52
  53     // Fixed point is just an integer with an implied scaling factor.
  54     // In 40.24 the scaling factor is 2^24 = 16777216,
  55     // so a value of 10*2^24 (in integer space) is equivalent to 10.0.
  56     //
  57     // The advantage is that addition and modulus [like x = (x + y) % 2^40]
  58     // have no rounding errors and no drift, and just require a single integer add.
  59     // (swh)
  60
  61     static const int64_t fractional_part_mask  = 0xFFFFFF;
  62     static const Sample  binary_scaling_factor = 16777216.0f;
  63
  64     public:
  65
  66         FixedPointLinearInterpolation () : phi (FIXPOINT_ONE), target_phi (FIXPOINT_ONE) {}
  67
  68         void set_speed (double new_speed) {
  69             target_phi = (uint64_t) (FIXPOINT_ONE * fabs(new_speed));
  70             phi = target_phi;
  71         }
  72
  73         uint64_t get_phi() { return phi; }
  74         uint64_t get_target_phi() { return target_phi; }
  75         uint64_t get_last_phase() { assert(last_phase.size()); return last_phase[0]; }
  76         void set_last_phase(uint64_t phase) { assert(last_phase.size()); last_phase[0] = phase; }
  77
  78         void add_channel_to (int input_buffer_size, int output_buffer_size);
  79         void remove_channel_from ();
  80
  81         nframes_t interpolate (int channel, nframes_t nframes, Sample* input, Sample* output);
  82         void reset ();
  83 };
  84
  85 class LinearInterpolation : public Interpolation {
  86  protected:
  87
  88  public:
  89      nframes_t interpolate (int channel, nframes_t nframes, Sample* input, Sample* output);
  90 };
  91
  92
  93 #define MAX_PERIOD_SIZE 4096
  94 /**
  95  * @class SplineInterpolation
  96  *
  97  * @brief interpolates using cubic spline interpolation over an input period
  98  *
  99  * Splines are piecewise cubic functions between each samples,
 100  * where the cubic polynomials' values, first and second derivatives are equal
 101  * on each sample point.
 102  *
 103  * Those conditions are equivalent of solving the linear system of equations
 104  * defined by the matrix equation (all indices are zero-based):
 105  *  A * M = d
 106  *
 107  * where A has (n-2) rows and (n-2) columns
 108  *
 109  *  [ 4 1 0 0 ... 0 0 0 0 ]   [ M[1]   ]   [ 6*y[0] - 12*y[1] + 6*y[2] ]
 110  *  [ 1 4 1 0 ... 0 0 0 0 ]   [ M[2]   ]   [ 6*y[1] - 12*y[2] + 6*y[3] ]
 111  *  [ 0 1 4 1 ... 0 0 0 0 ]   [ M[3]   ]   [ 6*y[2] - 12*y[3] + 6*y[4] ]
 112  *  [ 0 0 1 4 ... 0 0 0 0 ]   [ M[4]   ]   [ 6*y[3] - 12*y[4] + 6*y[5] ]
 113  *            ...           *            =            ...
 114  *  [ 0 0 0 0 ... 4 1 0 0 ]   [ M[n-5] ]   [ 6*y[n-6]- 12*y[n-5] + 6*y[n-4] ]
 115  *  [ 0 0 0 0 ... 1 4 1 0 ]   [ M[n-4] ]   [ 6*y[n-5]- 12*y[n-4] + 6*y[n-3] ]
 116  *  [ 0 0 0 0 ... 0 1 4 1 ]   [ M[n-3] ]   [ 6*y[n-4]- 12*y[n-3] + 6*y[n-2] ]
 117  *  [ 0 0 0 0 ... 0 0 1 4 ]   [ M[n-2] ]   [ 6*y[n-3]- 12*y[n-2] + 6*y[n-1] ]
 118  *
 119  *  For our purpose we use natural splines which means the boundary coefficients
 120  *  M[0] = M[n-1] = 0
 121  *
 122  *  The interpolation polynomial in the i-th interval then has the form
 123  *  p_i(x) = a3 (x - i)^3 + a2 (x - i)^2 + a1 (x - i) + a0
 124  *         = ((a3 * (x - i) + a2) * (x - i) + a1) * (x - i) + a0
 125  *     where
 126  *  a3 = (M[i+1] - M[i]) / 6
 127  *  a2 = M[i] / 2
 128  *  a1 = y[i+1] - y[i] - M[i+1]/6 - M[i]/3
 129  *  a0 = y[i]
 130  *
 131  *  We solve the system by LU-factoring the matrix A:
 132  *  A = L * U:
 133  *
 134  *  [ 4 1 0 0 ... 0 0 0 0 ]   [ 1    0    0    0   ... 0      0      0      0 ]   [ m[0] 1    0    0   ... 0      0      0      ]
 135  *  [ 1 4 1 0 ... 0 0 0 0 ]   [ l[0] 1    0    0   ... 0      0      0      0 ]   [ 0    m[1] 1    0   ... 0      0      0      ]
 136  *  [ 0 1 4 1 ... 0 0 0 0 ]   [ 0    l[1] 1    0   ... 0      0      0      0 ]   [ 0    0    m[2] 1   ... 0      0      0      ]
 137  *  [ 0 0 1 4 ... 0 0 0 0 ]   [ 0    0    l[2] 1   ... 0      0      0      0 ]                        ...
 138  *            ...           =                     ...                          *  [ 0    0    0    0   ... 0      0      0      ]
 139  *  [ 0 0 0 0 ... 4 1 0 0 ]   [ 0    0    0    0   ... 1      0      0      0 ]   [ 0    0    0    0   ... 1      0      0      ]
 140  *  [ 0 0 0 0 ... 1 4 1 0 ]   [ 0    0    0    0   ... l[n-6] 1      0      0 ]   [ 0    0    0    0   ... m[n-5] 1      0      ]
 141  *  [ 0 0 0 0 ... 0 1 4 1 ]   [ 0    0    0    0   ... 0      l[n-5] 1      0 ]   [ 0    0    0    0   ... 0      m[n-4] 1      ]
 142  *  [ 0 0 0 0 ... 0 0 1 4 ]   [ 0    0    0    0   ... 0      0      l[n-4] 1 ]   [ 0    0    0    0   ... 0      0      m[n-3] ]
 143  *
 144  *  where the l[i] and m[i] can be precomputed.
 145  *
 146  *  Then we solve the system A * M = d by first solving the system
 147  *    L * t = d
 148  *  and then
 149  *    R * M = t
 150  */
 151 class SplineInterpolation : public Interpolation {
 152  protected:
 153     double l[MAX_PERIOD_SIZE], m[MAX_PERIOD_SIZE];
 154
 155  public:
 156     SplineInterpolation();
 157     nframes_t interpolate (int channel, nframes_t nframes, Sample* input, Sample* output);
 158 };
 159
 160 class LibSamplerateInterpolation : public Interpolation {
 161  protected:
 162     std::vector<SRC_STATE*>  state;
 163     std::vector<SRC_DATA*>   data;
 164
 165     int        error;
 166
 167     void reset_state ();
 168
 169  public:
 170         LibSamplerateInterpolation ();
 171         ~LibSamplerateInterpolation ();
 172
 173         void   set_speed (double new_speed);
 174         void   set_target_speed (double new_speed)   {}
 175         double speed ()                        const { return _speed;      }
 176
 177         void add_channel_to (int input_buffer_size, int output_buffer_size);
 178         void remove_channel_from ();
 179
 180         nframes_t interpolate (int channel, nframes_t nframes, Sample* input, Sample* output);
 181         void reset() { reset_state (); }
 182 };
 183
 184 } // namespace ARDOUR
 185
 186 #endif