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