blob: 660fe34d7b3b331e2291a6e44b09f6bd885bd4fb [file] [log] [blame]
// Copyright 2015 The Vanadium 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 ptrie
// mostSignificantBit stores the mapping from a byte to the position of its most
// significant bit set to 1.
var mostSignificantBit [256]uint32
func init() {
for i := 2; i < 256; i++ {
mostSignificantBit[i] = mostSignificantBit[i>>1] + 1
}
}
// bitlen returns the length of a slice in bits, i.e. 8 * len(slice).
func bitlen(slice []byte) uint32 {
return uint32(len(slice)) << 3
}
// getBit returns i-th lexicographically significant bit of a slice.
// In other words, if we think of a byte slice as a big integer, getBit returns
// the i-th bit of that integer counting from the highest to the lowest.
func getBit(slice []byte, i uint32) byte {
return (slice[i>>3] >> (7 - (i & 7))) & 1
}
// sliceBitLCP returns the length of the longest common prefix between two
// slices. The slices are compared as two bit strings. The first skipbits of
// both slices are virtually removed and ignored.
// NOTE: sliceBitLCP assumes that 0 <= skipbits < 8.
func sliceBitLCP(a, b []byte, skipbits uint32) uint32 {
// Check that the first byte (without the first skipbits) is the same in
// both slices.
if x := (a[0] ^ b[0]) << skipbits; x != 0 {
return 7 - mostSignificantBit[x]
}
minlen := len(a)
if len(b) < minlen {
minlen = len(b)
}
for i := 1; i < minlen; i++ {
// (uint32(i<<3) - skipbits) --- the number of already compared bits.
if x := a[i] ^ b[i]; x != 0 {
return (uint32(i<<3) - skipbits) + (7 - mostSignificantBit[x])
}
}
return uint32(minlen<<3) - skipbits
}
// copyNode returns a copy of the provided pnode struct.
func copyNode(node *pnode) *pnode {
if node == nil {
return nil
}
return &pnode{
value: node.value,
child: node.child,
}
}
// copyNode returns a copy of the provided child struct.
func copyChild(child *pchild) *pchild {
if child == nil {
return nil
}
return &pchild{
node: child.node,
bitstr: child.bitstr,
bitlen: child.bitlen,
}
}
// bitLCP returns the length of the longest common bit-prefix between the Path
// of a child and a slice. The first skipbits of both slices are virtually
// removed and ignored. Returns 0 if the child is nil.
func bitLCP(child *pchild, slice []byte, skipbits uint32) uint32 {
if child == nil {
return 0
}
lcp := sliceBitLCP(child.bitstr, slice, skipbits)
if lcp > child.bitlen {
lcp = child.bitlen
}
return lcp
}
// appendBits appends 'b' to 'a', assuming that 'a' has the provided bit length.
// If the bit length is a multiple of 8, appendBits just appends 'b' to 'a'.
// Otherwise appendBits appends 'b' to 'a' overlapping the first byte of 'b'
// with the last byte of 'a' so that the first bitlen bits of 'a' are unchanged.
//
// If 'a' has not enough capacity to hold the result, appendBits creates a new
// slice to hold the result. Otherwise the result is stored in 'a'.
func appendBits(a []byte, bitlen uint32, b []byte) []byte {
newlen := int(bitlen>>3) + len(b)
if newlen > cap(a) {
tmp := make([]byte, newlen)
copy(tmp, a)
a = tmp
}
a = a[:newlen]
oldByte := a[bitlen>>3]
copy(a[bitlen>>3:], b)
var bitmask byte = (1 << (8 - (bitlen & 7))) - 1
a[bitlen>>3] = (bitmask & a[bitlen>>3]) | (^bitmask & oldByte)
return a
}
// copyBytes returns a copy of the provided slice.
func copyBytes(slice []byte) []byte {
result := make([]byte, len(slice))
copy(result, slice)
return result
}