| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (c) 2012 The WebRTC project authors. All Rights Reserved. | 2 * Copyright (c) 2012 The WebRTC project authors. All Rights Reserved. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license | 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 | 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 | 6 * tree. An additional intellectual property rights grant can be found |
| 7 * in the file PATENTS. All contributing project authors may | 7 * in the file PATENTS. All contributing project authors may |
| 8 * be found in the AUTHORS file in the root of the source tree. | 8 * be found in the AUTHORS file in the root of the source tree. |
| 9 */ | 9 */ |
| 10 | 10 |
| (...skipping 19 matching lines...) Expand all Loading... |
| 30 min_parent_size_(std::numeric_limits<int>::max()), | 30 min_parent_size_(std::numeric_limits<int>::max()), |
| 31 packet_start_(false) { | 31 packet_start_(false) { |
| 32 // If |this_size_| > INT_MAX, Cost() and CreateChildren() won't work properly. | 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())); | 33 assert(this_size_ <= static_cast<size_t>(std::numeric_limits<int>::max())); |
| 34 children_[kLeftChild] = NULL; | 34 children_[kLeftChild] = NULL; |
| 35 children_[kRightChild] = NULL; | 35 children_[kRightChild] = NULL; |
| 36 } | 36 } |
| 37 | 37 |
| 38 PartitionTreeNode* PartitionTreeNode::CreateRootNode(const size_t* size_vector, | 38 PartitionTreeNode* PartitionTreeNode::CreateRootNode(const size_t* size_vector, |
| 39 size_t num_partitions) { | 39 size_t num_partitions) { |
| 40 PartitionTreeNode* root_node = | 40 PartitionTreeNode* root_node = new PartitionTreeNode( |
| 41 new PartitionTreeNode(NULL, &size_vector[1], num_partitions - 1, | 41 NULL, &size_vector[1], num_partitions - 1, size_vector[0]); |
| 42 size_vector[0]); | |
| 43 root_node->set_packet_start(true); | 42 root_node->set_packet_start(true); |
| 44 return root_node; | 43 return root_node; |
| 45 } | 44 } |
| 46 | 45 |
| 47 PartitionTreeNode::~PartitionTreeNode() { | 46 PartitionTreeNode::~PartitionTreeNode() { |
| 48 delete children_[kLeftChild]; | 47 delete children_[kLeftChild]; |
| 49 delete children_[kRightChild]; | 48 delete children_[kRightChild]; |
| 50 } | 49 } |
| 51 | 50 |
| 52 int PartitionTreeNode::Cost(size_t penalty) { | 51 int PartitionTreeNode::Cost(size_t penalty) { |
| 53 int cost = 0; | 52 int cost = 0; |
| 54 if (num_partitions_ == 0) { | 53 if (num_partitions_ == 0) { |
| 55 // This is a solution node. | 54 // This is a solution node. |
| 56 cost = std::max(max_parent_size_, this_size_int()) - | 55 cost = std::max(max_parent_size_, this_size_int()) - |
| 57 std::min(min_parent_size_, this_size_int()); | 56 std::min(min_parent_size_, this_size_int()); |
| 58 } else { | 57 } else { |
| 59 cost = std::max(max_parent_size_, this_size_int()) - min_parent_size_; | 58 cost = std::max(max_parent_size_, this_size_int()) - min_parent_size_; |
| 60 } | 59 } |
| 61 return cost + NumPackets() * penalty; | 60 return cost + NumPackets() * penalty; |
| 62 } | 61 } |
| 63 | 62 |
| 64 bool PartitionTreeNode::CreateChildren(size_t max_size) { | 63 bool PartitionTreeNode::CreateChildren(size_t max_size) { |
| 65 assert(max_size > 0); | 64 assert(max_size > 0); |
| 66 bool children_created = false; | 65 bool children_created = false; |
| 67 if (num_partitions_ > 0) { | 66 if (num_partitions_ > 0) { |
| 68 if (this_size_ + size_vector_[0] <= max_size) { | 67 if (this_size_ + size_vector_[0] <= max_size) { |
| 69 assert(!children_[kLeftChild]); | 68 assert(!children_[kLeftChild]); |
| 70 children_[kLeftChild] = | 69 children_[kLeftChild] = |
| 71 new PartitionTreeNode(this, | 70 new PartitionTreeNode(this, &size_vector_[1], num_partitions_ - 1, |
| 72 &size_vector_[1], | |
| 73 num_partitions_ - 1, | |
| 74 this_size_ + size_vector_[0]); | 71 this_size_ + size_vector_[0]); |
| 75 children_[kLeftChild]->set_max_parent_size(max_parent_size_); | 72 children_[kLeftChild]->set_max_parent_size(max_parent_size_); |
| 76 children_[kLeftChild]->set_min_parent_size(min_parent_size_); | 73 children_[kLeftChild]->set_min_parent_size(min_parent_size_); |
| 77 // "Left" child is continuation of same packet. | 74 // "Left" child is continuation of same packet. |
| 78 children_[kLeftChild]->set_packet_start(false); | 75 children_[kLeftChild]->set_packet_start(false); |
| 79 children_created = true; | 76 children_created = true; |
| 80 } | 77 } |
| 81 if (this_size_ > 0) { | 78 if (this_size_ > 0) { |
| 82 assert(!children_[kRightChild]); | 79 assert(!children_[kRightChild]); |
| 83 children_[kRightChild] = new PartitionTreeNode(this, | 80 children_[kRightChild] = new PartitionTreeNode( |
| 84 &size_vector_[1], | 81 this, &size_vector_[1], num_partitions_ - 1, size_vector_[0]); |
| 85 num_partitions_ - 1, | |
| 86 size_vector_[0]); | |
| 87 children_[kRightChild]->set_max_parent_size( | 82 children_[kRightChild]->set_max_parent_size( |
| 88 std::max(max_parent_size_, this_size_int())); | 83 std::max(max_parent_size_, this_size_int())); |
| 89 children_[kRightChild]->set_min_parent_size( | 84 children_[kRightChild]->set_min_parent_size( |
| 90 std::min(min_parent_size_, this_size_int())); | 85 std::min(min_parent_size_, this_size_int())); |
| 91 // "Right" child starts a new packet. | 86 // "Right" child starts a new packet. |
| 92 children_[kRightChild]->set_packet_start(true); | 87 children_[kRightChild]->set_packet_start(true); |
| 93 children_created = true; | 88 children_created = true; |
| 94 } | 89 } |
| 95 } | 90 } |
| 96 return children_created; | 91 return children_created; |
| (...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 141 if (second->Cost(penalty) < first->Cost(penalty)) { | 136 if (second->Cost(penalty) < first->Cost(penalty)) { |
| 142 return second; | 137 return second; |
| 143 } | 138 } |
| 144 } | 139 } |
| 145 return first; | 140 return first; |
| 146 } | 141 } |
| 147 } | 142 } |
| 148 | 143 |
| 149 Vp8PartitionAggregator::Vp8PartitionAggregator( | 144 Vp8PartitionAggregator::Vp8PartitionAggregator( |
| 150 const RTPFragmentationHeader& fragmentation, | 145 const RTPFragmentationHeader& fragmentation, |
| 151 size_t first_partition_idx, size_t last_partition_idx) | 146 size_t first_partition_idx, |
| 147 size_t last_partition_idx) |
| 152 : root_(NULL), | 148 : root_(NULL), |
| 153 num_partitions_(last_partition_idx - first_partition_idx + 1), | 149 num_partitions_(last_partition_idx - first_partition_idx + 1), |
| 154 size_vector_(new size_t[num_partitions_]), | 150 size_vector_(new size_t[num_partitions_]), |
| 155 largest_partition_size_(0) { | 151 largest_partition_size_(0) { |
| 156 assert(last_partition_idx >= first_partition_idx); | 152 assert(last_partition_idx >= first_partition_idx); |
| 157 assert(last_partition_idx < fragmentation.fragmentationVectorSize); | 153 assert(last_partition_idx < fragmentation.fragmentationVectorSize); |
| 158 for (size_t i = 0; i < num_partitions_; ++i) { | 154 for (size_t i = 0; i < num_partitions_; ++i) { |
| 159 size_vector_[i] = | 155 size_vector_[i] = |
| 160 fragmentation.fragmentationLength[i + first_partition_idx]; | 156 fragmentation.fragmentationLength[i + first_partition_idx]; |
| 161 largest_partition_size_ = std::max(largest_partition_size_, | 157 largest_partition_size_ = |
| 162 size_vector_[i]); | 158 std::max(largest_partition_size_, size_vector_[i]); |
| 163 } | 159 } |
| 164 root_ = PartitionTreeNode::CreateRootNode(size_vector_, num_partitions_); | 160 root_ = PartitionTreeNode::CreateRootNode(size_vector_, num_partitions_); |
| 165 } | 161 } |
| 166 | 162 |
| 167 Vp8PartitionAggregator::~Vp8PartitionAggregator() { | 163 Vp8PartitionAggregator::~Vp8PartitionAggregator() { |
| 168 delete [] size_vector_; | 164 delete[] size_vector_; |
| 169 delete root_; | 165 delete root_; |
| 170 } | 166 } |
| 171 | 167 |
| 172 void Vp8PartitionAggregator::SetPriorMinMax(int min_size, int max_size) { | 168 void Vp8PartitionAggregator::SetPriorMinMax(int min_size, int max_size) { |
| 173 assert(root_); | 169 assert(root_); |
| 174 assert(min_size >= 0); | 170 assert(min_size >= 0); |
| 175 assert(max_size >= min_size); | 171 assert(max_size >= min_size); |
| 176 root_->set_min_parent_size(min_size); | 172 root_->set_min_parent_size(min_size); |
| 177 root_->set_max_parent_size(max_size); | 173 root_->set_max_parent_size(max_size); |
| 178 } | 174 } |
| 179 | 175 |
| 180 Vp8PartitionAggregator::ConfigVec | 176 Vp8PartitionAggregator::ConfigVec |
| 181 Vp8PartitionAggregator::FindOptimalConfiguration(size_t max_size, | 177 Vp8PartitionAggregator::FindOptimalConfiguration(size_t max_size, |
| 182 size_t penalty) { | 178 size_t penalty) { |
| 183 assert(root_); | 179 assert(root_); |
| 184 assert(max_size >= largest_partition_size_); | 180 assert(max_size >= largest_partition_size_); |
| 185 PartitionTreeNode* opt = root_->GetOptimalNode(max_size, penalty); | 181 PartitionTreeNode* opt = root_->GetOptimalNode(max_size, penalty); |
| 186 ConfigVec config_vector(num_partitions_, 0); | 182 ConfigVec config_vector(num_partitions_, 0); |
| 187 PartitionTreeNode* temp_node = opt; | 183 PartitionTreeNode* temp_node = opt; |
| 188 size_t packet_index = opt->NumPackets(); | 184 size_t packet_index = opt->NumPackets(); |
| 189 for (size_t i = num_partitions_; i > 0; --i) { | 185 for (size_t i = num_partitions_; i > 0; --i) { |
| 190 assert(packet_index > 0); | 186 assert(packet_index > 0); |
| 191 assert(temp_node != NULL); | 187 assert(temp_node != NULL); |
| 192 config_vector[i - 1] = packet_index - 1; | 188 config_vector[i - 1] = packet_index - 1; |
| 193 if (temp_node->packet_start()) --packet_index; | 189 if (temp_node->packet_start()) |
| 190 --packet_index; |
| 194 temp_node = temp_node->parent(); | 191 temp_node = temp_node->parent(); |
| 195 } | 192 } |
| 196 return config_vector; | 193 return config_vector; |
| 197 } | 194 } |
| 198 | 195 |
| 199 void Vp8PartitionAggregator::CalcMinMax(const ConfigVec& config, | 196 void Vp8PartitionAggregator::CalcMinMax(const ConfigVec& config, |
| 200 int* min_size, int* max_size) const { | 197 int* min_size, |
| 198 int* max_size) const { |
| 201 if (*min_size < 0) { | 199 if (*min_size < 0) { |
| 202 *min_size = std::numeric_limits<int>::max(); | 200 *min_size = std::numeric_limits<int>::max(); |
| 203 } | 201 } |
| 204 if (*max_size < 0) { | 202 if (*max_size < 0) { |
| 205 *max_size = 0; | 203 *max_size = 0; |
| 206 } | 204 } |
| 207 size_t i = 0; | 205 size_t i = 0; |
| 208 while (i < config.size()) { | 206 while (i < config.size()) { |
| 209 size_t this_size = 0; | 207 size_t this_size = 0; |
| 210 size_t j = i; | 208 size_t j = i; |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 256 } else { | 254 } else { |
| 257 cost = n * penalty; | 255 cost = n * penalty; |
| 258 } | 256 } |
| 259 if (fragment_size <= max_payload_size && cost < best_cost) { | 257 if (fragment_size <= max_payload_size && cost < best_cost) { |
| 260 num_fragments = n; | 258 num_fragments = n; |
| 261 best_cost = cost; | 259 best_cost = cost; |
| 262 } | 260 } |
| 263 } | 261 } |
| 264 assert(num_fragments > 0); | 262 assert(num_fragments > 0); |
| 265 // TODO(mflodman) Assert disabled since it's falsely triggered, see issue 293. | 263 // TODO(mflodman) Assert disabled since it's falsely triggered, see issue 293. |
| 266 //assert(large_partition_size / num_fragments + 1 <= max_payload_size); | 264 // assert(large_partition_size / num_fragments + 1 <= max_payload_size); |
| 267 return num_fragments; | 265 return num_fragments; |
| 268 } | 266 } |
| 269 | 267 |
| 270 } // namespace | 268 } // namespace |
| OLD | NEW |