hash_bins.go

Documentation: github.com/theupdateframework/go-tuf/pkg/targets

     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  }
   114
View as plain text