1 // Copyright 2013 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.
5 #include "url/url_canon_ip.h"
11 #include "base/logging.h"
12 #include "url/url_canon_internal.h"
18 // Converts one of the character types that represent a numerical base to the
19 // corresponding base.
20 int BaseForType(SharedCharTypes type) {
33 template<typename CHAR, typename UCHAR>
34 bool DoFindIPv4Components(const CHAR* spec,
35 const Component& host,
36 Component components[4]) {
37 if (!host.is_nonempty())
40 int cur_component = 0; // Index of the component we're working on.
41 int cur_component_begin = host.begin; // Start of the current component.
43 for (int i = host.begin; /* nothing */; i++) {
44 if (i >= end || spec[i] == '.') {
45 // Found the end of the current component.
46 int component_len = i - cur_component_begin;
47 components[cur_component] = Component(cur_component_begin, component_len);
49 // The next component starts after the dot.
50 cur_component_begin = i + 1;
53 // Don't allow empty components (two dots in a row), except we may
54 // allow an empty component at the end (this would indicate that the
55 // input ends in a dot). We also want to error if the component is
56 // empty and it's the only component (cur_component == 1).
57 if (component_len == 0 && (i < end || cur_component == 1))
61 break; // End of the input.
63 if (cur_component == 4) {
64 // Anything else after the 4th component is an error unless it is a
65 // dot that would otherwise be treated as the end of input.
66 if (spec[i] == '.' && i + 1 == end)
70 } else if (static_cast<UCHAR>(spec[i]) >= 0x80 ||
71 !IsIPv4Char(static_cast<unsigned char>(spec[i]))) {
72 // Invalid character for an IPv4 address.
77 // Fill in any unused components.
78 while (cur_component < 4)
79 components[cur_component++] = Component();
83 // Converts an IPv4 component to a 32-bit number, while checking for overflow.
85 // Possible return values:
86 // - IPV4 - The number was valid, and did not overflow.
87 // - BROKEN - The input was numeric, but too large for a 32-bit field.
88 // - NEUTRAL - Input was not numeric.
90 // The input is assumed to be ASCII. FindIPv4Components should have stripped
91 // out any input that is greater than 7 bits. The components are assumed
93 template<typename CHAR>
94 CanonHostInfo::Family IPv4ComponentToNumber(const CHAR* spec,
95 const Component& component,
97 // Figure out the base
99 int base_prefix_len = 0; // Size of the prefix for this base.
100 if (spec[component.begin] == '0') {
101 // Either hex or dec, or a standalone zero.
102 if (component.len == 1) {
104 } else if (spec[component.begin + 1] == 'X' ||
105 spec[component.begin + 1] == 'x') {
116 // Extend the prefix to consume all leading zeros.
117 while (base_prefix_len < component.len &&
118 spec[component.begin + base_prefix_len] == '0')
121 // Put the component, minus any base prefix, into a NULL-terminated buffer so
122 // we can call the standard library. Because leading zeros have already been
123 // discarded, filling the entire buffer is guaranteed to trigger the 32-bit
125 const int kMaxComponentLen = 16;
126 char buf[kMaxComponentLen + 1]; // digits + '\0'
128 for (int i = component.begin + base_prefix_len; i < component.end(); i++) {
129 // We know the input is 7-bit, so convert to narrow (if this is the wide
130 // version of the template) by casting.
131 char input = static_cast<char>(spec[i]);
133 // Validate that this character is OK for the given base.
134 if (!IsCharOfType(input, base))
135 return CanonHostInfo::NEUTRAL;
137 // Fill the buffer, if there's space remaining. This check allows us to
138 // verify that all characters are numeric, even those that don't fit.
139 if (dest_i < kMaxComponentLen)
140 buf[dest_i++] = input;
145 // Use the 64-bit strtoi so we get a big number (no hex, decimal, or octal
146 // number can overflow a 64-bit number in <= 16 characters).
147 uint64_t num = _strtoui64(buf, NULL, BaseForType(base));
149 // Check for 32-bit overflow.
150 if (num > std::numeric_limits<uint32_t>::max())
151 return CanonHostInfo::BROKEN;
153 // No overflow. Success!
154 *number = static_cast<uint32_t>(num);
155 return CanonHostInfo::IPV4;
158 // See declaration of IPv4AddressToNumber for documentation.
159 template<typename CHAR>
160 CanonHostInfo::Family DoIPv4AddressToNumber(const CHAR* spec,
161 const Component& host,
162 unsigned char address[4],
163 int* num_ipv4_components) {
164 // The identified components. Not all may exist.
165 Component components[4];
166 if (!FindIPv4Components(spec, host, components))
167 return CanonHostInfo::NEUTRAL;
169 // Convert existing components to digits. Values up to
170 // |existing_components| will be valid.
171 uint32_t component_values[4];
172 int existing_components = 0;
174 // Set to true if one or more components are BROKEN. BROKEN is only
175 // returned if all components are IPV4 or BROKEN, so, for example,
176 // 12345678912345.de returns NEUTRAL rather than broken.
178 for (int i = 0; i < 4; i++) {
179 if (components[i].len <= 0)
181 CanonHostInfo::Family family = IPv4ComponentToNumber(
182 spec, components[i], &component_values[existing_components]);
184 if (family == CanonHostInfo::BROKEN) {
186 } else if (family != CanonHostInfo::IPV4) {
187 // Stop if we hit a non-BROKEN invalid non-empty component.
191 existing_components++;
195 return CanonHostInfo::BROKEN;
197 // Use that sequence of numbers to fill out the 4-component IP address.
199 // First, process all components but the last, while making sure each fits
200 // within an 8-bit field.
201 for (int i = 0; i < existing_components - 1; i++) {
202 if (component_values[i] > std::numeric_limits<uint8_t>::max())
203 return CanonHostInfo::BROKEN;
204 address[i] = static_cast<unsigned char>(component_values[i]);
207 // Next, consume the last component to fill in the remaining bytes.
208 // Work around a gcc 4.9 bug. crbug.com/392872
209 #if ((__GNUC__ == 4 && __GNUC_MINOR__ >= 9) || __GNUC__ > 4)
210 #pragma GCC diagnostic push
211 #pragma GCC diagnostic ignored "-Warray-bounds"
213 uint32_t last_value = component_values[existing_components - 1];
214 #if ((__GNUC__ == 4 && __GNUC_MINOR__ >= 9) || __GNUC__ > 4)
215 #pragma GCC diagnostic pop
217 for (int i = 3; i >= existing_components - 1; i--) {
218 address[i] = static_cast<unsigned char>(last_value);
222 // If the last component has residual bits, report overflow.
224 return CanonHostInfo::BROKEN;
226 // Tell the caller how many components we saw.
227 *num_ipv4_components = existing_components;
230 return CanonHostInfo::IPV4;
233 // Return true if we've made a final IPV4/BROKEN decision, false if the result
234 // is NEUTRAL, and we could use a second opinion.
235 template<typename CHAR, typename UCHAR>
236 bool DoCanonicalizeIPv4Address(const CHAR* spec,
237 const Component& host,
239 CanonHostInfo* host_info) {
240 host_info->family = IPv4AddressToNumber(
241 spec, host, host_info->address, &host_info->num_ipv4_components);
243 switch (host_info->family) {
244 case CanonHostInfo::IPV4:
245 // Definitely an IPv4 address.
246 host_info->out_host.begin = output->length();
247 AppendIPv4Address(host_info->address, output);
248 host_info->out_host.len = output->length() - host_info->out_host.begin;
250 case CanonHostInfo::BROKEN:
251 // Definitely broken.
254 // Could be IPv6 or a hostname.
259 // Helper class that describes the main components of an IPv6 input string.
260 // See the following examples to understand how it breaks up an input string:
262 // [Example 1]: input = "[::aa:bb]"
263 // ==> num_hex_components = 2
264 // ==> hex_components[0] = Component(3,2) "aa"
265 // ==> hex_components[1] = Component(6,2) "bb"
266 // ==> index_of_contraction = 0
267 // ==> ipv4_component = Component(0, -1)
269 // [Example 2]: input = "[1:2::3:4:5]"
270 // ==> num_hex_components = 5
271 // ==> hex_components[0] = Component(1,1) "1"
272 // ==> hex_components[1] = Component(3,1) "2"
273 // ==> hex_components[2] = Component(6,1) "3"
274 // ==> hex_components[3] = Component(8,1) "4"
275 // ==> hex_components[4] = Component(10,1) "5"
276 // ==> index_of_contraction = 2
277 // ==> ipv4_component = Component(0, -1)
279 // [Example 3]: input = "[::ffff:192.168.0.1]"
280 // ==> num_hex_components = 1
281 // ==> hex_components[0] = Component(3,4) "ffff"
282 // ==> index_of_contraction = 0
283 // ==> ipv4_component = Component(8, 11) "192.168.0.1"
285 // [Example 4]: input = "[1::]"
286 // ==> num_hex_components = 1
287 // ==> hex_components[0] = Component(1,1) "1"
288 // ==> index_of_contraction = 1
289 // ==> ipv4_component = Component(0, -1)
291 // [Example 5]: input = "[::192.168.0.1]"
292 // ==> num_hex_components = 0
293 // ==> index_of_contraction = 0
294 // ==> ipv4_component = Component(8, 11) "192.168.0.1"
297 // Zero-out the parse information.
299 num_hex_components = 0;
300 index_of_contraction = -1;
301 ipv4_component.reset();
304 // There can be up to 8 hex components (colon separated) in the literal.
305 Component hex_components[8];
307 // The count of hex components present. Ranges from [0,8].
308 int num_hex_components;
310 // The index of the hex component that the "::" contraction precedes, or
311 // -1 if there is no contraction.
312 int index_of_contraction;
314 // The range of characters which are an IPv4 literal.
315 Component ipv4_component;
318 // Parse the IPv6 input string. If parsing succeeded returns true and fills
319 // |parsed| with the information. If parsing failed (because the input is
320 // invalid) returns false.
321 template<typename CHAR, typename UCHAR>
322 bool DoParseIPv6(const CHAR* spec, const Component& host, IPv6Parsed* parsed) {
323 // Zero-out the info.
326 if (!host.is_nonempty())
329 // The index for start and end of address range (no brackets).
330 int begin = host.begin;
331 int end = host.end();
333 int cur_component_begin = begin; // Start of the current component.
335 // Scan through the input, searching for hex components, "::" contractions,
336 // and IPv4 components.
337 for (int i = begin; /* i <= end */; i++) {
338 bool is_colon = spec[i] == ':';
339 bool is_contraction = is_colon && i < end - 1 && spec[i + 1] == ':';
341 // We reached the end of the current component if we encounter a colon
342 // (separator between hex components, or start of a contraction), or end of
344 if (is_colon || i == end) {
345 int component_len = i - cur_component_begin;
347 // A component should not have more than 4 hex digits.
348 if (component_len > 4)
351 // Don't allow empty components.
352 if (component_len == 0) {
353 // The exception is when contractions appear at beginning of the
354 // input or at the end of the input.
355 if (!((is_contraction && i == begin) || (i == end &&
356 parsed->index_of_contraction == parsed->num_hex_components)))
360 // Add the hex component we just found to running list.
361 if (component_len > 0) {
362 // Can't have more than 8 components!
363 if (parsed->num_hex_components >= 8)
366 parsed->hex_components[parsed->num_hex_components++] =
367 Component(cur_component_begin, component_len);
372 break; // Reached the end of the input, DONE.
374 // We found a "::" contraction.
375 if (is_contraction) {
376 // There can be at most one contraction in the literal.
377 if (parsed->index_of_contraction != -1)
379 parsed->index_of_contraction = parsed->num_hex_components;
380 ++i; // Consume the colon we peeked.
384 // Colons are separators between components, keep track of where the
385 // current component started (after this colon).
386 cur_component_begin = i + 1;
388 if (static_cast<UCHAR>(spec[i]) >= 0x80)
389 return false; // Not ASCII.
391 if (!IsHexChar(static_cast<unsigned char>(spec[i]))) {
392 // Regular components are hex numbers. It is also possible for
393 // a component to be an IPv4 address in dotted form.
394 if (IsIPv4Char(static_cast<unsigned char>(spec[i]))) {
395 // Since IPv4 address can only appear at the end, assume the rest
396 // of the string is an IPv4 address. (We will parse this separately
398 parsed->ipv4_component =
399 Component(cur_component_begin, end - cur_component_begin);
402 // The character was neither a hex digit, nor an IPv4 character.
412 // Verifies the parsed IPv6 information, checking that the various components
413 // add up to the right number of bits (hex components are 16 bits, while
414 // embedded IPv4 formats are 32 bits, and contractions are placeholdes for
415 // 16 or more bits). Returns true if sizes match up, false otherwise. On
416 // success writes the length of the contraction (if any) to
417 // |out_num_bytes_of_contraction|.
418 bool CheckIPv6ComponentsSize(const IPv6Parsed& parsed,
419 int* out_num_bytes_of_contraction) {
420 // Each group of four hex digits contributes 16 bits.
421 int num_bytes_without_contraction = parsed.num_hex_components * 2;
423 // If an IPv4 address was embedded at the end, it contributes 32 bits.
424 if (parsed.ipv4_component.is_valid())
425 num_bytes_without_contraction += 4;
427 // If there was a "::" contraction, its size is going to be:
428 // MAX([16bits], [128bits] - num_bytes_without_contraction).
429 int num_bytes_of_contraction = 0;
430 if (parsed.index_of_contraction != -1) {
431 num_bytes_of_contraction = 16 - num_bytes_without_contraction;
432 if (num_bytes_of_contraction < 2)
433 num_bytes_of_contraction = 2;
436 // Check that the numbers add up.
437 if (num_bytes_without_contraction + num_bytes_of_contraction != 16)
440 *out_num_bytes_of_contraction = num_bytes_of_contraction;
444 // Converts a hex component into a number. This cannot fail since the caller has
445 // already verified that each character in the string was a hex digit, and
446 // that there were no more than 4 characters.
447 template <typename CHAR>
448 uint16_t IPv6HexComponentToNumber(const CHAR* spec,
449 const Component& component) {
450 DCHECK(component.len <= 4);
452 // Copy the hex string into a C-string.
454 for (int i = 0; i < component.len; ++i)
455 buf[i] = static_cast<char>(spec[component.begin + i]);
456 buf[component.len] = '\0';
458 // Convert it to a number (overflow is not possible, since with 4 hex
459 // characters we can at most have a 16 bit number).
460 return static_cast<uint16_t>(_strtoui64(buf, NULL, 16));
463 // Converts an IPv6 address to a 128-bit number (network byte order), returning
464 // true on success. False means that the input was not a valid IPv6 address.
465 template<typename CHAR, typename UCHAR>
466 bool DoIPv6AddressToNumber(const CHAR* spec,
467 const Component& host,
468 unsigned char address[16]) {
469 // Make sure the component is bounded by '[' and ']'.
470 int end = host.end();
471 if (!host.is_nonempty() || spec[host.begin] != '[' || spec[end - 1] != ']')
474 // Exclude the square brackets.
475 Component ipv6_comp(host.begin + 1, host.len - 2);
477 // Parse the IPv6 address -- identify where all the colon separated hex
478 // components are, the "::" contraction, and the embedded IPv4 address.
479 IPv6Parsed ipv6_parsed;
480 if (!DoParseIPv6<CHAR, UCHAR>(spec, ipv6_comp, &ipv6_parsed))
483 // Do some basic size checks to make sure that the address doesn't
484 // specify more than 128 bits or fewer than 128 bits. This also resolves
485 // how may zero bytes the "::" contraction represents.
486 int num_bytes_of_contraction;
487 if (!CheckIPv6ComponentsSize(ipv6_parsed, &num_bytes_of_contraction))
490 int cur_index_in_address = 0;
492 // Loop through each hex components, and contraction in order.
493 for (int i = 0; i <= ipv6_parsed.num_hex_components; ++i) {
494 // Append the contraction if it appears before this component.
495 if (i == ipv6_parsed.index_of_contraction) {
496 for (int j = 0; j < num_bytes_of_contraction; ++j)
497 address[cur_index_in_address++] = 0;
499 // Append the hex component's value.
500 if (i != ipv6_parsed.num_hex_components) {
501 // Get the 16-bit value for this hex component.
502 uint16_t number = IPv6HexComponentToNumber<CHAR>(
503 spec, ipv6_parsed.hex_components[i]);
504 // Append to |address|, in network byte order.
505 address[cur_index_in_address++] = (number & 0xFF00) >> 8;
506 address[cur_index_in_address++] = (number & 0x00FF);
510 // If there was an IPv4 section, convert it into a 32-bit number and append
512 if (ipv6_parsed.ipv4_component.is_valid()) {
513 // Append the 32-bit number to |address|.
514 int ignored_num_ipv4_components;
515 if (CanonHostInfo::IPV4 !=
516 IPv4AddressToNumber(spec,
517 ipv6_parsed.ipv4_component,
518 &address[cur_index_in_address],
519 &ignored_num_ipv4_components))
526 // Searches for the longest sequence of zeros in |address|, and writes the
527 // range into |contraction_range|. The run of zeros must be at least 16 bits,
528 // and if there is a tie the first is chosen.
529 void ChooseIPv6ContractionRange(const unsigned char address[16],
530 Component* contraction_range) {
531 // The longest run of zeros in |address| seen so far.
534 // The current run of zeros in |address| being iterated over.
537 for (int i = 0; i < 16; i += 2) {
538 // Test for 16 bits worth of zero.
539 bool is_zero = (address[i] == 0 && address[i + 1] == 0);
542 // Add the zero to the current range (or start a new one).
543 if (!cur_range.is_valid())
544 cur_range = Component(i, 0);
548 if (!is_zero || i == 14) {
549 // Just completed a run of zeros. If the run is greater than 16 bits,
550 // it is a candidate for the contraction.
551 if (cur_range.len > 2 && cur_range.len > max_range.len) {
552 max_range = cur_range;
557 *contraction_range = max_range;
560 // Return true if we've made a final IPV6/BROKEN decision, false if the result
561 // is NEUTRAL, and we could use a second opinion.
562 template<typename CHAR, typename UCHAR>
563 bool DoCanonicalizeIPv6Address(const CHAR* spec,
564 const Component& host,
566 CanonHostInfo* host_info) {
567 // Turn the IP address into a 128 bit number.
568 if (!IPv6AddressToNumber(spec, host, host_info->address)) {
569 // If it's not an IPv6 address, scan for characters that should *only*
570 // exist in an IPv6 address.
571 for (int i = host.begin; i < host.end(); i++) {
576 host_info->family = CanonHostInfo::BROKEN;
581 // No invalid characters. Could still be IPv4 or a hostname.
582 host_info->family = CanonHostInfo::NEUTRAL;
586 host_info->out_host.begin = output->length();
587 output->push_back('[');
588 AppendIPv6Address(host_info->address, output);
589 output->push_back(']');
590 host_info->out_host.len = output->length() - host_info->out_host.begin;
592 host_info->family = CanonHostInfo::IPV6;
598 void AppendIPv4Address(const unsigned char address[4], CanonOutput* output) {
599 for (int i = 0; i < 4; i++) {
601 _itoa_s(address[i], str, 10);
603 for (int ch = 0; str[ch] != 0; ch++)
604 output->push_back(str[ch]);
607 output->push_back('.');
611 void AppendIPv6Address(const unsigned char address[16], CanonOutput* output) {
612 // We will output the address according to the rules in:
613 // http://tools.ietf.org/html/draft-kawamura-ipv6-text-representation-01#section-4
615 // Start by finding where to place the "::" contraction (if any).
616 Component contraction_range;
617 ChooseIPv6ContractionRange(address, &contraction_range);
619 for (int i = 0; i <= 14;) {
620 // We check 2 bytes at a time, from bytes (0, 1) to (14, 15), inclusive.
622 if (i == contraction_range.begin && contraction_range.len > 0) {
623 // Jump over the contraction.
625 output->push_back(':');
626 output->push_back(':');
627 i = contraction_range.end();
629 // Consume the next 16 bits from |address|.
630 int x = address[i] << 8 | address[i + 1];
634 // Stringify the 16 bit number (at most requires 4 hex digits).
637 for (int ch = 0; str[ch] != 0; ++ch)
638 output->push_back(str[ch]);
640 // Put a colon after each number, except the last.
642 output->push_back(':');
647 bool FindIPv4Components(const char* spec,
648 const Component& host,
649 Component components[4]) {
650 return DoFindIPv4Components<char, unsigned char>(spec, host, components);
653 bool FindIPv4Components(const base::char16* spec,
654 const Component& host,
655 Component components[4]) {
656 return DoFindIPv4Components<base::char16, base::char16>(
657 spec, host, components);
660 void CanonicalizeIPAddress(const char* spec,
661 const Component& host,
663 CanonHostInfo* host_info) {
664 if (DoCanonicalizeIPv4Address<char, unsigned char>(
665 spec, host, output, host_info))
667 if (DoCanonicalizeIPv6Address<char, unsigned char>(
668 spec, host, output, host_info))
672 void CanonicalizeIPAddress(const base::char16* spec,
673 const Component& host,
675 CanonHostInfo* host_info) {
676 if (DoCanonicalizeIPv4Address<base::char16, base::char16>(
677 spec, host, output, host_info))
679 if (DoCanonicalizeIPv6Address<base::char16, base::char16>(
680 spec, host, output, host_info))
684 CanonHostInfo::Family IPv4AddressToNumber(const char* spec,
685 const Component& host,
686 unsigned char address[4],
687 int* num_ipv4_components) {
688 return DoIPv4AddressToNumber<char>(spec, host, address, num_ipv4_components);
691 CanonHostInfo::Family IPv4AddressToNumber(const base::char16* spec,
692 const Component& host,
693 unsigned char address[4],
694 int* num_ipv4_components) {
695 return DoIPv4AddressToNumber<base::char16>(
696 spec, host, address, num_ipv4_components);
699 bool IPv6AddressToNumber(const char* spec,
700 const Component& host,
701 unsigned char address[16]) {
702 return DoIPv6AddressToNumber<char, unsigned char>(spec, host, address);
705 bool IPv6AddressToNumber(const base::char16* spec,
706 const Component& host,
707 unsigned char address[16]) {
708 return DoIPv6AddressToNumber<base::char16, base::char16>(spec, host, address);