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