Introduce DecodedFramesHistory class and use it in FrameBuffer
This is a space efficient way to store more records about decoded frames,
which is needed for long term references.
Bug: webrtc:9710
Change-Id: I051d59d34a966d48db011142466d9cd15304b7d9
Reviewed-on: https://webrtc-review.googlesource.com/c/116792
Commit-Queue: Ilya Nikolaevskiy <ilnik@webrtc.org>
Reviewed-by: Philip Eliasson <philipel@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#26240}diff --git a/modules/video_coding/BUILD.gn b/modules/video_coding/BUILD.gn
index 188b624..470f5b0 100644
--- a/modules/video_coding/BUILD.gn
+++ b/modules/video_coding/BUILD.gn
@@ -23,7 +23,6 @@
"../../api/video:video_frame_i420",
"../../modules:module_api",
"../../modules:module_api_public",
- "../../modules/video_coding:video_coding_utility",
"../../rtc_base:checks",
"../../rtc_base:rtc_base_approved",
"../../rtc_base/experiments:alr_experiment",
@@ -249,6 +248,8 @@
rtc_source_set("video_coding_utility") {
visibility = [ "*" ]
sources = [
+ "utility/decoded_frames_history.cc",
+ "utility/decoded_frames_history.h",
"utility/default_video_bitrate_allocator.cc",
"utility/default_video_bitrate_allocator.h",
"utility/frame_dropper.cc",
@@ -278,6 +279,7 @@
":video_codec_interface",
"..:module_api",
"../..:webrtc_common",
+ "../../api/video:encoded_frame",
"../../api/video:encoded_image",
"../../api/video:video_bitrate_allocation",
"../../api/video:video_bitrate_allocator",
@@ -862,6 +864,7 @@
"test/stream_generator.cc",
"test/stream_generator.h",
"timing_unittest.cc",
+ "utility/decoded_frames_history_unittest.cc",
"utility/default_video_bitrate_allocator_unittest.cc",
"utility/frame_dropper_unittest.cc",
"utility/framerate_controller_unittest.cc",
diff --git a/modules/video_coding/frame_buffer2.cc b/modules/video_coding/frame_buffer2.cc
index 4c0a3bb..832fd36 100644
--- a/modules/video_coding/frame_buffer2.cc
+++ b/modules/video_coding/frame_buffer2.cc
@@ -36,10 +36,10 @@
namespace {
// Max number of frames the buffer will hold.
-constexpr size_t kMaxFramesBuffered = 600;
+constexpr size_t kMaxFramesBuffered = 800;
// Max number of decoded frame info that will be saved.
-constexpr size_t kMaxFramesHistory = 50;
+constexpr int kMaxFramesHistory = 1 << 13;
// The time it's allowed for a frame to be late to its rendering prediction and
// still be rendered.
@@ -52,7 +52,8 @@
VCMJitterEstimator* jitter_estimator,
VCMTiming* timing,
VCMReceiveStatisticsCallback* stats_callback)
- : clock_(clock),
+ : decoded_frames_history_(kMaxFramesHistory),
+ clock_(clock),
jitter_estimator_(jitter_estimator),
timing_(timing),
inter_frame_delay_(clock_->TimeInMilliseconds()),
@@ -104,11 +105,14 @@
if (keyframe_required && !frame->is_keyframe())
continue;
+ auto last_decoded_frame_timestamp =
+ decoded_frames_history_.GetLastDecodedFrameTimestamp();
+
// TODO(https://bugs.webrtc.org/9974): consider removing this check
// as it may make a stream undecodable after a very long delay between
// frames.
- if (last_decoded_frame_timestamp_ &&
- AheadOf(*last_decoded_frame_timestamp_, frame->Timestamp())) {
+ if (last_decoded_frame_timestamp &&
+ AheadOf(*last_decoded_frame_timestamp, frame->Timestamp())) {
continue;
}
@@ -185,7 +189,7 @@
rtc::CritScope lock(&crit_);
now_ms = clock_->TimeInMilliseconds();
std::vector<EncodedFrame*> frames_out;
- for (const FrameMap::iterator& frame_it : frames_to_decode_) {
+ for (FrameMap::iterator& frame_it : frames_to_decode_) {
RTC_DCHECK(frame_it != frames_.end());
EncodedFrame* frame = frame_it->second.frame.release();
@@ -220,8 +224,12 @@
UpdateTimingFrameInfo();
PropagateDecodability(frame_it->second);
- AdvanceLastDecodedFrame(frame_it);
- last_decoded_frame_timestamp_ = frame->Timestamp();
+ decoded_frames_history_.InsertDecoded(frame_it->first,
+ frame->Timestamp());
+
+ // Remove decoded frame and all undecoded frames before it.
+ frames_.erase(frames_.begin(), ++frame_it);
+
frames_out.push_back(frame);
}
@@ -374,8 +382,11 @@
}
}
- if (last_decoded_frame_ && id <= *last_decoded_frame_) {
- if (AheadOf(frame->Timestamp(), *last_decoded_frame_timestamp_) &&
+ auto last_decoded_frame = decoded_frames_history_.GetLastDecodedFrameId();
+ auto last_decoded_frame_timestamp =
+ decoded_frames_history_.GetLastDecodedFrameTimestamp();
+ if (last_decoded_frame && id <= *last_decoded_frame) {
+ if (AheadOf(frame->Timestamp(), *last_decoded_frame_timestamp) &&
frame->is_keyframe()) {
// If this frame has a newer timestamp but an earlier picture id then we
// assume there has been a jump in the picture id due to some encoder
@@ -391,9 +402,8 @@
<< id.picture_id << ":"
<< static_cast<int>(id.spatial_layer)
<< ") inserted after frame ("
- << last_decoded_frame_->picture_id << ":"
- << static_cast<int>(
- last_decoded_frame_->spatial_layer)
+ << last_decoded_frame->picture_id << ":"
+ << static_cast<int>(last_decoded_frame->spatial_layer)
<< ") was handed off for decoding, dropping frame.";
return last_continuous_picture_id;
}
@@ -487,32 +497,13 @@
}
}
-void FrameBuffer::AdvanceLastDecodedFrame(FrameMap::iterator decoded) {
- TRACE_EVENT0("webrtc", "FrameBuffer::AdvanceLastDecodedFrame");
-
- decoded_frames_history_.insert(decoded->first);
-
- FrameMap::iterator frame_it = frames_.begin();
-
- // First, delete non-decoded frames from the history.
- while (frame_it != decoded)
- frame_it = frames_.erase(frame_it);
-
- // Then remove old history if we have too much history saved.
- if (decoded_frames_history_.size() > kMaxFramesHistory)
- decoded_frames_history_.erase(decoded_frames_history_.begin());
-
- // Then remove the frame from the undecoded frames list.
- last_decoded_frame_ = decoded->first;
- frames_.erase(decoded);
-}
-
bool FrameBuffer::UpdateFrameInfoWithIncomingFrame(const EncodedFrame& frame,
FrameMap::iterator info) {
TRACE_EVENT0("webrtc", "FrameBuffer::UpdateFrameInfoWithIncomingFrame");
const VideoLayerFrameId& id = frame.id;
- RTC_DCHECK(!last_decoded_frame_ || *last_decoded_frame_ < info->first);
+ auto last_decoded_frame = decoded_frames_history_.GetLastDecodedFrameId();
+ RTC_DCHECK(!last_decoded_frame || *last_decoded_frame < info->first);
// In this function we determine how many missing dependencies this |frame|
// has to become continuous/decodable. If a frame that this |frame| depend
@@ -532,11 +523,10 @@
for (size_t i = 0; i < frame.num_references; ++i) {
VideoLayerFrameId ref_key(frame.references[i], frame.id.spatial_layer);
// Does |frame| depend on a frame earlier than the last decoded one?
- if (last_decoded_frame_ && ref_key <= *last_decoded_frame_) {
+ if (last_decoded_frame && ref_key <= *last_decoded_frame) {
// Was that frame decoded? If not, this |frame| will never become
// decodable.
- if (decoded_frames_history_.find(ref_key) ==
- decoded_frames_history_.end()) {
+ if (!decoded_frames_history_.WasDecoded(ref_key)) {
int64_t now_ms = clock_->TimeInMilliseconds();
if (last_log_non_decoded_ms_ + kLogNonDecodedIntervalMs < now_ms) {
RTC_LOG(LS_WARNING)
@@ -562,7 +552,7 @@
auto ref_info = frames_.find(ref_key);
bool lower_layer_decoded =
- last_decoded_frame_ && *last_decoded_frame_ == ref_key;
+ last_decoded_frame && *last_decoded_frame == ref_key;
bool lower_layer_continuous =
lower_layer_decoded ||
(ref_info != frames_.end() && ref_info->second.continuous);
@@ -617,10 +607,9 @@
void FrameBuffer::ClearFramesAndHistory() {
TRACE_EVENT0("webrtc", "FrameBuffer::ClearFramesAndHistory");
frames_.clear();
- last_decoded_frame_.reset();
last_continuous_frame_.reset();
frames_to_decode_.clear();
- decoded_frames_history_.clear();
+ decoded_frames_history_.Clear();
}
EncodedFrame* FrameBuffer::CombineAndDeleteFrames(
diff --git a/modules/video_coding/frame_buffer2.h b/modules/video_coding/frame_buffer2.h
index 64249a5..1f41bfa 100644
--- a/modules/video_coding/frame_buffer2.h
+++ b/modules/video_coding/frame_buffer2.h
@@ -14,7 +14,6 @@
#include <array>
#include <map>
#include <memory>
-#include <set>
#include <utility>
#include <vector>
@@ -22,6 +21,7 @@
#include "api/video/encoded_frame.h"
#include "modules/video_coding/include/video_coding_defines.h"
#include "modules/video_coding/inter_frame_delay.h"
+#include "modules/video_coding/utility/decoded_frames_history.h"
#include "rtc_base/constructor_magic.h"
#include "rtc_base/critical_section.h"
#include "rtc_base/event.h"
@@ -132,10 +132,6 @@
void PropagateDecodability(const FrameInfo& info)
RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_);
- // Removes undecodable frames and moves decoded frame to the history.
- void AdvanceLastDecodedFrame(FrameMap::iterator decoded)
- RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_);
-
// Update the corresponding FrameInfo of |frame| and all FrameInfos that
// |frame| references.
// Return false if |frame| will never be decodable, true otherwise.
@@ -161,7 +157,7 @@
// Stores only undecoded frames.
FrameMap frames_ RTC_GUARDED_BY(crit_);
- std::set<VideoLayerFrameId> decoded_frames_history_ RTC_GUARDED_BY(crit_);
+ DecodedFramesHistory decoded_frames_history_ RTC_GUARDED_BY(crit_);
rtc::CriticalSection crit_;
Clock* const clock_;
@@ -169,8 +165,6 @@
VCMJitterEstimator* const jitter_estimator_ RTC_GUARDED_BY(crit_);
VCMTiming* const timing_ RTC_GUARDED_BY(crit_);
VCMInterFrameDelay inter_frame_delay_ RTC_GUARDED_BY(crit_);
- absl::optional<uint32_t> last_decoded_frame_timestamp_ RTC_GUARDED_BY(crit_);
- absl::optional<VideoLayerFrameId> last_decoded_frame_ RTC_GUARDED_BY(crit_);
absl::optional<VideoLayerFrameId> last_continuous_frame_
RTC_GUARDED_BY(crit_);
std::vector<FrameMap::iterator> frames_to_decode_ RTC_GUARDED_BY(crit_);
diff --git a/modules/video_coding/utility/decoded_frames_history.cc b/modules/video_coding/utility/decoded_frames_history.cc
new file mode 100644
index 0000000..42af6a1
--- /dev/null
+++ b/modules/video_coding/utility/decoded_frames_history.cc
@@ -0,0 +1,108 @@
+/*
+ * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/video_coding/utility/decoded_frames_history.h"
+
+#include <algorithm>
+
+#include "rtc_base/checks.h"
+#include "rtc_base/logging.h"
+
+namespace webrtc {
+namespace video_coding {
+
+DecodedFramesHistory::LayerHistory::LayerHistory() = default;
+DecodedFramesHistory::LayerHistory::~LayerHistory() = default;
+
+DecodedFramesHistory::DecodedFramesHistory(size_t window_size)
+ : window_size_(window_size) {}
+
+DecodedFramesHistory::~DecodedFramesHistory() = default;
+
+void DecodedFramesHistory::InsertDecoded(const VideoLayerFrameId& frameid,
+ uint32_t timestamp) {
+ last_decoded_frame_ = frameid;
+ last_decoded_frame_timestamp_ = timestamp;
+ if (static_cast<int>(layers_.size()) < frameid.spatial_layer + 1) {
+ layers_.resize(frameid.spatial_layer + 1);
+ layers_[frameid.spatial_layer].buffer.resize(window_size_);
+ layers_[frameid.spatial_layer].last_stored_index = frameid.picture_id;
+ layers_[frameid.spatial_layer].buffer[frameid.picture_id % window_size_] =
+ true;
+ return;
+ }
+
+ LayerHistory& history = layers_[frameid.spatial_layer];
+
+ RTC_DCHECK_LT(history.last_stored_index, frameid.picture_id);
+
+ int64_t id_jump = frameid.picture_id - history.last_stored_index;
+ int last_index = history.last_stored_index % window_size_;
+ int new_index = frameid.picture_id % window_size_;
+
+ // Need to clear indexes between last_index + 1 and new_index as they fall
+ // out of the history window and now represent new unseen picture ids.
+ if (id_jump >= window_size_) {
+ // Wraps around whole buffer - clear it all.
+ std::fill(history.buffer.begin(), history.buffer.end(), false);
+ } else if (new_index > last_index) {
+ std::fill(history.buffer.begin() + last_index + 1,
+ history.buffer.begin() + new_index, false);
+ } else {
+ std::fill(history.buffer.begin() + last_index + 1, history.buffer.end(),
+ false);
+ std::fill(history.buffer.begin(), history.buffer.begin() + new_index,
+ false);
+ }
+
+ history.buffer[new_index] = true;
+ history.last_stored_index = frameid.picture_id;
+}
+
+bool DecodedFramesHistory::WasDecoded(const VideoLayerFrameId& frameid) {
+ // Unseen before spatial layer.
+ if (static_cast<int>(layers_.size()) < frameid.spatial_layer + 1)
+ return false;
+
+ LayerHistory& history = layers_[frameid.spatial_layer];
+
+ // Reference to the picture_id out of the stored history should happen.
+ if (frameid.picture_id <= history.last_stored_index - window_size_) {
+ RTC_LOG(LS_WARNING) << "Referencing a frame out of the history window. "
+ "Assuming it was undecoded to avoid artifacts.";
+ return false;
+ }
+
+ if (frameid.picture_id > history.last_stored_index)
+ return false;
+
+ return history.buffer[frameid.picture_id % window_size_];
+}
+
+void DecodedFramesHistory::Clear() {
+ for (LayerHistory& layer : layers_) {
+ std::fill(layer.buffer.begin(), layer.buffer.end(), false);
+ layer.last_stored_index = 0;
+ }
+ last_decoded_frame_timestamp_.reset();
+ last_decoded_frame_.reset();
+}
+
+absl::optional<VideoLayerFrameId>
+DecodedFramesHistory::GetLastDecodedFrameId() {
+ return last_decoded_frame_;
+}
+
+absl::optional<uint32_t> DecodedFramesHistory::GetLastDecodedFrameTimestamp() {
+ return last_decoded_frame_timestamp_;
+}
+
+} // namespace video_coding
+} // namespace webrtc
diff --git a/modules/video_coding/utility/decoded_frames_history.h b/modules/video_coding/utility/decoded_frames_history.h
new file mode 100644
index 0000000..3790946
--- /dev/null
+++ b/modules/video_coding/utility/decoded_frames_history.h
@@ -0,0 +1,60 @@
+/*
+ * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef MODULES_VIDEO_CODING_UTILITY_DECODED_FRAMES_HISTORY_H_
+#define MODULES_VIDEO_CODING_UTILITY_DECODED_FRAMES_HISTORY_H_
+
+#include <stdint.h>
+#include <bitset>
+#include <vector>
+
+#include "absl/types/optional.h"
+#include "api/video/encoded_frame.h"
+
+namespace webrtc {
+namespace video_coding {
+
+class DecodedFramesHistory {
+ public:
+ // window_size - how much frames back to the past are actually remembered.
+ explicit DecodedFramesHistory(size_t window_size);
+ ~DecodedFramesHistory();
+ // Called for each decoded frame. Assumes picture id's are non-decreasing.
+ void InsertDecoded(const VideoLayerFrameId& frameid, uint32_t timestamp);
+ // Query if the following (picture_id, spatial_id) pair was inserted before.
+ // Should be at most less by window_size-1 than the last inserted picture id.
+ bool WasDecoded(const VideoLayerFrameId& frameid);
+
+ void Clear();
+
+ absl::optional<VideoLayerFrameId> GetLastDecodedFrameId();
+ absl::optional<uint32_t> GetLastDecodedFrameTimestamp();
+
+ private:
+ struct LayerHistory {
+ LayerHistory();
+ ~LayerHistory();
+ // Cyclic bitset buffer. Stores last known |window_size| bits.
+ // last_stored_index is the last actually stored bit. Previous
+ // |window_size-1| bits are also in the memory. Value for i-th bit is at
+ // buffer[i % window_size].
+ std::vector<bool> buffer;
+ int64_t last_stored_index;
+ };
+
+ const int window_size_;
+ std::vector<LayerHistory> layers_;
+ absl::optional<VideoLayerFrameId> last_decoded_frame_;
+ absl::optional<uint32_t> last_decoded_frame_timestamp_;
+};
+
+} // namespace video_coding
+} // namespace webrtc
+#endif // MODULES_VIDEO_CODING_UTILITY_DECODED_FRAMES_HISTORY_H_
diff --git a/modules/video_coding/utility/decoded_frames_history_unittest.cc b/modules/video_coding/utility/decoded_frames_history_unittest.cc
new file mode 100644
index 0000000..2155e5c
--- /dev/null
+++ b/modules/video_coding/utility/decoded_frames_history_unittest.cc
@@ -0,0 +1,116 @@
+/*
+ * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/video_coding/utility/decoded_frames_history.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace video_coding {
+namespace {
+
+constexpr int kHistorySize = 1 << 13;
+
+TEST(DecodedFramesHistory, RequestOnEmptyHistory) {
+ DecodedFramesHistory history(kHistorySize);
+ EXPECT_EQ(history.WasDecoded({1234, 0}), false);
+}
+
+TEST(DecodedFramesHistory, FindsLastDecodedFrame) {
+ DecodedFramesHistory history(kHistorySize);
+ history.InsertDecoded({1234, 0}, 0);
+ EXPECT_EQ(history.WasDecoded({1234, 0}), true);
+}
+
+TEST(DecodedFramesHistory, FindsPreviousFrame) {
+ DecodedFramesHistory history(kHistorySize);
+ history.InsertDecoded({1234, 0}, 0);
+ history.InsertDecoded({1235, 0}, 0);
+ EXPECT_EQ(history.WasDecoded({1234, 0}), true);
+}
+
+TEST(DecodedFramesHistory, ReportsMissingFrame) {
+ DecodedFramesHistory history(kHistorySize);
+ history.InsertDecoded({1234, 0}, 0);
+ history.InsertDecoded({1236, 0}, 0);
+ EXPECT_EQ(history.WasDecoded({1235, 0}), false);
+}
+
+TEST(DecodedFramesHistory, ClearsHistory) {
+ DecodedFramesHistory history(kHistorySize);
+ history.InsertDecoded({1234, 0}, 0);
+ history.Clear();
+ EXPECT_EQ(history.WasDecoded({1234, 0}), false);
+ EXPECT_EQ(history.GetLastDecodedFrameId(), absl::nullopt);
+ EXPECT_EQ(history.GetLastDecodedFrameTimestamp(), absl::nullopt);
+}
+
+TEST(DecodedFramesHistory, HandlesMultipleLayers) {
+ DecodedFramesHistory history(kHistorySize);
+ history.InsertDecoded({1234, 0}, 0);
+ history.InsertDecoded({1234, 1}, 0);
+ history.InsertDecoded({1235, 0}, 0);
+ history.InsertDecoded({1236, 0}, 0);
+ history.InsertDecoded({1236, 1}, 0);
+ EXPECT_EQ(history.WasDecoded({1235, 0}), true);
+ EXPECT_EQ(history.WasDecoded({1235, 1}), false);
+}
+
+TEST(DecodedFramesHistory, HandlesNewLayer) {
+ DecodedFramesHistory history(kHistorySize);
+ history.InsertDecoded({1234, 0}, 0);
+ history.InsertDecoded({1234, 1}, 0);
+ history.InsertDecoded({1235, 0}, 0);
+ history.InsertDecoded({1235, 1}, 0);
+ history.InsertDecoded({1236, 0}, 0);
+ history.InsertDecoded({1236, 1}, 0);
+ EXPECT_EQ(history.WasDecoded({1234, 2}), false);
+}
+
+TEST(DecodedFramesHistory, HandlesBigJumpInPictureId) {
+ DecodedFramesHistory history(kHistorySize);
+ history.InsertDecoded({1234, 0}, 0);
+ history.InsertDecoded({1235, 0}, 0);
+ history.InsertDecoded({1236, 0}, 0);
+ history.InsertDecoded({1236 + kHistorySize / 2, 0}, 0);
+ EXPECT_EQ(history.WasDecoded({1234, 0}), true);
+ EXPECT_EQ(history.WasDecoded({1237, 0}), false);
+}
+
+TEST(DecodedFramesHistory, ForgetsTooOldHistory) {
+ DecodedFramesHistory history(kHistorySize);
+ history.InsertDecoded({1234, 0}, 0);
+ history.InsertDecoded({1235, 0}, 0);
+ history.InsertDecoded({1236, 0}, 0);
+ history.InsertDecoded({1236 + kHistorySize * 2, 0}, 0);
+ EXPECT_EQ(history.WasDecoded({1234, 0}), false);
+ EXPECT_EQ(history.WasDecoded({1237, 0}), false);
+}
+
+TEST(DecodedFramesHistory, ReturnsLastDecodedFrameId) {
+ DecodedFramesHistory history(kHistorySize);
+ EXPECT_EQ(history.GetLastDecodedFrameId(), absl::nullopt);
+ history.InsertDecoded({1234, 0}, 0);
+ EXPECT_EQ(history.GetLastDecodedFrameId(), VideoLayerFrameId(1234, 0));
+ history.InsertDecoded({1235, 0}, 0);
+ EXPECT_EQ(history.GetLastDecodedFrameId(), VideoLayerFrameId(1235, 0));
+}
+
+TEST(DecodedFramesHistory, ReturnsLastDecodedFrameTimestamp) {
+ DecodedFramesHistory history(kHistorySize);
+ EXPECT_EQ(history.GetLastDecodedFrameTimestamp(), absl::nullopt);
+ history.InsertDecoded({1234, 0}, 12345);
+ EXPECT_EQ(history.GetLastDecodedFrameTimestamp(), 12345u);
+ history.InsertDecoded({1235, 0}, 12366);
+ EXPECT_EQ(history.GetLastDecodedFrameTimestamp(), 12366u);
+}
+
+} // namespace
+} // namespace video_coding
+} // namespace webrtc