forked from anacrolix/torrent
-
Notifications
You must be signed in to change notification settings - Fork 0
/
merkle.go
60 lines (52 loc) · 1.43 KB
/
merkle.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package merkle
import (
"crypto/sha256"
"fmt"
"math/bits"
g "github.com/anacrolix/generics"
)
// The leaf block size for BitTorrent v2 Merkle trees.
const BlockSize = 1 << 14 // 16KiB
func Root(hashes [][sha256.Size]byte) [sha256.Size]byte {
switch len(hashes) {
case 0:
return sha256.Sum256(nil)
case 1:
return hashes[0]
}
numHashes := uint(len(hashes))
if numHashes != RoundUpToPowerOfTwo(uint(len(hashes))) {
panic(fmt.Sprintf("expected power of two number of hashes, got %d", numHashes))
}
var next [][sha256.Size]byte
for i := 0; i < len(hashes); i += 2 {
left := hashes[i]
right := hashes[i+1]
h := sha256.Sum256(append(left[:], right[:]...))
next = append(next, h)
}
return Root(next)
}
func RootWithPadHash(hashes [][sha256.Size]byte, padHash [sha256.Size]byte) [sha256.Size]byte {
for uint(len(hashes)) < RoundUpToPowerOfTwo(uint(len(hashes))) {
hashes = append(hashes, padHash)
}
return Root(hashes)
}
func CompactLayerToSliceHashes(compactLayer string) (hashes [][sha256.Size]byte, err error) {
g.MakeSliceWithLength(&hashes, len(compactLayer)/sha256.Size)
for i := range hashes {
n := copy(hashes[i][:], compactLayer[i*sha256.Size:])
if n != sha256.Size {
err = fmt.Errorf("compact layer has incomplete hash at index %d", i)
return
}
}
return
}
func RoundUpToPowerOfTwo(n uint) (ret uint) {
return 1 << bits.Len(n-1)
}
func Log2RoundingUp(n uint) (ret uint) {
return uint(bits.Len(n - 1))
}