src/third_party/webrtc/modules/rtp_rtcp/test/testFec/test_fec.cc

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