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       effective_encryption_level_(NUM_ENCRYPTION_LEVELS) {
  27 }
  28
  29 QuicFecGroup::~QuicFecGroup() {}
  30
  31 bool QuicFecGroup::Update(EncryptionLevel encryption_level,
  32                           const QuicPacketHeader& header,
  33                           StringPiece decrypted_payload) {
  34   if (received_packets_.count(header.packet_sequence_number) != 0) {
  35     return false;
  36   }
  37   if (min_protected_packet_ != kNoSequenceNumber &&
  38       max_protected_packet_ != kNoSequenceNumber &&
  39       (header.packet_sequence_number < min_protected_packet_ ||
  40        header.packet_sequence_number > max_protected_packet_)) {
  41     DLOG(ERROR) << "FEC group does not cover received packet: "
  42                 << header.packet_sequence_number;
  43     return false;
  44   }
  45   if (!UpdateParity(decrypted_payload)) {
  46     return false;
  47   }
  48   received_packets_.insert(header.packet_sequence_number);
  49   if (encryption_level < effective_encryption_level_) {
  50     effective_encryption_level_ = encryption_level;
  51   }
  52   return true;
  53 }
  54
  55 bool QuicFecGroup::UpdateFec(
  56     EncryptionLevel encryption_level,
  57     QuicPacketSequenceNumber fec_packet_sequence_number,
  58     const QuicFecData& fec) {
  59   if (min_protected_packet_ != kNoSequenceNumber) {
  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 = kNoSequenceNumber;
 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(kNoSequenceNumber, 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_ != kNoSequenceNumber) {
 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_LE(payload.size(), kMaxPacketSize);
 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   DCHECK_LE(payload.size(), kMaxPacketSize);
 144   if (received_packets_.empty() &&
 145       min_protected_packet_ == kNoSequenceNumber) {
 146     // Initialize the parity to the value of this payload
 147     memcpy(payload_parity_, payload.data(), payload.size());
 148     if (payload.size() < kMaxPacketSize) {
 149       // TODO(rch): expand as needed.
 150       memset(payload_parity_ + payload.size(), 0,
 151              kMaxPacketSize - payload.size());
 152     }
 153     return true;
 154   }
 155   // Update the parity by XORing in the data (padding with 0s if necessary).
 156   for (size_t i = 0; i < kMaxPacketSize; ++i) {
 157     uint8 byte = i < payload.size() ? payload[i] : 0x00;
 158     payload_parity_[i] ^= byte;
 159   }
 160   return true;
 161 }
 162
 163 size_t QuicFecGroup::NumMissingPackets() const {
 164   if (min_protected_packet_ == kNoSequenceNumber)
 165     return numeric_limits<size_t>::max();
 166   return (max_protected_packet_ - min_protected_packet_ + 1) -
 167       received_packets_.size();
 168 }
 169
 170 }  // namespace net