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
19namespace webrtc {
20
21PartitionTreeNode::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
38PartitionTreeNode* 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
46PartitionTreeNode::~PartitionTreeNode() {
47  delete children_[kLeftChild];
48  delete children_[kRightChild];
49}
50
51int 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
63bool 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
94size_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
108PartitionTreeNode* 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
144Vp8PartitionAggregator::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
163Vp8PartitionAggregator::~Vp8PartitionAggregator() {
164  delete[] size_vector_;
165  delete root_;
166}
167
168void 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
176Vp8PartitionAggregator::ConfigVec
177Vp8PartitionAggregator::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
196void 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
223size_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