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 if (numBoundingSet != 1) 270 { 271 numBoundingSet = -1; 272 } 273 } else 274 { 275 // 1. Sort by increasing packetOH 276 for (int i = candidateSet.sizeOfSet() - 1; i >= 0; i--) 277 { 278 for (int j = 1; j <= i; j++) 279 { 280 if (candidateSet.PacketOH(j-1) > candidateSet.PacketOH(j)) 281 { 282 candidateSet.SwapEntries(j-1, j); 283 } 284 } 285 } 286 // 2. For tuples with same OH, keep the one w/ the lowest bitrate 287 for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++) 288 { 289 if (candidateSet.Tmmbr(i) > 0) 290 { 291 // get min bitrate for packets w/ same OH 292 uint32_t currentPacketOH = candidateSet.PacketOH(i); 293 uint32_t currentMinTMMBR = candidateSet.Tmmbr(i); 294 uint32_t currentMinIndexTMMBR = i; 295 for (uint32_t j = i+1; j < candidateSet.sizeOfSet(); j++) 296 { 297 if(candidateSet.PacketOH(j) == currentPacketOH) 298 { 299 if(candidateSet.Tmmbr(j) < currentMinTMMBR) 300 { 301 currentMinTMMBR = candidateSet.Tmmbr(j); 302 currentMinIndexTMMBR = j; 303 } 304 } 305 } 306 // keep lowest bitrate 307 for (uint32_t j = 0; j < candidateSet.sizeOfSet(); j++) 308 { 309 if(candidateSet.PacketOH(j) == currentPacketOH 310 && j != currentMinIndexTMMBR) 311 { 312 candidateSet.ClearEntry(j); 313 } 314 } 315 } 316 } 317 // 3. Select and remove tuple w/ lowest tmmbr. 318 // (If more than 1, choose the one w/ highest OH). 319 uint32_t minTMMBR = 0; 320 uint32_t minIndexTMMBR = 0; 321 for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++) 322 { 323 if (candidateSet.Tmmbr(i) > 0) 324 { 325 minTMMBR = candidateSet.Tmmbr(i); 326 minIndexTMMBR = i; 327 break; 328 } 329 } 330 331 for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++) 332 { 333 if (candidateSet.Tmmbr(i) > 0 && candidateSet.Tmmbr(i) <= minTMMBR) 334 { 335 // get min bitrate 336 minTMMBR = candidateSet.Tmmbr(i); 337 minIndexTMMBR = i; 338 } 339 } 340 // first member of selected list 341 _boundingSet.SetEntry(numBoundingSet, 342 candidateSet.Tmmbr(minIndexTMMBR), 343 candidateSet.PacketOH(minIndexTMMBR), 344 candidateSet.Ssrc(minIndexTMMBR)); 345 346 // set intersection value 347 _ptrIntersectionBoundingSet[numBoundingSet] = 0; 348 // calculate its maximum packet rate (where its line crosses x-axis) 349 _ptrMaxPRBoundingSet[numBoundingSet] 350 = _boundingSet.Tmmbr(numBoundingSet) * 1000 351 / float(8 * _boundingSet.PacketOH(numBoundingSet)); 352 numBoundingSet++; 353 // remove from candidate list 354 candidateSet.ClearEntry(minIndexTMMBR); 355 numCandidates--; 356 357 // 4. Discard from candidate list all tuple w/ lower OH 358 // (next tuple must be steeper) 359 for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++) 360 { 361 if(candidateSet.Tmmbr(i) > 0 362 && candidateSet.PacketOH(i) < _boundingSet.PacketOH(0)) 363 { 364 candidateSet.ClearEntry(i); 365 numCandidates--; 366 } 367 } 368 369 if (numCandidates == 0) 370 { 371 // Should be true already:_boundingSet.lengthOfSet = numBoundingSet; 372 assert(_boundingSet.lengthOfSet() == numBoundingSet); 373 return numBoundingSet; 374 } 375 376 bool getNewCandidate = true; 377 int curCandidateTMMBR = 0; 378 int curCandidateIndex = 0; 379 int curCandidatePacketOH = 0; 380 int curCandidateSSRC = 0; 381 do 382 { 383 if (getNewCandidate) 384 { 385 // 5. Remove first remaining tuple from candidate list 386 for (uint32_t i = 0; i < candidateSet.sizeOfSet(); i++) 387 { 388 if (candidateSet.Tmmbr(i) > 0) 389 { 390 curCandidateTMMBR = candidateSet.Tmmbr(i); 391 curCandidatePacketOH = candidateSet.PacketOH(i); 392 curCandidateSSRC = candidateSet.Ssrc(i); 393 curCandidateIndex = i; 394 candidateSet.ClearEntry(curCandidateIndex); 395 break; 396 } 397 } 398 } 399 400 // 6. Calculate packet rate and intersection of the current 401 // line with line of last tuple in selected list 402 float packetRate 403 = float(curCandidateTMMBR 404 - _boundingSet.Tmmbr(numBoundingSet-1))*1000 405 / (8*(curCandidatePacketOH 406 - _boundingSet.PacketOH(numBoundingSet-1))); 407 408 // 7. If the packet rate is equal or lower than intersection of 409 // last tuple in selected list, 410 // remove last tuple in selected list & go back to step 6 411 if(packetRate <= _ptrIntersectionBoundingSet[numBoundingSet-1]) 412 { 413 // remove last tuple and goto step 6 414 numBoundingSet--; 415 _boundingSet.ClearEntry(numBoundingSet); 416 _ptrIntersectionBoundingSet[numBoundingSet] = 0; 417 _ptrMaxPRBoundingSet[numBoundingSet] = 0; 418 getNewCandidate = false; 419 } else 420 { 421 // 8. If packet rate is lower than maximum packet rate of 422 // last tuple in selected list, add current tuple to selected 423 // list 424 if (packetRate < _ptrMaxPRBoundingSet[numBoundingSet-1]) 425 { 426 _boundingSet.SetEntry(numBoundingSet, 427 curCandidateTMMBR, 428 curCandidatePacketOH, 429 curCandidateSSRC); 430 _ptrIntersectionBoundingSet[numBoundingSet] = packetRate; 431 _ptrMaxPRBoundingSet[numBoundingSet] 432 = _boundingSet.Tmmbr(numBoundingSet)*1000 433 / float(8*_boundingSet.PacketOH(numBoundingSet)); 434 numBoundingSet++; 435 } 436 numCandidates--; 437 getNewCandidate = true; 438 } 439 440 // 9. Go back to step 5 if any tuple remains in candidate list 441 } while (numCandidates > 0); 442 } 443 return numBoundingSet; 444 } 445 446 bool TMMBRHelp::IsOwner(const uint32_t ssrc, 447 const uint32_t length) const { 448 CriticalSectionScoped lock(_criticalSection); 449 450 if (length == 0) { 451 // Empty bounding set. 452 return false; 453 } 454 for(uint32_t i = 0; 455 (i < length) && (i < _boundingSet.sizeOfSet()); ++i) { 456 if(_boundingSet.Ssrc(i) == ssrc) { 457 return true; 458 } 459 } 460 return false; 461 } 462 463 bool TMMBRHelp::CalcMinBitRate( uint32_t* minBitrateKbit) const { 464 CriticalSectionScoped lock(_criticalSection); 465 466 if (_candidateSet.sizeOfSet() == 0) { 467 // Empty bounding set. 468 return false; 469 } 470 *minBitrateKbit = std::numeric_limits<uint32_t>::max(); 471 472 for (uint32_t i = 0; i < _candidateSet.lengthOfSet(); ++i) { 473 uint32_t curNetBitRateKbit = _candidateSet.Tmmbr(i); 474 if (curNetBitRateKbit < MIN_VIDEO_BW_MANAGEMENT_BITRATE) { 475 curNetBitRateKbit = MIN_VIDEO_BW_MANAGEMENT_BITRATE; 476 } 477 *minBitrateKbit = curNetBitRateKbit < *minBitrateKbit ? 478 curNetBitRateKbit : *minBitrateKbit; 479 } 480 return true; 481 } 482 } // namespace webrtc 483
