Debian Codegraph @

v0/pkg/targets/hash_bins.go

raw
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 }