-/* $Id$ */
-
/***
This file is part of PulseAudio.
#include "time-smoother.h"
-#define HISTORY_MAX 50
+#define HISTORY_MAX 64
/*
* Implementation of a time smoothing algorithm to synchronize remote
struct pa_smoother {
pa_usec_t adjust_time, history_time;
- pa_bool_t monotonic;
pa_usec_t time_offset;
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;
- pa_bool_t abc_valid;
+ pa_bool_t abc_valid:1;
+
+ pa_bool_t monotonic:1;
+ pa_bool_t paused:1;
+ pa_bool_t smoothing:1; /* If FALSE we skip the polonyomial interpolation step */
- pa_bool_t paused;
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,
+ pa_bool_t smoothing,
+ unsigned min_history,
+ pa_usec_t time_offset,
+ pa_bool_t paused) {
+
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;
s->history_time = history_time;
- s->time_offset = 0;
+ s->min_history = min_history;
s->monotonic = monotonic;
+ s->smoothing = smoothing;
- s->px = s->py = 0;
- s->dp = 1;
-
- s->ex = s->ey = 0;
- s->de = 1;
-
- s->history_idx = 0;
- s->n_history = 0;
-
- s->last_y = 0;
-
- s->abc_valid = FALSE;
-
- s->paused = FALSE;
+ pa_smoother_reset(s, time_offset, paused);
return s;
}
pa_xfree(s);
}
+#define REDUCE(x) \
+ do { \
+ x = (x) % HISTORY_MAX; \
+ } while(FALSE)
+
+#define REDUCE_INC(x) \
+ do { \
+ x = ((x)+1) % HISTORY_MAX; \
+ } while(FALSE)
+
+
static void drop_old(pa_smoother *s, pa_usec_t x) {
- unsigned j;
- /* First drop items from history which are too old, but make sure
- * to always keep two entries in the history */
+ /* Drop items from history which are too old, but make sure to
+ * always keep min_history in the history */
- for (j = s->n_history; j > 2; j--) {
+ while (s->n_history > s->min_history) {
- if (s->history_x[s->history_idx] + s->history_time >= x) {
+ if (s->history_x[s->history_idx] + s->history_time >= x)
/* This item is still valid, and thus all following ones
* are too, so let's quit this loop */
break;
- }
/* Item is too old, let's drop it */
- s->history_idx ++;
- while (s->history_idx >= HISTORY_MAX)
- s->history_idx -= HISTORY_MAX;
+ REDUCE_INC(s->history_idx);
s->n_history --;
}
}
static void add_to_history(pa_smoother *s, pa_usec_t x, pa_usec_t y) {
- unsigned j;
+ unsigned j, i;
pa_assert(s);
+ /* First try to update an existing history entry */
+ i = s->history_idx;
+ for (j = s->n_history; j > 0; j--) {
+
+ if (s->history_x[i] == x) {
+ s->history_y[i] = y;
+ return;
+ }
+
+ REDUCE_INC(i);
+ }
+
+ /* Drop old entries */
drop_old(s, x);
/* Calculate position for new entry */
j = s->history_idx + s->n_history;
- while (j >= HISTORY_MAX)
- j -= HISTORY_MAX;
+ REDUCE(j);
/* Fill in entry */
s->history_x[j] = x;
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;
}
}
int64_t ax = 0, ay = 0, k, t;
double r;
- drop_old(s, x);
+ /* FIXME: Optimization: Jason Newton suggested that instead of
+ * going through the history on each iteration we could calculated
+ * avg_gradient() as we go.
+ *
+ * Second idea: it might make sense to weight history entries:
+ * more recent entries should matter more than old ones. */
+
+ /* 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;
for (j = s->n_history; j > 0; j--) {
- ax += s->history_x[i];
- ay += s->history_y[i];
+ ax += (int64_t) s->history_x[i];
+ ay += (int64_t) s->history_y[i];
c++;
- i++;
- while (i >= HISTORY_MAX)
- i -= HISTORY_MAX;
+ 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;
k += dx*dy;
t += dx*dx;
- i++;
- while (i >= HISTORY_MAX)
- i -= HISTORY_MAX;
+ REDUCE_INC(i);
}
- r = (double) k / t;
+ r = (double) k / (double) t;
+
+ 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)/ (double) kx - dp - (double) (2*de))) / (double) kx;
+ s->a = (dp/(double) kx - 2*s->b - de/(double) kx) / (double) (3*kx);
- return s->monotonic && r < 0 ? 0 : r;
+ s->abc_valid = TRUE;
}
static void estimate(pa_smoother *s, pa_usec_t x, pa_usec_t *y, double *deriv) {
pa_assert(y);
if (x >= s->px) {
+ /* Linear interpolation right from px */
int64_t t;
/* The requested point is right of the point where we wanted
* to be on track again, thus just linearly estimate */
- t = (int64_t) s->py + (int64_t) (s->dp * (x - s->px));
+ t = (int64_t) s->py + (int64_t) llrint(s->dp * (double) (x - s->px));
if (t < 0)
t = 0;
if (deriv)
*deriv = s->dp;
- } else {
+ } else if (x <= s->ex) {
+ /* Linear interpolation left from ex */
+ int64_t t;
- if (!s->abc_valid) {
- pa_usec_t ex, ey, px, py;
- int64_t kx, ky;
- double de, dp;
+ t = (int64_t) s->ey - (int64_t) llrint(s->de * (double) (s->ex - x));
- /* Ok, we're not yet on track, thus let's interpolate, and
- * make sure that the first derivative is smooth */
+ if (t < 0)
+ t = 0;
- /* 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 */
+ *y = (pa_usec_t) t;
- ex = s->ex; ey = s->ey;
- px = s->px; py = s->py;
- de = s->de; dp = s->dp;
+ if (deriv)
+ *deriv = s->de;
- pa_assert(ex < px);
+ } else {
+ /* Spline interpolation between ex and px */
+ double tx, ty;
- /* 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;
+ /* Ok, we're not yet on track, thus let's interpolate, and
+ * make sure that the first derivative is smooth */
- /* 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;
+ tx = (double) (x - s->ex);
/* Horner scheme */
- *y = (pa_usec_t) ((double) x * (s->c + (double) x * (s->b + (double) x * s->a)));
+ ty = (tx * (s->c + tx * (s->b + tx * s->a)));
/* Move back from origin */
- *y += s->ey;
+ ty += (double) s->ey;
+
+ *y = ty >= 0 ? (pa_usec_t) llrint(ty) : 0;
/* Horner scheme */
if (deriv)
- *deriv = s->c + ((double) x * (s->b*2 + (double) x * s->a*3));
+ *deriv = s->c + (tx * (s->b*2 + tx * s->a*3));
}
/* 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;
}
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);
- pa_assert(x >= s->time_offset);
/* Fix up x value */
if (s->paused)
x = s->pause_time;
- else
- x -= s->time_offset;
- pa_assert(x >= s->ex);
+ x = PA_LIKELY(x >= s->time_offset) ? x - s->time_offset : 0;
- /* 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;
+ is_new = x >= s->ex;
+
+ 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);
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;
+ if (s->smoothing) {
+ s->px = s->ex + s->adjust_time;
+ s->py = s->ry + (pa_usec_t) llrint(s->dp * (double) s->adjust_time);
+ } else {
+ s->px = s->ex;
+ s->py = s->ry;
+ }
s->abc_valid = FALSE;
+
+#ifdef DEBUG_DATA
+ pa_log_debug("%p, put(%llu | %llu) = %llu", s, (unsigned long long) (x + s->time_offset), (unsigned long long) x, (unsigned long long) y);
+#endif
}
pa_usec_t pa_smoother_get(pa_smoother *s, pa_usec_t x) {
pa_usec_t y;
pa_assert(s);
- pa_assert(x >= s->time_offset);
/* Fix up x value */
if (s->paused)
x = s->pause_time;
- else
- x -= s->time_offset;
- pa_assert(x >= s->ex);
+ x = PA_LIKELY(x >= s->time_offset) ? x - s->time_offset : 0;
+
+ if (s->monotonic)
+ if (x <= s->last_x)
+ x = s->last_x;
estimate(s, x, &y, NULL);
+
+ if (s->monotonic) {
+
+ /* Make sure the querier doesn't jump forth and back. */
+ s->last_x = x;
+
+ if (y < s->last_y)
+ y = s->last_y;
+ else
+ s->last_y = y;
+ }
+
+#ifdef DEBUG_DATA
+ pa_log_debug("%p, get(%llu | %llu) = %llu", s, (unsigned long long) (x + s->time_offset), (unsigned long long) x, (unsigned long long) y);
+#endif
+
return y;
}
pa_assert(s);
s->time_offset = offset;
+
+#ifdef DEBUG_DATA
+ pa_log_debug("offset(%llu)", (unsigned long long) offset);
+#endif
}
void pa_smoother_pause(pa_smoother *s, pa_usec_t x) {
if (s->paused)
return;
+#ifdef DEBUG_DATA
+ pa_log_debug("pause(%llu)", (unsigned long long) x);
+#endif
+
s->paused = TRUE;
s->pause_time = x;
}
-void pa_smoother_resume(pa_smoother *s, pa_usec_t x) {
+void pa_smoother_resume(pa_smoother *s, pa_usec_t x, pa_bool_t fix_now) {
pa_assert(s);
if (!s->paused)
return;
+ if (x < s->pause_time)
+ x = s->pause_time;
+
+#ifdef DEBUG_DATA
+ pa_log_debug("resume(%llu)", (unsigned long long) x);
+#endif
+
s->paused = FALSE;
s->time_offset += x - s->pause_time;
+
+ if (fix_now)
+ pa_smoother_fix_now(s);
+}
+
+void pa_smoother_fix_now(pa_smoother *s) {
+ pa_assert(s);
+
+ s->px = s->ex;
+ s->py = s->ry;
+}
+
+pa_usec_t pa_smoother_translate(pa_smoother *s, pa_usec_t x, pa_usec_t y_delay) {
+ pa_usec_t ney;
+ double nde;
+
+ pa_assert(s);
+
+ /* Fix up x value */
+ if (s->paused)
+ x = s->pause_time;
+
+ x = PA_LIKELY(x >= s->time_offset) ? x - s->time_offset : 0;
+
+ estimate(s, x, &ney, &nde);
+
+ /* 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;
+
+#ifdef DEBUG_DATA
+ pa_log_debug("translate(%llu) = %llu (%0.2f)", (unsigned long long) y_delay, (unsigned long long) ((double) y_delay / nde), nde);
+#endif
+
+ return (pa_usec_t) llrint((double) y_delay / nde);
+}
+
+void pa_smoother_reset(pa_smoother *s, pa_usec_t time_offset, pa_bool_t paused) {
+ pa_assert(s);
+
+ s->px = s->py = 0;
+ s->dp = 1;
+
+ s->ex = s->ey = s->ry = 0;
+ s->de = 1;
+
+ s->history_idx = 0;
+ s->n_history = 0;
+
+ s->last_y = s->last_x = 0;
+
+ s->abc_valid = FALSE;
+
+ s->paused = paused;
+ s->time_offset = s->pause_time = time_offset;
+
+#ifdef DEBUG_DATA
+ pa_log_debug("reset()");
+#endif
}