code.vuplus.com Git - vuplus_xbmc/blob - xbmc/utils/TimeSmoother.cpp

   1 /*
   2  *      Copyright (C) 2011-2013 Team XBMC
   3  *      http://xbmc.org
   4  *
   5  *  This Program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2, or (at your option)
   8  *  any later version.
   9  *
  10  *  This Program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with XBMC; see the file COPYING.  If not, see
  17  *  <http://www.gnu.org/licenses/>.
  18  *
  19  */
  20
  21
  22 #include "TimeSmoother.h"
  23 #include <math.h>
  24 #include <limits>
  25 #include "utils/MathUtils.h"
  26
  27 using namespace std;
  28
  29 CTimeSmoother::CTimeSmoother()
  30 : m_diffs(num_diffs),
  31   m_periods(num_periods),
  32   m_period(0),
  33   m_lastFrameTime(0),
  34   m_prevIn(num_stamps),
  35   m_prevOut(num_stamps)
  36 {
  37 }
  38
  39 void CTimeSmoother::AddTimeStamp(unsigned int currentTime)
  40 {
  41   double diff = m_prevIn.size() ? currentTime - m_prevIn.back() : currentTime;
  42   if (diff)
  43     m_diffs.push_back(diff);
  44
  45   vector<double> bins;
  46   BinData(m_diffs, bins, 0.15, 2);
  47
  48   if (bins.size() && m_diffs.size() == num_diffs)
  49   {
  50     // have enough data to update our estimate
  51     vector<unsigned int> binMultipliers;
  52     GetGCDMultipliers(bins, binMultipliers, 2);
  53     assert(binMultipliers.size() == bins.size());
  54
  55     vector<unsigned int> intRepresentation;
  56     GetIntRepresentation(m_diffs, intRepresentation, bins, binMultipliers);
  57     assert(intRepresentation.size() == m_diffs.size());
  58
  59     double period = EstimatePeriod(m_diffs, intRepresentation);
  60
  61     // update our mean period
  62     if (fabs(period - m_period) > m_period*0.1)
  63     { // more than 10 % out - kill our previous running average
  64       m_periods.clear();
  65       m_period = 0;
  66     }
  67     if (m_periods.size() < m_periods.capacity())
  68       m_period = (m_period * m_periods.size() + period) / (m_periods.size() + 1);
  69     else
  70       m_period += (period - m_periods[0]) / m_periods.size();
  71     m_periods.push_back(period);
  72   }
  73   double frameTime = EstimateFrameTime(currentTime);
  74   m_prevIn.push_back(currentTime);
  75   m_prevOut.push_back(frameTime);
  76 }
  77
  78 unsigned int CTimeSmoother::GetNextFrameTime(unsigned int currentTime)
  79 {
  80   if (m_period)
  81   {
  82     double frameTime = EstimateFrameTime(currentTime);
  83     // ensure we jump at least 1 period ahead of the last time we were called
  84     if (frameTime < m_lastFrameTime + m_period)
  85       frameTime = m_lastFrameTime + m_period;
  86     // Return an unsigned int in ms, so wrap into that, and round.
  87     // Don't use MathUtils::round_int as that's restricted to -2^30..2^30
  88     if (frameTime >= UINT_MAX)
  89       frameTime = fmod(frameTime, UINT_MAX);
  90     m_lastFrameTime = frameTime;
  91     return (unsigned int)floor(frameTime + 0.5);
  92   }
  93   return currentTime;
  94 }
  95
  96 void CTimeSmoother::BinData(const boost::circular_buffer<double> &data, vector<double> &bins, const double threshold, const unsigned int minbinsize)
  97 {
  98   if (!data.size())
  99     return;
 100
 101   bins.clear();
 102   vector<unsigned int> counts;
 103
 104   for (boost::circular_buffer<double>::const_iterator i = data.begin(); i != data.end(); ++i)
 105   {
 106     bool found = false;
 107     for (unsigned int j = 0; j < bins.size(); ++j)
 108     {
 109       if (fabs(*i - bins[j]) < threshold*bins[j])
 110       {
 111         found = true;
 112         // update our bin mean and count
 113         bins[j] = (bins[j]*counts[j] + *i)/(counts[j]+1);
 114         counts[j]++;
 115         break;
 116       }
 117     }
 118     if (!found)
 119     {
 120       bins.push_back(*i);
 121       counts.push_back(1);
 122     }
 123   }
 124   if (minbinsize)
 125   {
 126     assert(counts.size() == bins.size());
 127     assert(counts.size());
 128     // filter out any bins that are not large enough (and any bins that aren't positive)
 129     for (unsigned int j = 0; j < counts.size(); )
 130     {
 131       if (counts[j] < minbinsize || bins[j] < 0.05)
 132       {
 133         bins.erase(bins.begin() + j);
 134         counts.erase(counts.begin() + j);
 135       }
 136       else
 137         j++;
 138     }
 139   }
 140 }
 141
 142 void CTimeSmoother::GetConvergent(double value, unsigned int &num, unsigned int &denom, const unsigned int maxnumden)
 143 {
 144   assert(value >= 1);
 145
 146   unsigned int old_n = 1, old_d = 0;
 147   num = 0; denom = 1;
 148
 149   // this while loop would typically be guaranteed to terminate as new_n, new_d are increasing non-negative
 150   // integers as long as f >= 1.  This in turn is guaranteed as f may never be zero as long as value > 1 and
 151   // value - f < 1.  Given that f = floor(value) this *should* always be true.
 152   // However, as f is unsigned int and thus range restricted, we can not guarantee this, and hence
 153   // break if value - f >= 1.
 154
 155   // In addition, just to be on the safe side we don't allow the loop to run forever ;)
 156   unsigned int maxLoops = 3 * maxnumden;
 157   while (maxLoops--)
 158   {
 159     unsigned int f = (unsigned int)floor(value);
 160     if (value - f >= 1)
 161       break; // value out of range of unsigned int
 162     unsigned int new_n = f * num   + old_n;
 163     unsigned int new_d = f * denom + old_d;
 164     if (min(new_n, new_d) > maxnumden)
 165       break;
 166     old_n = num; old_d = denom;
 167     num = new_n; denom = new_d;
 168     if ((double)f == value)
 169       break;
 170     value = 1/(value - f);
 171   }
 172   // ensure num, denom are positive
 173   assert(num > 0 && denom > 0);
 174 }
 175
 176 void CTimeSmoother::GetGCDMultipliers(const vector<double> &data, vector<unsigned int> &multipliers, const unsigned int maxminmult)
 177 {
 178   vector<double>::const_iterator i = std::min_element(data.begin(), data.end());
 179
 180   multipliers.clear();
 181
 182   vector<unsigned int> num, denom;
 183   for (vector<double>::const_iterator j = data.begin(); j != data.end(); ++j)
 184   {
 185     if (j != i)
 186     {
 187       unsigned int n, d;
 188       GetConvergent(*j / *i, n, d, maxminmult);
 189       num.push_back(n);
 190       denom.push_back(d);
 191     }
 192     else
 193     {
 194       num.push_back(1);
 195       denom.push_back(1);
 196     }
 197   }
 198   vector<unsigned int>::const_iterator k = std::max_element(num.begin(), num.end());
 199   for (unsigned int i = 0; i < num.size(); ++i)
 200     multipliers.push_back(denom[i] * (*k) / num[i]);
 201 }
 202
 203 void CTimeSmoother::GetIntRepresentation(const boost::circular_buffer<double> &data, vector<unsigned int> &intData, const vector<double> &bins, const vector<unsigned int> &intBins)
 204 {
 205   intData.clear();
 206   for (boost::circular_buffer<double>::const_iterator i = data.begin(); i != data.end(); ++i)
 207   {
 208     double min_r2 = numeric_limits<double>::max();
 209     unsigned int min_j = 0;
 210     for (unsigned int j = 0; j < bins.size(); ++j)
 211     {
 212       double d = MathUtils::round_int(*i/bins[j]);
 213       double r2 = (*i - bins[j]*d)*(*i - bins[j]*d);
 214       if (r2 < min_r2)
 215       {
 216         min_j = j;
 217         min_r2 = r2;
 218       }
 219     }
 220     intData.push_back(MathUtils::round_int(*i/bins[min_j])*intBins[min_j]);
 221   }
 222 }
 223
 224 double CTimeSmoother::EstimatePeriod(const boost::circular_buffer<double> &data, const vector<unsigned int> &intData)
 225 {
 226   double sxy = 0, sxx = 0;
 227   for (unsigned int i = 0; i < data.size(); ++i)
 228   {
 229     sxy += intData[i] * data[i];
 230     sxx += intData[i] * intData[i];
 231   }
 232   return sxy/sxx;
 233 }
 234
 235 double CTimeSmoother::EstimateFrameTime(unsigned int currentTime)
 236 {
 237   assert(m_prevIn.size() == m_prevOut.size());
 238   if (m_period)
 239   {
 240     vector<double> outTimes;
 241     for (unsigned int i = 0; i < m_prevIn.size(); ++i)
 242       outTimes.push_back(m_prevOut[i] + m_period * MathUtils::round_int((currentTime - m_prevIn[i]) / m_period));
 243     sort(outTimes.begin(), outTimes.end());
 244     double outTime = outTimes[(outTimes.size()-1)/2];
 245     if (outTime < m_prevOut.back() + m_period)
 246       outTime = m_prevOut.back() + m_period;
 247     return outTime;
 248   }
 249   return currentTime;
 250 }