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 /* 12 * Test application for core FEC algorithm. Calls encoding and decoding 13 * functions in ForwardErrorCorrection directly. 14 */ 15 16 #include <assert.h> 17 #include <stdio.h> 18 #include <stdlib.h> 19 #include <string.h> 20 #include <time.h> 21 22 #include <list> 23 24 #include "testing/gtest/include/gtest/gtest.h" 25 #include "webrtc/base/random.h" 26 #include "webrtc/modules/rtp_rtcp/source/byte_io.h" 27 #include "webrtc/modules/rtp_rtcp/source/forward_error_correction.h" 28 #include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h" 29 #include "webrtc/test/testsupport/fileutils.h" 30 31 // #define VERBOSE_OUTPUT 32 33 namespace webrtc { 34 namespace fec_private_tables { 35 extern const uint8_t** kPacketMaskBurstyTbl[12]; 36 } 37 namespace test { 38 using fec_private_tables::kPacketMaskBurstyTbl; 39 40 void ReceivePackets( 41 ForwardErrorCorrection::ReceivedPacketList* toDecodeList, 42 ForwardErrorCorrection::ReceivedPacketList* receivedPacketList, 43 size_t numPacketsToDecode, 44 float reorderRate, 45 float duplicateRate, 46 Random* random) { 47 assert(toDecodeList->empty()); 48 assert(numPacketsToDecode <= receivedPacketList->size()); 49 50 ForwardErrorCorrection::ReceivedPacketList::iterator it; 51 for (size_t i = 0; i < numPacketsToDecode; i++) { 52 it = receivedPacketList->begin(); 53 // Reorder packets. 54 float randomVariable = random->Rand<float>(); 55 while (randomVariable < reorderRate) { 56 ++it; 57 if (it == receivedPacketList->end()) { 58 --it; 59 break; 60 } 61 randomVariable = random->Rand<float>(); 62 } 63 ForwardErrorCorrection::ReceivedPacket* receivedPacket = *it; 64 toDecodeList->push_back(receivedPacket); 65 66 // Duplicate packets. 67 randomVariable = random->Rand<float>(); 68 while (randomVariable < duplicateRate) { 69 ForwardErrorCorrection::ReceivedPacket* duplicatePacket = 70 new ForwardErrorCorrection::ReceivedPacket; 71 *duplicatePacket = *receivedPacket; 72 duplicatePacket->pkt = new ForwardErrorCorrection::Packet; 73 memcpy(duplicatePacket->pkt->data, receivedPacket->pkt->data, 74 receivedPacket->pkt->length); 75 duplicatePacket->pkt->length = receivedPacket->pkt->length; 76 77 toDecodeList->push_back(duplicatePacket); 78 randomVariable = random->Rand<float>(); 79 } 80 receivedPacketList->erase(it); 81 } 82 } 83 84 TEST(FecTest, FecTest) { 85 // TODO(marpan): Split this function into subroutines/helper functions. 86 enum { kMaxNumberMediaPackets = 48 }; 87 enum { kMaxNumberFecPackets = 48 }; 88 89 const uint32_t kNumMaskBytesL0 = 2; 90 const uint32_t kNumMaskBytesL1 = 6; 91 92 // FOR UEP 93 const bool kUseUnequalProtection = true; 94 95 // FEC mask types. 96 const FecMaskType kMaskTypes[] = {kFecMaskRandom, kFecMaskBursty}; 97 const int kNumFecMaskTypes = sizeof(kMaskTypes) / sizeof(*kMaskTypes); 98 99 // Maximum number of media packets allowed for the mask type. 100 const uint16_t kMaxMediaPackets[] = { 101 kMaxNumberMediaPackets, 102 sizeof(kPacketMaskBurstyTbl) / sizeof(*kPacketMaskBurstyTbl)}; 103 104 ASSERT_EQ(12, kMaxMediaPackets[1]) << "Max media packets for bursty mode not " 105 << "equal to 12."; 106 107 ForwardErrorCorrection fec; 108 ForwardErrorCorrection::PacketList mediaPacketList; 109 ForwardErrorCorrection::PacketList fecPacketList; 110 ForwardErrorCorrection::ReceivedPacketList toDecodeList; 111 ForwardErrorCorrection::ReceivedPacketList receivedPacketList; 112 ForwardErrorCorrection::RecoveredPacketList recoveredPacketList; 113 std::list<uint8_t*> fecMaskList; 114 115 ForwardErrorCorrection::Packet* mediaPacket = NULL; 116 // Running over only one loss rate to limit execution time. 117 const float lossRate[] = {0.5f}; 118 const uint32_t lossRateSize = sizeof(lossRate) / sizeof(*lossRate); 119 const float reorderRate = 0.1f; 120 const float duplicateRate = 0.1f; 121 122 uint8_t mediaLossMask[kMaxNumberMediaPackets]; 123 uint8_t fecLossMask[kMaxNumberFecPackets]; 124 uint8_t fecPacketMasks[kMaxNumberFecPackets][kMaxNumberMediaPackets]; 125 126 // Seed the random number generator, storing the seed to file in order to 127 // reproduce past results. 128 const unsigned int randomSeed = static_cast<unsigned int>(time(NULL)); 129 Random random(randomSeed); 130 std::string filename = webrtc::test::OutputPath() + "randomSeedLog.txt"; 131 FILE* randomSeedFile = fopen(filename.c_str(), "a"); 132 fprintf(randomSeedFile, "%u\n", randomSeed); 133 fclose(randomSeedFile); 134 randomSeedFile = NULL; 135 136 uint16_t seqNum = 0; 137 uint32_t timeStamp = random.Rand<uint32_t>(); 138 const uint32_t ssrc = random.Rand(1u, 0xfffffffe); 139 140 // Loop over the mask types: random and bursty. 141 for (int mask_type_idx = 0; mask_type_idx < kNumFecMaskTypes; 142 ++mask_type_idx) { 143 for (uint32_t lossRateIdx = 0; lossRateIdx < lossRateSize; ++lossRateIdx) { 144 printf("Loss rate: %.2f, Mask type %d \n", lossRate[lossRateIdx], 145 mask_type_idx); 146 147 const uint32_t packetMaskMax = kMaxMediaPackets[mask_type_idx]; 148 uint8_t* packetMask = new uint8_t[packetMaskMax * kNumMaskBytesL1]; 149 150 FecMaskType fec_mask_type = kMaskTypes[mask_type_idx]; 151 152 for (uint32_t numMediaPackets = 1; numMediaPackets <= packetMaskMax; 153 numMediaPackets++) { 154 internal::PacketMaskTable mask_table(fec_mask_type, numMediaPackets); 155 156 for (uint32_t numFecPackets = 1; 157 numFecPackets <= numMediaPackets && numFecPackets <= packetMaskMax; 158 numFecPackets++) { 159 // Loop over numImpPackets: usually <= (0.3*numMediaPackets). 160 // For this test we check up to ~ (numMediaPackets / 4). 161 uint32_t maxNumImpPackets = numMediaPackets / 4 + 1; 162 for (uint32_t numImpPackets = 0; numImpPackets <= maxNumImpPackets && 163 numImpPackets <= packetMaskMax; 164 numImpPackets++) { 165 uint8_t protectionFactor = 166 static_cast<uint8_t>(numFecPackets * 255 / numMediaPackets); 167 168 const uint32_t maskBytesPerFecPacket = 169 (numMediaPackets > 16) ? kNumMaskBytesL1 : kNumMaskBytesL0; 170 171 memset(packetMask, 0, numMediaPackets * maskBytesPerFecPacket); 172 173 // Transfer packet masks from bit-mask to byte-mask. 174 internal::GeneratePacketMasks(numMediaPackets, numFecPackets, 175 numImpPackets, kUseUnequalProtection, 176 mask_table, packetMask); 177 178 #ifdef VERBOSE_OUTPUT 179 printf( 180 "%u media packets, %u FEC packets, %u numImpPackets, " 181 "loss rate = %.2f \n", 182 numMediaPackets, numFecPackets, numImpPackets, 183 lossRate[lossRateIdx]); 184 printf("Packet mask matrix \n"); 185 #endif 186 187 for (uint32_t i = 0; i < numFecPackets; i++) { 188 for (uint32_t j = 0; j < numMediaPackets; j++) { 189 const uint8_t byteMask = 190 packetMask[i * maskBytesPerFecPacket + j / 8]; 191 const uint32_t bitPosition = (7 - j % 8); 192 fecPacketMasks[i][j] = 193 (byteMask & (1 << bitPosition)) >> bitPosition; 194 #ifdef VERBOSE_OUTPUT 195 printf("%u ", fecPacketMasks[i][j]); 196 #endif 197 } 198 #ifdef VERBOSE_OUTPUT 199 printf("\n"); 200 #endif 201 } 202 #ifdef VERBOSE_OUTPUT 203 printf("\n"); 204 #endif 205 // Check for all zero rows or columns: indicates incorrect mask. 206 uint32_t rowLimit = numMediaPackets; 207 for (uint32_t i = 0; i < numFecPackets; ++i) { 208 uint32_t rowSum = 0; 209 for (uint32_t j = 0; j < rowLimit; ++j) { 210 rowSum += fecPacketMasks[i][j]; 211 } 212 ASSERT_NE(0u, rowSum) << "Row is all zero " << i; 213 } 214 for (uint32_t j = 0; j < rowLimit; ++j) { 215 uint32_t columnSum = 0; 216 for (uint32_t i = 0; i < numFecPackets; ++i) { 217 columnSum += fecPacketMasks[i][j]; 218 } 219 ASSERT_NE(0u, columnSum) << "Column is all zero " << j; 220 } 221 222 // Construct media packets. 223 // Reset the sequence number here for each FEC code/mask tested 224 // below, to avoid sequence number wrap-around. In actual decoding, 225 // old FEC packets in list are dropped if sequence number wrap 226 // around is detected. This case is currently not handled below. 227 seqNum = 0; 228 for (uint32_t i = 0; i < numMediaPackets; ++i) { 229 mediaPacket = new ForwardErrorCorrection::Packet; 230 mediaPacketList.push_back(mediaPacket); 231 const uint32_t kMinPacketSize = 12; 232 const uint32_t kMaxPacketSize = static_cast<uint32_t>( 233 IP_PACKET_SIZE - 12 - 28 - 234 ForwardErrorCorrection::PacketOverhead()); 235 mediaPacket->length = random.Rand(kMinPacketSize, kMaxPacketSize); 236 237 // Generate random values for the first 2 bytes. 238 mediaPacket->data[0] = random.Rand<uint8_t>(); 239 mediaPacket->data[1] = random.Rand<uint8_t>(); 240 241 // The first two bits are assumed to be 10 by the 242 // FEC encoder. In fact the FEC decoder will set the 243 // two first bits to 10 regardless of what they 244 // actually were. Set the first two bits to 10 245 // so that a memcmp can be performed for the 246 // whole restored packet. 247 mediaPacket->data[0] |= 0x80; 248 mediaPacket->data[0] &= 0xbf; 249 250 // FEC is applied to a whole frame. 251 // A frame is signaled by multiple packets without 252 // the marker bit set followed by the last packet of 253 // the frame for which the marker bit is set. 254 // Only push one (fake) frame to the FEC. 255 mediaPacket->data[1] &= 0x7f; 256 257 ByteWriter<uint16_t>::WriteBigEndian(&mediaPacket->data[2], 258 seqNum); 259 ByteWriter<uint32_t>::WriteBigEndian(&mediaPacket->data[4], 260 timeStamp); 261 ByteWriter<uint32_t>::WriteBigEndian(&mediaPacket->data[8], ssrc); 262 // Generate random values for payload 263 for (size_t j = 12; j < mediaPacket->length; ++j) { 264 mediaPacket->data[j] = random.Rand<uint8_t>(); 265 } 266 seqNum++; 267 } 268 mediaPacket->data[1] |= 0x80; 269 270 ASSERT_EQ(0, fec.GenerateFEC(mediaPacketList, protectionFactor, 271 numImpPackets, kUseUnequalProtection, 272 fec_mask_type, &fecPacketList)) 273 << "GenerateFEC() failed"; 274 275 ASSERT_EQ(numFecPackets, fecPacketList.size()) 276 << "We requested " << numFecPackets << " FEC packets, but " 277 << "GenerateFEC() produced " << fecPacketList.size(); 278 memset(mediaLossMask, 0, sizeof(mediaLossMask)); 279 ForwardErrorCorrection::PacketList::iterator mediaPacketListItem = 280 mediaPacketList.begin(); 281 ForwardErrorCorrection::ReceivedPacket* receivedPacket; 282 uint32_t mediaPacketIdx = 0; 283 284 while (mediaPacketListItem != mediaPacketList.end()) { 285 mediaPacket = *mediaPacketListItem; 286 // We want a value between 0 and 1. 287 const float lossRandomVariable = random.Rand<float>(); 288 289 if (lossRandomVariable >= lossRate[lossRateIdx]) { 290 mediaLossMask[mediaPacketIdx] = 1; 291 receivedPacket = new ForwardErrorCorrection::ReceivedPacket; 292 receivedPacket->pkt = new ForwardErrorCorrection::Packet; 293 receivedPacketList.push_back(receivedPacket); 294 295 receivedPacket->pkt->length = mediaPacket->length; 296 memcpy(receivedPacket->pkt->data, mediaPacket->data, 297 mediaPacket->length); 298 receivedPacket->seq_num = 299 ByteReader<uint16_t>::ReadBigEndian(&mediaPacket->data[2]); 300 receivedPacket->is_fec = false; 301 } 302 mediaPacketIdx++; 303 ++mediaPacketListItem; 304 } 305 memset(fecLossMask, 0, sizeof(fecLossMask)); 306 ForwardErrorCorrection::PacketList::iterator fecPacketListItem = 307 fecPacketList.begin(); 308 ForwardErrorCorrection::Packet* fecPacket; 309 uint32_t fecPacketIdx = 0; 310 while (fecPacketListItem != fecPacketList.end()) { 311 fecPacket = *fecPacketListItem; 312 const float lossRandomVariable = random.Rand<float>(); 313 if (lossRandomVariable >= lossRate[lossRateIdx]) { 314 fecLossMask[fecPacketIdx] = 1; 315 receivedPacket = new ForwardErrorCorrection::ReceivedPacket; 316 receivedPacket->pkt = new ForwardErrorCorrection::Packet; 317 318 receivedPacketList.push_back(receivedPacket); 319 320 receivedPacket->pkt->length = fecPacket->length; 321 memcpy(receivedPacket->pkt->data, fecPacket->data, 322 fecPacket->length); 323 324 receivedPacket->seq_num = seqNum; 325 receivedPacket->is_fec = true; 326 receivedPacket->ssrc = ssrc; 327 328 fecMaskList.push_back(fecPacketMasks[fecPacketIdx]); 329 } 330 ++fecPacketIdx; 331 ++seqNum; 332 ++fecPacketListItem; 333 } 334 335 #ifdef VERBOSE_OUTPUT 336 printf("Media loss mask:\n"); 337 for (uint32_t i = 0; i < numMediaPackets; i++) { 338 printf("%u ", mediaLossMask[i]); 339 } 340 printf("\n\n"); 341 342 printf("FEC loss mask:\n"); 343 for (uint32_t i = 0; i < numFecPackets; i++) { 344 printf("%u ", fecLossMask[i]); 345 } 346 printf("\n\n"); 347 #endif 348 349 std::list<uint8_t*>::iterator fecMaskIt = fecMaskList.begin(); 350 uint8_t* fecMask; 351 while (fecMaskIt != fecMaskList.end()) { 352 fecMask = *fecMaskIt; 353 uint32_t hammingDist = 0; 354 uint32_t recoveryPosition = 0; 355 for (uint32_t i = 0; i < numMediaPackets; i++) { 356 if (mediaLossMask[i] == 0 && fecMask[i] == 1) { 357 recoveryPosition = i; 358 ++hammingDist; 359 } 360 } 361 std::list<uint8_t*>::iterator itemToDelete = fecMaskIt; 362 ++fecMaskIt; 363 364 if (hammingDist == 1) { 365 // Recovery possible. Restart search. 366 mediaLossMask[recoveryPosition] = 1; 367 fecMaskIt = fecMaskList.begin(); 368 } else if (hammingDist == 0) { 369 // FEC packet cannot provide further recovery. 370 fecMaskList.erase(itemToDelete); 371 } 372 } 373 #ifdef VERBOSE_OUTPUT 374 printf("Recovery mask:\n"); 375 for (uint32_t i = 0; i < numMediaPackets; ++i) { 376 printf("%u ", mediaLossMask[i]); 377 } 378 printf("\n\n"); 379 #endif 380 // For error-checking frame completion. 381 bool fecPacketReceived = false; 382 while (!receivedPacketList.empty()) { 383 size_t numPacketsToDecode = random.Rand( 384 1u, static_cast<uint32_t>(receivedPacketList.size())); 385 ReceivePackets(&toDecodeList, &receivedPacketList, 386 numPacketsToDecode, reorderRate, duplicateRate, 387 &random); 388 389 if (fecPacketReceived == false) { 390 ForwardErrorCorrection::ReceivedPacketList::iterator 391 toDecodeIt = toDecodeList.begin(); 392 while (toDecodeIt != toDecodeList.end()) { 393 receivedPacket = *toDecodeIt; 394 if (receivedPacket->is_fec) { 395 fecPacketReceived = true; 396 } 397 ++toDecodeIt; 398 } 399 } 400 ASSERT_EQ(0, fec.DecodeFEC(&toDecodeList, &recoveredPacketList)) 401 << "DecodeFEC() failed"; 402 ASSERT_TRUE(toDecodeList.empty()) 403 << "Received packet list is not empty."; 404 } 405 mediaPacketListItem = mediaPacketList.begin(); 406 mediaPacketIdx = 0; 407 while (mediaPacketListItem != mediaPacketList.end()) { 408 if (mediaLossMask[mediaPacketIdx] == 1) { 409 // Should have recovered this packet. 410 ForwardErrorCorrection::RecoveredPacketList::iterator 411 recoveredPacketListItem = recoveredPacketList.begin(); 412 413 ASSERT_FALSE(recoveredPacketListItem == 414 recoveredPacketList.end()) 415 << "Insufficient number of recovered packets."; 416 mediaPacket = *mediaPacketListItem; 417 ForwardErrorCorrection::RecoveredPacket* recoveredPacket = 418 *recoveredPacketListItem; 419 420 ASSERT_EQ(recoveredPacket->pkt->length, mediaPacket->length) 421 << "Recovered packet length not identical to original " 422 << "media packet"; 423 ASSERT_EQ(0, memcmp(recoveredPacket->pkt->data, 424 mediaPacket->data, mediaPacket->length)) 425 << "Recovered packet payload not identical to original " 426 << "media packet"; 427 delete recoveredPacket; 428 recoveredPacketList.pop_front(); 429 } 430 ++mediaPacketIdx; 431 ++mediaPacketListItem; 432 } 433 fec.ResetState(&recoveredPacketList); 434 ASSERT_TRUE(recoveredPacketList.empty()) 435 << "Excessive number of recovered packets.\t size is: " 436 << recoveredPacketList.size(); 437 // -- Teardown -- 438 mediaPacketListItem = mediaPacketList.begin(); 439 while (mediaPacketListItem != mediaPacketList.end()) { 440 delete *mediaPacketListItem; 441 ++mediaPacketListItem; 442 mediaPacketList.pop_front(); 443 } 444 assert(mediaPacketList.empty()); 445 446 fecPacketListItem = fecPacketList.begin(); 447 while (fecPacketListItem != fecPacketList.end()) { 448 ++fecPacketListItem; 449 fecPacketList.pop_front(); 450 } 451 452 // Delete received packets we didn't pass to DecodeFEC(), due to 453 // early frame completion. 454 ForwardErrorCorrection::ReceivedPacketList::iterator 455 receivedPacketIt = receivedPacketList.begin(); 456 while (receivedPacketIt != receivedPacketList.end()) { 457 receivedPacket = *receivedPacketIt; 458 delete receivedPacket; 459 ++receivedPacketIt; 460 receivedPacketList.pop_front(); 461 } 462 assert(receivedPacketList.empty()); 463 464 while (!fecMaskList.empty()) { 465 fecMaskList.pop_front(); 466 } 467 timeStamp += 90000 / 30; 468 } // loop over numImpPackets 469 } // loop over FecPackets 470 } // loop over numMediaPackets 471 delete[] packetMask; 472 } // loop over loss rates 473 } // loop over mask types 474 475 // Have DecodeFEC free allocated memory. 476 fec.ResetState(&recoveredPacketList); 477 ASSERT_TRUE(recoveredPacketList.empty()) 478 << "Recovered packet list is not empty"; 479 } 480 481 } // namespace test 482 } // namespace webrtc 483