-
Notifications
You must be signed in to change notification settings - Fork 4
/
summarize.go
147 lines (124 loc) · 3.34 KB
/
summarize.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
package ipx
import (
"errors"
b "math/bits"
"net"
)
var v4InV6Prefix = []byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xff, 0xff}
// SummarizeRange returns a series of networks which combined cover the range between the first and last addresses,
// inclusive.
func SummarizeRange(first, last net.IP) []*net.IPNet {
four := first.To4() != nil
if four != (last.To4() != nil) {
return nil // versions must be the same
}
if four {
return summarizeRange4(to32(first), to32(last))
}
return summarizeRange6(To128(first), To128(last))
}
func summarizeRange4(first, last uint32) (nets []*net.IPNet) {
for first <= last {
// the network will either be as long as all the trailing zeros of the first address OR the number of bits
// necessary to cover the distance between first and last address -- whichever is smaller
bits := 32
if trailingZeros := b.TrailingZeros32(first); trailingZeros < bits {
bits = trailingZeros
}
if first != 0 || last != maxUint32 { // guard overflow; this would just be 32 anyway
if diffBits := 31 - b.LeadingZeros32(last-first+1); diffBits < bits {
bits = diffBits
}
}
ipN := net.IPNet{IP: make(net.IP, len(net.IPv4zero)), Mask: net.CIDRMask(32-bits, 32)}
ipN.IP = ipN.IP[:4]
from32(first, ipN.IP)
nets = append(nets, &ipN)
first += 1 << bits
if first == 0 {
break
}
}
return
}
func summarizeRange6(first, last Uint128) (nets []*net.IPNet) {
for first.Cmp(last) != 1 {
bits := 128
if trailingZeros := trailingZeros128(first); trailingZeros < bits {
bits = trailingZeros
}
// check extremes to make sure no overflow
if first.Cmp(Uint128{0, 0}) != 0 || last.Cmp(Uint128{maxUint64, maxUint64}) != 0 {
if diffBits := 127 - leadingZeros128(last.Minus(first).Add(Uint128{0, 1})); diffBits < bits {
bits = diffBits
}
}
ipN := net.IPNet{IP: make(net.IP, net.IPv6len), Mask: net.CIDRMask(128-bits, 128)}
From128(first, ipN.IP)
nets = append(nets, &ipN)
first = first.Add(Uint128{0, 1}.Lsh(uint(bits)))
if first.Cmp(Uint128{0, 0}) == 0 {
break
}
}
return
}
func trailingZeros128(i Uint128) int {
trailingZeros := b.TrailingZeros64(i.L)
if trailingZeros == 64 {
trailingZeros += b.TrailingZeros64(i.H)
}
return trailingZeros
}
func leadingZeros128(i Uint128) int {
leadingZeros := b.LeadingZeros64(i.H)
if leadingZeros == 64 {
leadingZeros += b.LeadingZeros64(i.L)
}
return leadingZeros
}
func allFF(b []byte) bool {
for _, c := range b {
if c != 0xff {
return false
}
}
return true
}
func bytesEqual(a, b []byte) bool {
for len(a) != len(b) {
panic(errors.New("a and b are not equal length"))
}
for i := 0; i < len(a); i++ {
if a[i] != b[i] {
return false
}
}
return true
}
// NetToRange returns the start and end IPs for the given net
func NetToRange(cidr *net.IPNet) (start, end net.IP) {
// Ripped mostly from net.IP.Mask()
if cidr == nil {
panic(errors.New("cidr must not be nil"))
}
ip, mask := cidr.IP, cidr.Mask
if len(mask) == net.IPv6len && len(ip) == net.IPv4len && allFF(mask[:12]) {
mask = mask[12:]
}
// IPv4-mapped IPv6 address
if len(mask) == net.IPv4len && len(ip) == net.IPv6len && bytesEqual(ip[:12], v4InV6Prefix) {
ip = ip[12:]
}
n := len(ip)
if n != len(mask) {
return nil, nil
}
start = make(net.IP, n)
end = make(net.IP, n)
for i := 0; i < n; i++ {
start[i] = ip[i] & mask[i]
end[i] = ip[i] | ^mask[i]
}
return
}