src

bits.go (4353B)

---

 // Copyright 2021 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 package trie
 
 import (
 	"math/bits"
 )
 
 // This file contains bit twiddling functions for Patricia tries.
 // Consult this paper for details.
 //   C. Okasaki and A. Gill, “Fast mergeable integer maps,” in ACM SIGPLAN
 //   Workshop on ML, September 1998, pp. 77–86.
 
 // key is a key in a Map.
 type key uint64
 
 // bitpos is the position of a bit. A position is represented by having a 1
 // bit in that position.
 // Examples:
 //   - 0b0010 is the position of the `1` bit in 2.
 //     It is the 3rd most specific bit position in big endian encoding
 //     (0b0 and 0b1 are more specific).
 //   - 0b0100 is the position of the bit that 1 and 5 disagree on.
 //   - 0b0 is a special value indicating that all bit agree.
 type bitpos uint64
 
 // prefixes represent a set of keys that all agree with the
 // prefix up to a bitpos m.
 //
 // The value for a prefix is determined by the mask(k, m) function.
 // (See mask for details on the values.)
 // A `p` prefix for position `m` matches a key `k` iff mask(k, m) == p.
 // A prefix always mask(p, m) == p.
 //
 // A key is its own prefix for the bit position 64,
 // e.g. seeing a `prefix(key)` is not a problem.
 //
 // Prefixes should never be turned into keys.
 type prefix uint64
 
 // branchingBit returns the position of the first bit in `x` and `y`
 // that are not equal.
 func branchingBit(x, y prefix) bitpos {
 	p := x ^ y
 	if p == 0 {
 		return 0
 	}
 	return bitpos(1) << uint(bits.Len64(uint64(p))-1) // uint conversion needed for go1.12
 }
 
 // zeroBit returns true if k has a 0 bit at position `b`.
 func zeroBit(k prefix, b bitpos) bool {
 	return (uint64(k) & uint64(b)) == 0
 }
 
 // matchPrefix returns true if a prefix k matches a prefix p up to position `b`.
 func matchPrefix(k prefix, p prefix, b bitpos) bool {
 	return mask(k, b) == p
 }
 
 // mask returns a prefix of `k` with all bits after and including `b` zeroed out.
 //
 // In big endian encoding, this value is the [64-(m-1)] most significant bits of k
 // followed by a `0` bit at bitpos m, followed m-1 `1` bits.
 // Examples:
 //
 //	prefix(0b1011) for a bitpos 0b0100 represents the keys:
 //	  0b1000, 0b1001, 0b1010, 0b1011, 0b1100, 0b1101, 0b1110, 0b1111
 //
 // This mask function has the property that if matchPrefix(k, p, b), then
 // k <= p if and only if zeroBit(k, m). This induces binary search tree tries.
 // See Okasaki & Gill for more details about this choice of mask function.
 //
 // mask is idempotent for a given `b`, i.e. mask(mask(p, b), b) == mask(p,b).
 func mask(k prefix, b bitpos) prefix {
 	return prefix((uint64(k) | (uint64(b) - 1)) & (^uint64(b)))
 }
 
 // ord returns true if m comes before n in the bit ordering.
 func ord(m, n bitpos) bool {
 	return m > n // big endian encoding
 }
 
 // prefixesOverlap returns true if there is some key a prefix `p` for bitpos `m`
 // can hold that can also be held by a prefix `q` for some bitpos `n`.
 //
 // This is equivalent to:
 //
 //	m ==n && p == q,
 //	higher(m, n) && matchPrefix(q, p, m), or
 //	higher(n, m) && matchPrefix(p, q, n)
 func prefixesOverlap(p prefix, m bitpos, q prefix, n bitpos) bool {
 	fbb := n
 	if ord(m, n) {
 		fbb = m
 	}
 	return mask(p, fbb) == mask(q, fbb)
 	// Lemma:
 	//   mask(p, fbb) == mask(q, fbb)
 	// iff
 	//   m > n && matchPrefix(q, p, m) or  (note: big endian encoding)
 	//   m < n && matchPrefix(p, q, n) or  (note: big endian encoding)
 	//   m ==n && p == q
 	// Quick-n-dirty proof:
 	// p == mask(p0, m) for some p0 by precondition.
 	// q == mask(q0, n) for some q0 by precondition.
 	// So mask(p, m) == p and mask(q, n) == q as mask(*, n') is idempotent.
 	//
 	// [=> proof]
 	// Suppose mask(p, fbb) == mask(q, fbb).
 	// if m ==n, p == mask(p, m) == mask(p, fbb) == mask(q, fbb) == mask(q, n) == q
 	// if m > n, fbb = firstBranchBit(m, n) = m (big endian).
 	//   p == mask(p, m) == mask(p, fbb) == mask(q, fbb) == mask(q, m)
 	//   so mask(q, m) == p or matchPrefix(q, p, m)
 	// if m < n, is symmetric to the above.
 	//
 	// [<= proof]
 	// case m ==n && p == q. Then mask(p, fbb) == mask(q, fbb)
 	//
 	// case m > n && matchPrefix(q, p, m).
 	// fbb == firstBranchBit(m, n) == m (by m>n).
 	// mask(q, fbb) == mask(q, m) == p == mask(p, m) == mask(p, fbb)
 	//
 	// case m < n && matchPrefix(p, q, n) is symmetric.
 }