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