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