src/third_party/webrtc/modules/rtp_rtcp/source/forward_error_correction.h

   1 /*
   2  *  Copyright (c) 2012 The WebRTC project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  11 #ifndef WEBRTC_MODULES_RTP_RTCP_SOURCE_FORWARD_ERROR_CORRECTION_H_
  12 #define WEBRTC_MODULES_RTP_RTCP_SOURCE_FORWARD_ERROR_CORRECTION_H_
  13
  14 #include <list>
  15 #include <vector>
  16
  17 #include "webrtc/modules/rtp_rtcp/interface/rtp_rtcp_defines.h"
  18 #include "webrtc/system_wrappers/interface/ref_count.h"
  19 #include "webrtc/system_wrappers/interface/scoped_refptr.h"
  20 #include "webrtc/typedefs.h"
  21
  22 namespace webrtc {
  23
  24 // Forward declaration.
  25 class FecPacket;
  26
  27 // Performs codec-independent forward error correction (FEC), based on RFC 5109.
  28 // Option exists to enable unequal protection (UEP) across packets.
  29 // This is not to be confused with protection within packets
  30 // (referred to as uneven level protection (ULP) in RFC 5109).
  31 class ForwardErrorCorrection {
  32  public:
  33   // Maximum number of media packets we can protect
  34   static const unsigned int kMaxMediaPackets = 48u;
  35
  36   // TODO(holmer): As a next step all these struct-like packet classes should be
  37   // refactored into proper classes, and their members should be made private.
  38   // This will require parts of the functionality in forward_error_correction.cc
  39   // and receiver_fec.cc to be refactored into the packet classes.
  40   class Packet {
  41    public:
  42     Packet() : length(0), data(), ref_count_(0) {}
  43     virtual ~Packet() {}
  44
  45     // Add a reference.
  46     virtual int32_t AddRef();
  47
  48     // Release a reference. Will delete the object if the reference count
  49     // reaches zero.
  50     virtual int32_t Release();
  51
  52     uint16_t length;               // Length of packet in bytes.
  53     uint8_t data[IP_PACKET_SIZE];  // Packet data.
  54
  55    private:
  56     int32_t ref_count_;  // Counts the number of references to a packet.
  57   };
  58
  59   // TODO(holmer): Refactor into a proper class.
  60   class SortablePacket {
  61    public:
  62     // True if first is <= than second.
  63     static bool LessThan(const SortablePacket* first,
  64                          const SortablePacket* second);
  65
  66     uint16_t seq_num;
  67   };
  68
  69   // The received list parameter of #DecodeFEC() must reference structs of this
  70   // type. The last_media_pkt_in_frame is not required to be used for correct
  71   // recovery, but will reduce delay by allowing #DecodeFEC() to pre-emptively
  72   // determine frame completion. If set, we assume a FEC stream, and the
  73   // following assumptions must hold:\n
  74   //
  75   // 1. The media packets in a frame have contiguous sequence numbers, i.e. the
  76   //    frame's FEC packets have sequence numbers either lower than the first
  77   //    media packet or higher than the last media packet.\n
  78   // 2. All FEC packets have a sequence number base equal to the first media
  79   //    packet in the corresponding frame.\n
  80   //
  81   // The ssrc member is needed to ensure we can restore the SSRC field of
  82   // recovered packets. In most situations this could be retrieved from other
  83   // media packets, but in the case of an FEC packet protecting a single
  84   // missing media packet, we have no other means of obtaining it.
  85   // TODO(holmer): Refactor into a proper class.
  86   class ReceivedPacket : public SortablePacket {
  87    public:
  88     ReceivedPacket();
  89     ~ReceivedPacket();
  90
  91     uint32_t ssrc;  // SSRC of the current frame. Must be set for FEC
  92                     // packets, but not required for media packets.
  93     bool is_fec;    // Set to true if this is an FEC packet and false
  94                     // otherwise.
  95     scoped_refptr<Packet> pkt;  // Pointer to the packet storage.
  96   };
  97
  98   // The recovered list parameter of #DecodeFEC() will reference structs of
  99   // this type.
 100   // TODO(holmer): Refactor into a proper class.
 101   class RecoveredPacket : public SortablePacket {
 102    public:
 103     RecoveredPacket();
 104     ~RecoveredPacket();
 105
 106     bool was_recovered;  // Will be true if this packet was recovered by
 107                          // the FEC. Otherwise it was a media packet passed in
 108                          // through the received packet list.
 109     bool returned;  // True when the packet already has been returned to the
 110                     // caller through the callback.
 111     uint8_t length_recovery[2];  // Two bytes used for recovering the packet
 112                                  // length with XOR operations.
 113     scoped_refptr<Packet> pkt;   // Pointer to the packet storage.
 114   };
 115
 116   typedef std::list<Packet*> PacketList;
 117   typedef std::list<ReceivedPacket*> ReceivedPacketList;
 118   typedef std::list<RecoveredPacket*> RecoveredPacketList;
 119
 120   ForwardErrorCorrection();
 121
 122   virtual ~ForwardErrorCorrection();
 123
 124   /**
 125    * Generates a list of FEC packets from supplied media packets.
 126    *
 127    * \param[in]  mediaPacketList     List of media packets to protect, of type
 128    *                                 #Packet. All packets must belong to the
 129    *                                 same frame and the list must not be empty.
 130    * \param[in]  protectionFactor    FEC protection overhead in the [0, 255]
 131    *                                 domain. To obtain 100% overhead, or an
 132    *                                 equal number of FEC packets as media
 133    *                                 packets, use 255.
 134    * \param[in] numImportantPackets  The number of "important" packets in the
 135    *                                 frame. These packets may receive greater
 136    *                                 protection than the remaining packets. The
 137    *                                 important packets must be located at the
 138    *                                 start of the media packet list. For codecs
 139    *                                 with data partitioning, the important
 140    *                                 packets may correspond to first partition
 141    *                                 packets.
 142    * \param[in] useUnequalProtection Parameter to enable/disable unequal
 143    *                                 protection  (UEP) across packets. Enabling
 144    *                                 UEP will allocate more protection to the
 145    *                                 numImportantPackets from the start of the
 146    *                                 mediaPacketList.
 147    * \param[in]  fec_mask_type       The type of packet mask used in the FEC.
 148    *                                 Random or bursty type may be selected. The
 149    *                                 bursty type is only defined up to 12 media
 150    *                                 packets. If the number of media packets is
 151    *                                 above 12, the packets masks from the
 152    *                                 random table will be selected.
 153    * \param[out] fecPacketList       List of FEC packets, of type #Packet. Must
 154    *                                 be empty on entry. The memory available
 155    *                                 through the list will be valid until the
 156    *                                 next call to GenerateFEC().
 157    *
 158    * \return 0 on success, -1 on failure.
 159    */
 160   int32_t GenerateFEC(const PacketList& media_packet_list,
 161                       uint8_t protection_factor, int num_important_packets,
 162                       bool use_unequal_protection, FecMaskType fec_mask_type,
 163                       PacketList* fec_packet_list);
 164
 165   /**
 166    *  Decodes a list of media and FEC packets. It will parse the input received
 167    *  packet list, storing FEC packets internally and inserting media packets to
 168    *  the output recovered packet list. The recovered list will be sorted by
 169    *  ascending sequence number and have duplicates removed. The function
 170    *  should be called as new packets arrive, with the recovered list being
 171    *  progressively assembled with each call. The received packet list will be
 172    *  empty at output.\n
 173    *
 174    *  The user will allocate packets submitted through the received list. The
 175    *  function will handle allocation of recovered packets and optionally
 176    *  deleting of all packet memory. The user may delete the recovered list
 177    *  packets, in which case they must remove deleted packets from the
 178    *  recovered list.\n
 179    *
 180    * \param[in]  receivedPacketList  List of new received packets, of type
 181    *                                 #ReceivedPacket, belonging to a single
 182    *                                 frame. At output the list will be empty,
 183    *                                 with packets  either stored internally,
 184    *                                 or accessible through the recovered list.
 185    * \param[out] recoveredPacketList List of recovered media packets, of type
 186    *                                 #RecoveredPacket, belonging to a single
 187    *                                 frame. The memory available through the
 188    *                                 list will be valid until the next call to
 189    *                                 DecodeFEC().
 190    *
 191    * \return 0 on success, -1 on failure.
 192    */
 193   int32_t DecodeFEC(ReceivedPacketList* received_packet_list,
 194                     RecoveredPacketList* recovered_packet_list);
 195
 196   // Get the number of FEC packets, given the number of media packets and the
 197   // protection factor.
 198   int GetNumberOfFecPackets(int num_media_packets, int protection_factor);
 199
 200   // Gets the size in bytes of the FEC/ULP headers, which must be accounted for
 201   // as packet overhead.
 202   // \return Packet overhead in bytes.
 203   static uint16_t PacketOverhead();
 204
 205   // Reset internal states from last frame and clear the recovered_packet_list.
 206   // Frees all memory allocated by this class.
 207   void ResetState(RecoveredPacketList* recovered_packet_list);
 208
 209  private:
 210   typedef std::list<FecPacket*> FecPacketList;
 211
 212   void GenerateFecUlpHeaders(const PacketList& media_packet_list,
 213                              uint8_t* packet_mask, bool l_bit,
 214                              int num_fec_packets);
 215
 216   // Analyzes |media_packets| for holes in the sequence and inserts zero columns
 217   // into the |packet_mask| where those holes are found. Zero columns means that
 218   // those packets will have no protection.
 219   // Returns the number of bits used for one row of the new packet mask.
 220   // Requires that |packet_mask| has at least 6 * |num_fec_packets| bytes
 221   // allocated.
 222   int InsertZerosInBitMasks(const PacketList& media_packets,
 223                             uint8_t* packet_mask, int num_mask_bytes,
 224                             int num_fec_packets);
 225
 226   // Inserts |num_zeros| zero columns into |new_mask| at position
 227   // |new_bit_index|. If the current byte of |new_mask| can't fit all zeros, the
 228   // byte will be filled with zeros from |new_bit_index|, but the next byte will
 229   // be untouched.
 230   static void InsertZeroColumns(int num_zeros, uint8_t* new_mask,
 231                                 int new_mask_bytes, int num_fec_packets,
 232                                 int new_bit_index);
 233
 234   // Copies the left most bit column from the byte pointed to by
 235   // |old_bit_index| in |old_mask| to the right most column of the byte pointed
 236   // to by |new_bit_index| in |new_mask|. |old_mask_bytes| and |new_mask_bytes|
 237   // represent the number of bytes used per row for each mask. |num_fec_packets|
 238   // represent the number of rows of the masks.
 239   // The copied bit is shifted out from |old_mask| and is shifted one step to
 240   // the left in |new_mask|. |new_mask| will contain "xxxx xxn0" after this
 241   // operation, where x are previously inserted bits and n is the new bit.
 242   static void CopyColumn(uint8_t* new_mask, int new_mask_bytes,
 243                          uint8_t* old_mask, int old_mask_bytes,
 244                          int num_fec_packets, int new_bit_index,
 245                          int old_bit_index);
 246
 247   void GenerateFecBitStrings(const PacketList& media_packet_list,
 248                              uint8_t* packet_mask, int num_fec_packets,
 249                              bool l_bit);
 250
 251   // Insert received packets into FEC or recovered list.
 252   void InsertPackets(ReceivedPacketList* received_packet_list,
 253                      RecoveredPacketList* recovered_packet_list);
 254
 255   // Insert media packet into recovered packet list. We delete duplicates.
 256   void InsertMediaPacket(ReceivedPacket* rx_packet,
 257                          RecoveredPacketList* recovered_packet_list);
 258
 259   // Assigns pointers to the recovered packet from all FEC packets which cover
 260   // it.
 261   // Note: This reduces the complexity when we want to try to recover a packet
 262   // since we don't have to find the intersection between recovered packets and
 263   // packets covered by the FEC packet.
 264   void UpdateCoveringFECPackets(RecoveredPacket* packet);
 265
 266   // Insert packet into FEC list. We delete duplicates.
 267   void InsertFECPacket(ReceivedPacket* rx_packet,
 268                        const RecoveredPacketList* recovered_packet_list);
 269
 270   // Assigns pointers to already recovered packets covered by this FEC packet.
 271   static void AssignRecoveredPackets(
 272       FecPacket* fec_packet, const RecoveredPacketList* recovered_packets);
 273
 274   // Insert into recovered list in correct position.
 275   void InsertRecoveredPacket(RecoveredPacket* rec_packet_to_insert,
 276                              RecoveredPacketList* recovered_packet_list);
 277
 278   // Attempt to recover missing packets.
 279   void AttemptRecover(RecoveredPacketList* recovered_packet_list);
 280
 281   // Initializes the packet recovery using the FEC packet.
 282   static void InitRecovery(const FecPacket* fec_packet,
 283                            RecoveredPacket* recovered);
 284
 285   // Performs XOR between |src_packet| and |dst_packet| and stores the result
 286   // in |dst_packet|.
 287   static void XorPackets(const Packet* src_packet, RecoveredPacket* dst_packet);
 288
 289   // Finish up the recovery of a packet.
 290   static void FinishRecovery(RecoveredPacket* recovered);
 291
 292   // Recover a missing packet.
 293   void RecoverPacket(const FecPacket* fec_packet,
 294                      RecoveredPacket* rec_packet_to_insert);
 295
 296   // Get the number of missing media packets which are covered by this
 297   // FEC packet. An FEC packet can recover at most one packet, and if zero
 298   // packets are missing the FEC packet can be discarded.
 299   // This function returns 2 when two or more packets are missing.
 300   static int NumCoveredPacketsMissing(const FecPacket* fec_packet);
 301
 302   static void DiscardFECPacket(FecPacket* fec_packet);
 303   static void DiscardOldPackets(RecoveredPacketList* recovered_packet_list);
 304   static uint16_t ParseSequenceNumber(uint8_t* packet);
 305
 306   std::vector<Packet> generated_fec_packets_;
 307   FecPacketList fec_packet_list_;
 308   bool fec_packet_received_;
 309 };
 310 }  // namespace webrtc
 311 #endif  // WEBRTC_MODULES_RTP_RTCP_SOURCE_FORWARD_ERROR_CORRECTION_H_