1 // Copyright 2022-2025 The sacloud/packages-go Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 15 // Package cidr is a collection of assorted utilities for computing
16 // network and host addresses within network ranges.
17 //
18 // It expects a CIDR-type address structure where addresses are divided into
19 // some number of prefix bits representing the network and then the remaining
20 // suffix bits represent the host.
21 //
22 // For example, it can help to calculate addresses for sub-networks of a
23 // parent network, or to calculate host addresses within a particular prefix.
24 //
25 // At present this package is prioritizing simplicity of implementation and
26 // de-prioritizing speed and memory usage. Thus caution is advised before
27 // using this package in performance-critical applications or hot code paths.
28 // Patches to improve the speed and memory usage may be accepted as long as
29 // they do not result in a significant increase in code complexity.
30 //
31 // *********************************************************************************
32 // This was copied from https://github.com/apparentlymart/go-cidr
33 // ORIGINAL LICENSE is:
34 //
35 // Copyright (c) 2015 Martin Atkins
36 //
37 // Permission is hereby granted, free of charge, to any person obtaining a copy
38 // of this software and associated documentation files (the "Software"), to deal
39 // in the Software without restriction, including without limitation the rights
40 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
41 // copies of the Software, and to permit persons to whom the Software is
42 // furnished to do so, subject to the following conditions:
43 //
44 // The above copyright notice and this permission notice shall be included in
45 // all copies or substantial portions of the Software.
46 //
47 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
48 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
49 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
50 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
51 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
52 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
53 // THE SOFTWARE.
54 //
55 // *********************************************************************************
56 package cidr
57 58 import (
59 "fmt"
60 "math/big"
61 "net"
62 )
63 64 // Subnet takes a parent CIDR range and creates a subnet within it
65 // with the given number of additional prefix bits and the given
66 // network number.
67 //
68 // For example, 10.3.0.0/16, extended by 8 bits, with a network number
69 // of 5, becomes 10.3.5.0/24 .
70 func Subnet(base *net.IPNet, newBits int, num int) (*net.IPNet, error) {
71 ip := base.IP
72 mask := base.Mask
73 74 parentLen, addrLen := mask.Size()
75 newPrefixLen := parentLen + newBits
76 77 if newPrefixLen > addrLen {
78 return nil, fmt.Errorf("insufficient address space to extend prefix of %d by %d", parentLen, newBits)
79 }
80 81 maxNetNum := uint64(1<<uint64(newBits)) - 1
82 if uint64(num) > maxNetNum {
83 return nil, fmt.Errorf("prefix extension of %d does not accommodate a subnet numbered %d", newBits, num)
84 }
85 86 return &net.IPNet{
87 IP: insertNumIntoIP(ip, num, newPrefixLen),
88 Mask: net.CIDRMask(newPrefixLen, addrLen),
89 }, nil
90 }
91 92 // Host takes a parent CIDR range and turns it into a host IP address with
93 // the given host number.
94 //
95 // For example, 10.3.0.0/16 with a host number of 2 gives 10.3.0.2.
96 func Host(base *net.IPNet, num int) (net.IP, error) {
97 ip := base.IP
98 mask := base.Mask
99 100 parentLen, addrLen := mask.Size()
101 hostLen := addrLen - parentLen
102 103 maxHostNum := uint64(1<<uint64(hostLen)) - 1
104 105 numUint64 := uint64(num)
106 if num < 0 {
107 numUint64 = uint64(-num) - 1
108 num = int(maxHostNum - numUint64)
109 }
110 111 if numUint64 > maxHostNum {
112 return nil, fmt.Errorf("prefix of %d does not accommodate a host numbered %d", parentLen, num)
113 }
114 var bitlength int
115 if ip.To4() != nil {
116 bitlength = 32
117 } else {
118 bitlength = 128
119 }
120 return insertNumIntoIP(ip, num, bitlength), nil
121 }
122 123 // AddressRange returns the first and last addresses in the given CIDR range.
124 func AddressRange(network *net.IPNet) (net.IP, net.IP) {
125 // the first IP is easy
126 firstIP := network.IP
127 128 // the last IP is the network address OR NOT the mask address
129 prefixLen, bits := network.Mask.Size()
130 if prefixLen == bits {
131 // Easy!
132 // But make sure that our two slices are distinct, since they
133 // would be in all other cases.
134 lastIP := make([]byte, len(firstIP))
135 copy(lastIP, firstIP)
136 return firstIP, lastIP
137 }
138 139 firstIPInt, bits := ipToInt(firstIP)
140 hostLen := uint(bits) - uint(prefixLen)
141 lastIPInt := big.NewInt(1)
142 lastIPInt.Lsh(lastIPInt, hostLen)
143 lastIPInt.Sub(lastIPInt, big.NewInt(1))
144 lastIPInt.Or(lastIPInt, firstIPInt)
145 146 return firstIP, intToIP(lastIPInt, bits)
147 }
148 149 // AddressCount returns the number of distinct host addresses within the given
150 // CIDR range.
151 //
152 // Since the result is a uint64, this function returns meaningful information
153 // only for IPv4 ranges and IPv6 ranges with a prefix size of at least 65.
154 func AddressCount(network *net.IPNet) uint64 {
155 prefixLen, bits := network.Mask.Size()
156 return 1 << (uint64(bits) - uint64(prefixLen))
157 }
158 159 // VerifyNoOverlap takes a list subnets and supernet (CIDRBlock) and verifies
160 // none of the subnets overlap and all subnets are in the supernet
161 // it returns an error if any of those conditions are not satisfied
162 func VerifyNoOverlap(subnets []*net.IPNet, cidrBlock *net.IPNet) error {
163 firstLastIP := make([][]net.IP, len(subnets))
164 for i, s := range subnets {
165 first, last := AddressRange(s)
166 firstLastIP[i] = []net.IP{first, last}
167 }
168 for i, s := range subnets {
169 if !cidrBlock.Contains(firstLastIP[i][0]) || !cidrBlock.Contains(firstLastIP[i][1]) {
170 return fmt.Errorf("%s does not fully contain %s", cidrBlock.String(), s.String())
171 }
172 for j := 0; j < len(subnets); j++ {
173 if i == j {
174 continue
175 }
176 177 first := firstLastIP[j][0]
178 last := firstLastIP[j][1]
179 if s.Contains(first) || s.Contains(last) {
180 return fmt.Errorf("%s overlaps with %s", subnets[j].String(), s.String())
181 }
182 }
183 }
184 return nil
185 }
186 187 // PreviousSubnet returns the subnet of the desired mask in the IP space
188 // just lower than the start of IPNet provided. If the IP space rolls over
189 // then the second return value is true
190 func PreviousSubnet(network *net.IPNet, prefixLen int) (*net.IPNet, bool) {
191 startIP := checkIPv4(network.IP)
192 previousIP := make(net.IP, len(startIP))
193 copy(previousIP, startIP)
194 cMask := net.CIDRMask(prefixLen, 8*len(previousIP))
195 previousIP = Dec(previousIP)
196 previous := &net.IPNet{IP: previousIP.Mask(cMask), Mask: cMask}
197 if startIP.Equal(net.IPv4zero) || startIP.Equal(net.IPv6zero) {
198 return previous, true
199 }
200 return previous, false
201 }
202 203 // NextSubnet returns the next available subnet of the desired mask size
204 // starting for the maximum IP of the offset subnet
205 // If the IP exceeds the maximum IP then the second return value is true
206 func NextSubnet(network *net.IPNet, prefixLen int) (*net.IPNet, bool) {
207 _, currentLast := AddressRange(network)
208 mask := net.CIDRMask(prefixLen, 8*len(currentLast))
209 currentSubnet := &net.IPNet{IP: currentLast.Mask(mask), Mask: mask}
210 _, last := AddressRange(currentSubnet)
211 last = Inc(last)
212 next := &net.IPNet{IP: last.Mask(mask), Mask: mask}
213 if last.Equal(net.IPv4zero) || last.Equal(net.IPv6zero) {
214 return next, true
215 }
216 return next, false
217 }
218 219 // Inc increases the IP by one this returns a new []byte for the IP
220 func Inc(ip net.IP) net.IP {
221 ip = checkIPv4(ip)
222 incIP := make([]byte, len(ip))
223 copy(incIP, ip)
224 for j := len(incIP) - 1; j >= 0; j-- {
225 incIP[j]++
226 if incIP[j] > 0 {
227 break
228 }
229 }
230 return incIP
231 }
232 233 // Dec decreases the IP by one this returns a new []byte for the IP
234 func Dec(ip net.IP) net.IP {
235 ip = checkIPv4(ip)
236 decIP := make([]byte, len(ip))
237 copy(decIP, ip)
238 decIP = checkIPv4(decIP)
239 for j := len(decIP) - 1; j >= 0; j-- {
240 decIP[j]--
241 if decIP[j] < 255 {
242 break
243 }
244 }
245 return decIP
246 }
247 248 func checkIPv4(ip net.IP) net.IP {
249 // Go for some reason alloc IPv6len for IPv4 so we have to correct it
250 if v4 := ip.To4(); v4 != nil {
251 return v4
252 }
253 return ip
254 }
255 256 func ipToInt(ip net.IP) (*big.Int, int) {
257 val := &big.Int{}
258 val.SetBytes([]byte(ip))
259 if len(ip) == net.IPv4len { //nolint: gocritic
260 return val, 32
261 } else if len(ip) == net.IPv6len {
262 return val, 128
263 } else {
264 panic(fmt.Errorf("Unsupported address length %d", len(ip)))
265 }
266 }
267 268 func intToIP(ipInt *big.Int, bits int) net.IP {
269 ipBytes := ipInt.Bytes()
270 ret := make([]byte, bits/8)
271 // Pack our IP bytes into the end of the return array,
272 // since big.Int.Bytes() removes front zero padding.
273 for i := 1; i <= len(ipBytes); i++ {
274 ret[len(ret)-i] = ipBytes[len(ipBytes)-i]
275 }
276 return net.IP(ret)
277 }
278 279 func insertNumIntoIP(ip net.IP, num int, prefixLen int) net.IP {
280 ipInt, totalBits := ipToInt(ip)
281 bigNum := big.NewInt(int64(num))
282 bigNum.Lsh(bigNum, uint(totalBits-prefixLen))
283 ipInt.Or(ipInt, bigNum)
284 return intToIP(ipInt, totalBits)
285 }
286