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