| 1 |
package targets |
| 2 |
|
| 3 |
import ( |
| 4 |
"fmt" |
| 5 |
"strconv" |
| 6 |
"strings" |
| 7 |
) |
| 8 |
|
| 9 |
const MinDelegationHashPrefixBitLen = 1 |
| 10 |
const MaxDelegationHashPrefixBitLen = 32 |
| 11 |
|
| 12 |
// hexEncode formats x as a hex string. The hex string is left padded with |
| 13 |
// zeros to padWidth, if necessary. |
| 14 |
func hexEncode(x uint64, padWidth int) string { |
| 15 |
// Benchmarked to be more than 10x faster than padding with Sprintf. |
| 16 |
s := strconv.FormatUint(x, 16) |
| 17 |
if len(s) >= padWidth { |
| 18 |
return s |
| 19 |
} |
| 20 |
return strings.Repeat("0", padWidth-len(s)) + s |
| 21 |
} |
| 22 |
|
| 23 |
const bitsPerHexDigit = 4 |
| 24 |
|
| 25 |
// numHexDigits returns the number of hex digits required to encode the given |
| 26 |
// number of bits. |
| 27 |
func numHexDigits(numBits int) int { |
| 28 |
// ceil(numBits / bitsPerHexDigit) |
| 29 |
return ((numBits - 1) / bitsPerHexDigit) + 1 |
| 30 |
} |
| 31 |
|
| 32 |
// HashBins represents an ordered list of hash bin target roles, which together |
| 33 |
// partition the space of target path hashes equal-sized buckets based on path |
| 34 |
// has prefix. |
| 35 |
type HashBins struct { |
| 36 |
rolePrefix string |
| 37 |
bitLen int |
| 38 |
hexDigitLen int |
| 39 |
|
| 40 |
numBins uint64 |
| 41 |
numPrefixesPerBin uint64 |
| 42 |
} |
| 43 |
|
| 44 |
// NewHashBins creates a HashBins partitioning with 2^bitLen buckets. |
| 45 |
func NewHashBins(rolePrefix string, bitLen int) (*HashBins, error) { |
| 46 |
if bitLen < MinDelegationHashPrefixBitLen || bitLen > MaxDelegationHashPrefixBitLen { |
| 47 |
return nil, fmt.Errorf("bitLen is out of bounds, should be between %v and %v inclusive", MinDelegationHashPrefixBitLen, MaxDelegationHashPrefixBitLen) |
| 48 |
} |
| 49 |
|
| 50 |
hexDigitLen := numHexDigits(bitLen) |
| 51 |
numBins := uint64(1) << bitLen |
| 52 |
|
| 53 |
numPrefixesTotal := uint64(1) << (bitsPerHexDigit * hexDigitLen) |
| 54 |
numPrefixesPerBin := numPrefixesTotal / numBins |
| 55 |
|
| 56 |
return &HashBins{ |
| 57 |
rolePrefix: rolePrefix, |
| 58 |
bitLen: bitLen, |
| 59 |
hexDigitLen: hexDigitLen, |
| 60 |
numBins: numBins, |
| 61 |
numPrefixesPerBin: numPrefixesPerBin, |
| 62 |
}, nil |
| 63 |
} |
| 64 |
|
| 65 |
// NumBins returns the number of hash bin partitions. |
| 66 |
func (hb *HashBins) NumBins() uint64 { |
| 67 |
return hb.numBins |
| 68 |
} |
| 69 |
|
| 70 |
// GetBin returns the HashBin at index i, or nil if i is out of bounds. |
| 71 |
func (hb *HashBins) GetBin(i uint64) *HashBin { |
| 72 |
if i >= hb.numBins { |
| 73 |
return nil |
| 74 |
} |
| 75 |
|
| 76 |
return &HashBin{ |
| 77 |
rolePrefix: hb.rolePrefix, |
| 78 |
hexDigitLen: hb.hexDigitLen, |
| 79 |
first: i * hb.numPrefixesPerBin, |
| 80 |
last: ((i + 1) * hb.numPrefixesPerBin) - 1, |
| 81 |
} |
| 82 |
} |
| 83 |
|
| 84 |
// HashBin represents a hex prefix range. First should be less than Last. |
| 85 |
type HashBin struct { |
| 86 |
rolePrefix string |
| 87 |
hexDigitLen int |
| 88 |
first uint64 |
| 89 |
last uint64 |
| 90 |
} |
| 91 |
|
| 92 |
// RoleName returns the name of the role that signs for the HashBin. |
| 93 |
func (b *HashBin) RoleName() string { |
| 94 |
if b.first == b.last { |
| 95 |
return b.rolePrefix + hexEncode(b.first, b.hexDigitLen) |
| 96 |
} |
| 97 |
|
| 98 |
return b.rolePrefix + hexEncode(b.first, b.hexDigitLen) + "-" + hexEncode(b.last, b.hexDigitLen) |
| 99 |
} |
| 100 |
|
| 101 |
// HashPrefixes returns a slice of all hash prefixes in the bin. |
| 102 |
func (b *HashBin) HashPrefixes() []string { |
| 103 |
n := int(b.last - b.first + 1) |
| 104 |
ret := make([]string, int(n)) |
| 105 |
|
| 106 |
x := b.first |
| 107 |
for i := 0; i < n; i++ { |
| 108 |
ret[i] = hexEncode(x, b.hexDigitLen) |
| 109 |
x++ |
| 110 |
} |
| 111 |
|
| 112 |
return ret |
| 113 |
} |