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 19namespace webrtc { 20 21PartitionTreeNode::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 38PartitionTreeNode* 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 46PartitionTreeNode::~PartitionTreeNode() { 47 delete children_[kLeftChild]; 48 delete children_[kRightChild]; 49} 50 51int 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 63bool 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 94size_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 108PartitionTreeNode* 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 144Vp8PartitionAggregator::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 163Vp8PartitionAggregator::~Vp8PartitionAggregator() { 164 delete[] size_vector_; 165 delete root_; 166} 167 168void 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 176Vp8PartitionAggregator::ConfigVec 177Vp8PartitionAggregator::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 196void 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 223size_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