From 0ea0e0694ecd5e8b626b8e8414d5c8f7107233a3 Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Fri, 9 May 2008 22:27:44 +0000 Subject: 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 --- src/pulsecore/time-smoother.c | 143 +++++++++++++++++++++++++----------------- src/pulsecore/time-smoother.h | 2 +- 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 */ -- cgit