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 MODULES_VIDEO_CODING_JITTER_BUFFER_H_
12 #define MODULES_VIDEO_CODING_JITTER_BUFFER_H_
13 
14 #include <list>
15 #include <map>
16 #include <memory>
17 #include <set>
18 #include <vector>
19 
20 #include "modules/include/module_common_types.h"
21 #include "modules/include/module_common_types_public.h"
22 #include "modules/utility/include/process_thread.h"
23 #include "modules/video_coding/decoding_state.h"
24 #include "modules/video_coding/event_wrapper.h"
25 #include "modules/video_coding/include/video_coding.h"
26 #include "modules/video_coding/include/video_coding_defines.h"
27 #include "modules/video_coding/inter_frame_delay.h"
28 #include "modules/video_coding/jitter_buffer_common.h"
29 #include "modules/video_coding/jitter_estimator.h"
30 #include "rtc_base/constructor_magic.h"
31 #include "rtc_base/synchronization/mutex.h"
32 #include "rtc_base/thread_annotations.h"
33 
34 namespace webrtc {
35 
36 // forward declarations
37 class Clock;
38 class VCMFrameBuffer;
39 class VCMPacket;
40 class VCMEncodedFrame;
41 
42 typedef std::list<VCMFrameBuffer*> UnorderedFrameList;
43 
44 struct VCMJitterSample {
VCMJitterSampleVCMJitterSample45   VCMJitterSample() : timestamp(0), frame_size(0), latest_packet_time(-1) {}
46   uint32_t timestamp;
47   uint32_t frame_size;
48   int64_t latest_packet_time;
49 };
50 
51 class TimestampLessThan {
52  public:
operator()53   bool operator()(uint32_t timestamp1, uint32_t timestamp2) const {
54     return IsNewerTimestamp(timestamp2, timestamp1);
55   }
56 };
57 
58 class FrameList
59     : public std::map<uint32_t, VCMFrameBuffer*, TimestampLessThan> {
60  public:
61   void InsertFrame(VCMFrameBuffer* frame);
62   VCMFrameBuffer* FindFrame(uint16_t seq_num, uint32_t timestamp);
63   VCMFrameBuffer* PopFrame(uint32_t timestamp);
64   VCMFrameBuffer* Front() const;
65   VCMFrameBuffer* Back() const;
66   int RecycleFramesUntilKeyFrame(FrameList::iterator* key_frame_it,
67                                  UnorderedFrameList* free_frames);
68   void CleanUpOldOrEmptyFrames(VCMDecodingState* decoding_state,
69                                UnorderedFrameList* free_frames);
70   void Reset(UnorderedFrameList* free_frames);
71 };
72 
73 class VCMJitterBuffer {
74  public:
75   VCMJitterBuffer(Clock* clock, std::unique_ptr<EventWrapper> event);
76 
77   ~VCMJitterBuffer();
78 
79   // Initializes and starts jitter buffer.
80   void Start();
81 
82   // Signals all internal events and stops the jitter buffer.
83   void Stop();
84 
85   // Returns true if the jitter buffer is running.
86   bool Running() const;
87 
88   // Empty the jitter buffer of all its data.
89   void Flush();
90 
91   // Gets number of packets received.
92   int num_packets() const;
93 
94   // Gets number of duplicated packets received.
95   int num_duplicated_packets() const;
96 
97   // Wait |max_wait_time_ms| for a complete frame to arrive.
98   // If found, a pointer to the frame is returned. Returns nullptr otherwise.
99   VCMEncodedFrame* NextCompleteFrame(uint32_t max_wait_time_ms);
100 
101   // Extract frame corresponding to input timestamp.
102   // Frame will be set to a decoding state.
103   VCMEncodedFrame* ExtractAndSetDecode(uint32_t timestamp);
104 
105   // Releases a frame returned from the jitter buffer, should be called when
106   // done with decoding.
107   void ReleaseFrame(VCMEncodedFrame* frame);
108 
109   // Returns the time in ms when the latest packet was inserted into the frame.
110   // Retransmitted is set to true if any of the packets belonging to the frame
111   // has been retransmitted.
112   int64_t LastPacketTime(const VCMEncodedFrame* frame,
113                          bool* retransmitted) const;
114 
115   // Inserts a packet into a frame returned from GetFrame().
116   // If the return value is <= 0, |frame| is invalidated and the pointer must
117   // be dropped after this function returns.
118   VCMFrameBufferEnum InsertPacket(const VCMPacket& packet, bool* retransmitted);
119 
120   // Returns the estimated jitter in milliseconds.
121   uint32_t EstimatedJitterMs();
122 
123   void SetNackSettings(size_t max_nack_list_size,
124                        int max_packet_age_to_nack,
125                        int max_incomplete_time_ms);
126 
127   // Returns a list of the sequence numbers currently missing.
128   std::vector<uint16_t> GetNackList(bool* request_key_frame);
129 
130  private:
131   class SequenceNumberLessThan {
132    public:
operator()133     bool operator()(const uint16_t& sequence_number1,
134                     const uint16_t& sequence_number2) const {
135       return IsNewerSequenceNumber(sequence_number2, sequence_number1);
136     }
137   };
138   typedef std::set<uint16_t, SequenceNumberLessThan> SequenceNumberSet;
139 
140   // Gets the frame assigned to the timestamp of the packet. May recycle
141   // existing frames if no free frames are available. Returns an error code if
142   // failing, or kNoError on success. |frame_list| contains which list the
143   // packet was in, or NULL if it was not in a FrameList (a new frame).
144   VCMFrameBufferEnum GetFrame(const VCMPacket& packet,
145                               VCMFrameBuffer** frame,
146                               FrameList** frame_list)
147       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
148 
149   // Returns true if |frame| is continuous in |decoding_state|, not taking
150   // decodable frames into account.
151   bool IsContinuousInState(const VCMFrameBuffer& frame,
152                            const VCMDecodingState& decoding_state) const
153       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
154   // Returns true if |frame| is continuous in the |last_decoded_state_|, taking
155   // all decodable frames into account.
156   bool IsContinuous(const VCMFrameBuffer& frame) const
157       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
158   // Looks for frames in |incomplete_frames_| which are continuous in the
159   // provided |decoded_state|. Starts the search from the timestamp of
160   // |decoded_state|.
161   void FindAndInsertContinuousFramesWithState(
162       const VCMDecodingState& decoded_state)
163       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
164   // Looks for frames in |incomplete_frames_| which are continuous in
165   // |last_decoded_state_| taking all decodable frames into account. Starts
166   // the search from |new_frame|.
167   void FindAndInsertContinuousFrames(const VCMFrameBuffer& new_frame)
168       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
169   VCMFrameBuffer* NextFrame() const RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
170   // Returns true if the NACK list was updated to cover sequence numbers up to
171   // |sequence_number|. If false a key frame is needed to get into a state where
172   // we can continue decoding.
173   bool UpdateNackList(uint16_t sequence_number)
174       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
175   bool TooLargeNackList() const;
176   // Returns true if the NACK list was reduced without problem. If false a key
177   // frame is needed to get into a state where we can continue decoding.
178   bool HandleTooLargeNackList() RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
179   bool MissingTooOldPacket(uint16_t latest_sequence_number) const
180       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
181   // Returns true if the too old packets was successfully removed from the NACK
182   // list. If false, a key frame is needed to get into a state where we can
183   // continue decoding.
184   bool HandleTooOldPackets(uint16_t latest_sequence_number)
185       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
186   // Drops all packets in the NACK list up until |last_decoded_sequence_number|.
187   void DropPacketsFromNackList(uint16_t last_decoded_sequence_number);
188 
189   // Gets an empty frame, creating a new frame if necessary (i.e. increases
190   // jitter buffer size).
191   VCMFrameBuffer* GetEmptyFrame() RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
192 
193   // Attempts to increase the size of the jitter buffer. Returns true on
194   // success, false otherwise.
195   bool TryToIncreaseJitterBufferSize() RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
196 
197   // Recycles oldest frames until a key frame is found. Used if jitter buffer is
198   // completely full. Returns true if a key frame was found.
199   bool RecycleFramesUntilKeyFrame() RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
200 
201   // Update rolling average of packets per frame.
202   void UpdateAveragePacketsPerFrame(int current_number_packets_);
203 
204   // Cleans the frame list in the JB from old/empty frames.
205   // Should only be called prior to actual use.
206   void CleanUpOldOrEmptyFrames() RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
207 
208   // Returns true if |packet| is likely to have been retransmitted.
209   bool IsPacketRetransmitted(const VCMPacket& packet) const;
210 
211   // The following three functions update the jitter estimate with the
212   // payload size, receive time and RTP timestamp of a frame.
213   void UpdateJitterEstimate(const VCMJitterSample& sample,
214                             bool incomplete_frame);
215   void UpdateJitterEstimate(const VCMFrameBuffer& frame, bool incomplete_frame);
216   void UpdateJitterEstimate(int64_t latest_packet_time_ms,
217                             uint32_t timestamp,
218                             unsigned int frame_size,
219                             bool incomplete_frame);
220 
221   int NonContinuousOrIncompleteDuration() RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
222 
223   uint16_t EstimatedLowSequenceNumber(const VCMFrameBuffer& frame) const;
224 
225   // Reset frame buffer and return it to free_frames_.
226   void RecycleFrameBuffer(VCMFrameBuffer* frame)
227       RTC_EXCLUSIVE_LOCKS_REQUIRED(mutex_);
228 
229   Clock* clock_;
230   // If we are running (have started) or not.
231   bool running_;
232   mutable Mutex mutex_;
233   // Event to signal when we have a frame ready for decoder.
234   std::unique_ptr<EventWrapper> frame_event_;
235   // Number of allocated frames.
236   int max_number_of_frames_;
237   UnorderedFrameList free_frames_ RTC_GUARDED_BY(mutex_);
238   FrameList decodable_frames_ RTC_GUARDED_BY(mutex_);
239   FrameList incomplete_frames_ RTC_GUARDED_BY(mutex_);
240   VCMDecodingState last_decoded_state_ RTC_GUARDED_BY(mutex_);
241   bool first_packet_since_reset_;
242 
243   // Number of packets in a row that have been too old.
244   int num_consecutive_old_packets_;
245   // Number of packets received.
246   int num_packets_ RTC_GUARDED_BY(mutex_);
247   // Number of duplicated packets received.
248   int num_duplicated_packets_ RTC_GUARDED_BY(mutex_);
249 
250   // Jitter estimation.
251   // Filter for estimating jitter.
252   VCMJitterEstimator jitter_estimate_;
253   // Calculates network delays used for jitter calculations.
254   VCMInterFrameDelay inter_frame_delay_;
255   VCMJitterSample waiting_for_completion_;
256 
257   // Holds the internal NACK list (the missing sequence numbers).
258   SequenceNumberSet missing_sequence_numbers_;
259   uint16_t latest_received_sequence_number_;
260   size_t max_nack_list_size_;
261   int max_packet_age_to_nack_;  // Measured in sequence numbers.
262   int max_incomplete_time_ms_;
263 
264   // Estimated rolling average of packets per frame
265   float average_packets_per_frame_;
266   // average_packets_per_frame converges fast if we have fewer than this many
267   // frames.
268   int frame_counter_;
269 
270   RTC_DISALLOW_COPY_AND_ASSIGN(VCMJitterBuffer);
271 };
272 }  // namespace webrtc
273 
274 #endif  // MODULES_VIDEO_CODING_JITTER_BUFFER_H_
275