src/third_party/webrtc/modules/rtp_rtcp/source/forward_error_correction.cc

   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         ModuleRTPUtility::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     ModuleRTPUtility::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       ModuleRTPUtility::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     if (rx_packet->is_fec) {
 607       InsertFECPacket(rx_packet, recovered_packet_list);
 608     } else {
 609       // Insert packet at the end of |recoveredPacketList|.
 610       InsertMediaPacket(rx_packet, recovered_packet_list);
 611     }
 612     // Delete the received packet "wrapper", but not the packet data.
 613     delete rx_packet;
 614     received_packet_list->pop_front();
 615   }
 616   assert(received_packet_list->empty());
 617   DiscardOldPackets(recovered_packet_list);
 618 }
 619
 620 void ForwardErrorCorrection::InitRecovery(const FecPacket* fec_packet,
 621                                           RecoveredPacket* recovered) {
 622   // This is the first packet which we try to recover with.
 623   const uint16_t ulp_header_size =
 624       fec_packet->pkt->data[0] & 0x40 ? kUlpHeaderSizeLBitSet
 625                                       : kUlpHeaderSizeLBitClear;  // L bit set?
 626   recovered->pkt = new Packet;
 627   memset(recovered->pkt->data, 0, IP_PACKET_SIZE);
 628   recovered->returned = false;
 629   recovered->was_recovered = true;
 630   uint8_t protection_length[2];
 631   // Copy the protection length from the ULP header.
 632   memcpy(protection_length, &fec_packet->pkt->data[10], 2);
 633   // Copy FEC payload, skipping the ULP header.
 634   memcpy(&recovered->pkt->data[kRtpHeaderSize],
 635          &fec_packet->pkt->data[kFecHeaderSize + ulp_header_size],
 636          ModuleRTPUtility::BufferToUWord16(protection_length));
 637   // Copy the length recovery field.
 638   memcpy(recovered->length_recovery, &fec_packet->pkt->data[8], 2);
 639   // Copy the first 2 bytes of the FEC header.
 640   memcpy(recovered->pkt->data, fec_packet->pkt->data, 2);
 641   // Copy the 5th to 8th bytes of the FEC header.
 642   memcpy(&recovered->pkt->data[4], &fec_packet->pkt->data[4], 4);
 643   // Set the SSRC field.
 644   ModuleRTPUtility::AssignUWord32ToBuffer(&recovered->pkt->data[8],
 645                                           fec_packet->ssrc);
 646 }
 647
 648 void ForwardErrorCorrection::FinishRecovery(RecoveredPacket* recovered) {
 649   // Set the RTP version to 2.
 650   recovered->pkt->data[0] |= 0x80;  // Set the 1st bit.
 651   recovered->pkt->data[0] &= 0xbf;  // Clear the 2nd bit.
 652
 653   // Set the SN field.
 654   ModuleRTPUtility::AssignUWord16ToBuffer(&recovered->pkt->data[2],
 655                                           recovered->seq_num);
 656   // Recover the packet length.
 657   recovered->pkt->length =
 658       ModuleRTPUtility::BufferToUWord16(recovered->length_recovery) +
 659       kRtpHeaderSize;
 660 }
 661
 662 void ForwardErrorCorrection::XorPackets(const Packet* src_packet,
 663                                         RecoveredPacket* dst_packet) {
 664   // XOR with the first 2 bytes of the RTP header.
 665   for (uint32_t i = 0; i < 2; ++i) {
 666     dst_packet->pkt->data[i] ^= src_packet->data[i];
 667   }
 668   // XOR with the 5th to 8th bytes of the RTP header.
 669   for (uint32_t i = 4; i < 8; ++i) {
 670     dst_packet->pkt->data[i] ^= src_packet->data[i];
 671   }
 672   // XOR with the network-ordered payload size.
 673   uint8_t media_payload_length[2];
 674   ModuleRTPUtility::AssignUWord16ToBuffer(media_payload_length,
 675                                           src_packet->length - kRtpHeaderSize);
 676   dst_packet->length_recovery[0] ^= media_payload_length[0];
 677   dst_packet->length_recovery[1] ^= media_payload_length[1];
 678
 679   // XOR with RTP payload.
 680   // TODO(marpan/ajm): Are we doing more XORs than required here?
 681   for (int32_t i = kRtpHeaderSize; i < src_packet->length; ++i) {
 682     dst_packet->pkt->data[i] ^= src_packet->data[i];
 683   }
 684 }
 685
 686 void ForwardErrorCorrection::RecoverPacket(
 687     const FecPacket* fec_packet, RecoveredPacket* rec_packet_to_insert) {
 688   InitRecovery(fec_packet, rec_packet_to_insert);
 689   ProtectedPacketList::const_iterator protected_it =
 690       fec_packet->protected_pkt_list.begin();
 691   while (protected_it != fec_packet->protected_pkt_list.end()) {
 692     if ((*protected_it)->pkt == NULL) {
 693       // This is the packet we're recovering.
 694       rec_packet_to_insert->seq_num = (*protected_it)->seq_num;
 695     } else {
 696       XorPackets((*protected_it)->pkt, rec_packet_to_insert);
 697     }
 698     ++protected_it;
 699   }
 700   FinishRecovery(rec_packet_to_insert);
 701 }
 702
 703 void ForwardErrorCorrection::AttemptRecover(
 704     RecoveredPacketList* recovered_packet_list) {
 705   FecPacketList::iterator fec_packet_list_it = fec_packet_list_.begin();
 706   while (fec_packet_list_it != fec_packet_list_.end()) {
 707     // Search for each FEC packet's protected media packets.
 708     int packets_missing = NumCoveredPacketsMissing(*fec_packet_list_it);
 709
 710     // We can only recover one packet with an FEC packet.
 711     if (packets_missing == 1) {
 712       // Recovery possible.
 713       RecoveredPacket* packet_to_insert = new RecoveredPacket;
 714       packet_to_insert->pkt = NULL;
 715       RecoverPacket(*fec_packet_list_it, packet_to_insert);
 716
 717       // Add recovered packet to the list of recovered packets and update any
 718       // FEC packets covering this packet with a pointer to the data.
 719       // TODO(holmer): Consider replacing this with a binary search for the
 720       // right position, and then just insert the new packet. Would get rid of
 721       // the sort.
 722       recovered_packet_list->push_back(packet_to_insert);
 723       recovered_packet_list->sort(SortablePacket::LessThan);
 724       UpdateCoveringFECPackets(packet_to_insert);
 725       DiscardOldPackets(recovered_packet_list);
 726       DiscardFECPacket(*fec_packet_list_it);
 727       fec_packet_list_it = fec_packet_list_.erase(fec_packet_list_it);
 728
 729       // A packet has been recovered. We need to check the FEC list again, as
 730       // this may allow additional packets to be recovered.
 731       // Restart for first FEC packet.
 732       fec_packet_list_it = fec_packet_list_.begin();
 733     } else if (packets_missing == 0) {
 734       // Either all protected packets arrived or have been recovered. We can
 735       // discard this FEC packet.
 736       DiscardFECPacket(*fec_packet_list_it);
 737       fec_packet_list_it = fec_packet_list_.erase(fec_packet_list_it);
 738     } else {
 739       fec_packet_list_it++;
 740     }
 741   }
 742 }
 743
 744 int ForwardErrorCorrection::NumCoveredPacketsMissing(
 745     const FecPacket* fec_packet) {
 746   int packets_missing = 0;
 747   ProtectedPacketList::const_iterator it =
 748       fec_packet->protected_pkt_list.begin();
 749   for (; it != fec_packet->protected_pkt_list.end(); ++it) {
 750     if ((*it)->pkt == NULL) {
 751       ++packets_missing;
 752       if (packets_missing > 1) {
 753         break;  // We can't recover more than one packet.
 754       }
 755     }
 756   }
 757   return packets_missing;
 758 }
 759
 760 void ForwardErrorCorrection::DiscardFECPacket(FecPacket* fec_packet) {
 761   while (!fec_packet->protected_pkt_list.empty()) {
 762     delete fec_packet->protected_pkt_list.front();
 763     fec_packet->protected_pkt_list.pop_front();
 764   }
 765   assert(fec_packet->protected_pkt_list.empty());
 766   delete fec_packet;
 767 }
 768
 769 void ForwardErrorCorrection::DiscardOldPackets(
 770     RecoveredPacketList* recovered_packet_list) {
 771   while (recovered_packet_list->size() > kMaxMediaPackets) {
 772     ForwardErrorCorrection::RecoveredPacket* packet =
 773         recovered_packet_list->front();
 774     delete packet;
 775     recovered_packet_list->pop_front();
 776   }
 777   assert(recovered_packet_list->size() <= kMaxMediaPackets);
 778 }
 779
 780 uint16_t ForwardErrorCorrection::ParseSequenceNumber(uint8_t* packet) {
 781   return (packet[2] << 8) + packet[3];
 782 }
 783
 784 int32_t ForwardErrorCorrection::DecodeFEC(
 785     ReceivedPacketList* received_packet_list,
 786     RecoveredPacketList* recovered_packet_list) {
 787   // TODO(marpan/ajm): can we check for multiple ULP headers, and return an
 788   // error?
 789   if (recovered_packet_list->size() == kMaxMediaPackets) {
 790     const unsigned int seq_num_diff =
 791         abs(static_cast<int>(received_packet_list->front()->seq_num) -
 792             static_cast<int>(recovered_packet_list->back()->seq_num));
 793     if (seq_num_diff > kMaxMediaPackets) {
 794       // A big gap in sequence numbers. The old recovered packets
 795       // are now useless, so it's safe to do a reset.
 796       ResetState(recovered_packet_list);
 797     }
 798   }
 799   InsertPackets(received_packet_list, recovered_packet_list);
 800   AttemptRecover(recovered_packet_list);
 801   return 0;
 802 }
 803
 804 uint16_t ForwardErrorCorrection::PacketOverhead() {
 805   return kFecHeaderSize + kUlpHeaderSizeLBitSet;
 806 }
 807 }  // namespace webrtc