| OLD | NEW |
|---|
| (Empty) |
| 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 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 | |
| 38 PartitionTreeNode* 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 | |
| 46 PartitionTreeNode::~PartitionTreeNode() { | |
| 47 delete children_[kLeftChild]; | |
| 48 delete children_[kRightChild]; | |
| 49 } | |
| 50 | |
| 51 int 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 | |
| 63 bool 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 | |
| 94 size_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 | |
| 108 PartitionTreeNode* 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 | |
| 144 Vp8PartitionAggregator::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 | |
| 163 Vp8PartitionAggregator::~Vp8PartitionAggregator() { | |
| 164 delete[] size_vector_; | |
| 165 delete root_; | |
| 166 } | |
| 167 | |
| 168 void 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 | |
| 176 Vp8PartitionAggregator::ConfigVec | |
| 177 Vp8PartitionAggregator::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 | |
| 196 void 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 | |
| 223 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 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2871173008:
Fix packetization logic to leave space for extensions in the last packet (Closed)
