1/*
2 *  Copyright (c) 2012 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#ifndef WEBRTC_MODULES_VIDEO_CODING_MAIN_SOURCE_JITTER_BUFFER_H_
12#define WEBRTC_MODULES_VIDEO_CODING_MAIN_SOURCE_JITTER_BUFFER_H_
13
14#include <list>
15#include <map>
16#include <set>
17#include <vector>
18
19#include "webrtc/base/constructormagic.h"
20#include "webrtc/modules/interface/module_common_types.h"
21#include "webrtc/modules/video_coding/main/interface/video_coding.h"
22#include "webrtc/modules/video_coding/main/interface/video_coding_defines.h"
23#include "webrtc/modules/video_coding/main/source/decoding_state.h"
24#include "webrtc/modules/video_coding/main/source/inter_frame_delay.h"
25#include "webrtc/modules/video_coding/main/source/jitter_buffer_common.h"
26#include "webrtc/modules/video_coding/main/source/jitter_estimator.h"
27#include "webrtc/system_wrappers/interface/critical_section_wrapper.h"
28#include "webrtc/typedefs.h"
29
30namespace webrtc {
31
32enum VCMNackMode {
33  kNack,
34  kNoNack
35};
36
37// forward declarations
38class Clock;
39class EventFactory;
40class EventWrapper;
41class VCMFrameBuffer;
42class VCMPacket;
43class VCMEncodedFrame;
44
45typedef std::list<VCMFrameBuffer*> UnorderedFrameList;
46
47struct VCMJitterSample {
48  VCMJitterSample() : timestamp(0), frame_size(0), latest_packet_time(-1) {}
49  uint32_t timestamp;
50  uint32_t frame_size;
51  int64_t latest_packet_time;
52};
53
54class TimestampLessThan {
55 public:
56  bool operator() (const uint32_t& timestamp1,
57                   const uint32_t& timestamp2) const {
58    return IsNewerTimestamp(timestamp2, timestamp1);
59  }
60};
61
62class FrameList
63    : public std::map<uint32_t, VCMFrameBuffer*, TimestampLessThan> {
64 public:
65  void InsertFrame(VCMFrameBuffer* frame);
66  VCMFrameBuffer* FindFrame(uint32_t timestamp) const;
67  VCMFrameBuffer* PopFrame(uint32_t timestamp);
68  VCMFrameBuffer* Front() const;
69  VCMFrameBuffer* Back() const;
70  int RecycleFramesUntilKeyFrame(FrameList::iterator* key_frame_it,
71      UnorderedFrameList* free_frames);
72  int CleanUpOldOrEmptyFrames(VCMDecodingState* decoding_state,
73      UnorderedFrameList* free_frames);
74  void Reset(UnorderedFrameList* free_frames);
75};
76
77class VCMJitterBuffer {
78 public:
79  VCMJitterBuffer(Clock* clock,
80                  EventFactory* event_factory);
81  virtual ~VCMJitterBuffer();
82
83  // Makes |this| a deep copy of |rhs|.
84  void CopyFrom(const VCMJitterBuffer& rhs);
85
86  // Initializes and starts jitter buffer.
87  void Start();
88
89  // Signals all internal events and stops the jitter buffer.
90  void Stop();
91
92  // Returns true if the jitter buffer is running.
93  bool Running() const;
94
95  // Empty the jitter buffer of all its data.
96  void Flush();
97
98  // Get the number of received frames, by type, since the jitter buffer
99  // was started.
100  std::map<FrameType, uint32_t> FrameStatistics() const;
101
102  // The number of packets discarded by the jitter buffer because the decoder
103  // won't be able to decode them.
104  int num_not_decodable_packets() const;
105
106  // Gets number of packets discarded by the jitter buffer.
107  int num_discarded_packets() const;
108
109  // Statistics, Calculate frame and bit rates.
110  void IncomingRateStatistics(unsigned int* framerate,
111                              unsigned int* bitrate);
112
113  // Checks if the packet sequence will be complete if the next frame would be
114  // grabbed for decoding. That is, if a frame has been lost between the
115  // last decoded frame and the next, or if the next frame is missing one
116  // or more packets.
117  bool CompleteSequenceWithNextFrame();
118
119  // Wait |max_wait_time_ms| for a complete frame to arrive.
120  // The function returns true once such a frame is found, its corresponding
121  // timestamp is returned. Otherwise, returns false.
122  bool NextCompleteTimestamp(uint32_t max_wait_time_ms, uint32_t* timestamp);
123
124  // Locates a frame for decoding (even an incomplete) without delay.
125  // The function returns true once such a frame is found, its corresponding
126  // timestamp is returned. Otherwise, returns false.
127  bool NextMaybeIncompleteTimestamp(uint32_t* timestamp);
128
129  // Extract frame corresponding to input timestamp.
130  // Frame will be set to a decoding state.
131  VCMEncodedFrame* ExtractAndSetDecode(uint32_t timestamp);
132
133  // Releases a frame returned from the jitter buffer, should be called when
134  // done with decoding.
135  void ReleaseFrame(VCMEncodedFrame* frame);
136
137  // Returns the time in ms when the latest packet was inserted into the frame.
138  // Retransmitted is set to true if any of the packets belonging to the frame
139  // has been retransmitted.
140  int64_t LastPacketTime(const VCMEncodedFrame* frame,
141                         bool* retransmitted) const;
142
143  // Inserts a packet into a frame returned from GetFrame().
144  // If the return value is <= 0, |frame| is invalidated and the pointer must
145  // be dropped after this function returns.
146  VCMFrameBufferEnum InsertPacket(const VCMPacket& packet,
147                                  bool* retransmitted);
148
149  // Returns the estimated jitter in milliseconds.
150  uint32_t EstimatedJitterMs();
151
152  // Updates the round-trip time estimate.
153  void UpdateRtt(uint32_t rtt_ms);
154
155  // Set the NACK mode. |highRttNackThreshold| is an RTT threshold in ms above
156  // which NACK will be disabled if the NACK mode is |kNackHybrid|, -1 meaning
157  // that NACK is always enabled in the hybrid mode.
158  // |lowRttNackThreshold| is an RTT threshold in ms below which we expect to
159  // rely on NACK only, and therefore are using larger buffers to have time to
160  // wait for retransmissions.
161  void SetNackMode(VCMNackMode mode, int low_rtt_nack_threshold_ms,
162                   int high_rtt_nack_threshold_ms);
163
164  void SetNackSettings(size_t max_nack_list_size,
165                       int max_packet_age_to_nack,
166                       int max_incomplete_time_ms);
167
168  // Returns the current NACK mode.
169  VCMNackMode nack_mode() const;
170
171  // Returns a list of the sequence numbers currently missing.
172  uint16_t* GetNackList(uint16_t* nack_list_size, bool* request_key_frame);
173
174  // Set decode error mode - Should not be changed in the middle of the
175  // session. Changes will not influence frames already in the buffer.
176  void SetDecodeErrorMode(VCMDecodeErrorMode error_mode);
177  int64_t LastDecodedTimestamp() const;
178  VCMDecodeErrorMode decode_error_mode() const {return decode_error_mode_;}
179
180  // Used to compute time of complete continuous frames. Returns the timestamps
181  // corresponding to the start and end of the continuous complete buffer.
182  void RenderBufferSize(uint32_t* timestamp_start, uint32_t* timestamp_end);
183
184 private:
185  class SequenceNumberLessThan {
186   public:
187    bool operator() (const uint16_t& sequence_number1,
188                     const uint16_t& sequence_number2) const {
189      return IsNewerSequenceNumber(sequence_number2, sequence_number1);
190    }
191  };
192  typedef std::set<uint16_t, SequenceNumberLessThan> SequenceNumberSet;
193
194  // Gets the frame assigned to the timestamp of the packet. May recycle
195  // existing frames if no free frames are available. Returns an error code if
196  // failing, or kNoError on success.
197  VCMFrameBufferEnum GetFrame(const VCMPacket& packet, VCMFrameBuffer** frame);
198  void CopyFrames(FrameList* to_list, const FrameList& from_list);
199  void CopyFrames(FrameList* to_list, const FrameList& from_list, int* index);
200  // Returns true if |frame| is continuous in |decoding_state|, not taking
201  // decodable frames into account.
202  bool IsContinuousInState(const VCMFrameBuffer& frame,
203      const VCMDecodingState& decoding_state) const;
204  // Returns true if |frame| is continuous in the |last_decoded_state_|, taking
205  // all decodable frames into account.
206  bool IsContinuous(const VCMFrameBuffer& frame) const;
207  // Looks for frames in |incomplete_frames_| which are continuous in
208  // |last_decoded_state_| taking all decodable frames into account. Starts
209  // the search from |new_frame|.
210  void FindAndInsertContinuousFrames(const VCMFrameBuffer& new_frame);
211  VCMFrameBuffer* NextFrame() const;
212  // Returns true if the NACK list was updated to cover sequence numbers up to
213  // |sequence_number|. If false a key frame is needed to get into a state where
214  // we can continue decoding.
215  bool UpdateNackList(uint16_t sequence_number);
216  bool TooLargeNackList() const;
217  // Returns true if the NACK list was reduced without problem. If false a key
218  // frame is needed to get into a state where we can continue decoding.
219  bool HandleTooLargeNackList();
220  bool MissingTooOldPacket(uint16_t latest_sequence_number) const;
221  // Returns true if the too old packets was successfully removed from the NACK
222  // list. If false, a key frame is needed to get into a state where we can
223  // continue decoding.
224  bool HandleTooOldPackets(uint16_t latest_sequence_number);
225  // Drops all packets in the NACK list up until |last_decoded_sequence_number|.
226  void DropPacketsFromNackList(uint16_t last_decoded_sequence_number);
227
228  void ReleaseFrameIfNotDecoding(VCMFrameBuffer* frame);
229
230  // Gets an empty frame, creating a new frame if necessary (i.e. increases
231  // jitter buffer size).
232  VCMFrameBuffer* GetEmptyFrame();
233
234  // Attempts to increase the size of the jitter buffer. Returns true on
235  // success, false otherwise.
236  bool TryToIncreaseJitterBufferSize();
237
238  // Recycles oldest frames until a key frame is found. Used if jitter buffer is
239  // completely full. Returns true if a key frame was found.
240  bool RecycleFramesUntilKeyFrame();
241
242  // Updates the frame statistics.
243  // Counts only complete frames, so decodable incomplete frames will not be
244  // counted.
245  void CountFrame(const VCMFrameBuffer& frame);
246
247  // Update rolling average of packets per frame.
248  void UpdateAveragePacketsPerFrame(int current_number_packets_);
249
250  // Cleans the frame list in the JB from old/empty frames.
251  // Should only be called prior to actual use.
252  void CleanUpOldOrEmptyFrames();
253
254  // Returns true if |packet| is likely to have been retransmitted.
255  bool IsPacketRetransmitted(const VCMPacket& packet) const;
256
257  // The following three functions update the jitter estimate with the
258  // payload size, receive time and RTP timestamp of a frame.
259  void UpdateJitterEstimate(const VCMJitterSample& sample,
260                            bool incomplete_frame);
261  void UpdateJitterEstimate(const VCMFrameBuffer& frame, bool incomplete_frame);
262  void UpdateJitterEstimate(int64_t latest_packet_time_ms,
263                            uint32_t timestamp,
264                            unsigned int frame_size,
265                            bool incomplete_frame);
266
267  // Returns true if we should wait for retransmissions, false otherwise.
268  bool WaitForRetransmissions();
269
270  int NonContinuousOrIncompleteDuration();
271
272  uint16_t EstimatedLowSequenceNumber(const VCMFrameBuffer& frame) const;
273
274  Clock* clock_;
275  // If we are running (have started) or not.
276  bool running_;
277  CriticalSectionWrapper* crit_sect_;
278  // Event to signal when we have a frame ready for decoder.
279  scoped_ptr<EventWrapper> frame_event_;
280  // Event to signal when we have received a packet.
281  scoped_ptr<EventWrapper> packet_event_;
282  // Number of allocated frames.
283  int max_number_of_frames_;
284  // Array of pointers to the frames in jitter buffer.
285  VCMFrameBuffer* frame_buffers_[kMaxNumberOfFrames];
286  UnorderedFrameList free_frames_;
287  FrameList decodable_frames_;
288  FrameList incomplete_frames_;
289  VCMDecodingState last_decoded_state_;
290  bool first_packet_since_reset_;
291
292  // Statistics.
293  // Frame counts for each type (key, delta, ...)
294  std::map<FrameType, uint32_t> receive_statistics_;
295  // Latest calculated frame rates of incoming stream.
296  unsigned int incoming_frame_rate_;
297  unsigned int incoming_frame_count_;
298  int64_t time_last_incoming_frame_count_;
299  unsigned int incoming_bit_count_;
300  unsigned int incoming_bit_rate_;
301  unsigned int drop_count_;  // Frame drop counter.
302  // Number of frames in a row that have been too old.
303  int num_consecutive_old_frames_;
304  // Number of packets in a row that have been too old.
305  int num_consecutive_old_packets_;
306  // Number of packets discarded by the jitter buffer.
307  int num_discarded_packets_;
308
309  // Jitter estimation.
310  // Filter for estimating jitter.
311  VCMJitterEstimator jitter_estimate_;
312  // Calculates network delays used for jitter calculations.
313  VCMInterFrameDelay inter_frame_delay_;
314  VCMJitterSample waiting_for_completion_;
315  uint32_t rtt_ms_;
316
317  // NACK and retransmissions.
318  VCMNackMode nack_mode_;
319  int low_rtt_nack_threshold_ms_;
320  int high_rtt_nack_threshold_ms_;
321  // Holds the internal NACK list (the missing sequence numbers).
322  SequenceNumberSet missing_sequence_numbers_;
323  uint16_t latest_received_sequence_number_;
324  std::vector<uint16_t> nack_seq_nums_;
325  size_t max_nack_list_size_;
326  int max_packet_age_to_nack_;  // Measured in sequence numbers.
327  int max_incomplete_time_ms_;
328
329  VCMDecodeErrorMode decode_error_mode_;
330  // Estimated rolling average of packets per frame
331  float average_packets_per_frame_;
332  // average_packets_per_frame converges fast if we have fewer than this many
333  // frames.
334  int frame_counter_;
335  DISALLOW_COPY_AND_ASSIGN(VCMJitterBuffer);
336};
337}  // namespace webrtc
338
339#endif  // WEBRTC_MODULES_VIDEO_CODING_MAIN_SOURCE_JITTER_BUFFER_H_
340