Home | History | Annotate | Download | only in source 
      1 /*
      2  *  Copyright (c) 2012 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 "webrtc/modules/rtp_rtcp/source/tmmbr_help.h"
     12 
     13 #include <assert.h>
     14 #include <string.h>
     15 
     16 #include <limits>
     17 
     18 #include "webrtc/modules/rtp_rtcp/source/rtp_rtcp_config.h"
     19 
     20 namespace webrtc {
     21 TMMBRSet::TMMBRSet() :
     22     _sizeOfSet(0),
     23     _lengthOfSet(0)
     24 {
     25 }
     26 
     27 TMMBRSet::~TMMBRSet()
     28 {
     29     _sizeOfSet = 0;
     30     _lengthOfSet = 0;
     31 }
     32 
     33 void
     34 TMMBRSet::VerifyAndAllocateSet(uint32_t minimumSize)
     35 {
     36     if(minimumSize > _sizeOfSet)
     37     {
     38         // make sure that our buffers are big enough
     39         _data.resize(minimumSize);
     40         _sizeOfSet = minimumSize;
     41     }
     42     // reset memory
     43     for(uint32_t i = 0; i < _sizeOfSet; i++)
     44     {
     45         _data.at(i).tmmbr = 0;
     46         _data.at(i).packet_oh = 0;
     47         _data.at(i).ssrc = 0;
     48     }
     49     _lengthOfSet = 0;
     50 }
     51 
     52 void
     53 TMMBRSet::VerifyAndAllocateSetKeepingData(uint32_t minimumSize)
     54 {
     55     if(minimumSize > _sizeOfSet)
     56     {
     57         {
     58           _data.resize(minimumSize);
     59         }
     60         _sizeOfSet = minimumSize;
     61     }
     62 }
     63 
     64 void TMMBRSet::SetEntry(unsigned int i,
     65                          uint32_t tmmbrSet,
     66                          uint32_t packetOHSet,
     67                          uint32_t ssrcSet) {
     68   assert(i < _sizeOfSet);
     69   _data.at(i).tmmbr = tmmbrSet;
     70   _data.at(i).packet_oh = packetOHSet;
     71   _data.at(i).ssrc = ssrcSet;
     72   if (i >= _lengthOfSet) {
     73     _lengthOfSet = i + 1;
     74   }
     75 }
     76 
     77 void TMMBRSet::AddEntry(uint32_t tmmbrSet,
     78                         uint32_t packetOHSet,
     79                         uint32_t ssrcSet) {
     80   assert(_lengthOfSet < _sizeOfSet);
     81   SetEntry(_lengthOfSet, tmmbrSet, packetOHSet, ssrcSet);
     82 }
     83 
     84 void TMMBRSet::RemoveEntry(uint32_t sourceIdx) {
     85   assert(sourceIdx < _lengthOfSet);
     86   _data.erase(_data.begin() + sourceIdx);
     87   _lengthOfSet--;
     88   _data.resize(_sizeOfSet);  // Ensure that size remains the same.
     89 }
     90 
     91 void TMMBRSet::SwapEntries(uint32_t i, uint32_t j) {
     92     SetElement temp;
     93     temp = _data[i];
     94     _data[i] = _data[j];
     95     _data[j] = temp;
     96 }
     97 
     98 void TMMBRSet::ClearEntry(uint32_t idx) {
     99   SetEntry(idx, 0, 0, 0);
    100 }
    101 
    102 TMMBRHelp::TMMBRHelp()
    103     : _criticalSection(CriticalSectionWrapper::CreateCriticalSection()),
    104       _candidateSet(),
    105       _boundingSet(),
    106       _boundingSetToSend(),
    107       _ptrIntersectionBoundingSet(NULL),
    108       _ptrMaxPRBoundingSet(NULL) {
    109 }
    110 
    111 TMMBRHelp::~TMMBRHelp() {
    112   delete [] _ptrIntersectionBoundingSet;
    113   delete [] _ptrMaxPRBoundingSet;
    114   _ptrIntersectionBoundingSet = 0;
    115   _ptrMaxPRBoundingSet = 0;
    116   delete _criticalSection;
    117 }
    118 
    119 TMMBRSet*
    120 TMMBRHelp::VerifyAndAllocateBoundingSet(uint32_t minimumSize)
    121 {
    122     CriticalSectionScoped lock(_criticalSection);
    123 
    124     if(minimumSize > _boundingSet.sizeOfSet())
    125     {
    126         // make sure that our buffers are big enough
    127         if(_ptrIntersectionBoundingSet)
    128         {
    129             delete [] _ptrIntersectionBoundingSet;
    130             delete [] _ptrMaxPRBoundingSet;
    131         }
    132         _ptrIntersectionBoundingSet = new float[minimumSize];
    133         _ptrMaxPRBoundingSet = new float[minimumSize];
    134     }
    135     _boundingSet.VerifyAndAllocateSet(minimumSize);
    136     return &_boundingSet;
    137 }
    138 
    139 TMMBRSet* TMMBRHelp::BoundingSet() {
    140   return &_boundingSet;
    141 }
    142 
    143 int32_t
    144 TMMBRHelp::SetTMMBRBoundingSetToSend(const TMMBRSet* boundingSetToSend,
    145                                      const uint32_t maxBitrateKbit)
    146 {
    147     CriticalSectionScoped lock(_criticalSection);
    148 
    149     if (boundingSetToSend == NULL)
    150     {
    151         _boundingSetToSend.clearSet();
    152         return 0;
    153     }
    154 
    155     VerifyAndAllocateBoundingSetToSend(boundingSetToSend->lengthOfSet());
    156     _boundingSetToSend.clearSet();
    157     for (uint32_t i = 0; i < boundingSetToSend->lengthOfSet(); i++)
    158     {
    159         // cap at our configured max bitrate
    160         uint32_t bitrate = boundingSetToSend->Tmmbr(i);
    161         if(maxBitrateKbit)
    162         {
    163             // do we have a configured max bitrate?
    164             if(bitrate > maxBitrateKbit)
    165             {
    166                 bitrate = maxBitrateKbit;
    167             }
    168         }
    169         _boundingSetToSend.SetEntry(i, bitrate,
    170                                     boundingSetToSend->PacketOH(i),
    171                                     boundingSetToSend->Ssrc(i));
    172     }
    173     return 0;
    174 }
    175 
    176 int32_t
    177 TMMBRHelp::VerifyAndAllocateBoundingSetToSend(uint32_t minimumSize)
    178 {
    179     CriticalSectionScoped lock(_criticalSection);
    180 
    181     _boundingSetToSend.VerifyAndAllocateSet(minimumSize);
    182     return 0;
    183 }
    184 
    185 TMMBRSet*
    186 TMMBRHelp::VerifyAndAllocateCandidateSet(uint32_t minimumSize)
    187 {
    188     CriticalSectionScoped lock(_criticalSection);
    189 
    190     _candidateSet.VerifyAndAllocateSet(minimumSize);
    191     return &_candidateSet;
    192 }
    193 
    194 TMMBRSet*
    195 TMMBRHelp::CandidateSet()
    196 {
    197     return &_candidateSet;
    198 }
    199 
    200 TMMBRSet*
    201 TMMBRHelp::BoundingSetToSend()
    202 {
    203     return &_boundingSetToSend;
    204 }
    205 
    206 int32_t
    207 TMMBRHelp::FindTMMBRBoundingSet(TMMBRSet*& boundingSet)
    208 {
    209     CriticalSectionScoped lock(_criticalSection);
    210 
    211     // Work on local variable, will be modified
    212     TMMBRSet    candidateSet;
    213     candidateSet.VerifyAndAllocateSet(_candidateSet.sizeOfSet());
    214 
    215     // TODO(hta) Figure out if this should be lengthOfSet instead.
    216     for (uint32_t i = 0; i < _candidateSet.sizeOfSet(); i++)
    217     {
    218         if(_candidateSet.Tmmbr(i))
    219         {
    220             candidateSet.AddEntry(_candidateSet.Tmmbr(i),
    221                                   _candidateSet.PacketOH(i),
    222                                   _candidateSet.Ssrc(i));
    223         }
    224         else
    225         {
    226             // make sure this is zero if tmmbr = 0
    227             assert(_candidateSet.PacketOH(i) == 0);
    228             // Old code:
    229             // _candidateSet.ptrPacketOHSet[i] = 0;
    230         }
    231     }
    232 
    233     // Number of set candidates
    234     int32_t numSetCandidates = candidateSet.lengthOfSet();
    235     // Find bounding set
    236     uint32_t numBoundingSet = 0;
    237     if (numSetCandidates > 0)
    238     {
    239         numBoundingSet =  FindTMMBRBoundingSet(numSetCandidates, candidateSet);
    240         if(numBoundingSet < 1 || (numBoundingSet > _candidateSet.sizeOfSet()))
    241         {
    242             return -1;
    243         }
    244         boundingSet = &_boundingSet;
    245     }
    246     return numBoundingSet;
    247 }
    248 
    249 
    250 int32_t
    251 TMMBRHelp::FindTMMBRBoundingSet(int32_t numCandidates, TMMBRSet& candidateSet)
    252 {
    253     CriticalSectionScoped lock(_criticalSection);
    254 
    255     uint32_t numBoundingSet = 0;
    256     VerifyAndAllocateBoundingSet(candidateSet.sizeOfSet());
    257 
    258     if (numCandidates == 1)
    259     {
    260         // TODO(hta): lengthOfSet instead of sizeOfSet?
    261         for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++)
    262         {
    263             if (candidateSet.Tmmbr(i) > 0)
    264             {
    265                 _boundingSet.AddEntry(candidateSet.Tmmbr(i),
    266                                     candidateSet.PacketOH(i),
    267                                     candidateSet.Ssrc(i));
    268                 numBoundingSet++;
    269             }
    270         }
    271         return (numBoundingSet == 1) ? 1 : -1;
    272     }
    273 
    274     // 1. Sort by increasing packetOH
    275     for (int i = candidateSet.sizeOfSet() - 1; i >= 0; i--)
    276     {
    277         for (int j = 1; j <= i; j++)
    278         {
    279             if (candidateSet.PacketOH(j-1) > candidateSet.PacketOH(j))
    280             {
    281                 candidateSet.SwapEntries(j-1, j);
    282             }
    283         }
    284     }
    285     // 2. For tuples with same OH, keep the one w/ the lowest bitrate
    286     for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++)
    287     {
    288         if (candidateSet.Tmmbr(i) > 0)
    289         {
    290             // get min bitrate for packets w/ same OH
    291             uint32_t currentPacketOH = candidateSet.PacketOH(i);
    292             uint32_t currentMinTMMBR = candidateSet.Tmmbr(i);
    293             uint32_t currentMinIndexTMMBR = i;
    294             for (uint32_t j = i+1; j < candidateSet.sizeOfSet(); j++)
    295             {
    296                 if(candidateSet.PacketOH(j) == currentPacketOH)
    297                 {
    298                     if(candidateSet.Tmmbr(j) < currentMinTMMBR)
    299                     {
    300                         currentMinTMMBR = candidateSet.Tmmbr(j);
    301                         currentMinIndexTMMBR = j;
    302                     }
    303                 }
    304             }
    305             // keep lowest bitrate
    306             for (uint32_t j = 0; j < candidateSet.sizeOfSet(); j++)
    307             {
    308               if(candidateSet.PacketOH(j) == currentPacketOH
    309                   && j != currentMinIndexTMMBR)
    310                 {
    311                     candidateSet.ClearEntry(j);
    312                 }
    313             }
    314         }
    315     }
    316     // 3. Select and remove tuple w/ lowest tmmbr.
    317     // (If more than 1, choose the one w/ highest OH).
    318     uint32_t minTMMBR = 0;
    319     uint32_t minIndexTMMBR = 0;
    320     for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++)
    321     {
    322         if (candidateSet.Tmmbr(i) > 0)
    323         {
    324             minTMMBR = candidateSet.Tmmbr(i);
    325             minIndexTMMBR = i;
    326             break;
    327         }
    328     }
    329 
    330     for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++)
    331     {
    332         if (candidateSet.Tmmbr(i) > 0 && candidateSet.Tmmbr(i) <= minTMMBR)
    333         {
    334             // get min bitrate
    335             minTMMBR = candidateSet.Tmmbr(i);
    336             minIndexTMMBR = i;
    337         }
    338     }
    339     // first member of selected list
    340     _boundingSet.SetEntry(numBoundingSet,
    341                           candidateSet.Tmmbr(minIndexTMMBR),
    342                           candidateSet.PacketOH(minIndexTMMBR),
    343                           candidateSet.Ssrc(minIndexTMMBR));
    344 
    345     // set intersection value
    346     _ptrIntersectionBoundingSet[numBoundingSet] = 0;
    347     // calculate its maximum packet rate (where its line crosses x-axis)
    348     _ptrMaxPRBoundingSet[numBoundingSet]
    349         = _boundingSet.Tmmbr(numBoundingSet) * 1000
    350         / float(8 * _boundingSet.PacketOH(numBoundingSet));
    351     numBoundingSet++;
    352     // remove from candidate list
    353     candidateSet.ClearEntry(minIndexTMMBR);
    354     numCandidates--;
    355 
    356     // 4. Discard from candidate list all tuple w/ lower OH
    357     // (next tuple must be steeper)
    358     for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++)
    359     {
    360         if(candidateSet.Tmmbr(i) > 0
    361             && candidateSet.PacketOH(i) < _boundingSet.PacketOH(0))
    362         {
    363             candidateSet.ClearEntry(i);
    364             numCandidates--;
    365         }
    366     }
    367 
    368     if (numCandidates == 0)
    369     {
    370         // Should be true already:_boundingSet.lengthOfSet = numBoundingSet;
    371         assert(_boundingSet.lengthOfSet() == numBoundingSet);
    372         return numBoundingSet;
    373     }
    374 
    375     bool getNewCandidate = true;
    376     int curCandidateTMMBR = 0;
    377     int curCandidateIndex = 0;
    378     int curCandidatePacketOH = 0;
    379     int curCandidateSSRC = 0;
    380     do
    381     {
    382         if (getNewCandidate)
    383         {
    384             // 5. Remove first remaining tuple from candidate list
    385             for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++)
    386             {
    387                 if (candidateSet.Tmmbr(i) > 0)
    388                 {
    389                     curCandidateTMMBR    = candidateSet.Tmmbr(i);
    390                     curCandidatePacketOH = candidateSet.PacketOH(i);
    391                     curCandidateSSRC     = candidateSet.Ssrc(i);
    392                     curCandidateIndex    = i;
    393                     candidateSet.ClearEntry(curCandidateIndex);
    394                     break;
    395                 }
    396             }
    397         }
    398 
    399         // 6. Calculate packet rate and intersection of the current
    400         // line with line of last tuple in selected list
    401         float packetRate
    402             = float(curCandidateTMMBR
    403                     - _boundingSet.Tmmbr(numBoundingSet-1))*1000
    404             / (8*(curCandidatePacketOH
    405                   - _boundingSet.PacketOH(numBoundingSet-1)));
    406 
    407         // 7. If the packet rate is equal or lower than intersection of
    408         //    last tuple in selected list,
    409         //    remove last tuple in selected list & go back to step 6
    410         if(packetRate <= _ptrIntersectionBoundingSet[numBoundingSet-1])
    411         {
    412             // remove last tuple and goto step 6
    413             numBoundingSet--;
    414             _boundingSet.ClearEntry(numBoundingSet);
    415             _ptrIntersectionBoundingSet[numBoundingSet] = 0;
    416             _ptrMaxPRBoundingSet[numBoundingSet]        = 0;
    417             getNewCandidate = false;
    418         } else
    419         {
    420             // 8. If packet rate is lower than maximum packet rate of
    421             // last tuple in selected list, add current tuple to selected
    422             // list
    423             if (packetRate < _ptrMaxPRBoundingSet[numBoundingSet-1])
    424             {
    425                 _boundingSet.SetEntry(numBoundingSet,
    426                                       curCandidateTMMBR,
    427                                       curCandidatePacketOH,
    428                                       curCandidateSSRC);
    429                 _ptrIntersectionBoundingSet[numBoundingSet] = packetRate;
    430                 _ptrMaxPRBoundingSet[numBoundingSet]
    431                     = _boundingSet.Tmmbr(numBoundingSet)*1000
    432                     / float(8*_boundingSet.PacketOH(numBoundingSet));
    433                 numBoundingSet++;
    434             }
    435             numCandidates--;
    436             getNewCandidate = true;
    437         }
    438 
    439         // 9. Go back to step 5 if any tuple remains in candidate list
    440     } while (numCandidates > 0);
    441 
    442     return numBoundingSet;
    443 }
    444 
    445 bool TMMBRHelp::IsOwner(const uint32_t ssrc,
    446                         const uint32_t length) const {
    447   CriticalSectionScoped lock(_criticalSection);
    448 
    449   if (length == 0) {
    450     // Empty bounding set.
    451     return false;
    452   }
    453   for(uint32_t i = 0;
    454       (i < length) && (i < _boundingSet.sizeOfSet()); ++i) {
    455     if(_boundingSet.Ssrc(i) == ssrc) {
    456       return true;
    457     }
    458   }
    459   return false;
    460 }
    461 
    462 bool TMMBRHelp::CalcMinBitRate( uint32_t* minBitrateKbit) const {
    463   CriticalSectionScoped lock(_criticalSection);
    464 
    465   if (_candidateSet.sizeOfSet() == 0) {
    466     // Empty bounding set.
    467     return false;
    468   }
    469   *minBitrateKbit = std::numeric_limits<uint32_t>::max();
    470 
    471   for (uint32_t i = 0; i < _candidateSet.lengthOfSet(); ++i) {
    472     uint32_t curNetBitRateKbit = _candidateSet.Tmmbr(i);
    473     if (curNetBitRateKbit < MIN_VIDEO_BW_MANAGEMENT_BITRATE) {
    474       curNetBitRateKbit = MIN_VIDEO_BW_MANAGEMENT_BITRATE;
    475     }
    476     *minBitrateKbit = curNetBitRateKbit < *minBitrateKbit ?
    477         curNetBitRateKbit : *minBitrateKbit;
    478   }
    479   return true;
    480 }
    481 }  // namespace webrtc
    482