ip_math.go

package main

import (
	"bytes"
	"net"
)

func NetLast(n *net.IPNet) *net.IP {
	ip := n.IP
	last := make(net.IP, len(ip))
	// Copy in the mask bits
	copy(last, n.Mask)
	for i := 0; i < len(last); i = i + 1 {
		// Invert the mask bit and | in the first/ip, mask will always be 0
		// anywhere IP is not
		last[i] = ^last[i] | ip[i]
	}

	return &last
}

func IPNext(ip *net.IP) *net.IP {
	// net.IP is annoying, net.IpV4 creates a 16-byte IP :-(, this function
	// doesn't handle it as the way IPs are generated by everything here does
	// 4-byte v4. If/when that changes this will need some updating
	n := len(*ip)
	out := make(net.IP, n)

	// Starting with a carry will be our +1
	carry := byte(1)
	// For each byte of the IP, working last to first
	for i := n - 1; i >= 0; i = i - 1 {
		// Each byte of the IP plus any carry from the previous
		out[i] = (*ip)[i] + carry
		if out[i] < (*ip)[i] {
			// Wrapped so we carry
			carry = 1
		} else {
			carry = 0
		}
	}

	return &out
}

func IPNetFromFirstLast(first, last *net.IP, ret *[]*net.IPNet) {
	if bytes.Compare(*first, *last) == 0 {
		// It's a /32, short circuit
		//log.Printf("IPNetFromFirstLast: /32 short circuit")
		*ret = append(*ret, &net.IPNet{
			IP:   *first,
			Mask: net.CIDRMask(32, 32),
		})
		return
	} else if bytes.Compare(*first, net.IP{0, 0, 0, 0}) == 0 && bytes.Compare(*last, net.IP{255, 255, 255, 255}) == 0 {
		//log.Printf("IPNetFromFirstLast: /0 short circuit")
		*ret = append(*ret, &net.IPNet{
			IP:   *first,
			Mask: net.CIDRMask(0, 32),
		})
		return
	} else {
		numBits := 32
		if first.To4() == nil {
			numBits = 128
		}

		//log.Printf("IPNetFromFirstLast: first=%s, last=%s", first.String(), last.String())

		bit := 0
		// TODO: explore binary search
		for bit <= numBits {
			mask := net.CIDRMask(bit, numBits)
			candidate := &net.IPNet{
				IP:   first.Mask(mask),
				Mask: mask,
			}
			//log.Printf("IPNetFromFirstLast:   candidate.IP=%s, candidate.Mask=%s, bit=%d", candidate.IP, candidate.Mask, bit)
			// Make sure this candidate starts on the right IP
			if bytes.Compare(candidate.IP, *first) == 0 {
				candidate_last := NetLast(candidate)
				//log.Printf("IPNetFromFirstLast:   candidate.Last=%s", candidate_last.String())
				// If it's last is less than ours we can use it
				if bytes.Compare(*candidate_last, *last) <= 0 {
					//log.Printf("IPNetFromFirstLast:   match, net=%s", candidate.String())
					// We found one small enough (or exact sized) so use it
					*ret = append(*ret, candidate)

					// Shift to the IP after what we just found
					first = IPNext(candidate_last)
					if bytes.Compare(*first, *last) > 0 {
						//log.Printf("IPNetFromFirstLast:   beyond last, we're done")
						return
					}
					// Otherwise recurse down the remaining range to find further nets
					IPNetFromFirstLast(first, last, ret)
					// And then we're done
					return
				}
			}
			// try one smaller
			bit = bit + 1
		}
		// should never get here
	}
}