package filter

import (
	"encoding/binary"
	"errors"
	"fmt"
	"math/bits"
	"slices"
)

// Filter parameters defined by BIP158 for the basic filter type.
const (
	// FilterTypeBasic is the BIP158 basic block filter type.
	FilterTypeBasic = 0

	// M is the inverse target false positive rate of a basic filter.
	M uint64 = 784931

	// P is the Golomb-Rice remainder bit length of a basic filter.
	P uint = 19

	// maxFilterElements bounds the element count accepted by Match and Decode.
	// BIP158 requires N < 2^32; a block cannot realistically contain anywhere
	// near this many scripts, so a much tighter bound is used to reject absurd
	// serialized counts before allocating or decoding.
	maxFilterElements = 1 << 20

	// maxFilterValue is the exclusive upper bound on any mapped value in a
	// filter with maxFilterElements elements.
	maxFilterValue = uint64(maxFilterElements) * M

	// maxGolombQuotient bounds the unary part of a decoded delta.
	maxGolombQuotient = maxFilterValue>>P + 1
)

// Errors returned for malformed or implausible filters.
var (
	// ErrInvalidFilter indicates that a filter is truncated, non-canonical, or
	// otherwise not a valid BIP158 basic filter serialization.
	ErrInvalidFilter = errors.New("filter: invalid compact block filter")

	// ErrTooManyElements indicates that the CompactSize element count exceeds
	// the implementation limit.
	ErrTooManyElements = errors.New("filter: element count exceeds limit")
)

// Build constructs the BIP158 serialization of the basic compact block filter
// for items, keyed by the first 16 bytes of blockHash in internal
// (little-endian) byte order.
//
// Build encodes exactly the items it is given: the serialized element count is
// len(items), and duplicate items produce duplicate mapped values, which appear
// as zero deltas. The BIP158 element set is a set of distinct, non-empty
// elements, so callers supplying raw block data should remove duplicates and
// empty elements first. BuildFromScripts is a convenience that does so.
//
// An empty item set produces the single byte 0x00.
func Build(items [][]byte, blockHash [32]byte) []byte {
	n := len(items)
	out := appendCompactSize(make([]byte, 0, 1+((n*3)/2)), uint64(n))
	if n == 0 {
		return out
	}

	var key [16]byte
	copy(key[:], blockHash[:16])

	// F = N * M fits in 64 bits because N is bounded by an int on supported
	// platforms and a real block's element count is far below 2^32.
	f := uint64(n) * M
	values := make([]uint64, n)
	for i, item := range items {
		h := siphash24(key, item)
		hi, _ := bits.Mul64(h, f) // (h * F) >> 64
		values[i] = hi
	}
	slices.Sort(values)

	w := bitWriter{buf: out}
	var last uint64
	for _, v := range values {
		w.writeGolomb(v-last, P)
		last = v
	}
	w.flush()
	return w.buf
}

// Match reports whether any element of query maps to a value in filter.
//
// The filter must be a complete BIP158 serialization (CompactSize element count
// followed by the Golomb-Rice bitstream). It is decoded only as far as needed:
// decoding stops when the next filter value exceeds every remaining query value,
// and ErrInvalidFilter is returned if the bitstream is truncated or malformed
// before that point. The block hash key is blockHash[0:16].
//
// For a filter over the empty set, Match returns true only for an empty query.
func Match(filter []byte, blockHash [32]byte, query [][]byte) (bool, error) {
	n, payload, err := decodeHeader(filter)
	if err != nil {
		return false, err
	}
	if n == 0 {
		return len(query) == 0, nil
	}
	if len(query) == 0 {
		// Validate the serialization even though there is nothing to match.
		if _, _, err := Decode(filter); err != nil {
			return false, err
		}
		return false, nil
	}

	var key [16]byte
	copy(key[:], blockHash[:16])
	f := uint64(n) * M

	targets := make([]uint64, len(query))
	for i, item := range query {
		h := siphash24(key, item)
		hi, _ := bits.Mul64(h, f)
		targets[i] = hi
	}
	slices.Sort(targets)

	r := bitReader{data: payload}
	var last uint64
	target := 0
	for i := uint64(0); i < n; i++ {
		delta, err := r.readGolomb(P)
		if err != nil {
			return false, err
		}
		if delta >= f-last {
			return false, fmt.Errorf("%w: Golomb value out of range", ErrInvalidFilter)
		}
		last += delta

		// Values are strictly increasing (duplicates become zero deltas, so
		// they compare equal). Drop query values that are now too small.
		for target < len(targets) && targets[target] < last {
			target++
		}
		if target == len(targets) {
			return false, nil
		}
		if targets[target] == last {
			return true, nil
		}
	}

	if err := r.checkPadding(); err != nil {
		return false, err
	}
	return false, nil
}

// MatchScript reports whether any of scripts appears in filter. It is an alias
// for Match, provided for symmetry with the caller's element kind.
func MatchScript(filter []byte, blockHash [32]byte, scripts [][]byte) (bool, error) {
	return Match(filter, blockHash, scripts)
}

// MatchAny reports whether any of items appears in filter. It is an alias for
// Match.
func MatchAny(filter []byte, blockHash [32]byte, items [][]byte) (bool, error) {
	return Match(filter, blockHash, items)
}

// Decode parses and fully decodes a filter, returning its sorted mapped values
// and the serialized element count N. It is intended for tests and debugging;
// Match avoids materializing the values.
//
// Decode rejects truncated bitstreams, non-zero or overlong padding, and
// element counts above the implementation limit.
func Decode(filter []byte) (values []uint64, n uint64, err error) {
	n, payload, err := decodeHeader(filter)
	if err != nil {
		return nil, 0, err
	}
	if n == 0 {
		return nil, 0, nil
	}

	f := uint64(n) * M
	values = make([]uint64, 0, int(n))
	r := bitReader{data: payload}
	var last uint64
	for i := uint64(0); i < n; i++ {
		delta, err := r.readGolomb(P)
		if err != nil {
			return nil, 0, err
		}
		if delta >= f-last {
			return nil, 0, fmt.Errorf("%w: Golomb value out of range", ErrInvalidFilter)
		}
		last += delta
		values = append(values, last)
	}
	if err := r.checkPadding(); err != nil {
		return nil, 0, err
	}
	return values, n, nil
}

// decodeHeader reads the CompactSize element count and returns the filter's
// Golomb bitstream payload. Empty filters must be exactly one 0x00 byte.
func decodeHeader(filter []byte) (n uint64, payload []byte, err error) {
	n, off, err := readCompactSize(filter)
	if err != nil {
		return 0, nil, err
	}
	if n > maxFilterElements {
		return 0, nil, fmt.Errorf("%w: %d elements", ErrTooManyElements, n)
	}
	if n == 0 {
		if off != len(filter) {
			return 0, nil, fmt.Errorf("%w: trailing bytes after empty filter", ErrInvalidFilter)
		}
		return 0, nil, nil
	}
	return n, filter[off:], nil
}

func appendCompactSize(dst []byte, n uint64) []byte {
	switch {
	case n < 0xfd:
		return append(dst, byte(n))
	case n <= 0xffff:
		dst = append(dst, 0xfd)
		var buf [2]byte
		binary.LittleEndian.PutUint16(buf[:], uint16(n))
		return append(dst, buf[:]...)
	case n <= 0xffffffff:
		dst = append(dst, 0xfe)
		var buf [4]byte
		binary.LittleEndian.PutUint32(buf[:], uint32(n))
		return append(dst, buf[:]...)
	default:
		dst = append(dst, 0xff)
		var buf [8]byte
		binary.LittleEndian.PutUint64(buf[:], n)
		return append(dst, buf[:]...)
	}
}

// readCompactSize decodes a canonical Bitcoin CompactSize integer. It returns
// the value and the number of bytes consumed.
func readCompactSize(data []byte) (n uint64, size int, err error) {
	if len(data) == 0 {
		return 0, 0, fmt.Errorf("%w: missing CompactSize", ErrInvalidFilter)
	}

	switch data[0] {
	case 0xfd:
		if len(data) < 3 {
			return 0, 0, fmt.Errorf("%w: truncated CompactSize", ErrInvalidFilter)
		}
		n = uint64(binary.LittleEndian.Uint16(data[1:3]))
		if n < 0xfd {
			return 0, 0, fmt.Errorf("%w: non-canonical CompactSize", ErrInvalidFilter)
		}
		return n, 3, nil
	case 0xfe:
		if len(data) < 5 {
			return 0, 0, fmt.Errorf("%w: truncated CompactSize", ErrInvalidFilter)
		}
		n = uint64(binary.LittleEndian.Uint32(data[1:5]))
		if n <= 0xffff {
			return 0, 0, fmt.Errorf("%w: non-canonical CompactSize", ErrInvalidFilter)
		}
		return n, 5, nil
	case 0xff:
		if len(data) < 9 {
			return 0, 0, fmt.Errorf("%w: truncated CompactSize", ErrInvalidFilter)
		}
		n = binary.LittleEndian.Uint64(data[1:9])
		if n <= 0xffffffff {
			return 0, 0, fmt.Errorf("%w: non-canonical CompactSize", ErrInvalidFilter)
		}
		return n, 9, nil
	default:
		return uint64(data[0]), 1, nil
	}
}

// bitWriter appends bits most-significant first, as required by the BIP158
// write_bits_big_endian primitive.
type bitWriter struct {
	buf []byte
	cur byte
	n   uint8 // number of bits currently held in cur
}

func (w *bitWriter) writeBit(bit uint) {
	w.cur = w.cur<<1 | byte(bit&1)
	w.n++
	if w.n == 8 {
		w.buf = append(w.buf, w.cur)
		w.cur = 0
		w.n = 0
	}
}

func (w *bitWriter) writeBits(v uint64, n uint) {
	for i := n; i > 0; i-- {
		w.writeBit(uint(v >> (i - 1)))
	}
}

func (w *bitWriter) writeGolomb(v uint64, p uint) {
	q := v >> p
	for ; q > 0; q-- {
		w.writeBit(1)
	}
	w.writeBit(0)
	w.writeBits(v&(1<<p-1), p)
}

// flush pads the final partial byte with zero bits.
func (w *bitWriter) flush() {
	if w.n > 0 {
		w.buf = append(w.buf, w.cur<<(8-w.n))
		w.cur = 0
		w.n = 0
	}
}

// bitReader reads bits most-significant first.
type bitReader struct {
	data []byte
	bit  uint64 // absolute bit position
}

func (r *bitReader) readBit() (uint, error) {
	total := uint64(len(r.data)) * 8
	if r.bit >= total {
		return 0, fmt.Errorf("%w: truncated bitstream", ErrInvalidFilter)
	}
	b := (r.data[r.bit>>3] >> (7 - (r.bit & 7))) & 1
	r.bit++
	return uint(b), nil
}

func (r *bitReader) readBits(n uint) (uint64, error) {
	var v uint64
	for i := uint(0); i < n; i++ {
		b, err := r.readBit()
		if err != nil {
			return 0, err
		}
		v = v<<1 | uint64(b)
	}
	return v, nil
}

func (r *bitReader) readGolomb(p uint) (uint64, error) {
	var q uint64
	for {
		b, err := r.readBit()
		if err != nil {
			return 0, err
		}
		if b == 0 {
			break
		}
		q++
		if q > maxGolombQuotient {
			return 0, fmt.Errorf("%w: Golomb quotient too large", ErrInvalidFilter)
		}
	}

	rem, err := r.readBits(p)
	if err != nil {
		return 0, err
	}
	if q > (^uint64(0)-rem)>>p {
		return 0, fmt.Errorf("%w: Golomb value overflow", ErrInvalidFilter)
	}
	return q<<p | rem, nil
}

// checkPadding verifies that at most seven zero bits remain. A valid filter is
// padded only to the next byte boundary, so extra bytes are rejected too.
func (r *bitReader) checkPadding() error {
	total := uint64(len(r.data)) * 8
	if total-r.bit >= 8 {
		return fmt.Errorf("%w: trailing bytes after bitstream", ErrInvalidFilter)
	}
	for r.bit < total {
		b, err := r.readBit()
		if err != nil {
			return err
		}
		if b != 0 {
			return fmt.Errorf("%w: non-zero padding bits", ErrInvalidFilter)
		}
	}
	return nil
}