1/*
2 *  Copyright (c) 2011 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#ifndef WEBRTC_MODULES_RTP_RTCP_SOURCE_VP8_PARTITION_AGGREGATOR_H_
12#define WEBRTC_MODULES_RTP_RTCP_SOURCE_VP8_PARTITION_AGGREGATOR_H_
13
14#include <vector>
15
16#include "webrtc/base/constructormagic.h"
17#include "webrtc/modules/interface/module_common_types.h"
18#include "webrtc/typedefs.h"
19
20namespace webrtc {
21
22// Class used to solve the VP8 aggregation problem.
23class PartitionTreeNode {
24 public:
25  // Create a tree node.
26  PartitionTreeNode(PartitionTreeNode* parent,
27                    const int* size_vector,
28                    int num_partitions,
29                    int this_size);
30
31  // Create a root node.
32  static PartitionTreeNode* CreateRootNode(const int* size_vector,
33                                           int num_partitions);
34
35  ~PartitionTreeNode();
36
37  // Calculate the cost for the node. If the node is a solution node, the cost
38  // will be the actual cost associated with that solution. If not, the cost
39  // will be the cost accumulated so far along the current branch (which is a
40  // lower bound for any solution along the branch).
41  int Cost(int penalty);
42
43  // Create the two children for this node.
44  bool CreateChildren(int max_size);
45
46  // Get the number of packets for the configuration that this node represents.
47  int NumPackets();
48
49  // Find the optimal solution given a maximum packet size and a per-packet
50  // penalty. The method will be recursively called while the solver is
51  // probing down the tree of nodes.
52  PartitionTreeNode* GetOptimalNode(int max_size, int penalty);
53
54  // Setters and getters.
55  void set_max_parent_size(int size) { max_parent_size_ = size; }
56  void set_min_parent_size(int size) { min_parent_size_ = size; }
57  PartitionTreeNode* parent() const { return parent_; }
58  PartitionTreeNode* left_child() const { return children_[kLeftChild]; }
59  PartitionTreeNode* right_child() const { return children_[kRightChild]; }
60  int this_size() const { return this_size_; }
61  bool packet_start() const { return packet_start_; }
62
63 private:
64  enum Children {
65    kLeftChild = 0,
66    kRightChild = 1
67  };
68
69  void set_packet_start(bool value) { packet_start_ = value; }
70
71  PartitionTreeNode* parent_;
72  PartitionTreeNode* children_[2];
73  int this_size_;
74  const int* size_vector_;
75  int num_partitions_;
76  int max_parent_size_;
77  int min_parent_size_;
78  bool packet_start_;
79
80  DISALLOW_COPY_AND_ASSIGN(PartitionTreeNode);
81};
82
83// Class that calculates the optimal aggregation of VP8 partitions smaller than
84// the maximum packet size.
85class Vp8PartitionAggregator {
86 public:
87  typedef std::vector<int> ConfigVec;
88
89  // Constructor. All partitions in the fragmentation header from index
90  // first_partition_idx to last_partition_idx must be smaller than
91  // maximum packet size to be used in FindOptimalConfiguration.
92  Vp8PartitionAggregator(const RTPFragmentationHeader& fragmentation,
93                         int first_partition_idx, int last_partition_idx);
94
95  ~Vp8PartitionAggregator();
96
97  // Set the smallest and largest payload sizes produces so far.
98  void SetPriorMinMax(int min_size, int max_size);
99
100  // Find the aggregation of VP8 partitions that produces the smallest cost.
101  // The result is given as a vector of the same length as the number of
102  // partitions given to the constructor (i.e., last_partition_idx -
103  // first_partition_idx + 1), where each element indicates the packet index
104  // for that partition. Thus, the output vector starts at 0 and is increasing
105  // up to the number of packets - 1.
106  ConfigVec FindOptimalConfiguration(int max_size, int penalty);
107
108  // Calculate minimum and maximum packet sizes for a given aggregation config.
109  // The extreme packet sizes of the given aggregation are compared with the
110  // values given in min_size and max_size, and if either of these are exceeded,
111  // the new extreme value will be written to the corresponding variable.
112  void CalcMinMax(const ConfigVec& config, int* min_size, int* max_size) const;
113
114  // Calculate the number of fragments to divide a large partition into.
115  // The large partition is of size large_partition_size. The payload must not
116  // be larger than max_payload_size. Each fragment comes at an overhead cost
117  // of penalty bytes. If the size of the fragments fall outside the range
118  // [min_size, max_size], an extra cost is inflicted.
119  static int CalcNumberOfFragments(int large_partition_size,
120                                   int max_payload_size,
121                                   int penalty,
122                                   int min_size,
123                                   int max_size);
124
125 private:
126  PartitionTreeNode* root_;
127  size_t num_partitions_;
128  int* size_vector_;
129  int largest_partition_size_;
130
131  DISALLOW_COPY_AND_ASSIGN(Vp8PartitionAggregator);
132};
133}  // namespace
134
135#endif  // WEBRTC_MODULES_RTP_RTCP_SOURCE_VP8_PARTITION_AGGREGATOR_H_
136