<commit_before>package glacier

import (
	"crypto/sha256"
	"encoding/hex"
	"hash"
)

// MultiTreeHasher is used to calculate tree hashes for multi-part uploads
// Call Add sequentially on hashes you have calculated them for
// parts individually, and CreateHash to get the resulting root-level
// hash to use in a CompleteMultipart request.
type MultiTreeHasher struct {
	nodes [][sha256.Size]byte
}

// Add appends the hex-encoded hash to the treehash as a new node
// Add must be called sequentially on parts.
func (t *MultiTreeHasher) Add(hash string) {
	var b [sha256.Size]byte
	hex.Decode(b[:], []byte(hash))
	t.nodes = append(t.nodes, b)
}

// CreateHash returns the root-level hex-encoded hash to send in the
// CompleteMultipart request.
func (t *MultiTreeHasher) CreateHash() string {
	if len(t.nodes) == 0 {
		return ""
	}
	rootHash := treeHash(t.nodes)
	return hex.EncodeToString(rootHash[:])
}

// treeHash calculates the root-level treeHash given sequential
// leaf nodes.
func treeHash(nodes [][sha256.Size]byte) [sha256.Size]byte {
	curLevel := make([][sha256.Size]byte, len(nodes))
	copy(curLevel, nodes)
	for len(curLevel) > 1 {
		nextLevel := make([][sha256.Size]byte, 0)
		for i := 0; i < len(curLevel); i++ {
			if i%2 == 1 { // Concat with previous node and promote
				var sum [sha256.Size * 2]byte
				copy(sum[:sha256.Size], curLevel[i-1][:])
				copy(sum[sha256.Size:], curLevel[i][:])
				concat := sha256.Sum256(sum[:])
				nextLevel = append(nextLevel, concat)
				continue
			}
			if i == len(curLevel)-1 { // Promote last node in an odd-length level
				nextLevel = append(nextLevel, curLevel[i])
			}
		}
		curLevel = nextLevel
	}
	return curLevel[0]
}

// TreeHash is used to calculate the tree hash and regular sha256 hash of the
// data written to it. These values are needed when uploading an archive or
// verifying an aligned download. First each 1 MiB chunk of data is hashed.
// Second each consecutive child node's hashes are concatenated then hashed (if
// there is a single node left it is promoted to the next level). The second
// step is repeated until there is only a single node, this is the tree hash.
// See docs.aws.amazon.com/amazonglacier/latest/dev/checksum-calculations.html
type TreeHash struct {
	nodes       [][sha256.Size]byte
	remaining   []byte
	runningHash hash.Hash         // linear
	treeHash    [sha256.Size]byte // computed
	linearHash  []byte            //computed
}

// NewTreeHash returns an new, initialized tree hasher.
func NewTreeHash() *TreeHash {
	result := &TreeHash{}
	result.Reset()
	return result
}
<commit_msg>Reduce allocations when calculation the root of the tree hash.<commit_after>package glacier

import (
	"crypto/sha256"
	"encoding/hex"
	"hash"
)

// MultiTreeHasher is used to calculate tree hashes for multi-part uploads
// Call Add sequentially on hashes you have calculated them for
// parts individually, and CreateHash to get the resulting root-level
// hash to use in a CompleteMultipart request.
type MultiTreeHasher struct {
	nodes [][sha256.Size]byte
}

// Add appends the hex-encoded hash to the treehash as a new node
// Add must be called sequentially on parts.
func (t *MultiTreeHasher) Add(hash string) {
	var b [sha256.Size]byte
	hex.Decode(b[:], []byte(hash))
	t.nodes = append(t.nodes, b)
}

// CreateHash returns the root-level hex-encoded hash to send in the
// CompleteMultipart request.
func (t *MultiTreeHasher) CreateHash() string {
	if len(t.nodes) == 0 {
		return ""
	}
	rootHash := treeHash(t.nodes)
	return hex.EncodeToString(rootHash[:])
}

// treeHash calculates the root-level treeHash given sequential
// leaf nodes.
func treeHash(nodes [][sha256.Size]byte) [sha256.Size]byte {
	var combine [sha256.Size * 2]byte
	for len(nodes) > 1 {
		for i := 0; i < len(nodes)/2; i++ {
			copy(combine[:sha256.Size], nodes[i*2][:])
			copy(combine[sha256.Size:], nodes[i*2+1][:])
			nodes[i] = sha256.Sum256(combine[:])
		}
		if len(nodes)%2 == 0 {
			nodes = nodes[:len(nodes)/2]
		} else {
			nodes[len(nodes)/2] = nodes[len(nodes)-1]
			nodes = nodes[:len(nodes)/2+1]
		}
	}
	return nodes[0]
}

// TreeHash is used to calculate the tree hash and regular sha256 hash of the
// data written to it. These values are needed when uploading an archive or
// verifying an aligned download. First each 1 MiB chunk of data is hashed.
// Second each consecutive child node's hashes are concatenated then hashed (if
// there is a single node left it is promoted to the next level). The second
// step is repeated until there is only a single node, this is the tree hash.
// See docs.aws.amazon.com/amazonglacier/latest/dev/checksum-calculations.html
type TreeHash struct {
	nodes       [][sha256.Size]byte
	remaining   []byte
	runningHash hash.Hash         // linear
	treeHash    [sha256.Size]byte // computed
	linearHash  []byte            //computed
}

// NewTreeHash returns an new, initialized tree hasher.
func NewTreeHash() *TreeHash {
	result := &TreeHash{}
	result.Reset()
	return result
}

{'fraction_non_alphanumeric': 0.11549239391513211, 'fraction_numerical': 0.02241793434747798, 'mean_word_length': 3.6570363466915192, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1026677', 'n_tokens_mistral': 1726, 'n_tokens_neox': 1582, 'n_words': 559}