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
|
// Copyright 2018-present the CoreDHCP Authors. All rights reserved
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree.
// Provides functions to add/subtract ipv6 addresses, for use in offset
// calculations in allocators
package allocators
import (
"bytes"
"encoding/binary"
"errors"
"math/bits"
"net"
)
// ErrOverflow is returned when arithmetic operations on IPs carry bits
// over/under the 0th or 128th bit respectively
var ErrOverflow = errors.New("Operation overflows")
// Offset returns the absolute distance between addresses `a` and `b` in units
// of /`prefixLength` subnets.
// Both addresses will have a /`prefixLength` mask applied to them, any
// differences of less than that will be discarded
// If the distance is larger than 2^64 units of /`prefixLength` an error is returned
//
// This function is used in allocators to index bitmaps by an offset from the
// first ip of the range
func Offset(a, b net.IP, prefixLength int) (uint64, error) {
if prefixLength > 128 || prefixLength < 0 {
return 0, errors.New("prefix out of range")
}
reverse := bytes.Compare(a, b)
if reverse == 0 {
return 0, nil
} else if reverse < 0 {
a, b = b, a
}
// take an example of [a:b:c:d:e:f:g:h] [1:2:3:4:5:6:7:8]
// Cut the addresses as such: [a:b:c:d|e:f:g:h] [1:2:3:4|5:6:7:8] so we can use
// native integers for computation
ah, bh := binary.BigEndian.Uint64(a[:8]), binary.BigEndian.Uint64(b[:8])
if prefixLength <= 64 {
// [(a:b:c):d|e:f:g:h] - [(1:2:3):4|5:6:7:8]
// Only the high bits matter, so the distance always fits within 64 bits.
// We shift to remove anything to the right of the cut
// [(a:b:c):d] => [0:a:b:c]
return (ah - bh) >> (64 - uint(prefixLength)), nil
}
// General case where both high and low bits matter
al, bl := binary.BigEndian.Uint64(a[8:]), binary.BigEndian.Uint64(b[8:])
distanceLow, borrow := bits.Sub64(al, bl, 0)
// This is the distance between the high bits. depending on the prefix unit, we
// will shift this distance left or right
distanceHigh, _ := bits.Sub64(ah, bh, borrow) // [a:b:c:d] - [1:2:3:4]
// [a:b:c:(d|e:f:g):h] - [1:2:3:(4|5:6:7):8]
// we cut in the low bits (eg. between the parentheses)
// To ensure we stay within 64 bits, we need to ensure [a:b:c:d] - [1:2:3:4] = [0:0:0:d-4]
// so that we don't overflow when adding to the low bits
if distanceHigh >= (1 << (128 - uint(prefixLength))) {
return 0, ErrOverflow
}
// Schema of the carry and shifts:
// [a:b:c:(d]
// [e:f:g):h]
// <---------------> prefixLen
// <-> 128 - prefixLen (cut right)
// <-----> prefixLen - 64 (cut left)
//
// [a:b:c:(d] => [d:0:0:0]
distanceHigh <<= uint(prefixLength) - 64
// [e:f:g):h] => [0:e:f:g]
distanceLow >>= 128 - uint(prefixLength)
// [d:0:0:0] + [0:e:f:g] = (d:e:f:g)
return distanceHigh + distanceLow, nil
}
// AddPrefixes returns the `n`th /`unit` subnet after the `ip` base subnet. It
// is the converse operation of Offset(), used to retrieve a prefix from the
// index within the allocator table
func AddPrefixes(ip net.IP, n, unit uint64) (net.IP, error) {
if unit == 0 && n != 0 {
return net.IP{}, ErrOverflow
} else if n == 0 {
return ip, nil
}
if len(ip) != 16 {
// We don't actually care if they're true v6 or v4-mapped,
// but they need to be 128-bit to handle as 64-bit ints
return net.IP{}, errors.New("AddPrefixes needs 128-bit IPs")
}
// Compute as pairs of uint64 for easier operations
// This could all be 1 function call if go had 128-bit integers
iph, ipl := binary.BigEndian.Uint64(ip[:8]), binary.BigEndian.Uint64(ip[8:])
// Compute `n` /`unit` subnets as uint64 pair
var offh, offl uint64
if unit <= 64 {
offh = n << (64 - unit)
} else {
offh, offl = bits.Mul64(n, 1<<(128-unit))
}
// Now add the 2, check for overflow
ipl, carry := bits.Add64(offl, ipl, 0)
iph, carry = bits.Add64(offh, iph, carry)
if carry != 0 {
return net.IP{}, ErrOverflow
}
// Finally convert back to net.IP
ret := make(net.IP, net.IPv6len)
binary.BigEndian.PutUint64(ret[:8], iph)
binary.BigEndian.PutUint64(ret[8:], ipl)
return ret, nil
}
|
