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_(kInvalidPacketNumber),
  21       max_protected_packet_(kInvalidPacketNumber),
  22       payload_parity_len_(0),
  23       effective_encryption_level_(NUM_ENCRYPTION_LEVELS) {}
  24
  25 QuicFecGroup::~QuicFecGroup() {}
  26
  27 bool QuicFecGroup::Update(EncryptionLevel encryption_level,
  28                           const QuicPacketHeader& header,
  29                           StringPiece decrypted_payload) {
  30   DCHECK_NE(kInvalidPacketNumber, header.packet_packet_number);
  31   if (ContainsKey(received_packets_, header.packet_packet_number)) {
  32     return false;
  33   }
  34   if (min_protected_packet_ != kInvalidPacketNumber &&
  35       max_protected_packet_ != kInvalidPacketNumber &&
  36       (header.packet_packet_number < min_protected_packet_ ||
  37        header.packet_packet_number > max_protected_packet_)) {
  38     DLOG(ERROR) << "FEC group does not cover received packet: "
  39                 << header.packet_packet_number;
  40     return false;
  41   }
  42   if (!UpdateParity(decrypted_payload)) {
  43     return false;
  44   }
  45   received_packets_.insert(header.packet_packet_number);
  46   if (encryption_level < effective_encryption_level_) {
  47     effective_encryption_level_ = encryption_level;
  48   }
  49   return true;
  50 }
  51
  52 bool QuicFecGroup::UpdateFec(EncryptionLevel encryption_level,
  53                              QuicPacketNumber fec_packet_packet_number,
  54                              const QuicFecData& fec) {
  55   DCHECK_NE(kInvalidPacketNumber, fec_packet_packet_number);
  56   DCHECK_NE(kInvalidPacketNumber, fec.fec_group);
  57   if (min_protected_packet_ != kInvalidPacketNumber) {
  58     return false;
  59   }
  60   PacketNumberSet::const_iterator it = received_packets_.begin();
  61   while (it != received_packets_.end()) {
  62     if ((*it < fec.fec_group) || (*it >= fec_packet_packet_number)) {
  63       DLOG(ERROR) << "FEC group does not cover received packet: " << *it;
  64       return false;
  65     }
  66     ++it;
  67   }
  68   if (!UpdateParity(fec.redundancy)) {
  69     return false;
  70   }
  71   min_protected_packet_ = fec.fec_group;
  72   max_protected_packet_ = fec_packet_packet_number - 1;
  73   if (encryption_level < effective_encryption_level_) {
  74     effective_encryption_level_ = encryption_level;
  75   }
  76   return true;
  77 }
  78
  79 bool QuicFecGroup::CanRevive() const {
  80   // We can revive if we're missing exactly 1 packet.
  81   return NumMissingPackets() == 1;
  82 }
  83
  84 bool QuicFecGroup::IsFinished() const {
  85   // We are finished if we are not missing any packets.
  86   return NumMissingPackets() == 0;
  87 }
  88
  89 size_t QuicFecGroup::Revive(QuicPacketHeader* header,
  90                             char* decrypted_payload,
  91                             size_t decrypted_payload_len) {
  92   if (!CanRevive()) {
  93     return 0;
  94   }
  95
  96   // Identify the packet number to be resurrected.
  97   QuicPacketNumber missing = kInvalidPacketNumber;
  98   for (QuicPacketNumber i = min_protected_packet_; i <= max_protected_packet_;
  99        ++i) {
 100     // Is this packet missing?
 101     if (received_packets_.count(i) == 0) {
 102       missing = i;
 103       break;
 104     }
 105   }
 106   DCHECK_NE(kInvalidPacketNumber, missing);
 107
 108   DCHECK_LE(payload_parity_len_, decrypted_payload_len);
 109   if (payload_parity_len_ > decrypted_payload_len) {
 110     return 0;
 111   }
 112   for (size_t i = 0; i < payload_parity_len_; ++i) {
 113     decrypted_payload[i] = payload_parity_[i];
 114   }
 115
 116   header->packet_packet_number = missing;
 117   header->entropy_flag = false;  // Unknown entropy.
 118
 119   received_packets_.insert(missing);
 120   return payload_parity_len_;
 121 }
 122
 123 bool QuicFecGroup::ProtectsPacketsBefore(QuicPacketNumber num) const {
 124   if (max_protected_packet_ != kInvalidPacketNumber) {
 125     return max_protected_packet_ < num;
 126   }
 127   // Since we might not yet have received the FEC packet, we must check
 128   // the packets we have received.
 129   return *received_packets_.begin() < num;
 130 }
 131
 132 bool QuicFecGroup::UpdateParity(StringPiece payload) {
 133   DCHECK_GE(kMaxPacketSize, payload.size());
 134   if (payload.size() > kMaxPacketSize) {
 135     DLOG(ERROR) << "Illegal payload size: " << payload.size();
 136     return false;
 137   }
 138   if (payload_parity_len_ < payload.size()) {
 139     payload_parity_len_ = payload.size();
 140   }
 141   if (received_packets_.empty() &&
 142       min_protected_packet_ == kInvalidPacketNumber) {
 143     // Initialize the parity to the value of this payload
 144     memcpy(payload_parity_, payload.data(), payload.size());
 145     if (payload.size() < kMaxPacketSize) {
 146       // TODO(rch): expand as needed.
 147       memset(payload_parity_ + payload.size(), 0,
 148              kMaxPacketSize - payload.size());
 149     }
 150     return true;
 151   }
 152   // Update the parity by XORing in the data (padding with 0s if necessary).
 153   XorBuffers(payload.data(), payload.size(), payload_parity_);
 154   return true;
 155 }
 156
 157 QuicPacketCount QuicFecGroup::NumMissingPackets() const {
 158   if (min_protected_packet_ == kInvalidPacketNumber) {
 159     return numeric_limits<QuicPacketCount>::max();
 160   }
 161   return static_cast<QuicPacketCount>(
 162       (max_protected_packet_ - min_protected_packet_ + 1) -
 163       received_packets_.size());
 164 }
 165
 166 void QuicFecGroup::XorBuffers(const char* input,
 167                               size_t size_in_bytes,
 168                               char* output) {
 169 #if defined(__i386__) || defined(__x86_64__)
 170   // On x86, alignment is not required and casting bytes to words is safe.
 171
 172   // size_t is a reasonable approximation of how large a general-purpose
 173   // register is for the platforms and compilers Chrome is built on.
 174   typedef size_t platform_word;
 175   const size_t size_in_words = size_in_bytes / sizeof(platform_word);
 176
 177   const platform_word* input_words =
 178       reinterpret_cast<const platform_word*>(input);
 179   platform_word* output_words = reinterpret_cast<platform_word*>(output);
 180
 181   // Handle word-sized part of the buffer.
 182   size_t offset_in_words = 0;
 183   for (; offset_in_words < size_in_words; offset_in_words++) {
 184     output_words[offset_in_words] ^= input_words[offset_in_words];
 185   }
 186
 187   // Handle the tail which does not fit into the word.
 188   for (size_t offset_in_bytes = offset_in_words * sizeof(platform_word);
 189        offset_in_bytes < size_in_bytes; offset_in_bytes++) {
 190     output[offset_in_bytes] ^= input[offset_in_bytes];
 191   }
 192 #else
 193   // On ARM and most other plaforms, the code above could fail due to the
 194   // alignment errors.  Stick to byte-by-byte comparison.
 195   for (size_t offset = 0; offset < size_in_bytes; offset++) {
 196     output[offset] ^= input[offset];
 197   }
 198 #endif /* defined(__i386__) || defined(__x86_64__) */
 199 }
 200
 201 }  // namespace net