slow_test.go

     1  // Copyright 2020 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package netip_test
     6  
     7  import (
     8  	"fmt"
     9  	. "net/netip"
    10  	"strconv"
    11  	"strings"
    12  )
    13  
    14  // zeros is a slice of eight stringified zeros. It's used in
    15  // parseIPSlow to construct slices of specific amounts of zero fields,
    16  // from 1 to 8.
    17  var zeros = []string{"0", "0", "0", "0", "0", "0", "0", "0"}
    18  
    19  // parseIPSlow is like ParseIP, but aims for readability above
    20  // speed. It's the reference implementation for correctness checking
    21  // and against which we measure optimized parsers.
    22  //
    23  // parseIPSlow understands the following forms of IP addresses:
    24  //   - Regular IPv4: 1.2.3.4
    25  //   - IPv4 with many leading zeros: 0000001.0000002.0000003.0000004
    26  //   - Regular IPv6: 1111:2222:3333:4444:5555:6666:7777:8888
    27  //   - IPv6 with many leading zeros: 00000001:0000002:0000003:0000004:0000005:0000006:0000007:0000008
    28  //   - IPv6 with zero blocks elided: 1111:2222::7777:8888
    29  //   - IPv6 with trailing 32 bits expressed as IPv4: 1111:2222:3333:4444:5555:6666:77.77.88.88
    30  //
    31  // It does not process the following IP address forms, which have been
    32  // varyingly accepted by some programs due to an under-specification
    33  // of the shapes of IPv4 addresses:
    34  //
    35  //   - IPv4 as a single 32-bit uint: 4660 (same as "1.2.3.4")
    36  //   - IPv4 with octal numbers: 0300.0250.0.01 (same as "192.168.0.1")
    37  //   - IPv4 with hex numbers: 0xc0.0xa8.0x0.0x1 (same as "192.168.0.1")
    38  //   - IPv4 in "class-B style": 1.2.52 (same as "1.2.3.4")
    39  //   - IPv4 in "class-A style": 1.564 (same as "1.2.3.4")
    40  func parseIPSlow(s string) (Addr, error) {
    41  	// Identify and strip out the zone, if any. There should be 0 or 1
    42  	// '%' in the string.
    43  	var zone string
    44  	fs := strings.Split(s, "%")
    45  	switch len(fs) {
    46  	case 1:
    47  		// No zone, that's fine.
    48  	case 2:
    49  		s, zone = fs[0], fs[1]
    50  		if zone == "" {
    51  			return Addr{}, fmt.Errorf("netaddr.ParseIP(%q): no zone after zone specifier", s)
    52  		}
    53  	default:
    54  		return Addr{}, fmt.Errorf("netaddr.ParseIP(%q): too many zone specifiers", s) // TODO: less specific?
    55  	}
    56  
    57  	// IPv4 by itself is easy to do in a helper.
    58  	if strings.Count(s, ":") == 0 {
    59  		if zone != "" {
    60  			return Addr{}, fmt.Errorf("netaddr.ParseIP(%q): IPv4 addresses cannot have a zone", s)
    61  		}
    62  		return parseIPv4Slow(s)
    63  	}
    64  
    65  	normal, err := normalizeIPv6Slow(s)
    66  	if err != nil {
    67  		return Addr{}, err
    68  	}
    69  
    70  	// At this point, we've normalized the address back into 8 hex
    71  	// fields of 16 bits each. Parse that.
    72  	fs = strings.Split(normal, ":")
    73  	if len(fs) != 8 {
    74  		return Addr{}, fmt.Errorf("netaddr.ParseIP(%q): wrong size address", s)
    75  	}
    76  	var ret [16]byte
    77  	for i, f := range fs {
    78  		a, b, err := parseWord(f)
    79  		if err != nil {
    80  			return Addr{}, err
    81  		}
    82  		ret[i*2] = a
    83  		ret[i*2+1] = b
    84  	}
    85  
    86  	return AddrFrom16(ret).WithZone(zone), nil
    87  }
    88  
    89  // normalizeIPv6Slow expands s, which is assumed to be an IPv6
    90  // address, to its canonical text form.
    91  //
    92  // The canonical form of an IPv6 address is 8 colon-separated fields,
    93  // where each field should be a hex value from 0 to ffff. This
    94  // function does not verify the contents of each field.
    95  //
    96  // This function performs two transformations:
    97  //   - The last 32 bits of an IPv6 address may be represented in
    98  //     IPv4-style dotted quad form, as in 1:2:3:4:5:6:7.8.9.10. That
    99  //     address is transformed to its hex equivalent,
   100  //     e.g. 1:2:3:4:5:6:708:90a.
   101  //   - An address may contain one "::", which expands into as many
   102  //     16-bit blocks of zeros as needed to make the address its correct
   103  //     full size. For example, fe80::1:2 expands to fe80:0:0:0:0:0:1:2.
   104  //
   105  // Both short forms may be present in a single address,
   106  // e.g. fe80::1.2.3.4.
   107  func normalizeIPv6Slow(orig string) (string, error) {
   108  	s := orig
   109  
   110  	// Find and convert an IPv4 address in the final field, if any.
   111  	i := strings.LastIndex(s, ":")
   112  	if i == -1 {
   113  		return "", fmt.Errorf("netaddr.ParseIP(%q): invalid IP address", orig)
   114  	}
   115  	if strings.Contains(s[i+1:], ".") {
   116  		ip, err := parseIPv4Slow(s[i+1:])
   117  		if err != nil {
   118  			return "", err
   119  		}
   120  		a4 := ip.As4()
   121  		s = fmt.Sprintf("%s:%02x%02x:%02x%02x", s[:i], a4[0], a4[1], a4[2], a4[3])
   122  	}
   123  
   124  	// Find and expand a ::, if any.
   125  	fs := strings.Split(s, "::")
   126  	switch len(fs) {
   127  	case 1:
   128  		// No ::, nothing to do.
   129  	case 2:
   130  		lhs, rhs := fs[0], fs[1]
   131  		// Found a ::, figure out how many zero blocks need to be
   132  		// inserted.
   133  		nblocks := strings.Count(lhs, ":") + strings.Count(rhs, ":")
   134  		if lhs != "" {
   135  			nblocks++
   136  		}
   137  		if rhs != "" {
   138  			nblocks++
   139  		}
   140  		if nblocks > 7 {
   141  			return "", fmt.Errorf("netaddr.ParseIP(%q): address too long", orig)
   142  		}
   143  		fs = nil
   144  		// Either side of the :: can be empty. We don't want empty
   145  		// fields to feature in the final normalized address.
   146  		if lhs != "" {
   147  			fs = append(fs, lhs)
   148  		}
   149  		fs = append(fs, zeros[:8-nblocks]...)
   150  		if rhs != "" {
   151  			fs = append(fs, rhs)
   152  		}
   153  		s = strings.Join(fs, ":")
   154  	default:
   155  		// Too many ::
   156  		return "", fmt.Errorf("netaddr.ParseIP(%q): invalid IP address", orig)
   157  	}
   158  
   159  	return s, nil
   160  }
   161  
   162  // parseIPv4Slow parses and returns an IPv4 address in dotted quad
   163  // form, e.g. "192.168.0.1". It is slow but easy to read, and the
   164  // reference implementation against which we compare faster
   165  // implementations for correctness.
   166  func parseIPv4Slow(s string) (Addr, error) {
   167  	fs := strings.Split(s, ".")
   168  	if len(fs) != 4 {
   169  		return Addr{}, fmt.Errorf("netaddr.ParseIP(%q): invalid IP address", s)
   170  	}
   171  	var ret [4]byte
   172  	for i := range ret {
   173  		val, err := strconv.ParseUint(fs[i], 10, 8)
   174  		if err != nil {
   175  			return Addr{}, err
   176  		}
   177  		ret[i] = uint8(val)
   178  	}
   179  	return AddrFrom4([4]byte{ret[0], ret[1], ret[2], ret[3]}), nil
   180  }
   181  
   182  // parseWord converts a 16-bit hex string into its corresponding
   183  // two-byte value.
   184  func parseWord(s string) (byte, byte, error) {
   185  	if len(s) > 4 {
   186  		return 0, 0, fmt.Errorf("parseWord(%q): invalid word", s)
   187  	}
   188  	ret, err := strconv.ParseUint(s, 16, 16)
   189  	if err != nil {
   190  		return 0, 0, err
   191  	}
   192  	return uint8(ret >> 8), uint8(ret), nil
   193  }
   194
View as plain text