| 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 |