/*
 *  Copyright (c) 2012 The WebRTC project authors. All Rights Reserved.
 *
 *  Use of this source code is governed by a BSD-style license
 *  that can be found in the LICENSE file in the root of the source
 *  tree. An additional intellectual property rights grant can be found
 *  in the file PATENTS.  All contributing project authors may
 *  be found in the AUTHORS file in the root of the source tree.
 */

#include "webrtc/modules/rtp_rtcp/source/forward_error_correction.h"

#include <string.h>

#include <algorithm>
#include <iterator>
#include <utility>

#include "webrtc/base/checks.h"
#include "webrtc/base/logging.h"
#include "webrtc/modules/rtp_rtcp/include/rtp_rtcp_defines.h"
#include "webrtc/modules/rtp_rtcp/source/byte_io.h"
#include "webrtc/modules/rtp_rtcp/source/forward_error_correction_internal.h"

namespace webrtc {

// FEC header size in bytes.
constexpr size_t kFecHeaderSize = 10;

// ULP header size in bytes (L bit is set).
constexpr size_t kUlpHeaderSizeLBitSet = (2 + kMaskSizeLBitSet);

// ULP header size in bytes (L bit is cleared).
constexpr size_t kUlpHeaderSizeLBitClear = (2 + kMaskSizeLBitClear);

// Transport header size in bytes. Assume UDP/IPv4 as a reasonable minimum.
constexpr size_t kTransportOverhead = 28;

// Maximum number of media packets that can be protected.
constexpr size_t ForwardErrorCorrection::kMaxMediaPackets;

// Maximum number of FEC packets stored internally.
constexpr size_t kMaxFecPackets = ForwardErrorCorrection::kMaxMediaPackets;

int32_t ForwardErrorCorrection::Packet::AddRef() {
  return ++ref_count_;
}

int32_t ForwardErrorCorrection::Packet::Release() {
  int32_t ref_count;
  ref_count = --ref_count_;
  if (ref_count == 0)
    delete this;
  return ref_count;
}

// This comparator is used to compare std::unique_ptr's pointing to
// subclasses of SortablePackets. It needs to be parametric since
// the std::unique_ptr's are not covariant w.r.t. the types that
// they are pointing to.
template <typename S, typename T>
bool ForwardErrorCorrection::SortablePacket::LessThan::operator() (
    const S& first,
    const T& second) {
  return IsNewerSequenceNumber(second->seq_num, first->seq_num);
}

ForwardErrorCorrection::ReceivedPacket::ReceivedPacket() {}
ForwardErrorCorrection::ReceivedPacket::~ReceivedPacket() {}

ForwardErrorCorrection::RecoveredPacket::RecoveredPacket() {}
ForwardErrorCorrection::RecoveredPacket::~RecoveredPacket() {}

ForwardErrorCorrection::ForwardErrorCorrection()
    : generated_fec_packets_(kMaxMediaPackets), received_fec_packets_(),
      packet_mask_(), tmp_packet_mask_() {}
ForwardErrorCorrection::~ForwardErrorCorrection() {}

// Input packet
//   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//   |                    RTP Header (12 octets)                     |
//   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//   |                         RTP Payload                           |
//   |                                                               |
//   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

// Output packet
//   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//   |                    FEC Header (10 octets)                     |
//   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//   |                      FEC Level 0 Header                       |
//   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//   |                     FEC Level 0 Payload                       |
//   |                                                               |
//   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//
// Note that any potential RED headers are added/removed before calling
// GenerateFec() or DecodeFec().
int ForwardErrorCorrection::GenerateFec(const PacketList& media_packets,
                                        uint8_t protection_factor,
                                        int num_important_packets,
                                        bool use_unequal_protection,
                                        FecMaskType fec_mask_type,
                                        std::list<Packet*>* fec_packets) {
  const uint16_t num_media_packets = media_packets.size();
  // Sanity check arguments.
  RTC_DCHECK_GT(num_media_packets, 0);
  RTC_DCHECK_GE(num_important_packets, 0);
  RTC_DCHECK_LE(num_important_packets, num_media_packets);
  RTC_DCHECK(fec_packets->empty());

  if (num_media_packets > kMaxMediaPackets) {
    LOG(LS_WARNING) << "Can't protect " << num_media_packets
                    << " media packets per frame. Max is " << kMaxMediaPackets
                    << ".";
    return -1;
  }

  bool l_bit = (num_media_packets > 8 * kMaskSizeLBitClear);
  int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;

  // Do some error checking on the media packets.
  for (const auto& media_packet : media_packets) {
    RTC_DCHECK(media_packet);

    if (media_packet->length < kRtpHeaderSize) {
      LOG(LS_WARNING) << "Media packet " << media_packet->length << " bytes "
                      << "is smaller than RTP header.";
      return -1;
    }

    // Ensure our FEC packets will fit in a typical MTU.
    if (media_packet->length + PacketOverhead() + kTransportOverhead >
        IP_PACKET_SIZE) {
      LOG(LS_WARNING) << "Media packet " << media_packet->length << " bytes "
                      << "with overhead is larger than " << IP_PACKET_SIZE
                      << " bytes.";
    }
  }

  int num_fec_packets = GetNumberOfFecPackets(num_media_packets,
                                              protection_factor);
  if (num_fec_packets == 0) {
    return 0;
  }

  // Prepare generated FEC packets by setting them to 0.
  for (int i = 0; i < num_fec_packets; ++i) {
    memset(generated_fec_packets_[i].data, 0, IP_PACKET_SIZE);
    // Use this as a marker for untouched packets.
    generated_fec_packets_[i].length = 0;
    fec_packets->push_back(&generated_fec_packets_[i]);
  }

  const internal::PacketMaskTable mask_table(fec_mask_type, num_media_packets);

  // -- Generate packet masks --
  memset(packet_mask_, 0, num_fec_packets * num_mask_bytes);
  internal::GeneratePacketMasks(num_media_packets, num_fec_packets,
                                num_important_packets, use_unequal_protection,
                                mask_table, packet_mask_);

  int num_mask_bits = InsertZerosInBitMasks(
      media_packets, packet_mask_, num_mask_bytes, num_fec_packets);

  if (num_mask_bits < 0) {
    return -1;
  }
  l_bit = (static_cast<size_t>(num_mask_bits) > 8 * kMaskSizeLBitClear);
  if (l_bit) {
    num_mask_bytes = kMaskSizeLBitSet;
  }

  GenerateFecBitStrings(media_packets, packet_mask_, num_fec_packets, l_bit);
  GenerateFecUlpHeaders(media_packets, packet_mask_, num_fec_packets, l_bit);

  return 0;
}

int ForwardErrorCorrection::GetNumberOfFecPackets(int num_media_packets,
                                                  int protection_factor) {
  // Result in Q0 with an unsigned round.
  int num_fec_packets = (num_media_packets * protection_factor + (1 << 7)) >> 8;
  // Generate at least one FEC packet if we need protection.
  if (protection_factor > 0 && num_fec_packets == 0) {
    num_fec_packets = 1;
  }
  RTC_DCHECK_LE(num_fec_packets, num_media_packets);
  return num_fec_packets;
}

void ForwardErrorCorrection::GenerateFecBitStrings(
    const PacketList& media_packets,
    uint8_t* packet_mask,
    int num_fec_packets,
    bool l_bit) {
  RTC_DCHECK(!media_packets.empty());
  uint8_t media_payload_length[2];
  const int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;
  const uint16_t ulp_header_size =
      l_bit ? kUlpHeaderSizeLBitSet : kUlpHeaderSizeLBitClear;
  const uint16_t fec_rtp_offset =
      kFecHeaderSize + ulp_header_size - kRtpHeaderSize;

  for (int i = 0; i < num_fec_packets; ++i) {
    Packet* const fec_packet = &generated_fec_packets_[i];
    auto media_packets_it = media_packets.cbegin();
    uint32_t pkt_mask_idx = i * num_mask_bytes;
    uint32_t media_pkt_idx = 0;
    uint16_t fec_packet_length = 0;
    uint16_t prev_seq_num = ParseSequenceNumber((*media_packets_it)->data);
    while (media_packets_it != media_packets.end()) {
      // Each FEC packet has a multiple byte mask. Determine if this media
      // packet should be included in FEC packet i.
      if (packet_mask[pkt_mask_idx] & (1 << (7 - media_pkt_idx))) {
        Packet* media_packet = media_packets_it->get();

        // Assign network-ordered media payload length.
        ByteWriter<uint16_t>::WriteBigEndian(
            media_payload_length, media_packet->length - kRtpHeaderSize);

        fec_packet_length = media_packet->length + fec_rtp_offset;
        // On the first protected packet, we don't need to XOR.
        if (fec_packet->length == 0) {
          // Copy the first 2 bytes of the RTP header. Note that the E and L
          // bits are overwritten in GenerateFecUlpHeaders.
          memcpy(&fec_packet->data[0], &media_packet->data[0], 2);
          // Copy the 5th to 8th bytes of the RTP header (timestamp).
          memcpy(&fec_packet->data[4], &media_packet->data[4], 4);
          // Copy network-ordered payload size.
          memcpy(&fec_packet->data[8], media_payload_length, 2);

          // Copy RTP payload, leaving room for the ULP header.
          memcpy(&fec_packet->data[kFecHeaderSize + ulp_header_size],
                 &media_packet->data[kRtpHeaderSize],
                 media_packet->length - kRtpHeaderSize);
        } else {
          // XOR with the first 2 bytes of the RTP header.
          fec_packet->data[0] ^= media_packet->data[0];
          fec_packet->data[1] ^= media_packet->data[1];

          // XOR with the 5th to 8th bytes of the RTP header.
          for (uint32_t j = 4; j < 8; ++j) {
            fec_packet->data[j] ^= media_packet->data[j];
          }

          // XOR with the network-ordered payload size.
          fec_packet->data[8] ^= media_payload_length[0];
          fec_packet->data[9] ^= media_payload_length[1];

          // XOR with RTP payload, leaving room for the ULP header.
          for (int32_t j = kFecHeaderSize + ulp_header_size;
               j < fec_packet_length; j++) {
            fec_packet->data[j] ^= media_packet->data[j - fec_rtp_offset];
          }
        }
        if (fec_packet_length > fec_packet->length) {
          fec_packet->length = fec_packet_length;
        }
      }
      media_packets_it++;
      if (media_packets_it != media_packets.end()) {
        uint16_t seq_num = ParseSequenceNumber((*media_packets_it)->data);
        media_pkt_idx += static_cast<uint16_t>(seq_num - prev_seq_num);
        prev_seq_num = seq_num;
      }
      pkt_mask_idx += media_pkt_idx / 8;
      media_pkt_idx %= 8;
    }
    RTC_DCHECK_GT(fec_packet->length, 0u)
        << "Packet mask is wrong or poorly designed.";
  }
}

int ForwardErrorCorrection::InsertZerosInBitMasks(
    const PacketList& media_packets,
    uint8_t* packet_mask,
    int num_mask_bytes,
    int num_fec_packets) {
  if (media_packets.size() <= 1) {
    return media_packets.size();
  }
  int last_seq_num = ParseSequenceNumber(media_packets.back()->data);
  int first_seq_num = ParseSequenceNumber(media_packets.front()->data);
  int total_missing_seq_nums =
      static_cast<uint16_t>(last_seq_num - first_seq_num) -
      media_packets.size() + 1;
  if (total_missing_seq_nums == 0) {
    // All sequence numbers are covered by the packet mask. No zero insertion
    // required.
    return media_packets.size();
  }
  // We can only protect 8 * kMaskSizeLBitSet packets.
  if (total_missing_seq_nums + media_packets.size() > 8 * kMaskSizeLBitSet)
    return -1;
  // Allocate the new mask.
  int new_mask_bytes = kMaskSizeLBitClear;
  if (media_packets.size() +
      total_missing_seq_nums > 8 * kMaskSizeLBitClear) {
    new_mask_bytes = kMaskSizeLBitSet;
  }
  memset(tmp_packet_mask_, 0, num_fec_packets * kMaskSizeLBitSet);

  auto media_packets_it = media_packets.cbegin();
  uint16_t prev_seq_num = first_seq_num;
  ++media_packets_it;

  // Insert the first column.
  internal::CopyColumn(tmp_packet_mask_, new_mask_bytes, packet_mask_,
                       num_mask_bytes, num_fec_packets, 0, 0);
  size_t new_bit_index = 1;
  size_t old_bit_index = 1;
  // Insert zeros in the bit mask for every hole in the sequence.
  while (media_packets_it != media_packets.end()) {
    if (new_bit_index == 8 * kMaskSizeLBitSet) {
      // We can only cover up to 48 packets.
      break;
    }
    uint16_t seq_num = ParseSequenceNumber((*media_packets_it)->data);
    const int num_zeros_to_insert =
        static_cast<uint16_t>(seq_num - prev_seq_num - 1);
    if (num_zeros_to_insert > 0) {
      internal::InsertZeroColumns(num_zeros_to_insert, tmp_packet_mask_,
                                  new_mask_bytes, num_fec_packets,
                                  new_bit_index);
    }
    new_bit_index += num_zeros_to_insert;
    internal::CopyColumn(tmp_packet_mask_, new_mask_bytes, packet_mask_,
                         num_mask_bytes, num_fec_packets, new_bit_index,
                         old_bit_index);
    ++new_bit_index;
    ++old_bit_index;
    prev_seq_num = seq_num;
    ++media_packets_it;
  }
  if (new_bit_index % 8 != 0) {
    // We didn't fill the last byte. Shift bits to correct position.
    for (uint16_t row = 0; row < num_fec_packets; ++row) {
      int new_byte_index = row * new_mask_bytes + new_bit_index / 8;
      tmp_packet_mask_[new_byte_index] <<= (7 - (new_bit_index % 8));
    }
  }
  // Replace the old mask with the new.
  memcpy(packet_mask, tmp_packet_mask_, kMaskSizeLBitSet * num_fec_packets);
  return new_bit_index;
}

void ForwardErrorCorrection::GenerateFecUlpHeaders(
    const PacketList& media_packets,
    uint8_t* packet_mask,
    int num_fec_packets,
    bool l_bit) {
  // -- Generate FEC and ULP headers --
  //
  // FEC Header, 10 bytes
  //    0                   1                   2                   3
  //    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
  //   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  //   |E|L|P|X|  CC   |M| PT recovery |            SN base            |
  //   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  //   |                          TS recovery                          |
  //   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  //   |        length recovery        |
  //   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  //
  // ULP Header, 4 bytes (for L = 0)
  //    0                   1                   2                   3
  //    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
  //   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  //   |       Protection Length       |             mask              |
  //   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  //   |              mask cont. (present only when L = 1)             |
  //   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  int num_mask_bytes = l_bit ? kMaskSizeLBitSet : kMaskSizeLBitClear;
  const uint16_t ulp_header_size =
      l_bit ? kUlpHeaderSizeLBitSet : kUlpHeaderSizeLBitClear;

  RTC_DCHECK(!media_packets.empty());
  Packet* first_media_packet = media_packets.front().get();
  RTC_DCHECK(first_media_packet);
  uint16_t seq_num = ParseSequenceNumber(first_media_packet->data);
  for (int i = 0; i < num_fec_packets; ++i) {
    Packet* const fec_packet = &generated_fec_packets_[i];
    // -- FEC header --
    fec_packet->data[0] &= 0x7f;  // Set E to zero.
    if (l_bit == 0) {
      fec_packet->data[0] &= 0xbf;  // Clear the L bit.
    } else {
      fec_packet->data[0] |= 0x40;  // Set the L bit.
    }
    // Sequence number from first media packet used as SN base.
    // We use the same sequence number base for every FEC packet,
    // but that's not required in general.
    ByteWriter<uint16_t>::WriteBigEndian(&fec_packet->data[2], seq_num);

    // -- ULP header --
    // Copy the payload size to the protection length field.
    // (We protect the entire packet.)
    ByteWriter<uint16_t>::WriteBigEndian(
        &fec_packet->data[10],
        fec_packet->length - kFecHeaderSize - ulp_header_size);

    // Copy the packet mask.
    memcpy(&fec_packet->data[12], &packet_mask[i * num_mask_bytes],
           num_mask_bytes);
  }
}

void ForwardErrorCorrection::ResetState(
    RecoveredPacketList* recovered_packets) {
  // Free the memory for any existing recovered packets, if the caller hasn't.
  recovered_packets->clear();
  received_fec_packets_.clear();
}

void ForwardErrorCorrection::InsertMediaPacket(
    ReceivedPacket* received_packet,
    RecoveredPacketList* recovered_packets) {

  // Search for duplicate packets.
  for (const auto& recovered_packet : *recovered_packets) {
    if (received_packet->seq_num == recovered_packet->seq_num) {
      // Duplicate packet, no need to add to list.
      // Delete duplicate media packet data.
      received_packet->pkt = nullptr;
      return;
    }
  }

  std::unique_ptr<RecoveredPacket> recovered_packet(new RecoveredPacket());
  // This "recovered packet" was not recovered using parity packets.
  recovered_packet->was_recovered = false;
  // This media packet has already been passed on.
  recovered_packet->returned = true;
  recovered_packet->seq_num = received_packet->seq_num;
  recovered_packet->pkt = received_packet->pkt;
  recovered_packet->pkt->length = received_packet->pkt->length;

  RecoveredPacket* recovered_packet_ptr = recovered_packet.get();
  // TODO(holmer): Consider replacing this with a binary search for the right
  // position, and then just insert the new packet. Would get rid of the sort.
  recovered_packets->push_back(std::move(recovered_packet));
  recovered_packets->sort(SortablePacket::LessThan());
  UpdateCoveringFecPackets(recovered_packet_ptr);
}

void ForwardErrorCorrection::UpdateCoveringFecPackets(RecoveredPacket* packet) {
  for (auto& fec_packet : received_fec_packets_) {
    // Is this FEC packet protecting the media packet |packet|?
    auto protected_it = std::lower_bound(fec_packet->protected_packets.begin(),
                                         fec_packet->protected_packets.end(),
                                         packet,
                                         SortablePacket::LessThan());
    if (protected_it != fec_packet->protected_packets.end() &&
        (*protected_it)->seq_num == packet->seq_num) {
      // Found an FEC packet which is protecting |packet|.
      (*protected_it)->pkt = packet->pkt;
    }
  }
}

void ForwardErrorCorrection::InsertFecPacket(
    ReceivedPacket* received_packet,
    const RecoveredPacketList* recovered_packets) {
  // Check for duplicate.
  for (const auto& existing_fec_packet : received_fec_packets_) {
    if (received_packet->seq_num == existing_fec_packet->seq_num) {
      // Delete duplicate FEC packet data.
      received_packet->pkt = nullptr;
      return;
    }
  }

  std::unique_ptr<ReceivedFecPacket> fec_packet(new ReceivedFecPacket());
  fec_packet->pkt = received_packet->pkt;
  fec_packet->seq_num = received_packet->seq_num;
  fec_packet->ssrc = received_packet->ssrc;

  const uint16_t seq_num_base =
      ByteReader<uint16_t>::ReadBigEndian(&fec_packet->pkt->data[2]);
  const uint16_t mask_size_bytes = (fec_packet->pkt->data[0] & 0x40)
                                      ? kMaskSizeLBitSet
                                      : kMaskSizeLBitClear;  // L bit set?

  // Parse erasure code mask from ULP header and represent as protected packets.
  for (uint16_t byte_idx = 0; byte_idx < mask_size_bytes; ++byte_idx) {
    uint8_t packet_mask = fec_packet->pkt->data[12 + byte_idx];
    for (uint16_t bit_idx = 0; bit_idx < 8; ++bit_idx) {
      if (packet_mask & (1 << (7 - bit_idx))) {
        std::unique_ptr<ProtectedPacket> protected_packet(
            new ProtectedPacket());
        // This wraps naturally with the sequence number.
        protected_packet->seq_num =
            static_cast<uint16_t>(seq_num_base + (byte_idx << 3) + bit_idx);
        protected_packet->pkt = nullptr;
        // Note that |protected_pkt_list| is sorted (according to sequence
        // number) by construction.
        fec_packet->protected_packets.push_back(std::move(protected_packet));
      }
    }
  }
  if (fec_packet->protected_packets.empty()) {
    // All-zero packet mask; we can discard this FEC packet.
    LOG(LS_WARNING) << "Received FEC packet has an all-zero packet mask.";
  } else {
    AssignRecoveredPackets(fec_packet.get(), recovered_packets);
    // TODO(holmer): Consider replacing this with a binary search for the right
    // position, and then just insert the new packet. Would get rid of the sort.
    //
    // For correct decoding, |fec_packet_list_| does not necessarily
    // need to be sorted by sequence number (see decoding algorithm in
    // AttemptRecover()), but by keeping it sorted we try to recover the
    // oldest lost packets first.
    received_fec_packets_.push_back(std::move(fec_packet));
    received_fec_packets_.sort(SortablePacket::LessThan());
    if (received_fec_packets_.size() > kMaxFecPackets) {
      received_fec_packets_.pop_front();
    }
    RTC_DCHECK_LE(received_fec_packets_.size(), kMaxFecPackets);
  }
}

void ForwardErrorCorrection::AssignRecoveredPackets(
    ReceivedFecPacket* fec_packet,
    const RecoveredPacketList* recovered_packets) {
  ProtectedPacketList* protected_packets = &fec_packet->protected_packets;
  std::vector<RecoveredPacket*> recovered_protected_packets;

  // Find intersection between the (sorted) containers |protected_packets|
  // and |recovered_packets|, i.e. all protected packets that have already
  // been recovered. Update the corresponding protected packets to point to
  // the recovered packets.
  auto it_p = protected_packets->cbegin();
  auto it_r = recovered_packets->cbegin();
  SortablePacket::LessThan less_than;
  while (it_p != protected_packets->end() && it_r != recovered_packets->end()) {
    if (less_than(*it_p, *it_r)) {
      ++it_p;
    } else if (less_than(*it_r, *it_p)) {
      ++it_r;
    } else {  // *it_p == *it_r.
      // This protected packet has already been recovered.
      (*it_p)->pkt = (*it_r)->pkt;
      ++it_p;
      ++it_r;
    }
  }
}

void ForwardErrorCorrection::InsertPackets(
    ReceivedPacketList* received_packets,
    RecoveredPacketList* recovered_packets) {
  while (!received_packets->empty()) {
    ReceivedPacket* received_packet = received_packets->front().get();

    // Check for discarding oldest FEC packet, to avoid wrong FEC decoding from
    // sequence number wrap-around. Detection of old FEC packet is based on
    // sequence number difference of received packet and oldest packet in FEC
    // packet list.
    // TODO(marpan/holmer): We should be able to improve detection/discarding of
    // old FEC packets based on timestamp information or better sequence number
    // thresholding (e.g., to distinguish between wrap-around and reordering).
    if (!received_fec_packets_.empty()) {
      uint16_t seq_num_diff =
          abs(static_cast<int>(received_packet->seq_num) -
              static_cast<int>(received_fec_packets_.front()->seq_num));
      if (seq_num_diff > 0x3fff) {
        received_fec_packets_.pop_front();
      }
    }

    if (received_packet->is_fec) {
      InsertFecPacket(received_packet, recovered_packets);
    } else {
      InsertMediaPacket(received_packet, recovered_packets);
    }
    // Delete the received packet "wrapper".
    received_packets->pop_front();
  }
  RTC_DCHECK(received_packets->empty());
  DiscardOldRecoveredPackets(recovered_packets);
}

bool ForwardErrorCorrection::StartPacketRecovery(
      const ReceivedFecPacket* fec_packet,
      RecoveredPacket* recovered_packet) {
  // This is the first packet which we try to recover with.
  const uint16_t ulp_header_size = fec_packet->pkt->data[0] & 0x40
                                       ? kUlpHeaderSizeLBitSet
                                       : kUlpHeaderSizeLBitClear;  // L bit set?
  if (fec_packet->pkt->length <
      static_cast<size_t>(kFecHeaderSize + ulp_header_size)) {
    LOG(LS_WARNING)
        << "Truncated FEC packet doesn't contain room for ULP header.";
    return false;
  }
  recovered_packet->pkt = new Packet();
  memset(recovered_packet->pkt->data, 0, IP_PACKET_SIZE);
  recovered_packet->returned = false;
  recovered_packet->was_recovered = true;
  uint16_t protection_length =
      ByteReader<uint16_t>::ReadBigEndian(&fec_packet->pkt->data[10]);
  if (protection_length >
      std::min(
          sizeof(recovered_packet->pkt->data) - kRtpHeaderSize,
          sizeof(fec_packet->pkt->data) - kFecHeaderSize - ulp_header_size)) {
    LOG(LS_WARNING) << "Incorrect FEC protection length, dropping.";
    return false;
  }
  // Copy FEC payload, skipping the ULP header.
  memcpy(&recovered_packet->pkt->data[kRtpHeaderSize],
         &fec_packet->pkt->data[kFecHeaderSize + ulp_header_size],
         protection_length);
  // Copy the length recovery field.
  memcpy(recovered_packet->length_recovery, &fec_packet->pkt->data[8], 2);
  // Copy the first 2 bytes of the FEC header.
  memcpy(recovered_packet->pkt->data, fec_packet->pkt->data, 2);
  // Copy the 5th to 8th bytes of the FEC header.
  memcpy(&recovered_packet->pkt->data[4], &fec_packet->pkt->data[4], 4);
  // Set the SSRC field.
  ByteWriter<uint32_t>::WriteBigEndian(&recovered_packet->pkt->data[8],
                                       fec_packet->ssrc);
  return true;
}

bool ForwardErrorCorrection::FinishPacketRecovery(
    RecoveredPacket* recovered_packet) {
  // Set the RTP version to 2.
  recovered_packet->pkt->data[0] |= 0x80;  // Set the 1st bit.
  recovered_packet->pkt->data[0] &= 0xbf;  // Clear the 2nd bit.

  // Set the SN field.
  ByteWriter<uint16_t>::WriteBigEndian(&recovered_packet->pkt->data[2],
                                       recovered_packet->seq_num);
  // Recover the packet length.
  recovered_packet->pkt->length =
      ByteReader<uint16_t>::ReadBigEndian(recovered_packet->length_recovery) +
      kRtpHeaderSize;
  if (recovered_packet->pkt->length >
      sizeof(recovered_packet->pkt->data) - kRtpHeaderSize) {
    return false;
  }

  return true;
}

void ForwardErrorCorrection::XorPackets(const Packet* src,
                                        RecoveredPacket* dst) {
  // XOR with the first 2 bytes of the RTP header.
  for (uint32_t i = 0; i < 2; ++i) {
    dst->pkt->data[i] ^= src->data[i];
  }
  // XOR with the 5th to 8th bytes of the RTP header.
  for (uint32_t i = 4; i < 8; ++i) {
    dst->pkt->data[i] ^= src->data[i];
  }
  // XOR with the network-ordered payload size.
  uint8_t media_payload_length[2];
  ByteWriter<uint16_t>::WriteBigEndian(media_payload_length,
                                       src->length - kRtpHeaderSize);
  dst->length_recovery[0] ^= media_payload_length[0];
  dst->length_recovery[1] ^= media_payload_length[1];

  // XOR with RTP payload.
  // TODO(marpan/ajm): Are we doing more XORs than required here?
  for (size_t i = kRtpHeaderSize; i < src->length; ++i) {
    dst->pkt->data[i] ^= src->data[i];
  }
}

bool ForwardErrorCorrection::RecoverPacket(
    const ReceivedFecPacket* fec_packet,
    RecoveredPacket* rec_packet_to_insert) {
  if (!StartPacketRecovery(fec_packet, rec_packet_to_insert))
    return false;
  for (const auto& protected_packet : fec_packet->protected_packets) {
    if (protected_packet->pkt == nullptr) {
      // This is the packet we're recovering.
      rec_packet_to_insert->seq_num = protected_packet->seq_num;
    } else {
      XorPackets(protected_packet->pkt, rec_packet_to_insert);
    }
  }
  if (!FinishPacketRecovery(rec_packet_to_insert))
    return false;
  return true;
}

void ForwardErrorCorrection::AttemptRecover(
    RecoveredPacketList* recovered_packets) {
  auto fec_packet_it = received_fec_packets_.begin();
  while (fec_packet_it != received_fec_packets_.end()) {
    // Search for each FEC packet's protected media packets.
    int packets_missing = NumCoveredPacketsMissing(fec_packet_it->get());

    // We can only recover one packet with an FEC packet.
    if (packets_missing == 1) {
      // Recovery possible.
      std::unique_ptr<RecoveredPacket> packet_to_insert(new RecoveredPacket());
      packet_to_insert->pkt = nullptr;
      if (!RecoverPacket(fec_packet_it->get(), packet_to_insert.get())) {
        // Can't recover using this packet, drop it.
        fec_packet_it = received_fec_packets_.erase(fec_packet_it);
        continue;
      }

      auto packet_to_insert_ptr = packet_to_insert.get();
      // Add recovered packet to the list of recovered packets and update any
      // FEC packets covering this packet with a pointer to the data.
      // TODO(holmer): Consider replacing this with a binary search for the
      // right position, and then just insert the new packet. Would get rid of
      // the sort.
      recovered_packets->push_back(std::move(packet_to_insert));
      recovered_packets->sort(SortablePacket::LessThan());
      UpdateCoveringFecPackets(packet_to_insert_ptr);
      DiscardOldRecoveredPackets(recovered_packets);
      fec_packet_it = received_fec_packets_.erase(fec_packet_it);

      // A packet has been recovered. We need to check the FEC list again, as
      // this may allow additional packets to be recovered.
      // Restart for first FEC packet.
      fec_packet_it = received_fec_packets_.begin();
    } else if (packets_missing == 0) {
      // Either all protected packets arrived or have been recovered. We can
      // discard this FEC packet.
      fec_packet_it = received_fec_packets_.erase(fec_packet_it);
    } else {
      fec_packet_it++;
    }
  }
}

int ForwardErrorCorrection::NumCoveredPacketsMissing(
    const ReceivedFecPacket* fec_packet) {
  int packets_missing = 0;
  for (const auto& protected_packet : fec_packet->protected_packets) {
    if (protected_packet->pkt == nullptr) {
      ++packets_missing;
      if (packets_missing > 1) {
        break;  // We can't recover more than one packet.
      }
    }
  }
  return packets_missing;
}

void ForwardErrorCorrection::DiscardOldRecoveredPackets(
    RecoveredPacketList* recovered_packets) {
  while (recovered_packets->size() > kMaxMediaPackets) {
    recovered_packets->pop_front();
  }
  RTC_DCHECK_LE(recovered_packets->size(), kMaxMediaPackets);
}

uint16_t ForwardErrorCorrection::ParseSequenceNumber(uint8_t* packet) {
  return (packet[2] << 8) + packet[3];
}

int ForwardErrorCorrection::DecodeFec(
    ReceivedPacketList* received_packets,
    RecoveredPacketList* recovered_packets) {
  // TODO(marpan/ajm): can we check for multiple ULP headers, and return an
  // error?
  if (recovered_packets->size() == kMaxMediaPackets) {
    const unsigned int seq_num_diff =
        abs(static_cast<int>(received_packets->front()->seq_num) -
            static_cast<int>(recovered_packets->back()->seq_num));
    if (seq_num_diff > kMaxMediaPackets) {
      // A big gap in sequence numbers. The old recovered packets
      // are now useless, so it's safe to do a reset.
      ResetState(recovered_packets);
    }
  }
  InsertPackets(received_packets, recovered_packets);
  AttemptRecover(recovered_packets);
  return 0;
}

size_t ForwardErrorCorrection::PacketOverhead() {
  return kFecHeaderSize + kUlpHeaderSizeLBitSet;
}
}  // namespace webrtc