Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Delay Locked Loop based time filter
  3.  * Copyright (c) 2009 Samalyse
  4.  * Copyright (c) 2009 Michael Niedermayer
  5.  * Author: Olivier Guilyardi <olivier samalyse com>
  6.  *         Michael Niedermayer <michaelni gmx at>
  7.  *
  8.  * This file is part of FFmpeg.
  9.  *
  10.  * FFmpeg is free software; you can redistribute it and/or
  11.  * modify it under the terms of the GNU Lesser General Public
  12.  * License as published by the Free Software Foundation; either
  13.  * version 2.1 of the License, or (at your option) any later version.
  14.  *
  15.  * FFmpeg is distributed in the hope that it will be useful,
  16.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18.  * Lesser General Public License for more details.
  19.  *
  20.  * You should have received a copy of the GNU Lesser General Public
  21.  * License along with FFmpeg; if not, write to the Free Software
  22.  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  23.  */
  24.  
  25. #include "libavutil/common.h"
  26. #include "libavutil/mem.h"
  27. #include "config.h"
  28. #include "timefilter.h"
  29.  
  30. struct TimeFilter {
  31.     // Delay Locked Loop data. These variables refer to mathematical
  32.     // concepts described in: http://www.kokkinizita.net/papers/usingdll.pdf
  33.     double cycle_time;
  34.     double feedback2_factor;
  35.     double feedback3_factor;
  36.     double clock_period;
  37.     int count;
  38. };
  39.  
  40. /* 1 - exp(-x) using a 3-order power series */
  41. static double qexpneg(double x)
  42. {
  43.     return 1 - 1 / (1 + x * (1 + x / 2 * (1 + x / 3)));
  44. }
  45.  
  46. TimeFilter *ff_timefilter_new(double time_base,
  47.                               double period,
  48.                               double bandwidth)
  49. {
  50.     TimeFilter *self       = av_mallocz(sizeof(TimeFilter));
  51.     double o               = 2 * M_PI * bandwidth * period * time_base;
  52.  
  53.     if (!self)
  54.         return NULL;
  55.  
  56.     self->clock_period     = time_base;
  57.     self->feedback2_factor = qexpneg(M_SQRT2 * o);
  58.     self->feedback3_factor = qexpneg(o * o) / period;
  59.     return self;
  60. }
  61.  
  62. void ff_timefilter_destroy(TimeFilter *self)
  63. {
  64.     av_freep(&self);
  65. }
  66.  
  67. void ff_timefilter_reset(TimeFilter *self)
  68. {
  69.     self->count = 0;
  70. }
  71.  
  72. double ff_timefilter_update(TimeFilter *self, double system_time, double period)
  73. {
  74.     self->count++;
  75.     if (self->count == 1) {
  76.         self->cycle_time = system_time;
  77.     } else {
  78.         double loop_error;
  79.         self->cycle_time += self->clock_period * period;
  80.         loop_error = system_time - self->cycle_time;
  81.  
  82.         self->cycle_time   += FFMAX(self->feedback2_factor, 1.0 / self->count) * loop_error;
  83.         self->clock_period += self->feedback3_factor * loop_error;
  84.     }
  85.     return self->cycle_time;
  86. }
  87.  
  88. double ff_timefilter_eval(TimeFilter *self, double delta)
  89. {
  90.     return self->cycle_time + self->clock_period * delta;
  91. }
  92.  
  93. #ifdef TEST
  94. #include "libavutil/lfg.h"
  95. #define LFG_MAX ((1LL << 32) - 1)
  96.  
  97. int main(void)
  98. {
  99.     AVLFG prng;
  100.     double n0, n1;
  101. #define SAMPLES 1000
  102.     double ideal[SAMPLES];
  103.     double samples[SAMPLES];
  104.     double samplet[SAMPLES];
  105.     for (n0 = 0; n0 < 40; n0 = 2 * n0 + 1) {
  106.         for (n1 = 0; n1 < 10; n1 = 2 * n1 + 1) {
  107.             double best_error = 1000000000;
  108.             double bestpar0   = n0 ? 1 : 100000;
  109.             double bestpar1   = 1;
  110.             int better, i;
  111.  
  112.             av_lfg_init(&prng, 123);
  113.             for (i = 0; i < SAMPLES; i++) {
  114.                 samplet[i] = 10 + i + (av_lfg_get(&prng) < LFG_MAX/2 ? 0 : 0.999);
  115.                 ideal[i]   = samplet[i] + n1 * i / (1000);
  116.                 samples[i] = ideal[i] + n0 * (av_lfg_get(&prng) - LFG_MAX / 2) / (LFG_MAX * 10LL);
  117.                 if(i && samples[i]<samples[i-1])
  118.                     samples[i]=samples[i-1]+0.001;
  119.             }
  120.  
  121.             do {
  122.                 double par0, par1;
  123.                 better = 0;
  124.                 for (par0 = bestpar0 * 0.8; par0 <= bestpar0 * 1.21; par0 += bestpar0 * 0.05) {
  125.                     for (par1 = bestpar1 * 0.8; par1 <= bestpar1 * 1.21; par1 += bestpar1 * 0.05) {
  126.                         double error   = 0;
  127.                         TimeFilter *tf = ff_timefilter_new(1, par0, par1);
  128.                         if (!tf) {
  129.                             printf("Could not alocate memory for timefilter.\n");
  130.                             exit(1);
  131.                         }
  132.                         for (i = 0; i < SAMPLES; i++) {
  133.                             double filtered;
  134.                             filtered = ff_timefilter_update(tf, samples[i], i ? (samplet[i] - samplet[i-1]) : 1);
  135.                             if(filtered < 0 || filtered > 1000000000)
  136.                                 printf("filter is unstable\n");
  137.                             error   += (filtered - ideal[i]) * (filtered - ideal[i]);
  138.                         }
  139.                         ff_timefilter_destroy(tf);
  140.                         if (error < best_error) {
  141.                             best_error = error;
  142.                             bestpar0   = par0;
  143.                             bestpar1   = par1;
  144.                             better     = 1;
  145.                         }
  146.                     }
  147.                 }
  148.             } while (better);
  149. #if 0
  150.             double lastfil = 9;
  151.             TimeFilter *tf = ff_timefilter_new(1, bestpar0, bestpar1);
  152.             for (i = 0; i < SAMPLES; i++) {
  153.                 double filtered;
  154.                 filtered = ff_timefilter_update(tf, samples[i], 1);
  155.                 printf("%f %f %f %f\n", i - samples[i] + 10, filtered - samples[i],
  156.                        samples[FFMAX(i, 1)] - samples[FFMAX(i - 1, 0)], filtered - lastfil);
  157.                 lastfil = filtered;
  158.             }
  159.             ff_timefilter_destroy(tf);
  160. #else
  161.             printf(" [%12f %11f %9f]", bestpar0, bestpar1, best_error);
  162. #endif
  163.         }
  164.         printf("\n");
  165.     }
  166.     return 0;
  167. }
  168. #endif
  169.