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/vp8_partition_aggregator.h"
12
13 #include <assert.h>
14 #include <stdlib.h> // NULL
15
16 #include <algorithm>
17 #include <limits>
18
19 namespace webrtc {
20
PartitionTreeNode(PartitionTreeNode * parent,const size_t * size_vector,size_t num_partitions,size_t this_size)21 PartitionTreeNode::PartitionTreeNode(PartitionTreeNode* parent,
22 const size_t* size_vector,
23 size_t num_partitions,
24 size_t this_size)
25 : parent_(parent),
26 this_size_(this_size),
27 size_vector_(size_vector),
28 num_partitions_(num_partitions),
29 max_parent_size_(0),
30 min_parent_size_(std::numeric_limits<int>::max()),
31 packet_start_(false) {
32 // If |this_size_| > INT_MAX, Cost() and CreateChildren() won't work properly.
33 assert(this_size_ <= static_cast<size_t>(std::numeric_limits<int>::max()));
34 children_[kLeftChild] = NULL;
35 children_[kRightChild] = NULL;
36 }
37
CreateRootNode(const size_t * size_vector,size_t num_partitions)38 PartitionTreeNode* PartitionTreeNode::CreateRootNode(const size_t* size_vector,
39 size_t num_partitions) {
40 PartitionTreeNode* root_node = new PartitionTreeNode(
41 NULL, &size_vector[1], num_partitions - 1, size_vector[0]);
42 root_node->set_packet_start(true);
43 return root_node;
44 }
45
~PartitionTreeNode()46 PartitionTreeNode::~PartitionTreeNode() {
47 delete children_[kLeftChild];
48 delete children_[kRightChild];
49 }
50
Cost(size_t penalty)51 int PartitionTreeNode::Cost(size_t penalty) {
52 int cost = 0;
53 if (num_partitions_ == 0) {
54 // This is a solution node.
55 cost = std::max(max_parent_size_, this_size_int()) -
56 std::min(min_parent_size_, this_size_int());
57 } else {
58 cost = std::max(max_parent_size_, this_size_int()) - min_parent_size_;
59 }
60 return cost + NumPackets() * penalty;
61 }
62
CreateChildren(size_t max_size)63 bool PartitionTreeNode::CreateChildren(size_t max_size) {
64 assert(max_size > 0);
65 bool children_created = false;
66 if (num_partitions_ > 0) {
67 if (this_size_ + size_vector_[0] <= max_size) {
68 assert(!children_[kLeftChild]);
69 children_[kLeftChild] =
70 new PartitionTreeNode(this, &size_vector_[1], num_partitions_ - 1,
71 this_size_ + size_vector_[0]);
72 children_[kLeftChild]->set_max_parent_size(max_parent_size_);
73 children_[kLeftChild]->set_min_parent_size(min_parent_size_);
74 // "Left" child is continuation of same packet.
75 children_[kLeftChild]->set_packet_start(false);
76 children_created = true;
77 }
78 if (this_size_ > 0) {
79 assert(!children_[kRightChild]);
80 children_[kRightChild] = new PartitionTreeNode(
81 this, &size_vector_[1], num_partitions_ - 1, size_vector_[0]);
82 children_[kRightChild]->set_max_parent_size(
83 std::max(max_parent_size_, this_size_int()));
84 children_[kRightChild]->set_min_parent_size(
85 std::min(min_parent_size_, this_size_int()));
86 // "Right" child starts a new packet.
87 children_[kRightChild]->set_packet_start(true);
88 children_created = true;
89 }
90 }
91 return children_created;
92 }
93
NumPackets()94 size_t PartitionTreeNode::NumPackets() {
95 if (parent_ == NULL) {
96 // Root node is a "right" child by definition.
97 return 1;
98 }
99 if (parent_->children_[kLeftChild] == this) {
100 // This is a "left" child.
101 return parent_->NumPackets();
102 } else {
103 // This is a "right" child.
104 return 1 + parent_->NumPackets();
105 }
106 }
107
GetOptimalNode(size_t max_size,size_t penalty)108 PartitionTreeNode* PartitionTreeNode::GetOptimalNode(size_t max_size,
109 size_t penalty) {
110 CreateChildren(max_size);
111 PartitionTreeNode* left = children_[kLeftChild];
112 PartitionTreeNode* right = children_[kRightChild];
113 if ((left == NULL) && (right == NULL)) {
114 // This is a solution node; return it.
115 return this;
116 } else if (left == NULL) {
117 // One child empty, return the other.
118 return right->GetOptimalNode(max_size, penalty);
119 } else if (right == NULL) {
120 // One child empty, return the other.
121 return left->GetOptimalNode(max_size, penalty);
122 } else {
123 PartitionTreeNode* first;
124 PartitionTreeNode* second;
125 if (left->Cost(penalty) <= right->Cost(penalty)) {
126 first = left;
127 second = right;
128 } else {
129 first = right;
130 second = left;
131 }
132 first = first->GetOptimalNode(max_size, penalty);
133 if (second->Cost(penalty) <= first->Cost(penalty)) {
134 second = second->GetOptimalNode(max_size, penalty);
135 // Compare cost estimate for "second" with actual cost for "first".
136 if (second->Cost(penalty) < first->Cost(penalty)) {
137 return second;
138 }
139 }
140 return first;
141 }
142 }
143
Vp8PartitionAggregator(const RTPFragmentationHeader & fragmentation,size_t first_partition_idx,size_t last_partition_idx)144 Vp8PartitionAggregator::Vp8PartitionAggregator(
145 const RTPFragmentationHeader& fragmentation,
146 size_t first_partition_idx,
147 size_t last_partition_idx)
148 : root_(NULL),
149 num_partitions_(last_partition_idx - first_partition_idx + 1),
150 size_vector_(new size_t[num_partitions_]),
151 largest_partition_size_(0) {
152 assert(last_partition_idx >= first_partition_idx);
153 assert(last_partition_idx < fragmentation.fragmentationVectorSize);
154 for (size_t i = 0; i < num_partitions_; ++i) {
155 size_vector_[i] =
156 fragmentation.fragmentationLength[i + first_partition_idx];
157 largest_partition_size_ =
158 std::max(largest_partition_size_, size_vector_[i]);
159 }
160 root_ = PartitionTreeNode::CreateRootNode(size_vector_, num_partitions_);
161 }
162
~Vp8PartitionAggregator()163 Vp8PartitionAggregator::~Vp8PartitionAggregator() {
164 delete[] size_vector_;
165 delete root_;
166 }
167
SetPriorMinMax(int min_size,int max_size)168 void Vp8PartitionAggregator::SetPriorMinMax(int min_size, int max_size) {
169 assert(root_);
170 assert(min_size >= 0);
171 assert(max_size >= min_size);
172 root_->set_min_parent_size(min_size);
173 root_->set_max_parent_size(max_size);
174 }
175
176 Vp8PartitionAggregator::ConfigVec
FindOptimalConfiguration(size_t max_size,size_t penalty)177 Vp8PartitionAggregator::FindOptimalConfiguration(size_t max_size,
178 size_t penalty) {
179 assert(root_);
180 assert(max_size >= largest_partition_size_);
181 PartitionTreeNode* opt = root_->GetOptimalNode(max_size, penalty);
182 ConfigVec config_vector(num_partitions_, 0);
183 PartitionTreeNode* temp_node = opt;
184 size_t packet_index = opt->NumPackets();
185 for (size_t i = num_partitions_; i > 0; --i) {
186 assert(packet_index > 0);
187 assert(temp_node != NULL);
188 config_vector[i - 1] = packet_index - 1;
189 if (temp_node->packet_start())
190 --packet_index;
191 temp_node = temp_node->parent();
192 }
193 return config_vector;
194 }
195
CalcMinMax(const ConfigVec & config,int * min_size,int * max_size) const196 void Vp8PartitionAggregator::CalcMinMax(const ConfigVec& config,
197 int* min_size,
198 int* max_size) const {
199 if (*min_size < 0) {
200 *min_size = std::numeric_limits<int>::max();
201 }
202 if (*max_size < 0) {
203 *max_size = 0;
204 }
205 size_t i = 0;
206 while (i < config.size()) {
207 size_t this_size = 0;
208 size_t j = i;
209 while (j < config.size() && config[i] == config[j]) {
210 this_size += size_vector_[j];
211 ++j;
212 }
213 i = j;
214 if (this_size < static_cast<size_t>(*min_size)) {
215 *min_size = this_size;
216 }
217 if (this_size > static_cast<size_t>(*max_size)) {
218 *max_size = this_size;
219 }
220 }
221 }
222
CalcNumberOfFragments(size_t large_partition_size,size_t max_payload_size,size_t penalty,int min_size,int max_size)223 size_t Vp8PartitionAggregator::CalcNumberOfFragments(
224 size_t large_partition_size,
225 size_t max_payload_size,
226 size_t penalty,
227 int min_size,
228 int max_size) {
229 assert(large_partition_size > 0);
230 assert(max_payload_size > 0);
231 assert(min_size != 0);
232 assert(min_size <= max_size);
233 assert(max_size <= static_cast<int>(max_payload_size));
234 // Divisions with rounding up.
235 const size_t min_number_of_fragments =
236 (large_partition_size + max_payload_size - 1) / max_payload_size;
237 if (min_size < 0 || max_size < 0) {
238 // No aggregates produced, so we do not have any size boundaries.
239 // Simply split in as few partitions as possible.
240 return min_number_of_fragments;
241 }
242 const size_t max_number_of_fragments =
243 (large_partition_size + min_size - 1) / min_size;
244 int num_fragments = -1;
245 size_t best_cost = std::numeric_limits<size_t>::max();
246 for (size_t n = min_number_of_fragments; n <= max_number_of_fragments; ++n) {
247 // Round up so that we use the largest fragment.
248 size_t fragment_size = (large_partition_size + n - 1) / n;
249 size_t cost = 0;
250 if (fragment_size < static_cast<size_t>(min_size)) {
251 cost = min_size - fragment_size + n * penalty;
252 } else if (fragment_size > static_cast<size_t>(max_size)) {
253 cost = fragment_size - max_size + n * penalty;
254 } else {
255 cost = n * penalty;
256 }
257 if (fragment_size <= max_payload_size && cost < best_cost) {
258 num_fragments = n;
259 best_cost = cost;
260 }
261 }
262 assert(num_fragments > 0);
263 // TODO(mflodman) Assert disabled since it's falsely triggered, see issue 293.
264 // assert(large_partition_size / num_fragments + 1 <= max_payload_size);
265 return num_fragments;
266 }
267
268 } // namespace webrtc
269