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 int* size_vector,
23                                     int num_partitions,
24                                     int 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  assert(num_partitions >= 0);
33  children_[kLeftChild] = NULL;
34  children_[kRightChild] = NULL;
35}
36
37PartitionTreeNode* PartitionTreeNode::CreateRootNode(const int* size_vector,
38                                                     int num_partitions) {
39  PartitionTreeNode* root_node =
40      new PartitionTreeNode(NULL, &size_vector[1], num_partitions - 1,
41                            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(int penalty) {
52  assert(penalty >= 0);
53  int cost = 0;
54  if (num_partitions_ == 0) {
55    // This is a solution node.
56    cost = std::max(max_parent_size_, this_size_) -
57        std::min(min_parent_size_, this_size_);
58  } else {
59    cost = std::max(max_parent_size_, this_size_) - min_parent_size_;
60  }
61  return cost + NumPackets() * penalty;
62}
63
64bool PartitionTreeNode::CreateChildren(int max_size) {
65  assert(max_size > 0);
66  bool children_created = false;
67  if (num_partitions_ > 0) {
68    if (this_size_ + size_vector_[0] <= max_size) {
69      assert(!children_[kLeftChild]);
70      children_[kLeftChild] =
71          new PartitionTreeNode(this,
72                                &size_vector_[1],
73                                num_partitions_ - 1,
74                                this_size_ + size_vector_[0]);
75      children_[kLeftChild]->set_max_parent_size(max_parent_size_);
76      children_[kLeftChild]->set_min_parent_size(min_parent_size_);
77      // "Left" child is continuation of same packet.
78      children_[kLeftChild]->set_packet_start(false);
79      children_created = true;
80    }
81    if (this_size_ > 0) {
82      assert(!children_[kRightChild]);
83      children_[kRightChild] = new PartitionTreeNode(this,
84                                                     &size_vector_[1],
85                                                     num_partitions_ - 1,
86                                                     size_vector_[0]);
87      children_[kRightChild]->set_max_parent_size(
88          std::max(max_parent_size_, this_size_));
89      children_[kRightChild]->set_min_parent_size(
90          std::min(min_parent_size_, this_size_));
91      // "Right" child starts a new packet.
92      children_[kRightChild]->set_packet_start(true);
93      children_created = true;
94    }
95  }
96  return children_created;
97}
98
99int PartitionTreeNode::NumPackets() {
100  if (parent_ == NULL) {
101    // Root node is a "right" child by definition.
102    return 1;
103  }
104  if (parent_->children_[kLeftChild] == this) {
105    // This is a "left" child.
106    return parent_->NumPackets();
107  } else {
108    // This is a "right" child.
109    return 1 + parent_->NumPackets();
110  }
111}
112
113PartitionTreeNode* PartitionTreeNode::GetOptimalNode(int max_size,
114                                                     int penalty) {
115  CreateChildren(max_size);
116  PartitionTreeNode* left = children_[kLeftChild];
117  PartitionTreeNode* right = children_[kRightChild];
118  if ((left == NULL) && (right == NULL)) {
119    // This is a solution node; return it.
120    return this;
121  } else if (left == NULL) {
122    // One child empty, return the other.
123    return right->GetOptimalNode(max_size, penalty);
124  } else if (right == NULL) {
125    // One child empty, return the other.
126    return left->GetOptimalNode(max_size, penalty);
127  } else {
128    PartitionTreeNode* first;
129    PartitionTreeNode* second;
130    if (left->Cost(penalty) <= right->Cost(penalty)) {
131      first = left;
132      second = right;
133    } else {
134      first = right;
135      second = left;
136    }
137    first = first->GetOptimalNode(max_size, penalty);
138    if (second->Cost(penalty) <= first->Cost(penalty)) {
139      second = second->GetOptimalNode(max_size, penalty);
140      // Compare cost estimate for "second" with actual cost for "first".
141      if (second->Cost(penalty) < first->Cost(penalty)) {
142        return second;
143      }
144    }
145    return first;
146  }
147}
148
149Vp8PartitionAggregator::Vp8PartitionAggregator(
150    const RTPFragmentationHeader& fragmentation,
151    int first_partition_idx, int last_partition_idx)
152    : root_(NULL),
153      num_partitions_(last_partition_idx - first_partition_idx + 1),
154      size_vector_(new int[num_partitions_]),
155      largest_partition_size_(0) {
156  assert(first_partition_idx >= 0);
157  assert(last_partition_idx >= first_partition_idx);
158  assert(last_partition_idx < fragmentation.fragmentationVectorSize);
159  for (size_t i = 0; i < num_partitions_; ++i) {
160    size_vector_[i] =
161        fragmentation.fragmentationLength[i + first_partition_idx];
162    largest_partition_size_ = std::max(largest_partition_size_,
163                                       size_vector_[i]);
164  }
165  root_ = PartitionTreeNode::CreateRootNode(size_vector_, num_partitions_);
166}
167
168Vp8PartitionAggregator::~Vp8PartitionAggregator() {
169  delete [] size_vector_;
170  delete root_;
171}
172
173void Vp8PartitionAggregator::SetPriorMinMax(int min_size, int max_size) {
174  assert(root_);
175  assert(min_size >= 0);
176  assert(max_size >= min_size);
177  root_->set_min_parent_size(min_size);
178  root_->set_max_parent_size(max_size);
179}
180
181Vp8PartitionAggregator::ConfigVec
182Vp8PartitionAggregator::FindOptimalConfiguration(int max_size, int penalty) {
183  assert(root_);
184  assert(max_size >= largest_partition_size_);
185  PartitionTreeNode* opt = root_->GetOptimalNode(max_size, penalty);
186  ConfigVec config_vector(num_partitions_, 0);
187  PartitionTreeNode* temp_node = opt;
188  int packet_index = opt->NumPackets() - 1;
189  for (int i = num_partitions_ - 1; i >= 0; --i) {
190    assert(packet_index >= 0);
191    assert(temp_node != NULL);
192    config_vector[i] = packet_index;
193    if (temp_node->packet_start()) --packet_index;
194    temp_node = temp_node->parent();
195  }
196  return config_vector;
197}
198
199void Vp8PartitionAggregator::CalcMinMax(const ConfigVec& config,
200                                        int* min_size, int* max_size) const {
201  if (*min_size < 0) {
202    *min_size = std::numeric_limits<int>::max();
203  }
204  if (*max_size < 0) {
205    *max_size = 0;
206  }
207  unsigned int i = 0;
208  while (i < config.size()) {
209    int this_size = 0;
210    unsigned int j = i;
211    while (j < config.size() && config[i] == config[j]) {
212      this_size += size_vector_[j];
213      ++j;
214    }
215    i = j;
216    if (this_size < *min_size) {
217      *min_size = this_size;
218    }
219    if (this_size > *max_size) {
220      *max_size = this_size;
221    }
222  }
223}
224
225int Vp8PartitionAggregator::CalcNumberOfFragments(int large_partition_size,
226                                                  int max_payload_size,
227                                                  int penalty,
228                                                  int min_size,
229                                                  int max_size) {
230  assert(max_size <= max_payload_size);
231  assert(min_size <= max_size);
232  assert(max_payload_size > 0);
233  // Divisions with rounding up.
234  const int min_number_of_fragments =
235      (large_partition_size + max_payload_size - 1) / max_payload_size;
236  if (min_size < 0 || max_size < 0) {
237    // No aggregates produced, so we do not have any size boundaries.
238    // Simply split in as few partitions as possible.
239    return min_number_of_fragments;
240  }
241  const int max_number_of_fragments =
242      (large_partition_size + min_size - 1) / min_size;
243  int num_fragments = -1;
244  int best_cost = std::numeric_limits<int>::max();
245  for (int n = min_number_of_fragments; n <= max_number_of_fragments; ++n) {
246    // Round up so that we use the largest fragment.
247    int fragment_size = (large_partition_size + n - 1) / n;
248    int cost = 0;
249    if (fragment_size < min_size) {
250      cost = min_size - fragment_size + n * penalty;
251    } else if (fragment_size > max_size) {
252      cost = fragment_size - max_size + n * penalty;
253    } else {
254      cost = n * penalty;
255    }
256    if (fragment_size <= max_payload_size && cost < best_cost) {
257      num_fragments = n;
258      best_cost = cost;
259    }
260  }
261  assert(num_fragments > 0);
262  // TODO(mflodman) Assert disabled since it's falsely triggered, see issue 293.
263  //assert(large_partition_size / num_fragments + 1 <= max_payload_size);
264  return num_fragments;
265}
266
267}  // namespace
268