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 <stdlib.h>
14 #include <string.h>
15
16 #include <algorithm>
17 #include <iterator>
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/forward_error_correction_internal.h"
24
25 namespace webrtc {
26
27 // FEC header size in bytes.
28 const uint8_t kFecHeaderSize = 10;
29
30 // ULP header size in bytes (L bit is set).
31 const uint8_t kUlpHeaderSizeLBitSet = (2 + kMaskSizeLBitSet);
32
33 // ULP header size in bytes (L bit is cleared).
34 const uint8_t kUlpHeaderSizeLBitClear = (2 + kMaskSizeLBitClear);
35
36 // Transport header size in bytes. Assume UDP/IPv4 as a reasonable minimum.
37 const uint8_t kTransportOverhead = 28;
38
39 enum { kMaxFecPackets = ForwardErrorCorrection::kMaxMediaPackets };
40
AddRef()41 int32_t ForwardErrorCorrection::Packet::AddRef() {
42 return ++ref_count_;
43 }
44
Release()45 int32_t ForwardErrorCorrection::Packet::Release() {
46 int32_t ref_count;
47 ref_count = --ref_count_;
48 if (ref_count == 0)
49 delete this;
50 return ref_count;
51 }
52
53 // Used to link media packets to their protecting FEC packets.
54 //
55 // TODO(holmer): Refactor into a proper class.
56 class ProtectedPacket : public ForwardErrorCorrection::SortablePacket {
57 public:
58 rtc::scoped_refptr<ForwardErrorCorrection::Packet> pkt;
59 };
60
61 typedef std::list<ProtectedPacket*> ProtectedPacketList;
62
63 //
64 // Used for internal storage of FEC packets in a list.
65 //
66 // TODO(holmer): Refactor into a proper class.
67 class FecPacket : public ForwardErrorCorrection::SortablePacket {
68 public:
69 ProtectedPacketList protected_pkt_list;
70 uint32_t ssrc; // SSRC of the current frame.
71 rtc::scoped_refptr<ForwardErrorCorrection::Packet> pkt;
72 };
73
LessThan(const SortablePacket * first,const SortablePacket * second)74 bool ForwardErrorCorrection::SortablePacket::LessThan(
75 const SortablePacket* first,
76 const SortablePacket* second) {
77 return IsNewerSequenceNumber(second->seq_num, first->seq_num);
78 }
79
ReceivedPacket()80 ForwardErrorCorrection::ReceivedPacket::ReceivedPacket() {}
~ReceivedPacket()81 ForwardErrorCorrection::ReceivedPacket::~ReceivedPacket() {}
82
RecoveredPacket()83 ForwardErrorCorrection::RecoveredPacket::RecoveredPacket() {}
~RecoveredPacket()84 ForwardErrorCorrection::RecoveredPacket::~RecoveredPacket() {}
85
ForwardErrorCorrection()86 ForwardErrorCorrection::ForwardErrorCorrection()
87 : generated_fec_packets_(kMaxMediaPackets), fec_packet_received_(false) {}
88
~ForwardErrorCorrection()89 ForwardErrorCorrection::~ForwardErrorCorrection() {}
90
91 // Input packet
92 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
93 // | RTP Header (12 octets) |
94 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
95 // | RTP Payload |
96 // | |
97 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
98
99 // Output packet
100 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
101 // | FEC Header (10 octets) |
102 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
103 // | FEC Level 0 Header |
104 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
105 // | FEC Level 0 Payload |
106 // | |
107 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
GenerateFEC(const PacketList & media_packet_list,uint8_t protection_factor,int num_important_packets,bool use_unequal_protection,FecMaskType fec_mask_type,PacketList * fec_packet_list)108 int32_t ForwardErrorCorrection::GenerateFEC(const PacketList& media_packet_list,
109 uint8_t protection_factor,
110 int num_important_packets,
111 bool use_unequal_protection,
112 FecMaskType fec_mask_type,
113 PacketList* fec_packet_list) {
114 const uint16_t num_media_packets = media_packet_list.size();
115 // Sanity check arguments.
116 assert(num_media_packets > 0);
117 assert(num_important_packets >= 0 &&
118 num_important_packets <= num_media_packets);
119 assert(fec_packet_list->empty());
120
121 if (num_media_packets > kMaxMediaPackets) {
122 LOG(LS_WARNING) << "Can't protect " << num_media_packets
123 << " media packets per frame. Max is " << kMaxMediaPackets;
124 return -1;
125 }
126
127 bool l_bit = (num_media_packets > 8 * kMaskSizeLBitClear);
128 int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;
129
130 // Do some error checking on the media packets.
131 for (Packet* media_packet : media_packet_list) {
132 assert(media_packet);
133
134 if (media_packet->length < kRtpHeaderSize) {
135 LOG(LS_WARNING) << "Media packet " << media_packet->length << " bytes "
136 << "is smaller than RTP header.";
137 return -1;
138 }
139
140 // Ensure our FEC packets will fit in a typical MTU.
141 if (media_packet->length + PacketOverhead() + kTransportOverhead >
142 IP_PACKET_SIZE) {
143 LOG(LS_WARNING) << "Media packet " << media_packet->length << " bytes "
144 << "with overhead is larger than " << IP_PACKET_SIZE;
145 }
146 }
147
148 int num_fec_packets =
149 GetNumberOfFecPackets(num_media_packets, protection_factor);
150 if (num_fec_packets == 0) {
151 return 0;
152 }
153
154 // Prepare FEC packets by setting them to 0.
155 for (int i = 0; i < num_fec_packets; ++i) {
156 memset(generated_fec_packets_[i].data, 0, IP_PACKET_SIZE);
157 generated_fec_packets_[i].length = 0; // Use this as a marker for untouched
158 // packets.
159 fec_packet_list->push_back(&generated_fec_packets_[i]);
160 }
161
162 const internal::PacketMaskTable mask_table(fec_mask_type, num_media_packets);
163
164 // -- Generate packet masks --
165 // Always allocate space for a large mask.
166 rtc::scoped_ptr<uint8_t[]> packet_mask(
167 new uint8_t[num_fec_packets * kMaskSizeLBitSet]);
168 memset(packet_mask.get(), 0, num_fec_packets * num_mask_bytes);
169 internal::GeneratePacketMasks(num_media_packets, num_fec_packets,
170 num_important_packets, use_unequal_protection,
171 mask_table, packet_mask.get());
172
173 int num_mask_bits = InsertZerosInBitMasks(
174 media_packet_list, packet_mask.get(), num_mask_bytes, num_fec_packets);
175
176 if (num_mask_bits < 0) {
177 return -1;
178 }
179 l_bit = (num_mask_bits > 8 * kMaskSizeLBitClear);
180 if (l_bit) {
181 num_mask_bytes = kMaskSizeLBitSet;
182 }
183
184 GenerateFecBitStrings(media_packet_list, packet_mask.get(), num_fec_packets,
185 l_bit);
186 GenerateFecUlpHeaders(media_packet_list, packet_mask.get(), l_bit,
187 num_fec_packets);
188
189 return 0;
190 }
191
GetNumberOfFecPackets(int num_media_packets,int protection_factor)192 int ForwardErrorCorrection::GetNumberOfFecPackets(int num_media_packets,
193 int protection_factor) {
194 // Result in Q0 with an unsigned round.
195 int num_fec_packets = (num_media_packets * protection_factor + (1 << 7)) >> 8;
196 // Generate at least one FEC packet if we need protection.
197 if (protection_factor > 0 && num_fec_packets == 0) {
198 num_fec_packets = 1;
199 }
200 assert(num_fec_packets <= num_media_packets);
201 return num_fec_packets;
202 }
203
GenerateFecBitStrings(const PacketList & media_packet_list,uint8_t * packet_mask,int num_fec_packets,bool l_bit)204 void ForwardErrorCorrection::GenerateFecBitStrings(
205 const PacketList& media_packet_list,
206 uint8_t* packet_mask,
207 int num_fec_packets,
208 bool l_bit) {
209 if (media_packet_list.empty()) {
210 return;
211 }
212 uint8_t media_payload_length[2];
213 const int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;
214 const uint16_t ulp_header_size =
215 l_bit ? kUlpHeaderSizeLBitSet : kUlpHeaderSizeLBitClear;
216 const uint16_t fec_rtp_offset =
217 kFecHeaderSize + ulp_header_size - kRtpHeaderSize;
218
219 for (int i = 0; i < num_fec_packets; ++i) {
220 Packet* const fec_packet = &generated_fec_packets_[i];
221 PacketList::const_iterator media_list_it = media_packet_list.begin();
222 uint32_t pkt_mask_idx = i * num_mask_bytes;
223 uint32_t media_pkt_idx = 0;
224 uint16_t fec_packet_length = 0;
225 uint16_t prev_seq_num = ParseSequenceNumber((*media_list_it)->data);
226 while (media_list_it != media_packet_list.end()) {
227 // Each FEC packet has a multiple byte mask. Determine if this media
228 // packet should be included in FEC packet i.
229 if (packet_mask[pkt_mask_idx] & (1 << (7 - media_pkt_idx))) {
230 Packet* media_packet = *media_list_it;
231
232 // Assign network-ordered media payload length.
233 ByteWriter<uint16_t>::WriteBigEndian(
234 media_payload_length, media_packet->length - kRtpHeaderSize);
235
236 fec_packet_length = media_packet->length + fec_rtp_offset;
237 // On the first protected packet, we don't need to XOR.
238 if (fec_packet->length == 0) {
239 // Copy the first 2 bytes of the RTP header.
240 memcpy(fec_packet->data, media_packet->data, 2);
241 // Copy the 5th to 8th bytes of the RTP header.
242 memcpy(&fec_packet->data[4], &media_packet->data[4], 4);
243 // Copy network-ordered payload size.
244 memcpy(&fec_packet->data[8], media_payload_length, 2);
245
246 // Copy RTP payload, leaving room for the ULP header.
247 memcpy(&fec_packet->data[kFecHeaderSize + ulp_header_size],
248 &media_packet->data[kRtpHeaderSize],
249 media_packet->length - kRtpHeaderSize);
250 } else {
251 // XOR with the first 2 bytes of the RTP header.
252 fec_packet->data[0] ^= media_packet->data[0];
253 fec_packet->data[1] ^= media_packet->data[1];
254
255 // XOR with the 5th to 8th bytes of the RTP header.
256 for (uint32_t j = 4; j < 8; ++j) {
257 fec_packet->data[j] ^= media_packet->data[j];
258 }
259
260 // XOR with the network-ordered payload size.
261 fec_packet->data[8] ^= media_payload_length[0];
262 fec_packet->data[9] ^= media_payload_length[1];
263
264 // XOR with RTP payload, leaving room for the ULP header.
265 for (int32_t j = kFecHeaderSize + ulp_header_size;
266 j < fec_packet_length; j++) {
267 fec_packet->data[j] ^= media_packet->data[j - fec_rtp_offset];
268 }
269 }
270 if (fec_packet_length > fec_packet->length) {
271 fec_packet->length = fec_packet_length;
272 }
273 }
274 media_list_it++;
275 if (media_list_it != media_packet_list.end()) {
276 uint16_t seq_num = ParseSequenceNumber((*media_list_it)->data);
277 media_pkt_idx += static_cast<uint16_t>(seq_num - prev_seq_num);
278 prev_seq_num = seq_num;
279 }
280 pkt_mask_idx += media_pkt_idx / 8;
281 media_pkt_idx %= 8;
282 }
283 RTC_DCHECK_GT(fec_packet->length, 0u)
284 << "Packet mask is wrong or poorly designed.";
285 }
286 }
287
InsertZerosInBitMasks(const PacketList & media_packets,uint8_t * packet_mask,int num_mask_bytes,int num_fec_packets)288 int ForwardErrorCorrection::InsertZerosInBitMasks(
289 const PacketList& media_packets,
290 uint8_t* packet_mask,
291 int num_mask_bytes,
292 int num_fec_packets) {
293 uint8_t* new_mask = NULL;
294 if (media_packets.size() <= 1) {
295 return media_packets.size();
296 }
297 int last_seq_num = ParseSequenceNumber(media_packets.back()->data);
298 int first_seq_num = ParseSequenceNumber(media_packets.front()->data);
299 int total_missing_seq_nums =
300 static_cast<uint16_t>(last_seq_num - first_seq_num) -
301 media_packets.size() + 1;
302 if (total_missing_seq_nums == 0) {
303 // All sequence numbers are covered by the packet mask. No zero insertion
304 // required.
305 return media_packets.size();
306 }
307 // We can only protect 8 * kMaskSizeLBitSet packets.
308 if (total_missing_seq_nums + media_packets.size() > 8 * kMaskSizeLBitSet)
309 return -1;
310 // Allocate the new mask.
311 int new_mask_bytes = kMaskSizeLBitClear;
312 if (media_packets.size() + total_missing_seq_nums > 8 * kMaskSizeLBitClear) {
313 new_mask_bytes = kMaskSizeLBitSet;
314 }
315 new_mask = new uint8_t[num_fec_packets * kMaskSizeLBitSet];
316 memset(new_mask, 0, num_fec_packets * kMaskSizeLBitSet);
317
318 PacketList::const_iterator it = media_packets.begin();
319 uint16_t prev_seq_num = first_seq_num;
320 ++it;
321
322 // Insert the first column.
323 CopyColumn(new_mask, new_mask_bytes, packet_mask, num_mask_bytes,
324 num_fec_packets, 0, 0);
325 int new_bit_index = 1;
326 int old_bit_index = 1;
327 // Insert zeros in the bit mask for every hole in the sequence.
328 for (; it != media_packets.end(); ++it) {
329 if (new_bit_index == 8 * kMaskSizeLBitSet) {
330 // We can only cover up to 48 packets.
331 break;
332 }
333 uint16_t seq_num = ParseSequenceNumber((*it)->data);
334 const int zeros_to_insert =
335 static_cast<uint16_t>(seq_num - prev_seq_num - 1);
336 if (zeros_to_insert > 0) {
337 InsertZeroColumns(zeros_to_insert, new_mask, new_mask_bytes,
338 num_fec_packets, new_bit_index);
339 }
340 new_bit_index += zeros_to_insert;
341 CopyColumn(new_mask, new_mask_bytes, packet_mask, num_mask_bytes,
342 num_fec_packets, new_bit_index, old_bit_index);
343 ++new_bit_index;
344 ++old_bit_index;
345 prev_seq_num = seq_num;
346 }
347 if (new_bit_index % 8 != 0) {
348 // We didn't fill the last byte. Shift bits to correct position.
349 for (uint16_t row = 0; row < num_fec_packets; ++row) {
350 int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
351 new_mask[new_byte_index] <<= (7 - (new_bit_index % 8));
352 }
353 }
354 // Replace the old mask with the new.
355 memcpy(packet_mask, new_mask, kMaskSizeLBitSet * num_fec_packets);
356 delete[] new_mask;
357 return new_bit_index;
358 }
359
InsertZeroColumns(int num_zeros,uint8_t * new_mask,int new_mask_bytes,int num_fec_packets,int new_bit_index)360 void ForwardErrorCorrection::InsertZeroColumns(int num_zeros,
361 uint8_t* new_mask,
362 int new_mask_bytes,
363 int num_fec_packets,
364 int new_bit_index) {
365 for (uint16_t row = 0; row < num_fec_packets; ++row) {
366 const int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
367 const int max_shifts = (7 - (new_bit_index % 8));
368 new_mask[new_byte_index] <<= std::min(num_zeros, max_shifts);
369 }
370 }
371
CopyColumn(uint8_t * new_mask,int new_mask_bytes,uint8_t * old_mask,int old_mask_bytes,int num_fec_packets,int new_bit_index,int old_bit_index)372 void ForwardErrorCorrection::CopyColumn(uint8_t* new_mask,
373 int new_mask_bytes,
374 uint8_t* old_mask,
375 int old_mask_bytes,
376 int num_fec_packets,
377 int new_bit_index,
378 int old_bit_index) {
379 // Copy column from the old mask to the beginning of the new mask and shift it
380 // out from the old mask.
381 for (uint16_t row = 0; row < num_fec_packets; ++row) {
382 int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
383 int old_byte_index = row * old_mask_bytes + old_bit_index / 8;
384 new_mask[new_byte_index] |= ((old_mask[old_byte_index] & 0x80) >> 7);
385 if (new_bit_index % 8 != 7) {
386 new_mask[new_byte_index] <<= 1;
387 }
388 old_mask[old_byte_index] <<= 1;
389 }
390 }
391
GenerateFecUlpHeaders(const PacketList & media_packet_list,uint8_t * packet_mask,bool l_bit,int num_fec_packets)392 void ForwardErrorCorrection::GenerateFecUlpHeaders(
393 const PacketList& media_packet_list,
394 uint8_t* packet_mask,
395 bool l_bit,
396 int num_fec_packets) {
397 // -- Generate FEC and ULP headers --
398 //
399 // FEC Header, 10 bytes
400 // 0 1 2 3
401 // 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
402 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
403 // |E|L|P|X| CC |M| PT recovery | SN base |
404 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
405 // | TS recovery |
406 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
407 // | length recovery |
408 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
409 //
410 // ULP Header, 4 bytes (for L = 0)
411 // 0 1 2 3
412 // 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
413 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
414 // | Protection Length | mask |
415 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
416 // | mask cont. (present only when L = 1) |
417 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
418 PacketList::const_iterator media_list_it = media_packet_list.begin();
419 Packet* media_packet = *media_list_it;
420 assert(media_packet != NULL);
421 int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;
422 const uint16_t ulp_header_size =
423 l_bit ? kUlpHeaderSizeLBitSet : kUlpHeaderSizeLBitClear;
424
425 for (int i = 0; i < num_fec_packets; ++i) {
426 Packet* const fec_packet = &generated_fec_packets_[i];
427 // -- FEC header --
428 fec_packet->data[0] &= 0x7f; // Set E to zero.
429 if (l_bit == 0) {
430 fec_packet->data[0] &= 0xbf; // Clear the L bit.
431 } else {
432 fec_packet->data[0] |= 0x40; // Set the L bit.
433 }
434 // Two byte sequence number from first RTP packet to SN base.
435 // We use the same sequence number base for every FEC packet,
436 // but that's not required in general.
437 memcpy(&fec_packet->data[2], &media_packet->data[2], 2);
438
439 // -- ULP header --
440 // Copy the payload size to the protection length field.
441 // (We protect the entire packet.)
442 ByteWriter<uint16_t>::WriteBigEndian(
443 &fec_packet->data[10],
444 fec_packet->length - kFecHeaderSize - ulp_header_size);
445
446 // Copy the packet mask.
447 memcpy(&fec_packet->data[12], &packet_mask[i * num_mask_bytes],
448 num_mask_bytes);
449 }
450 }
451
ResetState(RecoveredPacketList * recovered_packet_list)452 void ForwardErrorCorrection::ResetState(
453 RecoveredPacketList* recovered_packet_list) {
454 fec_packet_received_ = false;
455
456 // Free the memory for any existing recovered packets, if the user hasn't.
457 while (!recovered_packet_list->empty()) {
458 delete recovered_packet_list->front();
459 recovered_packet_list->pop_front();
460 }
461 assert(recovered_packet_list->empty());
462
463 // Free the FEC packet list.
464 while (!fec_packet_list_.empty()) {
465 FecPacketList::iterator fec_packet_list_it = fec_packet_list_.begin();
466 FecPacket* fec_packet = *fec_packet_list_it;
467 ProtectedPacketList::iterator protected_packet_list_it;
468 protected_packet_list_it = fec_packet->protected_pkt_list.begin();
469 while (protected_packet_list_it != fec_packet->protected_pkt_list.end()) {
470 delete *protected_packet_list_it;
471 protected_packet_list_it =
472 fec_packet->protected_pkt_list.erase(protected_packet_list_it);
473 }
474 assert(fec_packet->protected_pkt_list.empty());
475 delete fec_packet;
476 fec_packet_list_.pop_front();
477 }
478 assert(fec_packet_list_.empty());
479 }
480
InsertMediaPacket(ReceivedPacket * rx_packet,RecoveredPacketList * recovered_packet_list)481 void ForwardErrorCorrection::InsertMediaPacket(
482 ReceivedPacket* rx_packet,
483 RecoveredPacketList* recovered_packet_list) {
484 RecoveredPacketList::iterator recovered_packet_list_it =
485 recovered_packet_list->begin();
486
487 // Search for duplicate packets.
488 while (recovered_packet_list_it != recovered_packet_list->end()) {
489 if (rx_packet->seq_num == (*recovered_packet_list_it)->seq_num) {
490 // Duplicate packet, no need to add to list.
491 // Delete duplicate media packet data.
492 rx_packet->pkt = NULL;
493 return;
494 }
495 recovered_packet_list_it++;
496 }
497 RecoveredPacket* recoverd_packet_to_insert = new RecoveredPacket;
498 recoverd_packet_to_insert->was_recovered = false;
499 // Inserted Media packet is already sent to VCM.
500 recoverd_packet_to_insert->returned = true;
501 recoverd_packet_to_insert->seq_num = rx_packet->seq_num;
502 recoverd_packet_to_insert->pkt = rx_packet->pkt;
503 recoverd_packet_to_insert->pkt->length = rx_packet->pkt->length;
504
505 // TODO(holmer): Consider replacing this with a binary search for the right
506 // position, and then just insert the new packet. Would get rid of the sort.
507 recovered_packet_list->push_back(recoverd_packet_to_insert);
508 recovered_packet_list->sort(SortablePacket::LessThan);
509 UpdateCoveringFECPackets(recoverd_packet_to_insert);
510 }
511
UpdateCoveringFECPackets(RecoveredPacket * packet)512 void ForwardErrorCorrection::UpdateCoveringFECPackets(RecoveredPacket* packet) {
513 for (FecPacketList::iterator it = fec_packet_list_.begin();
514 it != fec_packet_list_.end(); ++it) {
515 // Is this FEC packet protecting the media packet |packet|?
516 ProtectedPacketList::iterator protected_it = std::lower_bound(
517 (*it)->protected_pkt_list.begin(), (*it)->protected_pkt_list.end(),
518 packet, SortablePacket::LessThan);
519 if (protected_it != (*it)->protected_pkt_list.end() &&
520 (*protected_it)->seq_num == packet->seq_num) {
521 // Found an FEC packet which is protecting |packet|.
522 (*protected_it)->pkt = packet->pkt;
523 }
524 }
525 }
526
InsertFECPacket(ReceivedPacket * rx_packet,const RecoveredPacketList * recovered_packet_list)527 void ForwardErrorCorrection::InsertFECPacket(
528 ReceivedPacket* rx_packet,
529 const RecoveredPacketList* recovered_packet_list) {
530 fec_packet_received_ = true;
531
532 // Check for duplicate.
533 FecPacketList::iterator fec_packet_list_it = fec_packet_list_.begin();
534 while (fec_packet_list_it != fec_packet_list_.end()) {
535 if (rx_packet->seq_num == (*fec_packet_list_it)->seq_num) {
536 // Delete duplicate FEC packet data.
537 rx_packet->pkt = NULL;
538 return;
539 }
540 fec_packet_list_it++;
541 }
542 FecPacket* fec_packet = new FecPacket;
543 fec_packet->pkt = rx_packet->pkt;
544 fec_packet->seq_num = rx_packet->seq_num;
545 fec_packet->ssrc = rx_packet->ssrc;
546
547 const uint16_t seq_num_base =
548 ByteReader<uint16_t>::ReadBigEndian(&fec_packet->pkt->data[2]);
549 const uint16_t maskSizeBytes = (fec_packet->pkt->data[0] & 0x40)
550 ? kMaskSizeLBitSet
551 : kMaskSizeLBitClear; // L bit set?
552
553 for (uint16_t byte_idx = 0; byte_idx < maskSizeBytes; ++byte_idx) {
554 uint8_t packet_mask = fec_packet->pkt->data[12 + byte_idx];
555 for (uint16_t bit_idx = 0; bit_idx < 8; ++bit_idx) {
556 if (packet_mask & (1 << (7 - bit_idx))) {
557 ProtectedPacket* protected_packet = new ProtectedPacket;
558 fec_packet->protected_pkt_list.push_back(protected_packet);
559 // This wraps naturally with the sequence number.
560 protected_packet->seq_num =
561 static_cast<uint16_t>(seq_num_base + (byte_idx << 3) + bit_idx);
562 protected_packet->pkt = NULL;
563 }
564 }
565 }
566 if (fec_packet->protected_pkt_list.empty()) {
567 // All-zero packet mask; we can discard this FEC packet.
568 LOG(LS_WARNING) << "FEC packet has an all-zero packet mask.";
569 delete fec_packet;
570 } else {
571 AssignRecoveredPackets(fec_packet, recovered_packet_list);
572 // TODO(holmer): Consider replacing this with a binary search for the right
573 // position, and then just insert the new packet. Would get rid of the sort.
574 fec_packet_list_.push_back(fec_packet);
575 fec_packet_list_.sort(SortablePacket::LessThan);
576 if (fec_packet_list_.size() > kMaxFecPackets) {
577 DiscardFECPacket(fec_packet_list_.front());
578 fec_packet_list_.pop_front();
579 }
580 assert(fec_packet_list_.size() <= kMaxFecPackets);
581 }
582 }
583
AssignRecoveredPackets(FecPacket * fec_packet,const RecoveredPacketList * recovered_packets)584 void ForwardErrorCorrection::AssignRecoveredPackets(
585 FecPacket* fec_packet,
586 const RecoveredPacketList* recovered_packets) {
587 // Search for missing packets which have arrived or have been recovered by
588 // another FEC packet.
589 ProtectedPacketList* not_recovered = &fec_packet->protected_pkt_list;
590 RecoveredPacketList already_recovered;
591 std::set_intersection(
592 recovered_packets->begin(), recovered_packets->end(),
593 not_recovered->begin(), not_recovered->end(),
594 std::inserter(already_recovered, already_recovered.end()),
595 SortablePacket::LessThan);
596 // Set the FEC pointers to all recovered packets so that we don't have to
597 // search for them when we are doing recovery.
598 ProtectedPacketList::iterator not_recovered_it = not_recovered->begin();
599 for (RecoveredPacketList::iterator it = already_recovered.begin();
600 it != already_recovered.end(); ++it) {
601 // Search for the next recovered packet in |not_recovered|.
602 while ((*not_recovered_it)->seq_num != (*it)->seq_num)
603 ++not_recovered_it;
604 (*not_recovered_it)->pkt = (*it)->pkt;
605 }
606 }
607
InsertPackets(ReceivedPacketList * received_packet_list,RecoveredPacketList * recovered_packet_list)608 void ForwardErrorCorrection::InsertPackets(
609 ReceivedPacketList* received_packet_list,
610 RecoveredPacketList* recovered_packet_list) {
611 while (!received_packet_list->empty()) {
612 ReceivedPacket* rx_packet = received_packet_list->front();
613
614 // Check for discarding oldest FEC packet, to avoid wrong FEC decoding from
615 // sequence number wrap-around. Detection of old FEC packet is based on
616 // sequence number difference of received packet and oldest packet in FEC
617 // packet list.
618 // TODO(marpan/holmer): We should be able to improve detection/discarding of
619 // old FEC packets based on timestamp information or better sequence number
620 // thresholding (e.g., to distinguish between wrap-around and reordering).
621 if (!fec_packet_list_.empty()) {
622 uint16_t seq_num_diff =
623 abs(static_cast<int>(rx_packet->seq_num) -
624 static_cast<int>(fec_packet_list_.front()->seq_num));
625 if (seq_num_diff > 0x3fff) {
626 DiscardFECPacket(fec_packet_list_.front());
627 fec_packet_list_.pop_front();
628 }
629 }
630
631 if (rx_packet->is_fec) {
632 InsertFECPacket(rx_packet, recovered_packet_list);
633 } else {
634 // Insert packet at the end of |recoveredPacketList|.
635 InsertMediaPacket(rx_packet, recovered_packet_list);
636 }
637 // Delete the received packet "wrapper", but not the packet data.
638 delete rx_packet;
639 received_packet_list->pop_front();
640 }
641 assert(received_packet_list->empty());
642 DiscardOldPackets(recovered_packet_list);
643 }
644
InitRecovery(const FecPacket * fec_packet,RecoveredPacket * recovered)645 bool ForwardErrorCorrection::InitRecovery(const FecPacket* fec_packet,
646 RecoveredPacket* recovered) {
647 // This is the first packet which we try to recover with.
648 const uint16_t ulp_header_size = fec_packet->pkt->data[0] & 0x40
649 ? kUlpHeaderSizeLBitSet
650 : kUlpHeaderSizeLBitClear; // L bit set?
651 if (fec_packet->pkt->length <
652 static_cast<size_t>(kFecHeaderSize + ulp_header_size)) {
653 LOG(LS_WARNING)
654 << "Truncated FEC packet doesn't contain room for ULP header.";
655 return false;
656 }
657 recovered->pkt = new Packet;
658 memset(recovered->pkt->data, 0, IP_PACKET_SIZE);
659 recovered->returned = false;
660 recovered->was_recovered = true;
661 uint16_t protection_length =
662 ByteReader<uint16_t>::ReadBigEndian(&fec_packet->pkt->data[10]);
663 if (protection_length >
664 std::min(
665 sizeof(recovered->pkt->data) - kRtpHeaderSize,
666 sizeof(fec_packet->pkt->data) - kFecHeaderSize - ulp_header_size)) {
667 LOG(LS_WARNING) << "Incorrect FEC protection length, dropping.";
668 return false;
669 }
670 // Copy FEC payload, skipping the ULP header.
671 memcpy(&recovered->pkt->data[kRtpHeaderSize],
672 &fec_packet->pkt->data[kFecHeaderSize + ulp_header_size],
673 protection_length);
674 // Copy the length recovery field.
675 memcpy(recovered->length_recovery, &fec_packet->pkt->data[8], 2);
676 // Copy the first 2 bytes of the FEC header.
677 memcpy(recovered->pkt->data, fec_packet->pkt->data, 2);
678 // Copy the 5th to 8th bytes of the FEC header.
679 memcpy(&recovered->pkt->data[4], &fec_packet->pkt->data[4], 4);
680 // Set the SSRC field.
681 ByteWriter<uint32_t>::WriteBigEndian(&recovered->pkt->data[8],
682 fec_packet->ssrc);
683 return true;
684 }
685
FinishRecovery(RecoveredPacket * recovered)686 bool ForwardErrorCorrection::FinishRecovery(RecoveredPacket* recovered) {
687 // Set the RTP version to 2.
688 recovered->pkt->data[0] |= 0x80; // Set the 1st bit.
689 recovered->pkt->data[0] &= 0xbf; // Clear the 2nd bit.
690
691 // Set the SN field.
692 ByteWriter<uint16_t>::WriteBigEndian(&recovered->pkt->data[2],
693 recovered->seq_num);
694 // Recover the packet length.
695 recovered->pkt->length =
696 ByteReader<uint16_t>::ReadBigEndian(recovered->length_recovery) +
697 kRtpHeaderSize;
698 if (recovered->pkt->length > sizeof(recovered->pkt->data) - kRtpHeaderSize)
699 return false;
700
701 return true;
702 }
703
XorPackets(const Packet * src_packet,RecoveredPacket * dst_packet)704 void ForwardErrorCorrection::XorPackets(const Packet* src_packet,
705 RecoveredPacket* dst_packet) {
706 // XOR with the first 2 bytes of the RTP header.
707 for (uint32_t i = 0; i < 2; ++i) {
708 dst_packet->pkt->data[i] ^= src_packet->data[i];
709 }
710 // XOR with the 5th to 8th bytes of the RTP header.
711 for (uint32_t i = 4; i < 8; ++i) {
712 dst_packet->pkt->data[i] ^= src_packet->data[i];
713 }
714 // XOR with the network-ordered payload size.
715 uint8_t media_payload_length[2];
716 ByteWriter<uint16_t>::WriteBigEndian(media_payload_length,
717 src_packet->length - kRtpHeaderSize);
718 dst_packet->length_recovery[0] ^= media_payload_length[0];
719 dst_packet->length_recovery[1] ^= media_payload_length[1];
720
721 // XOR with RTP payload.
722 // TODO(marpan/ajm): Are we doing more XORs than required here?
723 for (size_t i = kRtpHeaderSize; i < src_packet->length; ++i) {
724 dst_packet->pkt->data[i] ^= src_packet->data[i];
725 }
726 }
727
RecoverPacket(const FecPacket * fec_packet,RecoveredPacket * rec_packet_to_insert)728 bool ForwardErrorCorrection::RecoverPacket(
729 const FecPacket* fec_packet,
730 RecoveredPacket* rec_packet_to_insert) {
731 if (!InitRecovery(fec_packet, rec_packet_to_insert))
732 return false;
733 ProtectedPacketList::const_iterator protected_it =
734 fec_packet->protected_pkt_list.begin();
735 while (protected_it != fec_packet->protected_pkt_list.end()) {
736 if ((*protected_it)->pkt == NULL) {
737 // This is the packet we're recovering.
738 rec_packet_to_insert->seq_num = (*protected_it)->seq_num;
739 } else {
740 XorPackets((*protected_it)->pkt, rec_packet_to_insert);
741 }
742 ++protected_it;
743 }
744 if (!FinishRecovery(rec_packet_to_insert))
745 return false;
746 return true;
747 }
748
AttemptRecover(RecoveredPacketList * recovered_packet_list)749 void ForwardErrorCorrection::AttemptRecover(
750 RecoveredPacketList* recovered_packet_list) {
751 FecPacketList::iterator fec_packet_list_it = fec_packet_list_.begin();
752 while (fec_packet_list_it != fec_packet_list_.end()) {
753 // Search for each FEC packet's protected media packets.
754 int packets_missing = NumCoveredPacketsMissing(*fec_packet_list_it);
755
756 // We can only recover one packet with an FEC packet.
757 if (packets_missing == 1) {
758 // Recovery possible.
759 RecoveredPacket* packet_to_insert = new RecoveredPacket;
760 packet_to_insert->pkt = NULL;
761 if (!RecoverPacket(*fec_packet_list_it, packet_to_insert)) {
762 // Can't recover using this packet, drop it.
763 DiscardFECPacket(*fec_packet_list_it);
764 fec_packet_list_it = fec_packet_list_.erase(fec_packet_list_it);
765 delete packet_to_insert;
766 continue;
767 }
768
769 // Add recovered packet to the list of recovered packets and update any
770 // FEC packets covering this packet with a pointer to the data.
771 // TODO(holmer): Consider replacing this with a binary search for the
772 // right position, and then just insert the new packet. Would get rid of
773 // the sort.
774 recovered_packet_list->push_back(packet_to_insert);
775 recovered_packet_list->sort(SortablePacket::LessThan);
776 UpdateCoveringFECPackets(packet_to_insert);
777 DiscardOldPackets(recovered_packet_list);
778 DiscardFECPacket(*fec_packet_list_it);
779 fec_packet_list_it = fec_packet_list_.erase(fec_packet_list_it);
780
781 // A packet has been recovered. We need to check the FEC list again, as
782 // this may allow additional packets to be recovered.
783 // Restart for first FEC packet.
784 fec_packet_list_it = fec_packet_list_.begin();
785 } else if (packets_missing == 0) {
786 // Either all protected packets arrived or have been recovered. We can
787 // discard this FEC packet.
788 DiscardFECPacket(*fec_packet_list_it);
789 fec_packet_list_it = fec_packet_list_.erase(fec_packet_list_it);
790 } else {
791 fec_packet_list_it++;
792 }
793 }
794 }
795
NumCoveredPacketsMissing(const FecPacket * fec_packet)796 int ForwardErrorCorrection::NumCoveredPacketsMissing(
797 const FecPacket* fec_packet) {
798 int packets_missing = 0;
799 ProtectedPacketList::const_iterator it =
800 fec_packet->protected_pkt_list.begin();
801 for (; it != fec_packet->protected_pkt_list.end(); ++it) {
802 if ((*it)->pkt == NULL) {
803 ++packets_missing;
804 if (packets_missing > 1) {
805 break; // We can't recover more than one packet.
806 }
807 }
808 }
809 return packets_missing;
810 }
811
DiscardFECPacket(FecPacket * fec_packet)812 void ForwardErrorCorrection::DiscardFECPacket(FecPacket* fec_packet) {
813 while (!fec_packet->protected_pkt_list.empty()) {
814 delete fec_packet->protected_pkt_list.front();
815 fec_packet->protected_pkt_list.pop_front();
816 }
817 assert(fec_packet->protected_pkt_list.empty());
818 delete fec_packet;
819 }
820
DiscardOldPackets(RecoveredPacketList * recovered_packet_list)821 void ForwardErrorCorrection::DiscardOldPackets(
822 RecoveredPacketList* recovered_packet_list) {
823 while (recovered_packet_list->size() > kMaxMediaPackets) {
824 ForwardErrorCorrection::RecoveredPacket* packet =
825 recovered_packet_list->front();
826 delete packet;
827 recovered_packet_list->pop_front();
828 }
829 assert(recovered_packet_list->size() <= kMaxMediaPackets);
830 }
831
ParseSequenceNumber(uint8_t * packet)832 uint16_t ForwardErrorCorrection::ParseSequenceNumber(uint8_t* packet) {
833 return (packet[2] << 8) + packet[3];
834 }
835
DecodeFEC(ReceivedPacketList * received_packet_list,RecoveredPacketList * recovered_packet_list)836 int32_t ForwardErrorCorrection::DecodeFEC(
837 ReceivedPacketList* received_packet_list,
838 RecoveredPacketList* recovered_packet_list) {
839 // TODO(marpan/ajm): can we check for multiple ULP headers, and return an
840 // error?
841 if (recovered_packet_list->size() == kMaxMediaPackets) {
842 const unsigned int seq_num_diff =
843 abs(static_cast<int>(received_packet_list->front()->seq_num) -
844 static_cast<int>(recovered_packet_list->back()->seq_num));
845 if (seq_num_diff > kMaxMediaPackets) {
846 // A big gap in sequence numbers. The old recovered packets
847 // are now useless, so it's safe to do a reset.
848 ResetState(recovered_packet_list);
849 }
850 }
851 InsertPackets(received_packet_list, recovered_packet_list);
852 AttemptRecover(recovered_packet_list);
853 return 0;
854 }
855
PacketOverhead()856 size_t ForwardErrorCorrection::PacketOverhead() {
857 return kFecHeaderSize + kUlpHeaderSizeLBitSet;
858 }
859 } // namespace webrtc
860