Cloudpods/backend/vendor/github.com/DataDog/go-tuf/pkg/targets/hash_bins.go

package targets

import (
	"fmt"
	"strconv"
	"strings"
)

const MinDelegationHashPrefixBitLen = 1
const MaxDelegationHashPrefixBitLen = 32

// hexEncode formats x as a hex string. The hex string is left padded with
// zeros to padWidth, if necessary.
func hexEncode(x uint64, padWidth int) string {
	// Benchmarked to be more than 10x faster than padding with Sprintf.
	s := strconv.FormatUint(x, 16)
	if len(s) >= padWidth {
		return s
	}
	return strings.Repeat("0", padWidth-len(s)) + s
}

const bitsPerHexDigit = 4

// numHexDigits returns the number of hex digits required to encode the given
// number of bits.
func numHexDigits(numBits int) int {
	// ceil(numBits / bitsPerHexDigit)
	return ((numBits - 1) / bitsPerHexDigit) + 1
}

// HashBins represents an ordered list of hash bin target roles, which together
// partition the space of target path hashes equal-sized buckets based on path
// has prefix.
type HashBins struct {
	rolePrefix  string
	bitLen      int
	hexDigitLen int

	numBins           uint64
	numPrefixesPerBin uint64
}

// NewHashBins creates a HashBins partitioning with 2^bitLen buckets.
func NewHashBins(rolePrefix string, bitLen int) (*HashBins, error) {
	if bitLen < MinDelegationHashPrefixBitLen || bitLen > MaxDelegationHashPrefixBitLen {
		return nil, fmt.Errorf("bitLen is out of bounds, should be between %v and %v inclusive", MinDelegationHashPrefixBitLen, MaxDelegationHashPrefixBitLen)
	}

	hexDigitLen := numHexDigits(bitLen)
	numBins := uint64(1) << bitLen

	numPrefixesTotal := uint64(1) << (bitsPerHexDigit * hexDigitLen)
	numPrefixesPerBin := numPrefixesTotal / numBins

	return &HashBins{
		rolePrefix:        rolePrefix,
		bitLen:            bitLen,
		hexDigitLen:       hexDigitLen,
		numBins:           numBins,
		numPrefixesPerBin: numPrefixesPerBin,
	}, nil
}

// NumBins returns the number of hash bin partitions.
func (hb *HashBins) NumBins() uint64 {
	return hb.numBins
}

// GetBin returns the HashBin at index i, or nil if i is out of bounds.
func (hb *HashBins) GetBin(i uint64) *HashBin {
	if i >= hb.numBins {
		return nil
	}

	return &HashBin{
		rolePrefix:  hb.rolePrefix,
		hexDigitLen: hb.hexDigitLen,
		first:       i * hb.numPrefixesPerBin,
		last:        ((i + 1) * hb.numPrefixesPerBin) - 1,
	}
}

// HashBin represents a hex prefix range. First should be less than Last.
type HashBin struct {
	rolePrefix  string
	hexDigitLen int
	first       uint64
	last        uint64
}

// RoleName returns the name of the role that signs for the HashBin.
func (b *HashBin) RoleName() string {
	if b.first == b.last {
		return b.rolePrefix + hexEncode(b.first, b.hexDigitLen)
	}

	return b.rolePrefix + hexEncode(b.first, b.hexDigitLen) + "-" + hexEncode(b.last, b.hexDigitLen)
}

// HashPrefixes returns a slice of all hash prefixes in the bin.
func (b *HashBin) HashPrefixes() []string {
	n := int(b.last - b.first + 1)
	ret := make([]string, int(n))

	x := b.first
	for i := 0; i < n; i++ {
		ret[i] = hexEncode(x, b.hexDigitLen)
		x++
	}

	return ret
}