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. set_max_parent_size(int size)55 void set_max_parent_size(int size) { max_parent_size_ = size; } set_min_parent_size(int size)56 void set_min_parent_size(int size) { min_parent_size_ = size; } parent()57 PartitionTreeNode* parent() const { return parent_; } left_child()58 PartitionTreeNode* left_child() const { return children_[kLeftChild]; } right_child()59 PartitionTreeNode* right_child() const { return children_[kRightChild]; } this_size()60 size_t this_size() const { return this_size_; } packet_start()61 bool packet_start() const { return packet_start_; } 62 63 private: 64 enum Children { 65 kLeftChild = 0, 66 kRightChild = 1 67 }; 68 this_size_int()69 int this_size_int() const { return static_cast<int>(this_size_); } set_packet_start(bool value)70 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_ 138