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 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;
}
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
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;
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;
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);
} 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;
/* 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);
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);
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;
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;
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);
}