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