blob: a89b71bf94301eaf1a7d36d47bdacf52dec94fa3 [file] [log] [blame]
/*
* 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.
*/
#include "webrtc/modules/rtp_rtcp/source/forward_error_correction.h"
#include <string.h>
#include <algorithm>
#include <iterator>
#include <utility>
#include "webrtc/base/checks.h"
#include "webrtc/base/logging.h"
#include "webrtc/modules/rtp_rtcp/include/rtp_rtcp_defines.h"
#include "webrtc/modules/rtp_rtcp/source/byte_io.h"
#include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h"
namespace webrtc {
// FEC header size in bytes.
constexpr size_t kFecHeaderSize = 10;
// ULP header size in bytes (L bit is set).
constexpr size_t kUlpHeaderSizeLBitSet = (2 + kMaskSizeLBitSet);
// ULP header size in bytes (L bit is cleared).
constexpr size_t kUlpHeaderSizeLBitClear = (2 + kMaskSizeLBitClear);
// Transport header size in bytes. Assume UDP/IPv4 as a reasonable minimum.
constexpr size_t kTransportOverhead = 28;
// Maximum number of media packets that can be protected.
constexpr size_t ForwardErrorCorrection::kMaxMediaPackets;
// Maximum number of FEC packets stored internally.
constexpr size_t kMaxFecPackets = ForwardErrorCorrection::kMaxMediaPackets;
int32_t ForwardErrorCorrection::Packet::AddRef() {
return ++ref_count_;
}
int32_t ForwardErrorCorrection::Packet::Release() {
int32_t ref_count;
ref_count = --ref_count_;
if (ref_count == 0)
delete this;
return ref_count;
}
// This comparator is used to compare std::unique_ptr's pointing to
// subclasses of SortablePackets. It needs to be parametric since
// the std::unique_ptr's are not covariant w.r.t. the types that
// they are pointing to.
template <typename S, typename T>
bool ForwardErrorCorrection::SortablePacket::LessThan::operator() (
const S& first,
const T& second) {
return IsNewerSequenceNumber(second->seq_num, first->seq_num);
}
ForwardErrorCorrection::ReceivedPacket::ReceivedPacket() {}
ForwardErrorCorrection::ReceivedPacket::~ReceivedPacket() {}
ForwardErrorCorrection::RecoveredPacket::RecoveredPacket() {}
ForwardErrorCorrection::RecoveredPacket::~RecoveredPacket() {}
ForwardErrorCorrection::ForwardErrorCorrection()
: generated_fec_packets_(kMaxMediaPackets), received_fec_packets_(),
packet_mask_(), tmp_packet_mask_() {}
ForwardErrorCorrection::~ForwardErrorCorrection() {}
// Input packet
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | RTP Header (12 octets) |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | RTP Payload |
// | |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// Output packet
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | FEC Header (10 octets) |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | FEC Level 0 Header |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | FEC Level 0 Payload |
// | |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//
int ForwardErrorCorrection::EncodeFec(const PacketList& media_packets,
uint8_t protection_factor,
int num_important_packets,
bool use_unequal_protection,
FecMaskType fec_mask_type,
std::list<Packet*>* fec_packets) {
const size_t num_media_packets = media_packets.size();
// Sanity check arguments.
RTC_DCHECK_GT(num_media_packets, 0u);
RTC_DCHECK_GE(num_important_packets, 0);
RTC_DCHECK_LE(static_cast<size_t>(num_important_packets), num_media_packets);
RTC_DCHECK(fec_packets->empty());
if (num_media_packets > kMaxMediaPackets) {
LOG(LS_WARNING) << "Can't protect " << num_media_packets
<< " media packets per frame. Max is " << kMaxMediaPackets
<< ".";
return -1;
}
bool l_bit = (num_media_packets > 8 * kMaskSizeLBitClear);
int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;
// Error check the media packets.
for (const auto& media_packet : media_packets) {
RTC_DCHECK(media_packet);
if (media_packet->length < kRtpHeaderSize) {
LOG(LS_WARNING) << "Media packet " << media_packet->length << " bytes "
<< "is smaller than RTP header.";
return -1;
}
// Ensure the FEC packets will fit in a typical MTU.
if (media_packet->length + MaxPacketOverhead() + kTransportOverhead >
IP_PACKET_SIZE) {
LOG(LS_WARNING) << "Media packet " << media_packet->length << " bytes "
<< "with overhead is larger than " << IP_PACKET_SIZE
<< " bytes.";
}
}
int num_fec_packets = NumFecPackets(num_media_packets, protection_factor);
if (num_fec_packets == 0) {
return 0;
}
// Prepare generated FEC packets by setting them to 0.
for (int i = 0; i < num_fec_packets; ++i) {
memset(generated_fec_packets_[i].data, 0, IP_PACKET_SIZE);
// Use this as a marker for untouched packets.
generated_fec_packets_[i].length = 0;
fec_packets->push_back(&generated_fec_packets_[i]);
}
const internal::PacketMaskTable mask_table(fec_mask_type, num_media_packets);
// -- Generate packet masks --
memset(packet_mask_, 0, num_fec_packets * num_mask_bytes);
internal::GeneratePacketMasks(num_media_packets, num_fec_packets,
num_important_packets, use_unequal_protection,
mask_table, packet_mask_);
int num_mask_bits = InsertZerosInBitMasks(
media_packets, packet_mask_, num_mask_bytes, num_fec_packets);
if (num_mask_bits < 0) {
return -1;
}
l_bit = (static_cast<size_t>(num_mask_bits) > 8 * kMaskSizeLBitClear);
if (l_bit) {
num_mask_bytes = kMaskSizeLBitSet;
}
GenerateFecBitStrings(media_packets, packet_mask_, num_fec_packets, l_bit);
GenerateFecUlpHeaders(media_packets, packet_mask_, num_fec_packets, l_bit);
return 0;
}
int ForwardErrorCorrection::NumFecPackets(int num_media_packets,
int protection_factor) {
// Result in Q0 with an unsigned round.
int num_fec_packets = (num_media_packets * protection_factor + (1 << 7)) >> 8;
// Generate at least one FEC packet if we need protection.
if (protection_factor > 0 && num_fec_packets == 0) {
num_fec_packets = 1;
}
RTC_DCHECK_LE(num_fec_packets, num_media_packets);
return num_fec_packets;
}
void ForwardErrorCorrection::GenerateFecBitStrings(
const PacketList& media_packets,
uint8_t* packet_mask,
int num_fec_packets,
bool l_bit) {
RTC_DCHECK(!media_packets.empty());
uint8_t media_payload_length[2];
const int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;
const uint16_t ulp_header_size =
l_bit ? kUlpHeaderSizeLBitSet : kUlpHeaderSizeLBitClear;
const uint16_t fec_rtp_offset =
kFecHeaderSize + ulp_header_size - kRtpHeaderSize;
for (int i = 0; i < num_fec_packets; ++i) {
Packet* const fec_packet = &generated_fec_packets_[i];
auto media_packets_it = media_packets.cbegin();
uint32_t pkt_mask_idx = i * num_mask_bytes;
uint32_t media_pkt_idx = 0;
uint16_t fec_packet_length = 0;
uint16_t prev_seq_num = ParseSequenceNumber((*media_packets_it)->data);
while (media_packets_it != media_packets.end()) {
// Each FEC packet has a multiple byte mask. Determine if this media
// packet should be included in FEC packet i.
if (packet_mask[pkt_mask_idx] & (1 << (7 - media_pkt_idx))) {
Packet* media_packet = media_packets_it->get();
// Assign network-ordered media payload length.
ByteWriter<uint16_t>::WriteBigEndian(
media_payload_length, media_packet->length - kRtpHeaderSize);
fec_packet_length = media_packet->length + fec_rtp_offset;
// On the first protected packet, we don't need to XOR.
if (fec_packet->length == 0) {
// Copy the first 2 bytes of the RTP header. Note that the E and L
// bits are overwritten in GenerateFecUlpHeaders.
memcpy(&fec_packet->data[0], &media_packet->data[0], 2);
// Copy the 5th to 8th bytes of the RTP header (timestamp).
memcpy(&fec_packet->data[4], &media_packet->data[4], 4);
// Copy network-ordered payload size.
memcpy(&fec_packet->data[8], media_payload_length, 2);
// Copy RTP payload, leaving room for the ULP header.
memcpy(&fec_packet->data[kFecHeaderSize + ulp_header_size],
&media_packet->data[kRtpHeaderSize],
media_packet->length - kRtpHeaderSize);
} else {
// XOR with the first 2 bytes of the RTP header.
fec_packet->data[0] ^= media_packet->data[0];
fec_packet->data[1] ^= media_packet->data[1];
// XOR with the 5th to 8th bytes of the RTP header.
for (uint32_t j = 4; j < 8; ++j) {
fec_packet->data[j] ^= media_packet->data[j];
}
// XOR with the network-ordered payload size.
fec_packet->data[8] ^= media_payload_length[0];
fec_packet->data[9] ^= media_payload_length[1];
// XOR with RTP payload, leaving room for the ULP header.
for (int32_t j = kFecHeaderSize + ulp_header_size;
j < fec_packet_length; j++) {
fec_packet->data[j] ^= media_packet->data[j - fec_rtp_offset];
}
}
if (fec_packet_length > fec_packet->length) {
fec_packet->length = fec_packet_length;
}
}
media_packets_it++;
if (media_packets_it != media_packets.end()) {
uint16_t seq_num = ParseSequenceNumber((*media_packets_it)->data);
media_pkt_idx += static_cast<uint16_t>(seq_num - prev_seq_num);
prev_seq_num = seq_num;
}
pkt_mask_idx += media_pkt_idx / 8;
media_pkt_idx %= 8;
}
RTC_DCHECK_GT(fec_packet->length, 0u)
<< "Packet mask is wrong or poorly designed.";
}
}
int ForwardErrorCorrection::InsertZerosInBitMasks(
const PacketList& media_packets,
uint8_t* packet_mask,
int num_mask_bytes,
int num_fec_packets) {
if (media_packets.size() <= 1) {
return media_packets.size();
}
int last_seq_num = ParseSequenceNumber(media_packets.back()->data);
int first_seq_num = ParseSequenceNumber(media_packets.front()->data);
int total_missing_seq_nums =
static_cast<uint16_t>(last_seq_num - first_seq_num) -
media_packets.size() + 1;
if (total_missing_seq_nums == 0) {
// All sequence numbers are covered by the packet mask. No zero insertion
// required.
return media_packets.size();
}
// We can only protect 8 * kMaskSizeLBitSet packets.
if (total_missing_seq_nums + media_packets.size() > 8 * kMaskSizeLBitSet)
return -1;
// Allocate the new mask.
int new_mask_bytes = kMaskSizeLBitClear;
if (media_packets.size() +
total_missing_seq_nums > 8 * kMaskSizeLBitClear) {
new_mask_bytes = kMaskSizeLBitSet;
}
memset(tmp_packet_mask_, 0, num_fec_packets * kMaskSizeLBitSet);
auto media_packets_it = media_packets.cbegin();
uint16_t prev_seq_num = first_seq_num;
++media_packets_it;
// Insert the first column.
internal::CopyColumn(tmp_packet_mask_, new_mask_bytes, packet_mask_,
num_mask_bytes, num_fec_packets, 0, 0);
size_t new_bit_index = 1;
size_t old_bit_index = 1;
// Insert zeros in the bit mask for every hole in the sequence.
while (media_packets_it != media_packets.end()) {
if (new_bit_index == 8 * kMaskSizeLBitSet) {
// We can only cover up to 48 packets.
break;
}
uint16_t seq_num = ParseSequenceNumber((*media_packets_it)->data);
const int num_zeros_to_insert =
static_cast<uint16_t>(seq_num - prev_seq_num - 1);
if (num_zeros_to_insert > 0) {
internal::InsertZeroColumns(num_zeros_to_insert, tmp_packet_mask_,
new_mask_bytes, num_fec_packets,
new_bit_index);
}
new_bit_index += num_zeros_to_insert;
internal::CopyColumn(tmp_packet_mask_, new_mask_bytes, packet_mask_,
num_mask_bytes, num_fec_packets, new_bit_index,
old_bit_index);
++new_bit_index;
++old_bit_index;
prev_seq_num = seq_num;
++media_packets_it;
}
if (new_bit_index % 8 != 0) {
// We didn't fill the last byte. Shift bits to correct position.
for (uint16_t row = 0; row < num_fec_packets; ++row) {
int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
tmp_packet_mask_[new_byte_index] <<= (7 - (new_bit_index % 8));
}
}
// Replace the old mask with the new.
memcpy(packet_mask, tmp_packet_mask_, kMaskSizeLBitSet * num_fec_packets);
return new_bit_index;
}
void ForwardErrorCorrection::GenerateFecUlpHeaders(
const PacketList& media_packets,
uint8_t* packet_mask,
int num_fec_packets,
bool l_bit) {
// -- Generate FEC and ULP headers --
//
// FEC Header, 10 bytes
// 0 1 2 3
// 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// |E|L|P|X| CC |M| PT recovery | SN base |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | TS recovery |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | length recovery |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//
// ULP Header, 4 bytes (for L = 0)
// 0 1 2 3
// 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | Protection Length | mask |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | mask cont. (present only when L = 1) |
// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;
const uint16_t ulp_header_size =
l_bit ? kUlpHeaderSizeLBitSet : kUlpHeaderSizeLBitClear;
RTC_DCHECK(!media_packets.empty());
Packet* first_media_packet = media_packets.front().get();
RTC_DCHECK(first_media_packet);
uint16_t seq_num = ParseSequenceNumber(first_media_packet->data);
for (int i = 0; i < num_fec_packets; ++i) {
Packet* const fec_packet = &generated_fec_packets_[i];
// -- FEC header --
fec_packet->data[0] &= 0x7f; // Set E to zero.
if (l_bit == 0) {
fec_packet->data[0] &= 0xbf; // Clear the L bit.
} else {
fec_packet->data[0] |= 0x40; // Set the L bit.
}
// Sequence number from first media packet used as SN base.
// We use the same sequence number base for every FEC packet,
// but that's not required in general.
ByteWriter<uint16_t>::WriteBigEndian(&fec_packet->data[2], seq_num);
// -- ULP header --
// Copy the payload size to the protection length field.
// (We protect the entire packet.)
ByteWriter<uint16_t>::WriteBigEndian(
&fec_packet->data[10],
fec_packet->length - kFecHeaderSize - ulp_header_size);
// Copy the packet mask.
memcpy(&fec_packet->data[12], &packet_mask[i * num_mask_bytes],
num_mask_bytes);
}
}
void ForwardErrorCorrection::ResetState(
RecoveredPacketList* recovered_packets) {
// Free the memory for any existing recovered packets, if the caller hasn't.
recovered_packets->clear();
received_fec_packets_.clear();
}
void ForwardErrorCorrection::InsertMediaPacket(
ReceivedPacket* received_packet,
RecoveredPacketList* recovered_packets) {
// Search for duplicate packets.
for (const auto& recovered_packet : *recovered_packets) {
if (received_packet->seq_num == recovered_packet->seq_num) {
// Duplicate packet, no need to add to list.
// Delete duplicate media packet data.
received_packet->pkt = nullptr;
return;
}
}
std::unique_ptr<RecoveredPacket> recovered_packet(new RecoveredPacket());
// This "recovered packet" was not recovered using parity packets.
recovered_packet->was_recovered = false;
// This media packet has already been passed on.
recovered_packet->returned = true;
recovered_packet->seq_num = received_packet->seq_num;
recovered_packet->pkt = received_packet->pkt;
recovered_packet->pkt->length = received_packet->pkt->length;
RecoveredPacket* recovered_packet_ptr = recovered_packet.get();
// TODO(holmer): Consider replacing this with a binary search for the right
// position, and then just insert the new packet. Would get rid of the sort.
recovered_packets->push_back(std::move(recovered_packet));
recovered_packets->sort(SortablePacket::LessThan());
UpdateCoveringFecPackets(recovered_packet_ptr);
}
void ForwardErrorCorrection::UpdateCoveringFecPackets(RecoveredPacket* packet) {
for (auto& fec_packet : received_fec_packets_) {
// Is this FEC packet protecting the media packet |packet|?
auto protected_it = std::lower_bound(fec_packet->protected_packets.begin(),
fec_packet->protected_packets.end(),
packet,
SortablePacket::LessThan());
if (protected_it != fec_packet->protected_packets.end() &&
(*protected_it)->seq_num == packet->seq_num) {
// Found an FEC packet which is protecting |packet|.
(*protected_it)->pkt = packet->pkt;
}
}
}
void ForwardErrorCorrection::InsertFecPacket(
ReceivedPacket* received_packet,
const RecoveredPacketList* recovered_packets) {
// Check for duplicate.
for (const auto& existing_fec_packet : received_fec_packets_) {
if (received_packet->seq_num == existing_fec_packet->seq_num) {
// Delete duplicate FEC packet data.
received_packet->pkt = nullptr;
return;
}
}
std::unique_ptr<ReceivedFecPacket> fec_packet(new ReceivedFecPacket());
fec_packet->pkt = received_packet->pkt;
fec_packet->seq_num = received_packet->seq_num;
fec_packet->ssrc = received_packet->ssrc;
const uint16_t seq_num_base =
ByteReader<uint16_t>::ReadBigEndian(&fec_packet->pkt->data[2]);
const uint16_t mask_size_bytes = (fec_packet->pkt->data[0] & 0x40)
? kMaskSizeLBitSet
: kMaskSizeLBitClear; // L bit set?
// Parse erasure code mask from ULP header and represent as protected packets.
for (uint16_t byte_idx = 0; byte_idx < mask_size_bytes; ++byte_idx) {
uint8_t packet_mask = fec_packet->pkt->data[12 + byte_idx];
for (uint16_t bit_idx = 0; bit_idx < 8; ++bit_idx) {
if (packet_mask & (1 << (7 - bit_idx))) {
std::unique_ptr<ProtectedPacket> protected_packet(
new ProtectedPacket());
// This wraps naturally with the sequence number.
protected_packet->seq_num =
static_cast<uint16_t>(seq_num_base + (byte_idx << 3) + bit_idx);
protected_packet->pkt = nullptr;
// Note that |protected_pkt_list| is sorted (according to sequence
// number) by construction.
fec_packet->protected_packets.push_back(std::move(protected_packet));
}
}
}
if (fec_packet->protected_packets.empty()) {
// All-zero packet mask; we can discard this FEC packet.
LOG(LS_WARNING) << "Received FEC packet has an all-zero packet mask.";
} else {
AssignRecoveredPackets(fec_packet.get(), recovered_packets);
// TODO(holmer): Consider replacing this with a binary search for the right
// position, and then just insert the new packet. Would get rid of the sort.
//
// For correct decoding, |fec_packet_list_| does not necessarily
// need to be sorted by sequence number (see decoding algorithm in
// AttemptRecover()), but by keeping it sorted we try to recover the
// oldest lost packets first.
received_fec_packets_.push_back(std::move(fec_packet));
received_fec_packets_.sort(SortablePacket::LessThan());
if (received_fec_packets_.size() > kMaxFecPackets) {
received_fec_packets_.pop_front();
}
RTC_DCHECK_LE(received_fec_packets_.size(), kMaxFecPackets);
}
}
void ForwardErrorCorrection::AssignRecoveredPackets(
ReceivedFecPacket* fec_packet,
const RecoveredPacketList* recovered_packets) {
ProtectedPacketList* protected_packets = &fec_packet->protected_packets;
std::vector<RecoveredPacket*> recovered_protected_packets;
// Find intersection between the (sorted) containers |protected_packets|
// and |recovered_packets|, i.e. all protected packets that have already
// been recovered. Update the corresponding protected packets to point to
// the recovered packets.
auto it_p = protected_packets->cbegin();
auto it_r = recovered_packets->cbegin();
SortablePacket::LessThan less_than;
while (it_p != protected_packets->end() && it_r != recovered_packets->end()) {
if (less_than(*it_p, *it_r)) {
++it_p;
} else if (less_than(*it_r, *it_p)) {
++it_r;
} else { // *it_p == *it_r.
// This protected packet has already been recovered.
(*it_p)->pkt = (*it_r)->pkt;
++it_p;
++it_r;
}
}
}
void ForwardErrorCorrection::InsertPackets(
ReceivedPacketList* received_packets,
RecoveredPacketList* recovered_packets) {
while (!received_packets->empty()) {
ReceivedPacket* received_packet = received_packets->front().get();
// Check for discarding oldest FEC packet, to avoid wrong FEC decoding from
// sequence number wrap-around. Detection of old FEC packet is based on
// sequence number difference of received packet and oldest packet in FEC
// packet list.
// TODO(marpan/holmer): We should be able to improve detection/discarding of
// old FEC packets based on timestamp information or better sequence number
// thresholding (e.g., to distinguish between wrap-around and reordering).
if (!received_fec_packets_.empty()) {
uint16_t seq_num_diff =
abs(static_cast<int>(received_packet->seq_num) -
static_cast<int>(received_fec_packets_.front()->seq_num));
if (seq_num_diff > 0x3fff) {
received_fec_packets_.pop_front();
}
}
if (received_packet->is_fec) {
InsertFecPacket(received_packet, recovered_packets);
} else {
InsertMediaPacket(received_packet, recovered_packets);
}
// Delete the received packet "wrapper".
received_packets->pop_front();
}
RTC_DCHECK(received_packets->empty());
DiscardOldRecoveredPackets(recovered_packets);
}
bool ForwardErrorCorrection::StartPacketRecovery(
const ReceivedFecPacket* fec_packet,
RecoveredPacket* recovered_packet) {
// This is the first packet which we try to recover with.
const uint16_t ulp_header_size = fec_packet->pkt->data[0] & 0x40
? kUlpHeaderSizeLBitSet
: kUlpHeaderSizeLBitClear; // L bit set?
if (fec_packet->pkt->length <
static_cast<size_t>(kFecHeaderSize + ulp_header_size)) {
LOG(LS_WARNING)
<< "Truncated FEC packet doesn't contain room for ULP header.";
return false;
}
recovered_packet->pkt = new Packet();
memset(recovered_packet->pkt->data, 0, IP_PACKET_SIZE);
recovered_packet->returned = false;
recovered_packet->was_recovered = true;
uint16_t protection_length =
ByteReader<uint16_t>::ReadBigEndian(&fec_packet->pkt->data[10]);
if (protection_length >
std::min(
sizeof(recovered_packet->pkt->data) - kRtpHeaderSize,
sizeof(fec_packet->pkt->data) - kFecHeaderSize - ulp_header_size)) {
LOG(LS_WARNING) << "Incorrect FEC protection length, dropping.";
return false;
}
// Copy FEC payload, skipping the ULP header.
memcpy(&recovered_packet->pkt->data[kRtpHeaderSize],
&fec_packet->pkt->data[kFecHeaderSize + ulp_header_size],
protection_length);
// Copy the length recovery field.
memcpy(recovered_packet->length_recovery, &fec_packet->pkt->data[8], 2);
// Copy the first 2 bytes of the FEC header.
memcpy(recovered_packet->pkt->data, fec_packet->pkt->data, 2);
// Copy the 5th to 8th bytes of the FEC header.
memcpy(&recovered_packet->pkt->data[4], &fec_packet->pkt->data[4], 4);
// Set the SSRC field.
ByteWriter<uint32_t>::WriteBigEndian(&recovered_packet->pkt->data[8],
fec_packet->ssrc);
return true;
}
bool ForwardErrorCorrection::FinishPacketRecovery(
RecoveredPacket* recovered_packet) {
// Set the RTP version to 2.
recovered_packet->pkt->data[0] |= 0x80; // Set the 1st bit.
recovered_packet->pkt->data[0] &= 0xbf; // Clear the 2nd bit.
// Set the SN field.
ByteWriter<uint16_t>::WriteBigEndian(&recovered_packet->pkt->data[2],
recovered_packet->seq_num);
// Recover the packet length.
recovered_packet->pkt->length =
ByteReader<uint16_t>::ReadBigEndian(recovered_packet->length_recovery) +
kRtpHeaderSize;
if (recovered_packet->pkt->length >
sizeof(recovered_packet->pkt->data) - kRtpHeaderSize) {
return false;
}
return true;
}
void ForwardErrorCorrection::XorPackets(const Packet* src,
RecoveredPacket* dst) {
// XOR with the first 2 bytes of the RTP header.
for (uint32_t i = 0; i < 2; ++i) {
dst->pkt->data[i] ^= src->data[i];
}
// XOR with the 5th to 8th bytes of the RTP header.
for (uint32_t i = 4; i < 8; ++i) {
dst->pkt->data[i] ^= src->data[i];
}
// XOR with the network-ordered payload size.
uint8_t media_payload_length[2];
ByteWriter<uint16_t>::WriteBigEndian(media_payload_length,
src->length - kRtpHeaderSize);
dst->length_recovery[0] ^= media_payload_length[0];
dst->length_recovery[1] ^= media_payload_length[1];
// XOR with RTP payload.
// TODO(marpan/ajm): Are we doing more XORs than required here?
for (size_t i = kRtpHeaderSize; i < src->length; ++i) {
dst->pkt->data[i] ^= src->data[i];
}
}
bool ForwardErrorCorrection::RecoverPacket(
const ReceivedFecPacket* fec_packet,
RecoveredPacket* rec_packet_to_insert) {
if (!StartPacketRecovery(fec_packet, rec_packet_to_insert))
return false;
for (const auto& protected_packet : fec_packet->protected_packets) {
if (protected_packet->pkt == nullptr) {
// This is the packet we're recovering.
rec_packet_to_insert->seq_num = protected_packet->seq_num;
} else {
XorPackets(protected_packet->pkt, rec_packet_to_insert);
}
}
if (!FinishPacketRecovery(rec_packet_to_insert))
return false;
return true;
}
void ForwardErrorCorrection::AttemptRecover(
RecoveredPacketList* recovered_packets) {
auto fec_packet_it = received_fec_packets_.begin();
while (fec_packet_it != received_fec_packets_.end()) {
// Search for each FEC packet's protected media packets.
int packets_missing = NumCoveredPacketsMissing(fec_packet_it->get());
// We can only recover one packet with an FEC packet.
if (packets_missing == 1) {
// Recovery possible.
std::unique_ptr<RecoveredPacket> packet_to_insert(new RecoveredPacket());
packet_to_insert->pkt = nullptr;
if (!RecoverPacket(fec_packet_it->get(), packet_to_insert.get())) {
// Can't recover using this packet, drop it.
fec_packet_it = received_fec_packets_.erase(fec_packet_it);
continue;
}
auto packet_to_insert_ptr = packet_to_insert.get();
// Add recovered packet to the list of recovered packets and update any
// FEC packets covering this packet with a pointer to the data.
// TODO(holmer): Consider replacing this with a binary search for the
// right position, and then just insert the new packet. Would get rid of
// the sort.
recovered_packets->push_back(std::move(packet_to_insert));
recovered_packets->sort(SortablePacket::LessThan());
UpdateCoveringFecPackets(packet_to_insert_ptr);
DiscardOldRecoveredPackets(recovered_packets);
fec_packet_it = received_fec_packets_.erase(fec_packet_it);
// A packet has been recovered. We need to check the FEC list again, as
// this may allow additional packets to be recovered.
// Restart for first FEC packet.
fec_packet_it = received_fec_packets_.begin();
} else if (packets_missing == 0) {
// Either all protected packets arrived or have been recovered. We can
// discard this FEC packet.
fec_packet_it = received_fec_packets_.erase(fec_packet_it);
} else {
fec_packet_it++;
}
}
}
int ForwardErrorCorrection::NumCoveredPacketsMissing(
const ReceivedFecPacket* fec_packet) {
int packets_missing = 0;
for (const auto& protected_packet : fec_packet->protected_packets) {
if (protected_packet->pkt == nullptr) {
++packets_missing;
if (packets_missing > 1) {
break; // We can't recover more than one packet.
}
}
}
return packets_missing;
}
void ForwardErrorCorrection::DiscardOldRecoveredPackets(
RecoveredPacketList* recovered_packets) {
while (recovered_packets->size() > kMaxMediaPackets) {
recovered_packets->pop_front();
}
RTC_DCHECK_LE(recovered_packets->size(), kMaxMediaPackets);
}
uint16_t ForwardErrorCorrection::ParseSequenceNumber(uint8_t* packet) {
return (packet[2] << 8) + packet[3];
}
int ForwardErrorCorrection::DecodeFec(
ReceivedPacketList* received_packets,
RecoveredPacketList* recovered_packets) {
// TODO(marpan/ajm): can we check for multiple ULP headers, and return an
// error?
if (recovered_packets->size() == kMaxMediaPackets) {
const unsigned int seq_num_diff =
abs(static_cast<int>(received_packets->front()->seq_num) -
static_cast<int>(recovered_packets->back()->seq_num));
if (seq_num_diff > kMaxMediaPackets) {
// A big gap in sequence numbers. The old recovered packets
// are now useless, so it's safe to do a reset.
ResetState(recovered_packets);
}
}
InsertPackets(received_packets, recovered_packets);
AttemptRecover(recovered_packets);
return 0;
}
size_t ForwardErrorCorrection::MaxPacketOverhead() const {
return kFecHeaderSize + kUlpHeaderSizeLBitSet;
}
} // namespace webrtc