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