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 12using base::StringPiece; 13using std::numeric_limits; 14using std::set; 15 16namespace net { 17 18namespace { 19const QuicPacketSequenceNumber kNoSequenceNumber = kuint64max; 20} // namespace 21 22QuicFecGroup::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 29QuicFecGroup::~QuicFecGroup() {} 30 31bool 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 55bool 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 81bool QuicFecGroup::CanRevive() const { 82 // We can revive if we're missing exactly 1 packet. 83 return NumMissingPackets() == 1; 84} 85 86bool QuicFecGroup::IsFinished() const { 87 // We are finished if we are not missing any packets. 88 return NumMissingPackets() == 0; 89} 90 91size_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 125bool 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 134bool 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 163size_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 171