vendor/github.com/apparentlymart/go-cidr/cidr/cidr.go

   1 // Package cidr is a collection of assorted utilities for computing
   2 // network and host addresses within network ranges.
   3 //
   4 // It expects a CIDR-type address structure where addresses are divided into
   5 // some number of prefix bits representing the network and then the remaining
   6 // suffix bits represent the host.
   7 //
   8 // For example, it can help to calculate addresses for sub-networks of a
   9 // parent network, or to calculate host addresses within a particular prefix.
  10 //
  11 // At present this package is prioritizing simplicity of implementation and
  12 // de-prioritizing speed and memory usage. Thus caution is advised before
  13 // using this package in performance-critical applications or hot codepaths.
  14 // Patches to improve the speed and memory usage may be accepted as long as
  15 // they do not result in a significant increase in code complexity.
  16 package cidr
  17
  18 import (
  19         "fmt"
  20         "math/big"
  21         "net"
  22 )
  23
  24 // Subnet takes a parent CIDR range and creates a subnet within it
  25 // with the given number of additional prefix bits and the given
  26 // network number.
  27 //
  28 // For example, 10.3.0.0/16, extended by 8 bits, with a network number
  29 // of 5, becomes 10.3.5.0/24 .
  30 func Subnet(base *net.IPNet, newBits int, num int) (*net.IPNet, error) {
  31         ip := base.IP
  32         mask := base.Mask
  33
  34         parentLen, addrLen := mask.Size()
  35         newPrefixLen := parentLen + newBits
  36
  37         if newPrefixLen > addrLen {
  38                 return nil, fmt.Errorf("insufficient address space to extend prefix of %d by %d", parentLen, newBits)
  39         }
  40
  41         maxNetNum := uint64(1<<uint64(newBits)) - 1
  42         if uint64(num) > maxNetNum {
  43                 return nil, fmt.Errorf("prefix extension of %d does not accommodate a subnet numbered %d", newBits, num)
  44         }
  45
  46         return &net.IPNet{
  47                 IP:   insertNumIntoIP(ip, num, newPrefixLen),
  48                 Mask: net.CIDRMask(newPrefixLen, addrLen),
  49         }, nil
  50 }
  51
  52 // Host takes a parent CIDR range and turns it into a host IP address with
  53 // the given host number.
  54 //
  55 // For example, 10.3.0.0/16 with a host number of 2 gives 10.3.0.2.
  56 func Host(base *net.IPNet, num int) (net.IP, error) {
  57         ip := base.IP
  58         mask := base.Mask
  59
  60         parentLen, addrLen := mask.Size()
  61         hostLen := addrLen - parentLen
  62
  63         maxHostNum := uint64(1<<uint64(hostLen)) - 1
  64
  65         numUint64 := uint64(num)
  66         if num < 0 {
  67                 numUint64 = uint64(-num) - 1
  68                 num = int(maxHostNum - numUint64)
  69         }
  70
  71         if numUint64 > maxHostNum {
  72                 return nil, fmt.Errorf("prefix of %d does not accommodate a host numbered %d", parentLen, num)
  73         }
  74         var bitlength int
  75         if ip.To4() != nil {
  76                 bitlength = 32
  77         } else {
  78                 bitlength = 128
  79         }
  80         return insertNumIntoIP(ip, num, bitlength), nil
  81 }
  82
  83 // AddressRange returns the first and last addresses in the given CIDR range.
  84 func AddressRange(network *net.IPNet) (net.IP, net.IP) {
  85         // the first IP is easy
  86         firstIP := network.IP
  87
  88         // the last IP is the network address OR NOT the mask address
  89         prefixLen, bits := network.Mask.Size()
  90         if prefixLen == bits {
  91                 // Easy!
  92                 // But make sure that our two slices are distinct, since they
  93                 // would be in all other cases.
  94                 lastIP := make([]byte, len(firstIP))
  95                 copy(lastIP, firstIP)
  96                 return firstIP, lastIP
  97         }
  98
  99         firstIPInt, bits := ipToInt(firstIP)
 100         hostLen := uint(bits) - uint(prefixLen)
 101         lastIPInt := big.NewInt(1)
 102         lastIPInt.Lsh(lastIPInt, hostLen)
 103         lastIPInt.Sub(lastIPInt, big.NewInt(1))
 104         lastIPInt.Or(lastIPInt, firstIPInt)
 105
 106         return firstIP, intToIP(lastIPInt, bits)
 107 }
 108
 109 // AddressCount returns the number of distinct host addresses within the given
 110 // CIDR range.
 111 //
 112 // Since the result is a uint64, this function returns meaningful information
 113 // only for IPv4 ranges and IPv6 ranges with a prefix size of at least 65.
 114 func AddressCount(network *net.IPNet) uint64 {
 115         prefixLen, bits := network.Mask.Size()
 116         return 1 << (uint64(bits) - uint64(prefixLen))
 117 }
 118
 119 //VerifyNoOverlap takes a list subnets and supernet (CIDRBlock) and verifies
 120 //none of the subnets overlap and all subnets are in the supernet
 121 //it returns an error if any of those conditions are not satisfied
 122 func VerifyNoOverlap(subnets []*net.IPNet, CIDRBlock *net.IPNet) error {
 123         firstLastIP := make([][]net.IP, len(subnets))
 124         for i, s := range subnets {
 125                 first, last := AddressRange(s)
 126                 firstLastIP[i] = []net.IP{first, last}
 127         }
 128         for i, s := range subnets {
 129                 if !CIDRBlock.Contains(firstLastIP[i][0]) || !CIDRBlock.Contains(firstLastIP[i][1]) {
 130                         return fmt.Errorf("%s does not fully contain %s", CIDRBlock.String(), s.String())
 131                 }
 132                 for j := i + 1; j < len(subnets); j++ {
 133                         first := firstLastIP[j][0]
 134                         last := firstLastIP[j][1]
 135                         if s.Contains(first) || s.Contains(last) {
 136                                 return fmt.Errorf("%s overlaps with %s", subnets[j].String(), s.String())
 137                         }
 138                 }
 139         }
 140         return nil
 141 }
 142
 143 // PreviousSubnet returns the subnet of the desired mask in the IP space
 144 // just lower than the start of IPNet provided. If the IP space rolls over
 145 // then the second return value is true
 146 func PreviousSubnet(network *net.IPNet, prefixLen int) (*net.IPNet, bool) {
 147         startIP := checkIPv4(network.IP)
 148         previousIP := make(net.IP, len(startIP))
 149         copy(previousIP, startIP)
 150         cMask := net.CIDRMask(prefixLen, 8*len(previousIP))
 151         previousIP = Dec(previousIP)
 152         previous := &net.IPNet{IP: previousIP.Mask(cMask), Mask: cMask}
 153         if startIP.Equal(net.IPv4zero) || startIP.Equal(net.IPv6zero) {
 154                 return previous, true
 155         }
 156         return previous, false
 157 }
 158
 159 // NextSubnet returns the next available subnet of the desired mask size
 160 // starting for the maximum IP of the offset subnet
 161 // If the IP exceeds the maxium IP then the second return value is true
 162 func NextSubnet(network *net.IPNet, prefixLen int) (*net.IPNet, bool) {
 163         _, currentLast := AddressRange(network)
 164         mask := net.CIDRMask(prefixLen, 8*len(currentLast))
 165         currentSubnet := &net.IPNet{IP: currentLast.Mask(mask), Mask: mask}
 166         _, last := AddressRange(currentSubnet)
 167         last = Inc(last)
 168         next := &net.IPNet{IP: last.Mask(mask), Mask: mask}
 169         if last.Equal(net.IPv4zero) || last.Equal(net.IPv6zero) {
 170                 return next, true
 171         }
 172         return next, false
 173 }
 174
 175 //Inc increases the IP by one this returns a new []byte for the IP
 176 func Inc(IP net.IP) net.IP {
 177         IP = checkIPv4(IP)
 178         incIP := make([]byte, len(IP))
 179         copy(incIP, IP)
 180         for j := len(incIP) - 1; j >= 0; j-- {
 181                 incIP[j]++
 182                 if incIP[j] > 0 {
 183                         break
 184                 }
 185         }
 186         return incIP
 187 }
 188
 189 //Dec decreases the IP by one this returns a new []byte for the IP
 190 func Dec(IP net.IP) net.IP {
 191         IP = checkIPv4(IP)
 192         decIP := make([]byte, len(IP))
 193         copy(decIP, IP)
 194         decIP = checkIPv4(decIP)
 195         for j := len(decIP) - 1; j >= 0; j-- {
 196                 decIP[j]--
 197                 if decIP[j] < 255 {
 198                         break
 199                 }
 200         }
 201         return decIP
 202 }
 203
 204 func checkIPv4(ip net.IP) net.IP {
 205         // Go for some reason allocs IPv6len for IPv4 so we have to correct it
 206         if v4 := ip.To4(); v4 != nil {
 207                 return v4
 208         }
 209         return ip
 210 }