ipplot/prefix.go

/*
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

package ipplot

import (
	"errors"
	"fmt"
	"math"
)

const (
	ipv4ByteSize = 4
)

func lessThan(o1, m1, o2, m2 byte) bool {
	/*
		We seek an isometry from a binary trie embedded in R²
		to the integral number line, with ones bits branching to
		the right and zeros bits branching to the left. When
		considering only the ones bits of an n-bit binary
		number, the usual decimal encoding suffices, as each ith
		bit, for 0 <= i <= n-1, shifts a point at the origin to
		the right by 2^i. However, the zeros bits have no
		effect, in this sense, as leading zeros do not
		contribute to the integer value, resulting in many
		binary strings occupying the same point. This mapping is
		well-formed and surjective (every integer has a binary
		encoding), but it is not injective.

		    -> R 0 00 000 0000
		               -> 0001
		           -> 001 0010
		               -> 0011
		        -> 01 010 0100
		               -> 0101
		           -> 011 0110
		               -> 0111
		      -> 1 10 100 1000
		               -> 1001
		           -> 101 1010
		               -> 1011
		        -> 11 110 1100
		               -> 1101
		           -> 111 1110
		               -> 1111

		Instead, by allowing each zero bit to provide a negative
		contribution, we ensure that every path (binary string)
		maps to a unique point on the integral line. To see that
		this is an isometry, project the nodes of a binary trie
		embedded in R², with branch width w = 2^(n-j-1) at rank
		j and arbitrary branch height h, onto the integral line.

		Here, we express the above isometry by simply
		subtracting the contributions of the place values of the
		zeros bits, which we obtain by ones complement (XOR).
		Masking ensures we map only the prefix.

		Finally, we note that projecting the usual geometry of a
		binary trie onto the integral line places each ancestor
		at the midpoint of its descendants. This creates a
		disagreement between the partial and total orders, which
		makes it difficult to recover the original partial order
		generated by the trie.

		    	                  -> 0000
		    	            -> 000
		    	                  -> 0001
		    	       -> 00
		    	                  -> 0010
		    	            -> 001
		    	                  -> 0011
		    	   -> 0
		    	                  -> 0100
		    	            -> 010
		    	                  -> 0101
		    	       -> 01
		    	                  -> 0110
		    	            -> 011
		    	                  -> 0111
		    	0/0
		    	                  -> 1000
		    	            -> 100
		    	                  -> 1001
		    	       -> 10
		    	                  -> 1010
		    	            -> 101
		    	                  -> 1011
		    	   -> 1
		    	                  -> 1100
		    	            -> 110
		    	                  -> 1101
		    	       -> 11
		    	                  -> 1110
		    	            -> 111
		    	                  -> 1111

		Instead, we require that the total order < given by the
		proposed isometry have the property that it always agree
		with the partial order ≪ given by the binary trie.  That
		is, given nodes a, b of a binary trie, if a ≪ b, then
		a < b. Note that the converse does not hold, nor would
		it be useful if it did.

		To accomplish this, we effectively apply a horizontal
		shear to the right on the binary trie such that the root
		of each subtree falls to the right of its descendants.

		                      -> 0000
		                      -> 0001
		                -> 000
		                      -> 0010
		                      -> 0011
		                -> 001
		           -> 00
		                      -> 0100
		                      -> 0101
		                -> 010
		                      -> 0110
		                      -> 0111
		                -> 011
		           -> 01
		       -> 0
		                      -> 1000
		                      -> 1001
		                -> 100
		                      -> 1010
		                      -> 1011
		                -> 101
		           -> 10
		                      -> 1100
		                      -> 1101
		                -> 110
		                      -> 1110
		                      -> 1111
		                -> 111
		           -> 11
		       -> 1
		    0/0

		In the unsheared isometry, the nodes we wish to reorder
		are specifically those which precede their descendants--
		that is, whenever a < b and b ≪ a, we would like to
		move a to the right of b so that b < a, thereby agreeing
		with the partial order. Since b ≪ a, it is the case
		that a represents a shorter prefix than b. Furthermore,
		since b is a descendant of a, b's prefix is guaranteed
		to share all of the bits of a. Conversely, if a and b
		share a prefix, then that prefix represents the most
		recent shared ancestor (least upper bound). And if the
		prefix shared by a and b is a's prefix, then it must be
		the case that a's prefix is shorter, and b is a
		descendant of a. Thus, b ≪ a.

		Therefore, we conclude that a must be reordered
		precisely when a < b and b shares a's prefix; hence, our
		assertion `f1 < f2 && o1 != o2&m1`. To reorder, we
		simply place prefixes with longer masks before prefixes
		with shorter ones, as given by `m1 > m2`.
	*/
	f1 := int(o1&m1) - int((o1^byte(255))&m1)
	f2 := int(o2&m2) - int((o2^byte(255))&m2)

	return (f1 < f2 &&
		(o1 != o2&m1 || // assume o2/m2 is not a descendant of o1/m1
			m1 > m2)) // otherwise, sort by length, descending
}

func lessThanOrEq(p1, p2 IPPrefix) bool {
	a1, a2 := p1.Prefix(), p2.Prefix()
	m1, m2 := p1.Mask(), p2.Mask()

	for i := 0; i < len(a1); i++ {
		if lessThan(a1[i], m1[i], a2[i], m2[i]) {
			return true
		}
		// !(p1<=p2) <=> p1>p2 <=> p2<p1
		if lessThan(a2[i], m2[i], a1[i], m1[i]) {
			return false
		}
	}
	return true
}

type IPPrefix interface {
	Mask() []byte
	Length() int
	LessThanOrEq(IPPrefix) bool
	Prefix() []byte
	String() string
	ToGeometry() (uint64, uint64, uint64, uint64)
}

var maskTable = &[9]byte{0, 128, 192, 224, 240, 248, 252, 254, 255}

func lengthToMask(byteSz, l int) (mask []byte) {
	mask = make([]byte, byteSz)

	for i := 0; i < len(mask); i++ {
		rem := l - 8*(i+1)
		if rem < 0 {
			if rem != -8 {
				mask[i] = maskTable[rem+8]
			}
			break
		}
		mask[i] = maskTable[8]
	}
	return
}

type IPv6Prefix struct {
	addr   [16]byte
	length int
}

type IPv4Prefix struct {
	addr   [4]byte
	length int
}

func (p1 IPv4Prefix) Mask() []byte {
	return lengthToMask(len(p1.Prefix()), p1.Length())
}

func (p1 IPv4Prefix) LessThanOrEq(p2 IPPrefix) bool {
	if p2, ok := p2.(IPv4Prefix); ok {
		return lessThanOrEq(p1, p2)
	}
	return false
}

func (p IPv4Prefix) Prefix() []byte {
	return p.addr[:]
}

func (p IPv4Prefix) Length() int {
	return p.length
}

func (p IPv4Prefix) String() string {
	return fmt.Sprintf(
		"%d.%d.%d.%d/%d",
		p.addr[0],
		p.addr[1],
		p.addr[2],
		p.addr[3],
		p.length,
	)
}

/*
"Unzip" bits from least- to most-significant, making the
first group the "x" coordinate, and the second group, the
"y" coordinate. This is sometimes called *Morton encoding*.
See https://en.wikipedia.org/wiki/Z-order_curve for details.

	abcdefgh     bdfh aceg
	10110001 -> (0101,1100)

This transformation exhibits a weak form of continuity,
where sufficiently small changes in the prefix result in
similarly small changes in the point (x, y), and vice versa.
*/
func (p IPv4Prefix) ToGeometry() (x, y, w, h uint64) {
	for i, b := range p.addr {
		x += uint64(((1 << 0) & b) >> 0)
		y += uint64(((1 << 1) & b) >> 1)
		x += uint64(((1 << 2) & b) >> 1)
		y += uint64(((1 << 3) & b) >> 2)
		x += uint64(((1 << 4) & b) >> 2)
		y += uint64(((1 << 5) & b) >> 3)
		x += uint64(((1 << 6) & b) >> 3)
		y += uint64(((1 << 7) & b) >> 4)
		if i < 3 { // Make room for the next four bits
			x <<= 4
			y <<= 4
		}
	}
	l := p.length
	w = uint64(math.Exp2(math.Ceil(float64(32-l) / 2)))
	h = uint64(math.Exp2(math.Floor(float64(32-l) / 2)))
	return
}

/*
Inverse of ToGeometry().

	 bdfh aceg     abcdefgh
	(0101,1100) -> 10110001
*/
func IPv4FromGeometry(x, y, w, h uint64) IPv4Prefix {
	p := [4]byte{}
	for i := 3; i >= 0; i-- {
		p[i] |= byte(((1 << 0) & x) << 0)
		p[i] |= byte(((1 << 0) & y) << 1)
		p[i] |= byte(((1 << 1) & x) << 1)
		p[i] |= byte(((1 << 1) & y) << 2)
		p[i] |= byte(((1 << 2) & x) << 2)
		p[i] |= byte(((1 << 2) & y) << 3)
		p[i] |= byte(((1 << 3) & x) << 3)
		p[i] |= byte(((1 << 3) & y) << 4)
		x >>= 4
		y >>= 4
	}
	l := 32 - 2*math.Log2(float64(w))
	if w != h {
		l += 1
	}
	return IPv4Prefix{addr: p, length: int(l)}
}

func NewIPv4(
	addr []byte,
	length int,
) (IPv4Prefix, error) {
	var newPrefix IPv4Prefix

	if len(addr) != 4 {
		return newPrefix, errors.New("bad ipv4 prefix")
	}
	if length < 0 || length > 32 {
		return newPrefix, errors.New("bad ipv4 prefix length")
	}
	copy(newPrefix.addr[:], addr[0:4])
	newPrefix.length = length

	return newPrefix, nil
}