net/quic/quic_fec_group.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/quic/quic_fec_group.h"
   6
   7 #include <limits>
   8
   9 #include "base/basictypes.h"
  10 #include "base/logging.h"
  11
  12 using base::StringPiece;
  13 using std::numeric_limits;
  14 using std::set;
  15
  16 namespace net {
  17
  18 namespace {
  19 const QuicPacketSequenceNumber kNoSequenceNumber = kuint64max;
  20 }  // namespace
  21
  22 QuicFecGroup::QuicFecGroup()
  23     : min_protected_packet_(kNoSequenceNumber),
  24       max_protected_packet_(kNoSequenceNumber),
  25       payload_parity_len_(0),
  26       entropy_parity_(false) {
  27 }
  28
  29 QuicFecGroup::~QuicFecGroup() {}
  30
  31 bool QuicFecGroup::Update(const QuicPacketHeader& header,
  32                           StringPiece decrypted_payload) {
  33   if (received_packets_.count(header.packet_sequence_number) != 0) {
  34     return false;
  35   }
  36   if (min_protected_packet_ != kNoSequenceNumber &&
  37       max_protected_packet_ != kNoSequenceNumber &&
  38       (header.packet_sequence_number < min_protected_packet_ ||
  39        header.packet_sequence_number > max_protected_packet_)) {
  40     DLOG(ERROR) << "FEC group does not cover received packet: "
  41                 << header.packet_sequence_number;
  42     return false;
  43   }
  44   if (!UpdateParity(decrypted_payload, header.entropy_flag)) {
  45     return false;
  46   }
  47   received_packets_.insert(header.packet_sequence_number);
  48   return true;
  49 }
  50
  51 bool QuicFecGroup::UpdateFec(
  52     QuicPacketSequenceNumber fec_packet_sequence_number,
  53     bool fec_packet_entropy,
  54     const QuicFecData& fec) {
  55   if (min_protected_packet_ != kNoSequenceNumber) {
  56     return false;
  57   }
  58   SequenceNumberSet::const_iterator it = received_packets_.begin();
  59   while (it != received_packets_.end()) {
  60     if ((*it < fec.fec_group) ||
  61         (*it >= fec_packet_sequence_number)) {
  62       DLOG(ERROR) << "FEC group does not cover received packet: " << *it;
  63       return false;
  64     }
  65     ++it;
  66   }
  67   if (!UpdateParity(fec.redundancy, fec_packet_entropy)) {
  68     return false;
  69   }
  70   min_protected_packet_ = fec.fec_group;
  71   max_protected_packet_ = fec_packet_sequence_number - 1;
  72   return true;
  73 }
  74
  75 bool QuicFecGroup::CanRevive() const {
  76   // We can revive if we're missing exactly 1 packet.
  77   return NumMissingPackets() == 1;
  78 }
  79
  80 bool QuicFecGroup::IsFinished() const {
  81   // We are finished if we are not missing any packets.
  82   return NumMissingPackets() == 0;
  83 }
  84
  85 size_t QuicFecGroup::Revive(QuicPacketHeader* header,
  86                             char* decrypted_payload,
  87                             size_t decrypted_payload_len) {
  88   if (!CanRevive()) {
  89     return 0;
  90   }
  91
  92   // Identify the packet sequence number to be resurrected.
  93   QuicPacketSequenceNumber missing = kNoSequenceNumber;
  94   for (QuicPacketSequenceNumber i = min_protected_packet_;
  95        i <= max_protected_packet_; ++i) {
  96     // Is this packet missing?
  97     if (received_packets_.count(i) == 0) {
  98       missing = i;
  99       break;
 100     }
 101   }
 102   DCHECK_NE(kNoSequenceNumber, missing);
 103
 104   DCHECK_LE(payload_parity_len_, decrypted_payload_len);
 105   if (payload_parity_len_ > decrypted_payload_len) {
 106     return 0;
 107   }
 108   for (size_t i = 0; i < payload_parity_len_; ++i) {
 109     decrypted_payload[i] = payload_parity_[i];
 110   }
 111
 112   header->packet_sequence_number = missing;
 113   header->entropy_flag = entropy_parity_;
 114
 115   received_packets_.insert(missing);
 116   return payload_parity_len_;
 117 }
 118
 119 bool QuicFecGroup::ProtectsPacketsBefore(QuicPacketSequenceNumber num) const {
 120   if (max_protected_packet_ != kNoSequenceNumber) {
 121     return max_protected_packet_ < num;
 122   }
 123   // Since we might not yet have recevied the FEC packet, we must check
 124   // the packets we have received.
 125   return *received_packets_.begin() < num;
 126 }
 127
 128 bool QuicFecGroup::UpdateParity(StringPiece payload, bool entropy) {
 129   DCHECK_LE(payload.size(), kMaxPacketSize);
 130   if (payload.size() > kMaxPacketSize) {
 131     DLOG(ERROR) << "Illegal payload size: " << payload.size();
 132     return false;
 133   }
 134   if (payload_parity_len_ < payload.size()) {
 135     payload_parity_len_ = payload.size();
 136   }
 137   DCHECK_LE(payload.size(), kMaxPacketSize);
 138   if (received_packets_.empty() &&
 139       min_protected_packet_ == kNoSequenceNumber) {
 140     // Initialize the parity to the value of this payload
 141     memcpy(payload_parity_, payload.data(), payload.size());
 142     if (payload.size() < kMaxPacketSize) {
 143       // TODO(rch): expand as needed.
 144       memset(payload_parity_ + payload.size(), 0,
 145              kMaxPacketSize - payload.size());
 146     }
 147     entropy_parity_ = entropy;
 148     return true;
 149   }
 150   // Update the parity by XORing in the data (padding with 0s if necessary).
 151   for (size_t i = 0; i < kMaxPacketSize; ++i) {
 152     uint8 byte = i < payload.size() ? payload[i] : 0x00;
 153     payload_parity_[i] ^= byte;
 154   }
 155   // xor of boolean values.
 156   entropy_parity_ = (entropy_parity_ != entropy);
 157   return true;
 158 }
 159
 160 size_t QuicFecGroup::NumMissingPackets() const {
 161   if (min_protected_packet_ == kNoSequenceNumber)
 162     return numeric_limits<size_t>::max();
 163   return (max_protected_packet_ - min_protected_packet_ + 1) -
 164       received_packets_.size();
 165 }
 166
 167 }  // namespace net