1// Copyright 2021 The go-ethereum Authors
2// This file is part of the go-ethereum library.
3//
4// The go-ethereum library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU Lesser General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// The go-ethereum library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU Lesser General Public License for more details.
13//
14// You should have received a copy of the GNU Lesser General Public License
15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
16
17package snap
18
19import (
20	"math/big"
21
22	"github.com/ethereum/go-ethereum/common"
23	"github.com/holiman/uint256"
24)
25
26// hashRange is a utility to handle ranges of hashes, Split up the
27// hash-space into sections, and 'walk' over the sections
28type hashRange struct {
29	current *uint256.Int
30	step    *uint256.Int
31}
32
33// newHashRange creates a new hashRange, initiated at the start position,
34// and with the step set to fill the desired 'num' chunks
35func newHashRange(start common.Hash, num uint64) *hashRange {
36	left := new(big.Int).Sub(hashSpace, start.Big())
37	step := new(big.Int).Div(
38		new(big.Int).Add(left, new(big.Int).SetUint64(num-1)),
39		new(big.Int).SetUint64(num),
40	)
41	step256 := new(uint256.Int)
42	step256.SetFromBig(step)
43
44	return &hashRange{
45		current: new(uint256.Int).SetBytes32(start[:]),
46		step:    step256,
47	}
48}
49
50// Next pushes the hash range to the next interval.
51func (r *hashRange) Next() bool {
52	next, overflow := new(uint256.Int).AddOverflow(r.current, r.step)
53	if overflow {
54		return false
55	}
56	r.current = next
57	return true
58}
59
60// Start returns the first hash in the current interval.
61func (r *hashRange) Start() common.Hash {
62	return r.current.Bytes32()
63}
64
65// End returns the last hash in the current interval.
66func (r *hashRange) End() common.Hash {
67	// If the end overflows (non divisible range), return a shorter interval
68	next, overflow := new(uint256.Int).AddOverflow(r.current, r.step)
69	if overflow {
70		return common.HexToHash("0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff")
71	}
72	return next.SubUint64(next, 1).Bytes32()
73}
74
75// incHash returns the next hash, in lexicographical order (a.k.a plus one)
76func incHash(h common.Hash) common.Hash {
77	var a uint256.Int
78	a.SetBytes32(h[:])
79	a.AddUint64(&a, 1)
80	return common.Hash(a.Bytes32())
81}
82