// Package mnemonic is BIP39: entropy to a word seed, a word seed back to entropy, and
// the 64-byte seed a wallet derives from it.
//
// It is the first thing a swap wallet needs and the only thing it cannot recover from:
// every key, address and HTLC in the wallet comes from this sentence, so a wrong word, a
// lost word or a different derivation is a different wallet. That is why the word list is
// vendored with its checksum pinned in a test, and why every function here is checked
// against the official vectors rather than against itself.
package mnemonic

import (
	"crypto/hmac"
	"crypto/rand"
	"crypto/sha256"
	"crypto/sha512"
	_ "embed"
	"encoding/binary"
	"encoding/hex"
	"fmt"
	"strings"
)

// The word list is the BIP39 English list: 2048 words, each unique, each 3 to 8
// lowercase letters, in ascending order. A test checks the file against a pinned
// sha256 as well as against those properties, because a single changed word silently
// changes every seed this package will ever produce.
//
//go:embed english.txt
var englishText string

// words is the parsed list, built once at start.
var words = parseWords(englishText)

// index maps a word to its position, built once at start.
var index = buildIndex(words)

// WordCount reports how many words the list holds, for a checksum of the whole list.
func WordCount() int { return len(words) }

// Word returns one word by position, or an empty string when it is out of range.
func Word(i int) string {
	if i < 0 || i >= len(words) {
		return ""
	}

	return words[i]
}

// parseWords splits the embedded list.
func parseWords(text string) []string {
	fields := strings.Fields(text)
	out := make([]string, 0, len(fields))

	for _, field := range fields {
		out = append(out, strings.ToLower(field))
	}

	return out
}

// buildIndex maps each word to its position.
func buildIndex(list []string) map[string]int {
	lookup := make(map[string]int, len(list))

	for i, word := range list {
		lookup[word] = i
	}

	return lookup
}

// Lengths are the word counts BIP39 defines, in words. The wallet offers the first and the
// last, because they are the two a person has a reason to choose: twelve words is what a
// phone can type, twenty-four is what a long-lived backup uses.
var Lengths = []int{12, 15, 18, 21, 24}

// entropyBits is the entropy size for a word count.
func entropyBits(count int) (int, error) {
	switch count {
	case 12:
		return 128, nil
	case 15:
		return 160, nil
	case 18:
		return 192, nil
	case 21:
		return 224, nil
	case 24:
		return 256, nil
	}

	return 0, fmt.Errorf("a word seed is 12, 15, 18, 21 or 24 words, not %d", count)
}

// New makes a fresh seed phrase of the given word count from the platform's entropy.
func New(count int) (string, error) { return NewFrom(rand.Reader, count) }

// NewFrom makes a fresh seed phrase from a supplied entropy source.
//
// It exists so a test can fix the entropy and compare against the official vectors; a
// caller with real money on the line passes New.
func NewFrom(random interface{ Read([]byte) (int, error) }, count int) (string, error) {
	bits, err := entropyBits(count)

	if err != nil {
		return "", err
	}

	entropy := make([]byte, bits/8)

	if err := readFull(random, entropy); err != nil {
		return "", fmt.Errorf("entropy: %w", err)
	}

	return FromEntropy(entropy)
}

// readFull fills the buffer or fails.
func readFull(random interface{ Read([]byte) (int, error) }, buffer []byte) error {
	filled := 0

	for filled < len(buffer) {
		n, err := random.Read(buffer[filled:])

		if err != nil {
			return err
		}

		if n == 0 {
			return fmt.Errorf("the entropy source returned no bytes")
		}

		filled += n
	}

	return nil
}

// FromEntropy turns 16, 20, 24, 28 or 32 bytes into a word seed.
//
// The last word carries the checksum, which is the first ENT/32 bits of the sha256 of the
// entropy: 4 bits for 128 bits of entropy, 8 bits for 256.
func FromEntropy(entropy []byte) (string, error) {
	switch len(entropy) {
	case 16, 20, 24, 28, 32:
	default:
		return "", fmt.Errorf(
			"entropy is 16, 20, 24, 28 or 32 bytes, not %d", len(entropy),
		)
	}

	checksumBits := len(entropy) * 8 / 32
	sum := sha256.Sum256(entropy)

	// The entropy and the checksum as one bit string, read in 11-bit groups. The whole
	// thing is at most 264 bits, so a fixed 33-byte buffer covers it.
	var stream [33]byte

	copy(stream[:], entropy)

	// Shift the checksum byte in after the entropy: with ENT a multiple of 8 and the
	// checksum at most 8 bits, the checksum is the top checksumBits of this byte.
	stream[len(entropy)] = sum[0]

	totalBits := len(entropy)*8 + checksumBits
	count := totalBits / 11

	out := make([]string, 0, count)

	for i := 0; i < count; i++ {
		position, err := bitsAt(stream[:], i*11, 11)

		if err != nil {
			return "", err
		}

		out = append(out, words[position])
	}

	return strings.Join(out, " "), nil
}

// bitsAt reads n bits starting at bit offset from a big-endian byte stream.
func bitsAt(stream []byte, offset, n int) (int, error) {
	value := 0

	for i := 0; i < n; i++ {
		bit := offset + i
		byteIndex := bit / 8

		if byteIndex >= len(stream) {
			return 0, fmt.Errorf("bit range %d..%d is past the buffer", offset, offset+n)
		}

		shift := 7 - uint(bit%8)
		value = value<<1 | int((stream[byteIndex]>>shift)&1)
	}

	return value, nil
}

// Normalize turns a typed phrase into the canonical form this package works in.
//
// The word list is English and lowercase, so the normalisation a person needs is
// whitespace and case, not Unicode folding: a phrase pasted from a backup often has a
// trailing space, a newline, a double space or a capital.
func Normalize(phrase string) string {
	return strings.Join(strings.Fields(strings.ToLower(phrase)), " ")
}

// Split returns the canonical words of a phrase.
func Split(phrase string) []string { return strings.Fields(Normalize(phrase)) }

// Validate reports whether a phrase is a well-formed BIP39 seed.
//
// It checks the word count, that every word is in the list, and the checksum. A phrase
// that fails any of those is not a seed with a typo; it is a phrase that will derive a
// different wallet, and the checksum is what makes that detectable.
func Validate(phrase string) error {
	_, err := Entropy(phrase)

	return err
}

// Entropy recovers the entropy a phrase encodes.
func Entropy(phrase string) ([]byte, error) {
	fields := Split(phrase)

	bits, err := entropyBits(len(fields))

	if err != nil {
		return nil, err
	}

	// Reassemble the 11-bit groups into a bit stream.
	stream := make([]byte, (bits+len(fields)*11)/8+1)
	position := 0

	for _, word := range fields {
		found, ok := index[word]

		if !ok {
			return nil, fmt.Errorf("%q is not a word in the BIP39 English list", word)
		}

		for i := 10; i >= 0; i-- {
			if (found>>uint(i))&1 == 1 {
				stream[position/8] |= 1 << uint(7-position%8)
			}

			position++
		}
	}

	entropy := stream[:bits/8]
	checksumBits := len(fields)*11 - bits

	// The checksum is the next checksumBits, and the rest of the last byte is padding
	// the phrase does not own.
	got, err := bitsAt(stream, bits, checksumBits)

	if err != nil {
		return nil, err
	}

	sum := sha256.Sum256(entropy)
	want := int(sum[0]) >> uint(8-checksumBits)

	if got != want {
		return nil, fmt.Errorf("the word seed's checksum does not match; check the words")
	}

	// Any padding bit set means the phrase is not the canonical encoding of this entropy.
	if remaining := len(fields)*11 - bits - checksumBits; remaining > 0 {
		padding, err := bitsAt(stream, bits+checksumBits, remaining)

		if err != nil {
			return nil, err
		}

		if padding != 0 {
			return nil, fmt.Errorf("the word seed has non-zero padding; check the words")
		}
	}

	out := make([]byte, len(entropy))
	copy(out, entropy)

	return out, nil
}

// Seed derives the 64-byte BIP39 seed for a phrase and a passphrase.
//
// The passphrase is the part of BIP39 that creates a second wallet from one phrase: the
// same words with a different passphrase derive different keys and no checksum catches the
// difference, which is why the wallet treats it as part of the backup and asks for it.
//
// The derivation is PBKDF2-HMAC-SHA512, 2048 rounds, salt "mnemonic" plus the passphrase,
// and the salt is the reason a non-ASCII passphrase is refused: BIP39 requires NFKD
// normalisation of both inputs, this build has no Unicode normalisation table, and the
// word list is ASCII so the phrase needs none. A passphrase that needs folding would
// silently derive a different seed than another wallet does, so it is refused with an
// explanation instead.
func Seed(phrase, passphrase string) ([64]byte, error) {
	var seed [64]byte

	normalized := Normalize(phrase)

	if err := Validate(normalized); err != nil {
		return seed, err
	}

	for _, r := range passphrase {
		if r > 0x7f {
			return seed, fmt.Errorf(
				"the passphrase must be ASCII in this build: BIP39 normalises it with " +
					"NFKD, which this client does not implement, so a non-ASCII " +
					"passphrase would derive a different seed than another wallet does",
			)
		}
	}

	password := []byte(normalized)
	salt := []byte("mnemonic" + passphrase)

	// PBKDF2 with dkLen equal to the hash length is exactly one block, so this is the
	// whole of PBKDF2 for this shape.
	block := pbkdf2Block(password, salt, 1, 2048)

	copy(seed[:], block)

	return seed, nil
}

// pbkdf2Block is one output block of PBKDF2-HMAC-SHA512.
//
// dkLen for a BIP39 seed is 64 bytes, the size of SHA-512, so PBKDF2 produces exactly one
// block and the general loop over blocks is not needed. The parameter is kept so the
// function reads as the algorithm rather than as a coincidence.
func pbkdf2Block(password, salt []byte, block uint32, rounds int) []byte {
	mac := hmac.New(sha512.New, password)

	// U1 = HMAC(password, salt || INT_32_BE(block))
	var counter [4]byte

	binary.BigEndian.PutUint32(counter[:], block)

	mac.Write(salt)
	mac.Write(counter[:])

	previous := mac.Sum(nil)
	out := make([]byte, len(previous))
	copy(out, previous)

	for round := 1; round < rounds; round++ {
		mac.Reset()
		mac.Write(previous)

		previous = mac.Sum(previous[:0])

		for i := range out {
			out[i] ^= previous[i]
		}
	}

	return out
}

// Hex renders entropy for a log or a test, never for a UI that shows it to a person.
func Hex(entropy []byte) string { return hex.EncodeToString(entropy) }