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_utils.h"
6
7#include <ctype.h>
8
9#include <algorithm>
10
11#include "base/basictypes.h"
12#include "base/logging.h"
13#include "base/port.h"
14#include "base/strings/stringprintf.h"
15#include "base/strings/string_number_conversions.h"
16#include "net/quic/quic_write_blocked_list.h"
17
18using base::StringPiece;
19using std::string;
20
21namespace net {
22
23// static
24uint64 QuicUtils::FNV1a_64_Hash(const char* data, int len) {
25  static const uint64 kOffset = GG_UINT64_C(14695981039346656037);
26  static const uint64 kPrime = GG_UINT64_C(1099511628211);
27
28  const uint8* octets = reinterpret_cast<const uint8*>(data);
29
30  uint64 hash = kOffset;
31
32  for (int i = 0; i < len; ++i) {
33    hash = hash ^ octets[i];
34    hash = hash * kPrime;
35  }
36
37  return hash;
38}
39
40// static
41uint128 QuicUtils::FNV1a_128_Hash(const char* data, int len) {
42  // The following two constants are defined as part of the hash algorithm.
43  // see http://www.isthe.com/chongo/tech/comp/fnv/
44  // 309485009821345068724781371
45  const uint128 kPrime(16777216, 315);
46  // 144066263297769815596495629667062367629
47  const uint128 kOffset(GG_UINT64_C(7809847782465536322),
48                        GG_UINT64_C(7113472399480571277));
49
50  const uint8* octets = reinterpret_cast<const uint8*>(data);
51
52  uint128 hash = kOffset;
53
54  for (int i = 0; i < len; ++i) {
55    hash  = hash ^ uint128(0, octets[i]);
56    hash = hash * kPrime;
57  }
58
59  return hash;
60}
61
62// static
63bool QuicUtils::FindMutualTag(const QuicTagVector& our_tags_vector,
64                              const QuicTag* their_tags,
65                              size_t num_their_tags,
66                              Priority priority,
67                              QuicTag* out_result,
68                              size_t* out_index) {
69  if (our_tags_vector.empty()) {
70    return false;
71  }
72  const size_t num_our_tags = our_tags_vector.size();
73  const QuicTag* our_tags = &our_tags_vector[0];
74
75  size_t num_priority_tags, num_inferior_tags;
76  const QuicTag* priority_tags;
77  const QuicTag* inferior_tags;
78  if (priority == LOCAL_PRIORITY) {
79    num_priority_tags = num_our_tags;
80    priority_tags = our_tags;
81    num_inferior_tags = num_their_tags;
82    inferior_tags = their_tags;
83  } else {
84    num_priority_tags = num_their_tags;
85    priority_tags = their_tags;
86    num_inferior_tags = num_our_tags;
87    inferior_tags = our_tags;
88  }
89
90  for (size_t i = 0; i < num_priority_tags; i++) {
91    for (size_t j = 0; j < num_inferior_tags; j++) {
92      if (priority_tags[i] == inferior_tags[j]) {
93        *out_result = priority_tags[i];
94        if (out_index) {
95          if (priority == LOCAL_PRIORITY) {
96            *out_index = j;
97          } else {
98            *out_index = i;
99          }
100        }
101        return true;
102      }
103    }
104  }
105
106  return false;
107}
108
109// static
110void QuicUtils::SerializeUint128(uint128 v, uint8* out) {
111  const uint64 lo = Uint128Low64(v);
112  const uint64 hi = Uint128High64(v);
113  // This assumes that the system is little-endian.
114  memcpy(out, &lo, sizeof(lo));
115  memcpy(out + sizeof(lo), &hi, sizeof(hi));
116}
117
118// static
119void QuicUtils::SerializeUint128Short(uint128 v, uint8* out) {
120  const uint64 lo = Uint128Low64(v);
121  const uint64 hi = Uint128High64(v);
122  // This assumes that the system is little-endian.
123  memcpy(out, &lo, sizeof(lo));
124  memcpy(out + sizeof(lo), &hi, sizeof(hi) / 2);
125}
126
127#define RETURN_STRING_LITERAL(x) \
128case x: \
129return #x;
130
131// static
132const char* QuicUtils::StreamErrorToString(QuicRstStreamErrorCode error) {
133  switch (error) {
134    RETURN_STRING_LITERAL(QUIC_STREAM_NO_ERROR);
135    RETURN_STRING_LITERAL(QUIC_STREAM_CONNECTION_ERROR);
136    RETURN_STRING_LITERAL(QUIC_ERROR_PROCESSING_STREAM);
137    RETURN_STRING_LITERAL(QUIC_MULTIPLE_TERMINATION_OFFSETS);
138    RETURN_STRING_LITERAL(QUIC_BAD_APPLICATION_PAYLOAD);
139    RETURN_STRING_LITERAL(QUIC_STREAM_PEER_GOING_AWAY);
140    RETURN_STRING_LITERAL(QUIC_STREAM_CANCELLED);
141    RETURN_STRING_LITERAL(QUIC_RST_FLOW_CONTROL_ACCOUNTING);
142    RETURN_STRING_LITERAL(QUIC_STREAM_LAST_ERROR);
143  }
144  // Return a default value so that we return this when |error| doesn't match
145  // any of the QuicRstStreamErrorCodes. This can happen when the RstStream
146  // frame sent by the peer (attacker) has invalid error code.
147  return "INVALID_RST_STREAM_ERROR_CODE";
148}
149
150// static
151const char* QuicUtils::ErrorToString(QuicErrorCode error) {
152  switch (error) {
153    RETURN_STRING_LITERAL(QUIC_NO_ERROR);
154    RETURN_STRING_LITERAL(QUIC_INTERNAL_ERROR);
155    RETURN_STRING_LITERAL(QUIC_STREAM_DATA_AFTER_TERMINATION);
156    RETURN_STRING_LITERAL(QUIC_INVALID_PACKET_HEADER);
157    RETURN_STRING_LITERAL(QUIC_INVALID_FRAME_DATA);
158    RETURN_STRING_LITERAL(QUIC_MISSING_PAYLOAD);
159    RETURN_STRING_LITERAL(QUIC_INVALID_FEC_DATA);
160    RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_DATA);
161    RETURN_STRING_LITERAL(QUIC_UNENCRYPTED_STREAM_DATA);
162    RETURN_STRING_LITERAL(QUIC_INVALID_RST_STREAM_DATA);
163    RETURN_STRING_LITERAL(QUIC_INVALID_CONNECTION_CLOSE_DATA);
164    RETURN_STRING_LITERAL(QUIC_INVALID_GOAWAY_DATA);
165    RETURN_STRING_LITERAL(QUIC_INVALID_WINDOW_UPDATE_DATA);
166    RETURN_STRING_LITERAL(QUIC_INVALID_BLOCKED_DATA);
167    RETURN_STRING_LITERAL(QUIC_INVALID_STOP_WAITING_DATA);
168    RETURN_STRING_LITERAL(QUIC_INVALID_ACK_DATA);
169    RETURN_STRING_LITERAL(QUIC_INVALID_CONGESTION_FEEDBACK_DATA);
170    RETURN_STRING_LITERAL(QUIC_INVALID_VERSION_NEGOTIATION_PACKET);
171    RETURN_STRING_LITERAL(QUIC_INVALID_PUBLIC_RST_PACKET);
172    RETURN_STRING_LITERAL(QUIC_DECRYPTION_FAILURE);
173    RETURN_STRING_LITERAL(QUIC_ENCRYPTION_FAILURE);
174    RETURN_STRING_LITERAL(QUIC_PACKET_TOO_LARGE);
175    RETURN_STRING_LITERAL(QUIC_PACKET_FOR_NONEXISTENT_STREAM);
176    RETURN_STRING_LITERAL(QUIC_PEER_GOING_AWAY);
177    RETURN_STRING_LITERAL(QUIC_HANDSHAKE_FAILED);
178    RETURN_STRING_LITERAL(QUIC_CRYPTO_TAGS_OUT_OF_ORDER);
179    RETURN_STRING_LITERAL(QUIC_CRYPTO_TOO_MANY_ENTRIES);
180    RETURN_STRING_LITERAL(QUIC_CRYPTO_TOO_MANY_REJECTS);
181    RETURN_STRING_LITERAL(QUIC_CRYPTO_INVALID_VALUE_LENGTH)
182    RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_AFTER_HANDSHAKE_COMPLETE);
183    RETURN_STRING_LITERAL(QUIC_CRYPTO_INTERNAL_ERROR);
184    RETURN_STRING_LITERAL(QUIC_CRYPTO_VERSION_NOT_SUPPORTED);
185    RETURN_STRING_LITERAL(QUIC_CRYPTO_NO_SUPPORT);
186    RETURN_STRING_LITERAL(QUIC_INVALID_CRYPTO_MESSAGE_TYPE);
187    RETURN_STRING_LITERAL(QUIC_INVALID_CRYPTO_MESSAGE_PARAMETER);
188    RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_PARAMETER_NOT_FOUND);
189    RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_PARAMETER_NO_OVERLAP);
190    RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_INDEX_NOT_FOUND);
191    RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_ID);
192    RETURN_STRING_LITERAL(QUIC_INVALID_PRIORITY);
193    RETURN_STRING_LITERAL(QUIC_TOO_MANY_OPEN_STREAMS);
194    RETURN_STRING_LITERAL(QUIC_TOO_MANY_UNFINISHED_STREAMS);
195    RETURN_STRING_LITERAL(QUIC_PUBLIC_RESET);
196    RETURN_STRING_LITERAL(QUIC_INVALID_VERSION);
197    RETURN_STRING_LITERAL(QUIC_INVALID_HEADER_ID);
198    RETURN_STRING_LITERAL(QUIC_INVALID_NEGOTIATED_VALUE);
199    RETURN_STRING_LITERAL(QUIC_DECOMPRESSION_FAILURE);
200    RETURN_STRING_LITERAL(QUIC_CONNECTION_TIMED_OUT);
201    RETURN_STRING_LITERAL(QUIC_CONNECTION_OVERALL_TIMED_OUT);
202    RETURN_STRING_LITERAL(QUIC_ERROR_MIGRATING_ADDRESS);
203    RETURN_STRING_LITERAL(QUIC_PACKET_WRITE_ERROR);
204    RETURN_STRING_LITERAL(QUIC_PACKET_READ_ERROR);
205    RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_FRAME);
206    RETURN_STRING_LITERAL(QUIC_INVALID_HEADERS_STREAM_DATA);
207    RETURN_STRING_LITERAL(QUIC_FLOW_CONTROL_RECEIVED_TOO_MUCH_DATA);
208    RETURN_STRING_LITERAL(QUIC_FLOW_CONTROL_SENT_TOO_MUCH_DATA);
209    RETURN_STRING_LITERAL(QUIC_FLOW_CONTROL_INVALID_WINDOW);
210    RETURN_STRING_LITERAL(QUIC_CONNECTION_IP_POOLED);
211    RETURN_STRING_LITERAL(QUIC_PROOF_INVALID);
212    RETURN_STRING_LITERAL(QUIC_CRYPTO_DUPLICATE_TAG);
213    RETURN_STRING_LITERAL(QUIC_CRYPTO_ENCRYPTION_LEVEL_INCORRECT);
214    RETURN_STRING_LITERAL(QUIC_CRYPTO_SERVER_CONFIG_EXPIRED);
215    RETURN_STRING_LITERAL(QUIC_INVALID_CHANNEL_ID_SIGNATURE);
216    RETURN_STRING_LITERAL(QUIC_CRYPTO_SYMMETRIC_KEY_SETUP_FAILED);
217    RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_WHILE_VALIDATING_CLIENT_HELLO);
218    RETURN_STRING_LITERAL(QUIC_CRYPTO_UPDATE_BEFORE_HANDSHAKE_COMPLETE);
219    RETURN_STRING_LITERAL(QUIC_VERSION_NEGOTIATION_MISMATCH);
220    RETURN_STRING_LITERAL(QUIC_LAST_ERROR);
221    // Intentionally have no default case, so we'll break the build
222    // if we add errors and don't put them here.
223  }
224  // Return a default value so that we return this when |error| doesn't match
225  // any of the QuicErrorCodes. This can happen when the ConnectionClose
226  // frame sent by the peer (attacker) has invalid error code.
227  return "INVALID_ERROR_CODE";
228}
229
230// static
231const char* QuicUtils::EncryptionLevelToString(EncryptionLevel level) {
232  switch (level) {
233    RETURN_STRING_LITERAL(ENCRYPTION_NONE);
234    RETURN_STRING_LITERAL(ENCRYPTION_INITIAL);
235    RETURN_STRING_LITERAL(ENCRYPTION_FORWARD_SECURE);
236    RETURN_STRING_LITERAL(NUM_ENCRYPTION_LEVELS);
237  }
238  return "INVALID_ENCRYPTION_LEVEL";
239}
240
241// static
242const char* QuicUtils::TransmissionTypeToString(TransmissionType type) {
243  switch (type) {
244    RETURN_STRING_LITERAL(NOT_RETRANSMISSION);
245    RETURN_STRING_LITERAL(HANDSHAKE_RETRANSMISSION);
246    RETURN_STRING_LITERAL(LOSS_RETRANSMISSION);
247    RETURN_STRING_LITERAL(ALL_UNACKED_RETRANSMISSION);
248    RETURN_STRING_LITERAL(ALL_INITIAL_RETRANSMISSION);
249    RETURN_STRING_LITERAL(RTO_RETRANSMISSION);
250    RETURN_STRING_LITERAL(TLP_RETRANSMISSION);
251  }
252  return "INVALID_TRANSMISSION_TYPE";
253}
254
255// static
256string QuicUtils::TagToString(QuicTag tag) {
257  char chars[4];
258  bool ascii = true;
259  const QuicTag orig_tag = tag;
260
261  for (size_t i = 0; i < sizeof(chars); i++) {
262    chars[i] = tag;
263    if ((chars[i] == 0 || chars[i] == '\xff') && i == 3) {
264      chars[i] = ' ';
265    }
266    if (!isprint(static_cast<unsigned char>(chars[i]))) {
267      ascii = false;
268      break;
269    }
270    tag >>= 8;
271  }
272
273  if (ascii) {
274    return string(chars, sizeof(chars));
275  }
276
277  return base::UintToString(orig_tag);
278}
279
280// static
281string QuicUtils::StringToHexASCIIDump(StringPiece in_buffer) {
282  int offset = 0;
283  const int kBytesPerLine = 16;   // Max bytes dumped per line
284  const char* buf = in_buffer.data();
285  int bytes_remaining = in_buffer.size();
286  string s;   // our output
287  const char* p = buf;
288  while (bytes_remaining > 0) {
289    const int line_bytes = std::min(bytes_remaining, kBytesPerLine);
290    base::StringAppendF(&s, "0x%04x:  ", offset);  // Do the line header
291    for (int i = 0; i < kBytesPerLine; ++i) {
292      if (i < line_bytes) {
293        base::StringAppendF(&s, "%02x", static_cast<unsigned char>(p[i]));
294      } else {
295        s += "  ";    // two-space filler instead of two-space hex digits
296      }
297      if (i % 2) s += ' ';
298    }
299    s += ' ';
300    for (int i = 0; i < line_bytes; ++i) {  // Do the ASCII dump
301      s+= (p[i] >  32 && p[i] < 127) ? p[i] : '.';
302    }
303
304    bytes_remaining -= line_bytes;
305    offset += line_bytes;
306    p += line_bytes;
307    s += '\n';
308  }
309  return s;
310}
311
312// static
313QuicPriority QuicUtils::LowestPriority() {
314  return QuicWriteBlockedList::kLowestPriority;
315}
316
317// static
318QuicPriority QuicUtils::HighestPriority() {
319  return QuicWriteBlockedList::kHighestPriority;
320}
321
322}  // namespace net
323