Repository: theupdateframework/go-tuf
Pull request #192 (2021-12-10 23:03:43)

[Delegations prereq 2] Add hash bins helpers
Splitting up https://github.com/theupdateframework/go-tuf/pull/175

This PR adds helpers to support hash bin targets delegation. The helpers will be used to generate a list of hash bin manifest names as `leaf_00.json, leaf_01.json, leaf_02.json, ..., leaf_ff.json`, which a targets manifest such as `bins.json` may delegate to using the TUF `path_hash_prefixes` feature ([see spec](https://theupdateframework.github.io/specification/latest/#path_hash_prefixes)).

coveralls: ## Pull Request Test Coverage Report for [Build 1565525441](https://coveralls.io/builds/44928191)

* **48** of **48**   **(100.0%)**  changed or added relevant lines in **1** file are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.5%**) to **70.136%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/44928191/badge)](https://coveralls.io/builds/44928191) |
| :-- | --: |
| Change from base [Build 1565520598](https://coveralls.io/builds/44928160): |  0.5% |
| Covered Lines: | 2116 |
| Relevant Lines: | 3017 |

---
##### 💛  - [Coveralls](https://coveralls.io)

hosseinsia: please provide some description of what this PR does.
ethan-lowman-dd: @hosseinsia Added a brief description. The unit tests are also a good place to look to see example usage of these functions. You can also find the intended usage in go-tuf APIs in `AddTargetsDelegationsForPathHashBins` in `repo.go` here: https://github.com/theupdateframework/go-tuf/pull/175
hosseinsia: makes sense. Thanks!

On Thu, Dec 16, 2021 at 11:31 AM Ethan Lowman ***@***.***>
wrote:

> ***@***.**** commented on this pull request.
> ------------------------------
>
> In internal/targets/hash_bins.go
> <https://github.com/theupdateframework/go-tuf/pull/192#discussion_r770714636>
> :
>
> > +		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 {
>
> This is an uint64, so it can not be negative, and zero is a valid index.
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/theupdateframework/go-tuf/pull/192#discussion_r770714636>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AUYDSRCO6IHD3IBINMTZ4MDURIH7XANCNFSM5J2GU3ZA>
> .
> Triage notifications on the go with GitHub Mobile for iOS
> <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675>
> or Android
> <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.
>
> You are receiving this because you were mentioned.Message ID:
> ***@***.***>
>


Patch:
diff --git a/internal/targets/hash_bins.go b/internal/targets/hash_bins.go
new file mode 100644
index 0000000..95f4405
--- /dev/null
+++ b/internal/targets/hash_bins.go
@@ -0,0 +1,113 @@
+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
+}


Test patch:
diff --git a/internal/targets/hash_bins_test.go b/internal/targets/hash_bins_test.go
new file mode 100644
index 0000000..dce2ab8
--- /dev/null
+++ b/internal/targets/hash_bins_test.go
@@ -0,0 +1,119 @@
+package targets
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func BenchmarkHexEncode1(b *testing.B) {
+	for n := 0; n <= b.N; n++ {
+		for x := uint64(0); x <= 0xf; x += 1 {
+			hexEncode(x, 1)
+		}
+	}
+}
+
+func BenchmarkHexEncode4(b *testing.B) {
+	for n := 0; n <= b.N; n++ {
+		for x := uint64(0); x <= 0xffff; x += 1 {
+			hexEncode(x, 4)
+		}
+	}
+}
+
+func TestHashBin(t *testing.T) {
+	tcs := []struct {
+		hb           *HashBin
+		roleName     string
+		hashPrefixes []string
+	}{
+		{
+			hb: &HashBin{
+				rolePrefix:  "abc_",
+				hexDigitLen: 1,
+				first:       0x0,
+				last:        0x7,
+			},
+			roleName: "abc_0-7",
+			hashPrefixes: []string{
+				"0", "1", "2", "3", "4", "5", "6", "7",
+			},
+		},
+		{
+			hb: &HashBin{
+				rolePrefix:  "abc_",
+				hexDigitLen: 2,
+				first:       0x0,
+				last:        0xf,
+			},
+			roleName: "abc_00-0f",
+			hashPrefixes: []string{
+				"00", "01", "02", "03", "04", "05", "06", "07",
+				"08", "09", "0a", "0b", "0c", "0d", "0e", "0f",
+			},
+		},
+		{
+			hb: &HashBin{
+				rolePrefix:  "cba_",
+				hexDigitLen: 4,
+				first:       0xcd,
+				last:        0xcf,
+			},
+			roleName:     "cba_00cd-00cf",
+			hashPrefixes: []string{"00cd", "00ce", "00cf"},
+		},
+		{
+			hb: &HashBin{
+				rolePrefix:  "cba_",
+				hexDigitLen: 3,
+				first:       0xc1,
+				last:        0xc1,
+			},
+			roleName:     "cba_0c1",
+			hashPrefixes: []string{"0c1"},
+		},
+	}
+
+	for i, tc := range tcs {
+		assert.Equalf(t, tc.roleName, tc.hb.RoleName(), "test case %v: RoleName()", i)
+		assert.Equalf(t, tc.hashPrefixes, tc.hb.HashPrefixes(), "test case %v: HashPrefixes()", i)
+	}
+}
+
+func TestHashBins(t *testing.T) {
+	tcs := []struct {
+		bitLen    int
+		roleNames []string
+	}{
+		{1, []string{"0-7", "8-f"}},
+		{2, []string{"0-3", "4-7", "8-b", "c-f"}},
+		{3, []string{"0-1", "2-3", "4-5", "6-7", "8-9", "a-b", "c-d", "e-f"}},
+		{4, []string{
+			"0", "1", "2", "3", "4", "5", "6", "7",
+			"8", "9", "a", "b", "c", "d", "e", "f",
+		}},
+		{5, []string{
+			"00-07", "08-0f", "10-17", "18-1f", "20-27", "28-2f", "30-37", "38-3f",
+			"40-47", "48-4f", "50-57", "58-5f", "60-67", "68-6f", "70-77", "78-7f",
+			"80-87", "88-8f", "90-97", "98-9f", "a0-a7", "a8-af", "b0-b7", "b8-bf",
+			"c0-c7", "c8-cf", "d0-d7", "d8-df", "e0-e7", "e8-ef", "f0-f7", "f8-ff",
+		}},
+	}
+	for i, tc := range tcs {
+		got := []string{}
+		hbs, err := NewHashBins("", tc.bitLen)
+		assert.NoError(t, err)
+		n := hbs.NumBins()
+		for i := uint64(0); i < n; i += 1 {
+			hb := hbs.GetBin(i)
+			got = append(got, hb.RoleName())
+		}
+		assert.Equalf(t, tc.roleNames, got, "test case %v", i)
+	}
+
+	_, err := NewHashBins("", 0)
+	assert.Error(t, err)
+	_, err = NewHashBins("", 33)
+	assert.Error(t, err)
+}