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