1// Package address contains the types used by yggdrasil to represent IPv6 addresses or prefixes, as well as functions for working with these types.
2// Of particular importance are the functions used to derive addresses or subnets from a NodeID, or to get the NodeID and bitmask of the bits visible from an address, which is needed for DHT searches.
3package address
4
5import (
6	"fmt"
7
8	"github.com/yggdrasil-network/yggdrasil-go/src/crypto"
9)
10
11// Address represents an IPv6 address in the yggdrasil address range.
12type Address [16]byte
13
14// Subnet represents an IPv6 /64 subnet in the yggdrasil subnet range.
15type Subnet [8]byte
16
17// GetPrefix returns the address prefix used by yggdrasil.
18// The current implementation requires this to be a muliple of 8 bits + 7 bits.
19// The 8th bit of the last byte is used to signal nodes (0) or /64 prefixes (1).
20// Nodes that configure this differently will be unable to communicate with eachother using IP packets, though routing and the DHT machinery *should* still work.
21func GetPrefix() [1]byte {
22	return [...]byte{0x02}
23}
24
25// IsValid returns true if an address falls within the range used by nodes in the network.
26func (a *Address) IsValid() bool {
27	prefix := GetPrefix()
28	for idx := range prefix {
29		if (*a)[idx] != prefix[idx] {
30			return false
31		}
32	}
33	return true
34}
35
36// IsValid returns true if a prefix falls within the range usable by the network.
37func (s *Subnet) IsValid() bool {
38	prefix := GetPrefix()
39	l := len(prefix)
40	for idx := range prefix[:l-1] {
41		if (*s)[idx] != prefix[idx] {
42			return false
43		}
44	}
45	return (*s)[l-1] == prefix[l-1]|0x01
46}
47
48// AddrForNodeID takes a *NodeID as an argument and returns an *Address.
49// This address begins with the contents of GetPrefix(), with the last bit set to 0 to indicate an address.
50// The following 8 bits are set to the number of leading 1 bits in the NodeID.
51// The NodeID, excluding the leading 1 bits and the first leading 0 bit, is truncated to the appropriate length and makes up the remainder of the address.
52func AddrForNodeID(nid *crypto.NodeID) *Address {
53	// 128 bit address
54	// Begins with prefix
55	// Next bit is a 0
56	// Next 7 bits, interpreted as a uint, are # of leading 1s in the NodeID
57	// Leading 1s and first leading 0 of the NodeID are truncated off
58	// The rest is appended to the IPv6 address (truncated to 128 bits total)
59	var addr Address
60	var temp []byte
61	done := false
62	ones := byte(0)
63	bits := byte(0)
64	nBits := 0
65	for idx := 0; idx < 8*len(nid); idx++ {
66		bit := (nid[idx/8] & (0x80 >> byte(idx%8))) >> byte(7-(idx%8))
67		if !done && bit != 0 {
68			ones++
69			continue
70		}
71		if !done && bit == 0 {
72			done = true
73			continue // FIXME? this assumes that ones <= 127, probably only worth changing by using a variable length uint64, but that would require changes to the addressing scheme, and I'm not sure ones > 127 is realistic
74		}
75		bits = (bits << 1) | bit
76		nBits++
77		if nBits == 8 {
78			nBits = 0
79			temp = append(temp, bits)
80		}
81	}
82	prefix := GetPrefix()
83	copy(addr[:], prefix[:])
84	addr[len(prefix)] = ones
85	copy(addr[len(prefix)+1:], temp)
86	return &addr
87}
88
89// SubnetForNodeID takes a *NodeID as an argument and returns an *Address.
90// This subnet begins with the address prefix, with the last bit set to 1 to indicate a prefix.
91// The following 8 bits are set to the number of leading 1 bits in the NodeID.
92// The NodeID, excluding the leading 1 bits and the first leading 0 bit, is truncated to the appropriate length and makes up the remainder of the subnet.
93func SubnetForNodeID(nid *crypto.NodeID) *Subnet {
94	// Exactly as the address version, with two exceptions:
95	//  1) The first bit after the fixed prefix is a 1 instead of a 0
96	//  2) It's truncated to a subnet prefix length instead of 128 bits
97	addr := *AddrForNodeID(nid)
98	var snet Subnet
99	copy(snet[:], addr[:])
100	prefix := GetPrefix()
101	snet[len(prefix)-1] |= 0x01
102	return &snet
103}
104
105// GetNodeIDandMask returns two *NodeID.
106// The first is a NodeID with all the bits known from the Address set to their correct values.
107// The second is a bitmask with 1 bit set for each bit that was known from the Address.
108// This is used to look up NodeIDs in the DHT and tell if they match an Address.
109func (a *Address) GetNodeIDandMask() (*crypto.NodeID, *crypto.NodeID) {
110	// Mask is a bitmask to mark the bits visible from the address
111	// This means truncated leading 1s, first leading 0, and visible part of addr
112	var nid crypto.NodeID
113	var mask crypto.NodeID
114	prefix := GetPrefix()
115	ones := int(a[len(prefix)])
116	for idx := 0; idx < ones; idx++ {
117		nid[idx/8] |= 0x80 >> byte(idx%8)
118	}
119	nidOffset := ones + 1
120	addrOffset := 8*len(prefix) + 8
121	for idx := addrOffset; idx < 8*len(a); idx++ {
122		bits := a[idx/8] & (0x80 >> byte(idx%8))
123		bits <<= byte(idx % 8)
124		nidIdx := nidOffset + (idx - addrOffset)
125		bits >>= byte(nidIdx % 8)
126		nid[nidIdx/8] |= bits
127	}
128	maxMask := 8*(len(a)-len(prefix)-1) + ones + 1
129	for idx := 0; idx < maxMask; idx++ {
130		mask[idx/8] |= 0x80 >> byte(idx%8)
131	}
132	return &nid, &mask
133}
134
135// GetNodeIDLengthString returns a string representation of the known bits of the NodeID, along with the number of known bits, for use with yggdrasil.Dialer's Dial and DialContext functions.
136func (a *Address) GetNodeIDLengthString() string {
137	nid, mask := a.GetNodeIDandMask()
138	l := mask.PrefixLength()
139	return fmt.Sprintf("%s/%d", nid.String(), l)
140}
141
142// GetNodeIDandMask returns two *NodeID.
143// The first is a NodeID with all the bits known from the Subnet set to their correct values.
144// The second is a bitmask with 1 bit set for each bit that was known from the Subnet.
145// This is used to look up NodeIDs in the DHT and tell if they match a Subnet.
146func (s *Subnet) GetNodeIDandMask() (*crypto.NodeID, *crypto.NodeID) {
147	// As with the address version, but visible parts of the subnet prefix instead
148	var nid crypto.NodeID
149	var mask crypto.NodeID
150	prefix := GetPrefix()
151	ones := int(s[len(prefix)])
152	for idx := 0; idx < ones; idx++ {
153		nid[idx/8] |= 0x80 >> byte(idx%8)
154	}
155	nidOffset := ones + 1
156	addrOffset := 8*len(prefix) + 8
157	for idx := addrOffset; idx < 8*len(s); idx++ {
158		bits := s[idx/8] & (0x80 >> byte(idx%8))
159		bits <<= byte(idx % 8)
160		nidIdx := nidOffset + (idx - addrOffset)
161		bits >>= byte(nidIdx % 8)
162		nid[nidIdx/8] |= bits
163	}
164	maxMask := 8*(len(s)-len(prefix)-1) + ones + 1
165	for idx := 0; idx < maxMask; idx++ {
166		mask[idx/8] |= 0x80 >> byte(idx%8)
167	}
168	return &nid, &mask
169}
170
171// GetNodeIDLengthString returns a string representation of the known bits of the NodeID, along with the number of known bits, for use with yggdrasil.Dialer's Dial and DialContext functions.
172func (s *Subnet) GetNodeIDLengthString() string {
173	nid, mask := s.GetNodeIDandMask()
174	l := mask.PrefixLength()
175	return fmt.Sprintf("%s/%d", nid.String(), l)
176}
177