make sure the smoother code can deal with incoming data that is out-of-order; start smoothing only when we have at least a configurable number of entries in our history

git-svn-id: file:///home/lennart/svn/public/pulseaudio/branches/glitch-free@2390 fefdeb5f-60dc-0310-8127-8f9354f1896f

2 files changed, 86 insertions, 59 deletions

diff --git a/src/pulsecore/time-smoother.c b/src/pulsecore/time-smoother.c
index 97e32b73..9b4be29f 100644
--- a/src/pulsecore/time-smoother.c
+++ b/src/pulsecore/time-smoother.c
@@ -69,13 +69,14 @@ struct pa_smoother {
 
     pa_usec_t ex, ey;     /* Point e, which we estimated before and need to smooth to */
     double de;            /* Gradient we estimated for point e */
+    pa_usec_t ry;         /* The original y value for ex */
 
                           /* History of last measurements */
     pa_usec_t history_x[HISTORY_MAX], history_y[HISTORY_MAX];
     unsigned history_idx, n_history;
 
     /* To even out for monotonicity */
-    pa_usec_t last_y;
+    pa_usec_t last_y, last_x;
 
     /* Cached parameters for our interpolation polynomial y=ax^3+b^2+cx */
     double a, b, c;
@@ -85,13 +86,17 @@ struct pa_smoother {
     pa_bool_t paused:1;
 
     pa_usec_t pause_time;
+
+    unsigned min_history;
 };
 
-pa_smoother* pa_smoother_new(pa_usec_t adjust_time, pa_usec_t history_time, pa_bool_t monotonic) {
+pa_smoother* pa_smoother_new(pa_usec_t adjust_time, pa_usec_t history_time, pa_bool_t monotonic, unsigned min_history) {
     pa_smoother *s;
 
     pa_assert(adjust_time > 0);
     pa_assert(history_time > 0);
+    pa_assert(min_history >= 2);
+    pa_assert(min_history <= HISTORY_MAX);
 
     s = pa_xnew(pa_smoother, 1);
     s->adjust_time = adjust_time;
@@ -102,18 +107,20 @@ pa_smoother* pa_smoother_new(pa_usec_t adjust_time, pa_usec_t history_time, pa_b
     s->px = s->py = 0;
     s->dp = 1;
 
-    s->ex = s->ey = 0;
+    s->ex = s->ey = s->ry = 0;
     s->de = 1;
 
     s->history_idx = 0;
     s->n_history = 0;
 
-    s->last_y = 0;
+    s->last_y = s->last_x = 0;
 
     s->abc_valid = FALSE;
 
     s->paused = FALSE;
 
+    s->min_history = min_history;
+
     return s;
 }
 
@@ -137,9 +144,9 @@ void pa_smoother_free(pa_smoother* s) {
 static void drop_old(pa_smoother *s, pa_usec_t x) {
 
     /* Drop items from history which are too old, but make sure to
-     * always keep two entries in the history */
+     * always keep min_history in the history */
 
-    while (s->n_history > 2) {
+    while (s->n_history > s->min_history) {
 
         if (s->history_x[s->history_idx] + s->history_time >= x)
             /* This item is still valid, and thus all following ones
@@ -184,7 +191,7 @@ static void add_to_history(pa_smoother *s, pa_usec_t x, pa_usec_t y) {
     s->n_history ++;
 
     /* And make sure we don't store more entries than fit in */
-    if (s->n_history >= HISTORY_MAX) {
+    if (s->n_history > HISTORY_MAX) {
         s->history_idx += s->n_history - HISTORY_MAX;
         REDUCE(s->history_idx);
         s->n_history = HISTORY_MAX;
@@ -196,7 +203,9 @@ static double avg_gradient(pa_smoother *s, pa_usec_t x) {
     int64_t ax = 0, ay = 0, k, t;
     double r;
 
-    drop_old(s, x);
+    /* Too few measurements, assume gradient of 1 */
+    if (s->n_history < s->min_history)
+        return 1;
 
     /* First, calculate average of all measurements */
     i = s->history_idx;
@@ -209,10 +218,7 @@ static double avg_gradient(pa_smoother *s, pa_usec_t x) {
         REDUCE_INC(i);
     }
 
-    /* Too few measurements, assume gradient of 1 */
-    if (c < 2)
-        return 1;
-
+    pa_assert(c >= s->min_history);
     ax /= c;
     ay /= c;
 
@@ -237,6 +243,39 @@ static double avg_gradient(pa_smoother *s, pa_usec_t x) {
     return (s->monotonic && r < 0) ? 0 : r;
 }
 
+static void calc_abc(pa_smoother *s) {
+    pa_usec_t ex, ey, px, py;
+    int64_t kx, ky;
+    double de, dp;
+
+    pa_assert(s);
+
+    if (s->abc_valid)
+        return;
+
+    /* We have two points: (ex|ey) and (px|py) with two gradients at
+     * these points de and dp. We do a polynomial
+     * interpolation of degree 3 with these 6 values */
+
+    ex = s->ex; ey = s->ey;
+    px = s->px; py = s->py;
+    de = s->de; dp = s->dp;
+
+    pa_assert(ex < px);
+
+    /* To increase the dynamic range and symplify calculation, we
+     * move these values to the origin */
+    kx = (int64_t) px - (int64_t) ex;
+    ky = (int64_t) py - (int64_t) ey;
+
+    /* Calculate a, b, c for y=ax^3+bx^2+cx */
+    s->c = de;
+    s->b = (((double) (3*ky)/kx - dp - 2*de)) / kx;
+    s->a = (dp/kx - 2*s->b - de/kx) / (3*kx);
+
+    s->abc_valid = TRUE;
+}
+
 static void estimate(pa_smoother *s, pa_usec_t x, pa_usec_t *y, double *deriv) {
     pa_assert(s);
     pa_assert(y);
@@ -259,36 +298,10 @@ static void estimate(pa_smoother *s, pa_usec_t x, pa_usec_t *y, double *deriv) {
 
     } else {
 
-        if (!s->abc_valid) {
-            pa_usec_t ex, ey, px, py;
-            int64_t kx, ky;
-            double de, dp;
+        /* Ok, we're not yet on track, thus let's interpolate, and
+         * make sure that the first derivative is smooth */
 
-            /* Ok, we're not yet on track, thus let's interpolate, and
-             * make sure that the first derivative is smooth */
-
-            /* We have two points: (ex|ey) and (px|py) with two gradients
-             * at these points de and dp. We do a polynomial interpolation
-             * of degree 3 with these 6 values */
-
-            ex = s->ex; ey = s->ey;
-            px = s->px; py = s->py;
-            de = s->de; dp = s->dp;
-
-            pa_assert(ex < px);
-
-            /* To increase the dynamic range and symplify calculation, we
-             * move these values to the origin */
-            kx = (int64_t) px - (int64_t) ex;
-            ky = (int64_t) py - (int64_t) ey;
-
-            /* Calculate a, b, c for y=ax^3+b^2+cx */
-            s->c = de;
-            s->b = (((double) (3*ky)/kx - dp - 2*de)) / kx;
-            s->a = (dp/kx - 2*s->b - de/kx) / (3*kx);
-
-            s->abc_valid = TRUE;
-        }
+        calc_abc(s);
 
         /* Move to origin */
         x -= s->ex;
@@ -307,11 +320,6 @@ static void estimate(pa_smoother *s, pa_usec_t x, pa_usec_t *y, double *deriv) {
     /* Guarantee monotonicity */
     if (s->monotonic) {
 
-        if (*y < s->last_y)
-            *y = s->last_y;
-        else
-            s->last_y = *y;
-
         if (deriv && *deriv < 0)
             *deriv = 0;
     }
@@ -320,6 +328,7 @@ static void estimate(pa_smoother *s, pa_usec_t x, pa_usec_t *y, double *deriv) {
 void pa_smoother_put(pa_smoother *s, pa_usec_t x, pa_usec_t y) {
     pa_usec_t ney;
     double nde;
+    pa_bool_t is_new;
 
     pa_assert(s);
 
@@ -329,12 +338,16 @@ void pa_smoother_put(pa_smoother *s, pa_usec_t x, pa_usec_t y) {
 
     x = PA_LIKELY(x >= s->time_offset) ? x - s->time_offset : 0;
 
-    pa_assert(x >= s->ex);
+    is_new = x >= s->ex;
 
-    /* First, we calculate the position we'd estimate for x, so that
-     * we can adjust our position smoothly from this one */
-    estimate(s, x, &ney, &nde);
-    s->ex = x; s->ey = ney; s->de = nde;
+    if (is_new) {
+        /* First, we calculate the position we'd estimate for x, so that
+         * we can adjust our position smoothly from this one */
+        estimate(s, x, &ney, &nde);
+        s->ex = x; s->ey = ney; s->de = nde;
+
+        s->ry = y;
+    }
 
     /* Then, we add the new measurement to our history */
     add_to_history(s, x, y);
@@ -343,8 +356,8 @@ void pa_smoother_put(pa_smoother *s, pa_usec_t x, pa_usec_t y) {
     s->dp = avg_gradient(s, x);
 
     /* And calculate when we want to be on track again */
-    s->px = x + s->adjust_time;
-    s->py = y + s->dp *s->adjust_time;
+    s->px = s->ex + s->adjust_time;
+    s->py = s->ry + s->dp *s->adjust_time;
 
     s->abc_valid = FALSE;
 
@@ -361,10 +374,21 @@ pa_usec_t pa_smoother_get(pa_smoother *s, pa_usec_t x) {
         x = s->pause_time;
 
     x = PA_LIKELY(x >= s->time_offset) ? x - s->time_offset : 0;
-    pa_assert(x >= s->ex);
 
     estimate(s, x, &y, NULL);
 
+    if (s->monotonic) {
+
+        /* Make sure the querier doesn't jump forth and back. */
+        pa_assert(x >= s->last_x);
+        s->last_x = x;
+
+        if (y < s->last_y)
+            y = s->last_y;
+        else
+            s->last_y = y;
+    }
+
 /*     pa_log_debug("get(%llu | %llu) = %llu", (unsigned long long) (x + s->time_offset), (unsigned long long) x, (unsigned long long) y); */
 
     return y;
@@ -416,11 +440,14 @@ pa_usec_t pa_smoother_translate(pa_smoother *s, pa_usec_t x, pa_usec_t y_delay)
 
     x = PA_LIKELY(x >= s->time_offset) ? x - s->time_offset : 0;
 
-    pa_assert(x >= s->ex);
-
     estimate(s, x, &ney, &nde);
 
-/*     pa_log_debug("translate(%llu) = %llu (%0.2f)", (unsigned long long) y_delay, (unsigned long long) ((double) y_delay / s->dp), s->dp); */
+    /* Play safe and take the larger gradient, so that we wakeup
+     * earlier when this is used for sleeping */
+    if (s->dp > nde)
+        nde = s->dp;
+
+/*     pa_log_debug("translate(%llu) = %llu (%0.2f)", (unsigned long long) y_delay, (unsigned long long) ((double) y_delay / nde), nde); */
 
-    return (pa_usec_t) ((double) y_delay / s->dp);
+    return (pa_usec_t) ((double) y_delay / nde);
 }
diff --git a/src/pulsecore/time-smoother.h b/src/pulsecore/time-smoother.h
index 85d9f0fd..b301b48c 100644
--- a/src/pulsecore/time-smoother.h
+++ b/src/pulsecore/time-smoother.h
@@ -29,7 +29,7 @@
 
 typedef struct pa_smoother pa_smoother;
 
-pa_smoother* pa_smoother_new(pa_usec_t x_adjust_time, pa_usec_t x_history_time, pa_bool_t monotonic);
+pa_smoother* pa_smoother_new(pa_usec_t x_adjust_time, pa_usec_t x_history_time, pa_bool_t monotonic, unsigned min_history);
 void pa_smoother_free(pa_smoother* s);
 
 /* Adds a new value to our dataset. x = local/system time, y = remote time */