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 : #include "webrtc/modules/rtp_rtcp/source/forward_error_correction.h"
12 :
13 : #include <string.h>
14 :
15 : #include <algorithm>
16 : #include <iterator>
17 : #include <utility>
18 :
19 : #include "webrtc/base/checks.h"
20 : #include "webrtc/base/logging.h"
21 : #include "webrtc/modules/rtp_rtcp/include/rtp_rtcp_defines.h"
22 : #include "webrtc/modules/rtp_rtcp/source/byte_io.h"
23 : #include "webrtc/modules/rtp_rtcp/source/flexfec_header_reader_writer.h"
24 : #include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h"
25 : #include "webrtc/modules/rtp_rtcp/source/ulpfec_header_reader_writer.h"
26 :
27 : namespace webrtc {
28 :
29 : namespace {
30 : // Transport header size in bytes. Assume UDP/IPv4 as a reasonable minimum.
31 : constexpr size_t kTransportOverhead = 28;
32 : } // namespace
33 :
34 0 : ForwardErrorCorrection::Packet::Packet() : length(0), data(), ref_count_(0) {}
35 : ForwardErrorCorrection::Packet::~Packet() = default;
36 :
37 0 : int32_t ForwardErrorCorrection::Packet::AddRef() {
38 0 : return ++ref_count_;
39 : }
40 :
41 0 : int32_t ForwardErrorCorrection::Packet::Release() {
42 : int32_t ref_count;
43 0 : ref_count = --ref_count_;
44 0 : if (ref_count == 0)
45 0 : delete this;
46 0 : return ref_count;
47 : }
48 :
49 : // This comparator is used to compare std::unique_ptr's pointing to
50 : // subclasses of SortablePackets. It needs to be parametric since
51 : // the std::unique_ptr's are not covariant w.r.t. the types that
52 : // they are pointing to.
53 : template <typename S, typename T>
54 0 : bool ForwardErrorCorrection::SortablePacket::LessThan::operator() (
55 : const S& first,
56 : const T& second) {
57 0 : return IsNewerSequenceNumber(second->seq_num, first->seq_num);
58 : }
59 :
60 : ForwardErrorCorrection::ReceivedPacket::ReceivedPacket() = default;
61 : ForwardErrorCorrection::ReceivedPacket::~ReceivedPacket() = default;
62 :
63 : ForwardErrorCorrection::RecoveredPacket::RecoveredPacket() = default;
64 : ForwardErrorCorrection::RecoveredPacket::~RecoveredPacket() = default;
65 :
66 : ForwardErrorCorrection::ProtectedPacket::ProtectedPacket() = default;
67 : ForwardErrorCorrection::ProtectedPacket::~ProtectedPacket() = default;
68 :
69 : ForwardErrorCorrection::ReceivedFecPacket::ReceivedFecPacket() = default;
70 : ForwardErrorCorrection::ReceivedFecPacket::~ReceivedFecPacket() = default;
71 :
72 0 : ForwardErrorCorrection::ForwardErrorCorrection(
73 : std::unique_ptr<FecHeaderReader> fec_header_reader,
74 0 : std::unique_ptr<FecHeaderWriter> fec_header_writer)
75 0 : : fec_header_reader_(std::move(fec_header_reader)),
76 0 : fec_header_writer_(std::move(fec_header_writer)),
77 : generated_fec_packets_(fec_header_writer_->MaxFecPackets()),
78 0 : packet_mask_size_(0) {}
79 :
80 : ForwardErrorCorrection::~ForwardErrorCorrection() = default;
81 :
82 0 : std::unique_ptr<ForwardErrorCorrection> ForwardErrorCorrection::CreateUlpfec() {
83 0 : std::unique_ptr<FecHeaderReader> fec_header_reader(new UlpfecHeaderReader());
84 0 : std::unique_ptr<FecHeaderWriter> fec_header_writer(new UlpfecHeaderWriter());
85 : return std::unique_ptr<ForwardErrorCorrection>(new ForwardErrorCorrection(
86 0 : std::move(fec_header_reader), std::move(fec_header_writer)));
87 : }
88 :
89 : std::unique_ptr<ForwardErrorCorrection>
90 0 : ForwardErrorCorrection::CreateFlexfec() {
91 0 : std::unique_ptr<FecHeaderReader> fec_header_reader(new FlexfecHeaderReader());
92 0 : std::unique_ptr<FecHeaderWriter> fec_header_writer(new FlexfecHeaderWriter());
93 : return std::unique_ptr<ForwardErrorCorrection>(new ForwardErrorCorrection(
94 0 : std::move(fec_header_reader), std::move(fec_header_writer)));
95 : }
96 :
97 0 : int ForwardErrorCorrection::EncodeFec(const PacketList& media_packets,
98 : uint8_t protection_factor,
99 : int num_important_packets,
100 : bool use_unequal_protection,
101 : FecMaskType fec_mask_type,
102 : std::list<Packet*>* fec_packets) {
103 0 : const size_t num_media_packets = media_packets.size();
104 :
105 : // Sanity check arguments.
106 0 : RTC_DCHECK_GT(num_media_packets, 0);
107 0 : RTC_DCHECK_GE(num_important_packets, 0);
108 0 : RTC_DCHECK_LE(num_important_packets, num_media_packets);
109 0 : RTC_DCHECK(fec_packets->empty());
110 0 : const size_t max_media_packets = fec_header_writer_->MaxMediaPackets();
111 0 : if (num_media_packets > max_media_packets) {
112 0 : LOG(LS_WARNING) << "Can't protect " << num_media_packets
113 0 : << " media packets per frame. Max is " << max_media_packets
114 0 : << ".";
115 0 : return -1;
116 : }
117 :
118 : // Error check the media packets.
119 0 : for (const auto& media_packet : media_packets) {
120 0 : RTC_DCHECK(media_packet);
121 0 : if (media_packet->length < kRtpHeaderSize) {
122 0 : LOG(LS_WARNING) << "Media packet " << media_packet->length << " bytes "
123 0 : << "is smaller than RTP header.";
124 0 : return -1;
125 : }
126 : // Ensure the FEC packets will fit in a typical MTU.
127 0 : if (media_packet->length + MaxPacketOverhead() + kTransportOverhead >
128 : IP_PACKET_SIZE) {
129 0 : LOG(LS_WARNING) << "Media packet " << media_packet->length << " bytes "
130 0 : << "with overhead is larger than " << IP_PACKET_SIZE
131 0 : << " bytes.";
132 : }
133 : }
134 :
135 : // Prepare generated FEC packets.
136 0 : int num_fec_packets = NumFecPackets(num_media_packets, protection_factor);
137 0 : if (num_fec_packets == 0) {
138 0 : return 0;
139 : }
140 0 : for (int i = 0; i < num_fec_packets; ++i) {
141 0 : memset(generated_fec_packets_[i].data, 0, IP_PACKET_SIZE);
142 : // Use this as a marker for untouched packets.
143 0 : generated_fec_packets_[i].length = 0;
144 0 : fec_packets->push_back(&generated_fec_packets_[i]);
145 : }
146 :
147 0 : const internal::PacketMaskTable mask_table(fec_mask_type, num_media_packets);
148 0 : packet_mask_size_ = internal::PacketMaskSize(num_media_packets);
149 0 : memset(packet_masks_, 0, num_fec_packets * packet_mask_size_);
150 0 : internal::GeneratePacketMasks(num_media_packets, num_fec_packets,
151 : num_important_packets, use_unequal_protection,
152 0 : mask_table, packet_masks_);
153 :
154 : // Adapt packet masks to missing media packets.
155 0 : int num_mask_bits = InsertZerosInPacketMasks(media_packets, num_fec_packets);
156 0 : if (num_mask_bits < 0) {
157 0 : return -1;
158 : }
159 0 : packet_mask_size_ = internal::PacketMaskSize(num_mask_bits);
160 :
161 : // Write FEC packets to |generated_fec_packets_|.
162 0 : GenerateFecPayloads(media_packets, num_fec_packets);
163 : // TODO(brandtr): Generalize this when multistream protection support is
164 : // added.
165 0 : const uint32_t media_ssrc = ParseSsrc(media_packets.front()->data);
166 : const uint16_t seq_num_base =
167 0 : ParseSequenceNumber(media_packets.front()->data);
168 0 : FinalizeFecHeaders(num_fec_packets, media_ssrc, seq_num_base);
169 :
170 0 : return 0;
171 : }
172 :
173 0 : int ForwardErrorCorrection::NumFecPackets(int num_media_packets,
174 : int protection_factor) {
175 : // Result in Q0 with an unsigned round.
176 0 : int num_fec_packets = (num_media_packets * protection_factor + (1 << 7)) >> 8;
177 : // Generate at least one FEC packet if we need protection.
178 0 : if (protection_factor > 0 && num_fec_packets == 0) {
179 0 : num_fec_packets = 1;
180 : }
181 0 : RTC_DCHECK_LE(num_fec_packets, num_media_packets);
182 0 : return num_fec_packets;
183 : }
184 :
185 0 : void ForwardErrorCorrection::GenerateFecPayloads(
186 : const PacketList& media_packets,
187 : size_t num_fec_packets) {
188 0 : RTC_DCHECK(!media_packets.empty());
189 0 : for (size_t i = 0; i < num_fec_packets; ++i) {
190 0 : Packet* const fec_packet = &generated_fec_packets_[i];
191 0 : size_t pkt_mask_idx = i * packet_mask_size_;
192 0 : const size_t min_packet_mask_size = fec_header_writer_->MinPacketMaskSize(
193 0 : &packet_masks_[pkt_mask_idx], packet_mask_size_);
194 : const size_t fec_header_size =
195 0 : fec_header_writer_->FecHeaderSize(min_packet_mask_size);
196 :
197 0 : size_t media_pkt_idx = 0;
198 0 : auto media_packets_it = media_packets.cbegin();
199 0 : uint16_t prev_seq_num = ParseSequenceNumber((*media_packets_it)->data);
200 0 : while (media_packets_it != media_packets.end()) {
201 0 : Packet* const media_packet = media_packets_it->get();
202 : // Should |media_packet| be protected by |fec_packet|?
203 0 : if (packet_masks_[pkt_mask_idx] & (1 << (7 - media_pkt_idx))) {
204 0 : size_t media_payload_length = media_packet->length - kRtpHeaderSize;
205 :
206 0 : bool first_protected_packet = (fec_packet->length == 0);
207 0 : size_t fec_packet_length = fec_header_size + media_payload_length;
208 0 : if (fec_packet_length > fec_packet->length) {
209 : // Recall that XORing with zero (which the FEC packets are prefilled
210 : // with) is the identity operator, thus all prior XORs are
211 : // still correct even though we expand the packet length here.
212 0 : fec_packet->length = fec_packet_length;
213 : }
214 0 : if (first_protected_packet) {
215 : // Write P, X, CC, M, and PT recovery fields.
216 : // Note that bits 0, 1, and 16 are overwritten in FinalizeFecHeaders.
217 0 : memcpy(&fec_packet->data[0], &media_packet->data[0], 2);
218 : // Write length recovery field. (This is a temporary location for
219 : // ULPFEC.)
220 0 : ByteWriter<uint16_t>::WriteBigEndian(&fec_packet->data[2],
221 0 : media_payload_length);
222 : // Write timestamp recovery field.
223 0 : memcpy(&fec_packet->data[4], &media_packet->data[4], 4);
224 : // Write payload.
225 0 : memcpy(&fec_packet->data[fec_header_size],
226 0 : &media_packet->data[kRtpHeaderSize], media_payload_length);
227 : } else {
228 0 : XorHeaders(*media_packet, fec_packet);
229 : XorPayloads(*media_packet, media_payload_length, fec_header_size,
230 0 : fec_packet);
231 : }
232 : }
233 0 : media_packets_it++;
234 0 : if (media_packets_it != media_packets.end()) {
235 0 : uint16_t seq_num = ParseSequenceNumber((*media_packets_it)->data);
236 0 : media_pkt_idx += static_cast<uint16_t>(seq_num - prev_seq_num);
237 0 : prev_seq_num = seq_num;
238 : }
239 0 : pkt_mask_idx += media_pkt_idx / 8;
240 0 : media_pkt_idx %= 8;
241 : }
242 0 : RTC_DCHECK_GT(fec_packet->length, 0)
243 0 : << "Packet mask is wrong or poorly designed.";
244 : }
245 0 : }
246 :
247 0 : int ForwardErrorCorrection::InsertZerosInPacketMasks(
248 : const PacketList& media_packets,
249 : size_t num_fec_packets) {
250 0 : size_t num_media_packets = media_packets.size();
251 0 : if (num_media_packets <= 1) {
252 0 : return num_media_packets;
253 : }
254 0 : uint16_t last_seq_num = ParseSequenceNumber(media_packets.back()->data);
255 0 : uint16_t first_seq_num = ParseSequenceNumber(media_packets.front()->data);
256 : size_t total_missing_seq_nums =
257 0 : static_cast<uint16_t>(last_seq_num - first_seq_num) - num_media_packets +
258 0 : 1;
259 0 : if (total_missing_seq_nums == 0) {
260 : // All sequence numbers are covered by the packet mask.
261 : // No zero insertion required.
262 0 : return num_media_packets;
263 : }
264 0 : const size_t max_media_packets = fec_header_writer_->MaxMediaPackets();
265 0 : if (total_missing_seq_nums + num_media_packets > max_media_packets) {
266 0 : return -1;
267 : }
268 : // Allocate the new mask.
269 : size_t tmp_packet_mask_size =
270 0 : internal::PacketMaskSize(total_missing_seq_nums + num_media_packets);
271 0 : memset(tmp_packet_masks_, 0, num_fec_packets * tmp_packet_mask_size);
272 :
273 0 : auto media_packets_it = media_packets.cbegin();
274 0 : uint16_t prev_seq_num = first_seq_num;
275 0 : ++media_packets_it;
276 :
277 : // Insert the first column.
278 0 : internal::CopyColumn(tmp_packet_masks_, tmp_packet_mask_size, packet_masks_,
279 0 : packet_mask_size_, num_fec_packets, 0, 0);
280 0 : size_t new_bit_index = 1;
281 0 : size_t old_bit_index = 1;
282 : // Insert zeros in the bit mask for every hole in the sequence.
283 0 : while (media_packets_it != media_packets.end()) {
284 0 : if (new_bit_index == max_media_packets) {
285 : // We can only cover up to 48 packets.
286 0 : break;
287 : }
288 0 : uint16_t seq_num = ParseSequenceNumber((*media_packets_it)->data);
289 : const int num_zeros_to_insert =
290 0 : static_cast<uint16_t>(seq_num - prev_seq_num - 1);
291 0 : if (num_zeros_to_insert > 0) {
292 0 : internal::InsertZeroColumns(num_zeros_to_insert, tmp_packet_masks_,
293 : tmp_packet_mask_size, num_fec_packets,
294 0 : new_bit_index);
295 : }
296 0 : new_bit_index += num_zeros_to_insert;
297 0 : internal::CopyColumn(tmp_packet_masks_, tmp_packet_mask_size, packet_masks_,
298 0 : packet_mask_size_, num_fec_packets, new_bit_index,
299 0 : old_bit_index);
300 0 : ++new_bit_index;
301 0 : ++old_bit_index;
302 0 : prev_seq_num = seq_num;
303 0 : ++media_packets_it;
304 : }
305 0 : if (new_bit_index % 8 != 0) {
306 : // We didn't fill the last byte. Shift bits to correct position.
307 0 : for (uint16_t row = 0; row < num_fec_packets; ++row) {
308 0 : int new_byte_index = row * tmp_packet_mask_size + new_bit_index / 8;
309 0 : tmp_packet_masks_[new_byte_index] <<= (7 - (new_bit_index % 8));
310 : }
311 : }
312 : // Replace the old mask with the new.
313 0 : memcpy(packet_masks_, tmp_packet_masks_,
314 0 : num_fec_packets * tmp_packet_mask_size);
315 0 : return new_bit_index;
316 : }
317 :
318 0 : void ForwardErrorCorrection::FinalizeFecHeaders(size_t num_fec_packets,
319 : uint32_t media_ssrc,
320 : uint16_t seq_num_base) {
321 0 : for (size_t i = 0; i < num_fec_packets; ++i) {
322 0 : fec_header_writer_->FinalizeFecHeader(
323 0 : media_ssrc, seq_num_base, &packet_masks_[i * packet_mask_size_],
324 0 : packet_mask_size_, &generated_fec_packets_[i]);
325 : }
326 0 : }
327 :
328 0 : void ForwardErrorCorrection::ResetState(
329 : RecoveredPacketList* recovered_packets) {
330 : // Free the memory for any existing recovered packets, if the caller hasn't.
331 0 : recovered_packets->clear();
332 0 : received_fec_packets_.clear();
333 0 : }
334 :
335 0 : void ForwardErrorCorrection::InsertMediaPacket(
336 : RecoveredPacketList* recovered_packets,
337 : ReceivedPacket* received_packet) {
338 : // Search for duplicate packets.
339 0 : for (const auto& recovered_packet : *recovered_packets) {
340 0 : if (received_packet->seq_num == recovered_packet->seq_num) {
341 : // Duplicate packet, no need to add to list.
342 : // Delete duplicate media packet data.
343 0 : received_packet->pkt = nullptr;
344 0 : return;
345 : }
346 : }
347 0 : std::unique_ptr<RecoveredPacket> recovered_packet(new RecoveredPacket());
348 : // This "recovered packet" was not recovered using parity packets.
349 0 : recovered_packet->was_recovered = false;
350 : // This media packet has already been passed on.
351 0 : recovered_packet->returned = true;
352 0 : recovered_packet->seq_num = received_packet->seq_num;
353 0 : recovered_packet->pkt = received_packet->pkt;
354 0 : recovered_packet->pkt->length = received_packet->pkt->length;
355 : // TODO(holmer): Consider replacing this with a binary search for the right
356 : // position, and then just insert the new packet. Would get rid of the sort.
357 0 : RecoveredPacket* recovered_packet_ptr = recovered_packet.get();
358 0 : recovered_packets->push_back(std::move(recovered_packet));
359 0 : recovered_packets->sort(SortablePacket::LessThan());
360 0 : UpdateCoveringFecPackets(*recovered_packet_ptr);
361 : }
362 :
363 0 : void ForwardErrorCorrection::UpdateCoveringFecPackets(
364 : const RecoveredPacket& packet) {
365 0 : for (auto& fec_packet : received_fec_packets_) {
366 : // Is this FEC packet protecting the media packet |packet|?
367 0 : auto protected_it = std::lower_bound(fec_packet->protected_packets.begin(),
368 0 : fec_packet->protected_packets.end(),
369 0 : &packet, SortablePacket::LessThan());
370 0 : if (protected_it != fec_packet->protected_packets.end() &&
371 0 : (*protected_it)->seq_num == packet.seq_num) {
372 : // Found an FEC packet which is protecting |packet|.
373 0 : (*protected_it)->pkt = packet.pkt;
374 : }
375 : }
376 0 : }
377 :
378 0 : void ForwardErrorCorrection::InsertFecPacket(
379 : const RecoveredPacketList& recovered_packets,
380 : ReceivedPacket* received_packet) {
381 : // Check for duplicate.
382 0 : for (const auto& existing_fec_packet : received_fec_packets_) {
383 0 : if (received_packet->seq_num == existing_fec_packet->seq_num) {
384 : // Delete duplicate FEC packet data.
385 0 : received_packet->pkt = nullptr;
386 0 : return;
387 : }
388 : }
389 0 : std::unique_ptr<ReceivedFecPacket> fec_packet(new ReceivedFecPacket());
390 0 : fec_packet->pkt = received_packet->pkt;
391 0 : fec_packet->seq_num = received_packet->seq_num;
392 0 : fec_packet->ssrc = received_packet->ssrc;
393 : // Parse ULPFEC/FlexFEC header specific info.
394 0 : bool ret = fec_header_reader_->ReadFecHeader(fec_packet.get());
395 0 : if (!ret) {
396 0 : return;
397 : }
398 : // Parse packet mask from header and represent as protected packets.
399 0 : for (uint16_t byte_idx = 0; byte_idx < fec_packet->packet_mask_size;
400 : ++byte_idx) {
401 : uint8_t packet_mask =
402 0 : fec_packet->pkt->data[fec_packet->packet_mask_offset + byte_idx];
403 0 : for (uint16_t bit_idx = 0; bit_idx < 8; ++bit_idx) {
404 0 : if (packet_mask & (1 << (7 - bit_idx))) {
405 : std::unique_ptr<ProtectedPacket> protected_packet(
406 0 : new ProtectedPacket());
407 : // This wraps naturally with the sequence number.
408 0 : protected_packet->seq_num = static_cast<uint16_t>(
409 0 : fec_packet->seq_num_base + (byte_idx << 3) + bit_idx);
410 0 : protected_packet->pkt = nullptr;
411 0 : fec_packet->protected_packets.push_back(std::move(protected_packet));
412 : }
413 : }
414 : }
415 0 : if (fec_packet->protected_packets.empty()) {
416 : // All-zero packet mask; we can discard this FEC packet.
417 0 : LOG(LS_WARNING) << "Received FEC packet has an all-zero packet mask.";
418 : } else {
419 0 : AssignRecoveredPackets(recovered_packets, fec_packet.get());
420 : // TODO(holmer): Consider replacing this with a binary search for the right
421 : // position, and then just insert the new packet. Would get rid of the sort.
422 : //
423 : // For correct decoding, |received_fec_packets_| does not necessarily
424 : // need to be sorted by sequence number (see decoding algorithm in
425 : // AttemptRecover()). By keeping it sorted we try to recover the
426 : // oldest lost packets first, however.
427 0 : received_fec_packets_.push_back(std::move(fec_packet));
428 0 : received_fec_packets_.sort(SortablePacket::LessThan());
429 0 : const size_t max_fec_packets = fec_header_reader_->MaxFecPackets();
430 0 : if (received_fec_packets_.size() > max_fec_packets) {
431 0 : received_fec_packets_.pop_front();
432 : }
433 0 : RTC_DCHECK_LE(received_fec_packets_.size(), max_fec_packets);
434 : }
435 : }
436 :
437 0 : void ForwardErrorCorrection::AssignRecoveredPackets(
438 : const RecoveredPacketList& recovered_packets,
439 : ReceivedFecPacket* fec_packet) {
440 0 : ProtectedPacketList* protected_packets = &fec_packet->protected_packets;
441 0 : std::vector<RecoveredPacket*> recovered_protected_packets;
442 :
443 : // Find intersection between the (sorted) containers |protected_packets|
444 : // and |recovered_packets|, i.e. all protected packets that have already
445 : // been recovered. Update the corresponding protected packets to point to
446 : // the recovered packets.
447 0 : auto it_p = protected_packets->cbegin();
448 0 : auto it_r = recovered_packets.cbegin();
449 : SortablePacket::LessThan less_than;
450 0 : while (it_p != protected_packets->end() && it_r != recovered_packets.end()) {
451 0 : if (less_than(*it_p, *it_r)) {
452 0 : ++it_p;
453 0 : } else if (less_than(*it_r, *it_p)) {
454 0 : ++it_r;
455 : } else { // *it_p == *it_r.
456 : // This protected packet has already been recovered.
457 0 : (*it_p)->pkt = (*it_r)->pkt;
458 0 : ++it_p;
459 0 : ++it_r;
460 : }
461 : }
462 0 : }
463 :
464 0 : void ForwardErrorCorrection::InsertPackets(
465 : ReceivedPacketList* received_packets,
466 : RecoveredPacketList* recovered_packets) {
467 0 : while (!received_packets->empty()) {
468 0 : ReceivedPacket* received_packet = received_packets->front().get();
469 :
470 : // Check for discarding oldest FEC packet, to avoid wrong FEC decoding from
471 : // sequence number wrap-around. Detection of old FEC packet is based on
472 : // sequence number difference of received packet and oldest packet in FEC
473 : // packet list.
474 : // TODO(marpan/holmer): We should be able to improve detection/discarding of
475 : // old FEC packets based on timestamp information or better sequence number
476 : // thresholding (e.g., to distinguish between wrap-around and reordering).
477 0 : if (!received_fec_packets_.empty()) {
478 : uint16_t seq_num_diff =
479 0 : abs(static_cast<int>(received_packet->seq_num) -
480 0 : static_cast<int>(received_fec_packets_.front()->seq_num));
481 0 : if (seq_num_diff > 0x3fff) {
482 0 : received_fec_packets_.pop_front();
483 : }
484 : }
485 :
486 0 : if (received_packet->is_fec) {
487 0 : InsertFecPacket(*recovered_packets, received_packet);
488 : } else {
489 0 : InsertMediaPacket(recovered_packets, received_packet);
490 : }
491 : // Delete the received packet "wrapper".
492 0 : received_packets->pop_front();
493 : }
494 0 : RTC_DCHECK(received_packets->empty());
495 0 : DiscardOldRecoveredPackets(recovered_packets);
496 0 : }
497 :
498 0 : bool ForwardErrorCorrection::StartPacketRecovery(
499 : const ReceivedFecPacket& fec_packet,
500 : RecoveredPacket* recovered_packet) {
501 : // Sanity check packet length.
502 0 : if (fec_packet.pkt->length < fec_packet.fec_header_size) {
503 0 : LOG(LS_WARNING)
504 : << "The FEC packet is truncated: it does not contain enough room "
505 0 : << "for its own header.";
506 0 : return false;
507 : }
508 : // Initialize recovered packet data.
509 0 : recovered_packet->pkt = new Packet();
510 0 : memset(recovered_packet->pkt->data, 0, IP_PACKET_SIZE);
511 0 : recovered_packet->returned = false;
512 0 : recovered_packet->was_recovered = true;
513 : // Copy bytes corresponding to minimum RTP header size.
514 : // Note that the sequence number and SSRC fields will be overwritten
515 : // at the end of packet recovery.
516 0 : memcpy(&recovered_packet->pkt->data, fec_packet.pkt->data, kRtpHeaderSize);
517 : // Copy remaining FEC payload.
518 0 : if (fec_packet.protection_length >
519 0 : std::min(sizeof(recovered_packet->pkt->data) - kRtpHeaderSize,
520 0 : sizeof(fec_packet.pkt->data) - fec_packet.fec_header_size)) {
521 0 : LOG(LS_WARNING) << "Incorrect protection length, dropping FEC packet.";
522 0 : return false;
523 : }
524 0 : memcpy(&recovered_packet->pkt->data[kRtpHeaderSize],
525 0 : &fec_packet.pkt->data[fec_packet.fec_header_size],
526 0 : fec_packet.protection_length);
527 0 : return true;
528 : }
529 :
530 0 : bool ForwardErrorCorrection::FinishPacketRecovery(
531 : const ReceivedFecPacket& fec_packet,
532 : RecoveredPacket* recovered_packet) {
533 : // Set the RTP version to 2.
534 0 : recovered_packet->pkt->data[0] |= 0x80; // Set the 1st bit.
535 0 : recovered_packet->pkt->data[0] &= 0xbf; // Clear the 2nd bit.
536 : // Recover the packet length, from temporary location.
537 0 : recovered_packet->pkt->length =
538 0 : ByteReader<uint16_t>::ReadBigEndian(&recovered_packet->pkt->data[2]) +
539 : kRtpHeaderSize;
540 0 : if (recovered_packet->pkt->length >
541 : sizeof(recovered_packet->pkt->data) - kRtpHeaderSize) {
542 0 : LOG(LS_WARNING) << "The recovered packet had a length larger than a "
543 0 : << "typical IP packet, and is thus dropped.";
544 0 : return false;
545 : }
546 : // Set the SN field.
547 0 : ByteWriter<uint16_t>::WriteBigEndian(&recovered_packet->pkt->data[2],
548 0 : recovered_packet->seq_num);
549 : // Set the SSRC field.
550 0 : ByteWriter<uint32_t>::WriteBigEndian(&recovered_packet->pkt->data[8],
551 0 : fec_packet.protected_ssrc);
552 0 : return true;
553 : }
554 :
555 0 : void ForwardErrorCorrection::XorHeaders(const Packet& src, Packet* dst) {
556 : // XOR the first 2 bytes of the header: V, P, X, CC, M, PT fields.
557 0 : dst->data[0] ^= src.data[0];
558 0 : dst->data[1] ^= src.data[1];
559 :
560 : // XOR the length recovery field.
561 : uint8_t src_payload_length_network_order[2];
562 0 : ByteWriter<uint16_t>::WriteBigEndian(src_payload_length_network_order,
563 0 : src.length - kRtpHeaderSize);
564 0 : dst->data[2] ^= src_payload_length_network_order[0];
565 0 : dst->data[3] ^= src_payload_length_network_order[1];
566 :
567 : // XOR the 5th to 8th bytes of the header: the timestamp field.
568 0 : dst->data[4] ^= src.data[4];
569 0 : dst->data[5] ^= src.data[5];
570 0 : dst->data[6] ^= src.data[6];
571 0 : dst->data[7] ^= src.data[7];
572 :
573 : // Skip the 9th to 12th bytes of the header.
574 0 : }
575 :
576 0 : void ForwardErrorCorrection::XorPayloads(const Packet& src,
577 : size_t payload_length,
578 : size_t dst_offset,
579 : Packet* dst) {
580 : // XOR the payload.
581 0 : RTC_DCHECK_LE(kRtpHeaderSize + payload_length, sizeof(src.data));
582 0 : RTC_DCHECK_LE(dst_offset + payload_length, sizeof(dst->data));
583 0 : for (size_t i = 0; i < payload_length; ++i) {
584 0 : dst->data[dst_offset + i] ^= src.data[kRtpHeaderSize + i];
585 : }
586 0 : }
587 :
588 0 : bool ForwardErrorCorrection::RecoverPacket(const ReceivedFecPacket& fec_packet,
589 : RecoveredPacket* recovered_packet) {
590 0 : if (!StartPacketRecovery(fec_packet, recovered_packet)) {
591 0 : return false;
592 : }
593 0 : for (const auto& protected_packet : fec_packet.protected_packets) {
594 0 : if (protected_packet->pkt == nullptr) {
595 : // This is the packet we're recovering.
596 0 : recovered_packet->seq_num = protected_packet->seq_num;
597 : } else {
598 0 : XorHeaders(*protected_packet->pkt, recovered_packet->pkt);
599 0 : XorPayloads(*protected_packet->pkt, protected_packet->pkt->length,
600 0 : kRtpHeaderSize, recovered_packet->pkt);
601 : }
602 : }
603 0 : if (!FinishPacketRecovery(fec_packet, recovered_packet)) {
604 0 : return false;
605 : }
606 0 : return true;
607 : }
608 :
609 0 : void ForwardErrorCorrection::AttemptRecovery(
610 : RecoveredPacketList* recovered_packets) {
611 0 : auto fec_packet_it = received_fec_packets_.begin();
612 0 : while (fec_packet_it != received_fec_packets_.end()) {
613 : // Search for each FEC packet's protected media packets.
614 0 : int packets_missing = NumCoveredPacketsMissing(**fec_packet_it);
615 :
616 : // We can only recover one packet with an FEC packet.
617 0 : if (packets_missing == 1) {
618 : // Recovery possible.
619 0 : std::unique_ptr<RecoveredPacket> recovered_packet(new RecoveredPacket());
620 0 : recovered_packet->pkt = nullptr;
621 0 : if (!RecoverPacket(**fec_packet_it, recovered_packet.get())) {
622 : // Can't recover using this packet, drop it.
623 0 : fec_packet_it = received_fec_packets_.erase(fec_packet_it);
624 0 : continue;
625 : }
626 :
627 0 : auto recovered_packet_ptr = recovered_packet.get();
628 : // Add recovered packet to the list of recovered packets and update any
629 : // FEC packets covering this packet with a pointer to the data.
630 : // TODO(holmer): Consider replacing this with a binary search for the
631 : // right position, and then just insert the new packet. Would get rid of
632 : // the sort.
633 0 : recovered_packets->push_back(std::move(recovered_packet));
634 0 : recovered_packets->sort(SortablePacket::LessThan());
635 0 : UpdateCoveringFecPackets(*recovered_packet_ptr);
636 0 : DiscardOldRecoveredPackets(recovered_packets);
637 0 : fec_packet_it = received_fec_packets_.erase(fec_packet_it);
638 :
639 : // A packet has been recovered. We need to check the FEC list again, as
640 : // this may allow additional packets to be recovered.
641 : // Restart for first FEC packet.
642 0 : fec_packet_it = received_fec_packets_.begin();
643 0 : } else if (packets_missing == 0) {
644 : // Either all protected packets arrived or have been recovered. We can
645 : // discard this FEC packet.
646 0 : fec_packet_it = received_fec_packets_.erase(fec_packet_it);
647 : } else {
648 0 : fec_packet_it++;
649 : }
650 : }
651 0 : }
652 :
653 0 : int ForwardErrorCorrection::NumCoveredPacketsMissing(
654 : const ReceivedFecPacket& fec_packet) {
655 0 : int packets_missing = 0;
656 0 : for (const auto& protected_packet : fec_packet.protected_packets) {
657 0 : if (protected_packet->pkt == nullptr) {
658 0 : ++packets_missing;
659 0 : if (packets_missing > 1) {
660 0 : break; // We can't recover more than one packet.
661 : }
662 : }
663 : }
664 0 : return packets_missing;
665 : }
666 :
667 0 : void ForwardErrorCorrection::DiscardOldRecoveredPackets(
668 : RecoveredPacketList* recovered_packets) {
669 0 : const size_t max_media_packets = fec_header_reader_->MaxMediaPackets();
670 0 : while (recovered_packets->size() > max_media_packets) {
671 0 : recovered_packets->pop_front();
672 : }
673 0 : RTC_DCHECK_LE(recovered_packets->size(), max_media_packets);
674 0 : }
675 :
676 0 : uint16_t ForwardErrorCorrection::ParseSequenceNumber(uint8_t* packet) {
677 0 : return (packet[2] << 8) + packet[3];
678 : }
679 :
680 0 : uint32_t ForwardErrorCorrection::ParseSsrc(uint8_t* packet) {
681 0 : return (packet[8] << 24) + (packet[9] << 16) + (packet[10] << 8) + packet[11];
682 : }
683 :
684 0 : int ForwardErrorCorrection::DecodeFec(
685 : ReceivedPacketList* received_packets,
686 : RecoveredPacketList* recovered_packets) {
687 : // TODO(marpan/ajm): can we check for multiple ULP headers, and return an
688 : // error?
689 0 : const size_t max_media_packets = fec_header_reader_->MaxMediaPackets();
690 0 : if (recovered_packets->size() == max_media_packets) {
691 : const unsigned int seq_num_diff =
692 0 : abs(static_cast<int>(received_packets->front()->seq_num) -
693 0 : static_cast<int>(recovered_packets->back()->seq_num));
694 0 : if (seq_num_diff > max_media_packets) {
695 : // A big gap in sequence numbers. The old recovered packets
696 : // are now useless, so it's safe to do a reset.
697 0 : ResetState(recovered_packets);
698 : }
699 : }
700 0 : InsertPackets(received_packets, recovered_packets);
701 0 : AttemptRecovery(recovered_packets);
702 0 : return 0;
703 : }
704 :
705 0 : size_t ForwardErrorCorrection::MaxPacketOverhead() const {
706 0 : return fec_header_writer_->MaxPacketOverhead();
707 : }
708 :
709 0 : FecHeaderReader::FecHeaderReader(size_t max_media_packets,
710 0 : size_t max_fec_packets)
711 : : max_media_packets_(max_media_packets),
712 0 : max_fec_packets_(max_fec_packets) {}
713 :
714 : FecHeaderReader::~FecHeaderReader() = default;
715 :
716 0 : size_t FecHeaderReader::MaxMediaPackets() const {
717 0 : return max_media_packets_;
718 : }
719 :
720 0 : size_t FecHeaderReader::MaxFecPackets() const {
721 0 : return max_fec_packets_;
722 : }
723 :
724 0 : FecHeaderWriter::FecHeaderWriter(size_t max_media_packets,
725 : size_t max_fec_packets,
726 0 : size_t max_packet_overhead)
727 : : max_media_packets_(max_media_packets),
728 : max_fec_packets_(max_fec_packets),
729 0 : max_packet_overhead_(max_packet_overhead) {}
730 :
731 : FecHeaderWriter::~FecHeaderWriter() = default;
732 :
733 0 : size_t FecHeaderWriter::MaxMediaPackets() const {
734 0 : return max_media_packets_;
735 : }
736 :
737 0 : size_t FecHeaderWriter::MaxFecPackets() const {
738 0 : return max_fec_packets_;
739 : }
740 :
741 0 : size_t FecHeaderWriter::MaxPacketOverhead() const {
742 0 : return max_packet_overhead_;
743 : }
744 :
745 : } // namespace webrtc
|