• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/base/scoped_ref_ptr.h"
18 #include "webrtc/modules/rtp_rtcp/include/rtp_rtcp_defines.h"
19 #include "webrtc/system_wrappers/include/ref_count.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:
Packet()42     Packet() : length(0), data(), ref_count_(0) {}
~Packet()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     size_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     rtc::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     rtc::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 size_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 bool 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 bool FinishRecovery(RecoveredPacket* recovered);
291 
292   // Recover a missing packet.
293   bool 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_
312