Home | History | Annotate | Download | only in quic 
      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_.empty() &&
    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
    167