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      ~Interpolation () { phase.clear(); }
  24
  25      void set_speed (double new_speed)          { _speed = new_speed; _target_speed = new_speed; }
  26      void set_target_speed (double new_speed)   { _target_speed = new_speed; }
  27
  28      double target_speed()          const { return _target_speed; }
  29      double speed()                 const { return _speed; }
  30
  31      void add_channel_to (int input_buffer_size, int output_buffer_size) { phase.push_back (0.0); }
  32      void remove_channel_from () { phase.pop_back (); }
  33
  34      void reset () {
  35          for (size_t i = 0; i <= phase.size(); i++) {
  36               phase[i] = 0.0;
  37           }
  38      }
  39 };
  40
  41 // 40.24 fixpoint math
  42 #define FIXPOINT_ONE 0x1000000
  43
  44 class FixedPointLinearInterpolation : public Interpolation {
  45     protected:
  46     /// speed in fixed point math
  47     uint64_t      phi;
  48
  49     /// target speed in fixed point math
  50     uint64_t      target_phi;
  51
  52     std::vector<uint64_t> last_phase;
  53
  54     // Fixed point is just an integer with an implied scaling factor.
  55     // In 40.24 the scaling factor is 2^24 = 16777216,
  56     // so a value of 10*2^24 (in integer space) is equivalent to 10.0.
  57     //
  58     // The advantage is that addition and modulus [like x = (x + y) % 2^40]
  59     // have no rounding errors and no drift, and just require a single integer add.
  60     // (swh)
  61
  62     static const int64_t fractional_part_mask  = 0xFFFFFF;
  63     static const Sample  binary_scaling_factor = 16777216.0f;
  64
  65     public:
  66
  67         FixedPointLinearInterpolation () : phi (FIXPOINT_ONE), target_phi (FIXPOINT_ONE) {}
  68
  69         void set_speed (double new_speed) {
  70             target_phi = (uint64_t) (FIXPOINT_ONE * fabs(new_speed));
  71             phi = target_phi;
  72         }
  73
  74         uint64_t get_phi() { return phi; }
  75         uint64_t get_target_phi() { return target_phi; }
  76         uint64_t get_last_phase() { assert(last_phase.size()); return last_phase[0]; }
  77         void set_last_phase(uint64_t phase) { assert(last_phase.size()); last_phase[0] = phase; }
  78
  79         void add_channel_to (int input_buffer_size, int output_buffer_size);
  80         void remove_channel_from ();
  81
  82         nframes_t interpolate (int channel, nframes_t nframes, Sample* input, Sample* output);
  83         void reset ();
  84 };
  85
  86 class LinearInterpolation : public Interpolation {
  87  protected:
  88
  89  public:
  90      nframes_t interpolate (int channel, nframes_t nframes, Sample* input, Sample* output);
  91 };
  92
  93
  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 = L(UM) = d by first solving the system
 147  *    L * t = d
 148  *
 149  *    [ 1    0    0    0   ... 0      0      0      0 ]    [ t[0]   ]    [ 6*y[0] - 12*y[1] + 6*y[2] ]
 150  *    [ l[0] 1    0    0   ... 0      0      0      0 ]    [ t[1]   ]    [ 6*y[1] - 12*y[2] + 6*y[3] ]
 151  *    [ 0    l[1] 1    0   ... 0      0      0      0 ]    [ t[2]   ]    [ 6*y[2] - 12*y[3] + 6*y[4] ]
 152  *    [ 0    0    l[2] 1   ... 0      0      0      0 ]    [ t[3]   ]    [ 6*y[3] - 12*y[4] + 6*y[5] ]
 153  *                        ...                           *             =             ...
 154  *    [ 0    0    0    0   ... 1      0      0      0 ]    [ t[n-6] ]    [ 6*y[n-6]- 12*y[n-5] + 6*y[n-4] ]
 155  *    [ 0    0    0    0   ... l[n-6] 1      0      0 ]    [ t[n-5] ]    [ 6*y[n-5]- 12*y[n-4] + 6*y[n-3] ]
 156  *    [ 0    0    0    0   ... 0      l[n-5] 1      0 ]    [ t[n-4] ]    [ 6*y[n-4]- 12*y[n-3] + 6*y[n-2] ]
 157  *    [ 0    0    0    0   ... 0      0      l[n-4] 1 ]    [ t[n-3] ]    [ 6*y[n-3]- 12*y[n-2] + 6*y[n-1] ]
 158  *
 159  *
 160  *  and then
 161  *    U * M = t
 162  *
 163  *  [ m[0] 1    0    0   ... 0      0      0      ]   [ M[1]   ]    [ t[0]   ]
 164  *  [ 0    m[1] 1    0   ... 0      0      0      ]   [ M[2]   ]    [ t[1]   ]
 165  *  [ 0    0    m[2] 1   ... 0      0      0      ]   [ M[3]   ]    [ t[2]   ]
 166  *                       ...                          [ M[4]   ]    [ t[3]   ]
 167  *  [ 0    0    0    0   ... 0      0      0      ] *            =
 168  *  [ 0    0    0    0   ... 1      0      0      ]   [ M[n-5] ]    [ t[n-6] ]
 169  *  [ 0    0    0    0   ... m[n-5] 1      0      ]   [ M[n-4] ]    [ t[n-5] ]
 170  *  [ 0    0    0    0   ... 0      m[n-4] 1      ]   [ M[n-3] ]    [ t[n-4] ]
 171  *  [ 0    0    0    0   ... 0      0      m[n-3] ]   [ M[n-2] ]    [ t[n-3] ]
 172  *
 173  */
 174 class SplineInterpolation : public Interpolation {
 175  protected:
 176     double _l[19], _m[20];
 177
 178     inline double l(nframes_t i) {  return (i >= 19) ? _l[18] : _l[i]; }
 179     inline double m(nframes_t i) {  return (i >= 20) ? _m[19] : _m[i]; }
 180
 181  public:
 182     SplineInterpolation();
 183     nframes_t interpolate (int channel, nframes_t nframes, Sample* input, Sample* output);
 184 };
 185
 186 class LibSamplerateInterpolation : public Interpolation {
 187  protected:
 188     std::vector<SRC_STATE*>  state;
 189     std::vector<SRC_DATA*>   data;
 190
 191     int        error;
 192
 193     void reset_state ();
 194
 195  public:
 196         LibSamplerateInterpolation ();
 197         ~LibSamplerateInterpolation ();
 198
 199         void   set_speed (double new_speed);
 200         void   set_target_speed (double new_speed)   {}
 201         double speed ()                        const { return _speed;      }
 202
 203         void add_channel_to (int input_buffer_size, int output_buffer_size);
 204         void remove_channel_from ();
 205
 206         nframes_t interpolate (int channel, nframes_t nframes, Sample* input, Sample* output);
 207         void reset() { reset_state (); }
 208 };
 209
 210 } // namespace ARDOUR
 211
 212 #endif