• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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