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