-/* $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 paused;
+ pa_bool_t monotonic:1;
+ 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;
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;
}
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);
+ /* 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;
+ 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);
+
+ s->abc_valid = TRUE;
}
static void estimate(pa_smoother *s, pa_usec_t x, pa_usec_t *y, double *deriv) {
/* 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;
*deriv = s->dp;
} else {
+ double tx, ty;
- 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 */
-
- /* 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);
+ /* Ok, we're not yet on track, thus let's interpolate, and
+ * make sure that the first derivative is smooth */
- /* 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;
+ calc_abc(s);
- /* 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;
- }
+ tx = (double) x;
/* Move to origin */
- x -= s->ex;
+ tx -= (double) 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;
+ s->px = s->ex + s->adjust_time;
+ s->py = s->ry + (pa_usec_t) llrint(s->dp * (double) s->adjust_time);
s->abc_valid = FALSE;
+
+/* pa_log_debug("put(%llu | %llu) = %llu", (unsigned long long) (x + s->time_offset), (unsigned long long) x, (unsigned long long) y); */
}
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;
+ }
+
+/* pa_log_debug("get(%llu | %llu) = %llu", (unsigned long long) (x + s->time_offset), (unsigned long long) x, (unsigned long long) y); */
+
return y;
}
pa_assert(s);
s->time_offset = offset;
+
+/* pa_log_debug("offset(%llu)", (unsigned long long) offset); */
}
void pa_smoother_pause(pa_smoother *s, pa_usec_t x) {
if (s->paused)
return;
+/* pa_log_debug("pause(%llu)", (unsigned long long) x); */
+
s->paused = TRUE;
s->pause_time = x;
}
if (!s->paused)
return;
+ if (x < s->pause_time)
+ x = s->pause_time;
+
+/* pa_log_debug("resume(%llu)", (unsigned long long) x); */
+
s->paused = FALSE;
s->time_offset += x - s->pause_time;
}
+
+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;
+
+/* 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) llrint((double) y_delay / nde);
+}
+
+void pa_smoother_reset(pa_smoother *s) {
+ pa_assert(s);
+
+ s->n_history = 0;
+ s->abc_valid = FALSE;
+}