// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// IP address manipulations
//
// IPv4 addresses are 4 bytes; IPv6 addresses are 16 bytes.
// An IPv4 address can be converted to an IPv6 address by
// adding a canonical prefix (10 zeros, 2 0xFFs).
// This library accepts either size of byte slice but always
// returns 16-byte addresses.

package net

import 

// IP address lengths (bytes).
const (
	IPv4len = 4
	IPv6len = 16
)

// An IP is a single IP address, a slice of bytes.
// Functions in this package accept either 4-byte (IPv4)
// or 16-byte (IPv6) slices as input.
//
// Note that in this documentation, referring to an
// IP address as an IPv4 address or an IPv6 address
// is a semantic property of the address, not just the
// length of the byte slice: a 16-byte slice can still
// be an IPv4 address.
type IP []byte

// An IPMask is a bitmask that can be used to manipulate
// IP addresses for IP addressing and routing.
//
// See type IPNet and func ParseCIDR for details.
type IPMask []byte

// An IPNet represents an IP network.
type IPNet struct {
	IP   IP     // network number
	Mask IPMask // network mask
}

// IPv4 returns the IP address (in 16-byte form) of the
// IPv4 address a.b.c.d.
func (, , ,  byte) IP {
	 := make(IP, IPv6len)
	copy(, v4InV6Prefix)
	[12] = 
	[13] = 
	[14] = 
	[15] = 
	return 
}

var v4InV6Prefix = []byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xff, 0xff}

// IPv4Mask returns the IP mask (in 4-byte form) of the
// IPv4 mask a.b.c.d.
func (, , ,  byte) IPMask {
	 := make(IPMask, IPv4len)
	[0] = 
	[1] = 
	[2] = 
	[3] = 
	return 
}

// CIDRMask returns an IPMask consisting of 'ones' 1 bits
// followed by 0s up to a total length of 'bits' bits.
// For a mask of this form, CIDRMask is the inverse of IPMask.Size.
func (,  int) IPMask {
	if  != 8*IPv4len &&  != 8*IPv6len {
		return nil
	}
	if  < 0 ||  >  {
		return nil
	}
	 :=  / 8
	 := make(IPMask, )
	 := uint()
	for  := 0;  < ; ++ {
		if  >= 8 {
			[] = 0xff
			 -= 8
			continue
		}
		[] = ^byte(0xff >> )
		 = 0
	}
	return 
}

// Well-known IPv4 addresses
var (
	IPv4bcast     = IPv4(255, 255, 255, 255) // limited broadcast
	IPv4allsys    = IPv4(224, 0, 0, 1)       // all systems
	IPv4allrouter = IPv4(224, 0, 0, 2)       // all routers
	IPv4zero      = IPv4(0, 0, 0, 0)         // all zeros
)

// Well-known IPv6 addresses
var (
	IPv6zero                   = IP{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
	IPv6unspecified            = IP{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
	IPv6loopback               = IP{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}
	IPv6interfacelocalallnodes = IP{0xff, 0x01, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x01}
	IPv6linklocalallnodes      = IP{0xff, 0x02, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x01}
	IPv6linklocalallrouters    = IP{0xff, 0x02, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x02}
)

// IsUnspecified reports whether ip is an unspecified address, either
// the IPv4 address "0.0.0.0" or the IPv6 address "::".
func ( IP) () bool {
	return .Equal(IPv4zero) || .Equal(IPv6unspecified)
}

// IsLoopback reports whether ip is a loopback address.
func ( IP) () bool {
	if  := .To4();  != nil {
		return [0] == 127
	}
	return .Equal(IPv6loopback)
}

// IsMulticast reports whether ip is a multicast address.
func ( IP) () bool {
	if  := .To4();  != nil {
		return [0]&0xf0 == 0xe0
	}
	return len() == IPv6len && [0] == 0xff
}

// IsInterfaceLocalMulticast reports whether ip is
// an interface-local multicast address.
func ( IP) () bool {
	return len() == IPv6len && [0] == 0xff && [1]&0x0f == 0x01
}

// IsLinkLocalMulticast reports whether ip is a link-local
// multicast address.
func ( IP) () bool {
	if  := .To4();  != nil {
		return [0] == 224 && [1] == 0 && [2] == 0
	}
	return len() == IPv6len && [0] == 0xff && [1]&0x0f == 0x02
}

// IsLinkLocalUnicast reports whether ip is a link-local
// unicast address.
func ( IP) () bool {
	if  := .To4();  != nil {
		return [0] == 169 && [1] == 254
	}
	return len() == IPv6len && [0] == 0xfe && [1]&0xc0 == 0x80
}

// IsGlobalUnicast reports whether ip is a global unicast
// address.
//
// The identification of global unicast addresses uses address type
// identification as defined in RFC 1122, RFC 4632 and RFC 4291 with
// the exception of IPv4 directed broadcast addresses.
// It returns true even if ip is in IPv4 private address space or
// local IPv6 unicast address space.
func ( IP) () bool {
	return (len() == IPv4len || len() == IPv6len) &&
		!.Equal(IPv4bcast) &&
		!.IsUnspecified() &&
		!.IsLoopback() &&
		!.IsMulticast() &&
		!.IsLinkLocalUnicast()
}

// Is p all zeros?
func isZeros( IP) bool {
	for  := 0;  < len(); ++ {
		if [] != 0 {
			return false
		}
	}
	return true
}

// To4 converts the IPv4 address ip to a 4-byte representation.
// If ip is not an IPv4 address, To4 returns nil.
func ( IP) () IP {
	if len() == IPv4len {
		return 
	}
	if len() == IPv6len &&
		isZeros([0:10]) &&
		[10] == 0xff &&
		[11] == 0xff {
		return [12:16]
	}
	return nil
}

// To16 converts the IP address ip to a 16-byte representation.
// If ip is not an IP address (it is the wrong length), To16 returns nil.
func ( IP) () IP {
	if len() == IPv4len {
		return IPv4([0], [1], [2], [3])
	}
	if len() == IPv6len {
		return 
	}
	return nil
}

// Default route masks for IPv4.
var (
	classAMask = IPv4Mask(0xff, 0, 0, 0)
	classBMask = IPv4Mask(0xff, 0xff, 0, 0)
	classCMask = IPv4Mask(0xff, 0xff, 0xff, 0)
)

// DefaultMask returns the default IP mask for the IP address ip.
// Only IPv4 addresses have default masks; DefaultMask returns
// nil if ip is not a valid IPv4 address.
func ( IP) () IPMask {
	if  = .To4();  == nil {
		return nil
	}
	switch {
	case [0] < 0x80:
		return classAMask
	case [0] < 0xC0:
		return classBMask
	default:
		return classCMask
	}
}

func allFF( []byte) bool {
	for ,  := range  {
		if  != 0xff {
			return false
		}
	}
	return true
}

// Mask returns the result of masking the IP address ip with mask.
func ( IP) ( IPMask) IP {
	if len() == IPv6len && len() == IPv4len && allFF([:12]) {
		 = [12:]
	}
	if len() == IPv4len && len() == IPv6len && bytealg.Equal([:12], v4InV6Prefix) {
		 = [12:]
	}
	 := len()
	if  != len() {
		return nil
	}
	 := make(IP, )
	for  := 0;  < ; ++ {
		[] = [] & []
	}
	return 
}

// ubtoa encodes the string form of the integer v to dst[start:] and
// returns the number of bytes written to dst. The caller must ensure
// that dst has sufficient length.
func ubtoa( []byte,  int,  byte) int {
	if  < 10 {
		[] =  + '0'
		return 1
	} else if  < 100 {
		[+1] = %10 + '0'
		[] = /10 + '0'
		return 2
	}

	[+2] = %10 + '0'
	[+1] = (/10)%10 + '0'
	[] = /100 + '0'
	return 3
}

// String returns the string form of the IP address ip.
// It returns one of 4 forms:
//   - "<nil>", if ip has length 0
//   - dotted decimal ("192.0.2.1"), if ip is an IPv4 or IP4-mapped IPv6 address
//   - IPv6 ("2001:db8::1"), if ip is a valid IPv6 address
//   - the hexadecimal form of ip, without punctuation, if no other cases apply
func ( IP) () string {
	 := 

	if len() == 0 {
		return "<nil>"
	}

	// If IPv4, use dotted notation.
	if  := .To4(); len() == IPv4len {
		const  = len("255.255.255.255")
		 := make([]byte, )

		 := ubtoa(, 0, [0])
		[] = '.'
		++

		 += ubtoa(, , [1])
		[] = '.'
		++

		 += ubtoa(, , [2])
		[] = '.'
		++

		 += ubtoa(, , [3])
		return string([:])
	}
	if len() != IPv6len {
		return "?" + hexString()
	}

	// Find longest run of zeros.
	 := -1
	 := -1
	for  := 0;  < IPv6len;  += 2 {
		 := 
		for  < IPv6len && [] == 0 && [+1] == 0 {
			 += 2
		}
		if  >  && - > - {
			 = 
			 = 
			 = 
		}
	}
	// The symbol "::" MUST NOT be used to shorten just one 16 bit 0 field.
	if - <= 2 {
		 = -1
		 = -1
	}

	const  = len("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff")
	 := make([]byte, 0, )

	// Print with possible :: in place of run of zeros
	for  := 0;  < IPv6len;  += 2 {
		if  ==  {
			 = append(, ':', ':')
			 = 
			if  >= IPv6len {
				break
			}
		} else if  > 0 {
			 = append(, ':')
		}
		 = appendHex(, (uint32([])<<8)|uint32([+1]))
	}
	return string()
}

func hexString( []byte) string {
	 := make([]byte, len()*2)
	for ,  := range  {
		[*2], [*2+1] = hexDigit[>>4], hexDigit[&0xf]
	}
	return string()
}

// ipEmptyString is like ip.String except that it returns
// an empty string when ip is unset.
func ipEmptyString( IP) string {
	if len() == 0 {
		return ""
	}
	return .String()
}

// MarshalText implements the encoding.TextMarshaler interface.
// The encoding is the same as returned by String, with one exception:
// When len(ip) is zero, it returns an empty slice.
func ( IP) () ([]byte, error) {
	if len() == 0 {
		return []byte(""), nil
	}
	if len() != IPv4len && len() != IPv6len {
		return nil, &AddrError{Err: "invalid IP address", Addr: hexString()}
	}
	return []byte(.String()), nil
}

// UnmarshalText implements the encoding.TextUnmarshaler interface.
// The IP address is expected in a form accepted by ParseIP.
func ( *IP) ( []byte) error {
	if len() == 0 {
		* = nil
		return nil
	}
	 := string()
	 := ParseIP()
	if  == nil {
		return &ParseError{Type: "IP address", Text: }
	}
	* = 
	return nil
}

// Equal reports whether ip and x are the same IP address.
// An IPv4 address and that same address in IPv6 form are
// considered to be equal.
func ( IP) ( IP) bool {
	if len() == len() {
		return bytealg.Equal(, )
	}
	if len() == IPv4len && len() == IPv6len {
		return bytealg.Equal([0:12], v4InV6Prefix) && bytealg.Equal(, [12:])
	}
	if len() == IPv6len && len() == IPv4len {
		return bytealg.Equal([0:12], v4InV6Prefix) && bytealg.Equal([12:], )
	}
	return false
}

func ( IP) ( IP) bool {
	return .To4() != nil && .To4() != nil || .To16() != nil && .To4() == nil && .To16() != nil && .To4() == nil
}

// If mask is a sequence of 1 bits followed by 0 bits,
// return the number of 1 bits.
func simpleMaskLength( IPMask) int {
	var  int
	for ,  := range  {
		if  == 0xff {
			 += 8
			continue
		}
		// found non-ff byte
		// count 1 bits
		for &0x80 != 0 {
			++
			 <<= 1
		}
		// rest must be 0 bits
		if  != 0 {
			return -1
		}
		for ++;  < len(); ++ {
			if [] != 0 {
				return -1
			}
		}
		break
	}
	return 
}

// Size returns the number of leading ones and total bits in the mask.
// If the mask is not in the canonical form--ones followed by zeros--then
// Size returns 0, 0.
func ( IPMask) () (,  int) {
	,  = simpleMaskLength(), len()*8
	if  == -1 {
		return 0, 0
	}
	return
}

// String returns the hexadecimal form of m, with no punctuation.
func ( IPMask) () string {
	if len() == 0 {
		return "<nil>"
	}
	return hexString()
}

func networkNumberAndMask( *IPNet) ( IP,  IPMask) {
	if  = .IP.To4();  == nil {
		 = .IP
		if len() != IPv6len {
			return nil, nil
		}
	}
	 = .Mask
	switch len() {
	case IPv4len:
		if len() != IPv4len {
			return nil, nil
		}
	case IPv6len:
		if len() == IPv4len {
			 = [12:]
		}
	default:
		return nil, nil
	}
	return
}

// Contains reports whether the network includes ip.
func ( *IPNet) ( IP) bool {
	,  := networkNumberAndMask()
	if  := .To4();  != nil {
		 = 
	}
	 := len()
	if  != len() {
		return false
	}
	for  := 0;  < ; ++ {
		if []&[] != []&[] {
			return false
		}
	}
	return true
}

// Network returns the address's network name, "ip+net".
func ( *IPNet) () string { return "ip+net" }

// String returns the CIDR notation of n like "192.0.2.0/24"
// or "2001:db8::/48" as defined in RFC 4632 and RFC 4291.
// If the mask is not in the canonical form, it returns the
// string which consists of an IP address, followed by a slash
// character and a mask expressed as hexadecimal form with no
// punctuation like "198.51.100.0/c000ff00".
func ( *IPNet) () string {
	,  := networkNumberAndMask()
	if  == nil ||  == nil {
		return "<nil>"
	}
	 := simpleMaskLength()
	if  == -1 {
		return .String() + "/" + .String()
	}
	return .String() + "/" + uitoa(uint())
}

// Parse IPv4 address (d.d.d.d).
func parseIPv4( string) IP {
	var  [IPv4len]byte
	for  := 0;  < IPv4len; ++ {
		if len() == 0 {
			// Missing octets.
			return nil
		}
		if  > 0 {
			if [0] != '.' {
				return nil
			}
			 = [1:]
		}
		, ,  := dtoi()
		if ! ||  > 0xFF {
			return nil
		}
		 = [:]
		[] = byte()
	}
	if len() != 0 {
		return nil
	}
	return IPv4([0], [1], [2], [3])
}

// parseIPv6Zone parses s as a literal IPv6 address and its associated zone
// identifier which is described in RFC 4007.
func parseIPv6Zone( string) (IP, string) {
	,  := splitHostZone()
	return parseIPv6(), 
}

// parseIPv6 parses s as a literal IPv6 address described in RFC 4291
// and RFC 5952.
func parseIPv6( string) ( IP) {
	 = make(IP, IPv6len)
	 := -1 // position of ellipsis in ip

	// Might have leading ellipsis
	if len() >= 2 && [0] == ':' && [1] == ':' {
		 = 0
		 = [2:]
		// Might be only ellipsis
		if len() == 0 {
			return 
		}
	}

	// Loop, parsing hex numbers followed by colon.
	 := 0
	for  < IPv6len {
		// Hex number.
		, ,  := xtoi()
		if ! ||  > 0xFFFF {
			return nil
		}

		// If followed by dot, might be in trailing IPv4.
		if  < len() && [] == '.' {
			if  < 0 &&  != IPv6len-IPv4len {
				// Not the right place.
				return nil
			}
			if +IPv4len > IPv6len {
				// Not enough room.
				return nil
			}
			 := parseIPv4()
			if  == nil {
				return nil
			}
			[] = [12]
			[+1] = [13]
			[+2] = [14]
			[+3] = [15]
			 = ""
			 += IPv4len
			break
		}

		// Save this 16-bit chunk.
		[] = byte( >> 8)
		[+1] = byte()
		 += 2

		// Stop at end of string.
		 = [:]
		if len() == 0 {
			break
		}

		// Otherwise must be followed by colon and more.
		if [0] != ':' || len() == 1 {
			return nil
		}
		 = [1:]

		// Look for ellipsis.
		if [0] == ':' {
			if  >= 0 { // already have one
				return nil
			}
			 = 
			 = [1:]
			if len() == 0 { // can be at end
				break
			}
		}
	}

	// Must have used entire string.
	if len() != 0 {
		return nil
	}

	// If didn't parse enough, expand ellipsis.
	if  < IPv6len {
		if  < 0 {
			return nil
		}
		 := IPv6len - 
		for  :=  - 1;  >= ; -- {
			[+] = []
		}
		for  :=  +  - 1;  >= ; -- {
			[] = 0
		}
	} else if  >= 0 {
		// Ellipsis must represent at least one 0 group.
		return nil
	}
	return 
}

// ParseIP parses s as an IP address, returning the result.
// The string s can be in IPv4 dotted decimal ("192.0.2.1"), IPv6
// ("2001:db8::68"), or IPv4-mapped IPv6 ("::ffff:192.0.2.1") form.
// If s is not a valid textual representation of an IP address,
// ParseIP returns nil.
func ( string) IP {
	for  := 0;  < len(); ++ {
		switch [] {
		case '.':
			return parseIPv4()
		case ':':
			return parseIPv6()
		}
	}
	return nil
}

// parseIPZone parses s as an IP address, return it and its associated zone
// identifier (IPv6 only).
func parseIPZone( string) (IP, string) {
	for  := 0;  < len(); ++ {
		switch [] {
		case '.':
			return parseIPv4(), ""
		case ':':
			return parseIPv6Zone()
		}
	}
	return nil, ""
}

// ParseCIDR parses s as a CIDR notation IP address and prefix length,
// like "192.0.2.0/24" or "2001:db8::/32", as defined in
// RFC 4632 and RFC 4291.
//
// It returns the IP address and the network implied by the IP and
// prefix length.
// For example, ParseCIDR("192.0.2.1/24") returns the IP address
// 192.0.2.1 and the network 192.0.2.0/24.
func ( string) (IP, *IPNet, error) {
	 := bytealg.IndexByteString(, '/')
	if  < 0 {
		return nil, nil, &ParseError{Type: "CIDR address", Text: }
	}
	,  := [:], [+1:]
	 := IPv4len
	 := parseIPv4()
	if  == nil {
		 = IPv6len
		 = parseIPv6()
	}
	, ,  := dtoi()
	if  == nil || ! ||  != len() ||  < 0 ||  > 8* {
		return nil, nil, &ParseError{Type: "CIDR address", Text: }
	}
	 := CIDRMask(, 8*)
	return , &IPNet{IP: .Mask(), Mask: }, nil
}