From 045c1d602dcba57868845ba3270510593c39480f Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Thu, 15 May 2008 23:34:41 +0000 Subject: merge glitch-free branch back into trunk git-svn-id: file:///home/lennart/svn/public/pulseaudio/trunk@2445 fefdeb5f-60dc-0310-8127-8f9354f1896f --- src/pulsecore/time-smoother.c | 233 +++++++++++++++++++++++++++--------------- 1 file changed, 152 insertions(+), 81 deletions(-) (limited to 'src/pulsecore/time-smoother.c') diff --git a/src/pulsecore/time-smoother.c b/src/pulsecore/time-smoother.c index 4cebded4..9b4be29f 100644 --- a/src/pulsecore/time-smoother.c +++ b/src/pulsecore/time-smoother.c @@ -34,7 +34,7 @@ #include "time-smoother.h" -#define HISTORY_MAX 50 +#define HISTORY_MAX 64 /* * Implementation of a time smoothing algorithm to synchronize remote @@ -61,7 +61,6 @@ struct pa_smoother { pa_usec_t adjust_time, history_time; - pa_bool_t monotonic; pa_usec_t time_offset; @@ -70,27 +69,34 @@ 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; 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; @@ -101,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; } @@ -122,39 +130,58 @@ void pa_smoother_free(pa_smoother* 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; @@ -164,8 +191,9 @@ 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; } } @@ -175,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; @@ -185,15 +215,10 @@ static double avg_gradient(pa_smoother *s, pa_usec_t x) { ay += 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; @@ -210,14 +235,45 @@ static double avg_gradient(pa_smoother *s, pa_usec_t x) { k += dx*dy; t += dx*dx; - i++; - while (i >= HISTORY_MAX) - i -= HISTORY_MAX; + REDUCE_INC(i); } r = (double) k / 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)/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) { @@ -242,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 */ - - /* 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; + /* 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; @@ -290,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; } @@ -303,23 +328,26 @@ 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); - pa_assert(x >= s->time_offset); /* Fix up x value */ if (s->paused) x = s->pause_time; - pa_assert(x >= s->time_offset); - x -= s->time_offset; + 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); @@ -328,28 +356,41 @@ 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; + +/* 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; - pa_assert(x >= s->time_offset); - x -= s->time_offset; - - pa_assert(x >= s->ex); + x = PA_LIKELY(x >= s->time_offset) ? x - s->time_offset : 0; 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; } @@ -357,6 +398,8 @@ void pa_smoother_set_time_offset(pa_smoother *s, pa_usec_t offset) { 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) { @@ -365,6 +408,8 @@ 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; } @@ -377,6 +422,32 @@ void pa_smoother_resume(pa_smoother *s, pa_usec_t x) { pa_assert(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) ((double) y_delay / nde); +} -- cgit