123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678 |
- // Copyright 2013 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "url/url_canon_ip.h"
- #include <stdint.h>
- #include <stdlib.h>
- #include <limits>
- #include "base/check.h"
- #include "url/url_canon_internal.h"
- namespace url {
- namespace {
- // Converts one of the character types that represent a numerical base to the
- // corresponding base.
- int BaseForType(SharedCharTypes type) {
- switch (type) {
- case CHAR_HEX:
- return 16;
- case CHAR_DEC:
- return 10;
- case CHAR_OCT:
- return 8;
- default:
- return 0;
- }
- }
- // Converts an IPv4 component to a 32-bit number, while checking for overflow.
- //
- // Possible return values:
- // - IPV4 - The number was valid, and did not overflow.
- // - BROKEN - The input was numeric, but too large for a 32-bit field.
- // - NEUTRAL - Input was not numeric.
- //
- // The input is assumed to be ASCII. The components are assumed to be non-empty.
- template<typename CHAR>
- CanonHostInfo::Family IPv4ComponentToNumber(const CHAR* spec,
- const Component& component,
- uint32_t* number) {
- // Empty components are considered non-numeric.
- if (!component.is_nonempty())
- return CanonHostInfo::NEUTRAL;
- // Figure out the base
- SharedCharTypes base;
- int base_prefix_len = 0; // Size of the prefix for this base.
- if (spec[component.begin] == '0') {
- // Either hex or dec, or a standalone zero.
- if (component.len == 1) {
- base = CHAR_DEC;
- } else if (spec[component.begin + 1] == 'X' ||
- spec[component.begin + 1] == 'x') {
- base = CHAR_HEX;
- base_prefix_len = 2;
- } else {
- base = CHAR_OCT;
- base_prefix_len = 1;
- }
- } else {
- base = CHAR_DEC;
- }
- // Extend the prefix to consume all leading zeros.
- while (base_prefix_len < component.len &&
- spec[component.begin + base_prefix_len] == '0')
- base_prefix_len++;
- // Put the component, minus any base prefix, into a NULL-terminated buffer so
- // we can call the standard library. Because leading zeros have already been
- // discarded, filling the entire buffer is guaranteed to trigger the 32-bit
- // overflow check.
- const int kMaxComponentLen = 16;
- char buf[kMaxComponentLen + 1]; // digits + '\0'
- int dest_i = 0;
- bool may_be_broken_octal = false;
- for (int i = component.begin + base_prefix_len; i < component.end(); i++) {
- if (spec[i] >= 0x80)
- return CanonHostInfo::NEUTRAL;
- // We know the input is 7-bit, so convert to narrow (if this is the wide
- // version of the template) by casting.
- char input = static_cast<char>(spec[i]);
- // Validate that this character is OK for the given base.
- if (!IsCharOfType(input, base)) {
- if (IsCharOfType(input, CHAR_DEC)) {
- // Entirely numeric components with leading 0s that aren't octal are
- // considered broken.
- may_be_broken_octal = true;
- } else {
- return CanonHostInfo::NEUTRAL;
- }
- }
- // Fill the buffer, if there's space remaining. This check allows us to
- // verify that all characters are numeric, even those that don't fit.
- if (dest_i < kMaxComponentLen)
- buf[dest_i++] = input;
- }
- if (may_be_broken_octal)
- return CanonHostInfo::BROKEN;
- buf[dest_i] = '\0';
- // Use the 64-bit strtoi so we get a big number (no hex, decimal, or octal
- // number can overflow a 64-bit number in <= 16 characters).
- uint64_t num = _strtoui64(buf, NULL, BaseForType(base));
- // Check for 32-bit overflow.
- if (num > std::numeric_limits<uint32_t>::max())
- return CanonHostInfo::BROKEN;
- // No overflow. Success!
- *number = static_cast<uint32_t>(num);
- return CanonHostInfo::IPV4;
- }
- // See declaration of IPv4AddressToNumber for documentation.
- template <typename CHAR, typename UCHAR>
- CanonHostInfo::Family DoIPv4AddressToNumber(const CHAR* spec,
- Component host,
- unsigned char address[4],
- int* num_ipv4_components) {
- // Ignore terminal dot, if present.
- if (host.is_nonempty() && spec[host.end() - 1] == '.')
- --host.len;
- // Do nothing if empty.
- if (!host.is_nonempty())
- return CanonHostInfo::NEUTRAL;
- // Read component values. The first `existing_components` of them are
- // populated front to back, with the first one corresponding to the last
- // component, which allows for early exit if the last component isn't a
- // number.
- uint32_t component_values[4];
- int existing_components = 0;
- int current_component_end = host.end();
- int current_position = current_component_end;
- while (true) {
- // If this is not the first character of a component, go to the next
- // component.
- if (current_position != host.begin && spec[current_position - 1] != '.') {
- --current_position;
- continue;
- }
- CanonHostInfo::Family family = IPv4ComponentToNumber(
- spec,
- Component(current_position, current_component_end - current_position),
- &component_values[existing_components]);
- // If `family` is NEUTRAL and this is the last component, return NEUTRAL. If
- // `family` is NEUTRAL but not the last component, this is considered a
- // BROKEN IPv4 address, as opposed to a non-IPv4 hostname.
- if (family == CanonHostInfo::NEUTRAL && existing_components == 0)
- return CanonHostInfo::NEUTRAL;
- if (family != CanonHostInfo::IPV4)
- return CanonHostInfo::BROKEN;
- ++existing_components;
- // If this is the final component, nothing else to do.
- if (current_position == host.begin)
- break;
- // If there are more than 4 components, fail.
- if (existing_components == 4)
- return CanonHostInfo::BROKEN;
- current_component_end = current_position - 1;
- --current_position;
- }
- // Use `component_values` to fill out the 4-component IP address.
- // First, process all components but the last, while making sure each fits
- // within an 8-bit field.
- for (int i = existing_components - 1; i > 0; i--) {
- if (component_values[i] > std::numeric_limits<uint8_t>::max())
- return CanonHostInfo::BROKEN;
- address[existing_components - i - 1] =
- static_cast<unsigned char>(component_values[i]);
- }
- uint32_t last_value = component_values[0];
- for (int i = 3; i >= existing_components - 1; i--) {
- address[i] = static_cast<unsigned char>(last_value);
- last_value >>= 8;
- }
- // If the last component has residual bits, report overflow.
- if (last_value != 0)
- return CanonHostInfo::BROKEN;
- // Tell the caller how many components we saw.
- *num_ipv4_components = existing_components;
- // Success!
- return CanonHostInfo::IPV4;
- }
- // Return true if we've made a final IPV4/BROKEN decision, false if the result
- // is NEUTRAL, and we could use a second opinion.
- template<typename CHAR, typename UCHAR>
- bool DoCanonicalizeIPv4Address(const CHAR* spec,
- const Component& host,
- CanonOutput* output,
- CanonHostInfo* host_info) {
- host_info->family = IPv4AddressToNumber(
- spec, host, host_info->address, &host_info->num_ipv4_components);
- switch (host_info->family) {
- case CanonHostInfo::IPV4:
- // Definitely an IPv4 address.
- host_info->out_host.begin = output->length();
- AppendIPv4Address(host_info->address, output);
- host_info->out_host.len = output->length() - host_info->out_host.begin;
- return true;
- case CanonHostInfo::BROKEN:
- // Definitely broken.
- return true;
- default:
- // Could be IPv6 or a hostname.
- return false;
- }
- }
- // Helper class that describes the main components of an IPv6 input string.
- // See the following examples to understand how it breaks up an input string:
- //
- // [Example 1]: input = "[::aa:bb]"
- // ==> num_hex_components = 2
- // ==> hex_components[0] = Component(3,2) "aa"
- // ==> hex_components[1] = Component(6,2) "bb"
- // ==> index_of_contraction = 0
- // ==> ipv4_component = Component(0, -1)
- //
- // [Example 2]: input = "[1:2::3:4:5]"
- // ==> num_hex_components = 5
- // ==> hex_components[0] = Component(1,1) "1"
- // ==> hex_components[1] = Component(3,1) "2"
- // ==> hex_components[2] = Component(6,1) "3"
- // ==> hex_components[3] = Component(8,1) "4"
- // ==> hex_components[4] = Component(10,1) "5"
- // ==> index_of_contraction = 2
- // ==> ipv4_component = Component(0, -1)
- //
- // [Example 3]: input = "[::ffff:192.168.0.1]"
- // ==> num_hex_components = 1
- // ==> hex_components[0] = Component(3,4) "ffff"
- // ==> index_of_contraction = 0
- // ==> ipv4_component = Component(8, 11) "192.168.0.1"
- //
- // [Example 4]: input = "[1::]"
- // ==> num_hex_components = 1
- // ==> hex_components[0] = Component(1,1) "1"
- // ==> index_of_contraction = 1
- // ==> ipv4_component = Component(0, -1)
- //
- // [Example 5]: input = "[::192.168.0.1]"
- // ==> num_hex_components = 0
- // ==> index_of_contraction = 0
- // ==> ipv4_component = Component(8, 11) "192.168.0.1"
- //
- struct IPv6Parsed {
- // Zero-out the parse information.
- void reset() {
- num_hex_components = 0;
- index_of_contraction = -1;
- ipv4_component.reset();
- }
- // There can be up to 8 hex components (colon separated) in the literal.
- Component hex_components[8];
- // The count of hex components present. Ranges from [0,8].
- int num_hex_components;
- // The index of the hex component that the "::" contraction precedes, or
- // -1 if there is no contraction.
- int index_of_contraction;
- // The range of characters which are an IPv4 literal.
- Component ipv4_component;
- };
- // Parse the IPv6 input string. If parsing succeeded returns true and fills
- // |parsed| with the information. If parsing failed (because the input is
- // invalid) returns false.
- template<typename CHAR, typename UCHAR>
- bool DoParseIPv6(const CHAR* spec, const Component& host, IPv6Parsed* parsed) {
- // Zero-out the info.
- parsed->reset();
- if (!host.is_nonempty())
- return false;
- // The index for start and end of address range (no brackets).
- int begin = host.begin;
- int end = host.end();
- int cur_component_begin = begin; // Start of the current component.
- // Scan through the input, searching for hex components, "::" contractions,
- // and IPv4 components.
- for (int i = begin; /* i <= end */; i++) {
- bool is_colon = spec[i] == ':';
- bool is_contraction = is_colon && i < end - 1 && spec[i + 1] == ':';
- // We reached the end of the current component if we encounter a colon
- // (separator between hex components, or start of a contraction), or end of
- // input.
- if (is_colon || i == end) {
- int component_len = i - cur_component_begin;
- // A component should not have more than 4 hex digits.
- if (component_len > 4)
- return false;
- // Don't allow empty components.
- if (component_len == 0) {
- // The exception is when contractions appear at beginning of the
- // input or at the end of the input.
- if (!((is_contraction && i == begin) || (i == end &&
- parsed->index_of_contraction == parsed->num_hex_components)))
- return false;
- }
- // Add the hex component we just found to running list.
- if (component_len > 0) {
- // Can't have more than 8 components!
- if (parsed->num_hex_components >= 8)
- return false;
- parsed->hex_components[parsed->num_hex_components++] =
- Component(cur_component_begin, component_len);
- }
- }
- if (i == end)
- break; // Reached the end of the input, DONE.
- // We found a "::" contraction.
- if (is_contraction) {
- // There can be at most one contraction in the literal.
- if (parsed->index_of_contraction != -1)
- return false;
- parsed->index_of_contraction = parsed->num_hex_components;
- ++i; // Consume the colon we peeked.
- }
- if (is_colon) {
- // Colons are separators between components, keep track of where the
- // current component started (after this colon).
- cur_component_begin = i + 1;
- } else {
- if (static_cast<UCHAR>(spec[i]) >= 0x80)
- return false; // Not ASCII.
- if (!IsHexChar(static_cast<unsigned char>(spec[i]))) {
- // Regular components are hex numbers. It is also possible for
- // a component to be an IPv4 address in dotted form.
- if (IsIPv4Char(static_cast<unsigned char>(spec[i]))) {
- // Since IPv4 address can only appear at the end, assume the rest
- // of the string is an IPv4 address. (We will parse this separately
- // later).
- parsed->ipv4_component =
- Component(cur_component_begin, end - cur_component_begin);
- break;
- } else {
- // The character was neither a hex digit, nor an IPv4 character.
- return false;
- }
- }
- }
- }
- return true;
- }
- // Verifies the parsed IPv6 information, checking that the various components
- // add up to the right number of bits (hex components are 16 bits, while
- // embedded IPv4 formats are 32 bits, and contractions are placeholdes for
- // 16 or more bits). Returns true if sizes match up, false otherwise. On
- // success writes the length of the contraction (if any) to
- // |out_num_bytes_of_contraction|.
- bool CheckIPv6ComponentsSize(const IPv6Parsed& parsed,
- int* out_num_bytes_of_contraction) {
- // Each group of four hex digits contributes 16 bits.
- int num_bytes_without_contraction = parsed.num_hex_components * 2;
- // If an IPv4 address was embedded at the end, it contributes 32 bits.
- if (parsed.ipv4_component.is_valid())
- num_bytes_without_contraction += 4;
- // If there was a "::" contraction, its size is going to be:
- // MAX([16bits], [128bits] - num_bytes_without_contraction).
- int num_bytes_of_contraction = 0;
- if (parsed.index_of_contraction != -1) {
- num_bytes_of_contraction = 16 - num_bytes_without_contraction;
- if (num_bytes_of_contraction < 2)
- num_bytes_of_contraction = 2;
- }
- // Check that the numbers add up.
- if (num_bytes_without_contraction + num_bytes_of_contraction != 16)
- return false;
- *out_num_bytes_of_contraction = num_bytes_of_contraction;
- return true;
- }
- // Converts a hex component into a number. This cannot fail since the caller has
- // already verified that each character in the string was a hex digit, and
- // that there were no more than 4 characters.
- template <typename CHAR>
- uint16_t IPv6HexComponentToNumber(const CHAR* spec,
- const Component& component) {
- DCHECK(component.len <= 4);
- // Copy the hex string into a C-string.
- char buf[5];
- for (int i = 0; i < component.len; ++i)
- buf[i] = static_cast<char>(spec[component.begin + i]);
- buf[component.len] = '\0';
- // Convert it to a number (overflow is not possible, since with 4 hex
- // characters we can at most have a 16 bit number).
- return static_cast<uint16_t>(_strtoui64(buf, NULL, 16));
- }
- // Converts an IPv6 address to a 128-bit number (network byte order), returning
- // true on success. False means that the input was not a valid IPv6 address.
- template<typename CHAR, typename UCHAR>
- bool DoIPv6AddressToNumber(const CHAR* spec,
- const Component& host,
- unsigned char address[16]) {
- // Make sure the component is bounded by '[' and ']'.
- int end = host.end();
- if (!host.is_nonempty() || spec[host.begin] != '[' || spec[end - 1] != ']')
- return false;
- // Exclude the square brackets.
- Component ipv6_comp(host.begin + 1, host.len - 2);
- // Parse the IPv6 address -- identify where all the colon separated hex
- // components are, the "::" contraction, and the embedded IPv4 address.
- IPv6Parsed ipv6_parsed;
- if (!DoParseIPv6<CHAR, UCHAR>(spec, ipv6_comp, &ipv6_parsed))
- return false;
- // Do some basic size checks to make sure that the address doesn't
- // specify more than 128 bits or fewer than 128 bits. This also resolves
- // how may zero bytes the "::" contraction represents.
- int num_bytes_of_contraction;
- if (!CheckIPv6ComponentsSize(ipv6_parsed, &num_bytes_of_contraction))
- return false;
- int cur_index_in_address = 0;
- // Loop through each hex components, and contraction in order.
- for (int i = 0; i <= ipv6_parsed.num_hex_components; ++i) {
- // Append the contraction if it appears before this component.
- if (i == ipv6_parsed.index_of_contraction) {
- for (int j = 0; j < num_bytes_of_contraction; ++j)
- address[cur_index_in_address++] = 0;
- }
- // Append the hex component's value.
- if (i != ipv6_parsed.num_hex_components) {
- // Get the 16-bit value for this hex component.
- uint16_t number = IPv6HexComponentToNumber<CHAR>(
- spec, ipv6_parsed.hex_components[i]);
- // Append to |address|, in network byte order.
- address[cur_index_in_address++] = (number & 0xFF00) >> 8;
- address[cur_index_in_address++] = (number & 0x00FF);
- }
- }
- // If there was an IPv4 section, convert it into a 32-bit number and append
- // it to |address|.
- if (ipv6_parsed.ipv4_component.is_valid()) {
- // Append the 32-bit number to |address|.
- int ignored_num_ipv4_components;
- if (CanonHostInfo::IPV4 !=
- IPv4AddressToNumber(spec,
- ipv6_parsed.ipv4_component,
- &address[cur_index_in_address],
- &ignored_num_ipv4_components))
- return false;
- }
- return true;
- }
- // Searches for the longest sequence of zeros in |address|, and writes the
- // range into |contraction_range|. The run of zeros must be at least 16 bits,
- // and if there is a tie the first is chosen.
- void ChooseIPv6ContractionRange(const unsigned char address[16],
- Component* contraction_range) {
- // The longest run of zeros in |address| seen so far.
- Component max_range;
- // The current run of zeros in |address| being iterated over.
- Component cur_range;
- for (int i = 0; i < 16; i += 2) {
- // Test for 16 bits worth of zero.
- bool is_zero = (address[i] == 0 && address[i + 1] == 0);
- if (is_zero) {
- // Add the zero to the current range (or start a new one).
- if (!cur_range.is_valid())
- cur_range = Component(i, 0);
- cur_range.len += 2;
- }
- if (!is_zero || i == 14) {
- // Just completed a run of zeros. If the run is greater than 16 bits,
- // it is a candidate for the contraction.
- if (cur_range.len > 2 && cur_range.len > max_range.len) {
- max_range = cur_range;
- }
- cur_range.reset();
- }
- }
- *contraction_range = max_range;
- }
- // Return true if we've made a final IPV6/BROKEN decision, false if the result
- // is NEUTRAL, and we could use a second opinion.
- template<typename CHAR, typename UCHAR>
- bool DoCanonicalizeIPv6Address(const CHAR* spec,
- const Component& host,
- CanonOutput* output,
- CanonHostInfo* host_info) {
- // Turn the IP address into a 128 bit number.
- if (!IPv6AddressToNumber(spec, host, host_info->address)) {
- // If it's not an IPv6 address, scan for characters that should *only*
- // exist in an IPv6 address.
- for (int i = host.begin; i < host.end(); i++) {
- switch (spec[i]) {
- case '[':
- case ']':
- case ':':
- host_info->family = CanonHostInfo::BROKEN;
- return true;
- }
- }
- // No invalid characters. Could still be IPv4 or a hostname.
- host_info->family = CanonHostInfo::NEUTRAL;
- return false;
- }
- host_info->out_host.begin = output->length();
- output->push_back('[');
- AppendIPv6Address(host_info->address, output);
- output->push_back(']');
- host_info->out_host.len = output->length() - host_info->out_host.begin;
- host_info->family = CanonHostInfo::IPV6;
- return true;
- }
- } // namespace
- void AppendIPv4Address(const unsigned char address[4], CanonOutput* output) {
- for (int i = 0; i < 4; i++) {
- char str[16];
- _itoa_s(address[i], str, 10);
- for (int ch = 0; str[ch] != 0; ch++)
- output->push_back(str[ch]);
- if (i != 3)
- output->push_back('.');
- }
- }
- void AppendIPv6Address(const unsigned char address[16], CanonOutput* output) {
- // We will output the address according to the rules in:
- // http://tools.ietf.org/html/draft-kawamura-ipv6-text-representation-01#section-4
- // Start by finding where to place the "::" contraction (if any).
- Component contraction_range;
- ChooseIPv6ContractionRange(address, &contraction_range);
- for (int i = 0; i <= 14;) {
- // We check 2 bytes at a time, from bytes (0, 1) to (14, 15), inclusive.
- DCHECK(i % 2 == 0);
- if (i == contraction_range.begin && contraction_range.len > 0) {
- // Jump over the contraction.
- if (i == 0)
- output->push_back(':');
- output->push_back(':');
- i = contraction_range.end();
- } else {
- // Consume the next 16 bits from |address|.
- int x = address[i] << 8 | address[i + 1];
- i += 2;
- // Stringify the 16 bit number (at most requires 4 hex digits).
- char str[5];
- _itoa_s(x, str, 16);
- for (int ch = 0; str[ch] != 0; ++ch)
- output->push_back(str[ch]);
- // Put a colon after each number, except the last.
- if (i < 16)
- output->push_back(':');
- }
- }
- }
- void CanonicalizeIPAddress(const char* spec,
- const Component& host,
- CanonOutput* output,
- CanonHostInfo* host_info) {
- if (DoCanonicalizeIPv4Address<char, unsigned char>(
- spec, host, output, host_info))
- return;
- if (DoCanonicalizeIPv6Address<char, unsigned char>(
- spec, host, output, host_info))
- return;
- }
- void CanonicalizeIPAddress(const char16_t* spec,
- const Component& host,
- CanonOutput* output,
- CanonHostInfo* host_info) {
- if (DoCanonicalizeIPv4Address<char16_t, char16_t>(spec, host, output,
- host_info))
- return;
- if (DoCanonicalizeIPv6Address<char16_t, char16_t>(spec, host, output,
- host_info))
- return;
- }
- CanonHostInfo::Family IPv4AddressToNumber(const char* spec,
- const Component& host,
- unsigned char address[4],
- int* num_ipv4_components) {
- return DoIPv4AddressToNumber<char, unsigned char>(spec, host, address,
- num_ipv4_components);
- }
- CanonHostInfo::Family IPv4AddressToNumber(const char16_t* spec,
- const Component& host,
- unsigned char address[4],
- int* num_ipv4_components) {
- return DoIPv4AddressToNumber<char16_t, char16_t>(spec, host, address,
- num_ipv4_components);
- }
- bool IPv6AddressToNumber(const char* spec,
- const Component& host,
- unsigned char address[16]) {
- return DoIPv6AddressToNumber<char, unsigned char>(spec, host, address);
- }
- bool IPv6AddressToNumber(const char16_t* spec,
- const Component& host,
- unsigned char address[16]) {
- return DoIPv6AddressToNumber<char16_t, char16_t>(spec, host, address);
- }
- } // namespace url
|