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