Home | History | Annotate | Download | only in source 
      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
    269