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 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 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 46 PartitionTreeNode::~PartitionTreeNode() { 47 delete children_[kLeftChild]; 48 delete children_[kRightChild]; 49 } 50 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 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 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 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 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 168 Vp8PartitionAggregator::~Vp8PartitionAggregator() { 169 delete [] size_vector_; 170 delete root_; 171 } 172 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 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 199 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 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
