blob: a7588a85824b22b04758812b62c8927ccd9f661b [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 <list>
#include <vector>
#include "modules/rtp_rtcp/interface/rtp_rtcp_defines.h"
#include "system_wrappers/interface/ref_count.h"
#include "system_wrappers/interface/scoped_refptr.h"
#include "typedefs.h"
namespace webrtc {
// Forward declaration.
class FecPacket;
* Performs codec-independent forward error correction (FEC), based on RFC 5109.
* Option exists to enable unequal protection (UEP) across packets.
* This is not to be confused with protection within packets
* (referred to as uneven level protection (ULP) in RFC 5109).
class ForwardErrorCorrection {
// Maximum number of media packets we can protect
static const unsigned int kMaxMediaPackets = 48u;
// TODO(holmer): As a next step all these struct-like packet classes should be
// refactored into proper classes, and their members should be made private.
// This will require parts of the functionality in
// and to be refactored into the packet classes.
class Packet {
Packet() : length(0), data(), ref_count_(0) {}
virtual ~Packet() {}
// Add a reference.
virtual int32_t AddRef() {
return ++ref_count_;
// Release a reference. Will delete the object if the reference count
// reaches zero.
virtual int32_t Release() {
int32_t ref_count;
ref_count = --ref_count_;
if (ref_count == 0)
delete this;
return ref_count;
uint16_t length; // Length of packet in bytes.
uint8_t data[IP_PACKET_SIZE]; // Packet data.
int32_t ref_count_; // Counts the number of references to a packet.
// TODO(holmer): Refactor into a proper class.
class SortablePacket {
// True if first is <= than second.
static bool LessThan(const SortablePacket* first,
const SortablePacket* second);
uint16_t seqNum;
* The received list parameter of #DecodeFEC() must reference structs of this
* type. The lastMediaPktInFrame is not required to be used for correct
* recovery, but will reduce delay by allowing #DecodeFEC() to pre-emptively
* determine frame completion. If set, we assume a FEC stream, and the
* following assumptions must hold:\n
* 1. The media packets in a frame have contiguous sequence numbers, i.e. the
* frame's FEC packets have sequence numbers either lower than the first
* media packet or higher than the last media packet.\n
* 2. All FEC packets have a sequence number base equal to the first media
* packet in the corresponding frame.\n
* The ssrc member is needed to ensure we can restore the SSRC field of
* recovered packets. In most situations this could be retrieved from other
* media packets, but in the case of an FEC packet protecting a single
* missing media packet, we have no other means of obtaining it.
// TODO(holmer): Refactor into a proper class.
class ReceivedPacket : public SortablePacket {
uint32_t ssrc; // SSRC of the current frame. Must be set for FEC
// packets, but not required for media packets.
bool isFec; // Set to true if this is an FEC packet and false
// otherwise.
scoped_refptr<Packet> pkt; // Pointer to the packet storage.
* The recovered list parameter of #DecodeFEC() will reference structs of
* this type.
// TODO(holmer): Refactor into a proper class.
class RecoveredPacket : public SortablePacket {
bool wasRecovered; // Will be true if this packet was recovered by
// the FEC. Otherwise it was a media packet passed in
// through the received packet list.
bool returned; // True when the packet already has been returned to the
// caller through the callback.
uint8_t length_recovery[2]; // Two bytes used for recovering the packet
// length with XOR operations.
scoped_refptr<Packet> pkt; // Pointer to the packet storage.
typedef std::list<Packet*> PacketList;
typedef std::list<ReceivedPacket*> ReceivedPacketList;
typedef std::list<RecoveredPacket*> RecoveredPacketList;
* \param[in] id Module ID
ForwardErrorCorrection(int32_t id);
virtual ~ForwardErrorCorrection();
* Generates a list of FEC packets from supplied media packets.
* \param[in] mediaPacketList List of media packets to protect, of type
* #Packet. All packets must belong to the
* same frame and the list must not be empty.
* \param[in] protectionFactor FEC protection overhead in the [0, 255]
* domain. To obtain 100% overhead, or an
* equal number of FEC packets as media
* packets, use 255.
* \param[in] numImportantPackets The number of "important" packets in the
* frame. These packets may receive greater
* protection than the remaining packets. The
* important packets must be located at the
* start of the media packet list. For codecs
* with data partitioning, the important
* packets may correspond to first partition
* packets.
* \param[in] useUnequalProtection Parameter to enable/disable unequal
* protection (UEP) across packets. Enabling
* UEP will allocate more protection to the
* numImportantPackets from the start of the
* mediaPacketList.
* \param[out] fecPacketList List of FEC packets, of type #Packet. Must
* be empty on entry. The memory available
* through the list will be valid until the
* next call to GenerateFEC().
* \return 0 on success, -1 on failure.
int32_t GenerateFEC(const PacketList& mediaPacketList,
uint8_t protectionFactor,
int numImportantPackets,
bool useUnequalProtection,
PacketList* fecPacketList);
* Decodes a list of media and FEC packets. It will parse the input received
* packet list, storing FEC packets internally and inserting media packets to
* the output recovered packet list. The recovered list will be sorted by
* ascending sequence number and have duplicates removed. The function
* should be called as new packets arrive, with the recovered list being
* progressively assembled with each call. The received packet list will be
* empty at output.\n
* The user will allocate packets submitted through the received list. The
* function will handle allocation of recovered packets and optionally
* deleting of all packet memory. The user may delete the recovered list
* packets, in which case they must remove deleted packets from the
* recovered list.\n
* \param[in] receivedPacketList List of new received packets, of type
* #ReceivedPacket, belonging to a single
* frame. At output the list will be empty,
* with packets either stored internally,
* or accessible through the recovered list.
* \param[out] recoveredPacketList List of recovered media packets, of type
* #RecoveredPacket, belonging to a single
* frame. The memory available through the
* list will be valid until the next call to
* DecodeFEC().
* \return 0 on success, -1 on failure.
int32_t DecodeFEC(ReceivedPacketList* receivedPacketList,
RecoveredPacketList* recoveredPacketList);
* Gets the size in bytes of the FEC/ULP headers, which must be accounted for
* as packet overhead.
* \return Packet overhead in bytes.
static uint16_t PacketOverhead();
// Reset internal states from last frame and clear the recoveredPacketList.
// Frees all memory allocated by this class.
void ResetState(RecoveredPacketList* recoveredPacketList);
typedef std::list<FecPacket*> FecPacketList;
void GenerateFecUlpHeaders(const PacketList& mediaPacketList,
uint8_t* packetMask,
uint32_t numFecPackets);
void GenerateFecBitStrings(const PacketList& mediaPacketList,
uint8_t* packetMask,
uint32_t numFecPackets);
// Insert received packets into FEC or recovered list.
void InsertPackets(ReceivedPacketList* receivedPacketList,
RecoveredPacketList* recoveredPacketList);
// Insert media packet into recovered packet list. We delete duplicates.
void InsertMediaPacket(ReceivedPacket* rxPacket,
RecoveredPacketList* recoveredPacketList);
// Assigns pointers to the recovered packet from all FEC packets which cover
// it.
// Note: This reduces the complexity when we want to try to recover a packet
// since we don't have to find the intersection between recovered packets and
// packets covered by the FEC packet.
void UpdateCoveringFECPackets(RecoveredPacket* packet);
// Insert packet into FEC list. We delete duplicates.
void InsertFECPacket(ReceivedPacket* rxPacket,
const RecoveredPacketList* recoveredPacketList);
// Assigns pointers to already recovered packets covered by this FEC packet.
static void AssignRecoveredPackets(
FecPacket* fec_packet,
const RecoveredPacketList* recovered_packets);
// Insert into recovered list in correct position.
void InsertRecoveredPacket(
RecoveredPacket* recPacketToInsert,
RecoveredPacketList* recoveredPacketList);
// Attempt to recover missing packets.
void AttemptRecover(RecoveredPacketList* recoveredPacketList);
// Initializes the packet recovery using the FEC packet.
static void InitRecovery(const FecPacket* fec_packet,
RecoveredPacket* recovered);
// Performs XOR between |src_packet| and |dst_packet| and stores the result
// in |dst_packet|.
static void XorPackets(const Packet* src_packet,
RecoveredPacket* dst_packet);
// Finish up the recovery of a packet.
static void FinishRecovery(RecoveredPacket* recovered);
// Recover a missing packet.
void RecoverPacket(const FecPacket* fecPacket,
RecoveredPacket* recPacketToInsert);
// Get the number of missing media packets which are covered by this
// FEC packet. An FEC packet can recover at most one packet, and if zero
// packets are missing the FEC packet can be discarded.
// This function returns 2 when two or more packets are missing.
static int NumCoveredPacketsMissing(const FecPacket* fec_packet);
static uint16_t LatestSequenceNumber(uint16_t first,
uint16_t second);
static void DiscardFECPacket(FecPacket* fec_packet);
static void DiscardOldPackets(RecoveredPacketList* recoveredPacketList);
int32_t _id;
std::vector<Packet> _generatedFecPackets;
FecPacketList _fecPacketList;
bool _fecPacketReceived;
} // namespace webrtc