1/*
2 *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#include "webrtc/modules/video_coding/main/source/internal_defines.h"
12#include "webrtc/modules/video_coding/main/source/rtt_filter.h"
13
14#include <math.h>
15#include <stdlib.h>
16#include <string.h>
17
18namespace webrtc {
19
20VCMRttFilter::VCMRttFilter()
21    : _filtFactMax(35),
22      _jumpStdDevs(2.5),
23      _driftStdDevs(3.5),
24      _detectThreshold(kMaxDriftJumpCount) {
25    Reset();
26}
27
28VCMRttFilter&
29VCMRttFilter::operator=(const VCMRttFilter& rhs)
30{
31    if (this != &rhs)
32    {
33        _gotNonZeroUpdate = rhs._gotNonZeroUpdate;
34        _avgRtt = rhs._avgRtt;
35        _varRtt = rhs._varRtt;
36        _maxRtt = rhs._maxRtt;
37        _filtFactCount = rhs._filtFactCount;
38        _jumpCount = rhs._jumpCount;
39        _driftCount = rhs._driftCount;
40        memcpy(_jumpBuf, rhs._jumpBuf, sizeof(_jumpBuf));
41        memcpy(_driftBuf, rhs._driftBuf, sizeof(_driftBuf));
42    }
43    return *this;
44}
45
46void
47VCMRttFilter::Reset()
48{
49    _gotNonZeroUpdate = false;
50    _avgRtt = 0;
51    _varRtt = 0;
52    _maxRtt = 0;
53    _filtFactCount = 1;
54    _jumpCount = 0;
55    _driftCount = 0;
56    memset(_jumpBuf, 0, kMaxDriftJumpCount);
57    memset(_driftBuf, 0, kMaxDriftJumpCount);
58}
59
60void
61VCMRttFilter::Update(uint32_t rttMs)
62{
63    if (!_gotNonZeroUpdate)
64    {
65        if (rttMs == 0)
66        {
67            return;
68        }
69        _gotNonZeroUpdate = true;
70    }
71
72    // Sanity check
73    if (rttMs > 3000)
74    {
75        rttMs = 3000;
76    }
77
78    double filtFactor = 0;
79    if (_filtFactCount > 1)
80    {
81        filtFactor = static_cast<double>(_filtFactCount - 1) / _filtFactCount;
82    }
83    _filtFactCount++;
84    if (_filtFactCount > _filtFactMax)
85    {
86        // This prevents filtFactor from going above
87        // (_filtFactMax - 1) / _filtFactMax,
88        // e.g., _filtFactMax = 50 => filtFactor = 49/50 = 0.98
89        _filtFactCount = _filtFactMax;
90    }
91    double oldAvg = _avgRtt;
92    double oldVar = _varRtt;
93    _avgRtt = filtFactor * _avgRtt + (1 - filtFactor) * rttMs;
94    _varRtt = filtFactor * _varRtt + (1 - filtFactor) *
95                (rttMs - _avgRtt) * (rttMs - _avgRtt);
96    _maxRtt = VCM_MAX(rttMs, _maxRtt);
97    if (!JumpDetection(rttMs) || !DriftDetection(rttMs))
98    {
99        // In some cases we don't want to update the statistics
100        _avgRtt = oldAvg;
101        _varRtt = oldVar;
102    }
103}
104
105bool
106VCMRttFilter::JumpDetection(uint32_t rttMs)
107{
108    double diffFromAvg = _avgRtt - rttMs;
109    if (fabs(diffFromAvg) > _jumpStdDevs * sqrt(_varRtt))
110    {
111        int diffSign = (diffFromAvg >= 0) ? 1 : -1;
112        int jumpCountSign = (_jumpCount >= 0) ? 1 : -1;
113        if (diffSign != jumpCountSign)
114        {
115            // Since the signs differ the samples currently
116            // in the buffer is useless as they represent a
117            // jump in a different direction.
118            _jumpCount = 0;
119        }
120        if (abs(_jumpCount) < kMaxDriftJumpCount)
121        {
122            // Update the buffer used for the short time
123            // statistics.
124            // The sign of the diff is used for updating the counter since
125            // we want to use the same buffer for keeping track of when
126            // the RTT jumps down and up.
127            _jumpBuf[abs(_jumpCount)] = rttMs;
128            _jumpCount += diffSign;
129        }
130        if (abs(_jumpCount) >= _detectThreshold)
131        {
132            // Detected an RTT jump
133            ShortRttFilter(_jumpBuf, abs(_jumpCount));
134            _filtFactCount = _detectThreshold + 1;
135            _jumpCount = 0;
136        }
137        else
138        {
139            return false;
140        }
141    }
142    else
143    {
144        _jumpCount = 0;
145    }
146    return true;
147}
148
149bool
150VCMRttFilter::DriftDetection(uint32_t rttMs)
151{
152    if (_maxRtt - _avgRtt > _driftStdDevs * sqrt(_varRtt))
153    {
154        if (_driftCount < kMaxDriftJumpCount)
155        {
156            // Update the buffer used for the short time
157            // statistics.
158            _driftBuf[_driftCount] = rttMs;
159            _driftCount++;
160        }
161        if (_driftCount >= _detectThreshold)
162        {
163            // Detected an RTT drift
164            ShortRttFilter(_driftBuf, _driftCount);
165            _filtFactCount = _detectThreshold + 1;
166            _driftCount = 0;
167        }
168    }
169    else
170    {
171        _driftCount = 0;
172    }
173    return true;
174}
175
176void
177VCMRttFilter::ShortRttFilter(uint32_t* buf, uint32_t length)
178{
179    if (length == 0)
180    {
181        return;
182    }
183    _maxRtt = 0;
184    _avgRtt = 0;
185    for (uint32_t i=0; i < length; i++)
186    {
187        if (buf[i] > _maxRtt)
188        {
189            _maxRtt = buf[i];
190        }
191        _avgRtt += buf[i];
192    }
193    _avgRtt = _avgRtt / static_cast<double>(length);
194}
195
196uint32_t
197VCMRttFilter::RttMs() const
198{
199    return static_cast<uint32_t>(_maxRtt + 0.5);
200}
201
202}
203