net/quic/quic_framer.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_framer.h"
   6
   7 #include <stdint.h>
   8
   9 #include "base/basictypes.h"
  10 #include "base/logging.h"
  11 #include "base/stl_util.h"
  12 #include "net/quic/crypto/crypto_framer.h"
  13 #include "net/quic/crypto/crypto_handshake_message.h"
  14 #include "net/quic/crypto/crypto_protocol.h"
  15 #include "net/quic/crypto/quic_decrypter.h"
  16 #include "net/quic/crypto/quic_encrypter.h"
  17 #include "net/quic/quic_data_reader.h"
  18 #include "net/quic/quic_data_writer.h"
  19 #include "net/quic/quic_flags.h"
  20 #include "net/quic/quic_socket_address_coder.h"
  21 #include "net/quic/quic_utils.h"
  22
  23 using base::StringPiece;
  24 using std::map;
  25 using std::max;
  26 using std::min;
  27 using std::numeric_limits;
  28 using std::string;
  29
  30 namespace net {
  31
  32 namespace {
  33
  34 // Mask to select the lowest 48 bits of a sequence number.
  35 const QuicPacketSequenceNumber k6ByteSequenceNumberMask =
  36     UINT64_C(0x0000FFFFFFFFFFFF);
  37 const QuicPacketSequenceNumber k4ByteSequenceNumberMask =
  38     UINT64_C(0x00000000FFFFFFFF);
  39 const QuicPacketSequenceNumber k2ByteSequenceNumberMask =
  40     UINT64_C(0x000000000000FFFF);
  41 const QuicPacketSequenceNumber k1ByteSequenceNumberMask =
  42     UINT64_C(0x00000000000000FF);
  43
  44 const QuicConnectionId k1ByteConnectionIdMask = UINT64_C(0x00000000000000FF);
  45 const QuicConnectionId k4ByteConnectionIdMask = UINT64_C(0x00000000FFFFFFFF);
  46
  47 // Number of bits the sequence number length bits are shifted from the right
  48 // edge of the public header.
  49 const uint8 kPublicHeaderSequenceNumberShift = 4;
  50
  51 // New Frame Types, QUIC v. >= 10:
  52 // There are two interpretations for the Frame Type byte in the QUIC protocol,
  53 // resulting in two Frame Types: Special Frame Types and Regular Frame Types.
  54 //
  55 // Regular Frame Types use the Frame Type byte simply. Currently defined
  56 // Regular Frame Types are:
  57 // Padding            : 0b 00000000 (0x00)
  58 // ResetStream        : 0b 00000001 (0x01)
  59 // ConnectionClose    : 0b 00000010 (0x02)
  60 // GoAway             : 0b 00000011 (0x03)
  61 // WindowUpdate       : 0b 00000100 (0x04)
  62 // Blocked            : 0b 00000101 (0x05)
  63 //
  64 // Special Frame Types encode both a Frame Type and corresponding flags
  65 // all in the Frame Type byte. Currently defined Special Frame Types are:
  66 // Stream             : 0b 1xxxxxxx
  67 // Ack                : 0b 01xxxxxx
  68 //
  69 // Semantics of the flag bits above (the x bits) depends on the frame type.
  70
  71 // Masks to determine if the frame type is a special use
  72 // and for specific special frame types.
  73 const uint8 kQuicFrameTypeSpecialMask = 0xE0;  // 0b 11100000
  74 const uint8 kQuicFrameTypeStreamMask = 0x80;
  75 const uint8 kQuicFrameTypeAckMask = 0x40;
  76
  77 // Stream frame relative shifts and masks for interpreting the stream flags.
  78 // StreamID may be 1, 2, 3, or 4 bytes.
  79 const uint8 kQuicStreamIdShift = 2;
  80 const uint8 kQuicStreamIDLengthMask = 0x03;
  81
  82 // Offset may be 0, 2, 3, 4, 5, 6, 7, 8 bytes.
  83 const uint8 kQuicStreamOffsetShift = 3;
  84 const uint8 kQuicStreamOffsetMask = 0x07;
  85
  86 // Data length may be 0 or 2 bytes.
  87 const uint8 kQuicStreamDataLengthShift = 1;
  88 const uint8 kQuicStreamDataLengthMask = 0x01;
  89
  90 // Fin bit may be set or not.
  91 const uint8 kQuicStreamFinShift = 1;
  92 const uint8 kQuicStreamFinMask = 0x01;
  93
  94 // Sequence number size shift used in AckFrames.
  95 const uint8 kQuicSequenceNumberLengthShift = 2;
  96
  97 // Acks may be truncated.
  98 const uint8 kQuicAckTruncatedShift = 1;
  99 const uint8 kQuicAckTruncatedMask = 0x01;
 100
 101 // Acks may not have any nacks.
 102 const uint8 kQuicHasNacksMask = 0x01;
 103
 104 // Returns the absolute value of the difference between |a| and |b|.
 105 QuicPacketSequenceNumber Delta(QuicPacketSequenceNumber a,
 106                                QuicPacketSequenceNumber b) {
 107   // Since these are unsigned numbers, we can't just return abs(a - b)
 108   if (a < b) {
 109     return b - a;
 110   }
 111   return a - b;
 112 }
 113
 114 QuicPacketSequenceNumber ClosestTo(QuicPacketSequenceNumber target,
 115                                    QuicPacketSequenceNumber a,
 116                                    QuicPacketSequenceNumber b) {
 117   return (Delta(target, a) < Delta(target, b)) ? a : b;
 118 }
 119
 120 QuicSequenceNumberLength ReadSequenceNumberLength(uint8 flags) {
 121   switch (flags & PACKET_FLAGS_6BYTE_SEQUENCE) {
 122     case PACKET_FLAGS_6BYTE_SEQUENCE:
 123       return PACKET_6BYTE_SEQUENCE_NUMBER;
 124     case PACKET_FLAGS_4BYTE_SEQUENCE:
 125       return PACKET_4BYTE_SEQUENCE_NUMBER;
 126     case PACKET_FLAGS_2BYTE_SEQUENCE:
 127       return PACKET_2BYTE_SEQUENCE_NUMBER;
 128     case PACKET_FLAGS_1BYTE_SEQUENCE:
 129       return PACKET_1BYTE_SEQUENCE_NUMBER;
 130     default:
 131       LOG(DFATAL) << "Unreachable case statement.";
 132       return PACKET_6BYTE_SEQUENCE_NUMBER;
 133   }
 134 }
 135
 136 }  // namespace
 137
 138 QuicFramer::QuicFramer(const QuicVersionVector& supported_versions,
 139                        QuicTime creation_time,
 140                        Perspective perspective)
 141     : visitor_(nullptr),
 142       entropy_calculator_(nullptr),
 143       error_(QUIC_NO_ERROR),
 144       last_sequence_number_(0),
 145       last_serialized_connection_id_(0),
 146       supported_versions_(supported_versions),
 147       decrypter_level_(ENCRYPTION_NONE),
 148       alternative_decrypter_level_(ENCRYPTION_NONE),
 149       alternative_decrypter_latch_(false),
 150       perspective_(perspective),
 151       validate_flags_(true),
 152       creation_time_(creation_time),
 153       last_timestamp_(QuicTime::Delta::Zero()) {
 154   DCHECK(!supported_versions.empty());
 155   quic_version_ = supported_versions_[0];
 156   decrypter_.reset(QuicDecrypter::Create(kNULL));
 157   encrypter_[ENCRYPTION_NONE].reset(QuicEncrypter::Create(kNULL));
 158 }
 159
 160 QuicFramer::~QuicFramer() {}
 161
 162 // static
 163 size_t QuicFramer::GetMinStreamFrameSize(QuicStreamId stream_id,
 164                                          QuicStreamOffset offset,
 165                                          bool last_frame_in_packet,
 166                                          InFecGroup is_in_fec_group) {
 167   bool no_stream_frame_length = last_frame_in_packet &&
 168                                 is_in_fec_group == NOT_IN_FEC_GROUP;
 169   return kQuicFrameTypeSize + GetStreamIdSize(stream_id) +
 170       GetStreamOffsetSize(offset) +
 171       (no_stream_frame_length ? 0 : kQuicStreamPayloadLengthSize);
 172 }
 173
 174 // static
 175 size_t QuicFramer::GetMinAckFrameSize(
 176     QuicSequenceNumberLength largest_observed_length) {
 177   return kQuicFrameTypeSize + kQuicEntropyHashSize +
 178       largest_observed_length + kQuicDeltaTimeLargestObservedSize;
 179 }
 180
 181 // static
 182 size_t QuicFramer::GetStopWaitingFrameSize(
 183     QuicSequenceNumberLength sequence_number_length) {
 184   return kQuicFrameTypeSize + kQuicEntropyHashSize +
 185       sequence_number_length;
 186 }
 187
 188 // static
 189 size_t QuicFramer::GetMinRstStreamFrameSize() {
 190   return kQuicFrameTypeSize + kQuicMaxStreamIdSize +
 191       kQuicMaxStreamOffsetSize + kQuicErrorCodeSize +
 192       kQuicErrorDetailsLengthSize;
 193 }
 194
 195 // static
 196 size_t QuicFramer::GetRstStreamFrameSize() {
 197   return kQuicFrameTypeSize + kQuicMaxStreamIdSize + kQuicMaxStreamOffsetSize +
 198          kQuicErrorCodeSize;
 199 }
 200
 201 // static
 202 size_t QuicFramer::GetMinConnectionCloseFrameSize() {
 203   return kQuicFrameTypeSize + kQuicErrorCodeSize + kQuicErrorDetailsLengthSize;
 204 }
 205
 206 // static
 207 size_t QuicFramer::GetMinGoAwayFrameSize() {
 208   return kQuicFrameTypeSize + kQuicErrorCodeSize + kQuicErrorDetailsLengthSize +
 209       kQuicMaxStreamIdSize;
 210 }
 211
 212 // static
 213 size_t QuicFramer::GetWindowUpdateFrameSize() {
 214   return kQuicFrameTypeSize + kQuicMaxStreamIdSize + kQuicMaxStreamOffsetSize;
 215 }
 216
 217 // static
 218 size_t QuicFramer::GetBlockedFrameSize() {
 219   return kQuicFrameTypeSize + kQuicMaxStreamIdSize;
 220 }
 221
 222 // static
 223 size_t QuicFramer::GetStreamIdSize(QuicStreamId stream_id) {
 224   // Sizes are 1 through 4 bytes.
 225   for (int i = 1; i <= 4; ++i) {
 226     stream_id >>= 8;
 227     if (stream_id == 0) {
 228       return i;
 229     }
 230   }
 231   LOG(DFATAL) << "Failed to determine StreamIDSize.";
 232   return 4;
 233 }
 234
 235 // static
 236 size_t QuicFramer::GetStreamOffsetSize(QuicStreamOffset offset) {
 237   // 0 is a special case.
 238   if (offset == 0) {
 239     return 0;
 240   }
 241   // 2 through 8 are the remaining sizes.
 242   offset >>= 8;
 243   for (int i = 2; i <= 8; ++i) {
 244     offset >>= 8;
 245     if (offset == 0) {
 246       return i;
 247     }
 248   }
 249   LOG(DFATAL) << "Failed to determine StreamOffsetSize.";
 250   return 8;
 251 }
 252
 253 // static
 254 size_t QuicFramer::GetVersionNegotiationPacketSize(size_t number_versions) {
 255   return kPublicFlagsSize + PACKET_8BYTE_CONNECTION_ID +
 256       number_versions * kQuicVersionSize;
 257 }
 258
 259 bool QuicFramer::IsSupportedVersion(const QuicVersion version) const {
 260   for (size_t i = 0; i < supported_versions_.size(); ++i) {
 261     if (version == supported_versions_[i]) {
 262       return true;
 263     }
 264   }
 265   return false;
 266 }
 267
 268 size_t QuicFramer::GetSerializedFrameLength(
 269     const QuicFrame& frame,
 270     size_t free_bytes,
 271     bool first_frame,
 272     bool last_frame,
 273     InFecGroup is_in_fec_group,
 274     QuicSequenceNumberLength sequence_number_length) {
 275   // Prevent a rare crash reported in b/19458523.
 276   if (frame.stream_frame == nullptr) {
 277     LOG(DFATAL) << "Cannot compute the length of a null frame. "
 278                 << "type:" << frame.type << "free_bytes:" << free_bytes
 279                 << " first_frame:" << first_frame
 280                 << " last_frame:" << last_frame
 281                 << " is_in_fec:" << is_in_fec_group
 282                 << " seq num length:" << sequence_number_length;
 283     set_error(QUIC_INTERNAL_ERROR);
 284     visitor_->OnError(this);
 285     return false;
 286   }
 287   if (frame.type == PADDING_FRAME) {
 288     // PADDING implies end of packet.
 289     return free_bytes;
 290   }
 291   size_t frame_len =
 292       ComputeFrameLength(frame, last_frame, is_in_fec_group,
 293                          sequence_number_length);
 294   if (frame_len <= free_bytes) {
 295     // Frame fits within packet. Note that acks may be truncated.
 296     return frame_len;
 297   }
 298   // Only truncate the first frame in a packet, so if subsequent ones go
 299   // over, stop including more frames.
 300   if (!first_frame) {
 301     return 0;
 302   }
 303   bool can_truncate =
 304       frame.type == ACK_FRAME &&
 305       free_bytes >= GetMinAckFrameSize(PACKET_6BYTE_SEQUENCE_NUMBER);
 306   if (can_truncate) {
 307     // Truncate the frame so the packet will not exceed kMaxPacketSize.
 308     // Note that we may not use every byte of the writer in this case.
 309     DVLOG(1) << "Truncating large frame, free bytes: " << free_bytes;
 310     return free_bytes;
 311   }
 312   if (!FLAGS_quic_allow_oversized_packets_for_test) {
 313     return 0;
 314   }
 315   LOG(DFATAL) << "Packet size too small to fit frame.";
 316   return frame_len;
 317 }
 318
 319 QuicFramer::AckFrameInfo::AckFrameInfo() : max_delta(0) {}
 320
 321 QuicFramer::AckFrameInfo::~AckFrameInfo() {}
 322
 323 // static
 324 QuicPacketEntropyHash QuicFramer::GetPacketEntropyHash(
 325     const QuicPacketHeader& header) {
 326   return header.entropy_flag << (header.packet_sequence_number % 8);
 327 }
 328
 329 QuicPacket* QuicFramer::BuildDataPacket(const QuicPacketHeader& header,
 330                                         const QuicFrames& frames,
 331                                         char* buffer,
 332                                         size_t packet_length) {
 333   QuicDataWriter writer(packet_length, buffer);
 334   if (!AppendPacketHeader(header, &writer)) {
 335     LOG(DFATAL) << "AppendPacketHeader failed";
 336     return nullptr;
 337   }
 338
 339   size_t i = 0;
 340   for (const QuicFrame& frame : frames) {
 341     // Determine if we should write stream frame length in header.
 342     const bool no_stream_frame_length =
 343         (header.is_in_fec_group == NOT_IN_FEC_GROUP) &&
 344         (i == frames.size() - 1);
 345     if (!AppendTypeByte(frame, no_stream_frame_length, &writer)) {
 346       LOG(DFATAL) << "AppendTypeByte failed";
 347       return nullptr;
 348     }
 349
 350     switch (frame.type) {
 351       case PADDING_FRAME:
 352         writer.WritePadding();
 353         break;
 354       case STREAM_FRAME:
 355         if (!AppendStreamFrame(
 356             *frame.stream_frame, no_stream_frame_length, &writer)) {
 357           LOG(DFATAL) << "AppendStreamFrame failed";
 358           return nullptr;
 359         }
 360         break;
 361       case ACK_FRAME:
 362         if (!AppendAckFrameAndTypeByte(
 363                 header, *frame.ack_frame, &writer)) {
 364           LOG(DFATAL) << "AppendAckFrameAndTypeByte failed";
 365           return nullptr;
 366         }
 367         break;
 368       case STOP_WAITING_FRAME:
 369         if (!AppendStopWaitingFrame(
 370                 header, *frame.stop_waiting_frame, &writer)) {
 371           LOG(DFATAL) << "AppendStopWaitingFrame failed";
 372           return nullptr;
 373         }
 374         break;
 375       case PING_FRAME:
 376         // Ping has no payload.
 377         break;
 378       case RST_STREAM_FRAME:
 379         if (!AppendRstStreamFrame(*frame.rst_stream_frame, &writer)) {
 380           LOG(DFATAL) << "AppendRstStreamFrame failed";
 381           return nullptr;
 382         }
 383         break;
 384       case CONNECTION_CLOSE_FRAME:
 385         if (!AppendConnectionCloseFrame(
 386                 *frame.connection_close_frame, &writer)) {
 387           LOG(DFATAL) << "AppendConnectionCloseFrame failed";
 388           return nullptr;
 389         }
 390         break;
 391       case GOAWAY_FRAME:
 392         if (!AppendGoAwayFrame(*frame.goaway_frame, &writer)) {
 393           LOG(DFATAL) << "AppendGoAwayFrame failed";
 394           return nullptr;
 395         }
 396         break;
 397       case WINDOW_UPDATE_FRAME:
 398         if (!AppendWindowUpdateFrame(*frame.window_update_frame, &writer)) {
 399           LOG(DFATAL) << "AppendWindowUpdateFrame failed";
 400           return nullptr;
 401         }
 402         break;
 403       case BLOCKED_FRAME:
 404         if (!AppendBlockedFrame(*frame.blocked_frame, &writer)) {
 405           LOG(DFATAL) << "AppendBlockedFrame failed";
 406           return nullptr;
 407         }
 408         break;
 409       default:
 410         RaiseError(QUIC_INVALID_FRAME_DATA);
 411         LOG(DFATAL) << "QUIC_INVALID_FRAME_DATA";
 412         return nullptr;
 413     }
 414     ++i;
 415   }
 416
 417   QuicPacket* packet =
 418       new QuicPacket(writer.data(), writer.length(), false,
 419                      header.public_header.connection_id_length,
 420                      header.public_header.version_flag,
 421                      header.public_header.sequence_number_length);
 422
 423   return packet;
 424 }
 425
 426 QuicPacket* QuicFramer::BuildFecPacket(const QuicPacketHeader& header,
 427                                        const QuicFecData& fec) {
 428   DCHECK_EQ(IN_FEC_GROUP, header.is_in_fec_group);
 429   DCHECK_NE(0u, header.fec_group);
 430   size_t len = GetPacketHeaderSize(header);
 431   len += fec.redundancy.length();
 432
 433   scoped_ptr<char[]> buffer(new char[len]);
 434   QuicDataWriter writer(len, buffer.get());
 435   if (!AppendPacketHeader(header, &writer)) {
 436     LOG(DFATAL) << "AppendPacketHeader failed";
 437     return nullptr;
 438   }
 439
 440   if (!writer.WriteBytes(fec.redundancy.data(), fec.redundancy.length())) {
 441     LOG(DFATAL) << "Failed to add FEC";
 442     return nullptr;
 443   }
 444
 445   return new QuicPacket(buffer.release(), len, true,
 446                         header.public_header.connection_id_length,
 447                         header.public_header.version_flag,
 448                         header.public_header.sequence_number_length);
 449 }
 450
 451 // static
 452 QuicEncryptedPacket* QuicFramer::BuildPublicResetPacket(
 453     const QuicPublicResetPacket& packet) {
 454   DCHECK(packet.public_header.reset_flag);
 455
 456   CryptoHandshakeMessage reset;
 457   reset.set_tag(kPRST);
 458   reset.SetValue(kRNON, packet.nonce_proof);
 459   reset.SetValue(kRSEQ, packet.rejected_sequence_number);
 460   if (!packet.client_address.address().empty()) {
 461     // packet.client_address is non-empty.
 462     QuicSocketAddressCoder address_coder(packet.client_address);
 463     string serialized_address = address_coder.Encode();
 464     if (serialized_address.empty()) {
 465       return nullptr;
 466     }
 467     reset.SetStringPiece(kCADR, serialized_address);
 468   }
 469   const QuicData& reset_serialized = reset.GetSerialized();
 470
 471   size_t len =
 472       kPublicFlagsSize + PACKET_8BYTE_CONNECTION_ID + reset_serialized.length();
 473   scoped_ptr<char[]> buffer(new char[len]);
 474   QuicDataWriter writer(len, buffer.get());
 475
 476   uint8 flags = static_cast<uint8>(PACKET_PUBLIC_FLAGS_RST |
 477                                    PACKET_PUBLIC_FLAGS_8BYTE_CONNECTION_ID);
 478   if (!writer.WriteUInt8(flags)) {
 479     return nullptr;
 480   }
 481
 482   if (!writer.WriteUInt64(packet.public_header.connection_id)) {
 483     return nullptr;
 484   }
 485
 486   if (!writer.WriteBytes(reset_serialized.data(), reset_serialized.length())) {
 487     return nullptr;
 488   }
 489
 490   return new QuicEncryptedPacket(buffer.release(), len, true);
 491 }
 492
 493 QuicEncryptedPacket* QuicFramer::BuildVersionNegotiationPacket(
 494     const QuicPacketPublicHeader& header,
 495     const QuicVersionVector& supported_versions) {
 496   DCHECK(header.version_flag);
 497   size_t len = GetVersionNegotiationPacketSize(supported_versions.size());
 498   scoped_ptr<char[]> buffer(new char[len]);
 499   QuicDataWriter writer(len, buffer.get());
 500
 501   uint8 flags = static_cast<uint8>(PACKET_PUBLIC_FLAGS_VERSION |
 502                                    PACKET_PUBLIC_FLAGS_8BYTE_CONNECTION_ID);
 503   if (!writer.WriteUInt8(flags)) {
 504     return nullptr;
 505   }
 506
 507   if (!writer.WriteUInt64(header.connection_id)) {
 508     return nullptr;
 509   }
 510
 511   for (size_t i = 0; i < supported_versions.size(); ++i) {
 512     if (!writer.WriteUInt32(QuicVersionToQuicTag(supported_versions[i]))) {
 513       return nullptr;
 514     }
 515   }
 516
 517   return new QuicEncryptedPacket(buffer.release(), len, true);
 518 }
 519
 520 bool QuicFramer::ProcessPacket(const QuicEncryptedPacket& packet) {
 521   DCHECK(!reader_.get());
 522   reader_.reset(new QuicDataReader(packet.data(), packet.length()));
 523
 524   visitor_->OnPacket();
 525
 526   // First parse the public header.
 527   QuicPacketPublicHeader public_header;
 528   if (!ProcessPublicHeader(&public_header)) {
 529     DLOG(WARNING) << "Unable to process public header.";
 530     DCHECK_NE("", detailed_error_);
 531     return RaiseError(QUIC_INVALID_PACKET_HEADER);
 532   }
 533
 534   if (!visitor_->OnUnauthenticatedPublicHeader(public_header)) {
 535     // The visitor suppresses further processing of the packet.
 536     reader_.reset(nullptr);
 537     return true;
 538   }
 539
 540   if (perspective_ == Perspective::IS_SERVER && public_header.version_flag &&
 541       public_header.versions[0] != quic_version_) {
 542     if (!visitor_->OnProtocolVersionMismatch(public_header.versions[0])) {
 543       reader_.reset(nullptr);
 544       return true;
 545     }
 546   }
 547
 548   bool rv;
 549   if (perspective_ == Perspective::IS_CLIENT && public_header.version_flag) {
 550     rv = ProcessVersionNegotiationPacket(&public_header);
 551   } else if (public_header.reset_flag) {
 552     rv = ProcessPublicResetPacket(public_header);
 553   } else if (packet.length() <= kMaxPacketSize) {
 554     char buffer[kMaxPacketSize];
 555     rv = ProcessDataPacket(public_header, packet, buffer, kMaxPacketSize);
 556   } else {
 557     scoped_ptr<char[]> large_buffer(new char[packet.length()]);
 558     rv = ProcessDataPacket(public_header, packet, large_buffer.get(),
 559                            packet.length());
 560     LOG_IF(DFATAL, rv) << "QUIC should never successfully process packets "
 561                        << "larger than kMaxPacketSize. packet size:"
 562                        << packet.length();
 563   }
 564
 565   reader_.reset(nullptr);
 566   return rv;
 567 }
 568
 569 bool QuicFramer::ProcessVersionNegotiationPacket(
 570     QuicPacketPublicHeader* public_header) {
 571   DCHECK_EQ(Perspective::IS_CLIENT, perspective_);
 572   // Try reading at least once to raise error if the packet is invalid.
 573   do {
 574     QuicTag version;
 575     if (!reader_->ReadBytes(&version, kQuicVersionSize)) {
 576       set_detailed_error("Unable to read supported version in negotiation.");
 577       return RaiseError(QUIC_INVALID_VERSION_NEGOTIATION_PACKET);
 578     }
 579     public_header->versions.push_back(QuicTagToQuicVersion(version));
 580   } while (!reader_->IsDoneReading());
 581
 582   visitor_->OnVersionNegotiationPacket(*public_header);
 583   return true;
 584 }
 585
 586 bool QuicFramer::ProcessDataPacket(const QuicPacketPublicHeader& public_header,
 587                                    const QuicEncryptedPacket& packet,
 588                                    char* decrypted_buffer,
 589                                    size_t buffer_length) {
 590   QuicPacketHeader header(public_header);
 591   if (!ProcessPacketHeader(&header, packet, decrypted_buffer, buffer_length)) {
 592     DLOG(WARNING) << "Unable to process packet header.  Stopping parsing.";
 593     return false;
 594   }
 595
 596   if (!visitor_->OnPacketHeader(header)) {
 597     // The visitor suppresses further processing of the packet.
 598     return true;
 599   }
 600
 601   if (packet.length() > kMaxPacketSize) {
 602     DLOG(WARNING) << "Packet too large: " << packet.length();
 603     return RaiseError(QUIC_PACKET_TOO_LARGE);
 604   }
 605
 606   // Handle the payload.
 607   if (!header.fec_flag) {
 608     if (header.is_in_fec_group == IN_FEC_GROUP) {
 609       StringPiece payload = reader_->PeekRemainingPayload();
 610       visitor_->OnFecProtectedPayload(payload);
 611     }
 612     if (!ProcessFrameData(header)) {
 613       DCHECK_NE(QUIC_NO_ERROR, error_);  // ProcessFrameData sets the error.
 614       DLOG(WARNING) << "Unable to process frame data.";
 615       return false;
 616     }
 617   } else {
 618     QuicFecData fec_data;
 619     fec_data.fec_group = header.fec_group;
 620     fec_data.redundancy = reader_->ReadRemainingPayload();
 621     visitor_->OnFecData(fec_data);
 622   }
 623
 624   visitor_->OnPacketComplete();
 625   return true;
 626 }
 627
 628 bool QuicFramer::ProcessPublicResetPacket(
 629     const QuicPacketPublicHeader& public_header) {
 630   QuicPublicResetPacket packet(public_header);
 631
 632   scoped_ptr<CryptoHandshakeMessage> reset(
 633       CryptoFramer::ParseMessage(reader_->ReadRemainingPayload()));
 634   if (!reset.get()) {
 635     set_detailed_error("Unable to read reset message.");
 636     return RaiseError(QUIC_INVALID_PUBLIC_RST_PACKET);
 637   }
 638   if (reset->tag() != kPRST) {
 639     set_detailed_error("Incorrect message tag.");
 640     return RaiseError(QUIC_INVALID_PUBLIC_RST_PACKET);
 641   }
 642
 643   if (reset->GetUint64(kRNON, &packet.nonce_proof) != QUIC_NO_ERROR) {
 644     set_detailed_error("Unable to read nonce proof.");
 645     return RaiseError(QUIC_INVALID_PUBLIC_RST_PACKET);
 646   }
 647   // TODO(satyamshekhar): validate nonce to protect against DoS.
 648
 649   if (reset->GetUint64(kRSEQ, &packet.rejected_sequence_number) !=
 650       QUIC_NO_ERROR) {
 651     set_detailed_error("Unable to read rejected sequence number.");
 652     return RaiseError(QUIC_INVALID_PUBLIC_RST_PACKET);
 653   }
 654
 655   StringPiece address;
 656   if (reset->GetStringPiece(kCADR, &address)) {
 657     QuicSocketAddressCoder address_coder;
 658     if (address_coder.Decode(address.data(), address.length())) {
 659       packet.client_address = IPEndPoint(address_coder.ip(),
 660                                          address_coder.port());
 661     }
 662   }
 663
 664   visitor_->OnPublicResetPacket(packet);
 665   return true;
 666 }
 667
 668 bool QuicFramer::ProcessRevivedPacket(QuicPacketHeader* header,
 669                                       StringPiece payload) {
 670   DCHECK(!reader_.get());
 671
 672   visitor_->OnRevivedPacket();
 673
 674   header->entropy_hash = GetPacketEntropyHash(*header);
 675
 676   if (!visitor_->OnPacketHeader(*header)) {
 677     return true;
 678   }
 679
 680   if (payload.length() > kMaxPacketSize) {
 681     set_detailed_error("Revived packet too large.");
 682     return RaiseError(QUIC_PACKET_TOO_LARGE);
 683   }
 684
 685   reader_.reset(new QuicDataReader(payload.data(), payload.length()));
 686   if (!ProcessFrameData(*header)) {
 687     DCHECK_NE(QUIC_NO_ERROR, error_);  // ProcessFrameData sets the error.
 688     DLOG(WARNING) << "Unable to process frame data.";
 689     return false;
 690   }
 691
 692   visitor_->OnPacketComplete();
 693   reader_.reset(nullptr);
 694   return true;
 695 }
 696
 697 bool QuicFramer::AppendPacketHeader(const QuicPacketHeader& header,
 698                                     QuicDataWriter* writer) {
 699   DVLOG(1) << "Appending header: " << header;
 700   DCHECK(header.fec_group > 0 || header.is_in_fec_group == NOT_IN_FEC_GROUP);
 701   uint8 public_flags = 0;
 702   if (header.public_header.reset_flag) {
 703     public_flags |= PACKET_PUBLIC_FLAGS_RST;
 704   }
 705   if (header.public_header.version_flag) {
 706     public_flags |= PACKET_PUBLIC_FLAGS_VERSION;
 707   }
 708
 709   public_flags |=
 710       GetSequenceNumberFlags(header.public_header.sequence_number_length)
 711           << kPublicHeaderSequenceNumberShift;
 712
 713   switch (header.public_header.connection_id_length) {
 714     case PACKET_0BYTE_CONNECTION_ID:
 715       if (!writer->WriteUInt8(
 716               public_flags | PACKET_PUBLIC_FLAGS_0BYTE_CONNECTION_ID)) {
 717         return false;
 718       }
 719       break;
 720     case PACKET_1BYTE_CONNECTION_ID:
 721       if (!writer->WriteUInt8(
 722               public_flags | PACKET_PUBLIC_FLAGS_1BYTE_CONNECTION_ID)) {
 723          return false;
 724       }
 725       if (!writer->WriteUInt8(
 726               header.public_header.connection_id & k1ByteConnectionIdMask)) {
 727         return false;
 728       }
 729       break;
 730     case PACKET_4BYTE_CONNECTION_ID:
 731       if (!writer->WriteUInt8(
 732               public_flags | PACKET_PUBLIC_FLAGS_4BYTE_CONNECTION_ID)) {
 733          return false;
 734       }
 735       if (!writer->WriteUInt32(
 736               header.public_header.connection_id & k4ByteConnectionIdMask)) {
 737         return false;
 738       }
 739       break;
 740     case PACKET_8BYTE_CONNECTION_ID:
 741       if (!writer->WriteUInt8(
 742               public_flags | PACKET_PUBLIC_FLAGS_8BYTE_CONNECTION_ID)) {
 743         return false;
 744       }
 745       if (!writer->WriteUInt64(header.public_header.connection_id)) {
 746         return false;
 747       }
 748       break;
 749   }
 750   last_serialized_connection_id_ = header.public_header.connection_id;
 751
 752   if (header.public_header.version_flag) {
 753     DCHECK_EQ(Perspective::IS_CLIENT, perspective_);
 754     QuicTag tag = QuicVersionToQuicTag(quic_version_);
 755     writer->WriteUInt32(tag);
 756     DVLOG(1) << "version = " << quic_version_ << ", tag = '"
 757              << QuicUtils::TagToString(tag) << "'";
 758   }
 759
 760   if (!AppendPacketSequenceNumber(header.public_header.sequence_number_length,
 761                                   header.packet_sequence_number, writer)) {
 762     return false;
 763   }
 764
 765   uint8 private_flags = 0;
 766   if (header.entropy_flag) {
 767     private_flags |= PACKET_PRIVATE_FLAGS_ENTROPY;
 768   }
 769   if (header.is_in_fec_group == IN_FEC_GROUP) {
 770     private_flags |= PACKET_PRIVATE_FLAGS_FEC_GROUP;
 771   }
 772   if (header.fec_flag) {
 773     private_flags |= PACKET_PRIVATE_FLAGS_FEC;
 774   }
 775   if (!writer->WriteUInt8(private_flags)) {
 776     return false;
 777   }
 778
 779   // The FEC group number is the sequence number of the first fec
 780   // protected packet, or 0 if this packet is not protected.
 781   if (header.is_in_fec_group == IN_FEC_GROUP) {
 782     DCHECK_LE(header.fec_group, header.packet_sequence_number);
 783     DCHECK_LT(header.packet_sequence_number - header.fec_group, 255u);
 784     // Offset from the current packet sequence number to the first fec
 785     // protected packet.
 786     uint8 first_fec_protected_packet_offset =
 787         static_cast<uint8>(header.packet_sequence_number - header.fec_group);
 788     if (!writer->WriteBytes(&first_fec_protected_packet_offset, 1)) {
 789       return false;
 790     }
 791   }
 792
 793   return true;
 794 }
 795
 796 const QuicTime::Delta QuicFramer::CalculateTimestampFromWire(
 797     uint32 time_delta_us) {
 798   // The new time_delta might have wrapped to the next epoch, or it
 799   // might have reverse wrapped to the previous epoch, or it might
 800   // remain in the same epoch. Select the time closest to the previous
 801   // time.
 802   //
 803   // epoch_delta is the delta between epochs. A delta is 4 bytes of
 804   // microseconds.
 805   const uint64 epoch_delta = UINT64_C(1) << 32;
 806   uint64 epoch = last_timestamp_.ToMicroseconds() & ~(epoch_delta - 1);
 807   // Wrapping is safe here because a wrapped value will not be ClosestTo below.
 808   uint64 prev_epoch = epoch - epoch_delta;
 809   uint64 next_epoch = epoch + epoch_delta;
 810
 811   uint64 time = ClosestTo(last_timestamp_.ToMicroseconds(),
 812                           epoch + time_delta_us,
 813                           ClosestTo(last_timestamp_.ToMicroseconds(),
 814                                     prev_epoch + time_delta_us,
 815                                     next_epoch + time_delta_us));
 816
 817   return QuicTime::Delta::FromMicroseconds(time);
 818 }
 819
 820 QuicPacketSequenceNumber QuicFramer::CalculatePacketSequenceNumberFromWire(
 821     QuicSequenceNumberLength sequence_number_length,
 822     QuicPacketSequenceNumber packet_sequence_number) const {
 823   // The new sequence number might have wrapped to the next epoch, or
 824   // it might have reverse wrapped to the previous epoch, or it might
 825   // remain in the same epoch.  Select the sequence number closest to the
 826   // next expected sequence number, the previous sequence number plus 1.
 827
 828   // epoch_delta is the delta between epochs the sequence number was serialized
 829   // with, so the correct value is likely the same epoch as the last sequence
 830   // number or an adjacent epoch.
 831   const QuicPacketSequenceNumber epoch_delta =
 832       UINT64_C(1) << (8 * sequence_number_length);
 833   QuicPacketSequenceNumber next_sequence_number = last_sequence_number_ + 1;
 834   QuicPacketSequenceNumber epoch = last_sequence_number_ & ~(epoch_delta - 1);
 835   QuicPacketSequenceNumber prev_epoch = epoch - epoch_delta;
 836   QuicPacketSequenceNumber next_epoch = epoch + epoch_delta;
 837
 838   return ClosestTo(next_sequence_number,
 839                    epoch + packet_sequence_number,
 840                    ClosestTo(next_sequence_number,
 841                              prev_epoch + packet_sequence_number,
 842                              next_epoch + packet_sequence_number));
 843 }
 844
 845 bool QuicFramer::ProcessPublicHeader(
 846     QuicPacketPublicHeader* public_header) {
 847   uint8 public_flags;
 848   if (!reader_->ReadBytes(&public_flags, 1)) {
 849     set_detailed_error("Unable to read public flags.");
 850     return false;
 851   }
 852
 853   public_header->reset_flag = (public_flags & PACKET_PUBLIC_FLAGS_RST) != 0;
 854   public_header->version_flag =
 855       (public_flags & PACKET_PUBLIC_FLAGS_VERSION) != 0;
 856
 857   if (validate_flags_ &&
 858       !public_header->version_flag && public_flags > PACKET_PUBLIC_FLAGS_MAX) {
 859     set_detailed_error("Illegal public flags value.");
 860     return false;
 861   }
 862
 863   if (public_header->reset_flag && public_header->version_flag) {
 864     set_detailed_error("Got version flag in reset packet");
 865     return false;
 866   }
 867
 868   switch (public_flags & PACKET_PUBLIC_FLAGS_8BYTE_CONNECTION_ID) {
 869     case PACKET_PUBLIC_FLAGS_8BYTE_CONNECTION_ID:
 870       if (!reader_->ReadUInt64(&public_header->connection_id)) {
 871         set_detailed_error("Unable to read ConnectionId.");
 872         return false;
 873       }
 874       public_header->connection_id_length = PACKET_8BYTE_CONNECTION_ID;
 875       break;
 876     case PACKET_PUBLIC_FLAGS_4BYTE_CONNECTION_ID:
 877       // If the connection_id is truncated, expect to read the last serialized
 878       // connection_id.
 879       if (!reader_->ReadBytes(&public_header->connection_id,
 880                               PACKET_4BYTE_CONNECTION_ID)) {
 881         set_detailed_error("Unable to read ConnectionId.");
 882         return false;
 883       }
 884       if (last_serialized_connection_id_ &&
 885           (public_header->connection_id & k4ByteConnectionIdMask) !=
 886           (last_serialized_connection_id_ & k4ByteConnectionIdMask)) {
 887         set_detailed_error("Truncated 4 byte ConnectionId does not match "
 888                            "previous connection_id.");
 889         return false;
 890       }
 891       public_header->connection_id_length = PACKET_4BYTE_CONNECTION_ID;
 892       public_header->connection_id = last_serialized_connection_id_;
 893       break;
 894     case PACKET_PUBLIC_FLAGS_1BYTE_CONNECTION_ID:
 895       if (!reader_->ReadBytes(&public_header->connection_id,
 896                               PACKET_1BYTE_CONNECTION_ID)) {
 897         set_detailed_error("Unable to read ConnectionId.");
 898         return false;
 899       }
 900       if (last_serialized_connection_id_ &&
 901           (public_header->connection_id & k1ByteConnectionIdMask) !=
 902           (last_serialized_connection_id_ & k1ByteConnectionIdMask)) {
 903         set_detailed_error("Truncated 1 byte ConnectionId does not match "
 904                            "previous connection_id.");
 905         return false;
 906       }
 907       public_header->connection_id_length = PACKET_1BYTE_CONNECTION_ID;
 908       public_header->connection_id = last_serialized_connection_id_;
 909       break;
 910     case PACKET_PUBLIC_FLAGS_0BYTE_CONNECTION_ID:
 911       public_header->connection_id_length = PACKET_0BYTE_CONNECTION_ID;
 912       public_header->connection_id = last_serialized_connection_id_;
 913       break;
 914   }
 915
 916   public_header->sequence_number_length =
 917       ReadSequenceNumberLength(
 918           public_flags >> kPublicHeaderSequenceNumberShift);
 919
 920   // Read the version only if the packet is from the client.
 921   // version flag from the server means version negotiation packet.
 922   if (public_header->version_flag && perspective_ == Perspective::IS_SERVER) {
 923     QuicTag version_tag;
 924     if (!reader_->ReadUInt32(&version_tag)) {
 925       set_detailed_error("Unable to read protocol version.");
 926       return false;
 927     }
 928
 929     // If the version from the new packet is the same as the version of this
 930     // framer, then the public flags should be set to something we understand.
 931     // If not, this raises an error.
 932     QuicVersion version = QuicTagToQuicVersion(version_tag);
 933     if (version == quic_version_ && public_flags > PACKET_PUBLIC_FLAGS_MAX) {
 934       set_detailed_error("Illegal public flags value.");
 935       return false;
 936     }
 937     public_header->versions.push_back(version);
 938   }
 939   return true;
 940 }
 941
 942 // static
 943 QuicSequenceNumberLength QuicFramer::GetMinSequenceNumberLength(
 944     QuicPacketSequenceNumber sequence_number) {
 945   if (sequence_number < 1 << (PACKET_1BYTE_SEQUENCE_NUMBER * 8)) {
 946     return PACKET_1BYTE_SEQUENCE_NUMBER;
 947   } else if (sequence_number < 1 << (PACKET_2BYTE_SEQUENCE_NUMBER * 8)) {
 948     return PACKET_2BYTE_SEQUENCE_NUMBER;
 949   } else if (sequence_number <
 950              UINT64_C(1) << (PACKET_4BYTE_SEQUENCE_NUMBER * 8)) {
 951     return PACKET_4BYTE_SEQUENCE_NUMBER;
 952   } else {
 953     return PACKET_6BYTE_SEQUENCE_NUMBER;
 954   }
 955 }
 956
 957 // static
 958 uint8 QuicFramer::GetSequenceNumberFlags(
 959     QuicSequenceNumberLength sequence_number_length) {
 960   switch (sequence_number_length) {
 961     case PACKET_1BYTE_SEQUENCE_NUMBER:
 962       return PACKET_FLAGS_1BYTE_SEQUENCE;
 963     case PACKET_2BYTE_SEQUENCE_NUMBER:
 964       return PACKET_FLAGS_2BYTE_SEQUENCE;
 965     case PACKET_4BYTE_SEQUENCE_NUMBER:
 966       return PACKET_FLAGS_4BYTE_SEQUENCE;
 967     case PACKET_6BYTE_SEQUENCE_NUMBER:
 968       return PACKET_FLAGS_6BYTE_SEQUENCE;
 969     default:
 970       LOG(DFATAL) << "Unreachable case statement.";
 971       return PACKET_FLAGS_6BYTE_SEQUENCE;
 972   }
 973 }
 974
 975 // static
 976 QuicFramer::AckFrameInfo QuicFramer::GetAckFrameInfo(
 977     const QuicAckFrame& frame) {
 978   AckFrameInfo ack_info;
 979   if (frame.missing_packets.empty()) {
 980     return ack_info;
 981   }
 982   DCHECK_GE(frame.largest_observed, *frame.missing_packets.rbegin());
 983   size_t cur_range_length = 0;
 984   SequenceNumberSet::const_iterator iter = frame.missing_packets.begin();
 985   QuicPacketSequenceNumber last_missing = *iter;
 986   ++iter;
 987   for (; iter != frame.missing_packets.end(); ++iter) {
 988     if (cur_range_length < numeric_limits<uint8>::max() &&
 989         *iter == (last_missing + 1)) {
 990       ++cur_range_length;
 991     } else {
 992       ack_info.nack_ranges[last_missing - cur_range_length] =
 993           static_cast<uint8>(cur_range_length);
 994       cur_range_length = 0;
 995     }
 996     ack_info.max_delta = max(ack_info.max_delta, *iter - last_missing);
 997     last_missing = *iter;
 998   }
 999   // Include the last nack range.
1000   ack_info.nack_ranges[last_missing - cur_range_length] =
1001       static_cast<uint8>(cur_range_length);
1002   // Include the range to the largest observed.
1003   ack_info.max_delta =
1004       max(ack_info.max_delta, frame.largest_observed - last_missing);
1005   return ack_info;
1006 }
1007
1008 bool QuicFramer::ProcessPacketHeader(QuicPacketHeader* header,
1009                                      const QuicEncryptedPacket& packet,
1010                                      char* decrypted_buffer,
1011                                      size_t buffer_length) {
1012   if (!ProcessPacketSequenceNumber(header->public_header.sequence_number_length,
1013                                    &header->packet_sequence_number)) {
1014     set_detailed_error("Unable to read sequence number.");
1015     return RaiseError(QUIC_INVALID_PACKET_HEADER);
1016   }
1017
1018   if (header->packet_sequence_number == 0u) {
1019     set_detailed_error("Packet sequence numbers cannot be 0.");
1020     return RaiseError(QUIC_INVALID_PACKET_HEADER);
1021   }
1022
1023   if (!visitor_->OnUnauthenticatedHeader(*header)) {
1024     return false;
1025   }
1026
1027   if (!DecryptPayload(*header, packet, decrypted_buffer, buffer_length)) {
1028     set_detailed_error("Unable to decrypt payload.");
1029     return RaiseError(QUIC_DECRYPTION_FAILURE);
1030   }
1031
1032   uint8 private_flags;
1033   if (!reader_->ReadBytes(&private_flags, 1)) {
1034     set_detailed_error("Unable to read private flags.");
1035     return RaiseError(QUIC_INVALID_PACKET_HEADER);
1036   }
1037
1038   if (private_flags > PACKET_PRIVATE_FLAGS_MAX) {
1039     set_detailed_error("Illegal private flags value.");
1040     return RaiseError(QUIC_INVALID_PACKET_HEADER);
1041   }
1042
1043   header->entropy_flag = (private_flags & PACKET_PRIVATE_FLAGS_ENTROPY) != 0;
1044   header->fec_flag = (private_flags & PACKET_PRIVATE_FLAGS_FEC) != 0;
1045
1046   if ((private_flags & PACKET_PRIVATE_FLAGS_FEC_GROUP) != 0) {
1047     header->is_in_fec_group = IN_FEC_GROUP;
1048     uint8 first_fec_protected_packet_offset;
1049     if (!reader_->ReadBytes(&first_fec_protected_packet_offset, 1)) {
1050       set_detailed_error("Unable to read first fec protected packet offset.");
1051       return RaiseError(QUIC_INVALID_PACKET_HEADER);
1052     }
1053     if (first_fec_protected_packet_offset >= header->packet_sequence_number) {
1054       set_detailed_error("First fec protected packet offset must be less "
1055                          "than the sequence number.");
1056       return RaiseError(QUIC_INVALID_PACKET_HEADER);
1057     }
1058     header->fec_group =
1059         header->packet_sequence_number - first_fec_protected_packet_offset;
1060   }
1061
1062   header->entropy_hash = GetPacketEntropyHash(*header);
1063   // Set the last sequence number after we have decrypted the packet
1064   // so we are confident is not attacker controlled.
1065   last_sequence_number_ = header->packet_sequence_number;
1066   return true;
1067 }
1068
1069 bool QuicFramer::ProcessPacketSequenceNumber(
1070     QuicSequenceNumberLength sequence_number_length,
1071     QuicPacketSequenceNumber* sequence_number) {
1072   QuicPacketSequenceNumber wire_sequence_number = 0u;
1073   if (!reader_->ReadBytes(&wire_sequence_number, sequence_number_length)) {
1074     return false;
1075   }
1076
1077   // TODO(ianswett): Explore the usefulness of trying multiple sequence numbers
1078   // in case the first guess is incorrect.
1079   *sequence_number =
1080       CalculatePacketSequenceNumberFromWire(sequence_number_length,
1081                                             wire_sequence_number);
1082   return true;
1083 }
1084
1085 bool QuicFramer::ProcessFrameData(const QuicPacketHeader& header) {
1086   if (reader_->IsDoneReading()) {
1087     set_detailed_error("Packet has no frames.");
1088     return RaiseError(QUIC_MISSING_PAYLOAD);
1089   }
1090   while (!reader_->IsDoneReading()) {
1091     uint8 frame_type;
1092     if (!reader_->ReadBytes(&frame_type, 1)) {
1093       set_detailed_error("Unable to read frame type.");
1094       return RaiseError(QUIC_INVALID_FRAME_DATA);
1095     }
1096
1097     if (frame_type & kQuicFrameTypeSpecialMask) {
1098       // Stream Frame
1099       if (frame_type & kQuicFrameTypeStreamMask) {
1100         QuicStreamFrame frame;
1101         if (!ProcessStreamFrame(frame_type, &frame)) {
1102           return RaiseError(QUIC_INVALID_STREAM_DATA);
1103         }
1104         if (!visitor_->OnStreamFrame(frame)) {
1105           DVLOG(1) << "Visitor asked to stop further processing.";
1106           // Returning true since there was no parsing error.
1107           return true;
1108         }
1109         continue;
1110       }
1111
1112       // Ack Frame
1113       if (frame_type & kQuicFrameTypeAckMask) {
1114         QuicAckFrame frame;
1115         if (!ProcessAckFrame(frame_type, &frame)) {
1116           return RaiseError(QUIC_INVALID_ACK_DATA);
1117         }
1118         if (!visitor_->OnAckFrame(frame)) {
1119           DVLOG(1) << "Visitor asked to stop further processing.";
1120           // Returning true since there was no parsing error.
1121           return true;
1122         }
1123         continue;
1124       }
1125
1126       // This was a special frame type that did not match any
1127       // of the known ones. Error.
1128       set_detailed_error("Illegal frame type.");
1129       DLOG(WARNING) << "Illegal frame type: "
1130                     << static_cast<int>(frame_type);
1131       return RaiseError(QUIC_INVALID_FRAME_DATA);
1132     }
1133
1134     switch (frame_type) {
1135       case PADDING_FRAME:
1136         // We're done with the packet.
1137         return true;
1138
1139       case RST_STREAM_FRAME: {
1140         QuicRstStreamFrame frame;
1141         if (!ProcessRstStreamFrame(&frame)) {
1142           return RaiseError(QUIC_INVALID_RST_STREAM_DATA);
1143         }
1144         if (!visitor_->OnRstStreamFrame(frame)) {
1145           DVLOG(1) << "Visitor asked to stop further processing.";
1146           // Returning true since there was no parsing error.
1147           return true;
1148         }
1149         continue;
1150       }
1151
1152       case CONNECTION_CLOSE_FRAME: {
1153         QuicConnectionCloseFrame frame;
1154         if (!ProcessConnectionCloseFrame(&frame)) {
1155           return RaiseError(QUIC_INVALID_CONNECTION_CLOSE_DATA);
1156         }
1157
1158         if (!visitor_->OnConnectionCloseFrame(frame)) {
1159           DVLOG(1) << "Visitor asked to stop further processing.";
1160           // Returning true since there was no parsing error.
1161           return true;
1162         }
1163         continue;
1164       }
1165
1166       case GOAWAY_FRAME: {
1167         QuicGoAwayFrame goaway_frame;
1168         if (!ProcessGoAwayFrame(&goaway_frame)) {
1169           return RaiseError(QUIC_INVALID_GOAWAY_DATA);
1170         }
1171         if (!visitor_->OnGoAwayFrame(goaway_frame)) {
1172           DVLOG(1) << "Visitor asked to stop further processing.";
1173           // Returning true since there was no parsing error.
1174           return true;
1175         }
1176         continue;
1177       }
1178
1179       case WINDOW_UPDATE_FRAME: {
1180         QuicWindowUpdateFrame window_update_frame;
1181         if (!ProcessWindowUpdateFrame(&window_update_frame)) {
1182           return RaiseError(QUIC_INVALID_WINDOW_UPDATE_DATA);
1183         }
1184         if (!visitor_->OnWindowUpdateFrame(window_update_frame)) {
1185           DVLOG(1) << "Visitor asked to stop further processing.";
1186           // Returning true since there was no parsing error.
1187           return true;
1188         }
1189         continue;
1190       }
1191
1192       case BLOCKED_FRAME: {
1193         QuicBlockedFrame blocked_frame;
1194         if (!ProcessBlockedFrame(&blocked_frame)) {
1195           return RaiseError(QUIC_INVALID_BLOCKED_DATA);
1196         }
1197         if (!visitor_->OnBlockedFrame(blocked_frame)) {
1198           DVLOG(1) << "Visitor asked to stop further processing.";
1199           // Returning true since there was no parsing error.
1200           return true;
1201         }
1202         continue;
1203       }
1204
1205       case STOP_WAITING_FRAME: {
1206         QuicStopWaitingFrame stop_waiting_frame;
1207         if (!ProcessStopWaitingFrame(header, &stop_waiting_frame)) {
1208           return RaiseError(QUIC_INVALID_STOP_WAITING_DATA);
1209         }
1210         if (!visitor_->OnStopWaitingFrame(stop_waiting_frame)) {
1211           DVLOG(1) << "Visitor asked to stop further processing.";
1212           // Returning true since there was no parsing error.
1213           return true;
1214         }
1215         continue;
1216       }
1217       case PING_FRAME: {
1218         // Ping has no payload.
1219         QuicPingFrame ping_frame;
1220         if (!visitor_->OnPingFrame(ping_frame)) {
1221           DVLOG(1) << "Visitor asked to stop further processing.";
1222           // Returning true since there was no parsing error.
1223           return true;
1224         }
1225         continue;
1226       }
1227
1228       default:
1229         set_detailed_error("Illegal frame type.");
1230         DLOG(WARNING) << "Illegal frame type: "
1231                       << static_cast<int>(frame_type);
1232         return RaiseError(QUIC_INVALID_FRAME_DATA);
1233     }
1234   }
1235
1236   return true;
1237 }
1238
1239 bool QuicFramer::ProcessStreamFrame(uint8 frame_type,
1240                                     QuicStreamFrame* frame) {
1241   uint8 stream_flags = frame_type;
1242
1243   stream_flags &= ~kQuicFrameTypeStreamMask;
1244
1245   // Read from right to left: StreamID, Offset, Data Length, Fin.
1246   const uint8 stream_id_length = (stream_flags & kQuicStreamIDLengthMask) + 1;
1247   stream_flags >>= kQuicStreamIdShift;
1248
1249   uint8 offset_length = (stream_flags & kQuicStreamOffsetMask);
1250   // There is no encoding for 1 byte, only 0 and 2 through 8.
1251   if (offset_length > 0) {
1252     offset_length += 1;
1253   }
1254   stream_flags >>= kQuicStreamOffsetShift;
1255
1256   bool has_data_length =
1257       (stream_flags & kQuicStreamDataLengthMask) == kQuicStreamDataLengthMask;
1258   stream_flags >>= kQuicStreamDataLengthShift;
1259
1260   frame->fin = (stream_flags & kQuicStreamFinMask) == kQuicStreamFinShift;
1261
1262   frame->stream_id = 0;
1263   if (!reader_->ReadBytes(&frame->stream_id, stream_id_length)) {
1264     set_detailed_error("Unable to read stream_id.");
1265     return false;
1266   }
1267
1268   frame->offset = 0;
1269   if (!reader_->ReadBytes(&frame->offset, offset_length)) {
1270     set_detailed_error("Unable to read offset.");
1271     return false;
1272   }
1273
1274   if (has_data_length) {
1275     if (!reader_->ReadStringPiece16(&frame->data)) {
1276       set_detailed_error("Unable to read frame data.");
1277       return false;
1278     }
1279   } else {
1280     if (!reader_->ReadStringPiece(&frame->data, reader_->BytesRemaining())) {
1281       set_detailed_error("Unable to read frame data.");
1282       return false;
1283     }
1284   }
1285
1286   return true;
1287 }
1288
1289 bool QuicFramer::ProcessAckFrame(uint8 frame_type, QuicAckFrame* ack_frame) {
1290   // Determine the three lengths from the frame type: largest observed length,
1291   // missing sequence number length, and missing range length.
1292   const QuicSequenceNumberLength missing_sequence_number_length =
1293       ReadSequenceNumberLength(frame_type);
1294   frame_type >>= kQuicSequenceNumberLengthShift;
1295   const QuicSequenceNumberLength largest_observed_sequence_number_length =
1296       ReadSequenceNumberLength(frame_type);
1297   frame_type >>= kQuicSequenceNumberLengthShift;
1298   ack_frame->is_truncated = frame_type & kQuicAckTruncatedMask;
1299   frame_type >>= kQuicAckTruncatedShift;
1300   bool has_nacks = frame_type & kQuicHasNacksMask;
1301
1302   if (!reader_->ReadBytes(&ack_frame->entropy_hash, 1)) {
1303     set_detailed_error("Unable to read entropy hash for received packets.");
1304     return false;
1305   }
1306
1307   if (!reader_->ReadBytes(&ack_frame->largest_observed,
1308                           largest_observed_sequence_number_length)) {
1309     set_detailed_error("Unable to read largest observed.");
1310     return false;
1311   }
1312
1313   uint64 delta_time_largest_observed_us;
1314   if (!reader_->ReadUFloat16(&delta_time_largest_observed_us)) {
1315     set_detailed_error("Unable to read delta time largest observed.");
1316     return false;
1317   }
1318
1319   if (delta_time_largest_observed_us == kUFloat16MaxValue) {
1320     ack_frame->delta_time_largest_observed = QuicTime::Delta::Infinite();
1321   } else {
1322     ack_frame->delta_time_largest_observed =
1323         QuicTime::Delta::FromMicroseconds(delta_time_largest_observed_us);
1324   }
1325
1326   if (!ProcessTimestampsInAckFrame(ack_frame)) {
1327     return false;
1328   }
1329
1330   if (!has_nacks) {
1331     return true;
1332   }
1333
1334   uint8 num_missing_ranges;
1335   if (!reader_->ReadBytes(&num_missing_ranges, 1)) {
1336     set_detailed_error("Unable to read num missing packet ranges.");
1337     return false;
1338   }
1339
1340   QuicPacketSequenceNumber last_sequence_number = ack_frame->largest_observed;
1341   for (size_t i = 0; i < num_missing_ranges; ++i) {
1342     QuicPacketSequenceNumber missing_delta = 0;
1343     if (!reader_->ReadBytes(&missing_delta, missing_sequence_number_length)) {
1344       set_detailed_error("Unable to read missing sequence number delta.");
1345       return false;
1346     }
1347     last_sequence_number -= missing_delta;
1348     QuicPacketSequenceNumber range_length = 0;
1349     if (!reader_->ReadBytes(&range_length, PACKET_1BYTE_SEQUENCE_NUMBER)) {
1350       set_detailed_error("Unable to read missing sequence number range.");
1351       return false;
1352     }
1353     for (size_t j = 0; j <= range_length; ++j) {
1354       ack_frame->missing_packets.insert(last_sequence_number - j);
1355     }
1356     // Subtract an extra 1 to ensure ranges are represented efficiently and
1357     // can't overlap by 1 sequence number.  This allows a missing_delta of 0
1358     // to represent an adjacent nack range.
1359     last_sequence_number -= (range_length + 1);
1360   }
1361
1362   // Parse the revived packets list.
1363   uint8 num_revived_packets;
1364   if (!reader_->ReadBytes(&num_revived_packets, 1)) {
1365     set_detailed_error("Unable to read num revived packets.");
1366     return false;
1367   }
1368
1369   for (size_t i = 0; i < num_revived_packets; ++i) {
1370     QuicPacketSequenceNumber revived_packet = 0;
1371     if (!reader_->ReadBytes(&revived_packet,
1372                             largest_observed_sequence_number_length)) {
1373       set_detailed_error("Unable to read revived packet.");
1374       return false;
1375     }
1376
1377     ack_frame->revived_packets.insert(revived_packet);
1378   }
1379
1380   return true;
1381 }
1382
1383 bool QuicFramer::ProcessTimestampsInAckFrame(QuicAckFrame* ack_frame) {
1384   if (ack_frame->is_truncated) {
1385     return true;
1386   }
1387   uint8 num_received_packets;
1388   if (!reader_->ReadBytes(&num_received_packets, 1)) {
1389     set_detailed_error("Unable to read num received packets.");
1390     return false;
1391   }
1392
1393   if (num_received_packets > 0) {
1394     uint8 delta_from_largest_observed;
1395     if (!reader_->ReadBytes(&delta_from_largest_observed,
1396                             PACKET_1BYTE_SEQUENCE_NUMBER)) {
1397       set_detailed_error("Unable to read sequence delta in received packets.");
1398       return false;
1399     }
1400     QuicPacketSequenceNumber seq_num =
1401         ack_frame->largest_observed - delta_from_largest_observed;
1402
1403     // Time delta from the framer creation.
1404     uint32 time_delta_us;
1405     if (!reader_->ReadBytes(&time_delta_us, sizeof(time_delta_us))) {
1406       set_detailed_error("Unable to read time delta in received packets.");
1407       return false;
1408     }
1409
1410     last_timestamp_ = CalculateTimestampFromWire(time_delta_us);
1411
1412     ack_frame->received_packet_times.push_back(
1413         std::make_pair(seq_num, creation_time_.Add(last_timestamp_)));
1414
1415     for (uint8 i = 1; i < num_received_packets; ++i) {
1416       if (!reader_->ReadBytes(&delta_from_largest_observed,
1417                               PACKET_1BYTE_SEQUENCE_NUMBER)) {
1418         set_detailed_error(
1419             "Unable to read sequence delta in received packets.");
1420         return false;
1421       }
1422       seq_num = ack_frame->largest_observed - delta_from_largest_observed;
1423
1424       // Time delta from the previous timestamp.
1425       uint64 incremental_time_delta_us;
1426       if (!reader_->ReadUFloat16(&incremental_time_delta_us)) {
1427         set_detailed_error(
1428             "Unable to read incremental time delta in received packets.");
1429         return false;
1430       }
1431
1432       last_timestamp_ = last_timestamp_.Add(
1433           QuicTime::Delta::FromMicroseconds(incremental_time_delta_us));
1434       ack_frame->received_packet_times.push_back(
1435           std::make_pair(seq_num, creation_time_.Add(last_timestamp_)));
1436     }
1437   }
1438   return true;
1439 }
1440
1441 bool QuicFramer::ProcessStopWaitingFrame(const QuicPacketHeader& header,
1442                                          QuicStopWaitingFrame* stop_waiting) {
1443   if (!reader_->ReadBytes(&stop_waiting->entropy_hash, 1)) {
1444     set_detailed_error("Unable to read entropy hash for sent packets.");
1445     return false;
1446   }
1447
1448   QuicPacketSequenceNumber least_unacked_delta = 0;
1449   if (!reader_->ReadBytes(&least_unacked_delta,
1450                           header.public_header.sequence_number_length)) {
1451     set_detailed_error("Unable to read least unacked delta.");
1452     return false;
1453   }
1454   DCHECK_GE(header.packet_sequence_number, least_unacked_delta);
1455   stop_waiting->least_unacked =
1456       header.packet_sequence_number - least_unacked_delta;
1457
1458   return true;
1459 }
1460
1461 bool QuicFramer::ProcessRstStreamFrame(QuicRstStreamFrame* frame) {
1462   if (!reader_->ReadUInt32(&frame->stream_id)) {
1463     set_detailed_error("Unable to read stream_id.");
1464     return false;
1465   }
1466
1467   if (!reader_->ReadUInt64(&frame->byte_offset)) {
1468     set_detailed_error("Unable to read rst stream sent byte offset.");
1469     return false;
1470   }
1471
1472   uint32 error_code;
1473   if (!reader_->ReadUInt32(&error_code)) {
1474     set_detailed_error("Unable to read rst stream error code.");
1475     return false;
1476   }
1477
1478   if (error_code >= QUIC_STREAM_LAST_ERROR) {
1479     set_detailed_error("Invalid rst stream error code.");
1480     return false;
1481   }
1482
1483   frame->error_code = static_cast<QuicRstStreamErrorCode>(error_code);
1484   if (quic_version_ <= QUIC_VERSION_24) {
1485     StringPiece error_details;
1486     if (!reader_->ReadStringPiece16(&error_details)) {
1487       set_detailed_error("Unable to read rst stream error details.");
1488       return false;
1489     }
1490     frame->error_details = error_details.as_string();
1491   }
1492
1493   return true;
1494 }
1495
1496 bool QuicFramer::ProcessConnectionCloseFrame(QuicConnectionCloseFrame* frame) {
1497   uint32 error_code;
1498   if (!reader_->ReadUInt32(&error_code)) {
1499     set_detailed_error("Unable to read connection close error code.");
1500     return false;
1501   }
1502
1503   if (error_code >= QUIC_LAST_ERROR) {
1504     set_detailed_error("Invalid error code.");
1505     return false;
1506   }
1507
1508   frame->error_code = static_cast<QuicErrorCode>(error_code);
1509
1510   StringPiece error_details;
1511   if (!reader_->ReadStringPiece16(&error_details)) {
1512     set_detailed_error("Unable to read connection close error details.");
1513     return false;
1514   }
1515   frame->error_details = error_details.as_string();
1516
1517   return true;
1518 }
1519
1520 bool QuicFramer::ProcessGoAwayFrame(QuicGoAwayFrame* frame) {
1521   uint32 error_code;
1522   if (!reader_->ReadUInt32(&error_code)) {
1523     set_detailed_error("Unable to read go away error code.");
1524     return false;
1525   }
1526   frame->error_code = static_cast<QuicErrorCode>(error_code);
1527
1528   if (error_code >= QUIC_LAST_ERROR) {
1529     set_detailed_error("Invalid error code.");
1530     return false;
1531   }
1532
1533   uint32 stream_id;
1534   if (!reader_->ReadUInt32(&stream_id)) {
1535     set_detailed_error("Unable to read last good stream id.");
1536     return false;
1537   }
1538   frame->last_good_stream_id = static_cast<QuicStreamId>(stream_id);
1539
1540   StringPiece reason_phrase;
1541   if (!reader_->ReadStringPiece16(&reason_phrase)) {
1542     set_detailed_error("Unable to read goaway reason.");
1543     return false;
1544   }
1545   frame->reason_phrase = reason_phrase.as_string();
1546
1547   return true;
1548 }
1549
1550 bool QuicFramer::ProcessWindowUpdateFrame(QuicWindowUpdateFrame* frame) {
1551   if (!reader_->ReadUInt32(&frame->stream_id)) {
1552     set_detailed_error("Unable to read stream_id.");
1553     return false;
1554   }
1555
1556   if (!reader_->ReadUInt64(&frame->byte_offset)) {
1557     set_detailed_error("Unable to read window byte_offset.");
1558     return false;
1559   }
1560
1561   return true;
1562 }
1563
1564 bool QuicFramer::ProcessBlockedFrame(QuicBlockedFrame* frame) {
1565   if (!reader_->ReadUInt32(&frame->stream_id)) {
1566     set_detailed_error("Unable to read stream_id.");
1567     return false;
1568   }
1569
1570   return true;
1571 }
1572
1573 // static
1574 StringPiece QuicFramer::GetAssociatedDataFromEncryptedPacket(
1575     const QuicEncryptedPacket& encrypted,
1576     QuicConnectionIdLength connection_id_length,
1577     bool includes_version,
1578     QuicSequenceNumberLength sequence_number_length) {
1579   return StringPiece(
1580       encrypted.data() + kStartOfHashData, GetStartOfEncryptedData(
1581           connection_id_length, includes_version, sequence_number_length)
1582       - kStartOfHashData);
1583 }
1584
1585 void QuicFramer::SetDecrypter(EncryptionLevel level, QuicDecrypter* decrypter) {
1586   DCHECK(alternative_decrypter_.get() == nullptr);
1587   DCHECK_GE(level, decrypter_level_);
1588   decrypter_.reset(decrypter);
1589   decrypter_level_ = level;
1590 }
1591
1592 void QuicFramer::SetAlternativeDecrypter(EncryptionLevel level,
1593                                          QuicDecrypter* decrypter,
1594                                          bool latch_once_used) {
1595   alternative_decrypter_.reset(decrypter);
1596   alternative_decrypter_level_ = level;
1597   alternative_decrypter_latch_ = latch_once_used;
1598 }
1599
1600 const QuicDecrypter* QuicFramer::decrypter() const {
1601   return decrypter_.get();
1602 }
1603
1604 const QuicDecrypter* QuicFramer::alternative_decrypter() const {
1605   return alternative_decrypter_.get();
1606 }
1607
1608 void QuicFramer::SetEncrypter(EncryptionLevel level,
1609                               QuicEncrypter* encrypter) {
1610   DCHECK_GE(level, 0);
1611   DCHECK_LT(level, NUM_ENCRYPTION_LEVELS);
1612   encrypter_[level].reset(encrypter);
1613 }
1614
1615 QuicEncryptedPacket* QuicFramer::EncryptPayload(
1616     EncryptionLevel level,
1617     QuicPacketSequenceNumber packet_sequence_number,
1618     const QuicPacket& packet,
1619     char* buffer,
1620     size_t buffer_len) {
1621   DCHECK(encrypter_[level].get() != nullptr);
1622
1623   const size_t encrypted_len =
1624       encrypter_[level]->GetCiphertextSize(packet.Plaintext().length());
1625   StringPiece header_data = packet.BeforePlaintext();
1626   const size_t total_len = header_data.length() + encrypted_len;
1627
1628   char* encryption_buffer = buffer;
1629   // Allocate a large enough buffer for the header and the encrypted data.
1630   const bool is_new_buffer = total_len > buffer_len;
1631   if (is_new_buffer) {
1632     if (!FLAGS_quic_allow_oversized_packets_for_test) {
1633       LOG(DFATAL) << "Buffer of length:" << buffer_len
1634                   << " is not large enough to encrypt length " << total_len;
1635       return nullptr;
1636     }
1637     encryption_buffer = new char[total_len];
1638   }
1639   // Copy in the header, because the encrypter only populates the encrypted
1640   // plaintext content.
1641   memcpy(encryption_buffer, header_data.data(), header_data.length());
1642   // Encrypt the plaintext into the buffer.
1643   size_t output_length = 0;
1644   if (!encrypter_[level]->EncryptPacket(
1645           packet_sequence_number, packet.AssociatedData(), packet.Plaintext(),
1646           encryption_buffer + header_data.length(), &output_length,
1647           encrypted_len)) {
1648     RaiseError(QUIC_ENCRYPTION_FAILURE);
1649     return nullptr;
1650   }
1651
1652   return new QuicEncryptedPacket(
1653       encryption_buffer, header_data.length() + output_length, is_new_buffer);
1654 }
1655
1656 size_t QuicFramer::GetMaxPlaintextSize(size_t ciphertext_size) {
1657   // In order to keep the code simple, we don't have the current encryption
1658   // level to hand. Both the NullEncrypter and AES-GCM have a tag length of 12.
1659   size_t min_plaintext_size = ciphertext_size;
1660
1661   for (int i = ENCRYPTION_NONE; i < NUM_ENCRYPTION_LEVELS; i++) {
1662     if (encrypter_[i].get() != nullptr) {
1663       size_t size = encrypter_[i]->GetMaxPlaintextSize(ciphertext_size);
1664       if (size < min_plaintext_size) {
1665         min_plaintext_size = size;
1666       }
1667     }
1668   }
1669
1670   return min_plaintext_size;
1671 }
1672
1673 bool QuicFramer::DecryptPayload(const QuicPacketHeader& header,
1674                                 const QuicEncryptedPacket& packet,
1675                                 char* decrypted_buffer,
1676                                 size_t buffer_length) {
1677   StringPiece encrypted = reader_->ReadRemainingPayload();
1678   DCHECK(decrypter_.get() != nullptr);
1679   const StringPiece& associated_data = GetAssociatedDataFromEncryptedPacket(
1680       packet, header.public_header.connection_id_length,
1681       header.public_header.version_flag,
1682       header.public_header.sequence_number_length);
1683   size_t decrypted_length = 0;
1684   bool success = decrypter_->DecryptPacket(
1685       header.packet_sequence_number, associated_data, encrypted,
1686       decrypted_buffer, &decrypted_length, buffer_length);
1687   if (success) {
1688     visitor_->OnDecryptedPacket(decrypter_level_);
1689   } else if (alternative_decrypter_.get() != nullptr) {
1690     success = alternative_decrypter_->DecryptPacket(
1691         header.packet_sequence_number, associated_data, encrypted,
1692         decrypted_buffer, &decrypted_length, buffer_length);
1693     if (success) {
1694       visitor_->OnDecryptedPacket(alternative_decrypter_level_);
1695       if (alternative_decrypter_latch_) {
1696         // Switch to the alternative decrypter and latch so that we cannot
1697         // switch back.
1698         decrypter_.reset(alternative_decrypter_.release());
1699         decrypter_level_ = alternative_decrypter_level_;
1700         alternative_decrypter_level_ = ENCRYPTION_NONE;
1701       } else {
1702         // Switch the alternative decrypter so that we use it first next time.
1703         decrypter_.swap(alternative_decrypter_);
1704         EncryptionLevel level = alternative_decrypter_level_;
1705         alternative_decrypter_level_ = decrypter_level_;
1706         decrypter_level_ = level;
1707       }
1708     }
1709   }
1710
1711   if (!success) {
1712     DLOG(WARNING) << "DecryptPacket failed for sequence_number:"
1713                   << header.packet_sequence_number;
1714     return false;
1715   }
1716
1717   reader_.reset(new QuicDataReader(decrypted_buffer, decrypted_length));
1718   return true;
1719 }
1720
1721 size_t QuicFramer::GetAckFrameSize(
1722     const QuicAckFrame& ack,
1723     QuicSequenceNumberLength sequence_number_length) {
1724   AckFrameInfo ack_info = GetAckFrameInfo(ack);
1725   QuicSequenceNumberLength largest_observed_length =
1726       GetMinSequenceNumberLength(ack.largest_observed);
1727   QuicSequenceNumberLength missing_sequence_number_length =
1728       GetMinSequenceNumberLength(ack_info.max_delta);
1729
1730   size_t ack_size = GetMinAckFrameSize(largest_observed_length);
1731   if (!ack_info.nack_ranges.empty()) {
1732     ack_size += kNumberOfNackRangesSize  + kNumberOfRevivedPacketsSize;
1733     ack_size += min(ack_info.nack_ranges.size(), kMaxNackRanges) *
1734       (missing_sequence_number_length + PACKET_1BYTE_SEQUENCE_NUMBER);
1735     ack_size += min(ack.revived_packets.size(),
1736                     kMaxRevivedPackets) * largest_observed_length;
1737   }
1738
1739   // In version 23, if the ack will be truncated due to too many nack ranges,
1740   // then do not include the number of timestamps (1 byte).
1741   if (ack_info.nack_ranges.size() <= kMaxNackRanges) {
1742     // 1 byte for the number of timestamps.
1743     ack_size += 1;
1744     if (ack.received_packet_times.size() > 0) {
1745       // 1 byte for sequence number, 4 bytes for timestamp for the first
1746       // packet.
1747       ack_size += 5;
1748
1749       // 1 byte for sequence number, 2 bytes for timestamp for the other
1750       // packets.
1751       ack_size += 3 * (ack.received_packet_times.size() - 1);
1752     }
1753   }
1754
1755   return ack_size;
1756 }
1757
1758 size_t QuicFramer::ComputeFrameLength(
1759     const QuicFrame& frame,
1760     bool last_frame_in_packet,
1761     InFecGroup is_in_fec_group,
1762     QuicSequenceNumberLength sequence_number_length) {
1763   switch (frame.type) {
1764     case STREAM_FRAME:
1765       return GetMinStreamFrameSize(frame.stream_frame->stream_id,
1766                                    frame.stream_frame->offset,
1767                                    last_frame_in_packet, is_in_fec_group) +
1768              frame.stream_frame->data.length();
1769     case ACK_FRAME: {
1770       return GetAckFrameSize(*frame.ack_frame, sequence_number_length);
1771     }
1772     case STOP_WAITING_FRAME:
1773       return GetStopWaitingFrameSize(sequence_number_length);
1774     case PING_FRAME:
1775       // Ping has no payload.
1776       return kQuicFrameTypeSize;
1777     case RST_STREAM_FRAME:
1778       if (quic_version_ <= QUIC_VERSION_24) {
1779         return GetMinRstStreamFrameSize() +
1780                frame.rst_stream_frame->error_details.size();
1781       }
1782       return GetRstStreamFrameSize();
1783     case CONNECTION_CLOSE_FRAME:
1784       return GetMinConnectionCloseFrameSize() +
1785           frame.connection_close_frame->error_details.size();
1786     case GOAWAY_FRAME:
1787       return GetMinGoAwayFrameSize() + frame.goaway_frame->reason_phrase.size();
1788     case WINDOW_UPDATE_FRAME:
1789       return GetWindowUpdateFrameSize();
1790     case BLOCKED_FRAME:
1791       return GetBlockedFrameSize();
1792     case PADDING_FRAME:
1793       DCHECK(false);
1794       return 0;
1795     case NUM_FRAME_TYPES:
1796       DCHECK(false);
1797       return 0;
1798   }
1799
1800   // Not reachable, but some Chrome compilers can't figure that out.  *sigh*
1801   DCHECK(false);
1802   return 0;
1803 }
1804
1805 bool QuicFramer::AppendTypeByte(const QuicFrame& frame,
1806                                 bool no_stream_frame_length,
1807                                 QuicDataWriter* writer) {
1808   uint8 type_byte = 0;
1809   switch (frame.type) {
1810     case STREAM_FRAME: {
1811       if (frame.stream_frame == nullptr) {
1812         LOG(DFATAL) << "Failed to append STREAM frame with no stream_frame.";
1813       }
1814       // Fin bit.
1815       type_byte |= frame.stream_frame->fin ? kQuicStreamFinMask : 0;
1816
1817       // Data Length bit.
1818       type_byte <<= kQuicStreamDataLengthShift;
1819       type_byte |= no_stream_frame_length ? 0: kQuicStreamDataLengthMask;
1820
1821       // Offset 3 bits.
1822       type_byte <<= kQuicStreamOffsetShift;
1823       const size_t offset_len = GetStreamOffsetSize(frame.stream_frame->offset);
1824       if (offset_len > 0) {
1825         type_byte |= offset_len - 1;
1826       }
1827
1828       // stream id 2 bits.
1829       type_byte <<= kQuicStreamIdShift;
1830       type_byte |= GetStreamIdSize(frame.stream_frame->stream_id) - 1;
1831       type_byte |= kQuicFrameTypeStreamMask;  // Set Stream Frame Type to 1.
1832       break;
1833     }
1834     case ACK_FRAME:
1835       return true;
1836     default:
1837       type_byte = static_cast<uint8>(frame.type);
1838       break;
1839   }
1840
1841   return writer->WriteUInt8(type_byte);
1842 }
1843
1844 // static
1845 bool QuicFramer::AppendPacketSequenceNumber(
1846     QuicSequenceNumberLength sequence_number_length,
1847     QuicPacketSequenceNumber packet_sequence_number,
1848     QuicDataWriter* writer) {
1849   // Ensure the entire sequence number can be written.
1850   if (writer->capacity() - writer->length() <
1851       static_cast<size_t>(sequence_number_length)) {
1852     return false;
1853   }
1854   switch (sequence_number_length) {
1855     case PACKET_1BYTE_SEQUENCE_NUMBER:
1856       return writer->WriteUInt8(
1857           packet_sequence_number & k1ByteSequenceNumberMask);
1858       break;
1859     case PACKET_2BYTE_SEQUENCE_NUMBER:
1860       return writer->WriteUInt16(
1861           packet_sequence_number & k2ByteSequenceNumberMask);
1862       break;
1863     case PACKET_4BYTE_SEQUENCE_NUMBER:
1864       return writer->WriteUInt32(
1865           packet_sequence_number & k4ByteSequenceNumberMask);
1866       break;
1867     case PACKET_6BYTE_SEQUENCE_NUMBER:
1868       return writer->WriteUInt48(
1869           packet_sequence_number & k6ByteSequenceNumberMask);
1870       break;
1871     default:
1872       DCHECK(false) << "sequence_number_length: " << sequence_number_length;
1873       return false;
1874   }
1875 }
1876
1877 bool QuicFramer::AppendStreamFrame(
1878     const QuicStreamFrame& frame,
1879     bool no_stream_frame_length,
1880     QuicDataWriter* writer) {
1881   if (!writer->WriteBytes(&frame.stream_id, GetStreamIdSize(frame.stream_id))) {
1882     LOG(DFATAL) << "Writing stream id size failed.";
1883     return false;
1884   }
1885   if (!writer->WriteBytes(&frame.offset, GetStreamOffsetSize(frame.offset))) {
1886     LOG(DFATAL) << "Writing offset size failed.";
1887     return false;
1888   }
1889   if (!no_stream_frame_length) {
1890     if ((frame.data.size() > numeric_limits<uint16>::max()) ||
1891         !writer->WriteUInt16(static_cast<uint16>(frame.data.size()))) {
1892       LOG(DFATAL) << "Writing stream frame length failed";
1893       return false;
1894     }
1895   }
1896
1897   if (!writer->WriteBytes(frame.data.data(), frame.data.size())) {
1898     LOG(DFATAL) << "Writing frame data failed.";
1899     return false;
1900   }
1901   return true;
1902 }
1903
1904 void QuicFramer::set_version(const QuicVersion version) {
1905   DCHECK(IsSupportedVersion(version)) << QuicVersionToString(version);
1906   quic_version_ = version;
1907 }
1908
1909 bool QuicFramer::AppendAckFrameAndTypeByte(
1910     const QuicPacketHeader& header,
1911     const QuicAckFrame& frame,
1912     QuicDataWriter* writer) {
1913   AckFrameInfo ack_info = GetAckFrameInfo(frame);
1914   QuicPacketSequenceNumber ack_largest_observed = frame.largest_observed;
1915   QuicSequenceNumberLength largest_observed_length =
1916       GetMinSequenceNumberLength(ack_largest_observed);
1917   QuicSequenceNumberLength missing_sequence_number_length =
1918       GetMinSequenceNumberLength(ack_info.max_delta);
1919   // Determine whether we need to truncate ranges.
1920   size_t available_range_bytes =
1921       writer->capacity() - writer->length() - kNumberOfRevivedPacketsSize -
1922       kNumberOfNackRangesSize - GetMinAckFrameSize(largest_observed_length);
1923   size_t max_num_ranges = available_range_bytes /
1924       (missing_sequence_number_length + PACKET_1BYTE_SEQUENCE_NUMBER);
1925   max_num_ranges = min(kMaxNackRanges, max_num_ranges);
1926   bool truncated = ack_info.nack_ranges.size() > max_num_ranges;
1927   DVLOG_IF(1, truncated) << "Truncating ack from "
1928                          << ack_info.nack_ranges.size() << " ranges to "
1929                          << max_num_ranges;
1930   // Write out the type byte by setting the low order bits and doing shifts
1931   // to make room for the next bit flags to be set.
1932   // Whether there are any nacks.
1933   uint8 type_byte = ack_info.nack_ranges.empty() ? 0 : kQuicHasNacksMask;
1934
1935   // truncating bit.
1936   type_byte <<= kQuicAckTruncatedShift;
1937   type_byte |= truncated ? kQuicAckTruncatedMask : 0;
1938
1939   // Largest observed sequence number length.
1940   type_byte <<= kQuicSequenceNumberLengthShift;
1941   type_byte |= GetSequenceNumberFlags(largest_observed_length);
1942
1943   // Missing sequence number length.
1944   type_byte <<= kQuicSequenceNumberLengthShift;
1945   type_byte |= GetSequenceNumberFlags(missing_sequence_number_length);
1946
1947   type_byte |= kQuicFrameTypeAckMask;
1948
1949   if (!writer->WriteUInt8(type_byte)) {
1950     return false;
1951   }
1952
1953   QuicPacketEntropyHash ack_entropy_hash = frame.entropy_hash;
1954   NackRangeMap::reverse_iterator ack_iter = ack_info.nack_ranges.rbegin();
1955   if (truncated) {
1956     // Skip the nack ranges which the truncated ack won't include and set
1957     // a correct largest observed for the truncated ack.
1958     for (size_t i = 1; i < (ack_info.nack_ranges.size() - max_num_ranges);
1959          ++i) {
1960       ++ack_iter;
1961     }
1962     // If the last range is followed by acks, include them.
1963     // If the last range is followed by another range, specify the end of the
1964     // range as the largest_observed.
1965     ack_largest_observed = ack_iter->first - 1;
1966     // Also update the entropy so it matches the largest observed.
1967     ack_entropy_hash = entropy_calculator_->EntropyHash(ack_largest_observed);
1968     ++ack_iter;
1969   }
1970
1971   if (!writer->WriteUInt8(ack_entropy_hash)) {
1972     return false;
1973   }
1974
1975   if (!AppendPacketSequenceNumber(largest_observed_length,
1976                                   ack_largest_observed, writer)) {
1977     return false;
1978   }
1979
1980   uint64 delta_time_largest_observed_us = kUFloat16MaxValue;
1981   if (!frame.delta_time_largest_observed.IsInfinite()) {
1982     DCHECK_LE(0u, frame.delta_time_largest_observed.ToMicroseconds());
1983     delta_time_largest_observed_us =
1984         frame.delta_time_largest_observed.ToMicroseconds();
1985   }
1986
1987   if (!writer->WriteUFloat16(delta_time_largest_observed_us)) {
1988     return false;
1989   }
1990
1991   // Timestamp goes at the end of the required fields.
1992   if (!truncated) {
1993     if (!AppendTimestampToAckFrame(frame, writer)) {
1994       return false;
1995     }
1996   }
1997
1998   if (ack_info.nack_ranges.empty()) {
1999     return true;
2000   }
2001
2002   const uint8 num_missing_ranges =
2003       static_cast<uint8>(min(ack_info.nack_ranges.size(), max_num_ranges));
2004   if (!writer->WriteBytes(&num_missing_ranges, 1)) {
2005     return false;
2006   }
2007
2008   int num_ranges_written = 0;
2009   QuicPacketSequenceNumber last_sequence_written = ack_largest_observed;
2010   for (; ack_iter != ack_info.nack_ranges.rend(); ++ack_iter) {
2011     // Calculate the delta to the last number in the range.
2012     QuicPacketSequenceNumber missing_delta =
2013         last_sequence_written - (ack_iter->first + ack_iter->second);
2014     if (!AppendPacketSequenceNumber(missing_sequence_number_length,
2015                                     missing_delta, writer)) {
2016       return false;
2017     }
2018     if (!AppendPacketSequenceNumber(PACKET_1BYTE_SEQUENCE_NUMBER,
2019                                     ack_iter->second, writer)) {
2020       return false;
2021     }
2022     // Subtract 1 so a missing_delta of 0 means an adjacent range.
2023     last_sequence_written = ack_iter->first - 1;
2024     ++num_ranges_written;
2025   }
2026   DCHECK_EQ(num_missing_ranges, num_ranges_written);
2027
2028   // Append revived packets.
2029   // If not all the revived packets fit, only mention the ones that do.
2030   uint8 num_revived_packets =
2031       static_cast<uint8>(min(frame.revived_packets.size(), kMaxRevivedPackets));
2032   num_revived_packets = static_cast<uint8>(min(
2033       static_cast<size_t>(num_revived_packets),
2034       (writer->capacity() - writer->length()) / largest_observed_length));
2035   if (!writer->WriteBytes(&num_revived_packets, 1)) {
2036     return false;
2037   }
2038
2039   SequenceNumberSet::const_iterator iter = frame.revived_packets.begin();
2040   for (int i = 0; i < num_revived_packets; ++i, ++iter) {
2041     LOG_IF(DFATAL, !ContainsKey(frame.missing_packets, *iter));
2042     if (!AppendPacketSequenceNumber(largest_observed_length,
2043                                     *iter, writer)) {
2044       return false;
2045     }
2046   }
2047
2048   return true;
2049 }
2050
2051 bool QuicFramer::AppendTimestampToAckFrame(const QuicAckFrame& frame,
2052                                            QuicDataWriter* writer) {
2053   DCHECK_GE(numeric_limits<uint8>::max(), frame.received_packet_times.size());
2054   // num_received_packets is only 1 byte.
2055   if (frame.received_packet_times.size() > numeric_limits<uint8>::max()) {
2056     return false;
2057   }
2058
2059   uint8 num_received_packets = frame.received_packet_times.size();
2060
2061   if (!writer->WriteBytes(&num_received_packets, 1)) {
2062     return false;
2063   }
2064   if (num_received_packets == 0) {
2065     return true;
2066   }
2067
2068   PacketTimeList::const_iterator it = frame.received_packet_times.begin();
2069   QuicPacketSequenceNumber sequence_number = it->first;
2070   QuicPacketSequenceNumber delta_from_largest_observed =
2071       frame.largest_observed - sequence_number;
2072
2073   DCHECK_GE(numeric_limits<uint8>::max(), delta_from_largest_observed);
2074   if (delta_from_largest_observed > numeric_limits<uint8>::max()) {
2075     return false;
2076   }
2077
2078   if (!writer->WriteUInt8(
2079     delta_from_largest_observed & k1ByteSequenceNumberMask)) {
2080     return false;
2081   }
2082
2083   // Use the lowest 4 bytes of the time delta from the creation_time_.
2084   const uint64 time_epoch_delta_us = UINT64_C(1) << 32;
2085   uint32 time_delta_us =
2086       static_cast<uint32>(it->second.Subtract(creation_time_).ToMicroseconds()
2087                           & (time_epoch_delta_us - 1));
2088   if (!writer->WriteBytes(&time_delta_us, sizeof(time_delta_us))) {
2089     return false;
2090   }
2091
2092   QuicTime prev_time = it->second;
2093
2094   for (++it; it != frame.received_packet_times.end(); ++it) {
2095     sequence_number = it->first;
2096     delta_from_largest_observed = frame.largest_observed - sequence_number;
2097
2098     if (delta_from_largest_observed > numeric_limits<uint8>::max()) {
2099       return false;
2100     }
2101
2102     if (!writer->WriteUInt8(
2103             delta_from_largest_observed & k1ByteSequenceNumberMask)) {
2104       return false;
2105     }
2106
2107     uint64 frame_time_delta_us =
2108         it->second.Subtract(prev_time).ToMicroseconds();
2109     prev_time = it->second;
2110     if (!writer->WriteUFloat16(frame_time_delta_us)) {
2111       return false;
2112     }
2113   }
2114   return true;
2115 }
2116
2117 bool QuicFramer::AppendStopWaitingFrame(
2118     const QuicPacketHeader& header,
2119     const QuicStopWaitingFrame& frame,
2120     QuicDataWriter* writer) {
2121   DCHECK_GE(header.packet_sequence_number, frame.least_unacked);
2122   const QuicPacketSequenceNumber least_unacked_delta =
2123       header.packet_sequence_number - frame.least_unacked;
2124   const QuicPacketSequenceNumber length_shift =
2125       header.public_header.sequence_number_length * 8;
2126   if (!writer->WriteUInt8(frame.entropy_hash)) {
2127     LOG(DFATAL) << " hash failed";
2128     return false;
2129   }
2130
2131   if (least_unacked_delta >> length_shift > 0) {
2132     LOG(DFATAL) << "sequence_number_length "
2133                 << header.public_header.sequence_number_length
2134                 << " is too small for least_unacked_delta: "
2135                 << least_unacked_delta;
2136     return false;
2137   }
2138   if (!AppendPacketSequenceNumber(header.public_header.sequence_number_length,
2139                                   least_unacked_delta, writer)) {
2140     LOG(DFATAL) << " seq failed: "
2141                 << header.public_header.sequence_number_length;
2142     return false;
2143   }
2144
2145   return true;
2146 }
2147
2148 bool QuicFramer::AppendRstStreamFrame(const QuicRstStreamFrame& frame,
2149                                       QuicDataWriter* writer) {
2150   if (!writer->WriteUInt32(frame.stream_id)) {
2151     return false;
2152   }
2153
2154   if (!writer->WriteUInt64(frame.byte_offset)) {
2155     return false;
2156   }
2157
2158   uint32 error_code = static_cast<uint32>(frame.error_code);
2159   if (!writer->WriteUInt32(error_code)) {
2160     return false;
2161   }
2162
2163   if (quic_version_ <= QUIC_VERSION_24) {
2164     if (!writer->WriteStringPiece16(frame.error_details)) {
2165       return false;
2166     }
2167   }
2168   return true;
2169 }
2170
2171 bool QuicFramer::AppendConnectionCloseFrame(
2172     const QuicConnectionCloseFrame& frame,
2173     QuicDataWriter* writer) {
2174   uint32 error_code = static_cast<uint32>(frame.error_code);
2175   if (!writer->WriteUInt32(error_code)) {
2176     return false;
2177   }
2178   if (!writer->WriteStringPiece16(frame.error_details)) {
2179     return false;
2180   }
2181   return true;
2182 }
2183
2184 bool QuicFramer::AppendGoAwayFrame(const QuicGoAwayFrame& frame,
2185                                    QuicDataWriter* writer) {
2186   uint32 error_code = static_cast<uint32>(frame.error_code);
2187   if (!writer->WriteUInt32(error_code)) {
2188     return false;
2189   }
2190   uint32 stream_id = static_cast<uint32>(frame.last_good_stream_id);
2191   if (!writer->WriteUInt32(stream_id)) {
2192     return false;
2193   }
2194   if (!writer->WriteStringPiece16(frame.reason_phrase)) {
2195     return false;
2196   }
2197   return true;
2198 }
2199
2200 bool QuicFramer::AppendWindowUpdateFrame(const QuicWindowUpdateFrame& frame,
2201                                          QuicDataWriter* writer) {
2202   uint32 stream_id = static_cast<uint32>(frame.stream_id);
2203   if (!writer->WriteUInt32(stream_id)) {
2204     return false;
2205   }
2206   if (!writer->WriteUInt64(frame.byte_offset)) {
2207     return false;
2208   }
2209   return true;
2210 }
2211
2212 bool QuicFramer::AppendBlockedFrame(const QuicBlockedFrame& frame,
2213                                     QuicDataWriter* writer) {
2214   uint32 stream_id = static_cast<uint32>(frame.stream_id);
2215   if (!writer->WriteUInt32(stream_id)) {
2216     return false;
2217   }
2218   return true;
2219 }
2220
2221 bool QuicFramer::RaiseError(QuicErrorCode error) {
2222   DVLOG(1) << "Error: " << QuicUtils::ErrorToString(error)
2223            << " detail: " << detailed_error_;
2224   set_error(error);
2225   visitor_->OnError(this);
2226   reader_.reset(nullptr);
2227   return false;
2228 }
2229
2230 }  // namespace net