package backend

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

// RFC 6962 §2.1 Merkle tree hashing. We use the standard CT scheme:
//   leaf hash  = SHA-256(0x00 || data)
//   node hash  = SHA-256(0x01 || left || right)
// so that an inclusion proof from this server can later be audited by
// anything that speaks the certificate-transparency merkle format.

func leafHash(data []byte) []byte {
	h := sha256.New()
	h.Write([]byte{0x00})
	h.Write(data)
	return h.Sum(nil)
}

func nodeHash(left, right []byte) []byte {
	h := sha256.New()
	h.Write([]byte{0x01})
	h.Write(left)
	h.Write(right)
	return h.Sum(nil)
}

// merkleTreeHash computes the Merkle Tree Hash (MTH) of the given list of
// leaf hashes. MTH([]) is SHA-256 of the empty string per RFC 6962, but we
// never call it on an empty slice in practice.
func merkleTreeHash(leaves [][]byte) []byte {
	n := len(leaves)
	switch n {
	case 0:
		h := sha256.Sum256(nil)
		return h[:]
	case 1:
		return append([]byte(nil), leaves[0]...)
	}
	k := largestPow2LessThan(n)
	return nodeHash(merkleTreeHash(leaves[:k]), merkleTreeHash(leaves[k:]))
}

// auditPath returns the RFC 6962 audit path for leaf index m within the
// given leaf-hash slice (tree size n = len(leaves)). The returned slice is
// the ordered list of sibling hashes from the leaf up to (but not including)
// the root. Returns an empty slice for a single-leaf tree.
func auditPath(leaves [][]byte, m int) [][]byte {
	n := len(leaves)
	if n <= 1 {
		return nil
	}
	k := largestPow2LessThan(n)
	if m < k {
		return append(auditPath(leaves[:k], m), merkleTreeHash(leaves[k:]))
	}
	return append(auditPath(leaves[k:], m-k), merkleTreeHash(leaves[:k]))
}

// largestPow2LessThan returns the largest power of two strictly smaller than
// n (n must be >= 2).
func largestPow2LessThan(n int) int {
	k := 1
	for k < n {
		k <<= 1
	}
	return k >> 1
}

func sha256Hex(b []byte) string {
	return "sha256:" + hex.EncodeToString(b)
}