Note: We no longer publish the latest version of our code here. We primarily use a kumc-bmi github organization. The heron ETL repository, in particular, is not public. Peers in the informatics community should see MultiSiteDev for details on requesting access.

source: webrtc/webrtc/modules/rtp_rtcp/source/forward_error_correction.h @ 0:4bda6873e34c

pub_scrub_3792 tip
Last change on this file since 0:4bda6873e34c was 0:4bda6873e34c, checked in by Michael Prittie <mprittie@…>, 6 years ago

Scrubbed password for publication.

File size: 14.5 KB
Line 
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
22namespace webrtc {
23
24// Forward declaration.
25class 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).
31class 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  // \param[in] id Module ID
121  ForwardErrorCorrection(int32_t id);
122
123  virtual ~ForwardErrorCorrection();
124
125  /**
126   * Generates a list of FEC packets from supplied media packets.
127   *
128   * \param[in]  mediaPacketList     List of media packets to protect, of type
129   *                                 #Packet. All packets must belong to the
130   *                                 same frame and the list must not be empty.
131   * \param[in]  protectionFactor    FEC protection overhead in the [0, 255]
132   *                                 domain. To obtain 100% overhead, or an
133   *                                 equal number of FEC packets as media
134   *                                 packets, use 255.
135   * \param[in] numImportantPackets  The number of "important" packets in the
136   *                                 frame. These packets may receive greater
137   *                                 protection than the remaining packets. The
138   *                                 important packets must be located at the
139   *                                 start of the media packet list. For codecs
140   *                                 with data partitioning, the important
141   *                                 packets may correspond to first partition
142   *                                 packets.
143   * \param[in] useUnequalProtection Parameter to enable/disable unequal
144   *                                 protection  (UEP) across packets. Enabling
145   *                                 UEP will allocate more protection to the
146   *                                 numImportantPackets from the start of the
147   *                                 mediaPacketList.
148   * \param[in]  fec_mask_type       The type of packet mask used in the FEC.
149   *                                 Random or bursty type may be selected. The
150   *                                 bursty type is only defined up to 12 media
151   *                                 packets. If the number of media packets is
152   *                                 above 12, the packets masks from the
153   *                                 random table will be selected.
154   * \param[out] fecPacketList       List of FEC packets, of type #Packet. Must
155   *                                 be empty on entry. The memory available
156   *                                 through the list will be valid until the
157   *                                 next call to GenerateFEC().
158   *
159   * \return 0 on success, -1 on failure.
160   */
161  int32_t GenerateFEC(const PacketList& media_packet_list,
162                      uint8_t protection_factor, int num_important_packets,
163                      bool use_unequal_protection, FecMaskType fec_mask_type,
164                      PacketList* fec_packet_list);
165
166  /**
167   *  Decodes a list of media and FEC packets. It will parse the input received
168   *  packet list, storing FEC packets internally and inserting media packets to
169   *  the output recovered packet list. The recovered list will be sorted by
170   *  ascending sequence number and have duplicates removed. The function
171   *  should be called as new packets arrive, with the recovered list being
172   *  progressively assembled with each call. The received packet list will be
173   *  empty at output.\n
174   *
175   *  The user will allocate packets submitted through the received list. The
176   *  function will handle allocation of recovered packets and optionally
177   *  deleting of all packet memory. The user may delete the recovered list
178   *  packets, in which case they must remove deleted packets from the
179   *  recovered list.\n
180   *
181   * \param[in]  receivedPacketList  List of new received packets, of type
182   *                                 #ReceivedPacket, belonging to a single
183   *                                 frame. At output the list will be empty,
184   *                                 with packets  either stored internally,
185   *                                 or accessible through the recovered list.
186   * \param[out] recoveredPacketList List of recovered media packets, of type
187   *                                 #RecoveredPacket, belonging to a single
188   *                                 frame. The memory available through the
189   *                                 list will be valid until the next call to
190   *                                 DecodeFEC().
191   *
192   * \return 0 on success, -1 on failure.
193   */
194  int32_t DecodeFEC(ReceivedPacketList* received_packet_list,
195                    RecoveredPacketList* recovered_packet_list);
196
197  // Get the number of FEC packets, given the number of media packets and the
198  // protection factor.
199  int GetNumberOfFecPackets(int num_media_packets, int protection_factor);
200
201  // Gets the size in bytes of the FEC/ULP headers, which must be accounted for
202  // as packet overhead.
203  // \return Packet overhead in bytes.
204  static uint16_t PacketOverhead();
205
206  // Reset internal states from last frame and clear the recovered_packet_list.
207  // Frees all memory allocated by this class.
208  void ResetState(RecoveredPacketList* recovered_packet_list);
209
210 private:
211  typedef std::list<FecPacket*> FecPacketList;
212
213  void GenerateFecUlpHeaders(const PacketList& media_packet_list,
214                             uint8_t* packet_mask, bool l_bit,
215                             int num_fec_packets);
216
217  // Analyzes |media_packets| for holes in the sequence and inserts zero columns
218  // into the |packet_mask| where those holes are found. Zero columns means that
219  // those packets will have no protection.
220  // Returns the number of bits used for one row of the new packet mask.
221  // Requires that |packet_mask| has at least 6 * |num_fec_packets| bytes
222  // allocated.
223  int InsertZerosInBitMasks(const PacketList& media_packets,
224                            uint8_t* packet_mask, int num_mask_bytes,
225                            int num_fec_packets);
226
227  // Inserts |num_zeros| zero columns into |new_mask| at position
228  // |new_bit_index|. If the current byte of |new_mask| can't fit all zeros, the
229  // byte will be filled with zeros from |new_bit_index|, but the next byte will
230  // be untouched.
231  static void InsertZeroColumns(int num_zeros, uint8_t* new_mask,
232                                int new_mask_bytes, int num_fec_packets,
233                                int new_bit_index);
234
235  // Copies the left most bit column from the byte pointed to by
236  // |old_bit_index| in |old_mask| to the right most column of the byte pointed
237  // to by |new_bit_index| in |new_mask|. |old_mask_bytes| and |new_mask_bytes|
238  // represent the number of bytes used per row for each mask. |num_fec_packets|
239  // represent the number of rows of the masks.
240  // The copied bit is shifted out from |old_mask| and is shifted one step to
241  // the left in |new_mask|. |new_mask| will contain "xxxx xxn0" after this
242  // operation, where x are previously inserted bits and n is the new bit.
243  static void CopyColumn(uint8_t* new_mask, int new_mask_bytes,
244                         uint8_t* old_mask, int old_mask_bytes,
245                         int num_fec_packets, int new_bit_index,
246                         int old_bit_index);
247
248  void GenerateFecBitStrings(const PacketList& media_packet_list,
249                             uint8_t* packet_mask, int num_fec_packets,
250                             bool l_bit);
251
252  // Insert received packets into FEC or recovered list.
253  void InsertPackets(ReceivedPacketList* received_packet_list,
254                     RecoveredPacketList* recovered_packet_list);
255
256  // Insert media packet into recovered packet list. We delete duplicates.
257  void InsertMediaPacket(ReceivedPacket* rx_packet,
258                         RecoveredPacketList* recovered_packet_list);
259
260  // Assigns pointers to the recovered packet from all FEC packets which cover
261  // it.
262  // Note: This reduces the complexity when we want to try to recover a packet
263  // since we don't have to find the intersection between recovered packets and
264  // packets covered by the FEC packet.
265  void UpdateCoveringFECPackets(RecoveredPacket* packet);
266
267  // Insert packet into FEC list. We delete duplicates.
268  void InsertFECPacket(ReceivedPacket* rx_packet,
269                       const RecoveredPacketList* recovered_packet_list);
270
271  // Assigns pointers to already recovered packets covered by this FEC packet.
272  static void AssignRecoveredPackets(
273      FecPacket* fec_packet, const RecoveredPacketList* recovered_packets);
274
275  // Insert into recovered list in correct position.
276  void InsertRecoveredPacket(RecoveredPacket* rec_packet_to_insert,
277                             RecoveredPacketList* recovered_packet_list);
278
279  // Attempt to recover missing packets.
280  void AttemptRecover(RecoveredPacketList* recovered_packet_list);
281
282  // Initializes the packet recovery using the FEC packet.
283  static void InitRecovery(const FecPacket* fec_packet,
284                           RecoveredPacket* recovered);
285
286  // Performs XOR between |src_packet| and |dst_packet| and stores the result
287  // in |dst_packet|.
288  static void XorPackets(const Packet* src_packet, RecoveredPacket* dst_packet);
289
290  // Finish up the recovery of a packet.
291  static void FinishRecovery(RecoveredPacket* recovered);
292
293  // Recover a missing packet.
294  void RecoverPacket(const FecPacket* fec_packet,
295                     RecoveredPacket* rec_packet_to_insert);
296
297  // Get the number of missing media packets which are covered by this
298  // FEC packet. An FEC packet can recover at most one packet, and if zero
299  // packets are missing the FEC packet can be discarded.
300  // This function returns 2 when two or more packets are missing.
301  static int NumCoveredPacketsMissing(const FecPacket* fec_packet);
302
303  static void DiscardFECPacket(FecPacket* fec_packet);
304  static void DiscardOldPackets(RecoveredPacketList* recovered_packet_list);
305  static uint16_t ParseSequenceNumber(uint8_t* packet);
306
307  int32_t id_;
308  std::vector<Packet> generated_fec_packets_;
309  FecPacketList fec_packet_list_;
310  bool fec_packet_received_;
311};
312}  // namespace webrtc
313#endif  // WEBRTC_MODULES_RTP_RTCP_SOURCE_FORWARD_ERROR_CORRECTION_H_
Note: See TracBrowser for help on using the repository browser.