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 41 int32_t ForwardErrorCorrection::Packet::AddRef() { 42 return ++ref_count_; 43 } 44 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 74 bool ForwardErrorCorrection::SortablePacket::LessThan( 75 const SortablePacket* first, 76 const SortablePacket* second) { 77 return IsNewerSequenceNumber(second->seq_num, first->seq_num); 78 } 79 80 ForwardErrorCorrection::ReceivedPacket::ReceivedPacket() {} 81 ForwardErrorCorrection::ReceivedPacket::~ReceivedPacket() {} 82 83 ForwardErrorCorrection::RecoveredPacket::RecoveredPacket() {} 84 ForwardErrorCorrection::RecoveredPacket::~RecoveredPacket() {} 85 86 ForwardErrorCorrection::ForwardErrorCorrection() 87 : generated_fec_packets_(kMaxMediaPackets), fec_packet_received_(false) {} 88 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 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 832 uint16_t ForwardErrorCorrection::ParseSequenceNumber(uint8_t* packet) { 833 return (packet[2] << 8) + packet[3]; 834 } 835 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 856 size_t ForwardErrorCorrection::PacketOverhead() { 857 return kFecHeaderSize + kUlpHeaderSizeLBitSet; 858 } 859 } // namespace webrtc 860
