Line data Source code
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 <stdint.h>
15 :
16 : #include <list>
17 : #include <memory>
18 : #include <vector>
19 :
20 : #include "webrtc/base/basictypes.h"
21 : #include "webrtc/base/constructormagic.h"
22 : #include "webrtc/base/refcount.h"
23 : #include "webrtc/base/scoped_ref_ptr.h"
24 : #include "webrtc/modules/rtp_rtcp/include/rtp_rtcp_defines.h"
25 : #include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h"
26 :
27 : namespace webrtc {
28 :
29 : class FecHeaderReader;
30 : class FecHeaderWriter;
31 :
32 : // Performs codec-independent forward error correction (FEC), based on RFC 5109.
33 : // Option exists to enable unequal protection (UEP) across packets.
34 : // This is not to be confused with protection within packets
35 : // (referred to as uneven level protection (ULP) in RFC 5109).
36 0 : class ForwardErrorCorrection {
37 : public:
38 : // TODO(holmer): As a next step all these struct-like packet classes should be
39 : // refactored into proper classes, and their members should be made private.
40 : // This will require parts of the functionality in forward_error_correction.cc
41 : // and receiver_fec.cc to be refactored into the packet classes.
42 0 : class Packet {
43 : public:
44 : Packet();
45 : virtual ~Packet();
46 :
47 : // Add a reference.
48 : virtual int32_t AddRef();
49 :
50 : // Release a reference. Will delete the object if the reference count
51 : // reaches zero.
52 : virtual int32_t Release();
53 :
54 : size_t length; // Length of packet in bytes.
55 : uint8_t data[IP_PACKET_SIZE]; // Packet data.
56 :
57 : private:
58 : int32_t ref_count_; // Counts the number of references to a packet.
59 : };
60 :
61 : // TODO(holmer): Refactor into a proper class.
62 0 : class SortablePacket {
63 : public:
64 : // Functor which returns true if the sequence number of |first|
65 : // is < the sequence number of |second|.
66 : struct LessThan {
67 : template <typename S, typename T>
68 : bool operator() (const S& first, const T& second);
69 : };
70 :
71 : uint16_t seq_num;
72 : };
73 :
74 : // The received list parameter of DecodeFec() references structs of this type.
75 : //
76 : // The ssrc member is needed to ensure that we can restore the SSRC field of
77 : // recovered packets. In most situations this could be retrieved from other
78 : // media packets, but in the case of an FEC packet protecting a single
79 : // missing media packet, we have no other means of obtaining it.
80 : // TODO(holmer): Refactor into a proper class.
81 0 : class ReceivedPacket : public SortablePacket {
82 : public:
83 : ReceivedPacket();
84 : ~ReceivedPacket();
85 :
86 : uint32_t ssrc; // SSRC of the current frame. Must be set for FEC
87 : // packets, but not required for media packets.
88 : bool is_fec; // Set to true if this is an FEC packet and false
89 : // otherwise.
90 : rtc::scoped_refptr<Packet> pkt; // Pointer to the packet storage.
91 : };
92 :
93 : // The recovered list parameter of DecodeFec() references structs of
94 : // this type.
95 : // TODO(holmer): Refactor into a proper class.
96 0 : class RecoveredPacket : public SortablePacket {
97 : public:
98 : RecoveredPacket();
99 : ~RecoveredPacket();
100 :
101 : bool was_recovered; // Will be true if this packet was recovered by
102 : // the FEC. Otherwise it was a media packet passed in
103 : // through the received packet list.
104 : bool returned; // True when the packet already has been returned to the
105 : // caller through the callback.
106 : rtc::scoped_refptr<Packet> pkt; // Pointer to the packet storage.
107 : };
108 :
109 : // Used to link media packets to their protecting FEC packets.
110 : //
111 : // TODO(holmer): Refactor into a proper class.
112 0 : class ProtectedPacket : public ForwardErrorCorrection::SortablePacket {
113 : public:
114 : ProtectedPacket();
115 : ~ProtectedPacket();
116 :
117 : rtc::scoped_refptr<ForwardErrorCorrection::Packet> pkt;
118 : };
119 :
120 : using ProtectedPacketList = std::list<std::unique_ptr<ProtectedPacket>>;
121 :
122 : // Used for internal storage of received FEC packets in a list.
123 : //
124 : // TODO(holmer): Refactor into a proper class.
125 0 : class ReceivedFecPacket : public ForwardErrorCorrection::SortablePacket {
126 : public:
127 : ReceivedFecPacket();
128 : ~ReceivedFecPacket();
129 :
130 : // List of media packets that this FEC packet protects.
131 : ProtectedPacketList protected_packets;
132 : // RTP header fields.
133 : uint32_t ssrc;
134 : // FEC header fields.
135 : size_t fec_header_size;
136 : uint32_t protected_ssrc;
137 : uint16_t seq_num_base;
138 : size_t packet_mask_offset; // Relative start of FEC header.
139 : size_t packet_mask_size;
140 : size_t protection_length;
141 : // Raw data.
142 : rtc::scoped_refptr<ForwardErrorCorrection::Packet> pkt;
143 : };
144 :
145 : using PacketList = std::list<std::unique_ptr<Packet>>;
146 : using ReceivedPacketList = std::list<std::unique_ptr<ReceivedPacket>>;
147 : using RecoveredPacketList = std::list<std::unique_ptr<RecoveredPacket>>;
148 : using ReceivedFecPacketList = std::list<std::unique_ptr<ReceivedFecPacket>>;
149 :
150 : ~ForwardErrorCorrection();
151 :
152 : // Creates a ForwardErrorCorrection tailored for a specific FEC scheme.
153 : static std::unique_ptr<ForwardErrorCorrection> CreateUlpfec();
154 : static std::unique_ptr<ForwardErrorCorrection> CreateFlexfec();
155 :
156 : // Generates a list of FEC packets from supplied media packets.
157 : //
158 : // Input: media_packets List of media packets to protect, of type
159 : // Packet. All packets must belong to the
160 : // same frame and the list must not be empty.
161 : // Input: protection_factor FEC protection overhead in the [0, 255]
162 : // domain. To obtain 100% overhead, or an
163 : // equal number of FEC packets as
164 : // media packets, use 255.
165 : // Input: num_important_packets The number of "important" packets in the
166 : // frame. These packets may receive greater
167 : // protection than the remaining packets.
168 : // The important packets must be located at the
169 : // start of the media packet list. For codecs
170 : // with data partitioning, the important
171 : // packets may correspond to first partition
172 : // packets.
173 : // Input: use_unequal_protection Parameter to enable/disable unequal
174 : // protection (UEP) across packets. Enabling
175 : // UEP will allocate more protection to the
176 : // num_important_packets from the start of the
177 : // media_packets.
178 : // Input: fec_mask_type The type of packet mask used in the FEC.
179 : // Random or bursty type may be selected. The
180 : // bursty type is only defined up to 12 media
181 : // packets. If the number of media packets is
182 : // above 12, the packet masks from the random
183 : // table will be selected.
184 : // Output: fec_packets List of pointers to generated FEC packets,
185 : // of type Packet. Must be empty on entry.
186 : // The memory available through the list will
187 : // be valid until the next call to
188 : // EncodeFec().
189 : //
190 : // Returns 0 on success, -1 on failure.
191 : //
192 : int EncodeFec(const PacketList& media_packets,
193 : uint8_t protection_factor,
194 : int num_important_packets,
195 : bool use_unequal_protection,
196 : FecMaskType fec_mask_type,
197 : std::list<Packet*>* fec_packets);
198 :
199 : // Decodes a list of received media and FEC packets. It will parse the
200 : // |received_packets|, storing FEC packets internally, and move
201 : // media packets to |recovered_packets|. The recovered list will be
202 : // sorted by ascending sequence number and have duplicates removed.
203 : // The function should be called as new packets arrive, and
204 : // |recovered_packets| will be progressively assembled with each call.
205 : // When the function returns, |received_packets| will be empty.
206 : //
207 : // The caller will allocate packets submitted through |received_packets|.
208 : // The function will handle allocation of recovered packets.
209 : //
210 : // Input: received_packets List of new received packets, of type
211 : // ReceivedPacket, belonging to a single
212 : // frame. At output the list will be empty,
213 : // with packets either stored internally,
214 : // or accessible through the recovered list.
215 : // Output: recovered_packets List of recovered media packets, of type
216 : // RecoveredPacket, belonging to a single
217 : // frame. The memory available through the
218 : // list will be valid until the next call to
219 : // DecodeFec().
220 : //
221 : // Returns 0 on success, -1 on failure.
222 : //
223 : int DecodeFec(ReceivedPacketList* received_packets,
224 : RecoveredPacketList* recovered_packets);
225 :
226 : // Get the number of generated FEC packets, given the number of media packets
227 : // and the protection factor.
228 : static int NumFecPackets(int num_media_packets, int protection_factor);
229 :
230 : // Gets the maximum size of the FEC headers in bytes, which must be
231 : // accounted for as packet overhead.
232 : size_t MaxPacketOverhead() const;
233 :
234 : // Reset internal states from last frame and clear |recovered_packets|.
235 : // Frees all memory allocated by this class.
236 : void ResetState(RecoveredPacketList* recovered_packets);
237 :
238 : // TODO(brandtr): Remove these functions when the Packet classes
239 : // have been refactored.
240 : static uint16_t ParseSequenceNumber(uint8_t* packet);
241 : static uint32_t ParseSsrc(uint8_t* packet);
242 :
243 : protected:
244 : ForwardErrorCorrection(std::unique_ptr<FecHeaderReader> fec_header_reader,
245 : std::unique_ptr<FecHeaderWriter> fec_header_writer);
246 :
247 : private:
248 : // Analyzes |media_packets| for holes in the sequence and inserts zero columns
249 : // into the |packet_mask| where those holes are found. Zero columns means that
250 : // those packets will have no protection.
251 : // Returns the number of bits used for one row of the new packet mask.
252 : // Requires that |packet_mask| has at least 6 * |num_fec_packets| bytes
253 : // allocated.
254 : int InsertZerosInPacketMasks(const PacketList& media_packets,
255 : size_t num_fec_packets);
256 :
257 : // Writes FEC payloads and some recovery fields in the FEC headers.
258 : void GenerateFecPayloads(const PacketList& media_packets,
259 : size_t num_fec_packets);
260 :
261 : // Writes the FEC header fields that are not written by GenerateFecPayloads.
262 : // This includes writing the packet masks.
263 : void FinalizeFecHeaders(size_t num_fec_packets,
264 : uint32_t media_ssrc,
265 : uint16_t seq_num_base);
266 :
267 : // Inserts the |received_packets| into the internal received FEC packet list
268 : // or into |recovered_packets|.
269 : void InsertPackets(ReceivedPacketList* received_packets,
270 : RecoveredPacketList* recovered_packets);
271 :
272 : // Inserts the |received_packet| into |recovered_packets|. Deletes duplicates.
273 : void InsertMediaPacket(RecoveredPacketList* recovered_packets,
274 : ReceivedPacket* received_packet);
275 :
276 : // Assigns pointers to the recovered packet from all FEC packets which cover
277 : // it.
278 : // Note: This reduces the complexity when we want to try to recover a packet
279 : // since we don't have to find the intersection between recovered packets and
280 : // packets covered by the FEC packet.
281 : void UpdateCoveringFecPackets(const RecoveredPacket& packet);
282 :
283 : // Insert |received_packet| into internal FEC list. Deletes duplicates.
284 : void InsertFecPacket(const RecoveredPacketList& recovered_packets,
285 : ReceivedPacket* received_packet);
286 :
287 : // Assigns pointers to already recovered packets covered by |fec_packet|.
288 : static void AssignRecoveredPackets(
289 : const RecoveredPacketList& recovered_packets,
290 : ReceivedFecPacket* fec_packet);
291 :
292 : // Attempt to recover missing packets, using the internally stored
293 : // received FEC packets.
294 : void AttemptRecovery(RecoveredPacketList* recovered_packets);
295 :
296 : // Initializes headers and payload before the XOR operation
297 : // that recovers a packet.
298 : static bool StartPacketRecovery(const ReceivedFecPacket& fec_packet,
299 : RecoveredPacket* recovered_packet);
300 :
301 : // Performs XOR between the first 8 bytes of |src| and |dst| and stores
302 : // the result in |dst|. The 3rd and 4th bytes are used for storing
303 : // the length recovery field.
304 : static void XorHeaders(const Packet& src, Packet* dst);
305 :
306 : // Performs XOR between the payloads of |src| and |dst| and stores the result
307 : // in |dst|. The parameter |dst_offset| determines at what byte the
308 : // XOR operation starts in |dst|. In total, |payload_length| bytes are XORed.
309 : static void XorPayloads(const Packet& src,
310 : size_t payload_length,
311 : size_t dst_offset,
312 : Packet* dst);
313 :
314 : // Finalizes recovery of packet by setting RTP header fields.
315 : // This is not specific to the FEC scheme used.
316 : static bool FinishPacketRecovery(const ReceivedFecPacket& fec_packet,
317 : RecoveredPacket* recovered_packet);
318 :
319 : // Recover a missing packet.
320 : static bool RecoverPacket(const ReceivedFecPacket& fec_packet,
321 : RecoveredPacket* recovered_packet);
322 :
323 : // Get the number of missing media packets which are covered by |fec_packet|.
324 : // An FEC packet can recover at most one packet, and if zero packets are
325 : // missing the FEC packet can be discarded. This function returns 2 when two
326 : // or more packets are missing.
327 : static int NumCoveredPacketsMissing(const ReceivedFecPacket& fec_packet);
328 :
329 : // Discards old packets in |recovered_packets|, which are no longer relevant
330 : // for recovering lost packets.
331 : void DiscardOldRecoveredPackets(RecoveredPacketList* recovered_packets);
332 :
333 : std::unique_ptr<FecHeaderReader> fec_header_reader_;
334 : std::unique_ptr<FecHeaderWriter> fec_header_writer_;
335 :
336 : std::vector<Packet> generated_fec_packets_;
337 : ReceivedFecPacketList received_fec_packets_;
338 :
339 : // Arrays used to avoid dynamically allocating memory when generating
340 : // the packet masks.
341 : // (There are never more than |kUlpfecMaxMediaPackets| FEC packets generated.)
342 : uint8_t packet_masks_[kUlpfecMaxMediaPackets * kUlpfecMaxPacketMaskSize];
343 : uint8_t tmp_packet_masks_[kUlpfecMaxMediaPackets * kUlpfecMaxPacketMaskSize];
344 : size_t packet_mask_size_;
345 : };
346 :
347 : // Classes derived from FecHeader{Reader,Writer} encapsulate the
348 : // specifics of reading and writing FEC header for, e.g., ULPFEC
349 : // and FlexFEC.
350 0 : class FecHeaderReader {
351 : public:
352 : virtual ~FecHeaderReader();
353 :
354 : // The maximum number of media packets that can be covered by one FEC packet.
355 : size_t MaxMediaPackets() const;
356 :
357 : // The maximum number of FEC packets that is supported, per call
358 : // to ForwardErrorCorrection::EncodeFec().
359 : size_t MaxFecPackets() const;
360 :
361 : // Parses FEC header and stores information in ReceivedFecPacket members.
362 : virtual bool ReadFecHeader(
363 : ForwardErrorCorrection::ReceivedFecPacket* fec_packet) const = 0;
364 :
365 : protected:
366 : FecHeaderReader(size_t max_media_packets, size_t max_fec_packets);
367 :
368 : const size_t max_media_packets_;
369 : const size_t max_fec_packets_;
370 : };
371 :
372 0 : class FecHeaderWriter {
373 : public:
374 : virtual ~FecHeaderWriter();
375 :
376 : // The maximum number of media packets that can be covered by one FEC packet.
377 : size_t MaxMediaPackets() const;
378 :
379 : // The maximum number of FEC packets that is supported, per call
380 : // to ForwardErrorCorrection::EncodeFec().
381 : size_t MaxFecPackets() const;
382 :
383 : // The maximum overhead (in bytes) per packet, due to FEC headers.
384 : size_t MaxPacketOverhead() const;
385 :
386 : // Calculates the minimum packet mask size needed (in bytes),
387 : // given the discrete options of the ULPFEC masks and the bits
388 : // set in the current packet mask.
389 : virtual size_t MinPacketMaskSize(const uint8_t* packet_mask,
390 : size_t packet_mask_size) const = 0;
391 :
392 : // The header size (in bytes), given the packet mask size.
393 : virtual size_t FecHeaderSize(size_t packet_mask_size) const = 0;
394 :
395 : // Writes FEC header.
396 : virtual void FinalizeFecHeader(
397 : uint32_t media_ssrc,
398 : uint16_t seq_num_base,
399 : const uint8_t* packet_mask,
400 : size_t packet_mask_size,
401 : ForwardErrorCorrection::Packet* fec_packet) const = 0;
402 :
403 : protected:
404 : FecHeaderWriter(size_t max_media_packets,
405 : size_t max_fec_packets,
406 : size_t max_packet_overhead);
407 :
408 : const size_t max_media_packets_;
409 : const size_t max_fec_packets_;
410 : const size_t max_packet_overhead_;
411 : };
412 :
413 : } // namespace webrtc
414 :
415 : #endif // WEBRTC_MODULES_RTP_RTCP_SOURCE_FORWARD_ERROR_CORRECTION_H_
|