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