tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

svc_rate_allocator.cc (16742B)

      1 /*
      2 *  Copyright (c) 2018 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 #include "modules/video_coding/svc/svc_rate_allocator.h"
     12 
     13 #include <algorithm>
     14 #include <cmath>
     15 #include <cstddef>
     16 #include <numeric>
     17 #include <optional>
     18 #include <vector>
     19 
     20 #include "absl/container/inlined_vector.h"
     21 #include "api/field_trials_view.h"
     22 #include "api/units/data_rate.h"
     23 #include "api/video/video_bitrate_allocation.h"
     24 #include "api/video/video_bitrate_allocator.h"
     25 #include "api/video/video_codec_constants.h"
     26 #include "api/video/video_codec_type.h"
     27 #include "api/video_codecs/scalability_mode.h"
     28 #include "api/video_codecs/video_codec.h"
     29 #include "modules/video_coding/svc/create_scalability_structure.h"
     30 #include "modules/video_coding/svc/scalable_video_controller.h"
     31 #include "rtc_base/checks.h"
     32 
     33 namespace webrtc {
     34 namespace {
     35 
     36 constexpr float kSpatialLayeringRateScalingFactor = 0.55f;
     37 constexpr float kTemporalLayeringRateScalingFactor = 0.55f;
     38 
     39 struct ActiveSpatialLayers {
     40  size_t first = 0;
     41  size_t num = 0;
     42 };
     43 
     44 ActiveSpatialLayers GetActiveSpatialLayers(const VideoCodec& codec,
     45                                           size_t num_spatial_layers) {
     46  ActiveSpatialLayers active;
     47  for (active.first = 0; active.first < num_spatial_layers; ++active.first) {
     48    if (codec.spatialLayers[active.first].active) {
     49      break;
     50    }
     51  }
     52 
     53  size_t last_active_layer = active.first;
     54  for (; last_active_layer < num_spatial_layers; ++last_active_layer) {
     55    if (!codec.spatialLayers[last_active_layer].active) {
     56      break;
     57    }
     58  }
     59  active.num = last_active_layer - active.first;
     60 
     61  return active;
     62 }
     63 
     64 std::vector<DataRate> AdjustAndVerify(
     65    const VideoCodec& codec,
     66    size_t first_active_layer,
     67    const std::vector<DataRate>& spatial_layer_rates) {
     68  std::vector<DataRate> adjusted_spatial_layer_rates;
     69  // Keep track of rate that couldn't be applied to the previous layer due to
     70  // max bitrate constraint, try to pass it forward to the next one.
     71  DataRate excess_rate = DataRate::Zero();
     72  for (size_t sl_idx = 0; sl_idx < spatial_layer_rates.size(); ++sl_idx) {
     73    DataRate min_rate = DataRate::KilobitsPerSec(
     74        codec.spatialLayers[first_active_layer + sl_idx].minBitrate);
     75    DataRate max_rate = DataRate::KilobitsPerSec(
     76        codec.spatialLayers[first_active_layer + sl_idx].maxBitrate);
     77 
     78    DataRate layer_rate = spatial_layer_rates[sl_idx] + excess_rate;
     79    if (layer_rate < min_rate) {
     80      // Not enough rate to reach min bitrate for desired number of layers,
     81      // abort allocation.
     82      if (spatial_layer_rates.size() == 1) {
     83        return spatial_layer_rates;
     84      }
     85      return adjusted_spatial_layer_rates;
     86    }
     87 
     88    if (layer_rate <= max_rate) {
     89      excess_rate = DataRate::Zero();
     90      adjusted_spatial_layer_rates.push_back(layer_rate);
     91    } else {
     92      excess_rate = layer_rate - max_rate;
     93      adjusted_spatial_layer_rates.push_back(max_rate);
     94    }
     95  }
     96 
     97  return adjusted_spatial_layer_rates;
     98 }
     99 
    100 std::vector<DataRate> SplitBitrate(size_t num_layers,
    101                                   DataRate total_bitrate,
    102                                   float rate_scaling_factor) {
    103  std::vector<DataRate> bitrates;
    104 
    105  double denominator = 0.0;
    106  for (size_t layer_idx = 0; layer_idx < num_layers; ++layer_idx) {
    107    denominator += std::pow(rate_scaling_factor, layer_idx);
    108  }
    109 
    110  double numerator = std::pow(rate_scaling_factor, num_layers - 1);
    111  for (size_t layer_idx = 0; layer_idx < num_layers; ++layer_idx) {
    112    bitrates.push_back(numerator * total_bitrate / denominator);
    113    numerator /= rate_scaling_factor;
    114  }
    115 
    116  const DataRate sum =
    117      std::accumulate(bitrates.begin(), bitrates.end(), DataRate::Zero());
    118 
    119  // Keep the sum of split bitrates equal to the total bitrate by adding or
    120  // subtracting bits, which were lost due to rounding, to the latest layer.
    121  if (total_bitrate > sum) {
    122    bitrates.back() += total_bitrate - sum;
    123  } else if (total_bitrate < sum) {
    124    bitrates.back() -= sum - total_bitrate;
    125  }
    126 
    127  return bitrates;
    128 }
    129 
    130 VideoBitrateAllocation DistributeAllocationToTemporalLayers(
    131    std::vector<DataRate> spatial_layer_birates,
    132    size_t first_active_layer,
    133    size_t num_temporal_layers) {
    134  // Distribute rate across temporal layers. Allocate more bits to lower
    135  // layers since they are used for prediction of higher layers and their
    136  // references are far apart.
    137  VideoBitrateAllocation bitrate_allocation;
    138  for (size_t sl_idx = 0; sl_idx < spatial_layer_birates.size(); ++sl_idx) {
    139    std::vector<DataRate> temporal_layer_bitrates =
    140        SplitBitrate(num_temporal_layers, spatial_layer_birates[sl_idx],
    141                     kTemporalLayeringRateScalingFactor);
    142 
    143    if (num_temporal_layers == 1) {
    144      bitrate_allocation.SetBitrate(sl_idx + first_active_layer, 0,
    145                                    temporal_layer_bitrates[0].bps());
    146    } else if (num_temporal_layers == 2) {
    147      bitrate_allocation.SetBitrate(sl_idx + first_active_layer, 0,
    148                                    temporal_layer_bitrates[1].bps());
    149      bitrate_allocation.SetBitrate(sl_idx + first_active_layer, 1,
    150                                    temporal_layer_bitrates[0].bps());
    151    } else {
    152      RTC_CHECK_EQ(num_temporal_layers, 3);
    153      // In case of three temporal layers the high layer has two frames and the
    154      // middle layer has one frame within GOP (in between two consecutive low
    155      // layer frames). Thus high layer requires more bits (comparing pure
    156      // bitrate of layer, excluding bitrate of base layers) to keep quality on
    157      // par with lower layers.
    158      bitrate_allocation.SetBitrate(sl_idx + first_active_layer, 0,
    159                                    temporal_layer_bitrates[2].bps());
    160      bitrate_allocation.SetBitrate(sl_idx + first_active_layer, 1,
    161                                    temporal_layer_bitrates[0].bps());
    162      bitrate_allocation.SetBitrate(sl_idx + first_active_layer, 2,
    163                                    temporal_layer_bitrates[1].bps());
    164    }
    165  }
    166 
    167  return bitrate_allocation;
    168 }
    169 
    170 // Returns the minimum bitrate needed for `num_active_layers` spatial layers to
    171 // become active using the configuration specified by `codec`.
    172 DataRate FindLayerTogglingThreshold(const VideoCodec& codec,
    173                                    size_t first_active_layer,
    174                                    size_t num_active_layers) {
    175  if (num_active_layers == 1) {
    176    return DataRate::KilobitsPerSec(codec.spatialLayers[0].minBitrate);
    177  }
    178 
    179  if (codec.mode == VideoCodecMode::kRealtimeVideo) {
    180    DataRate lower_bound = DataRate::Zero();
    181    DataRate upper_bound = DataRate::Zero();
    182    if (num_active_layers > 1) {
    183      for (size_t i = 0; i < num_active_layers - 1; ++i) {
    184        lower_bound += DataRate::KilobitsPerSec(
    185            codec.spatialLayers[first_active_layer + i].minBitrate);
    186        upper_bound += DataRate::KilobitsPerSec(
    187            codec.spatialLayers[first_active_layer + i].maxBitrate);
    188      }
    189    }
    190    upper_bound += DataRate::KilobitsPerSec(
    191        codec.spatialLayers[first_active_layer + num_active_layers - 1]
    192            .minBitrate);
    193 
    194    // Do a binary search until upper and lower bound is the highest bitrate for
    195    // `num_active_layers` - 1 layers and lowest bitrate for `num_active_layers`
    196    // layers respectively.
    197    while (upper_bound - lower_bound > DataRate::BitsPerSec(1)) {
    198      DataRate try_rate = (lower_bound + upper_bound) / 2;
    199      if (AdjustAndVerify(codec, first_active_layer,
    200                          SplitBitrate(num_active_layers, try_rate,
    201                                       kSpatialLayeringRateScalingFactor))
    202              .size() == num_active_layers) {
    203        upper_bound = try_rate;
    204      } else {
    205        lower_bound = try_rate;
    206      }
    207    }
    208    return upper_bound;
    209  } else {
    210    DataRate toggling_rate = DataRate::Zero();
    211    for (size_t i = 0; i < num_active_layers - 1; ++i) {
    212      toggling_rate += DataRate::KilobitsPerSec(
    213          codec.spatialLayers[first_active_layer + i].targetBitrate);
    214    }
    215    toggling_rate += DataRate::KilobitsPerSec(
    216        codec.spatialLayers[first_active_layer + num_active_layers - 1]
    217            .minBitrate);
    218    return toggling_rate;
    219  }
    220 }
    221 
    222 }  // namespace
    223 
    224 SvcRateAllocator::NumLayers SvcRateAllocator::GetNumLayers(
    225    const VideoCodec& codec) {
    226  NumLayers layers;
    227  if (std::optional<ScalabilityMode> scalability_mode =
    228          codec.GetScalabilityMode();
    229      scalability_mode.has_value()) {
    230    if (auto structure = CreateScalabilityStructure(*scalability_mode)) {
    231      ScalableVideoController::StreamLayersConfig config =
    232          structure->StreamConfig();
    233      layers.spatial = config.num_spatial_layers;
    234      layers.temporal = config.num_temporal_layers;
    235      return layers;
    236    }
    237  }
    238  if (codec.codecType == kVideoCodecVP9) {
    239    layers.spatial = codec.VP9().numberOfSpatialLayers;
    240    layers.temporal = codec.VP9().numberOfTemporalLayers;
    241    return layers;
    242  }
    243  layers.spatial = 1;
    244  layers.temporal = 1;
    245  return layers;
    246 }
    247 
    248 SvcRateAllocator::SvcRateAllocator(const VideoCodec& codec,
    249                                   const FieldTrialsView& field_trials)
    250    : codec_(codec),
    251      num_layers_(GetNumLayers(codec)),
    252      cumulative_layer_start_bitrates_(GetLayerStartBitrates(codec)),
    253      last_active_layer_count_(0) {
    254  RTC_DCHECK_GT(num_layers_.spatial, 0);
    255  RTC_DCHECK_LE(num_layers_.spatial, kMaxSpatialLayers);
    256  RTC_DCHECK_GT(num_layers_.temporal, 0);
    257  RTC_DCHECK_LE(num_layers_.temporal, 3);
    258  for (size_t layer_idx = 0; layer_idx < num_layers_.spatial; ++layer_idx) {
    259    // Verify min <= target <= max.
    260    if (codec.spatialLayers[layer_idx].active) {
    261      RTC_DCHECK_GT(codec.spatialLayers[layer_idx].maxBitrate, 0);
    262      RTC_DCHECK_GE(codec.spatialLayers[layer_idx].maxBitrate,
    263                    codec.spatialLayers[layer_idx].minBitrate);
    264      RTC_DCHECK_GE(codec.spatialLayers[layer_idx].targetBitrate,
    265                    codec.spatialLayers[layer_idx].minBitrate);
    266      RTC_DCHECK_GE(codec.spatialLayers[layer_idx].maxBitrate,
    267                    codec.spatialLayers[layer_idx].targetBitrate);
    268    }
    269  }
    270 }
    271 
    272 VideoBitrateAllocation SvcRateAllocator::Allocate(
    273    VideoBitrateAllocationParameters parameters) {
    274  DataRate total_bitrate = parameters.total_bitrate;
    275  if (codec_.maxBitrate != 0) {
    276    total_bitrate =
    277        std::min(total_bitrate, DataRate::KilobitsPerSec(codec_.maxBitrate));
    278  }
    279 
    280  if (codec_.spatialLayers[0].targetBitrate == 0) {
    281    // Delegate rate distribution to encoder wrapper if bitrate thresholds
    282    // are not set.
    283    VideoBitrateAllocation bitrate_allocation;
    284    bitrate_allocation.SetBitrate(0, 0, total_bitrate.bps());
    285    return bitrate_allocation;
    286  }
    287 
    288  const ActiveSpatialLayers active_layers =
    289      GetActiveSpatialLayers(codec_, num_layers_.spatial);
    290  size_t num_spatial_layers = active_layers.num;
    291 
    292  if (num_spatial_layers == 0) {
    293    return VideoBitrateAllocation();  // All layers are deactivated.
    294  }
    295 
    296  // Figure out how many spatial layers should be active.
    297  num_spatial_layers = FindNumEnabledLayers(total_bitrate);
    298  last_active_layer_count_ = num_spatial_layers;
    299 
    300  std::vector<DataRate> spatial_layer_bitrates;
    301  if (codec_.mode == VideoCodecMode::kRealtimeVideo) {
    302    spatial_layer_bitrates = DistributeAllocationToSpatialLayersNormalVideo(
    303        total_bitrate, active_layers.first, num_spatial_layers);
    304  } else {
    305    spatial_layer_bitrates = DistributeAllocationToSpatialLayersScreenSharing(
    306        total_bitrate, active_layers.first, num_spatial_layers);
    307  }
    308 
    309  VideoBitrateAllocation allocation = DistributeAllocationToTemporalLayers(
    310      spatial_layer_bitrates, active_layers.first, num_layers_.temporal);
    311 
    312  allocation.set_bw_limited(num_spatial_layers < active_layers.num);
    313  return allocation;
    314 }
    315 
    316 std::vector<DataRate>
    317 SvcRateAllocator::DistributeAllocationToSpatialLayersNormalVideo(
    318    DataRate total_bitrate,
    319    size_t first_active_layer,
    320    size_t num_spatial_layers) const {
    321  std::vector<DataRate> spatial_layer_rates;
    322  if (num_spatial_layers == 0) {
    323    // Not enough rate for even the base layer. Force allocation at the total
    324    // bitrate anyway.
    325    num_spatial_layers = 1;
    326    spatial_layer_rates.push_back(total_bitrate);
    327    return spatial_layer_rates;
    328  }
    329 
    330  spatial_layer_rates =
    331      AdjustAndVerify(codec_, first_active_layer,
    332                      SplitBitrate(num_spatial_layers, total_bitrate,
    333                                   kSpatialLayeringRateScalingFactor));
    334  RTC_DCHECK_EQ(spatial_layer_rates.size(), num_spatial_layers);
    335  return spatial_layer_rates;
    336 }
    337 
    338 // Bit-rate is allocated in such a way, that the highest enabled layer will have
    339 // between min and max bitrate, and all others will have exactly target
    340 // bit-rate allocated.
    341 std::vector<DataRate>
    342 SvcRateAllocator::DistributeAllocationToSpatialLayersScreenSharing(
    343    DataRate total_bitrate,
    344    size_t first_active_layer,
    345    size_t num_spatial_layers) const {
    346  std::vector<DataRate> spatial_layer_rates;
    347  if (num_spatial_layers == 0 ||
    348      total_bitrate <
    349          DataRate::KilobitsPerSec(
    350              codec_.spatialLayers[first_active_layer].minBitrate)) {
    351    // Always enable at least one layer.
    352    spatial_layer_rates.push_back(total_bitrate);
    353    return spatial_layer_rates;
    354  }
    355 
    356  DataRate allocated_rate = DataRate::Zero();
    357  DataRate top_layer_rate = DataRate::Zero();
    358  size_t sl_idx;
    359  for (sl_idx = first_active_layer;
    360       sl_idx < first_active_layer + num_spatial_layers; ++sl_idx) {
    361    const DataRate min_rate =
    362        DataRate::KilobitsPerSec(codec_.spatialLayers[sl_idx].minBitrate);
    363    const DataRate target_rate =
    364        DataRate::KilobitsPerSec(codec_.spatialLayers[sl_idx].targetBitrate);
    365 
    366    if (allocated_rate + min_rate > total_bitrate) {
    367      // Use stable rate to determine if layer should be enabled.
    368      break;
    369    }
    370 
    371    top_layer_rate = std::min(target_rate, total_bitrate - allocated_rate);
    372    spatial_layer_rates.push_back(top_layer_rate);
    373    allocated_rate += top_layer_rate;
    374  }
    375 
    376  if (sl_idx > 0 && total_bitrate - allocated_rate > DataRate::Zero()) {
    377    // Add leftover to the last allocated layer.
    378    top_layer_rate = std::min(
    379        top_layer_rate + (total_bitrate - allocated_rate),
    380        DataRate::KilobitsPerSec(codec_.spatialLayers[sl_idx - 1].maxBitrate));
    381    spatial_layer_rates.back() = top_layer_rate;
    382  }
    383 
    384  return spatial_layer_rates;
    385 }
    386 
    387 size_t SvcRateAllocator::FindNumEnabledLayers(DataRate target_rate) const {
    388  if (cumulative_layer_start_bitrates_.empty()) {
    389    return 0;
    390  }
    391 
    392  size_t num_enabled_layers = 0;
    393  for (DataRate start_rate : cumulative_layer_start_bitrates_) {
    394    // First layer is always enabled.
    395    if (num_enabled_layers == 0 || start_rate <= target_rate) {
    396      ++num_enabled_layers;
    397    } else {
    398      break;
    399    }
    400  }
    401 
    402  return num_enabled_layers;
    403 }
    404 
    405 DataRate SvcRateAllocator::GetMaxBitrate(const VideoCodec& codec) {
    406  const NumLayers num_layers = GetNumLayers(codec);
    407  const ActiveSpatialLayers active_layers =
    408      GetActiveSpatialLayers(codec, num_layers.spatial);
    409 
    410  DataRate max_bitrate = DataRate::Zero();
    411  for (size_t sl_idx = 0; sl_idx < active_layers.num; ++sl_idx) {
    412    max_bitrate += DataRate::KilobitsPerSec(
    413        codec.spatialLayers[active_layers.first + sl_idx].maxBitrate);
    414  }
    415 
    416  if (codec.maxBitrate != 0) {
    417    max_bitrate =
    418        std::min(max_bitrate, DataRate::KilobitsPerSec(codec.maxBitrate));
    419  }
    420 
    421  return max_bitrate;
    422 }
    423 
    424 DataRate SvcRateAllocator::GetPaddingBitrate(const VideoCodec& codec) {
    425  auto start_bitrate = GetLayerStartBitrates(codec);
    426  if (start_bitrate.empty()) {
    427    return DataRate::Zero();  // All layers are deactivated.
    428  }
    429 
    430  return start_bitrate.back();
    431 }
    432 
    433 absl::InlinedVector<DataRate, kMaxSpatialLayers>
    434 SvcRateAllocator::GetLayerStartBitrates(const VideoCodec& codec) {
    435  absl::InlinedVector<DataRate, kMaxSpatialLayers> start_bitrates;
    436  const NumLayers num_layers = GetNumLayers(codec);
    437  const ActiveSpatialLayers active_layers =
    438      GetActiveSpatialLayers(codec, num_layers.spatial);
    439  DataRate last_rate = DataRate::Zero();
    440  for (size_t i = 1; i <= active_layers.num; ++i) {
    441    DataRate layer_toggling_rate =
    442        FindLayerTogglingThreshold(codec, active_layers.first, i);
    443    start_bitrates.push_back(layer_toggling_rate);
    444    RTC_DCHECK_LE(last_rate, layer_toggling_rate);
    445    last_rate = layer_toggling_rate;
    446  }
    447  return start_bitrates;
    448 }
    449 
    450 }  // namespace webrtc