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