Line data Source code
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 : #include "webrtc/modules/rtp_rtcp/source/tmmbr_help.h"
12 :
13 : #include <algorithm>
14 : #include <limits>
15 :
16 : #include "webrtc/base/checks.h"
17 :
18 : namespace webrtc {
19 0 : std::vector<rtcp::TmmbItem> TMMBRHelp::FindBoundingSet(
20 : std::vector<rtcp::TmmbItem> candidates) {
21 : // Filter out candidates with 0 bitrate.
22 0 : for (auto it = candidates.begin(); it != candidates.end();) {
23 0 : if (!it->bitrate_bps())
24 0 : it = candidates.erase(it);
25 : else
26 0 : ++it;
27 : }
28 :
29 0 : if (candidates.size() <= 1)
30 0 : return candidates;
31 :
32 0 : size_t num_candidates = candidates.size();
33 :
34 : // 1. Sort by increasing packet overhead.
35 0 : std::sort(candidates.begin(), candidates.end(),
36 0 : [](const rtcp::TmmbItem& lhs, const rtcp::TmmbItem& rhs) {
37 0 : return lhs.packet_overhead() < rhs.packet_overhead();
38 0 : });
39 :
40 : // 2. For tuples with same overhead, keep the one with the lowest bitrate.
41 0 : for (auto it = candidates.begin(); it != candidates.end();) {
42 0 : RTC_DCHECK(it->bitrate_bps());
43 0 : auto current_min = it;
44 0 : auto next_it = it + 1;
45 : // Use fact candidates are sorted by overhead, so candidates with same
46 : // overhead are adjusted.
47 0 : while (next_it != candidates.end() &&
48 0 : next_it->packet_overhead() == current_min->packet_overhead()) {
49 0 : if (next_it->bitrate_bps() < current_min->bitrate_bps()) {
50 0 : current_min->set_bitrate_bps(0);
51 0 : current_min = next_it;
52 : } else {
53 0 : next_it->set_bitrate_bps(0);
54 : }
55 0 : ++next_it;
56 0 : --num_candidates;
57 : }
58 0 : it = next_it;
59 : }
60 :
61 : // 3. Select and remove tuple with lowest bitrate.
62 : // (If more than 1, choose the one with highest overhead).
63 0 : auto min_bitrate_it = candidates.end();
64 0 : for (auto it = candidates.begin(); it != candidates.end(); ++it) {
65 0 : if (it->bitrate_bps()) {
66 0 : min_bitrate_it = it;
67 0 : break;
68 : }
69 : }
70 :
71 0 : for (auto it = min_bitrate_it; it != candidates.end(); ++it) {
72 0 : if (it->bitrate_bps() &&
73 0 : it->bitrate_bps() <= min_bitrate_it->bitrate_bps()) {
74 : // Get min bitrate.
75 0 : min_bitrate_it = it;
76 : }
77 : }
78 :
79 0 : std::vector<rtcp::TmmbItem> bounding_set;
80 0 : bounding_set.reserve(num_candidates);
81 0 : std::vector<float> intersection(num_candidates);
82 0 : std::vector<float> max_packet_rate(num_candidates);
83 :
84 : // First member of selected list.
85 0 : bounding_set.push_back(*min_bitrate_it);
86 0 : intersection[0] = 0;
87 : // Calculate its maximum packet rate (where its line crosses x-axis).
88 0 : uint16_t packet_overhead = bounding_set.back().packet_overhead();
89 0 : if (packet_overhead == 0) {
90 : // Avoid division by zero.
91 0 : max_packet_rate[0] = std::numeric_limits<float>::max();
92 : } else {
93 0 : max_packet_rate[0] =
94 0 : bounding_set.back().bitrate_bps() / static_cast<float>(packet_overhead);
95 : }
96 : // Remove from candidate list.
97 0 : min_bitrate_it->set_bitrate_bps(0);
98 0 : --num_candidates;
99 :
100 : // 4. Discard from candidate list all tuple with lower overhead
101 : // (next tuple must be steeper).
102 0 : for (auto it = candidates.begin(); it != candidates.end(); ++it) {
103 0 : if (it->bitrate_bps() &&
104 0 : it->packet_overhead() < bounding_set.front().packet_overhead()) {
105 0 : it->set_bitrate_bps(0);
106 0 : --num_candidates;
107 : }
108 : }
109 :
110 0 : bool get_new_candidate = true;
111 0 : rtcp::TmmbItem cur_candidate;
112 0 : while (num_candidates > 0) {
113 0 : if (get_new_candidate) {
114 : // 5. Remove first remaining tuple from candidate list.
115 0 : for (auto it = candidates.begin(); it != candidates.end(); ++it) {
116 0 : if (it->bitrate_bps()) {
117 0 : cur_candidate = *it;
118 0 : it->set_bitrate_bps(0);
119 0 : break;
120 : }
121 : }
122 : }
123 :
124 : // 6. Calculate packet rate and intersection of the current
125 : // line with line of last tuple in selected list.
126 0 : RTC_DCHECK_NE(cur_candidate.packet_overhead(),
127 0 : bounding_set.back().packet_overhead());
128 0 : float packet_rate = static_cast<float>(cur_candidate.bitrate_bps() -
129 0 : bounding_set.back().bitrate_bps()) /
130 0 : (cur_candidate.packet_overhead() -
131 0 : bounding_set.back().packet_overhead());
132 :
133 : // 7. If the packet rate is equal or lower than intersection of
134 : // last tuple in selected list,
135 : // remove last tuple in selected list & go back to step 6.
136 0 : if (packet_rate <= intersection[bounding_set.size() - 1]) {
137 : // Remove last tuple and goto step 6.
138 0 : bounding_set.pop_back();
139 0 : get_new_candidate = false;
140 : } else {
141 : // 8. If packet rate is lower than maximum packet rate of
142 : // last tuple in selected list, add current tuple to selected
143 : // list.
144 0 : if (packet_rate < max_packet_rate[bounding_set.size() - 1]) {
145 0 : bounding_set.push_back(cur_candidate);
146 0 : intersection[bounding_set.size() - 1] = packet_rate;
147 0 : uint16_t packet_overhead = bounding_set.back().packet_overhead();
148 0 : RTC_DCHECK_NE(packet_overhead, 0);
149 0 : max_packet_rate[bounding_set.size() - 1] =
150 0 : bounding_set.back().bitrate_bps() /
151 0 : static_cast<float>(packet_overhead);
152 : }
153 0 : --num_candidates;
154 0 : get_new_candidate = true;
155 : }
156 :
157 : // 9. Go back to step 5 if any tuple remains in candidate list.
158 : }
159 0 : RTC_DCHECK(!bounding_set.empty());
160 0 : return bounding_set;
161 : }
162 :
163 0 : bool TMMBRHelp::IsOwner(const std::vector<rtcp::TmmbItem>& bounding,
164 : uint32_t ssrc) {
165 0 : for (const rtcp::TmmbItem& item : bounding) {
166 0 : if (item.ssrc() == ssrc) {
167 0 : return true;
168 : }
169 : }
170 0 : return false;
171 : }
172 :
173 0 : uint64_t TMMBRHelp::CalcMinBitrateBps(
174 : const std::vector<rtcp::TmmbItem>& candidates) {
175 0 : RTC_DCHECK(!candidates.empty());
176 0 : uint64_t min_bitrate_bps = std::numeric_limits<uint64_t>::max();
177 0 : for (const rtcp::TmmbItem& item : candidates)
178 0 : if (item.bitrate_bps() < min_bitrate_bps)
179 0 : min_bitrate_bps = item.bitrate_bps();
180 0 : return min_bitrate_bps;
181 : }
182 : } // namespace webrtc
|
