tor-browser

tmmbr_help.cc (6325B)

---

/*
*  Copyright (c) 2012 The WebRTC project authors. All Rights Reserved.
*
*  Use of this source code is governed by a BSD-style license
*  that can be found in the LICENSE file in the root of the source
*  tree. An additional intellectual property rights grant can be found
*  in the file PATENTS.  All contributing project authors may
*  be found in the AUTHORS file in the root of the source tree.
*/

#include "modules/rtp_rtcp/source/tmmbr_help.h"

#include <cstddef>
#include <cstdint>
#include <limits>
#include <vector>

#include "absl/algorithm/container.h"
#include "modules/rtp_rtcp/source/rtcp_packet/tmmb_item.h"
#include "rtc_base/checks.h"

namespace webrtc {
std::vector<rtcp::TmmbItem> TMMBRHelp::FindBoundingSet(
   std::vector<rtcp::TmmbItem> candidates) {
 // Filter out candidates with 0 bitrate.
 for (auto it = candidates.begin(); it != candidates.end();) {
   if (!it->bitrate_bps())
     it = candidates.erase(it);
   else
     ++it;
 }

 if (candidates.size() <= 1)
   return candidates;

 size_t num_candidates = candidates.size();

 // 1. Sort by increasing packet overhead.
 absl::c_sort(candidates,
              [](const rtcp::TmmbItem& lhs, const rtcp::TmmbItem& rhs) {
                return lhs.packet_overhead() < rhs.packet_overhead();
              });

 // 2. For tuples with same overhead, keep the one with the lowest bitrate.
 for (auto it = candidates.begin(); it != candidates.end();) {
   RTC_DCHECK(it->bitrate_bps());
   auto current_min = it;
   auto next_it = it + 1;
   // Use fact candidates are sorted by overhead, so candidates with same
   // overhead are adjusted.
   while (next_it != candidates.end() &&
          next_it->packet_overhead() == current_min->packet_overhead()) {
     if (next_it->bitrate_bps() < current_min->bitrate_bps()) {
       current_min->set_bitrate_bps(0);
       current_min = next_it;
     } else {
       next_it->set_bitrate_bps(0);
     }
     ++next_it;
     --num_candidates;
   }
   it = next_it;
 }

 // 3. Select and remove tuple with lowest bitrate.
 // (If more than 1, choose the one with highest overhead).
 auto min_bitrate_it = candidates.end();
 for (auto it = candidates.begin(); it != candidates.end(); ++it) {
   if (it->bitrate_bps()) {
     min_bitrate_it = it;
     break;
   }
 }

 for (auto it = min_bitrate_it; it != candidates.end(); ++it) {
   if (it->bitrate_bps() &&
       it->bitrate_bps() <= min_bitrate_it->bitrate_bps()) {
     // Get min bitrate.
     min_bitrate_it = it;
   }
 }

 std::vector<rtcp::TmmbItem> bounding_set;
 bounding_set.reserve(num_candidates);
 std::vector<float> intersection(num_candidates);
 std::vector<float> max_packet_rate(num_candidates);

 // First member of selected list.
 bounding_set.push_back(*min_bitrate_it);
 intersection[0] = 0;
 // Calculate its maximum packet rate (where its line crosses x-axis).
 if (bounding_set.back().packet_overhead() == 0) {
   // Avoid division by zero.
   max_packet_rate[0] = std::numeric_limits<float>::max();
 } else {
   max_packet_rate[0] =
       bounding_set.back().bitrate_bps() /
       static_cast<float>(bounding_set.back().packet_overhead());
 }
 // Remove from candidate list.
 min_bitrate_it->set_bitrate_bps(0);
 --num_candidates;

 // 4. Discard from candidate list all tuple with lower overhead
 // (next tuple must be steeper).
 for (auto it = candidates.begin(); it != candidates.end(); ++it) {
   if (it->bitrate_bps() &&
       it->packet_overhead() < bounding_set.front().packet_overhead()) {
     it->set_bitrate_bps(0);
     --num_candidates;
   }
 }

 bool get_new_candidate = true;
 rtcp::TmmbItem cur_candidate;
 while (num_candidates > 0) {
   if (get_new_candidate) {
     // 5. Remove first remaining tuple from candidate list.
     for (auto it = candidates.begin(); it != candidates.end(); ++it) {
       if (it->bitrate_bps()) {
         cur_candidate = *it;
         it->set_bitrate_bps(0);
         break;
       }
     }
   }

   // 6. Calculate packet rate and intersection of the current
   // line with line of last tuple in selected list.
   RTC_DCHECK_NE(cur_candidate.packet_overhead(),
                 bounding_set.back().packet_overhead());
   float packet_rate = static_cast<float>(cur_candidate.bitrate_bps() -
                                          bounding_set.back().bitrate_bps()) /
                       (cur_candidate.packet_overhead() -
                        bounding_set.back().packet_overhead());

   // 7. If the packet rate is equal or lower than intersection of
   //    last tuple in selected list,
   //    remove last tuple in selected list & go back to step 6.
   if (packet_rate <= intersection[bounding_set.size() - 1]) {
     // Remove last tuple and goto step 6.
     bounding_set.pop_back();
     get_new_candidate = false;
   } else {
     // 8. If packet rate is lower than maximum packet rate of
     // last tuple in selected list, add current tuple to selected
     // list.
     if (packet_rate < max_packet_rate[bounding_set.size() - 1]) {
       bounding_set.push_back(cur_candidate);
       intersection[bounding_set.size() - 1] = packet_rate;
       uint16_t packet_overhead = bounding_set.back().packet_overhead();
       RTC_DCHECK_NE(packet_overhead, 0);
       max_packet_rate[bounding_set.size() - 1] =
           bounding_set.back().bitrate_bps() /
           static_cast<float>(packet_overhead);
     }
     --num_candidates;
     get_new_candidate = true;
   }

   // 9. Go back to step 5 if any tuple remains in candidate list.
 }
 RTC_DCHECK(!bounding_set.empty());
 return bounding_set;
}

bool TMMBRHelp::IsOwner(const std::vector<rtcp::TmmbItem>& bounding,
                       uint32_t ssrc) {
 for (const rtcp::TmmbItem& item : bounding) {
   if (item.ssrc() == ssrc) {
     return true;
   }
 }
 return false;
}

uint64_t TMMBRHelp::CalcMinBitrateBps(
   const std::vector<rtcp::TmmbItem>& candidates) {
 RTC_DCHECK(!candidates.empty());
 uint64_t min_bitrate_bps = std::numeric_limits<uint64_t>::max();
 for (const rtcp::TmmbItem& item : candidates)
   if (item.bitrate_bps() < min_bitrate_bps)
     min_bitrate_bps = item.bitrate_bps();
 return min_bitrate_bps;
}
}  // namespace webrtc