From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- .../test/testFec/average_residual_loss_xor_codes.h | 57 ++ .../modules/rtp_rtcp/test/testFec/test_fec.cc | 474 +++++++++ .../test/testFec/test_packet_masks_metrics.cc | 1060 ++++++++++++++++++++ 3 files changed, 1591 insertions(+) create mode 100644 third_party/libwebrtc/modules/rtp_rtcp/test/testFec/average_residual_loss_xor_codes.h create mode 100644 third_party/libwebrtc/modules/rtp_rtcp/test/testFec/test_fec.cc create mode 100644 third_party/libwebrtc/modules/rtp_rtcp/test/testFec/test_packet_masks_metrics.cc (limited to 'third_party/libwebrtc/modules/rtp_rtcp/test') diff --git a/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/average_residual_loss_xor_codes.h b/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/average_residual_loss_xor_codes.h new file mode 100644 index 0000000000..0bc2f56917 --- /dev/null +++ b/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/average_residual_loss_xor_codes.h @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2012 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ +#ifndef MODULES_RTP_RTCP_TEST_TESTFEC_AVERAGE_RESIDUAL_LOSS_XOR_CODES_H_ +#define MODULES_RTP_RTCP_TEST_TESTFEC_AVERAGE_RESIDUAL_LOSS_XOR_CODES_H_ + +namespace webrtc { + +// Maximum number of media packets allowed in this test. The burst mask types +// are currently defined up to (kMaxMediaPacketsTest, kMaxMediaPacketsTest). +const int kMaxMediaPacketsTest = 12; + +// Maximum number of FEC codes considered in this test. +const int kNumberCodes = kMaxMediaPacketsTest * (kMaxMediaPacketsTest + 1) / 2; + +// For the random mask type: reference level for the maximum average residual +// loss expected for each code size up to: +// (kMaxMediaPacketsTest, kMaxMediaPacketsTest). +const float kMaxResidualLossRandomMask[kNumberCodes] = { + 0.009463f, 0.022436f, 0.007376f, 0.033895f, 0.012423f, 0.004644f, 0.043438f, + 0.019937f, 0.008820f, 0.003438f, 0.051282f, 0.025795f, 0.012872f, 0.006458f, + 0.003195f, 0.057728f, 0.032146f, 0.016708f, 0.009242f, 0.005054f, 0.003078f, + 0.063050f, 0.037261f, 0.021767f, 0.012447f, 0.007099f, 0.003826f, 0.002504f, + 0.067476f, 0.042348f, 0.026169f, 0.015695f, 0.009478f, 0.005887f, 0.003568f, + 0.001689f, 0.071187f, 0.046575f, 0.031697f, 0.019797f, 0.012433f, 0.007027f, + 0.004845f, 0.002777f, 0.001753f, 0.074326f, 0.050628f, 0.034978f, 0.021955f, + 0.014821f, 0.009462f, 0.006393f, 0.004181f, 0.003105f, 0.001231f, 0.077008f, + 0.054226f, 0.038407f, 0.026251f, 0.018634f, 0.011568f, 0.008130f, 0.004957f, + 0.003334f, 0.002069f, 0.001304f, 0.079318f, 0.057180f, 0.041268f, 0.028842f, + 0.020033f, 0.014061f, 0.009636f, 0.006411f, 0.004583f, 0.002817f, 0.001770f, + 0.001258f}; + +// For the bursty mask type: reference level for the maximum average residual +// loss expected for each code size up to: +// (kMaxMediaPacketsTestf, kMaxMediaPacketsTest). +const float kMaxResidualLossBurstyMask[kNumberCodes] = { + 0.033236f, 0.053344f, 0.026616f, 0.064129f, 0.036589f, 0.021892f, 0.071055f, + 0.043890f, 0.028009f, 0.018524f, 0.075968f, 0.049828f, 0.033288f, 0.022791f, + 0.016088f, 0.079672f, 0.054586f, 0.037872f, 0.026679f, 0.019326f, 0.014293f, + 0.082582f, 0.058719f, 0.042045f, 0.030504f, 0.022391f, 0.016894f, 0.012946f, + 0.084935f, 0.062169f, 0.045620f, 0.033713f, 0.025570f, 0.019439f, 0.015121f, + 0.011920f, 0.086881f, 0.065267f, 0.048721f, 0.037613f, 0.028278f, 0.022152f, + 0.017314f, 0.013791f, 0.011130f, 0.088516f, 0.067911f, 0.051709f, 0.040819f, + 0.030777f, 0.024547f, 0.019689f, 0.015877f, 0.012773f, 0.010516f, 0.089909f, + 0.070332f, 0.054402f, 0.043210f, 0.034096f, 0.026625f, 0.021823f, 0.017648f, + 0.014649f, 0.011982f, 0.010035f, 0.091109f, 0.072428f, 0.056775f, 0.045418f, + 0.036679f, 0.028599f, 0.023693f, 0.019966f, 0.016603f, 0.013690f, 0.011359f, + 0.009657f}; + +} // namespace webrtc +#endif // MODULES_RTP_RTCP_TEST_TESTFEC_AVERAGE_RESIDUAL_LOSS_XOR_CODES_H_ diff --git a/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/test_fec.cc b/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/test_fec.cc new file mode 100644 index 0000000000..5ac8feca21 --- /dev/null +++ b/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/test_fec.cc @@ -0,0 +1,474 @@ +/* + * Copyright (c) 2012 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +/* + * Test application for core FEC algorithm. Calls encoding and decoding + * functions in ForwardErrorCorrection directly. + */ + +#include +#include + +#include + +#include "modules/rtp_rtcp/source/byte_io.h" +#include "modules/rtp_rtcp/source/forward_error_correction.h" +#include "modules/rtp_rtcp/source/forward_error_correction_internal.h" +#include "rtc_base/random.h" +#include "test/gtest.h" +#include "test/testsupport/file_utils.h" + +// #define VERBOSE_OUTPUT + +namespace webrtc { +namespace fec_private_tables { +extern const uint8_t** kPacketMaskBurstyTbl[12]; +} +namespace test { +using fec_private_tables::kPacketMaskBurstyTbl; + +void ReceivePackets( + std::vector>* + to_decode_list, + std::vector>* + received_packet_list, + size_t num_packets_to_decode, + float reorder_rate, + float duplicate_rate, + Random* random) { + RTC_DCHECK(to_decode_list->empty()); + RTC_DCHECK_LE(num_packets_to_decode, received_packet_list->size()); + + for (size_t i = 0; i < num_packets_to_decode; i++) { + auto it = received_packet_list->begin(); + // Reorder packets. + float random_variable = random->Rand(); + while (random_variable < reorder_rate) { + ++it; + if (it == received_packet_list->end()) { + --it; + break; + } + random_variable = random->Rand(); + } + to_decode_list->push_back(std::move(*it)); + received_packet_list->erase(it); + + // Duplicate packets. + ForwardErrorCorrection::ReceivedPacket* received_packet = + to_decode_list->back().get(); + random_variable = random->Rand(); + while (random_variable < duplicate_rate) { + std::unique_ptr duplicate_packet( + new ForwardErrorCorrection::ReceivedPacket()); + *duplicate_packet = *received_packet; + duplicate_packet->pkt = new ForwardErrorCorrection::Packet(); + duplicate_packet->pkt->data = received_packet->pkt->data; + + to_decode_list->push_back(std::move(duplicate_packet)); + random_variable = random->Rand(); + } + } +} + +void RunTest(bool use_flexfec) { + // TODO(marpan): Split this function into subroutines/helper functions. + enum { kMaxNumberMediaPackets = 48 }; + enum { kMaxNumberFecPackets = 48 }; + + const uint32_t kNumMaskBytesL0 = 2; + const uint32_t kNumMaskBytesL1 = 6; + + // FOR UEP + const bool kUseUnequalProtection = true; + + // FEC mask types. + const FecMaskType kMaskTypes[] = {kFecMaskRandom, kFecMaskBursty}; + const int kNumFecMaskTypes = sizeof(kMaskTypes) / sizeof(*kMaskTypes); + + // Maximum number of media packets allowed for the mask type. + const uint16_t kMaxMediaPackets[] = { + kMaxNumberMediaPackets, + sizeof(kPacketMaskBurstyTbl) / sizeof(*kPacketMaskBurstyTbl)}; + + ASSERT_EQ(12, kMaxMediaPackets[1]) << "Max media packets for bursty mode not " + "equal to 12."; + + ForwardErrorCorrection::PacketList media_packet_list; + std::list fec_packet_list; + std::vector> + to_decode_list; + std::vector> + received_packet_list; + ForwardErrorCorrection::RecoveredPacketList recovered_packet_list; + std::list fec_mask_list; + + // Running over only two loss rates to limit execution time. + const float loss_rate[] = {0.05f, 0.01f}; + const uint32_t loss_rate_size = sizeof(loss_rate) / sizeof(*loss_rate); + const float reorder_rate = 0.1f; + const float duplicate_rate = 0.1f; + + uint8_t media_loss_mask[kMaxNumberMediaPackets]; + uint8_t fec_loss_mask[kMaxNumberFecPackets]; + uint8_t fec_packet_masks[kMaxNumberFecPackets][kMaxNumberMediaPackets]; + + // Seed the random number generator, storing the seed to file in order to + // reproduce past results. + const unsigned int random_seed = static_cast(time(nullptr)); + Random random(random_seed); + std::string filename = webrtc::test::OutputPath() + "randomSeedLog.txt"; + FILE* random_seed_file = fopen(filename.c_str(), "a"); + fprintf(random_seed_file, "%u\n", random_seed); + fclose(random_seed_file); + random_seed_file = nullptr; + + uint16_t seq_num = 0; + uint32_t timestamp = random.Rand(); + const uint32_t media_ssrc = random.Rand(1u, 0xfffffffe); + uint32_t fec_ssrc; + uint16_t fec_seq_num_offset; + if (use_flexfec) { + fec_ssrc = random.Rand(1u, 0xfffffffe); + fec_seq_num_offset = random.Rand(0, 1 << 15); + } else { + fec_ssrc = media_ssrc; + fec_seq_num_offset = 0; + } + + std::unique_ptr fec; + if (use_flexfec) { + fec = ForwardErrorCorrection::CreateFlexfec(fec_ssrc, media_ssrc); + } else { + RTC_DCHECK_EQ(media_ssrc, fec_ssrc); + fec = ForwardErrorCorrection::CreateUlpfec(fec_ssrc); + } + + // Loop over the mask types: random and bursty. + for (int mask_type_idx = 0; mask_type_idx < kNumFecMaskTypes; + ++mask_type_idx) { + for (uint32_t loss_rate_idx = 0; loss_rate_idx < loss_rate_size; + ++loss_rate_idx) { + printf("Loss rate: %.2f, Mask type %d \n", loss_rate[loss_rate_idx], + mask_type_idx); + + const uint32_t packet_mask_max = kMaxMediaPackets[mask_type_idx]; + std::unique_ptr packet_mask( + new uint8_t[packet_mask_max * kNumMaskBytesL1]); + + FecMaskType fec_mask_type = kMaskTypes[mask_type_idx]; + + for (uint32_t num_media_packets = 1; num_media_packets <= packet_mask_max; + num_media_packets++) { + internal::PacketMaskTable mask_table(fec_mask_type, num_media_packets); + + for (uint32_t num_fec_packets = 1; + num_fec_packets <= num_media_packets && + num_fec_packets <= packet_mask_max; + num_fec_packets++) { + // Loop over num_imp_packets: usually <= (0.3*num_media_packets). + // For this test we check up to ~ (num_media_packets / 4). + uint32_t max_num_imp_packets = num_media_packets / 4 + 1; + for (uint32_t num_imp_packets = 0; + num_imp_packets <= max_num_imp_packets && + num_imp_packets <= packet_mask_max; + num_imp_packets++) { + uint8_t protection_factor = + static_cast(num_fec_packets * 255 / num_media_packets); + + const uint32_t mask_bytes_per_fec_packet = + (num_media_packets > 16) ? kNumMaskBytesL1 : kNumMaskBytesL0; + + memset(packet_mask.get(), 0, + num_media_packets * mask_bytes_per_fec_packet); + + // Transfer packet masks from bit-mask to byte-mask. + internal::GeneratePacketMasks( + num_media_packets, num_fec_packets, num_imp_packets, + kUseUnequalProtection, &mask_table, packet_mask.get()); + +#ifdef VERBOSE_OUTPUT + printf( + "%u media packets, %u FEC packets, %u num_imp_packets, " + "loss rate = %.2f \n", + num_media_packets, num_fec_packets, num_imp_packets, + loss_rate[loss_rate_idx]); + printf("Packet mask matrix \n"); +#endif + + for (uint32_t i = 0; i < num_fec_packets; i++) { + for (uint32_t j = 0; j < num_media_packets; j++) { + const uint8_t byte_mask = + packet_mask[i * mask_bytes_per_fec_packet + j / 8]; + const uint32_t bit_position = (7 - j % 8); + fec_packet_masks[i][j] = + (byte_mask & (1 << bit_position)) >> bit_position; +#ifdef VERBOSE_OUTPUT + printf("%u ", fec_packet_masks[i][j]); +#endif + } +#ifdef VERBOSE_OUTPUT + printf("\n"); +#endif + } +#ifdef VERBOSE_OUTPUT + printf("\n"); +#endif + // Check for all zero rows or columns: indicates incorrect mask. + uint32_t row_limit = num_media_packets; + for (uint32_t i = 0; i < num_fec_packets; ++i) { + uint32_t row_sum = 0; + for (uint32_t j = 0; j < row_limit; ++j) { + row_sum += fec_packet_masks[i][j]; + } + ASSERT_NE(0u, row_sum) << "Row is all zero " << i; + } + for (uint32_t j = 0; j < row_limit; ++j) { + uint32_t column_sum = 0; + for (uint32_t i = 0; i < num_fec_packets; ++i) { + column_sum += fec_packet_masks[i][j]; + } + ASSERT_NE(0u, column_sum) << "Column is all zero " << j; + } + + // Construct media packets. + // Reset the sequence number here for each FEC code/mask tested + // below, to avoid sequence number wrap-around. In actual decoding, + // old FEC packets in list are dropped if sequence number wrap + // around is detected. This case is currently not handled below. + seq_num = 0; + for (uint32_t i = 0; i < num_media_packets; ++i) { + std::unique_ptr media_packet( + new ForwardErrorCorrection::Packet()); + const uint32_t kMinPacketSize = 12; + const uint32_t kMaxPacketSize = static_cast( + IP_PACKET_SIZE - 12 - 28 - fec->MaxPacketOverhead()); + size_t packet_length = + random.Rand(kMinPacketSize, kMaxPacketSize); + media_packet->data.SetSize(packet_length); + + uint8_t* data = media_packet->data.MutableData(); + // Generate random values for the first 2 bytes. + data[0] = random.Rand(); + data[1] = random.Rand(); + + // The first two bits are assumed to be 10 by the + // FEC encoder. In fact the FEC decoder will set the + // two first bits to 10 regardless of what they + // actually were. Set the first two bits to 10 + // so that a memcmp can be performed for the + // whole restored packet. + data[0] |= 0x80; + data[0] &= 0xbf; + + // FEC is applied to a whole frame. + // A frame is signaled by multiple packets without + // the marker bit set followed by the last packet of + // the frame for which the marker bit is set. + // Only push one (fake) frame to the FEC. + data[1] &= 0x7f; + + ByteWriter::WriteBigEndian(&data[2], seq_num); + ByteWriter::WriteBigEndian(&data[4], timestamp); + ByteWriter::WriteBigEndian(&data[8], media_ssrc); + // Generate random values for payload + for (size_t j = 12; j < packet_length; ++j) { + data[j] = random.Rand(); + } + media_packet_list.push_back(std::move(media_packet)); + seq_num++; + } + media_packet_list.back()->data.MutableData()[1] |= 0x80; + + ASSERT_EQ(0, fec->EncodeFec(media_packet_list, protection_factor, + num_imp_packets, kUseUnequalProtection, + fec_mask_type, &fec_packet_list)) + << "EncodeFec() failed"; + + ASSERT_EQ(num_fec_packets, fec_packet_list.size()) + << "We requested " << num_fec_packets + << " FEC packets, but " + "EncodeFec() produced " + << fec_packet_list.size(); + + memset(media_loss_mask, 0, sizeof(media_loss_mask)); + uint32_t media_packet_idx = 0; + for (const auto& media_packet : media_packet_list) { + // We want a value between 0 and 1. + const float loss_random_variable = random.Rand(); + + if (loss_random_variable >= loss_rate[loss_rate_idx]) { + media_loss_mask[media_packet_idx] = 1; + std::unique_ptr + received_packet( + new ForwardErrorCorrection::ReceivedPacket()); + received_packet->pkt = new ForwardErrorCorrection::Packet(); + received_packet->pkt->data = media_packet->data; + received_packet->ssrc = media_ssrc; + received_packet->seq_num = ByteReader::ReadBigEndian( + media_packet->data.data() + 2); + received_packet->is_fec = false; + received_packet_list.push_back(std::move(received_packet)); + } + media_packet_idx++; + } + + memset(fec_loss_mask, 0, sizeof(fec_loss_mask)); + uint32_t fec_packet_idx = 0; + for (auto* fec_packet : fec_packet_list) { + const float loss_random_variable = random.Rand(); + if (loss_random_variable >= loss_rate[loss_rate_idx]) { + fec_loss_mask[fec_packet_idx] = 1; + std::unique_ptr + received_packet( + new ForwardErrorCorrection::ReceivedPacket()); + received_packet->pkt = new ForwardErrorCorrection::Packet(); + received_packet->pkt->data = fec_packet->data; + received_packet->seq_num = fec_seq_num_offset + seq_num; + received_packet->is_fec = true; + received_packet->ssrc = fec_ssrc; + received_packet_list.push_back(std::move(received_packet)); + + fec_mask_list.push_back(fec_packet_masks[fec_packet_idx]); + } + ++fec_packet_idx; + ++seq_num; + } + +#ifdef VERBOSE_OUTPUT + printf("Media loss mask:\n"); + for (uint32_t i = 0; i < num_media_packets; i++) { + printf("%u ", media_loss_mask[i]); + } + printf("\n\n"); + + printf("FEC loss mask:\n"); + for (uint32_t i = 0; i < num_fec_packets; i++) { + printf("%u ", fec_loss_mask[i]); + } + printf("\n\n"); +#endif + + auto fec_mask_it = fec_mask_list.begin(); + while (fec_mask_it != fec_mask_list.end()) { + uint32_t hamming_dist = 0; + uint32_t recovery_position = 0; + for (uint32_t i = 0; i < num_media_packets; i++) { + if (media_loss_mask[i] == 0 && (*fec_mask_it)[i] == 1) { + recovery_position = i; + ++hamming_dist; + } + } + auto item_to_delete = fec_mask_it; + ++fec_mask_it; + + if (hamming_dist == 1) { + // Recovery possible. Restart search. + media_loss_mask[recovery_position] = 1; + fec_mask_it = fec_mask_list.begin(); + } else if (hamming_dist == 0) { + // FEC packet cannot provide further recovery. + fec_mask_list.erase(item_to_delete); + } + } +#ifdef VERBOSE_OUTPUT + printf("Recovery mask:\n"); + for (uint32_t i = 0; i < num_media_packets; ++i) { + printf("%u ", media_loss_mask[i]); + } + printf("\n\n"); +#endif + // For error-checking frame completion. + bool fec_packet_received = false; + while (!received_packet_list.empty()) { + size_t num_packets_to_decode = random.Rand( + 1u, static_cast(received_packet_list.size())); + ReceivePackets(&to_decode_list, &received_packet_list, + num_packets_to_decode, reorder_rate, + duplicate_rate, &random); + + if (fec_packet_received == false) { + for (const auto& received_packet : to_decode_list) { + if (received_packet->is_fec) { + fec_packet_received = true; + } + } + } + for (const auto& received_packet : to_decode_list) { + fec->DecodeFec(*received_packet, &recovered_packet_list); + } + to_decode_list.clear(); + } + media_packet_idx = 0; + for (const auto& media_packet : media_packet_list) { + if (media_loss_mask[media_packet_idx] == 1) { + // Should have recovered this packet. + auto recovered_packet_list_it = recovered_packet_list.cbegin(); + + ASSERT_FALSE(recovered_packet_list_it == + recovered_packet_list.end()) + << "Insufficient number of recovered packets."; + ForwardErrorCorrection::RecoveredPacket* recovered_packet = + recovered_packet_list_it->get(); + + ASSERT_EQ(recovered_packet->pkt->data.size(), + media_packet->data.size()) + << "Recovered packet length not identical to original " + "media packet"; + ASSERT_EQ(0, memcmp(recovered_packet->pkt->data.cdata(), + media_packet->data.cdata(), + media_packet->data.size())) + << "Recovered packet payload not identical to original " + "media packet"; + recovered_packet_list.pop_front(); + } + ++media_packet_idx; + } + fec->ResetState(&recovered_packet_list); + ASSERT_TRUE(recovered_packet_list.empty()) + << "Excessive number of recovered packets.\t size is: " + << recovered_packet_list.size(); + // -- Teardown -- + media_packet_list.clear(); + + // Clear FEC packet list, so we don't pass in a non-empty + // list in the next call to DecodeFec(). + fec_packet_list.clear(); + + // Delete received packets we didn't pass to DecodeFec(), due to + // early frame completion. + received_packet_list.clear(); + + while (!fec_mask_list.empty()) { + fec_mask_list.pop_front(); + } + timestamp += 90000 / 30; + } // loop over num_imp_packets + } // loop over FecPackets + } // loop over num_media_packets + } // loop over loss rates + } // loop over mask types + + // Have DecodeFec clear the recovered packet list. + fec->ResetState(&recovered_packet_list); + ASSERT_TRUE(recovered_packet_list.empty()) + << "Recovered packet list is not empty"; +} + +TEST(FecTest, UlpfecTest) { + RunTest(false); +} + +TEST(FecTest, FlexfecTest) { + RunTest(true); +} + +} // namespace test +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/test_packet_masks_metrics.cc b/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/test_packet_masks_metrics.cc new file mode 100644 index 0000000000..25ceee585a --- /dev/null +++ b/third_party/libwebrtc/modules/rtp_rtcp/test/testFec/test_packet_masks_metrics.cc @@ -0,0 +1,1060 @@ +/* + * Copyright (c) 2012 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +/* + * The purpose of this test is to compute metrics to characterize the properties + * and efficiency of the packets masks used in the generic XOR FEC code. + * + * The metrics measure the efficiency (recovery potential or residual loss) of + * the FEC code, under various statistical loss models for the packet/symbol + * loss events. Various constraints on the behavior of these metrics are + * verified, and compared to the reference RS (Reed-Solomon) code. This serves + * in some way as a basic check/benchmark for the packet masks. + * + * By an FEC code, we mean an erasure packet/symbol code, characterized by: + * (1) The code size parameters (k,m), where k = number of source/media packets, + * and m = number of FEC packets, + * (2) The code type: XOR or RS. + * In the case of XOR, the residual loss is determined via the set of packet + * masks (generator matrix). In the case of RS, the residual loss is determined + * directly from the MDS (maximum distance separable) property of RS. + * + * Currently two classes of packets masks are available (random type and bursty + * type), so three codes are considered below: RS, XOR-random, and XOR-bursty. + * The bursty class is defined up to k=12, so (k=12,m=12) is largest code size + * considered in this test. + * + * The XOR codes are defined via the RFC 5109 and correspond to the class of + * LDGM (low density generator matrix) codes, which is a subset of the LDPC + * (low density parity check) codes. Future implementation will consider + * extending our XOR codes to include LDPC codes, which explicitly include + * protection of FEC packets. + * + * The type of packet/symbol loss models considered in this test are: + * (1) Random loss: Bernoulli process, characterized by the average loss rate. + * (2) Bursty loss: Markov chain (Gilbert-Elliot model), characterized by two + * parameters: average loss rate and average burst length. + */ + +#include +#include + +#include "modules/rtp_rtcp/source/forward_error_correction_internal.h" +#include "modules/rtp_rtcp/test/testFec/average_residual_loss_xor_codes.h" +#include "test/gtest.h" +#include "test/testsupport/file_utils.h" + +namespace webrtc { + +// Maximum number of media packets allows for XOR (RFC 5109) code. +enum { kMaxNumberMediaPackets = 48 }; + +// Maximum number of media packets allowed for each mask type. +const uint16_t kMaxMediaPackets[] = {kMaxNumberMediaPackets, 12}; + +// Maximum gap size for characterizing the consecutiveness of the loss. +const int kMaxGapSize = 2 * kMaxMediaPacketsTest; + +// Number of gap levels written to file/output. +const int kGapSizeOutput = 5; + +// Maximum number of states for characterizing the residual loss distribution. +const int kNumStatesDistribution = 2 * kMaxMediaPacketsTest * kMaxGapSize + 1; + +// The code type. +enum CodeType { + xor_random_code, // XOR with random mask type. + xor_bursty_code, // XOR with bursty mask type. + rs_code // Reed_solomon. +}; + +// The code size parameters. +struct CodeSizeParams { + int num_media_packets; + int num_fec_packets; + // Protection level: num_fec_packets / (num_media_packets + num_fec_packets). + float protection_level; + // Number of loss configurations, for a given loss number and gap number. + // The gap number refers to the maximum gap/hole of a loss configuration + // (used to measure the "consecutiveness" of the loss). + int configuration_density[kNumStatesDistribution]; +}; + +// The type of loss models. +enum LossModelType { kRandomLossModel, kBurstyLossModel }; + +struct LossModel { + LossModelType loss_type; + float average_loss_rate; + float average_burst_length; +}; + +// Average loss rates. +const float kAverageLossRate[] = {0.025f, 0.05f, 0.1f, 0.25f}; + +// Average burst lengths. The case of |kAverageBurstLength = 1.0| refers to +// the random model. Note that for the random (Bernoulli) model, the average +// burst length is determined by the average loss rate, i.e., +// AverageBurstLength = 1 / (1 - AverageLossRate) for random model. +const float kAverageBurstLength[] = {1.0f, 2.0f, 4.0f}; + +// Total number of loss models: For each burst length case, there are +// a number of models corresponding to the loss rates. +const int kNumLossModels = + (sizeof(kAverageBurstLength) / sizeof(*kAverageBurstLength)) * + (sizeof(kAverageLossRate) / sizeof(*kAverageLossRate)); + +// Thresholds on the average loss rate of the packet loss model, below which +// certain properties of the codes are expected. +float loss_rate_upper_threshold = 0.20f; +float loss_rate_lower_threshold = 0.025f; + +// Set of thresholds on the expected average recovery rate, for each code type. +// These are global thresholds for now; in future version we may condition them +// on the code length/size and protection level. +const float kRecoveryRateXorRandom[3] = {0.94f, 0.50f, 0.19f}; +const float kRecoveryRateXorBursty[3] = {0.90f, 0.54f, 0.22f}; + +// Metrics for a given FEC code; each code is defined by the code type +// (RS, XOR-random/bursty), and the code size parameters (k,m), where +// k = num_media_packets, m = num_fec_packets. +struct MetricsFecCode { + // The average and variance of the residual loss, as a function of the + // packet/symbol loss model. The average/variance is computed by averaging + // over all loss configurations wrt the loss probability given by the + // underlying loss model. + double average_residual_loss[kNumLossModels]; + double variance_residual_loss[kNumLossModels]; + // The residual loss, as a function of the loss number and the gap number of + // the loss configurations. The gap number refers to the maximum gap/hole of + // a loss configuration (used to measure the "consecutiveness" of the loss). + double residual_loss_per_loss_gap[kNumStatesDistribution]; + // The recovery rate as a function of the loss number. + double recovery_rate_per_loss[2 * kMaxMediaPacketsTest + 1]; +}; + +MetricsFecCode kMetricsXorRandom[kNumberCodes]; +MetricsFecCode kMetricsXorBursty[kNumberCodes]; +MetricsFecCode kMetricsReedSolomon[kNumberCodes]; + +class FecPacketMaskMetricsTest : public ::testing::Test { + protected: + FecPacketMaskMetricsTest() {} + + int max_num_codes_; + LossModel loss_model_[kNumLossModels]; + CodeSizeParams code_params_[kNumberCodes]; + + uint8_t fec_packet_masks_[kMaxNumberMediaPackets][kMaxNumberMediaPackets]; + FILE* fp_mask_; + + // Measure of the gap of the loss for configuration given by `state`. + // This is to measure degree of consecutiveness for the loss configuration. + // Useful if the packets are sent out in order of sequence numbers and there + // is little/no re-ordering during transmission. + int GapLoss(int tot_num_packets, uint8_t* state) { + int max_gap_loss = 0; + // Find the first loss. + int first_loss = 0; + for (int i = 0; i < tot_num_packets; i++) { + if (state[i] == 1) { + first_loss = i; + break; + } + } + int prev_loss = first_loss; + for (int i = first_loss + 1; i < tot_num_packets; i++) { + if (state[i] == 1) { // Lost state. + int gap_loss = (i - prev_loss) - 1; + if (gap_loss > max_gap_loss) { + max_gap_loss = gap_loss; + } + prev_loss = i; + } + } + return max_gap_loss; + } + + // Returns the number of recovered media packets for the XOR code, given the + // packet mask `fec_packet_masks_`, for the loss state/configuration given by + // `state`. + int RecoveredMediaPackets(int num_media_packets, + int num_fec_packets, + uint8_t* state) { + std::unique_ptr state_tmp( + new uint8_t[num_media_packets + num_fec_packets]); + memcpy(state_tmp.get(), state, num_media_packets + num_fec_packets); + int num_recovered_packets = 0; + bool loop_again = true; + while (loop_again) { + loop_again = false; + bool recovered_new_packet = false; + // Check if we can recover anything: loop over all possible FEC packets. + for (int i = 0; i < num_fec_packets; i++) { + if (state_tmp[i + num_media_packets] == 0) { + // We have this FEC packet. + int num_packets_in_mask = 0; + int num_received_packets_in_mask = 0; + for (int j = 0; j < num_media_packets; j++) { + if (fec_packet_masks_[i][j] == 1) { + num_packets_in_mask++; + if (state_tmp[j] == 0) { + num_received_packets_in_mask++; + } + } + } + if ((num_packets_in_mask - 1) == num_received_packets_in_mask) { + // We can recover the missing media packet for this FEC packet. + num_recovered_packets++; + recovered_new_packet = true; + int jsel = -1; + int check_num_recovered = 0; + // Update the state with newly recovered media packet. + for (int j = 0; j < num_media_packets; j++) { + if (fec_packet_masks_[i][j] == 1 && state_tmp[j] == 1) { + // This is the lost media packet we will recover. + jsel = j; + check_num_recovered++; + } + } + // Check that we can only recover 1 packet. + RTC_DCHECK_EQ(check_num_recovered, 1); + // Update the state with the newly recovered media packet. + state_tmp[jsel] = 0; + } + } + } // Go to the next FEC packet in the loop. + // If we have recovered at least one new packet in this FEC loop, + // go through loop again, otherwise we leave loop. + if (recovered_new_packet) { + loop_again = true; + } + } + return num_recovered_packets; + } + + // Compute the probability of occurence of the loss state/configuration, + // given by `state`, for all the loss models considered in this test. + void ComputeProbabilityWeight(double* prob_weight, + uint8_t* state, + int tot_num_packets) { + // Loop over the loss models. + for (int k = 0; k < kNumLossModels; k++) { + double loss_rate = static_cast(loss_model_[k].average_loss_rate); + double burst_length = + static_cast(loss_model_[k].average_burst_length); + double result = 1.0; + if (loss_model_[k].loss_type == kRandomLossModel) { + for (int i = 0; i < tot_num_packets; i++) { + if (state[i] == 0) { + result *= (1.0 - loss_rate); + } else { + result *= loss_rate; + } + } + } else { // Gilbert-Elliot model for burst model. + RTC_DCHECK_EQ(loss_model_[k].loss_type, kBurstyLossModel); + // Transition probabilities: from previous to current state. + // Prob. of previous = lost --> current = received. + double prob10 = 1.0 / burst_length; + // Prob. of previous = lost --> currrent = lost. + double prob11 = 1.0 - prob10; + // Prob. of previous = received --> current = lost. + double prob01 = prob10 * (loss_rate / (1.0 - loss_rate)); + // Prob. of previous = received --> current = received. + double prob00 = 1.0 - prob01; + + // Use stationary probability for first state/packet. + if (state[0] == 0) { // Received + result = (1.0 - loss_rate); + } else { // Lost + result = loss_rate; + } + + // Subsequent states: use transition probabilities. + for (int i = 1; i < tot_num_packets; i++) { + // Current state is received + if (state[i] == 0) { + if (state[i - 1] == 0) { + result *= prob00; // Previous received, current received. + } else { + result *= prob10; // Previous lost, current received. + } + } else { // Current state is lost + if (state[i - 1] == 0) { + result *= prob01; // Previous received, current lost. + } else { + result *= prob11; // Previous lost, current lost. + } + } + } + } + prob_weight[k] = result; + } + } + + void CopyMetrics(MetricsFecCode* metrics_output, + MetricsFecCode metrics_input) { + memcpy(metrics_output->average_residual_loss, + metrics_input.average_residual_loss, + sizeof(double) * kNumLossModels); + memcpy(metrics_output->variance_residual_loss, + metrics_input.variance_residual_loss, + sizeof(double) * kNumLossModels); + memcpy(metrics_output->residual_loss_per_loss_gap, + metrics_input.residual_loss_per_loss_gap, + sizeof(double) * kNumStatesDistribution); + memcpy(metrics_output->recovery_rate_per_loss, + metrics_input.recovery_rate_per_loss, + sizeof(double) * 2 * kMaxMediaPacketsTest); + } + + // Compute the residual loss per gap, by summing the + // `residual_loss_per_loss_gap` over all loss configurations up to loss number + // = `num_fec_packets`. + double ComputeResidualLossPerGap(MetricsFecCode metrics, + int gap_number, + int num_fec_packets, + int code_index) { + double residual_loss_gap = 0.0; + int tot_num_configs = 0; + for (int loss = 1; loss <= num_fec_packets; loss++) { + int index = gap_number * (2 * kMaxMediaPacketsTest) + loss; + residual_loss_gap += metrics.residual_loss_per_loss_gap[index]; + tot_num_configs += code_params_[code_index].configuration_density[index]; + } + // Normalize, to compare across code sizes. + if (tot_num_configs > 0) { + residual_loss_gap = + residual_loss_gap / static_cast(tot_num_configs); + } + return residual_loss_gap; + } + + // Compute the recovery rate per loss number, by summing the + // `residual_loss_per_loss_gap` over all gap configurations. + void ComputeRecoveryRatePerLoss(MetricsFecCode* metrics, + int num_media_packets, + int num_fec_packets, + int code_index) { + for (int loss = 1; loss <= num_media_packets + num_fec_packets; loss++) { + metrics->recovery_rate_per_loss[loss] = 0.0; + int tot_num_configs = 0; + double arl = 0.0; + for (int gap = 0; gap < kMaxGapSize; gap++) { + int index = gap * (2 * kMaxMediaPacketsTest) + loss; + arl += metrics->residual_loss_per_loss_gap[index]; + tot_num_configs += + code_params_[code_index].configuration_density[index]; + } + // Normalize, to compare across code sizes. + if (tot_num_configs > 0) { + arl = arl / static_cast(tot_num_configs); + } + // Recovery rate for a given loss `loss` is 1 minus the scaled `arl`, + // where the scale factor is relative to code size/parameters. + double scaled_loss = + static_cast(loss * num_media_packets) / + static_cast(num_media_packets + num_fec_packets); + metrics->recovery_rate_per_loss[loss] = 1.0 - arl / scaled_loss; + } + } + + void SetMetricsZero(MetricsFecCode* metrics) { + memset(metrics->average_residual_loss, 0, sizeof(double) * kNumLossModels); + memset(metrics->variance_residual_loss, 0, sizeof(double) * kNumLossModels); + memset(metrics->residual_loss_per_loss_gap, 0, + sizeof(double) * kNumStatesDistribution); + memset(metrics->recovery_rate_per_loss, 0, + sizeof(double) * 2 * kMaxMediaPacketsTest + 1); + } + + // Compute the metrics for an FEC code, given by the code type `code_type` + // (XOR-random/ bursty or RS), and by the code index `code_index` + // (which containes the code size parameters/protection length). + void ComputeMetricsForCode(CodeType code_type, int code_index) { + std::unique_ptr prob_weight(new double[kNumLossModels]); + memset(prob_weight.get(), 0, sizeof(double) * kNumLossModels); + MetricsFecCode metrics_code; + SetMetricsZero(&metrics_code); + + int num_media_packets = code_params_[code_index].num_media_packets; + int num_fec_packets = code_params_[code_index].num_fec_packets; + int tot_num_packets = num_media_packets + num_fec_packets; + std::unique_ptr state(new uint8_t[tot_num_packets]); + memset(state.get(), 0, tot_num_packets); + + int num_loss_configurations = 1 << tot_num_packets; + // Loop over all loss configurations for the symbol sequence of length + // `tot_num_packets`. In this version we process up to (k=12, m=12) codes, + // and get exact expressions for the residual loss. + // TODO(marpan): For larger codes, loop over some random sample of loss + // configurations, sampling driven by the underlying statistical loss model + // (importance sampling). + + // The symbols/packets are arranged as a sequence of source/media packets + // followed by FEC packets. This is the sequence ordering used in the RTP. + // A configuration refers to a sequence of received/lost (0/1 bit) states + // for the string of packets/symbols. For example, for a (k=4,m=3) code + // (4 media packets, 3 FEC packets), with 2 losses (one media and one FEC), + // the loss configurations is: + // Media1 Media2 Media3 Media4 FEC1 FEC2 FEC3 + // 0 0 1 0 0 1 0 + for (int i = 1; i < num_loss_configurations; i++) { + // Counter for number of packets lost. + int num_packets_lost = 0; + // Counters for the number of media packets lost. + int num_media_packets_lost = 0; + + // Map configuration number to a loss state. + for (int j = 0; j < tot_num_packets; j++) { + state[j] = 0; // Received state. + int bit_value = i >> (tot_num_packets - j - 1) & 1; + if (bit_value == 1) { + state[j] = 1; // Lost state. + num_packets_lost++; + if (j < num_media_packets) { + num_media_packets_lost++; + } + } + } // Done with loop over total number of packets. + RTC_DCHECK_LE(num_media_packets_lost, num_media_packets); + RTC_DCHECK_LE(num_packets_lost, tot_num_packets && num_packets_lost > 0); + double residual_loss = 0.0; + // Only need to compute residual loss (number of recovered packets) for + // configurations that have at least one media packet lost. + if (num_media_packets_lost >= 1) { + // Compute the number of recovered packets. + int num_recovered_packets = 0; + if (code_type == xor_random_code || code_type == xor_bursty_code) { + num_recovered_packets = RecoveredMediaPackets( + num_media_packets, num_fec_packets, state.get()); + } else { + // For the RS code, we can either completely recover all the packets + // if the loss is less than or equal to the number of FEC packets, + // otherwise we can recover none of the missing packets. This is the + // all or nothing (MDS) property of the RS code. + if (num_packets_lost <= num_fec_packets) { + num_recovered_packets = num_media_packets_lost; + } + } + RTC_DCHECK_LE(num_recovered_packets, num_media_packets); + // Compute the residual loss. We only care about recovering media/source + // packets, so residual loss is based on lost/recovered media packets. + residual_loss = + static_cast(num_media_packets_lost - num_recovered_packets); + // Compute the probability weights for this configuration. + ComputeProbabilityWeight(prob_weight.get(), state.get(), + tot_num_packets); + // Update the average and variance of the residual loss. + for (int k = 0; k < kNumLossModels; k++) { + metrics_code.average_residual_loss[k] += + residual_loss * prob_weight[k]; + metrics_code.variance_residual_loss[k] += + residual_loss * residual_loss * prob_weight[k]; + } + } // Done with processing for num_media_packets_lost >= 1. + // Update the distribution statistics. + // Compute the gap of the loss (the "consecutiveness" of the loss). + int gap_loss = GapLoss(tot_num_packets, state.get()); + RTC_DCHECK_LT(gap_loss, kMaxGapSize); + int index = gap_loss * (2 * kMaxMediaPacketsTest) + num_packets_lost; + RTC_DCHECK_LT(index, kNumStatesDistribution); + metrics_code.residual_loss_per_loss_gap[index] += residual_loss; + if (code_type == xor_random_code) { + // The configuration density is only a function of the code length and + // only needs to computed for the first `code_type` passed here. + code_params_[code_index].configuration_density[index]++; + } + } // Done with loop over configurations. + // Normalize the average residual loss and compute/normalize the variance. + for (int k = 0; k < kNumLossModels; k++) { + // Normalize the average residual loss by the total number of packets + // `tot_num_packets` (i.e., the code length). For a code with no (zero) + // recovery, the average residual loss for that code would be reduced like + // ~`average_loss_rate` * `num_media_packets` / `tot_num_packets`. This is + // the expected reduction in the average residual loss just from adding + // FEC packets to the symbol sequence. + metrics_code.average_residual_loss[k] = + metrics_code.average_residual_loss[k] / + static_cast(tot_num_packets); + metrics_code.variance_residual_loss[k] = + metrics_code.variance_residual_loss[k] / + static_cast(num_media_packets * num_media_packets); + metrics_code.variance_residual_loss[k] = + metrics_code.variance_residual_loss[k] - + (metrics_code.average_residual_loss[k] * + metrics_code.average_residual_loss[k]); + RTC_DCHECK_GE(metrics_code.variance_residual_loss[k], 0.0); + RTC_DCHECK_GT(metrics_code.average_residual_loss[k], 0.0); + metrics_code.variance_residual_loss[k] = + std::sqrt(metrics_code.variance_residual_loss[k]) / + metrics_code.average_residual_loss[k]; + } + + // Compute marginal distribution as a function of loss parameter. + ComputeRecoveryRatePerLoss(&metrics_code, num_media_packets, + num_fec_packets, code_index); + if (code_type == rs_code) { + CopyMetrics(&kMetricsReedSolomon[code_index], metrics_code); + } else if (code_type == xor_random_code) { + CopyMetrics(&kMetricsXorRandom[code_index], metrics_code); + } else if (code_type == xor_bursty_code) { + CopyMetrics(&kMetricsXorBursty[code_index], metrics_code); + } else { + RTC_DCHECK_NOTREACHED(); + } + } + + void WriteOutMetricsAllFecCodes() { + std::string filename = test::OutputPath() + "data_metrics_all_codes"; + FILE* fp = fopen(filename.c_str(), "wb"); + // Loop through codes up to `kMaxMediaPacketsTest`. + int code_index = 0; + for (int num_media_packets = 1; num_media_packets <= kMaxMediaPacketsTest; + num_media_packets++) { + for (int num_fec_packets = 1; num_fec_packets <= num_media_packets; + num_fec_packets++) { + fprintf(fp, "FOR CODE: (%d, %d) \n", num_media_packets, + num_fec_packets); + for (int k = 0; k < kNumLossModels; k++) { + float loss_rate = loss_model_[k].average_loss_rate; + float burst_length = loss_model_[k].average_burst_length; + fprintf( + fp, + "Loss rate = %.2f, Burst length = %.2f: %.4f %.4f %.4f" + " **** %.4f %.4f %.4f \n", + loss_rate, burst_length, + 100 * kMetricsReedSolomon[code_index].average_residual_loss[k], + 100 * kMetricsXorRandom[code_index].average_residual_loss[k], + 100 * kMetricsXorBursty[code_index].average_residual_loss[k], + kMetricsReedSolomon[code_index].variance_residual_loss[k], + kMetricsXorRandom[code_index].variance_residual_loss[k], + kMetricsXorBursty[code_index].variance_residual_loss[k]); + } + for (int gap = 0; gap < kGapSizeOutput; gap++) { + double rs_residual_loss = + ComputeResidualLossPerGap(kMetricsReedSolomon[code_index], gap, + num_fec_packets, code_index); + double xor_random_residual_loss = ComputeResidualLossPerGap( + kMetricsXorRandom[code_index], gap, num_fec_packets, code_index); + double xor_bursty_residual_loss = ComputeResidualLossPerGap( + kMetricsXorBursty[code_index], gap, num_fec_packets, code_index); + fprintf(fp, + "Residual loss as a function of gap " + "%d: %.4f %.4f %.4f \n", + gap, rs_residual_loss, xor_random_residual_loss, + xor_bursty_residual_loss); + } + fprintf(fp, "Recovery rate as a function of loss number \n"); + for (int loss = 1; loss <= num_media_packets + num_fec_packets; + loss++) { + fprintf(fp, "For loss number %d: %.4f %.4f %.4f \n", loss, + kMetricsReedSolomon[code_index].recovery_rate_per_loss[loss], + kMetricsXorRandom[code_index].recovery_rate_per_loss[loss], + kMetricsXorBursty[code_index].recovery_rate_per_loss[loss]); + } + fprintf(fp, "******************\n"); + fprintf(fp, "\n"); + code_index++; + } + } + fclose(fp); + } + + void SetLossModels() { + int num_loss_rates = sizeof(kAverageLossRate) / sizeof(*kAverageLossRate); + int num_burst_lengths = + sizeof(kAverageBurstLength) / sizeof(*kAverageBurstLength); + int num_loss_models = 0; + for (int k = 0; k < num_burst_lengths; k++) { + for (int k2 = 0; k2 < num_loss_rates; k2++) { + loss_model_[num_loss_models].average_loss_rate = kAverageLossRate[k2]; + loss_model_[num_loss_models].average_burst_length = + kAverageBurstLength[k]; + // First set of loss models are of random type. + if (k == 0) { + loss_model_[num_loss_models].loss_type = kRandomLossModel; + } else { + loss_model_[num_loss_models].loss_type = kBurstyLossModel; + } + num_loss_models++; + } + } + RTC_DCHECK_EQ(num_loss_models, kNumLossModels); + } + + void SetCodeParams() { + int code_index = 0; + for (int num_media_packets = 1; num_media_packets <= kMaxMediaPacketsTest; + num_media_packets++) { + for (int num_fec_packets = 1; num_fec_packets <= num_media_packets; + num_fec_packets++) { + code_params_[code_index].num_media_packets = num_media_packets; + code_params_[code_index].num_fec_packets = num_fec_packets; + code_params_[code_index].protection_level = + static_cast(num_fec_packets) / + static_cast(num_media_packets + num_fec_packets); + for (int k = 0; k < kNumStatesDistribution; k++) { + code_params_[code_index].configuration_density[k] = 0; + } + code_index++; + } + } + max_num_codes_ = code_index; + } + + // Make some basic checks on the packet masks. Return -1 if any of these + // checks fail. + int RejectInvalidMasks(int num_media_packets, int num_fec_packets) { + // Make sure every FEC packet protects something. + for (int i = 0; i < num_fec_packets; i++) { + int row_degree = 0; + for (int j = 0; j < num_media_packets; j++) { + if (fec_packet_masks_[i][j] == 1) { + row_degree++; + } + } + if (row_degree == 0) { + printf( + "Invalid mask: FEC packet has empty mask (does not protect " + "anything) %d %d %d \n", + i, num_media_packets, num_fec_packets); + return -1; + } + } + // Mask sure every media packet has some protection. + for (int j = 0; j < num_media_packets; j++) { + int column_degree = 0; + for (int i = 0; i < num_fec_packets; i++) { + if (fec_packet_masks_[i][j] == 1) { + column_degree++; + } + } + if (column_degree == 0) { + printf( + "Invalid mask: Media packet has no protection at all %d %d %d " + "\n", + j, num_media_packets, num_fec_packets); + return -1; + } + } + // Make sure we do not have two identical FEC packets. + for (int i = 0; i < num_fec_packets; i++) { + for (int i2 = i + 1; i2 < num_fec_packets; i2++) { + int overlap = 0; + for (int j = 0; j < num_media_packets; j++) { + if (fec_packet_masks_[i][j] == fec_packet_masks_[i2][j]) { + overlap++; + } + } + if (overlap == num_media_packets) { + printf("Invalid mask: Two FEC packets are identical %d %d %d %d \n", + i, i2, num_media_packets, num_fec_packets); + return -1; + } + } + } + // Avoid codes that have two media packets with full protection (all 1s in + // their corresponding columns). This would mean that if we lose those + // two packets, we can never recover them even if we receive all the other + // packets. Exclude the special cases of 1 or 2 FEC packets. + if (num_fec_packets > 2) { + for (int j = 0; j < num_media_packets; j++) { + for (int j2 = j + 1; j2 < num_media_packets; j2++) { + int degree = 0; + for (int i = 0; i < num_fec_packets; i++) { + if (fec_packet_masks_[i][j] == fec_packet_masks_[i][j2] && + fec_packet_masks_[i][j] == 1) { + degree++; + } + } + if (degree == num_fec_packets) { + printf( + "Invalid mask: Two media packets are have full degree " + "%d %d %d %d \n", + j, j2, num_media_packets, num_fec_packets); + return -1; + } + } + } + } + return 0; + } + + void GetPacketMaskConvertToBitMask(uint8_t* packet_mask, + int num_media_packets, + int num_fec_packets, + int mask_bytes_fec_packet, + CodeType code_type) { + for (int i = 0; i < num_fec_packets; i++) { + for (int j = 0; j < num_media_packets; j++) { + const uint8_t byte_mask = + packet_mask[i * mask_bytes_fec_packet + j / 8]; + const int bit_position = (7 - j % 8); + fec_packet_masks_[i][j] = + (byte_mask & (1 << bit_position)) >> bit_position; + fprintf(fp_mask_, "%d ", fec_packet_masks_[i][j]); + } + fprintf(fp_mask_, "\n"); + } + fprintf(fp_mask_, "\n"); + } + + int ProcessXORPacketMasks(CodeType code_type, FecMaskType fec_mask_type) { + int code_index = 0; + // Maximum number of media packets allowed for the mask type. + const int packet_mask_max = kMaxMediaPackets[fec_mask_type]; + std::unique_ptr packet_mask( + new uint8_t[packet_mask_max * kUlpfecMaxPacketMaskSize]); + // Loop through codes up to `kMaxMediaPacketsTest`. + for (int num_media_packets = 1; num_media_packets <= kMaxMediaPacketsTest; + ++num_media_packets) { + const int mask_bytes_fec_packet = + static_cast(internal::PacketMaskSize(num_media_packets)); + internal::PacketMaskTable mask_table(fec_mask_type, num_media_packets); + for (int num_fec_packets = 1; num_fec_packets <= num_media_packets; + num_fec_packets++) { + memset(packet_mask.get(), 0, num_media_packets * mask_bytes_fec_packet); + rtc::ArrayView mask = + mask_table.LookUp(num_media_packets, num_fec_packets); + memcpy(packet_mask.get(), &mask[0], mask.size()); + // Convert to bit mask. + GetPacketMaskConvertToBitMask(packet_mask.get(), num_media_packets, + num_fec_packets, mask_bytes_fec_packet, + code_type); + if (RejectInvalidMasks(num_media_packets, num_fec_packets) < 0) { + return -1; + } + // Compute the metrics for this code/mask. + ComputeMetricsForCode(code_type, code_index); + code_index++; + } + } + RTC_DCHECK_EQ(code_index, kNumberCodes); + return 0; + } + + void ProcessRS(CodeType code_type) { + int code_index = 0; + for (int num_media_packets = 1; num_media_packets <= kMaxMediaPacketsTest; + num_media_packets++) { + for (int num_fec_packets = 1; num_fec_packets <= num_media_packets; + num_fec_packets++) { + // Compute the metrics for this code type. + ComputeMetricsForCode(code_type, code_index); + code_index++; + } + } + } + + // Compute metrics for all code types and sizes. + void ComputeMetricsAllCodes() { + SetLossModels(); + SetCodeParams(); + // Get metrics for XOR code with packet masks of random type. + std::string filename = test::OutputPath() + "data_packet_masks"; + fp_mask_ = fopen(filename.c_str(), "wb"); + fprintf(fp_mask_, "MASK OF TYPE RANDOM: \n"); + EXPECT_EQ(ProcessXORPacketMasks(xor_random_code, kFecMaskRandom), 0); + // Get metrics for XOR code with packet masks of bursty type. + fprintf(fp_mask_, "MASK OF TYPE BURSTY: \n"); + EXPECT_EQ(ProcessXORPacketMasks(xor_bursty_code, kFecMaskBursty), 0); + fclose(fp_mask_); + // Get metrics for Reed-Solomon code. + ProcessRS(rs_code); + } +}; + +// Verify that the average residual loss, averaged over loss models +// appropriate to each mask type, is below some maximum acceptable level. The +// acceptable levels are read in from a file, and correspond to a current set +// of packet masks. The levels for each code may be updated over time. +TEST_F(FecPacketMaskMetricsTest, FecXorMaxResidualLoss) { + SetLossModels(); + SetCodeParams(); + ComputeMetricsAllCodes(); + WriteOutMetricsAllFecCodes(); + int num_loss_rates = sizeof(kAverageLossRate) / sizeof(*kAverageLossRate); + int num_burst_lengths = + sizeof(kAverageBurstLength) / sizeof(*kAverageBurstLength); + for (int code_index = 0; code_index < max_num_codes_; code_index++) { + double sum_residual_loss_random_mask_random_loss = 0.0; + double sum_residual_loss_bursty_mask_bursty_loss = 0.0; + // Compute the sum residual loss across the models, for each mask type. + for (int k = 0; k < kNumLossModels; k++) { + if (loss_model_[k].loss_type == kRandomLossModel) { + sum_residual_loss_random_mask_random_loss += + kMetricsXorRandom[code_index].average_residual_loss[k]; + } else if (loss_model_[k].loss_type == kBurstyLossModel) { + sum_residual_loss_bursty_mask_bursty_loss += + kMetricsXorBursty[code_index].average_residual_loss[k]; + } + } + float average_residual_loss_random_mask_random_loss = + sum_residual_loss_random_mask_random_loss / num_loss_rates; + float average_residual_loss_bursty_mask_bursty_loss = + sum_residual_loss_bursty_mask_bursty_loss / + (num_loss_rates * (num_burst_lengths - 1)); + const float ref_random_mask = kMaxResidualLossRandomMask[code_index]; + const float ref_bursty_mask = kMaxResidualLossBurstyMask[code_index]; + EXPECT_LE(average_residual_loss_random_mask_random_loss, ref_random_mask); + EXPECT_LE(average_residual_loss_bursty_mask_bursty_loss, ref_bursty_mask); + } +} + +// Verify the behavior of the XOR codes vs the RS codes. +// For random loss model with average loss rates <= the code protection level, +// the RS code (optimal MDS code) is more efficient than XOR codes. +// However, for larger loss rates (above protection level) and/or bursty +// loss models, the RS is not always more efficient than XOR (though in most +// cases it still is). +TEST_F(FecPacketMaskMetricsTest, FecXorVsRS) { + SetLossModels(); + SetCodeParams(); + for (int code_index = 0; code_index < max_num_codes_; code_index++) { + for (int k = 0; k < kNumLossModels; k++) { + float loss_rate = loss_model_[k].average_loss_rate; + float protection_level = code_params_[code_index].protection_level; + // Under these conditions we expect XOR to not be better than RS. + if (loss_model_[k].loss_type == kRandomLossModel && + loss_rate <= protection_level) { + EXPECT_GE(kMetricsXorRandom[code_index].average_residual_loss[k], + kMetricsReedSolomon[code_index].average_residual_loss[k]); + EXPECT_GE(kMetricsXorBursty[code_index].average_residual_loss[k], + kMetricsReedSolomon[code_index].average_residual_loss[k]); + } + // TODO(marpan): There are some cases (for high loss rates and/or + // burst loss models) where XOR is better than RS. Is there some pattern + // we can identify and enforce as a constraint? + } + } +} + +// Verify the trend (change) in the average residual loss, as a function of +// loss rate, of the XOR code relative to the RS code. +// The difference between XOR and RS should not get worse as we increase +// the average loss rate. +TEST_F(FecPacketMaskMetricsTest, FecTrendXorVsRsLossRate) { + SetLossModels(); + SetCodeParams(); + // TODO(marpan): Examine this further to see if the condition can be strictly + // satisfied (i.e., scale = 1.0) for all codes with different/better masks. + double scale = 0.90; + int num_loss_rates = sizeof(kAverageLossRate) / sizeof(*kAverageLossRate); + int num_burst_lengths = + sizeof(kAverageBurstLength) / sizeof(*kAverageBurstLength); + for (int code_index = 0; code_index < max_num_codes_; code_index++) { + for (int i = 0; i < num_burst_lengths; i++) { + for (int j = 0; j < num_loss_rates - 1; j++) { + int k = num_loss_rates * i + j; + // For XOR random. + if (kMetricsXorRandom[code_index].average_residual_loss[k] > + kMetricsReedSolomon[code_index].average_residual_loss[k]) { + double diff_rs_xor_random_loss1 = + (kMetricsXorRandom[code_index].average_residual_loss[k] - + kMetricsReedSolomon[code_index].average_residual_loss[k]) / + kMetricsXorRandom[code_index].average_residual_loss[k]; + double diff_rs_xor_random_loss2 = + (kMetricsXorRandom[code_index].average_residual_loss[k + 1] - + kMetricsReedSolomon[code_index].average_residual_loss[k + 1]) / + kMetricsXorRandom[code_index].average_residual_loss[k + 1]; + EXPECT_GE(diff_rs_xor_random_loss1, scale * diff_rs_xor_random_loss2); + } + // TODO(marpan): Investigate the cases for the bursty mask where + // this trend is not strictly satisfied. + } + } + } +} + +// Verify the average residual loss behavior via the protection level and +// the code length. The average residual loss for a given (k1,m1) code +// should generally be higher than that of another code (k2,m2), which has +// either of the two conditions satisfied: +// 1) higher protection & code length at least as large: (k2+m2) >= (k1+m1), +// 2) equal protection and larger code length: (k2+m2) > (k1+m1). +// Currently does not hold for some cases of the XOR code with random mask. +TEST_F(FecPacketMaskMetricsTest, FecBehaviorViaProtectionLevelAndLength) { + SetLossModels(); + SetCodeParams(); + for (int code_index1 = 0; code_index1 < max_num_codes_; code_index1++) { + float protection_level1 = code_params_[code_index1].protection_level; + int length1 = code_params_[code_index1].num_media_packets + + code_params_[code_index1].num_fec_packets; + for (int code_index2 = 0; code_index2 < max_num_codes_; code_index2++) { + float protection_level2 = code_params_[code_index2].protection_level; + int length2 = code_params_[code_index2].num_media_packets + + code_params_[code_index2].num_fec_packets; + // Codes with higher protection are more efficient, conditioned on the + // length of the code (higher protection but shorter length codes are + // generally not more efficient). For two codes with equal protection, + // the longer code is generally more efficient. For high loss rate + // models, this condition may be violated for some codes with equal or + // very close protection levels. High loss rate case is excluded below. + if ((protection_level2 > protection_level1 && length2 >= length1) || + (protection_level2 == protection_level1 && length2 > length1)) { + for (int k = 0; k < kNumLossModels; k++) { + float loss_rate = loss_model_[k].average_loss_rate; + if (loss_rate < loss_rate_upper_threshold) { + EXPECT_LT( + kMetricsReedSolomon[code_index2].average_residual_loss[k], + kMetricsReedSolomon[code_index1].average_residual_loss[k]); + // TODO(marpan): There are some corner cases where this is not + // satisfied with the current packet masks. Look into updating + // these cases to see if this behavior should/can be satisfied, + // with overall lower residual loss for those XOR codes. + // EXPECT_LT( + // kMetricsXorBursty[code_index2].average_residual_loss[k], + // kMetricsXorBursty[code_index1].average_residual_loss[k]); + // EXPECT_LT( + // kMetricsXorRandom[code_index2].average_residual_loss[k], + // kMetricsXorRandom[code_index1].average_residual_loss[k]); + } + } + } + } + } +} + +// Verify the beheavior of the variance of the XOR codes. +// The partial recovery of the XOR versus the all or nothing behavior of the RS +// code means that the variance of the residual loss for XOR should generally +// not be worse than RS. +TEST_F(FecPacketMaskMetricsTest, FecVarianceBehaviorXorVsRs) { + SetLossModels(); + SetCodeParams(); + // The condition is not strictly satisfied with the current masks, + // i.e., for some codes, the variance of XOR may be slightly higher than RS. + // TODO(marpan): Examine this further to see if the condition can be strictly + // satisfied (i.e., scale = 1.0) for all codes with different/better masks. + double scale = 0.95; + for (int code_index = 0; code_index < max_num_codes_; code_index++) { + for (int k = 0; k < kNumLossModels; k++) { + EXPECT_LE(scale * kMetricsXorRandom[code_index].variance_residual_loss[k], + kMetricsReedSolomon[code_index].variance_residual_loss[k]); + EXPECT_LE(scale * kMetricsXorBursty[code_index].variance_residual_loss[k], + kMetricsReedSolomon[code_index].variance_residual_loss[k]); + } + } +} + +// For the bursty mask type, the residual loss must be strictly zero for all +// consecutive losses (i.e, gap = 0) with number of losses <= num_fec_packets. +// This is a design property of the bursty mask type. +TEST_F(FecPacketMaskMetricsTest, FecXorBurstyPerfectRecoveryConsecutiveLoss) { + SetLossModels(); + SetCodeParams(); + for (int code_index = 0; code_index < max_num_codes_; code_index++) { + int num_fec_packets = code_params_[code_index].num_fec_packets; + for (int loss = 1; loss <= num_fec_packets; loss++) { + int index = loss; // `gap` is zero. + EXPECT_EQ(kMetricsXorBursty[code_index].residual_loss_per_loss_gap[index], + 0.0); + } + } +} + +// The XOR codes with random mask type are generally better than the ones with +// bursty mask type, for random loss models at low loss rates. +// The XOR codes with bursty mask types are generally better than the one with +// random mask type, for bursty loss models and/or high loss rates. +// TODO(marpan): Enable this test when some of the packet masks are updated. +// Some isolated cases of the codes don't pass this currently. +/* +TEST_F(FecPacketMaskMetricsTest, FecXorRandomVsBursty) { + SetLossModels(); + SetCodeParams(); + for (int code_index = 0; code_index < max_num_codes_; code_index++) { + double sum_residual_loss_random_mask_random_loss = 0.0; + double sum_residual_loss_bursty_mask_random_loss = 0.0; + double sum_residual_loss_random_mask_bursty_loss = 0.0; + double sum_residual_loss_bursty_mask_bursty_loss = 0.0; + // Compute the sum residual loss across the models, for each mask type. + for (int k = 0; k < kNumLossModels; k++) { + float loss_rate = loss_model_[k].average_loss_rate; + if (loss_model_[k].loss_type == kRandomLossModel && + loss_rate < loss_rate_upper_threshold) { + sum_residual_loss_random_mask_random_loss += + kMetricsXorRandom[code_index].average_residual_loss[k]; + sum_residual_loss_bursty_mask_random_loss += + kMetricsXorBursty[code_index].average_residual_loss[k]; + } else if (loss_model_[k].loss_type == kBurstyLossModel && + loss_rate > loss_rate_lower_threshold) { + sum_residual_loss_random_mask_bursty_loss += + kMetricsXorRandom[code_index].average_residual_loss[k]; + sum_residual_loss_bursty_mask_bursty_loss += + kMetricsXorBursty[code_index].average_residual_loss[k]; + } + } + EXPECT_LE(sum_residual_loss_random_mask_random_loss, + sum_residual_loss_bursty_mask_random_loss); + EXPECT_LE(sum_residual_loss_bursty_mask_bursty_loss, + sum_residual_loss_random_mask_bursty_loss); + } +} +*/ + +// Verify that the average recovery rate for each code is equal or above some +// threshold, for certain loss number conditions. +TEST_F(FecPacketMaskMetricsTest, FecRecoveryRateUnderLossConditions) { + SetLossModels(); + SetCodeParams(); + for (int code_index = 0; code_index < max_num_codes_; code_index++) { + int num_media_packets = code_params_[code_index].num_media_packets; + int num_fec_packets = code_params_[code_index].num_fec_packets; + // Perfect recovery (`recovery_rate_per_loss` == 1) is expected for + // `loss_number` = 1, for all codes. + int loss_number = 1; + EXPECT_EQ( + kMetricsReedSolomon[code_index].recovery_rate_per_loss[loss_number], + 1.0); + EXPECT_EQ(kMetricsXorRandom[code_index].recovery_rate_per_loss[loss_number], + 1.0); + EXPECT_EQ(kMetricsXorBursty[code_index].recovery_rate_per_loss[loss_number], + 1.0); + // For `loss_number` = `num_fec_packets` / 2, we expect the following: + // Perfect recovery for RS, and recovery for XOR above the threshold. + loss_number = num_fec_packets / 2 > 0 ? num_fec_packets / 2 : 1; + EXPECT_EQ( + kMetricsReedSolomon[code_index].recovery_rate_per_loss[loss_number], + 1.0); + EXPECT_GE(kMetricsXorRandom[code_index].recovery_rate_per_loss[loss_number], + kRecoveryRateXorRandom[0]); + EXPECT_GE(kMetricsXorBursty[code_index].recovery_rate_per_loss[loss_number], + kRecoveryRateXorBursty[0]); + // For `loss_number` = `num_fec_packets`, we expect the following: + // Perfect recovery for RS, and recovery for XOR above the threshold. + loss_number = num_fec_packets; + EXPECT_EQ( + kMetricsReedSolomon[code_index].recovery_rate_per_loss[loss_number], + 1.0); + EXPECT_GE(kMetricsXorRandom[code_index].recovery_rate_per_loss[loss_number], + kRecoveryRateXorRandom[1]); + EXPECT_GE(kMetricsXorBursty[code_index].recovery_rate_per_loss[loss_number], + kRecoveryRateXorBursty[1]); + // For `loss_number` = `num_fec_packets` + 1, we expect the following: + // Zero recovery for RS, but non-zero recovery for XOR. + if (num_fec_packets > 1 && num_media_packets > 2) { + loss_number = num_fec_packets + 1; + EXPECT_EQ( + kMetricsReedSolomon[code_index].recovery_rate_per_loss[loss_number], + 0.0); + EXPECT_GE( + kMetricsXorRandom[code_index].recovery_rate_per_loss[loss_number], + kRecoveryRateXorRandom[2]); + EXPECT_GE( + kMetricsXorBursty[code_index].recovery_rate_per_loss[loss_number], + kRecoveryRateXorBursty[2]); + } + } +} + +} // namespace webrtc -- cgit v1.2.3