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