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