stringzilla 5.1.1

/// A simple semantic version structure.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct SemVer {
    pub major: i32,
    pub minor: i32,
    pub patch: i32,
}

#[repr(C)]
#[derive(Debug, PartialEq)]
pub enum Status {
    /// For algorithms that return a status, this status indicates that the operation was successful.
    /// Corresponds to `sz_success_k = 0` in C.
    Success = 0,
    /// For algorithms that require memory allocation, this status indicates that the allocation failed.
    /// Corresponds to `sz_bad_alloc_k = -10` in C.
    BadAlloc = -10,
    /// For algorithms that require UTF8 input, this status indicates that the input is invalid.
    /// Corresponds to `sz_invalid_utf8_k = -12` in C.
    InvalidUtf8 = -12,
    /// For algorithms that take collections of unique elements, this status indicates presence of duplicates.
    /// Corresponds to `sz_contains_duplicates_k = -13` in C.
    ContainsDuplicates = -13,
    /// For algorithms dealing with large inputs, this error reports the need to upcast the logic to larger types.
    /// Corresponds to `sz_overflow_risk_k = -14` in C.
    OverflowRisk = -14,
    /// For algorithms with multi-stage pipelines indicates input/output size mismatch.
    /// Corresponds to `sz_unexpected_dimensions_k = -15` in C.
    UnexpectedDimensions = -15,
    /// GPU support is missing in the library.
    /// Corresponds to `sz_missing_gpu_k = -16` in C.
    MissingGpu = -16,
    /// Backend-device mismatch (e.g., GPU kernel with CPU/default executor).
    /// Corresponds to `sz_device_code_mismatch_k = -17` in C.
    DeviceCodeMismatch = -17,
    /// Device memory mismatch (e.g., pageable host memory where Unified/Device memory is required).
    /// Corresponds to `sz_device_memory_mismatch_k = -18` in C.
    DeviceMemoryMismatch = -18,
    /// An authenticated decryption saw a tag that does not match the ciphertext it accompanies.
    /// Corresponds to `sz_authentication_failed_k = -19` in C.
    AuthenticationFailed = -19,
    /// A sink-hole status for unknown errors.
    /// Corresponds to `sz_status_unknown_k = -1` in C.
    StatusUnknown = -1,
}

/// Unicode normalization forms for UTF-8 normalization operations.
///
/// Corresponds to `sz_normal_form_t` in the C API.
#[repr(i32)]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Utf8NormalForm {
    /// Canonical Decomposition. Decomposes precomposed characters into base + combining marks.
    Nfd = 0,
    /// Canonical Decomposition followed by Canonical Composition. The most common Unicode form.
    Nfc = 1,
    /// Compatibility Decomposition. Decomposes ligatures and compatibility characters.
    Nfkd = 2,
    /// Compatibility Decomposition followed by Canonical Composition.
    Nfkc = 3,
}

#[repr(C)]
#[derive(Debug, Clone, Copy)]
pub struct Byteset {
    bits: [u64; 4],
}

/// Represents a byte span with offset and length.
///
/// Used for matches of UTF-8 characters, substrings, or any byte-level operations.
/// Stores the byte offset from the start of the text and the length in bytes.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::IndexSpan;
///
/// let text = "Hello\nWorld";
/// let span = IndexSpan::new(5, 1);
/// assert_eq!(span.offset, 5);
/// assert_eq!(span.length, 1);
/// let matched = span.extract(text.as_bytes());
/// assert_eq!(matched, b"\n");
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct IndexSpan {
    /// Byte offset from the start of the text
    pub offset: usize,
    /// Length in bytes of the matched span
    pub length: usize,
}

impl IndexSpan {
    /// Creates a new IndexSpan with the given offset and length.
    #[inline]
    pub const fn new(offset: usize, length: usize) -> Self {
        Self { offset, length }
    }

    /// Returns the range of bytes covered by this span.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::stringzilla::IndexSpan;
    ///
    /// let span = IndexSpan::new(5, 3);
    /// assert_eq!(span.range(), 5..8);
    /// ```
    #[inline]
    pub const fn range(&self) -> core::ops::Range<usize> {
        self.offset..self.offset + self.length
    }

    /// Extracts the matched bytes from the source text.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::stringzilla::IndexSpan;
    ///
    /// let text = b"Hello World";
    /// let span = IndexSpan::new(6, 5);
    /// assert_eq!(span.extract(text), b"World");
    /// ```
    #[inline]
    pub fn extract<'a>(&self, text: &'a [u8]) -> &'a [u8] {
        &text[self.range()]
    }

    /// Returns the end offset (offset + length).
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::stringzilla::IndexSpan;
    ///
    /// let span = IndexSpan::new(5, 3);
    /// assert_eq!(span.end(), 8);
    /// ```
    #[inline]
    pub const fn end(&self) -> usize {
        self.offset + self.length
    }
}

/// Internal metadata for uncased UTF-8 search operations.
///
/// This structure caches pre-computed information about the needle for reuse
/// across multiple searches. Zero-initialization (default) triggers automatic
/// analysis on first use.
///
/// Matches C's `sz_utf8_uncased_needle_metadata_t`.
#[repr(C)]
#[derive(Debug, Clone, Copy)]
pub(crate) struct Utf8UncasedNeedleMetadata {
    // sz_size_t offset_in_unfolded
    offset_in_unfolded: usize,
    // sz_size_t length_in_unfolded
    length_in_unfolded: usize,
    // sz_u8_t folded_slice[16]
    folded_slice: [u8; 16],
    // sz_u8_t folded_slice_length
    folded_slice_length: u8,
    // sz_u8_t probe_second
    probe_second: u8,
    // sz_u8_t probe_third
    probe_third: u8,
    // sz_u8_t kernel_id
    kernel_id: u8,
}

impl Utf8UncasedNeedleMetadata {
    /// The state that requests analysis on first use, usable in a `const` unlike the `Default` it backs.
    pub(crate) const UNANALYZED: Self = Self {
        offset_in_unfolded: 0,
        length_in_unfolded: 0,
        folded_slice: [0; 16],
        folded_slice_length: 0,
        probe_second: 0,
        probe_third: 0,
        kernel_id: 0, // sz_utf8_uncased_rune_unknown_k = 0, triggers analysis
    };
}

impl Default for Utf8UncasedNeedleMetadata {
    fn default() -> Self {
        Self::UNANALYZED
    }
}

/// Pre-compiled uncased search pattern for UTF-8 strings.
///
/// Caches metadata for efficient repeated searches with the same needle.
/// Useful when searching multiple haystacks for the same pattern.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::{utf8_uncased_search, Utf8UncasedNeedle};
///
/// let needle = Utf8UncasedNeedle::new(b"hello");
/// let haystack1 = b"Hello World";
/// let haystack2 = b"HELLO there";
///
/// // Metadata is computed once on first search, reused for subsequent searches
/// let result1 = utf8_uncased_search(haystack1, &needle);
/// let result2 = utf8_uncased_search(haystack2, &needle);
///
/// assert!(result1.is_some());
/// assert!(result2.is_some());
/// ```
pub struct Utf8UncasedNeedle<'a> {
    needle: &'a [u8],
    metadata: UnsafeCell<Utf8UncasedNeedleMetadata>,
}

impl<'a> Utf8UncasedNeedle<'a> {
    /// Creates a new pre-compiled uncased needle.
    ///
    /// The metadata will be computed lazily on first use.
    #[inline]
    pub const fn new(needle: &'a [u8]) -> Self {
        Self {
            needle,
            metadata: UnsafeCell::new(Utf8UncasedNeedleMetadata::UNANALYZED),
        }
    }

    /// Returns the needle bytes.
    #[inline]
    pub const fn as_bytes(&self) -> &[u8] {
        self.needle
    }

    /// Returns the length of the needle in bytes.
    #[inline]
    pub const fn len(&self) -> usize {
        self.needle.len()
    }

    /// Returns true if the needle is empty.
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.needle.is_empty()
    }

    /// Internal: returns a mutable pointer to the metadata for FFI calls.
    #[inline]
    pub(crate) fn metadata_ptr(&self) -> *mut Utf8UncasedNeedleMetadata {
        self.metadata.get()
    }
}

// Safety: The metadata is only mutated through FFI during search operations,
// which internally synchronize access. The needle reference is immutable.
unsafe impl<'a> Send for Utf8UncasedNeedle<'a> {}
unsafe impl<'a> Sync for Utf8UncasedNeedle<'a> {}

/// Incremental hasher state for StringZilla's 64-bit hash.
///
/// Use `Hasher::new(seed)` to construct, then call `update(&mut self, data)`
/// zero or more times, and finally call `digest(&self)` to read the current
/// hash value without consuming the state.
#[repr(C)]
#[derive(Debug, Clone, Copy)]
#[repr(align(64))] // For optimal performance we align to 64 bytes.
pub struct Hasher {
    aes: [u64; 8],
    sum: [u64; 8],
    ins: [u64; 8], // Ignored in comparisons
    key: [u64; 2],
    ins_length: usize, // Ignored in comparisons
}

/// Bytes in a SHA256 digest, fixed by FIPS 180-4.
pub const SHA256_DIGEST_LENGTH: usize = 32;

/// Bytes in a SHA256 message block, fixed by FIPS 180-4.
pub const SHA256_BLOCK_LENGTH: usize = 64;

/// One SHA256 digest, as produced by [`Sha256::digest`] and [`sha256_multistate_digest`].
pub type Sha256Digest = [u8; SHA256_DIGEST_LENGTH];

/// Incremental SHA256 hasher state for cryptographic hashing.
///
/// # Examples
///
/// One-shot hashing:
///
/// ```
/// use stringzilla::stringzilla::Sha256;
/// let digest = Sha256::hash(b"Hello, world!");
/// assert_eq!(digest.len(), 32); // 256 bits = 32 bytes
/// ```
///
/// Incremental hashing:
///
/// ```
/// use stringzilla::stringzilla::Sha256;
/// let mut hasher = Sha256::new();
/// hasher.update(b"Hello, ");
/// hasher.update(b"world!");
/// let digest = hasher.digest();
/// assert_eq!(digest, Sha256::hash(b"Hello, world!"));
/// ```
/*  Mirrors the C `sz_sha256_state_t` by size and alignment only. Every operation on it is an FFI call, so
 *  restating the C fields here would buy nothing and would let a field change in `hash.h` desynchronize
 *  silently. Deliberately not over-aligned: forcing 64-byte alignment would change the array stride
 *  relative to C and silently misplace every element of a `&mut [Sha256]` handed to the batched kernels. */
#[repr(C, align(8))]
#[derive(Debug, Clone, Copy)]
pub struct Sha256([u8; 128]);

/*  Guards the layout the batched kernels depend on: they index a contiguous array with the C stride. */
const _: () = assert!(core::mem::size_of::<Sha256>() == 128);
const _: () = assert!(core::mem::align_of::<Sha256>() == 8);

/// Bytes in an AES-256 secret key.
pub const AES256_KEY_LENGTH: usize = 32;

/// Bytes in the nonce both AES-256 modes accept, the width NIST SP 800-38D recommends.
pub const AES256_NONCE_LENGTH: usize = 12;

/// Bytes in a Galois/counter mode, or GCM, authentication tag.
pub const AES256_TAG_LENGTH: usize = 16;

/// Round keys in an AES-256 schedule: 15 of them, four 32-bit words each.
const AES256_ROUND_KEYS: usize = 60;

/// Bytes of Galois hash, or GHASH, subkey powers, holding `H^1` through `H^8` ascending.
const AES256_GALOIS_POWERS: usize = 8 * 16;

/// Why an authenticated decryption refused to hand back plaintext.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AuthenticationError {
    /// The tag did not match the ciphertext and associated data, so the output holds zeros
    /// rather than the plaintext an attacker chose.
    TagMismatch,
    /// The C core reported a status this binding does not model, so the output is untrusted.
    UnexpectedStatus(i32),
}

/// Expanded AES-256 round-key schedule for counter mode, the construction named AES-256-CTR.
///
/// Counter mode is unauthenticated and seekable: the keystream at a byte offset depends on nothing
/// but the key, the nonce and that offset, so a caller may decrypt the middle of a file without
/// touching its start. Reusing a nonce under one key exposes the exclusive-or of two plaintexts.
///
/// Mirrors `sz_aes256_key_t`, and carries none of the Galois hash powers counter mode never reads.
#[repr(C)]
pub struct Aes256CtrKey {
    round_keys: [u32; AES256_ROUND_KEYS],
}

/// Expanded AES-256 schedule plus the Galois hash subkey powers, the construction named AES-256-GCM.
///
/// Authentication costs the ability to seek, so this mode transforms whole messages or bounded
/// chunks in order. Reusing a nonce under one key exposes the hash subkey, from which every message
/// under that key can be forged.
///
/// Mirrors `sz_aes256_gcm_key_t`.
#[repr(C)]
pub struct Aes256GcmKey {
    block: Aes256CtrKey,
    powers: [u8; AES256_GALOIS_POWERS],
}

/// The payload both directions of a chunked transformation carry.
///
/// Mirrors `sz_aes256_gcm_state_t`. It holds no direction: the Galois hash absorbs ciphertext both
/// ways, the output buffer when sealing and the input when opening, and the C core encodes that in
/// the type of the wrapper rather than in a field. The key is embedded rather than borrowed, so a
/// state cannot outlive it, and wipes with the state.
#[repr(C)]
struct Aes256GcmState {
    key: Aes256GcmKey,
    accumulator: [u8; 16],
    counter: [u8; 16],
    tag_mask: [u8; 16],
    partial: [u8; 16],
    keystream: [u8; 16],
    associated_length: u64,
    text_length: u64,
    buffered: u8,
    keystream_used: u8,
}

/// Seals a message delivered in chunks under Galois/counter mode, or GCM, accumulating its tag as it goes.
///
/// A chunk boundary is invisible to the result, so any chunking produces the ciphertext and tag a
/// single [`Aes256GcmKey::encrypt_into`] would.
///
/// Mirrors `sz_aes256_gcm_encryptor_t`, whose address every call below passes.
#[repr(C)]
pub struct Aes256GcmEncryptor {
    state: Aes256GcmState,
}

/// Opens a message delivered in chunks under Galois/counter mode, or GCM, accumulating its tag as it goes.
///
/// Every emitted byte leaves this type unauthenticated, which is why the methods that emit them say
/// so in their names. Only [`Aes256GcmDecryptor::verify`] tells the caller whether they were genuine.
///
/// Mirrors `sz_aes256_gcm_decryptor_t`, whose address every call below passes.
#[repr(C)]
pub struct Aes256GcmDecryptor {
    state: Aes256GcmState,
}

pub type SortedIdx = usize;

/// A trait for types that support indexed lookup.
pub trait SequenceData {
    type Item;
    fn len(&self) -> usize;
    fn is_empty(&self) -> bool {
        self.len() == 0
    }
    fn index(&self, idx: usize) -> &Self::Item;
}

// Implement SequenceData for slices.
impl<Element> SequenceData for [Element] {
    type Item = Element;
    #[inline]
    fn len(&self) -> usize {
        self.len()
    }
    #[inline]
    fn index(&self, idx: usize) -> &Element {
        &self[idx]
    }
}

#[repr(C)]
pub struct _SzSequence {
    pub handle: *const c_void,
    pub count: usize,
    pub get_start: Option<unsafe extern "C" fn(handle: *const c_void, idx: usize) -> *const c_void>,
    pub get_length: Option<unsafe extern "C" fn(handle: *const c_void, idx: usize) -> usize>,
}

impl Byteset {
    /// Initializes a bit-set to an empty collection (all characters banned).
    #[inline]
    pub const fn new() -> Self {
        Self { bits: [0; 4] }
    }

    /// Initializes a bit-set to contain all ASCII characters.
    #[inline]
    pub const fn new_ascii() -> Self {
        Self {
            bits: [u64::MAX, u64::MAX, 0, 0],
        }
    }

    /// Adds a byte to the set.
    #[inline]
    pub const fn add_u8(&mut self, byte: u8) {
        let word = (byte >> 6) as usize; // Divide by 64.
        let bit = byte & 63; // Remainder modulo 64.
        self.bits[word] |= 1 << bit;
    }

    /// Adds a character to the set.
    ///
    /// This function assumes the character is in the ASCII range.
    #[inline]
    pub const fn add(&mut self, character: char) {
        self.add_u8(character as u8);
    }

    /// Inverts the bit-set so that all set bits become unset and vice versa.
    #[inline]
    pub const fn invert(&mut self) {
        let mut word = 0;
        while word < 4 {
            self.bits[word] = !self.bits[word];
            word += 1;
        }
    }

    /// Returns a new Byteset with all bits inverted, leaving self unchanged.
    #[inline]
    pub const fn inverted(&self) -> Self {
        Self {
            bits: [!self.bits[0], !self.bits[1], !self.bits[2], !self.bits[3]],
        }
    }

    /// Constructs a Byteset from a slice of bytes.
    ///
    /// Usable in a `const`, so a hot loop can name a set instead of rebuilding one per call:
    ///
    /// ```rust
    /// use stringzilla::sz::Byteset;
    /// const WHITESPACE: Byteset = Byteset::from_bytes(b" \t\r\n");
    /// assert_eq!(stringzilla::sz::find_byteset("ab cd", WHITESPACE), Some(2));
    /// ```
    #[inline]
    pub const fn from_bytes(bytes: &[u8]) -> Self {
        let mut set = Self::new();
        let mut index = 0;
        while index < bytes.len() {
            set.add_u8(bytes[index]);
            index += 1;
        }
        set
    }
}

impl Default for Byteset {
    fn default() -> Self {
        Self::new()
    }
}

impl<Source: AsRef<[u8]>> From<Source> for Byteset {
    #[inline]
    fn from(bytes: Source) -> Self {
        Self::from_bytes(bytes.as_ref())
    }
}

use core::cell::UnsafeCell;
use core::cmp::Ordering;
use core::ffi::{c_char, c_void, CStr};
use core::fmt::{self, Write};

// Import the functions from the StringZillable C library.
extern "C" {

    pub(crate) fn sz_dynamic_dispatch() -> i32;
    pub(crate) fn sz_version_major() -> i32;
    pub(crate) fn sz_version_minor() -> i32;
    pub(crate) fn sz_version_patch() -> i32;
    pub(crate) fn sz_capabilities() -> u32;
    pub(crate) fn sz_capabilities_to_string(caps: u32) -> *const c_void;

    pub(crate) fn sz_copy(target: *const c_void, source: *const c_void, length: usize);
    pub(crate) fn sz_fill(target: *const c_void, length: usize, value: u8);
    pub(crate) fn sz_move(target: *const c_void, source: *const c_void, length: usize);
    pub(crate) fn sz_fill_random(text: *mut c_void, length: usize, seed: u64);
    pub(crate) fn sz_lookup(target: *const c_void, length: usize, source: *const c_void, lut: *const u8);

    pub(crate) fn sz_find(
        haystack: *const c_void,
        haystack_length: usize,
        needle: *const c_void,
        needle_length: usize,
    ) -> *const c_void;

    pub(crate) fn sz_rfind(
        haystack: *const c_void,
        haystack_length: usize,
        needle: *const c_void,
        needle_length: usize,
    ) -> *const c_void;

    pub(crate) fn sz_find_byteset(
        haystack: *const c_void,
        haystack_length: usize,
        byteset: *const c_void,
    ) -> *const c_void;
    pub(crate) fn sz_rfind_byteset(
        haystack: *const c_void,
        haystack_length: usize,
        byteset: *const c_void,
    ) -> *const c_void;

    pub(crate) fn sz_utf8_count(text: *const c_void, length: usize) -> usize;
    pub(crate) fn sz_utf8_seek(text: *const c_void, length: usize, n: usize) -> *const c_void;
    pub(crate) fn sz_utf8_decode(
        text: *const c_void,
        length: usize,
        runes: *mut u32,
        runes_capacity: usize,
        runes_unpacked: *mut usize,
    ) -> *const c_void;
    pub(crate) fn sz_utf8_newlines(
        text: *const c_void,
        length: usize,
        match_offsets: *mut usize,
        match_lengths: *mut usize,
        matches_capacity: usize,
        bytes_consumed: *mut usize,
    ) -> usize;
    pub(crate) fn sz_utf8_whitespaces(
        text: *const c_void,
        length: usize,
        match_offsets: *mut usize,
        match_lengths: *mut usize,
        matches_capacity: usize,
        bytes_consumed: *mut usize,
    ) -> usize;
    pub(crate) fn sz_utf8_delimiters(
        text: *const c_void,
        length: usize,
        match_offsets: *mut usize,
        match_lengths: *mut usize,
        matches_capacity: usize,
        bytes_consumed: *mut usize,
    ) -> usize;
    pub(crate) fn sz_utf8_uncased_fold(source: *const c_void, source_length: usize, destination: *mut c_void) -> usize;
    pub(crate) fn sz_utf8_norm(
        source: *const c_void,
        source_length: usize,
        form: i32,
        destination: *mut c_void,
    ) -> usize;
    pub(crate) fn sz_utf8_find_denormalized(source: *const c_void, source_length: usize, form: i32) -> *const c_void;
    pub(crate) fn sz_utf8_uncased_search(
        haystack: *const c_void,
        haystack_length: usize,
        needle: *const c_void,
        needle_length: usize,
        needle_metadata: *mut Utf8UncasedNeedleMetadata,
        matched_length: *mut usize,
    ) -> *const c_void;
    pub(crate) fn sz_utf8_uncased_order(a: *const c_void, a_length: usize, b: *const c_void, b_length: usize) -> i32;

    pub(crate) fn sz_utf8_wordbreaks(
        text: *const c_void,
        length: usize,
        word_starts: *mut usize,
        word_lengths: *mut usize,
        words_capacity: usize,
        bytes_consumed: *mut usize,
    ) -> usize;

    pub(crate) fn sz_utf8_graphemes(
        text: *const c_void,
        length: usize,
        starts: *mut usize,
        lengths: *mut usize,
        cap: usize,
        consumed: *mut usize,
    ) -> usize;
    pub(crate) fn sz_utf8_sentences(
        text: *const c_void,
        length: usize,
        starts: *mut usize,
        lengths: *mut usize,
        cap: usize,
        consumed: *mut usize,
    ) -> usize;
    pub(crate) fn sz_utf8_linebreaks(
        text: *const c_void,
        length: usize,
        starts: *mut usize,
        lengths: *mut usize,
        cap: usize,
        consumed: *mut usize,
    ) -> usize;

    pub(crate) fn sz_equal(a: *const c_void, b: *const c_void, length: usize) -> i32;
    pub(crate) fn sz_order(a: *const c_void, a_length: usize, b: *const c_void, b_length: usize) -> i32;

    pub(crate) fn sz_bytesum(text: *const c_void, length: usize) -> u64;
    pub(crate) fn sz_hash(text: *const c_void, length: usize, seed: u64) -> u64;
    pub(crate) fn sz_hash_multiseed(
        text: *const c_void,
        length: usize,
        seeds: *const u64,
        seeds_count: usize,
        hashes: *mut u64,
    );
    pub(crate) fn sz_hash_state_init(state: *const c_void, seed: u64);
    pub(crate) fn sz_hash_state_update(state: *const c_void, text: *const c_void, length: usize);
    pub(crate) fn sz_hash_state_digest(state: *const c_void) -> u64;
    pub(crate) fn sz_sha256_state_init(state: *const c_void);
    pub(crate) fn sz_sha256_state_update(state: *const c_void, data: *const c_void, length: usize);
    pub(crate) fn sz_sha256_state_digest(state: *const c_void, digest: *mut u8);
    pub(crate) fn sz_sha256_multistate_update(states: *mut c_void, texts: *const _SzSequence);
    pub(crate) fn sz_sha256_multistate_digest(states: *const c_void, states_count: usize, digests: *mut u8);

    pub(crate) fn sz_aes256_key_init(key: *mut c_void, secret: *const u8);
    pub(crate) fn sz_aes256_ctr_xor(
        key: *const c_void,
        nonce: *const u8,
        byte_offset: u64,
        text: *const c_void,
        length: usize,
        output: *mut c_void,
    );
    pub(crate) fn sz_aes256_gcm_key_init(key: *mut c_void, secret: *const u8);
    pub(crate) fn sz_aes256_gcm_encrypt(
        key: *const c_void,
        nonce: *const u8,
        associated: *const c_void,
        associated_length: usize,
        text: *const c_void,
        length: usize,
        output: *mut c_void,
        tag: *mut u8,
    );
    /// Returns `sz_status_t` as a raw code, because a value outside `Status` would be undefined
    /// behavior to receive as that enum, and a decryption must never mistake one for success.
    pub(crate) fn sz_aes256_gcm_decrypt(
        key: *const c_void,
        nonce: *const u8,
        associated: *const c_void,
        associated_length: usize,
        text: *const c_void,
        length: usize,
        output: *mut c_void,
        tag: *const u8,
    ) -> i32;
    pub(crate) fn sz_aes256_gcm_encryptor_init(encryptor: *mut c_void, key: *const c_void, nonce: *const u8);
    pub(crate) fn sz_aes256_gcm_encryptor_associate(encryptor: *mut c_void, text: *const c_void, length: usize);
    pub(crate) fn sz_aes256_gcm_encryptor_update(
        encryptor: *mut c_void,
        text: *const c_void,
        length: usize,
        output: *mut c_void,
    );
    pub(crate) fn sz_aes256_gcm_encryptor_digest(encryptor: *const c_void, tag: *mut u8);
    pub(crate) fn sz_aes256_gcm_decryptor_init(decryptor: *mut c_void, key: *const c_void, nonce: *const u8);
    pub(crate) fn sz_aes256_gcm_decryptor_associate(decryptor: *mut c_void, text: *const c_void, length: usize);
    pub(crate) fn sz_aes256_gcm_decryptor_update_unverified(
        decryptor: *mut c_void,
        text: *const c_void,
        length: usize,
        output: *mut c_void,
    );
    /// Returns `sz_status_t` as a raw code, for the same reason as `sz_aes256_gcm_decrypt`.
    pub(crate) fn sz_aes256_gcm_decryptor_verify(decryptor: *const c_void, tag: *const u8) -> i32;

    pub(crate) fn sz_sequence_argsort(
        //
        sequence: *const _SzSequence,
        alloc: *const c_void,
        order: *mut SortedIdx,
        top_count: usize,
        reverse: i32,
    ) -> Status;

    pub(crate) fn sz_sequence_argsort_uncased(
        //
        sequence: *const _SzSequence,
        alloc: *const c_void,
        order: *mut SortedIdx,
        top_count: usize,
        reverse: i32,
    ) -> Status;

    pub(crate) fn sz_sequence_intersect(
        first_sequence: *const _SzSequence,
        second_sequence: *const _SzSequence,
        alloc: *const c_void,
        seed: u64,
        intersection_size: *mut usize,
        first_positions: *mut SortedIdx,
        second_positions: *mut SortedIdx,
    ) -> Status;

}

impl SemVer {
    pub const fn new(major: i32, minor: i32, patch: i32) -> Self {
        Self { major, minor, patch }
    }
}

impl Hasher {
    /// Creates a new hasher initialized with `seed`.
    pub fn new(seed: u64) -> Self {
        let mut state = Hasher {
            aes: [0; 8],
            sum: [0; 8],
            ins: [0; 8],
            key: [0; 2],
            ins_length: 0,
        };
        unsafe {
            sz_hash_state_init(&mut state as *mut _ as *mut c_void, seed);
        }
        state
    }

    /// Updates the hasher with more data.
    pub fn update(&mut self, data: &[u8]) -> &mut Self {
        unsafe {
            sz_hash_state_update(
                self as *mut _ as *mut c_void,
                data.as_ptr() as *const c_void,
                data.len(),
            );
        }
        self
    }

    /// Returns the current hash value without consuming the state.
    pub fn digest(&self) -> u64 {
        unsafe { sz_hash_state_digest(self as *const _ as *const c_void) }
    }
}

impl PartialEq for Hasher {
    fn eq(&self, other: &Self) -> bool {
        self.aes == other.aes && self.sum == other.sum && self.key == other.key
    }
}

impl Default for Hasher {
    #[inline]
    fn default() -> Self {
        Hasher::new(0)
    }
}

impl Sha256 {
    /// Creates a new SHA256 hasher with the initial state.
    pub fn new() -> Self {
        let mut state = Sha256([0; 128]);
        unsafe {
            sz_sha256_state_init(&mut state as *mut _ as *mut c_void);
        }
        state
    }

    /// Updates the hasher with more data.
    pub fn update(&mut self, data: &[u8]) -> &mut Self {
        unsafe {
            sz_sha256_state_update(
                self as *mut _ as *mut c_void,
                data.as_ptr() as *const c_void,
                data.len(),
            );
        }
        self
    }

    /// Returns the current SHA256 digest, leaving the hasher able to accept more data.
    pub fn digest(&self) -> Sha256Digest {
        let mut digest = [0u8; SHA256_DIGEST_LENGTH];
        unsafe {
            sz_sha256_state_digest(self as *const _ as *const c_void, digest.as_mut_ptr());
        }
        digest
    }

    /// Convenience method to hash data in one call.
    pub fn hash(data: &[u8]) -> Sha256Digest {
        let mut hasher = Sha256::new();
        hasher.update(data);
        hasher.digest()
    }
}

impl Default for Sha256 {
    #[inline]
    fn default() -> Self {
        Sha256::new()
    }
}

/// Advances many independent SHA256 states at once, one message per lane.
///
/// Hashing a single message is a serial dependency chain, so no instruction set can speed it up. Independent
/// messages do compress in parallel lanes: sixteen at a time on AVX-512, eight on AVX2. Feed at least a few
/// kilobytes per lane per call, since shorter chunks never reach the lane-parallel path.
///
/// Borrows the caller's storage throughout and allocates nothing. Accepts anything that dereferences to
/// bytes, so a `Vec<String>` or `Vec<Vec<u8>>` needs no intermediate slice-of-slices. See
/// [`sha256_multistate_update_by`] for messages that do not sit in one contiguous slice.
///
/// # Errors
///
/// Returns [`Status::BadAlloc`] if `chunks` does not have exactly one entry per lane.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
///
/// let mut states = vec![sz::Sha256::new(); 2];
/// let heads: Vec<String> = vec!["Hello, ".into(), "Goodbye, ".into()];
/// let tails: Vec<String> = vec!["world!".into(), "world!".into()];
/// sz::sha256_multistate_update(&mut states, &heads).unwrap();
/// sz::sha256_multistate_update(&mut states, &tails).unwrap();
///
/// let mut digests = vec![[0u8; 32]; 2];
/// sz::sha256_multistate_digest(&states, &mut digests).unwrap();
/// assert_eq!(digests[0], sz::Sha256::hash(b"Hello, world!"));
/// assert_eq!(digests[1], sz::Sha256::hash(b"Goodbye, world!"));
/// ```
pub fn sha256_multistate_update<Element: AsRef<[u8]>>(states: &mut [Sha256], chunks: &[Element]) -> Result<(), Status> {
    if chunks.len() != states.len() {
        return Err(Status::BadAlloc);
    }
    sha256_multistate_update_by(states, |lane_index| chunks[lane_index].as_ref())
}

/// Advances many independent SHA256 states at once, taking each lane's next chunk from a caller-provided key.
///
/// # Errors
///
/// Returns [`Status::BadAlloc`] if `mapper` cannot serve one chunk per lane.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
///
/// struct Record { payload: &'static str }
/// let records = [Record { payload: "alpha" }, Record { payload: "beta" }];
///
/// let mut states = vec![sz::Sha256::new(); 2];
/// sz::sha256_multistate_update_by(&mut states, |lane| records[lane].payload.as_bytes()).unwrap();
///
/// let mut digests = vec![[0u8; 32]; 2];
/// sz::sha256_multistate_digest(&states, &mut digests).unwrap();
/// assert_eq!(digests[0], sz::Sha256::hash(b"alpha"));
/// ```
pub fn sha256_multistate_update_by<Mapper, Key>(states: &mut [Sha256], mapper: Mapper) -> Result<(), Status>
where
    Mapper: Fn(usize) -> Key,
    Key: AsRef<[u8]>,
{
    if states.is_empty() {
        return Ok(());
    }

    // Same adapter as `argsort_by`: relabel each borrowed chunk `'static` so it can cross the C ABI. Safe
    // because the kernel reads the chunks only during this synchronous call.
    let adapter = move |lane_index: usize| -> &'static [u8] {
        let binding = mapper(lane_index);
        let slice = binding.as_ref();
        unsafe { core::mem::transmute(slice) }
    };
    _sha256_multistate_update_impl(adapter, states)
}

/// Helper that takes an adapter (with a concrete type) and performs the FFI call.
fn _sha256_multistate_update_impl<Adapter>(adapter: Adapter, states: &mut [Sha256]) -> Result<(), Status>
where
    Adapter: Fn(usize) -> &'static [u8],
{
    let wrapper = _PunnedSliceLookupView {
        get_slice: unsafe { _get_slice_fn::<Adapter>() },
        data: &adapter as *const Adapter as *const c_void,
    };
    let texts = _SzSequence {
        handle: &wrapper as *const _ as *const c_void,
        count: states.len(),
        get_start: Some(_slice_get_start_punned),
        get_length: Some(_slice_get_length_punned),
    };
    unsafe { sz_sha256_multistate_update(states.as_mut_ptr() as *mut c_void, &texts) };
    Ok(())
}

/// Writes each lane's digest into caller-provided storage, leaving every lane able to accept more data.
///
/// # Errors
///
/// Returns [`Status::BadAlloc`] if `digests` does not have exactly one entry per lane.
pub fn sha256_multistate_digest(states: &[Sha256], digests: &mut [Sha256Digest]) -> Result<(), Status> {
    if digests.len() != states.len() {
        return Err(Status::BadAlloc);
    }
    if states.is_empty() {
        return Ok(());
    }
    unsafe {
        sz_sha256_multistate_digest(
            states.as_ptr() as *const c_void,
            states.len(),
            digests.as_mut_ptr() as *mut u8,
        )
    };
    Ok(())
}

/// Computes HMAC-SHA256 (Hash-based Message Authentication Code) for the given key and message.
///
/// # Arguments
///
/// * `key` - The secret key (can be any length, will be hashed if > 64 bytes)
/// * `message` - The message to authenticate
///
/// # Returns
///
/// A 32-byte HMAC-SHA256 digest
///
/// # Example
///
/// ```
/// use stringzilla::stringzilla::hmac_sha256;
/// let key = b"secret_key";
/// let message = b"important message";
/// let mac = hmac_sha256(key, message);
/// assert_eq!(mac.len(), 32);
/// ```
pub fn hmac_sha256(key: &[u8], message: &[u8]) -> Sha256Digest {
    let (mut inner, outer) = _hmac_sha256_primed(key);
    inner.update(message);
    _hmac_sha256_wrap(&inner, &outer)
}

/// Primes the inner and outer states with the HMAC key pads, per FIPS 198-1.
///
/// The message enters only the inner hash, as the suffix of the ipad block, so authenticating many
/// messages under one key is as lane-parallel as digesting them: prime once, then broadcast.
fn _hmac_sha256_primed(key: &[u8]) -> (Sha256, Sha256) {
    // Keys longer than one block are replaced by their digest; shorter ones are zero-padded.
    let mut key_pad = [0u8; SHA256_BLOCK_LENGTH];
    if key.len() > SHA256_BLOCK_LENGTH {
        key_pad[..SHA256_DIGEST_LENGTH].copy_from_slice(&Sha256::hash(key));
    } else {
        key_pad[..key.len()].copy_from_slice(key);
    }

    let mut block = [0u8; SHA256_BLOCK_LENGTH];
    let mut inner = Sha256::new();
    for byte_index in 0..SHA256_BLOCK_LENGTH {
        block[byte_index] = key_pad[byte_index] ^ 0x36;
    }
    inner.update(&block);

    let mut outer = Sha256::new();
    for byte_index in 0..SHA256_BLOCK_LENGTH {
        block[byte_index] = key_pad[byte_index] ^ 0x5c;
    }
    outer.update(&block);

    // The pads are derived from the secret, so don't leave them on the stack for the next frame. The
    // writes are volatile because nothing reads them afterwards and a plain assignment is a dead store.
    unsafe {
        core::ptr::write_volatile(&mut key_pad, [0u8; SHA256_BLOCK_LENGTH]);
        core::ptr::write_volatile(&mut block, [0u8; SHA256_BLOCK_LENGTH]);
    }
    core::sync::atomic::compiler_fence(core::sync::atomic::Ordering::SeqCst);
    (inner, outer)
}

/// Wraps the inner state's digest with the primed outer state, completing one tag.
fn _hmac_sha256_wrap(inner: &Sha256, outer: &Sha256) -> Sha256Digest {
    let mut wrapping = *outer;
    wrapping.update(&inner.digest());
    wrapping.digest()
}

/// Authenticates many messages under one key at once, one message per lane.
///
/// Authenticating one message is a serial dependency chain, but independent messages compress in
/// parallel lanes - sixteen at a time on AVX-512, eight on AVX2 - and both the message pass and HMAC's
/// outer wrap ride those same kernels. Intended for batches of short messages, such as tokens or
/// webhook bodies sharing a secret; there is no streaming form, since the message never spans calls.
///
/// Borrows the caller's storage throughout and allocates nothing, so it works under `no_std`. `states`
/// is scratch of one state per message, reused for both passes; only `tags` is written for keeps.
///
/// # Errors
///
/// Returns [`Status::BadAlloc`] unless `messages`, `states` and `tags` all have the same length.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
///
/// let messages: Vec<String> = vec!["alpha".into(), "beta".into()];
/// let mut states = vec![sz::Sha256::new(); messages.len()];
/// let mut tags = vec![[0u8; 32]; messages.len()];
///
/// sz::hmac_sha256_multistate(b"secret", &messages, &mut states, &mut tags).unwrap();
/// assert_eq!(tags[0], sz::hmac_sha256(b"secret", b"alpha"));
/// ```
pub fn hmac_sha256_multistate<Element: AsRef<[u8]>>(
    key: &[u8],
    messages: &[Element],
    states: &mut [Sha256],
    tags: &mut [Sha256Digest],
) -> Result<(), Status> {
    if messages.len() != states.len() || messages.len() != tags.len() {
        return Err(Status::BadAlloc);
    }
    if messages.is_empty() {
        return Ok(());
    }

    let (inner, outer) = _hmac_sha256_primed(key);
    for state in states.iter_mut() {
        *state = inner;
    }
    sha256_multistate_update(states, messages)?;
    sha256_multistate_digest(states, tags)?;

    // Second pass: every lane absorbs its own inner digest, read straight out of `tags`.
    for state in states.iter_mut() {
        *state = outer;
    }
    {
        let inner_digests = &*tags;
        sha256_multistate_update_by(states, |lane_index| &inner_digests[lane_index][..])?;
    }

    // Safe to overwrite in place: every inner digest has already been absorbed into its lane.
    sha256_multistate_digest(states, tags)
}

/// Standard Hasher trait to interoperate with `std::collections`.
impl core::hash::Hasher for Hasher {
    #[inline]
    fn finish(&self) -> u64 {
        self.digest()
    }

    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        let _ = self.update(bytes);
    }

    // Feed integers as little-endian bytes for cross-platform stability
    #[inline]
    fn write_u8(&mut self, i: u8) {
        self.write(&[i]);
    }
    #[inline]
    fn write_u16(&mut self, i: u16) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_u32(&mut self, i: u32) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_u64(&mut self, i: u64) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_u128(&mut self, i: u128) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_usize(&mut self, i: usize) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_i8(&mut self, i: i8) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_i16(&mut self, i: i16) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_i32(&mut self, i: i32) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_i64(&mut self, i: i64) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_i128(&mut self, i: i128) {
        self.write(&i.to_le_bytes());
    }
    #[inline]
    fn write_isize(&mut self, i: isize) {
        self.write(&i.to_le_bytes());
    }
}

/// BuildHasher for constructing `Hasher` instances, enabling use with HashMap/HashSet.
///
/// By default uses seed 0 for deterministic hashing across runs and platforms.
/// If you need DOS-resistant randomized seeding, consider wrapping this in your
/// application with a per-process random seed.
#[cfg(feature = "std")]
#[derive(Debug, Clone, Copy, Default)]
pub struct BuildSzHasher {
    pub seed: u64,
}

#[cfg(feature = "std")]
impl BuildSzHasher {
    #[inline]
    pub const fn with_seed(seed: u64) -> Self {
        Self { seed }
    }
}

#[cfg(feature = "std")]
impl std::hash::BuildHasher for BuildSzHasher {
    type Hasher = Hasher;
    #[inline]
    fn build_hasher(&self) -> Self::Hasher {
        Hasher::new(self.seed)
    }
}

/// Maps the raw `sz_status_t` of an authenticated path onto a `Result` the caller cannot drop
/// silently. Any status other than success refuses the plaintext rather than guessing at it.
fn authentication_result_from_status(status: i32) -> Result<(), AuthenticationError> {
    const SUCCESS: i32 = Status::Success as i32;
    const AUTHENTICATION_FAILED: i32 = Status::AuthenticationFailed as i32;
    match status {
        SUCCESS => Ok(()),
        AUTHENTICATION_FAILED => Err(AuthenticationError::TagMismatch),
        other => Err(AuthenticationError::UnexpectedStatus(other)),
    }
}

impl Aes256CtrKey {
    /// Expands a 32-byte secret into the AES-256 round-key schedule.
    pub fn new(secret: &[u8; AES256_KEY_LENGTH]) -> Self {
        let mut key = Aes256CtrKey::zeroed();
        unsafe { sz_aes256_key_init(&mut key as *mut _ as *mut c_void, secret.as_ptr()) };
        key
    }

    /// Exclusive-ors `text` against the keystream starting at `byte_offset`, writing `output`.
    /// Counter mode is its own inverse, so this call both encrypts and decrypts.
    ///
    /// # Panics
    ///
    /// Panics if `output` is not as long as `text`.
    pub fn xor_into(&self, nonce: &[u8; AES256_NONCE_LENGTH], byte_offset: u64, text: &[u8], output: &mut [u8]) {
        assert_eq!(text.len(), output.len(), "`output` must be as long as `text`");
        unsafe {
            sz_aes256_ctr_xor(
                self as *const _ as *const c_void,
                nonce.as_ptr(),
                byte_offset,
                text.as_ptr() as *const c_void,
                text.len(),
                output.as_mut_ptr() as *mut c_void,
            )
        }
    }

    /// Exclusive-ors `text` against the keystream starting at `byte_offset`, in place.
    /// Counter mode is its own inverse, so this call both encrypts and decrypts.
    pub fn xor_in_place(&self, nonce: &[u8; AES256_NONCE_LENGTH], byte_offset: u64, text: &mut [u8]) {
        let length = text.len();
        let pointer = text.as_mut_ptr() as *mut c_void;
        unsafe {
            sz_aes256_ctr_xor(
                self as *const _ as *const c_void,
                nonce.as_ptr(),
                byte_offset,
                pointer as *const c_void,
                length,
                pointer,
            )
        }
    }

    /// An all-zero schedule, expanded in place by the C core before any caller sees it.
    const fn zeroed() -> Self {
        Aes256CtrKey {
            round_keys: [0; AES256_ROUND_KEYS],
        }
    }
}

impl Drop for Aes256CtrKey {
    /// Overwrites the schedule so the key does not outlive its use.
    ///
    /// The write is volatile because a plain assignment is a dead store - nothing reads the schedule
    /// after this returns, so the optimizer is free to delete it - and the fence stops the zeros from
    /// sinking past the end of the drop.
    fn drop(&mut self) {
        unsafe { core::ptr::write_volatile(self as *mut Self, Self::zeroed()) };
        core::sync::atomic::compiler_fence(core::sync::atomic::Ordering::SeqCst);
    }
}

impl fmt::Debug for Aes256CtrKey {
    /// Prints a placeholder, because a key that reaches a log is a key that has leaked.
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        formatter.write_str("Aes256CtrKey(<secret>)")
    }
}

impl Aes256GcmKey {
    /// Expands a 32-byte secret into a schedule and the Galois hash subkey powers.
    pub fn new(secret: &[u8; AES256_KEY_LENGTH]) -> Self {
        let mut key = Aes256GcmKey::zeroed();
        unsafe { sz_aes256_gcm_key_init(&mut key as *mut _ as *mut c_void, secret.as_ptr()) };
        key
    }

    /// Encrypts `text` into `output`, returning the tag over the ciphertext and `associated`.
    /// The associated bytes are authenticated but not encrypted, such as a routing header.
    ///
    /// # Panics
    ///
    /// Panics if `output` is not as long as `text`.
    pub fn encrypt_into(
        &self,
        nonce: &[u8; AES256_NONCE_LENGTH],
        associated: &[u8],
        text: &[u8],
        output: &mut [u8],
    ) -> [u8; AES256_TAG_LENGTH] {
        assert_eq!(text.len(), output.len(), "`output` must be as long as `text`");
        let mut tag = [0u8; AES256_TAG_LENGTH];
        unsafe {
            sz_aes256_gcm_encrypt(
                self as *const _ as *const c_void,
                nonce.as_ptr(),
                associated.as_ptr() as *const c_void,
                associated.len(),
                text.as_ptr() as *const c_void,
                text.len(),
                output.as_mut_ptr() as *mut c_void,
                tag.as_mut_ptr(),
            )
        };
        tag
    }

    /// Encrypts `text` in place, returning the tag over the ciphertext and `associated`.
    pub fn encrypt_in_place(
        &self,
        nonce: &[u8; AES256_NONCE_LENGTH],
        associated: &[u8],
        text: &mut [u8],
    ) -> [u8; AES256_TAG_LENGTH] {
        let mut tag = [0u8; AES256_TAG_LENGTH];
        let length = text.len();
        let pointer = text.as_mut_ptr() as *mut c_void;
        unsafe {
            sz_aes256_gcm_encrypt(
                self as *const _ as *const c_void,
                nonce.as_ptr(),
                associated.as_ptr() as *const c_void,
                associated.len(),
                pointer as *const c_void,
                length,
                pointer,
                tag.as_mut_ptr(),
            )
        };
        tag
    }

    /// Verifies `tag` and decrypts `text` into `output`, which holds the plaintext only on success.
    /// A rejected tag leaves `output` zeroed, so a caller who drops the error still cannot read
    /// forged plaintext. The comparison takes the same time wherever the tag first differs.
    ///
    /// # Panics
    ///
    /// Panics if `output` is not as long as `text`.
    pub fn decrypt_into(
        &self,
        nonce: &[u8; AES256_NONCE_LENGTH],
        associated: &[u8],
        text: &[u8],
        output: &mut [u8],
        tag: &[u8; AES256_TAG_LENGTH],
    ) -> Result<(), AuthenticationError> {
        assert_eq!(text.len(), output.len(), "`output` must be as long as `text`");
        let status = unsafe {
            sz_aes256_gcm_decrypt(
                self as *const _ as *const c_void,
                nonce.as_ptr(),
                associated.as_ptr() as *const c_void,
                associated.len(),
                text.as_ptr() as *const c_void,
                text.len(),
                output.as_mut_ptr() as *mut c_void,
                tag.as_ptr(),
            )
        };
        authentication_result_from_status(status)
    }

    /// Verifies `tag` and decrypts `text` in place, which holds the plaintext only on success.
    /// A rejected tag zeroes `text`, destroying the ciphertext it arrived with.
    pub fn decrypt_in_place(
        &self,
        nonce: &[u8; AES256_NONCE_LENGTH],
        associated: &[u8],
        text: &mut [u8],
        tag: &[u8; AES256_TAG_LENGTH],
    ) -> Result<(), AuthenticationError> {
        let length = text.len();
        let pointer = text.as_mut_ptr() as *mut c_void;
        let status = unsafe {
            sz_aes256_gcm_decrypt(
                self as *const _ as *const c_void,
                nonce.as_ptr(),
                associated.as_ptr() as *const c_void,
                associated.len(),
                pointer as *const c_void,
                length,
                pointer,
                tag.as_ptr(),
            )
        };
        authentication_result_from_status(status)
    }

    /// An all-zero key, expanded in place by the C core before any caller sees it.
    const fn zeroed() -> Self {
        Aes256GcmKey {
            block: Aes256CtrKey::zeroed(),
            powers: [0; AES256_GALOIS_POWERS],
        }
    }
}

impl Drop for Aes256GcmKey {
    /// Overwrites the schedule and the hash powers so the key does not outlive its use.
    ///
    /// The write is volatile for the same reason as in [`Aes256CtrKey`]: a plain assignment is a
    /// dead store the optimizer may delete, and the fence stops the zeros from sinking past the end
    /// of the drop.
    fn drop(&mut self) {
        unsafe { core::ptr::write_volatile(self as *mut Self, Self::zeroed()) };
        core::sync::atomic::compiler_fence(core::sync::atomic::Ordering::SeqCst);
    }
}

impl fmt::Debug for Aes256GcmKey {
    /// Prints a placeholder, because a key that reaches a log is a key that has leaked.
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        formatter.write_str("Aes256GcmKey(<secret>)")
    }
}

impl Aes256GcmState {
    /// An all-zero payload, filled in by the typed C entry point before any caller sees it.
    const fn zeroed() -> Self {
        Aes256GcmState {
            key: Aes256GcmKey::zeroed(),
            accumulator: [0; 16],
            counter: [0; 16],
            tag_mask: [0; 16],
            partial: [0; 16],
            keystream: [0; 16],
            associated_length: 0,
            text_length: 0,
            buffered: 0,
            keystream_used: 0,
        }
    }
}

impl Drop for Aes256GcmEncryptor {
    /// Overwrites the payload so a streamed message leaves nothing behind.
    ///
    /// The embedded key scrubs itself through [`Aes256GcmKey`]'s drop; the rest does not, and 77 bytes
    /// of tag mask, live keystream and pending hash block survived before this existed.
    fn drop(&mut self) {
        unsafe { core::ptr::write_volatile(&mut self.state as *mut Aes256GcmState, Aes256GcmState::zeroed()) };
        core::sync::atomic::compiler_fence(core::sync::atomic::Ordering::SeqCst);
    }
}

impl Drop for Aes256GcmDecryptor {
    /// Overwrites the payload for the same reason [`Aes256GcmEncryptor`] does.
    fn drop(&mut self) {
        unsafe { core::ptr::write_volatile(&mut self.state as *mut Aes256GcmState, Aes256GcmState::zeroed()) };
        core::sync::atomic::compiler_fence(core::sync::atomic::Ordering::SeqCst);
    }
}

impl Aes256GcmEncryptor {
    /// Begins a chunked encryption under `key` and `nonce`, copying `key` in so this cannot outlive it.
    pub fn new(key: &Aes256GcmKey, nonce: &[u8; AES256_NONCE_LENGTH]) -> Self {
        let mut encryptor = Aes256GcmEncryptor {
            state: Aes256GcmState::zeroed(),
        };
        unsafe {
            sz_aes256_gcm_encryptor_init(
                &mut encryptor as *mut _ as *mut c_void,
                key as *const _ as *const c_void,
                nonce.as_ptr(),
            )
        };
        encryptor
    }

    /// Absorbs associated data, which is authenticated but not encrypted.
    /// All of it must be absorbed before the first chunk of the message.
    pub fn associate(&mut self, associated: &[u8]) -> &mut Self {
        unsafe {
            sz_aes256_gcm_encryptor_associate(
                self as *mut _ as *mut c_void,
                associated.as_ptr() as *const c_void,
                associated.len(),
            )
        };
        self
    }

    /// Encrypts one chunk into `output` and folds its ciphertext into the running tag.
    ///
    /// # Panics
    ///
    /// Panics if `output` is not as long as `text`.
    pub fn encrypt_into(&mut self, text: &[u8], output: &mut [u8]) -> &mut Self {
        assert_eq!(text.len(), output.len(), "`output` must be as long as `text`");
        unsafe {
            sz_aes256_gcm_encryptor_update(
                self as *mut _ as *mut c_void,
                text.as_ptr() as *const c_void,
                text.len(),
                output.as_mut_ptr() as *mut c_void,
            )
        };
        self
    }

    /// Encrypts one chunk in place and folds its ciphertext into the running tag.
    pub fn encrypt_in_place(&mut self, text: &mut [u8]) -> &mut Self {
        let length = text.len();
        let pointer = text.as_mut_ptr() as *mut c_void;
        unsafe {
            sz_aes256_gcm_encryptor_update(self as *mut _ as *mut c_void, pointer as *const c_void, length, pointer)
        };
        self
    }

    /// Returns the tag over everything encrypted so far, leaving the encryptor ready for more.
    pub fn digest(&self) -> [u8; AES256_TAG_LENGTH] {
        let mut tag = [0u8; AES256_TAG_LENGTH];
        unsafe { sz_aes256_gcm_encryptor_digest(self as *const _ as *const c_void, tag.as_mut_ptr()) };
        tag
    }
}

impl Aes256GcmDecryptor {
    /// Begins a chunked decryption under `key` and `nonce`, copying `key` in so this cannot outlive it.
    pub fn new(key: &Aes256GcmKey, nonce: &[u8; AES256_NONCE_LENGTH]) -> Self {
        let mut decryptor = Aes256GcmDecryptor {
            state: Aes256GcmState::zeroed(),
        };
        unsafe {
            sz_aes256_gcm_decryptor_init(
                &mut decryptor as *mut _ as *mut c_void,
                key as *const _ as *const c_void,
                nonce.as_ptr(),
            )
        };
        decryptor
    }

    /// Absorbs associated data, which is authenticated but not encrypted.
    /// All of it must be absorbed before the first chunk of the message.
    pub fn associate(&mut self, associated: &[u8]) -> &mut Self {
        unsafe {
            sz_aes256_gcm_decryptor_associate(
                self as *mut _ as *mut c_void,
                associated.as_ptr() as *const c_void,
                associated.len(),
            )
        };
        self
    }

    /// Decrypts one chunk into `output` and folds its ciphertext into the running tag.
    ///
    /// The emitted bytes are **not authenticated**. Nothing has yet checked that this ciphertext is
    /// genuine, so the caller owns that risk: buffer the output until [`Self::verify`] succeeds and
    /// discard it if it does not. A streaming decryption cannot avoid this, which is why the name
    /// says so. Callers who can hold the whole message should use [`Aes256GcmKey::decrypt_into`],
    /// which emits nothing until the tag has matched.
    ///
    /// # Panics
    ///
    /// Panics if `output` is not as long as `text`.
    pub fn decrypt_unverified_into(&mut self, text: &[u8], output: &mut [u8]) -> &mut Self {
        assert_eq!(text.len(), output.len(), "`output` must be as long as `text`");
        unsafe {
            sz_aes256_gcm_decryptor_update_unverified(
                self as *mut _ as *mut c_void,
                text.as_ptr() as *const c_void,
                text.len(),
                output.as_mut_ptr() as *mut c_void,
            )
        };
        self
    }

    /// Decrypts one chunk in place and folds its ciphertext into the running tag.
    ///
    /// The emitted bytes are **not authenticated**, exactly as in [`Self::decrypt_unverified_into`],
    /// and in place they also overwrite the ciphertext a failed [`Self::verify`] would have to discard.
    pub fn decrypt_unverified_in_place(&mut self, text: &mut [u8]) -> &mut Self {
        let length = text.len();
        let pointer = text.as_mut_ptr() as *mut c_void;
        unsafe {
            sz_aes256_gcm_decryptor_update_unverified(
                self as *mut _ as *mut c_void,
                pointer as *const c_void,
                length,
                pointer,
            )
        };
        self
    }

    /// Checks `tag` against everything absorbed so far, in time independent of where it differs.
    /// Until this returns `Ok`, every byte the decryptor emitted is an attacker's to choose.
    pub fn verify(&self, tag: &[u8; AES256_TAG_LENGTH]) -> Result<(), AuthenticationError> {
        let status = unsafe { sz_aes256_gcm_decryptor_verify(self as *const _ as *const c_void, tag.as_ptr()) };
        authentication_result_from_status(status)
    }
}

/// Checks if the library was compiled with dynamic dispatch enabled.
pub fn dynamic_dispatch() -> bool {
    unsafe { sz_dynamic_dispatch() != 0 }
}

/// Returns the semantic version information.
pub fn version() -> SemVer {
    SemVer {
        major: unsafe { sz_version_major() },
        minor: unsafe { sz_version_minor() },
        patch: unsafe { sz_version_patch() },
    }
}

/// A fixed-size, compile-time known C-string buffer type.
/// It keeps track of the number of written bytes (excluding the null terminator).
pub struct FixedCString<const CAPACITY: usize> {
    buf: [u8; CAPACITY],
    len: usize,
}

impl<const CAPACITY: usize> FixedCString<CAPACITY> {
    /// Create a new, empty buffer.
    /// The buffer always has a terminating NUL (0) byte at position `len`.
    pub const fn new() -> Self {
        Self {
            buf: [0u8; CAPACITY],
            len: 0,
        }
    }

    /// Returns the raw pointer to the C string.
    pub const fn as_ptr(&self) -> *const u8 {
        self.buf.as_ptr()
    }

    /// Returns a reference as a CStr.
    /// # Safety
    /// The buffer must be correctly NUL terminated.
    pub fn as_c_str(&self) -> &CStr {
        // We know buf[..=len] is NUL-terminated because write_str() always sets it.
        unsafe { CStr::from_bytes_with_nul_unchecked(&self.buf[..=self.len]) }
    }

    /// Returns the current content as a &str.
    /// Returns an empty string if the content isn’t valid UTF-8.
    pub fn as_str(&self) -> &str {
        core::str::from_utf8(&self.buf[..self.len]).unwrap_or("")
    }
}

impl<const CAPACITY: usize> Default for FixedCString<CAPACITY> {
    fn default() -> Self {
        Self::new()
    }
}

impl<const CAPACITY: usize> Write for FixedCString<CAPACITY> {
    fn write_str(&mut self, s: &str) -> fmt::Result {
        let bytes = s.as_bytes();
        // Ensure we have room for the new bytes and a NUL terminator.
        if self.len + bytes.len() >= CAPACITY {
            return Err(fmt::Error);
        }
        self.buf[self.len..self.len + bytes.len()].copy_from_slice(bytes);
        self.len += bytes.len();
        // Always set a null terminator.
        self.buf[self.len] = 0;
        Ok(())
    }
}

pub type SmallCString = FixedCString<256>;

/// Copies the capabilities C-string into a fixed buffer and returns it.
/// The returned SmallCString is guaranteed to be null-terminated.
pub(crate) fn capabilities_from_enum(caps: u32) -> SmallCString {
    let caps_ptr = unsafe { sz_capabilities_to_string(caps) };
    // Assume that the external function returns a valid null-terminated C string.
    let cstr = unsafe { CStr::from_ptr(caps_ptr as *const c_char) };
    let bytes = cstr.to_bytes();

    let mut buf = SmallCString::new();
    // Use core::fmt::Write to copy the bytes.
    // If the string is too long, it will fail. You might want to truncate in a real-world use.
    // Here, we assume it fits.
    let s = core::str::from_utf8(bytes).unwrap_or("");
    let _ = buf.write_str(s);
    buf
}

/// Copies the capabilities C-string into a fixed buffer and returns it.
/// The returned SmallCString is guaranteed to be null-terminated.
pub fn capabilities() -> SmallCString {
    let caps = unsafe { sz_capabilities() };
    capabilities_from_enum(caps)
}

/// Computes the checksum value of unsigned bytes in a given byte slice `text`.
/// This function is useful for verifying data integrity and detecting changes in
/// binary data, such as files or network packets.
///
/// # Arguments
///
/// * `text`: The byte slice to compute the checksum for.
///
/// # Returns
///
/// A `u64` representing the checksum value of the input byte slice.
#[inline(always)]
pub fn bytesum<Text>(text: Text) -> u64
where
    Text: AsRef<[u8]>,
{
    let text_ref = text.as_ref();
    let text_pointer = text_ref.as_ptr() as _;
    let text_length = text_ref.len();
    unsafe { sz_bytesum(text_pointer, text_length) }
}

/// Moves the contents of `source` into `target`, overwriting the existing contents of `target`.
/// This function is useful for scenarios where you need to replace the contents of a byte slice
/// with the contents of another byte slice.
#[inline(always)]
pub fn move_<Target, Source>(target: &mut Target, source: &Source)
where
    Target: AsMut<[u8]> + ?Sized,
    Source: AsRef<[u8]> + ?Sized,
{
    let target_slice = target.as_mut();
    let source_slice = source.as_ref();
    assert!(
        target_slice.len() >= source_slice.len(),
        "target must be at least as long as source"
    );
    unsafe {
        sz_move(
            target_slice.as_mut_ptr() as *const c_void,
            source_slice.as_ptr() as *const c_void,
            source_slice.len(),
        );
    }
}

/// Fills the contents of `target` with the specified `value`. This function is useful for
/// scenarios where you need to set all bytes in a byte slice to a specific value, such as
/// zeroing out a buffer or initializing a buffer with a specific byte pattern.
#[inline(always)]
pub fn fill<Target>(target: &mut Target, value: u8)
where
    Target: AsMut<[u8]> + ?Sized,
{
    let target_slice = target.as_mut();
    unsafe {
        sz_fill(target_slice.as_ptr() as *const c_void, target_slice.len(), value);
    }
}

/// Copies the contents of `source` into `target`, overwriting the existing contents of `target`.
/// This function is useful for scenarios where you need to replace the contents of a byte slice
/// with the contents of another byte slice.
#[inline(always)]
pub fn copy<Target, Source>(target: &mut Target, source: &Source)
where
    Target: AsMut<[u8]> + ?Sized,
    Source: AsRef<[u8]> + ?Sized,
{
    let target_slice = target.as_mut();
    let source_slice = source.as_ref();
    assert!(
        target_slice.len() >= source_slice.len(),
        "target must be at least as long as source"
    );
    unsafe {
        sz_copy(
            target_slice.as_mut_ptr() as *mut c_void,
            source_slice.as_ptr() as *const c_void,
            source_slice.len(),
        );
    }
}

/// Performs a lookup transformation (LUT), mapping contents of a buffer into the same or other
/// memory region, taking a byte substitution value from the provided table.
///
/// # Arguments
///
/// * `target`: A mutable buffer to populate.
/// * `source`: An immutable buffer to map from.
/// * `table`: Lookup table of 256 substitution values.
///
/// # Examples
///
/// To convert uppercase ASCII characters to lowercase:
///
/// ```
/// use stringzilla::stringzilla as sz;
/// let mut to_lower: [u8; 256] = core::array::from_fn(|i| i as u8);
/// for (upper, lower) in ('A'..='Z').zip('a'..='z') {
///     to_lower[upper as usize] = lower as u8;
/// }
/// let source = "HELLO WORLD!";
/// let mut target = vec![0u8; source.len()];
/// sz::lookup(&mut target, &source, to_lower);
/// let result = String::from_utf8(target).expect("Invalid UTF-8 sequence");
/// assert_eq!(result, "hello world!");
/// ```
///
pub fn lookup<Target, Source>(target: &mut Target, source: &Source, table: [u8; 256])
where
    Target: AsMut<[u8]> + ?Sized,
    Source: AsRef<[u8]> + ?Sized,
{
    let target_slice = target.as_mut();
    let source_slice = source.as_ref();
    assert!(
        target_slice.len() >= source_slice.len(),
        "target must be at least as long as source"
    );
    unsafe {
        sz_lookup(
            target_slice.as_mut_ptr() as *mut c_void,
            source_slice.len(),
            source_slice.as_ptr() as *const c_void,
            table.as_ptr() as _,
        );
    }
}

/// Performs a lookup transformation (LUT), mapping contents of a buffer into the same or other
/// memory region, taking a byte substitution value from the provided table.
///
/// # Arguments
///
/// * `buffer`: A mutable buffer to update inplace.
/// * `table`: Lookup table of 256 substitution values.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
/// let mut to_lower: [u8; 256] = core::array::from_fn(|i| i as u8);
/// for (upper, lower) in ('A'..='Z').zip('a'..='z') {
///     to_lower[upper as usize] = lower as u8;
/// }
/// let mut text = *b"HELLO WORLD!";
/// sz::lookup_inplace(&mut text, to_lower);
/// assert_eq!(text, *b"hello world!");
/// ```
///
pub fn lookup_inplace<Buffer>(buffer: &mut Buffer, table: [u8; 256])
where
    Buffer: AsMut<[u8]> + ?Sized,
{
    let buffer_slice = buffer.as_mut();
    unsafe {
        sz_lookup(
            buffer_slice.as_mut_ptr() as *mut c_void,
            buffer_slice.len(),
            buffer_slice.as_ptr() as *const c_void,
            table.as_ptr() as _,
        );
    }
}

/// Applies Unicode case folding to a UTF-8 string, writing the result to a destination buffer.
///
/// Case folding normalizes text for uncased comparisons by mapping uppercase letters
/// to their lowercase equivalents and handling special cases like German U+00DF -> ss expansion.
///
/// # Arguments
///
/// * `source`: The UTF-8 string to case-fold.
/// * `destination`: The destination buffer to write the case-folded string.
///
/// # Returns
///
/// Returns the number of bytes written to the destination buffer.
///
/// # Safety
///
/// The caller must ensure the destination buffer is large enough.
/// Use `source.len() * 3` bytes for worst-case 3:1 expansion ratio.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
/// let source = "HELLO WORLD";
/// let mut dest = [0u8; 32];
/// let len = sz::utf8_uncased_fold(source, &mut dest);
/// assert_eq!(&dest[..len], b"hello world");
/// ```
///
pub fn utf8_uncased_fold<Source, Destination>(source: Source, destination: &mut Destination) -> usize
where
    Source: AsRef<[u8]>,
    Destination: AsMut<[u8]> + ?Sized,
{
    let source_ref = source.as_ref();
    let dest_slice = destination.as_mut();

    unsafe {
        sz_utf8_uncased_fold(
            source_ref.as_ptr() as *const c_void,
            source_ref.len(),
            dest_slice.as_mut_ptr() as *mut c_void,
        )
    }
}

/// Normalizes a UTF-8 string to the requested Unicode Normal Form, writing the result to a
/// destination buffer.
///
/// Covers all four standard forms: NFD, NFC, NFKD, and NFKC. NFC is the most common form on
/// the web; NFD is useful for collation. Compatibility forms (NFKD/NFKC) additionally decompose
/// ligatures and compatibility characters (e.g., U+FB03 ffi → "ffi").
///
/// # Arguments
///
/// * `source`: The UTF-8 string to normalize.
/// * `form`: The target Unicode normalization form.
/// * `destination`: The destination buffer to write the normalized string.
///
/// # Returns
///
/// Returns the number of bytes written to the destination buffer.
///
/// # Safety
///
/// The caller must ensure the destination buffer is large enough.
/// Use `source.len() * 18` bytes for worst-case expansion (canonical decomposition).
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
/// use sz::Utf8NormalForm;
/// let source = "caf\u{00E9}"; // "café" NFC (precomposed é)
/// let mut dest = vec![0u8; source.len() * 18];
/// let len = sz::utf8_norm(source, Utf8NormalForm::Nfc, &mut dest);
/// assert_eq!(&dest[..len], "caf\u{00E9}".as_bytes()); // unchanged — already NFC
/// ```
///
pub fn utf8_norm<Source, Destination>(source: Source, form: Utf8NormalForm, destination: &mut Destination) -> usize
where
    Source: AsRef<[u8]>,
    Destination: AsMut<[u8]> + ?Sized,
{
    let source_ref = source.as_ref();
    let dest_slice = destination.as_mut();

    unsafe {
        sz_utf8_norm(
            source_ref.as_ptr() as *const c_void,
            source_ref.len(),
            form as i32,
            dest_slice.as_mut_ptr() as *mut c_void,
        )
    }
}

/// Returns the byte offset of the first byte in `source` that violates the given Unicode Normal
/// Form, or `None` if `source` is already in the requested form.
///
/// This is a fast check — it does not produce the normalized output. Use it to avoid an
/// unnecessary [`utf8_norm`] call when the input is likely already normalized.
///
/// # Arguments
///
/// * `source`: The UTF-8 string to inspect.
/// * `form`: The normalization form to check against.
///
/// # Returns
///
/// * `None` if `source` already conforms to `form`.
/// * `Some(offset)` with the byte offset of the first offending byte otherwise.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
/// use sz::Utf8NormalForm;
/// // NFD string (decomposed): base 'e' + combining acute U+0301
/// let nfd = "cafe\u{0301}";
/// assert!(sz::utf8_find_denormalized(nfd, Utf8NormalForm::Nfc).is_some());
/// assert!(sz::utf8_find_denormalized("café", Utf8NormalForm::Nfc).is_none());
/// ```
///
pub fn utf8_find_denormalized<Source>(source: Source, form: Utf8NormalForm) -> Option<usize>
where
    Source: AsRef<[u8]>,
{
    let source_ref = source.as_ref();
    let ptr = unsafe { sz_utf8_find_denormalized(source_ref.as_ptr() as *const c_void, source_ref.len(), form as i32) };
    if ptr.is_null() {
        None
    } else {
        let offset = unsafe { (ptr as *const u8).offset_from(source_ref.as_ptr()) } as usize;
        Some(offset)
    }
}

/// Performs uncased search for `needle` in UTF-8 `haystack`.
///
/// Unlike ASCII uncased search, this handles Unicode case folding
/// (e.g., German ß matches "ss", Turkish İ matches "i").
///
/// # Arguments
///
/// * `haystack`: The UTF-8 text to search in.
/// * `needle`: The UTF-8 pattern to search for.
///
/// # Returns
///
/// If found, returns `Some((offset, matched_length))` where:
/// - `offset` is the byte position in haystack where the match starts
/// - `matched_length` is the number of bytes matched in haystack (may differ from needle length)
///
/// Returns `None` if no match is found.
///
/// # Examples
///
/// Basic usage with string slices:
///
/// ```
/// use stringzilla::stringzilla as sz;
/// let haystack = "Hello WORLD";
/// if let Some((offset, len)) = sz::utf8_uncased_search(haystack, "world") {
///     assert_eq!(offset, 6);
///     assert_eq!(len, 5);
/// }
/// ```
///
/// With a pre-compiled needle for repeated searches:
///
/// ```
/// use stringzilla::stringzilla::{utf8_uncased_search, Utf8UncasedNeedle};
///
/// let needle = Utf8UncasedNeedle::new(b"hello");
///
/// // Metadata is computed once, reused for subsequent searches
/// let result1 = utf8_uncased_search(b"Hello World", &needle);
/// let result2 = utf8_uncased_search(b"HELLO there", &needle);
///
/// assert_eq!(result1, Some((0, 5)));
/// assert_eq!(result2, Some((0, 5)));
/// ```
///
pub fn utf8_uncased_search<Haystack, Needle>(haystack: Haystack, needle: Needle) -> Option<(usize, usize)>
where
    Haystack: AsRef<[u8]>,
    Needle: Utf8UncasedNeedleArg,
{
    needle.find_uncased_in(haystack.as_ref())
}

/// Trait for types that can be used as a uncased search needle.
///
/// This trait is implemented for:
/// - Any type implementing `AsRef<[u8]>` (strings, byte slices, etc.)
/// - [`Utf8UncasedNeedle`] references for efficient repeated searches
pub trait Utf8UncasedNeedleArg {
    /// Performs the uncased search in the given haystack.
    fn find_uncased_in(self, haystack: &[u8]) -> Option<(usize, usize)>;
}

impl<Source: AsRef<[u8]>> Utf8UncasedNeedleArg for Source {
    fn find_uncased_in(self, haystack: &[u8]) -> Option<(usize, usize)> {
        let needle_ref = self.as_ref();
        let mut matched_length: usize = 0;
        let mut needle_metadata = Utf8UncasedNeedleMetadata::default();

        let result = unsafe {
            sz_utf8_uncased_search(
                haystack.as_ptr() as *const c_void,
                haystack.len(),
                needle_ref.as_ptr() as *const c_void,
                needle_ref.len(),
                &mut needle_metadata,
                &mut matched_length,
            )
        };

        if result.is_null() {
            None
        } else {
            let offset = unsafe { result.offset_from(haystack.as_ptr() as *const c_void) };
            Some((offset as usize, matched_length))
        }
    }
}

impl<'a, 'b> Utf8UncasedNeedleArg for &'b Utf8UncasedNeedle<'a> {
    fn find_uncased_in(self, haystack: &[u8]) -> Option<(usize, usize)> {
        let needle_bytes = self.as_bytes();
        let mut matched_length: usize = 0;

        let result = unsafe {
            sz_utf8_uncased_search(
                haystack.as_ptr() as *const c_void,
                haystack.len(),
                needle_bytes.as_ptr() as *const c_void,
                needle_bytes.len(),
                &mut *self.metadata_ptr(),
                &mut matched_length,
            )
        };

        if result.is_null() {
            None
        } else {
            let offset = unsafe { result.offset_from(haystack.as_ptr() as *const c_void) };
            Some((offset as usize, matched_length))
        }
    }
}

/// Compares two UTF-8 strings in uncased manner.
///
/// Uses Unicode case folding for comparison, handling characters like
/// German ß, Turkish İ/ı, and other case variants.
///
/// # Arguments
///
/// * `first`: First UTF-8 string.
/// * `second`: Second UTF-8 string.
///
/// # Returns
///
/// * `Ordering::Less` if `first < second`
/// * `Ordering::Equal` if `first == second` (uncasedly)
/// * `Ordering::Greater` if `first > second`
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
/// use std::cmp::Ordering;
/// assert_eq!(sz::utf8_uncased_order("Hello", "HELLO"), Ordering::Equal);
/// assert_eq!(sz::utf8_uncased_order("abc", "ABD"), Ordering::Less);
/// ```
///
pub fn utf8_uncased_order<First, Second>(first: First, second: Second) -> Ordering
where
    First: AsRef<[u8]>,
    Second: AsRef<[u8]>,
{
    let first_ref = first.as_ref();
    let second_ref = second.as_ref();

    let result = unsafe {
        sz_utf8_uncased_order(
            first_ref.as_ptr() as *const c_void,
            first_ref.len(),
            second_ref.as_ptr() as *const c_void,
            second_ref.len(),
        )
    };

    match result {
        x if x < 0 => Ordering::Less,
        0 => Ordering::Equal,
        _ => Ordering::Greater,
    }
}

/// Lexicographic (byte-order) comparison of two strings, SIMD-accelerated.
///
/// Mirrors `Ord` on `&[u8]` but uses StringZilla's vectorized `sz_order`.
///
/// # Examples
///
/// ```
/// use std::cmp::Ordering;
/// use stringzilla::stringzilla as sz;
///
/// assert_eq!(sz::order("apple", "banana"), Ordering::Less);
/// assert_eq!(sz::order("abc", "abc"), Ordering::Equal);
/// ```
pub fn order<First, Second>(first: First, second: Second) -> Ordering
where
    First: AsRef<[u8]>,
    Second: AsRef<[u8]>,
{
    let first_ref = first.as_ref();
    let second_ref = second.as_ref();
    let result = unsafe {
        sz_order(
            first_ref.as_ptr() as *const c_void,
            first_ref.len(),
            second_ref.as_ptr() as *const c_void,
            second_ref.len(),
        )
    };
    match result {
        x if x < 0 => Ordering::Less,
        0 => Ordering::Equal,
        _ => Ordering::Greater,
    }
}

/// Byte-level equality of two strings, SIMD-accelerated via `sz_equal`.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
///
/// assert!(sz::equal("abc", "abc"));
/// assert!(!sz::equal("abc", "abd"));
/// ```
pub fn equal<First, Second>(first: First, second: Second) -> bool
where
    First: AsRef<[u8]>,
    Second: AsRef<[u8]>,
{
    let first_ref = first.as_ref();
    let second_ref = second.as_ref();
    // `sz_equal` assumes equal lengths; differing lengths can never be byte-equal.
    first_ref.len() == second_ref.len()
        && unsafe {
            sz_equal(
                first_ref.as_ptr() as *const c_void,
                second_ref.as_ptr() as *const c_void,
                first_ref.len(),
            ) != 0
        }
}

/// Unpacks a UTF-8 byte sequence into UTF-32 codepoints.
///
/// This function decodes UTF-8 encoded text into individual Unicode codepoints, storing them in a u32 array.
/// It fills the output buffer (or drains the input) in a single call, looping internally regardless of how many
/// byte-widths the text mixes. Ill-formed bytes decode to the replacement character U+FFFD (one per maximal
/// ill-formed subpart), so every written value is a valid Unicode scalar value; a well-formed but truncated
/// trailing sequence is left unconsumed so a streaming caller can resume once more bytes arrive.
///
/// # Arguments
///
/// * `text`: The UTF-8 encoded byte slice to decode.
/// * `runes`: Output buffer to store decoded codepoints.
///
/// # Returns
///
/// A tuple `(bytes_consumed, runes_unpacked)` where:
/// - `bytes_consumed` is the number of bytes processed from `text`
/// - `runes_unpacked` is the number of codepoints written to `runes`
///
/// # Examples
///
/// Processing pure ASCII text (most common case, single chunk):
/// ```
/// use stringzilla::stringzilla as sz;
/// let text = "Hello World!";
/// let mut runes = [0u32; 16];
/// let (bytes, count) = sz::utf8_decode(text.as_bytes(), &mut runes);
/// assert_eq!(count, 12);  // All 12 ASCII characters
/// assert_eq!(bytes, 12);  // 12 bytes consumed
/// assert_eq!(runes[0], 'H' as u32);
/// assert_eq!(runes[11], '!' as u32);
/// ```
///
/// Each call fills the output buffer or drains the input; call repeatedly (resuming at `bytes_consumed`)
/// to process a string longer than the buffer:
/// ```
/// use stringzilla::stringzilla as sz;
/// let text = "Hi世界";  // 2 ASCII + 2 CJK
/// let bytes = text.as_bytes();
/// let mut runes = [0u32; 16];
/// let mut all_runes = Vec::new();
/// let mut offset = 0;
/// while offset < bytes.len() {
///     let (consumed, count) = sz::utf8_decode(&bytes[offset..], &mut runes);
///     all_runes.extend_from_slice(&runes[..count]);
///     offset += consumed;
/// }
/// assert_eq!(all_runes.len(), 4);  // 2 ASCII + 2 CJK = 4 codepoints
/// ```
///
pub fn utf8_decode(text: &[u8], runes: &mut [u32]) -> (usize, usize) {
    let mut runes_unpacked: usize = 0;

    let result = unsafe {
        sz_utf8_decode(
            text.as_ptr() as *const c_void,
            text.len(),
            runes.as_mut_ptr(),
            runes.len(),
            &mut runes_unpacked,
        )
    };

    let bytes_consumed = if result.is_null() {
        0
    } else {
        unsafe { result.offset_from(text.as_ptr() as *const c_void) as usize }
    };

    (bytes_consumed, runes_unpacked)
}

/// Computes a 64-bit AES-based hash value for a given byte slice `text`.
/// This function is designed to provide a high-quality hash value for use in
/// hash tables, data structures, and cryptographic applications.
/// Unlike the bytesum function, the hash function is order-sensitive.
///
/// # Arguments
///
/// * `text`: The byte slice to compute the checksum for.
/// * `seed`: A 64-bit value that acts as the seed for the hash function.
///
/// # Returns
///
/// A `u64` representing the hash value of the input byte slice.
#[inline(always)]
pub fn hash_with_seed<Text>(text: Text, seed: u64) -> u64
where
    Text: AsRef<[u8]>,
{
    let text_ref = text.as_ref();
    let text_pointer = text_ref.as_ptr() as _;
    let text_length = text_ref.len();
    unsafe { sz_hash(text_pointer, text_length, seed) }
}

/// Computes a 64-bit AES-based hash value for a given byte slice `text`.
/// This function is designed to provide a high-quality hash value for use in
/// hash tables, data structures, and cryptographic applications.
/// Unlike the bytesum function, the hash function is order-sensitive.
///
/// # Arguments
///
/// * `text`: The byte slice to compute the checksum for.
///
/// # Returns
///
/// A `u64` representing the hash value of the input byte slice.
#[inline(always)]
pub fn hash<Text>(text: Text) -> u64
where
    Text: AsRef<[u8]>,
{
    hash_with_seed(text, 0)
}

/// Hashes one byte slice under many seeds at once, writing the results into `out`.
/// Equivalent to `out[i] = hash_with_seed(text, seeds[i])`, but normalizes the input into AES
/// blocks once and replays the cheap per-seed rounds - markedly faster for short strings under
/// many seeds (feature hashing, Count-Min sketches, Bloom/cuckoo filters, MinHash/LSH).
///
/// # Arguments
///
/// * `text`: The byte slice to hash.
/// * `seeds`: The 64-bit seeds to hash under.
/// * `out`: The output buffer, filled with one hash per seed. Must be the same length as `seeds`.
///
/// # Panics
///
/// Panics if `out.len() != seeds.len()`.
#[inline(always)]
pub fn hash_multiseed_into<Text>(text: Text, seeds: &[u64], out: &mut [u64])
where
    Text: AsRef<[u8]>,
{
    assert_eq!(seeds.len(), out.len(), "`out` must have one slot per seed");
    let text_ref = text.as_ref();
    unsafe {
        sz_hash_multiseed(
            text_ref.as_ptr() as _,
            text_ref.len(),
            seeds.as_ptr(),
            seeds.len(),
            out.as_mut_ptr(),
        )
    }
}

/// Locates the first matching substring within `haystack` that equals `needle`.
/// This function is similar to the `memmem()` function in LibC, but, unlike `strstr()`,
/// it requires the length of both haystack and needle to be known beforehand.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needle`: The byte slice to find within the haystack.
///
/// # Returns
///
/// An `Option<usize>` representing the starting index of the first occurrence of `needle`
/// within `haystack` if found, otherwise `None`.
///
/// # Empty needle
///
/// The C core returns the start of `haystack` for an empty needle, like `strstr`, so
/// `find(haystack, b"")` is always `Some(0)`, matching `"abc".find("") == Some(0)`. This holds even
/// for an empty `haystack`.
pub fn find<Haystack, Needle>(haystack: Haystack, needle: Needle) -> Option<usize>
where
    Haystack: AsRef<[u8]>,
    Needle: AsRef<[u8]>,
{
    let haystack_ref = haystack.as_ref();
    let needle_ref = needle.as_ref();
    let haystack_pointer = haystack_ref.as_ptr() as _;
    let haystack_length = haystack_ref.len();
    let needle_pointer = needle_ref.as_ptr() as _;
    let needle_length = needle_ref.len();
    let result = unsafe { sz_find(haystack_pointer, haystack_length, needle_pointer, needle_length) };

    if result.is_null() {
        None
    } else {
        Some(unsafe { result.offset_from(haystack_pointer) }.try_into().unwrap())
    }
}

/// Locates the last matching substring within `haystack` that equals `needle`.
/// This function is useful for finding the most recent or last occurrence of a pattern
/// within a byte slice.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needle`: The byte slice to find within the haystack.
///
/// # Returns
///
/// An `Option<usize>` representing the starting index of the last occurrence of `needle`
/// within `haystack` if found, otherwise `None`.
///
/// # Empty needle
///
/// The C core returns the end of `haystack` for an empty needle, the reverse mirror of `strstr`, so
/// `rfind(haystack, b"")` is always `Some(haystack.len())`, matching `"abc".rfind("") == Some(3)`.
/// This holds even for an empty `haystack`.
#[inline(always)]
pub fn rfind<Haystack, Needle>(haystack: Haystack, needle: Needle) -> Option<usize>
where
    Haystack: AsRef<[u8]>,
    Needle: AsRef<[u8]>,
{
    let haystack_ref = haystack.as_ref();
    let needle_ref = needle.as_ref();
    let haystack_pointer = haystack_ref.as_ptr() as _;
    let haystack_length = haystack_ref.len();
    let needle_pointer = needle_ref.as_ptr() as _;
    let needle_length = needle_ref.len();
    let result = unsafe { sz_rfind(haystack_pointer, haystack_length, needle_pointer, needle_length) };

    if result.is_null() {
        None
    } else {
        Some(unsafe { result.offset_from(haystack_pointer) }.try_into().unwrap())
    }
}

/// Checks whether `needle` occurs anywhere within `haystack`.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needle`: The byte slice to look for within the haystack.
///
/// # Returns
///
/// `true` if `needle` occurs within `haystack`, `false` otherwise.
///
/// # Empty needle
///
/// Mirrors `str::contains`: an empty needle is always present, so `contains(haystack, b"")` is
/// always `true`, matching `"abc".contains("") == true` (even for an empty `haystack`).
#[inline(always)]
pub fn contains<Haystack, Needle>(haystack: Haystack, needle: Needle) -> bool
where
    Haystack: AsRef<[u8]>,
    Needle: AsRef<[u8]>,
{
    find(haystack, needle).is_some()
}

/// Finds the index of the first character in `haystack` that is also present in `needles`.
/// This function is particularly useful for parsing and tokenization tasks where a set of
/// delimiter characters is used.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needles`: The set of bytes to search for within the haystack.
///
/// # Returns
///
/// An `Option<usize>` representing the index of the first occurrence of any byte from
/// `needles` within `haystack`, if found, otherwise `None`.
#[inline(always)]
pub fn find_byteset<Haystack>(haystack: Haystack, needles: Byteset) -> Option<usize>
where
    Haystack: AsRef<[u8]>,
{
    let haystack_ref = haystack.as_ref();
    let haystack_pointer = haystack_ref.as_ptr() as _;
    let haystack_length = haystack_ref.len();

    let result = unsafe { sz_find_byteset(haystack_pointer, haystack_length, &needles as *const _ as *const c_void) };
    if result.is_null() {
        None
    } else {
        Some(unsafe { result.offset_from(haystack_pointer) }.try_into().unwrap())
    }
}

/// Finds the index of the last character in `haystack` that is also present in `needles`.
/// This can be used to find the last occurrence of any character from a specified set,
/// useful in parsing scenarios such as finding the last delimiter in a string.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needles`: The set of bytes to search for within the haystack.
///
/// # Returns
///
/// An `Option<usize>` representing the index of the last occurrence of any byte from
/// `needles` within `haystack`, if found, otherwise `None`.
pub fn rfind_byteset<Haystack>(haystack: Haystack, needles: Byteset) -> Option<usize>
where
    Haystack: AsRef<[u8]>,
{
    let haystack_ref = haystack.as_ref();
    let haystack_pointer = haystack_ref.as_ptr() as _;
    let haystack_length = haystack_ref.len();

    let result = unsafe { sz_rfind_byteset(haystack_pointer, haystack_length, &needles as *const _ as *const c_void) };
    if result.is_null() {
        None
    } else {
        Some(unsafe { result.offset_from(haystack_pointer) }.try_into().unwrap())
    }
}

/// Finds the index of the first character in `haystack` that is also present in `needles`.
/// This function is particularly useful for parsing and tokenization tasks where a set of
/// delimiter characters is used.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needles`: The set of bytes to search for within the haystack.
///
/// # Returns
///
/// An `Option<usize>` representing the index of the first occurrence of any byte from
/// `needles` within `haystack`, if found, otherwise `None`.
#[inline(always)]
pub fn find_byte_from<Haystack, Needle>(haystack: Haystack, needles: Needle) -> Option<usize>
where
    Haystack: AsRef<[u8]>,
    Needle: AsRef<[u8]>,
{
    find_byteset(haystack, Byteset::from(needles))
}

/// Finds the index of the last character in `haystack` that is also present in `needles`.
/// This can be used to find the last occurrence of any character from a specified set,
/// useful in parsing scenarios such as finding the last delimiter in a string.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needles`: The set of bytes to search for within the haystack.
///
/// # Returns
///
/// An `Option<usize>` representing the index of the last occurrence of any byte from
/// `needles` within `haystack`, if found, otherwise `None`.
pub fn rfind_byte_from<Haystack, Needle>(haystack: Haystack, needles: Needle) -> Option<usize>
where
    Haystack: AsRef<[u8]>,
    Needle: AsRef<[u8]>,
{
    rfind_byteset(haystack, Byteset::from(needles))
}

/// Finds the index of the first character in `haystack` that is not present in `needles`.
/// This function is useful for skipping over a known set of characters and finding the
/// first character that does not belong to that set.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needles`: The set of bytes that should not be matched within the haystack.
///
/// # Returns
///
/// An `Option<usize>` representing the index of the first occurrence of any byte not in
/// `needles` within `haystack`, if found, otherwise `None`.
pub fn find_byte_not_from<Haystack, Needle>(haystack: Haystack, needles: Needle) -> Option<usize>
where
    Haystack: AsRef<[u8]>,
    Needle: AsRef<[u8]>,
{
    find_byteset(haystack, Byteset::from(needles).inverted())
}

/// Finds the index of the last character in `haystack` that is not present in `needles`.
/// Useful for text processing tasks such as trimming trailing characters that belong to
/// a specified set.
///
/// # Arguments
///
/// * `haystack`: The byte slice to search.
/// * `needles`: The set of bytes that should not be matched within the haystack.
///
/// # Returns
///
/// An `Option<usize>` representing the index of the last occurrence of any byte not in
/// `needles` within `haystack`, if found, otherwise `None`.
pub fn rfind_byte_not_from<Haystack, Needle>(haystack: Haystack, needles: Needle) -> Option<usize>
where
    Haystack: AsRef<[u8]>,
    Needle: AsRef<[u8]>,
{
    rfind_byteset(haystack, Byteset::from(needles).inverted())
}

#[cfg(feature = "std")]
fn replace_all_with_finder<FindNext, FindPrev>(
    buffer: &mut Vec<u8>,
    needle_length: usize,
    replacement: &[u8],
    mut find_next: FindNext,
    mut find_prev: FindPrev,
) -> Result<usize, Status>
where
    FindNext: FnMut(&[u8], usize) -> Option<usize>,
    FindPrev: FnMut(&[u8], usize) -> Option<usize>,
{
    if needle_length == 0 || buffer.is_empty() {
        return Ok(0);
    }

    // Case 1: needle and replacement are the same length – overwrite each match in place.
    if needle_length == replacement.len() {
        let mut replaced = 0;
        let mut search_from = 0;
        while let Some(pos) = find_next(buffer.as_slice(), search_from) {
            copy(&mut buffer[pos..pos + needle_length], &replacement);
            search_from = pos + needle_length;
            replaced += 1;
        }
        return Ok(replaced);
    }

    // Case 2: replacement is shorter – compact forward to minimize memmoves and avoid allocations.
    if needle_length > replacement.len() {
        let mut replaced = 0;
        let mut read = 0;
        let mut write = 0;
        let len = buffer.len();

        while let Some(pos) = find_next(buffer.as_slice(), read) {
            if pos > read {
                let chunk = pos - read;
                unsafe {
                    sz_move(
                        buffer.as_mut_ptr().add(write) as *const c_void,
                        buffer.as_ptr().add(read) as *const c_void,
                        chunk,
                    );
                }
                write += chunk;
            }
            copy(&mut buffer[write..write + replacement.len()], replacement);
            write += replacement.len();
            read = pos + needle_length;
            replaced += 1;
        }

        if read < len {
            let chunk = len - read;
            unsafe {
                sz_move(
                    buffer.as_mut_ptr().add(write) as *const c_void,
                    buffer.as_ptr().add(read) as *const c_void,
                    chunk,
                );
            }
            write += len - read;
        }
        buffer.truncate(write);
        return Ok(replaced);
    }

    // Case 3: replacement is longer – collect match positions once, resize once, then rewrite from the back.
    let mut match_count = 0usize;
    let mut search_from = 0;
    while let Some(pos) = find_next(buffer.as_slice(), search_from) {
        match_count += 1;
        search_from = pos + needle_length;
    }

    if match_count == 0 {
        return Ok(0);
    }

    let original_len = buffer.len();
    let delta = replacement.len() - needle_length;
    let added = match match_count.checked_mul(delta) {
        Some(v) => v,
        None => return Err(Status::OverflowRisk),
    };
    let new_len = match original_len.checked_add(added) {
        Some(v) => v,
        None => return Err(Status::OverflowRisk),
    };
    if let Err(_) = buffer.try_reserve_exact(added) {
        return Err(Status::BadAlloc);
    }
    buffer.resize(new_len, 0);

    let mut read_end = original_len;
    let mut write_end = new_len;

    while let Some(pos) = find_prev(buffer.as_slice(), read_end) {
        let match_end = pos + needle_length;
        let tail_len = read_end - match_end;
        if tail_len > 0 {
            unsafe {
                sz_move(
                    buffer.as_mut_ptr().add(write_end - tail_len) as *const c_void,
                    buffer.as_ptr().add(match_end) as *const c_void,
                    tail_len,
                );
            }
        }
        write_end -= tail_len;
        write_end -= replacement.len();
        copy(&mut buffer[write_end..write_end + replacement.len()], replacement);
        read_end = pos;
    }

    debug_assert_eq!(write_end, read_end, "replace_all backfill mismatch");
    Ok(match_count)
}

/// Tries to replace all non-overlapping occurrences of `needle` inside `buffer` in place.
///
/// The algorithm mirrors the C++ `replace_all` logic:
/// - equal-length replacements simply overwrite matches,
/// - shorter replacements compact forward without allocating,
/// - longer replacements count matches once, resize once, and rewrite from the back.
///
/// Returns the number of replacements performed.
#[cfg(feature = "std")]
pub fn try_replace_all(buffer: &mut Vec<u8>, needle: &[u8], replacement: &[u8]) -> Result<usize, Status> {
    replace_all_with_finder(
        buffer,
        needle.len(),
        replacement,
        |haystack, start| {
            if start >= haystack.len() {
                None
            } else {
                find(&haystack[start..], needle).map(|offset| start + offset)
            }
        },
        |haystack, end| {
            if end == 0 {
                None
            } else {
                rfind(&haystack[..end], needle)
            }
        },
    )
}

/// Tries to replace all non-overlapping bytes in `buffer` that belong to `byteset` with `replacement`.
///
/// Uses the same three-way strategy as [`try_replace_all`]. If the byteset is empty, the buffer is
/// left untouched. Returns the number of replacements performed.
#[cfg(feature = "std")]
pub fn try_replace_all_byteset(buffer: &mut Vec<u8>, byteset: Byteset, replacement: &[u8]) -> Result<usize, Status> {
    if byteset.bits.iter().all(|&b| b == 0) {
        return Ok(0);
    }

    replace_all_with_finder(
        buffer,
        1,
        replacement,
        |haystack, start| {
            if start >= haystack.len() {
                None
            } else {
                find_byteset(&haystack[start..], byteset).map(|offset| start + offset)
            }
        },
        |haystack, end| {
            if end == 0 {
                None
            } else {
                rfind_byteset(&haystack[..end], byteset)
            }
        },
    )
}

/// Counts the number of UTF-8 characters in the text.
///
/// This function efficiently counts UTF-8 characters by identifying character start bytes
/// (non-continuation bytes). Uses SIMD acceleration when available.
///
/// # Arguments
///
/// * `text`: The UTF-8 encoded byte slice to count characters in.
///
/// # Returns
///
/// The number of UTF-8 characters (codepoints) in the text.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
///
/// let text = "Hello";
/// assert_eq!(sz::count_utf8(text), 5);
///
/// let text_unicode = "Hello🌍";
/// assert_eq!(sz::count_utf8(text_unicode), 6);
///
/// let text_cjk = "你好世界";
/// assert_eq!(sz::count_utf8(text_cjk), 4);
/// ```
pub fn count_utf8<Text>(text: Text) -> usize
where
    Text: AsRef<[u8]>,
{
    let text_ref = text.as_ref();
    let text_pointer = text_ref.as_ptr() as *const c_void;
    let text_length = text_ref.len();

    unsafe { sz_utf8_count(text_pointer, text_length) }
}

/// Finds the byte offset of the Nth UTF-8 character (0-indexed).
///
/// This function efficiently locates the Nth UTF-8 character without decoding
/// the entire string. Uses SIMD acceleration when available.
///
/// # Arguments
///
/// * `text`: The UTF-8 encoded byte slice to search.
/// * `n`: The 0-based index of the character to find.
///
/// # Returns
///
/// An `Option<usize>` containing the byte offset of the Nth character.
/// Returns `None` if the string has fewer than N+1 characters.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
///
/// let text = "Hello";
/// assert_eq!(sz::find_nth_utf8(text, 0), Some(0)); // 'H'
/// assert_eq!(sz::find_nth_utf8(text, 4), Some(4)); // 'o'
/// assert_eq!(sz::find_nth_utf8(text, 5), None);
///
/// let text_unicode = "Hello🌍";
/// assert_eq!(sz::find_nth_utf8(text_unicode, 5), Some(5)); // 🌍 starts at byte 5
/// assert_eq!(sz::find_nth_utf8(text_unicode, 6), None);
/// ```
pub fn find_nth_utf8<Text>(text: Text, n: usize) -> Option<usize>
where
    Text: AsRef<[u8]>,
{
    let text_ref = text.as_ref();
    let text_pointer = text_ref.as_ptr() as *const c_void;
    let text_length = text_ref.len();

    let result = unsafe { sz_utf8_seek(text_pointer, text_length, n) };

    if result.is_null() {
        None
    } else {
        let offset = unsafe { (result as *const u8).offset_from(text_pointer as *const u8) }
            .try_into()
            .unwrap();
        Some(offset)
    }
}

/// Lazy UTF-8 character view with SIMD-accelerated operations.
///
/// Provides O(1) construction with lazy character counting and efficient random access.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
///
/// let text = "Hello🌍";
/// let view = sz::Utf8View::new(text.as_bytes());
///
/// // Lazy character count (computed once, then cached)
/// assert_eq!(view.len(), 6);
///
/// // Random access to byte offset of Nth character
/// assert_eq!(view.offset_of(5), Some(5)); // 🌍 at byte 5
///
/// // Iterate over characters
/// let chars: Vec<char> = view.iter().collect();
/// assert_eq!(chars, vec!['H', 'e', 'l', 'l', 'o', '🌍']);
/// ```
pub struct Utf8View<'a> {
    octets: &'a [u8],
    cached_len: core::cell::Cell<Option<usize>>,
}

impl<'a> Utf8View<'a> {
    /// Creates a new UTF-8 view (O(1) - no scanning).
    pub const fn new(octets: &'a [u8]) -> Self {
        Self {
            octets,
            cached_len: core::cell::Cell::new(None),
        }
    }

    /// Returns the number of UTF-8 characters (lazy evaluation, cached after first call).
    pub fn len(&self) -> usize {
        if let Some(len) = self.cached_len.get() {
            return len;
        }
        let len = count_utf8(self.octets);
        self.cached_len.set(Some(len));
        len
    }

    /// Checks if the view is empty.
    pub const fn is_empty(&self) -> bool {
        self.octets.is_empty()
    }

    /// Gets the byte offset of the Nth character (0-indexed, SIMD-accelerated).
    pub fn offset_of(&self, n: usize) -> Option<usize> {
        find_nth_utf8(self.octets, n)
    }

    /// Returns an iterator over UTF-8 characters.
    pub fn iter(&self) -> Utf8Runes<'a> {
        Utf8Runes::new(self.octets)
    }
}

/// Iterator over UTF-8 characters using batched decoding.
///
/// Each refill decodes up to `STEPS` codepoints in a single `sz_utf8_decode` FFI call (the decoder fills
/// the whole buffer regardless of script width), then yields them one at a time - far cheaper than decoding
/// character-by-character. Ill-formed bytes decode to the replacement character U+FFFD, so iteration is total
/// and never silently truncates.
///
/// Typically created through [`Utf8View::iter()`].
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
///
/// let text = "Hello🌍";
/// let view = sz::Utf8View::new(text.as_bytes());
/// let chars: Vec<char> = view.iter().collect();
/// assert_eq!(chars, vec!['H', 'e', 'l', 'l', 'o', '🌍']);
/// ```
pub struct Utf8Runes<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> {
    octets: &'a [u8],
    octets_offset: usize,
    runes: [u32; STEPS], // Buffered codepoints decoded from the current chunk
    runes_count: usize,  // Number of buffered codepoints (0 once exhausted)
    runes_offset: usize, // Index of the next codepoint to yield from the buffer
}

impl<'a> Utf8Runes<'a, ITERATORS_DEFAULT_STEPS> {
    /// Constructs an iterator with the default batch size ([`ITERATORS_DEFAULT_STEPS`]).
    /// For an explicit batch size use [`Self::with_steps`] with a turbofish, e.g.
    /// `Utf8Runes::<256>::with_steps(octets)`.
    fn new(octets: &'a [u8]) -> Self {
        Self::with_steps(octets)
    }
}

impl<'a, const STEPS: usize> Utf8Runes<'a, STEPS> {
    /// Constructs an iterator buffering up to `STEPS` codepoints per FFI call.
    pub fn with_steps(octets: &'a [u8]) -> Self {
        let mut iter = Self {
            octets,
            octets_offset: 0,
            runes: [0; STEPS],
            runes_count: 0,
            runes_offset: 0,
        };
        iter.decode_batch();
        iter
    }

    /// Decodes the next chunk of UTF-8 bytes into the runes buffer; `runes_count` becomes 0 once drained.
    fn decode_batch(&mut self) {
        if self.octets_offset >= self.octets.len() {
            self.runes_count = 0;
            return;
        }

        let octets_ptr = unsafe { self.octets.as_ptr().add(self.octets_offset) as *const c_void };
        let mut unpacked_count: usize = 0;
        let next_ptr = unsafe {
            sz_utf8_decode(
                octets_ptr,
                self.octets.len() - self.octets_offset,
                self.runes.as_mut_ptr(),
                STEPS,
                &mut unpacked_count as *mut usize,
            )
        };

        let bytes_consumed: usize = unsafe {
            let offset = (next_ptr as *const u8).offset_from(octets_ptr as *const u8);
            debug_assert!(offset >= 0, "sz_utf8_decode returned a pointer before the input");
            offset.try_into().expect("offset should be non-negative")
        };
        self.octets_offset += bytes_consumed;
        self.runes_offset = 0;

        // The decoder stops (yielding nothing) on a well-formed but truncated trailing sequence so a streaming
        // caller can resume. We own the whole slice, so there is nothing more to resume with: finalize that tail
        // as a single U+FFFD (its maximal subpart) instead of silently dropping it, matching `from_utf8_lossy`.
        if unpacked_count == 0 && self.octets_offset < self.octets.len() {
            self.runes[0] = 0xFFFD;
            self.runes_count = 1;
            self.octets_offset = self.octets.len();
        } else {
            self.runes_count = unpacked_count;
        }
    }
}

impl<'a, const STEPS: usize> Iterator for Utf8Runes<'a, STEPS> {
    type Item = char;

    fn next(&mut self) -> Option<char> {
        // If the buffer is drained, decode the next chunk.
        if self.runes_offset >= self.runes_count {
            self.decode_batch();
            if self.runes_count == 0 {
                return None;
            }
        }

        let codepoint = self.runes[self.runes_offset];
        self.runes_offset += 1;
        // Safety: `sz_utf8_decode` only emits valid Unicode scalar values (ill-formed input becomes U+FFFD),
        // so the conversion never sees a surrogate or an out-of-range value - no per-codepoint re-validation needed.
        Some(unsafe { char::from_u32_unchecked(codepoint) })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        // Lower bound: remaining runes in current buffer; upper bound unknown without counting the whole string.
        let lower = self.runes_count.saturating_sub(self.runes_offset);
        (lower, None)
    }
}

/// Randomizes the contents of a given byte slice `text` using characters from
/// a specified `alphabet`. This function mutates `text` in place, replacing each
/// byte with a random one from `alphabet`. It is designed for situations where
/// you need to generate random strings or data sequences based on a specific set
/// of characters, such as generating random DNA sequences or testing inputs.
///
/// # Arguments
///
/// * `buffer`: A mutable reference to the data to randomize. This data will be mutated in place.
/// * `nonce`: A 64-bit "number used once" (nonce) value to seed the random number generator.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla as sz;
/// let mut buffer = vec![0; 10];
/// sz::fill_random(&mut buffer, 42);
/// ```
///
/// After than,  `buffer` is filled with random byte values from 0 to 255.
pub fn fill_random<Buffer>(buffer: &mut Buffer, nonce: u64)
where
    Buffer: AsMut<[u8]> + ?Sized, // Allows for mutable references to dynamically sized types.
{
    let buffer_slice = buffer.as_mut();
    unsafe {
        sz_fill_random(buffer_slice.as_ptr() as _, buffer_slice.len(), nonce);
    }
}

/// Type-punned wrapper for the slice lookup view.
///
/// Carries a mapper closure which, given an index, returns the corresponding byte-slice representation,
/// alongside the monomorphized accessor that recovers the closure's concrete type. Callers write closures
/// like `|i| data[i].as_ref()` or `|i| people[i].name.as_bytes()`.
struct _PunnedSliceLookupView {
    get_slice: unsafe fn(*const c_void, usize) -> &'static [u8],
    data: *const c_void,
}

unsafe extern "C" fn _slice_get_start_punned(handle: *const c_void, idx: SortedIdx) -> *const c_void {
    let view = &*(handle as *const _PunnedSliceLookupView);
    let slice = (view.get_slice)(view.data, idx);
    slice.as_ptr() as *const c_void
}

unsafe extern "C" fn _slice_get_length_punned(handle: *const c_void, idx: SortedIdx) -> usize {
    let view = &*(handle as *const _PunnedSliceLookupView);
    let slice = (view.get_slice)(view.data, idx);
    slice.len()
}

/// Type-specific function generator for each concrete type
unsafe fn _get_slice_fn<Mapper>() -> unsafe fn(*const c_void, usize) -> &'static [u8]
where
    Mapper: Fn(usize) -> &'static [u8],
{
    unsafe fn get_slice_impl<Mapper>(data: *const c_void, idx: usize) -> &'static [u8]
    where
        Mapper: Fn(usize) -> &'static [u8],
    {
        let mapper = &*(data as *const Mapper);
        mapper(idx)
    }
    get_slice_impl::<Mapper>
}

/// Knobs for [`argsort`] and [`argsort_by`].
///
/// The default is a full, ascending, byte-lexicographic, **stable** sort (equal elements keep their
/// input order). Tweak the public fields directly or chain the builder methods:
///
/// ```rust
/// use stringzilla::stringzilla as sz;
///
/// let descending = sz::ArgsortOptions::default().reversed();
/// let top_10_folded = sz::ArgsortOptions { uncased: true, top: Some(10), ..Default::default() };
/// # let _ = (descending, top_10_folded);
/// ```
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct ArgsortOptions {
    /// Sort in descending order; equal elements still keep their input order (stable).
    pub reverse: bool,
    /// Order under Unicode case-folding instead of raw bytes.
    pub uncased: bool,
    /// Only fully order the leading `Some(k)` elements (top-K / partial sort); `None` sorts everything.
    /// The remaining entries of `order` stay a valid - but arbitrary - permutation of the leftover indices.
    pub top: Option<usize>,
}

impl ArgsortOptions {
    /// Sort in descending order.
    pub const fn reversed(mut self) -> Self {
        self.reverse = true;
        self
    }
    /// Order under Unicode case-folding instead of raw bytes.
    pub const fn uncased(mut self) -> Self {
        self.uncased = true;
        self
    }
    /// Only fully order the leading `count` elements (top-K / partial sort).
    pub const fn top(mut self, count: usize) -> Self {
        self.top = Some(count);
        self
    }
}

/// Computes the permutation that sorts `data` by its byte-slice representations.
///
/// The caller supplies an output buffer `order` of length at least `data.len()`; on success the sorted
/// permutation indices are written into its first `data.len()` slots. See [`ArgsortOptions`] for
/// descending, uncased, and top-K variants.
///
/// # Example
///
/// ```rust
/// use stringzilla::stringzilla as sz;
///
/// let fruits = ["banana", "apple", "cherry"];
/// let mut order = [0; 3];
/// sz::argsort(&fruits, &mut order, Default::default()).expect("sort failed");
/// assert_eq!(&order, &[1, 0, 2]); // "apple", "banana", "cherry"
///
/// // Descending, uncased:
/// let labels = ["beta", "Alpha", "BETA"];
/// let mut order = [0; 3];
/// sz::argsort(&labels, &mut order, sz::ArgsortOptions::default().reversed().uncased()).unwrap();
/// assert_eq!(labels[order[0]], "beta"); // "beta"/"BETA" (fold-equal) before "Alpha", stable on ties
/// ```
pub fn argsort<Element: AsRef<[u8]>>(
    data: &[Element],
    order: &mut [SortedIdx],
    options: ArgsortOptions,
) -> Result<(), Status> {
    if data.len() > order.len() {
        return Err(Status::BadAlloc);
    }
    argsort_by(|i| data[i].as_ref(), &mut order[..data.len()], options)
}

/// Computes the permutation that sorts items by a caller-provided byte-slice key.
/// The number of items is inferred from the length of the `order` slice.
///
/// # Example
///
/// ```rust
/// use stringzilla::stringzilla as sz;
///
/// struct Person { name: &'static str, age: u32 }
/// let people = [
///     Person { name: "Charlie", age: 20 },
///     Person { name: "Alice", age: 25 },
///     Person { name: "Bob", age: 30 },
/// ];
/// let mut order = [0; 3];
/// sz::argsort_by(|i| people[i].name.as_bytes(), &mut order, Default::default()).expect("sort failed");
/// assert_eq!(&order, &[1, 2, 0]); // "Alice", "Bob", "Charlie"
/// ```
pub fn argsort_by<Mapper, Key>(mapper: Mapper, order: &mut [SortedIdx], options: ArgsortOptions) -> Result<(), Status>
where
    Mapper: Fn(usize) -> Key,
    Key: AsRef<[u8]>,
{
    // Adapter closure: given an index, call the provided mapper and then transmute the
    // resulting slice to have a `'static` lifetime. This transmute is safe as long as
    // the FFI call is synchronous and the returned slices are only used during the call.
    let adapter = move |i: usize| -> &'static [u8] {
        let binding = mapper(i);
        let slice = binding.as_ref();
        unsafe { core::mem::transmute(slice) }
    };

    _argsort_impl(adapter, order, options)
}

/// Helper that takes an adapter (with a concrete type) and performs the FFI call.
fn _argsort_impl<Adapter>(adapter: Adapter, order: &mut [SortedIdx], options: ArgsortOptions) -> Result<(), Status>
where
    Adapter: Fn(usize) -> &'static [u8],
{
    let wrapper = _PunnedSliceLookupView {
        get_slice: unsafe { _get_slice_fn::<Adapter>() },
        data: &adapter as *const Adapter as *const c_void,
    };
    let seq = _SzSequence {
        handle: &wrapper as *const _ as *const c_void,
        count: order.len(),
        get_start: Some(_slice_get_start_punned),
        get_length: Some(_slice_get_length_punned),
    };
    let top_count = options.top.unwrap_or(0);
    let reverse = options.reverse as i32;
    let status = unsafe {
        if options.uncased {
            sz_sequence_argsort_uncased(&seq, core::ptr::null(), order.as_mut_ptr(), top_count, reverse)
        } else {
            sz_sequence_argsort(&seq, core::ptr::null(), order.as_mut_ptr(), top_count, reverse)
        }
    };
    if status == Status::Success {
        Ok(())
    } else {
        Err(status)
    }
}

// ----------------------------------------------------------------------
// Intersection functions
// ----------------------------------------------------------------------

/// Intersects two sequences (inner join) using their default byte-slice views.
///
/// Both sequences must have an output buffer provided (for first and second positions)
/// whose length is at least the minimum of the two input lengths.
///
/// # Example
///
/// ```rust
/// use stringzilla::stringzilla as sz;
///
/// let set1 = ["banana", "apple", "cherry"];
/// let set2 = ["cherry", "orange", "pineapple", "banana"];
/// let mut positions1 = [0; 3]; // at least min(3, 4) == 3 elements.
/// let mut positions2 = [0; 3];
/// let n = sz::intersection(&set1, &set2, 0, &mut positions1, &mut positions2).expect("intersection failed");
/// assert!(n == 2); // "banana" and "cherry" are common.
/// ```
pub fn intersection<Element: AsRef<[u8]>>(
    data1: &[Element],
    data2: &[Element],
    seed: u64,
    positions1: &mut [SortedIdx],
    positions2: &mut [SortedIdx],
) -> Result<usize, Status> {
    let min_count = data1.len().min(data2.len());
    if positions1.len() < min_count || positions2.len() < min_count {
        return Err(Status::BadAlloc);
    }

    // Call the lower-level implementation with accurate counts for both sequences.
    let adapter1 = move |i: usize| -> &'static [u8] {
        // SAFETY: used only during the FFI call
        unsafe { core::mem::transmute::<&[u8], &'static [u8]>(data1[i].as_ref()) }
    };
    let adapter2 = move |j: usize| -> &'static [u8] {
        // SAFETY: used only during the FFI call
        unsafe { core::mem::transmute::<&[u8], &'static [u8]>(data2[j].as_ref()) }
    };
    _intersection_by_impl(
        adapter1,
        adapter2,
        seed,
        positions1,
        positions2,
        data1.len(),
        data2.len(),
    )
}

/// Intersects two sequences (inner join) using their elements corresponding byte-slice views.
/// The caller must provide a closure that maps an index to the byte slice representation of
/// the corresponding element in the first and second sequences.
///
/// # Example
///
/// ```rust
/// use stringzilla::stringzilla as sz;
///
/// #[derive(Debug)]
/// struct Person { name: &'static str, age: u32 }
///
/// let people1 = [
///     Person { name: "Charlie", age: 20 },
///     Person { name: "Alice", age: 25 },
///     Person { name: "Bob", age: 30 },
/// ];
/// let people2 = [
///     Person { name: "Alice", age: 25 },
///     Person { name: "Bob", age: 30 },
///     Person { name: "Charlie", age: 20 },
/// ];
/// let mut positions1 = [0; 3]; // min(people1.len(), people2.len())
/// let mut positions2 = [0; 3]; // min(people1.len(), people2.len())
/// let n = sz::intersection_by(
///     |i| people1[i].name.as_bytes(),
///     |j| people2[j].name.as_bytes(),
///     0,
///     &mut positions1,
///     &mut positions2,
/// ).expect("intersection_by failed");
/// assert!(n == 3); // "Alice", "Bob", and "Charlie" are common.
/// ```
pub fn intersection_by<Mapper1, Mapper2, Key1, Key2>(
    mapper1: Mapper1,
    mapper2: Mapper2,
    seed: u64,
    positions1: &mut [SortedIdx],
    positions2: &mut [SortedIdx],
) -> Result<usize, Status>
where
    Mapper1: Fn(usize) -> Key1,
    Key1: AsRef<[u8]>,
    Mapper2: Fn(usize) -> Key2,
    Key2: AsRef<[u8]>,
{
    if positions1.len() != positions2.len() {
        return Err(Status::BadAlloc);
    }

    // Adapter closure: given an index, call the provided mapper and then transmute the
    // resulting slice to have a `'static` lifetime. This transmute is safe as long as
    // the FFI call is synchronous and the returned slices are only used during the call.
    let adapter1 = move |i: usize| -> &'static [u8] {
        let binding = mapper1(i);
        let slice = binding.as_ref();
        unsafe { core::mem::transmute(slice) }
    };
    let adapter2 = move |i: usize| -> &'static [u8] {
        let binding = mapper2(i);
        let slice = binding.as_ref();
        unsafe { core::mem::transmute(slice) }
    };

    _intersection_by_impl(
        adapter1,
        adapter2,
        seed,
        positions1,
        positions2,
        positions1.len(),
        positions2.len(),
    )
}

fn _intersection_by_impl<Adapter1, Adapter2>(
    adapter1: Adapter1,
    adapter2: Adapter2,
    seed: u64,
    positions1: &mut [SortedIdx],
    positions2: &mut [SortedIdx],
    count1: usize,
    count2: usize,
) -> Result<usize, Status>
where
    Adapter1: Fn(usize) -> &'static [u8],
    Adapter2: Fn(usize) -> &'static [u8],
{
    let wrapper1 = _PunnedSliceLookupView {
        get_slice: unsafe { _get_slice_fn::<Adapter1>() },
        data: &adapter1 as *const Adapter1 as *const c_void,
    };
    let wrapper2 = _PunnedSliceLookupView {
        get_slice: unsafe { _get_slice_fn::<Adapter2>() },
        data: &adapter2 as *const Adapter2 as *const c_void,
    };
    let seq1 = _SzSequence {
        handle: &wrapper1 as *const _ as *const c_void,
        count: count1,
        get_start: Some(_slice_get_start_punned),
        get_length: Some(_slice_get_length_punned),
    };
    let seq2 = _SzSequence {
        handle: &wrapper2 as *const _ as *const c_void,
        count: count2,
        get_start: Some(_slice_get_start_punned),
        get_length: Some(_slice_get_length_punned),
    };
    let mut inter_size: usize = 0;
    let status = unsafe {
        sz_sequence_intersect(
            &seq1,
            &seq2,
            core::ptr::null(),
            seed,
            &mut inter_size as *mut usize,
            positions1.as_mut_ptr(),
            positions2.as_mut_ptr(),
        )
    };
    if status == Status::Success {
        Ok(inter_size)
    } else {
        Err(status)
    }
}

pub trait Matcher<'a> {
    fn find(&self, haystack: &'a [u8]) -> Option<usize>;
    fn needle_length(&self) -> usize;
}

pub enum MatcherType<'a> {
    Find(&'a [u8]),
    RFind(&'a [u8]),
    FindFirstOf(&'a [u8]),
    FindLastOf(&'a [u8]),
    FindFirstNotOf(&'a [u8]),
    FindLastNotOf(&'a [u8]),
}

impl<'a> Matcher<'a> for MatcherType<'a> {
    fn find(&self, haystack: &'a [u8]) -> Option<usize> {
        match self {
            MatcherType::Find(needle) => find(haystack, needle),
            MatcherType::RFind(needle) => rfind(haystack, needle),
            MatcherType::FindFirstOf(needles) => find_byte_from(haystack, needles),
            MatcherType::FindLastOf(needles) => rfind_byte_from(haystack, needles),
            MatcherType::FindFirstNotOf(needles) => find_byte_not_from(haystack, needles),
            MatcherType::FindLastNotOf(needles) => rfind_byte_not_from(haystack, needles),
        }
    }

    fn needle_length(&self) -> usize {
        match self {
            MatcherType::Find(needle) | MatcherType::RFind(needle) => needle.len(),
            _ => 1,
        }
    }
}

/// An iterator over non-overlapping matches of a pattern in a string slice.
/// This iterator yields the matched substrings in the order they are found.
///
/// # Empty needle
///
/// An empty needle matches at every position, including past the last byte: iterating over an
/// `n`-byte haystack yields `n + 1` empty matches, mirroring `"abc".matches("").count() == 4`.
/// Each zero-length match still advances the search position by at least one byte, so the
/// iterator always terminates instead of looping forever on the same spot.
///
/// # Examples
///
/// ```
/// use stringzilla::{stringzilla as sz, stringzilla::{MatcherType, FindMatches}};
///
/// let haystack = b"abababa";
/// let matcher = MatcherType::Find(b"aba");
/// let matches: Vec<&[u8]> = FindMatches::new(haystack, matcher).collect();
/// assert_eq!(matches, vec![b"aba", b"aba"]);
/// ```
pub struct FindMatches<'a, Overlap: Overlaps = NonOverlapping> {
    haystack: &'a [u8],
    matcher: MatcherType<'a>,
    position: usize,
    _overlaps: PhantomData<Overlap>,
}

impl<'a> FindMatches<'a, NonOverlapping> {
    pub fn new(haystack: &'a [u8], matcher: MatcherType<'a>) -> Self {
        Self {
            haystack,
            matcher,
            position: 0,
            _overlaps: PhantomData,
        }
    }

    /// Report overlapping matches too (compile-time policy; returns the `Overlapping` variant).
    pub fn overlapping(self) -> FindMatches<'a, Overlapping> {
        FindMatches {
            haystack: self.haystack,
            matcher: self.matcher,
            position: self.position,
            _overlaps: PhantomData,
        }
    }
}

impl<'a, Overlap: Overlaps> Iterator for FindMatches<'a, Overlap> {
    type Item = &'a [u8];

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        // An empty needle matches even in the empty slice at `haystack.len()`, so the bound is
        // exclusive on the *next* sentinel position, not on `haystack.len()` itself; once
        // exhausted, `position` is parked one past `haystack.len()` so this guard is stable.
        if self.position > self.haystack.len() {
            return None;
        }

        if let Some(index) = self.matcher.find(&self.haystack[self.position..]) {
            debug_assert!(
                self.position + index + self.matcher.needle_length() <= self.haystack.len(),
                "matcher returned a match span past the haystack end"
            );
            let start = self.position + index;
            let end = start + self.matcher.needle_length();
            // A zero-length match (empty needle) must still advance by at least one byte, or
            // this would loop forever re-matching the same position.
            let step = if Overlap::OVERLAP {
                1
            } else {
                self.matcher.needle_length().max(1)
            };
            self.position = start + step;
            Some(&self.haystack[start..end])
        } else {
            self.position = self.haystack.len() + 1;
            None
        }
    }
}

/// An iterator over non-overlapping splits of a string slice by a pattern.
/// This iterator yields the substrings between the matches of the pattern.
///
/// By default empty segments are **kept** (adjacent delimiters and leading/trailing matches yield empty
/// slices, mirroring `str::split`). Call [`Self::skip_empty`] to drop zero-length segments. The `STEPS`
/// const-generic mirrors the UTF-8 split iterators for API uniformity; substring/byteset splits search
/// match-by-match, so it does not affect the yielded segments.
///
/// # Empty needle and empty haystack
///
/// An empty haystack always yields exactly one (empty) segment, mirroring `"".split(",") == [""]`.
/// An empty needle matches at every position - including past the last byte - so it still yields one
/// empty segment per position instead of hanging: each zero-length match advances the search position
/// by at least one byte.
///
/// # Examples
///
/// ```
/// use stringzilla::{stringzilla as sz, stringzilla::{MatcherType, FindSplits}};
///
/// let haystack = b"a,b,c,d";
/// let matcher = MatcherType::Find(b",");
/// let splits: Vec<&[u8]> = FindSplits::new(haystack, matcher).collect();
/// assert_eq!(splits, vec![b"a", b"b", b"c", b"d"]);
/// ```
pub struct FindSplits<'a, Empty: EmptySegments = KeepEmpty, const STEPS: usize = ITERATORS_DEFAULT_STEPS> {
    haystack: &'a [u8],
    matcher: MatcherType<'a>,
    position: usize,
    _empties: PhantomData<Empty>,
}

impl<'a> FindSplits<'a, KeepEmpty, ITERATORS_DEFAULT_STEPS> {
    /// Constructs an iterator with the default batch size ([`ITERATORS_DEFAULT_STEPS`]).
    pub fn new(haystack: &'a [u8], matcher: MatcherType<'a>) -> Self {
        Self::with_steps(haystack, matcher)
    }
}

impl<'a, const STEPS: usize> FindSplits<'a, KeepEmpty, STEPS> {
    /// Constructs an iterator with an explicit batch size (kept for API uniformity with the UTF-8 splits).
    pub fn with_steps(haystack: &'a [u8], matcher: MatcherType<'a>) -> Self {
        Self {
            haystack,
            matcher,
            position: 0,
            _empties: PhantomData,
        }
    }

    /// Drop zero-length segments (compile-time policy; returns the `SkipEmpty` variant).
    pub fn skip_empty(self) -> FindSplits<'a, SkipEmpty, STEPS> {
        FindSplits {
            haystack: self.haystack,
            matcher: self.matcher,
            position: self.position,
            _empties: PhantomData,
        }
    }
}

impl<'a, Empty: EmptySegments, const STEPS: usize> FindSplits<'a, Empty, STEPS> {
    /// Yields the next raw segment without the empty-segment filter.
    #[inline(always)]
    fn next_raw(&mut self) -> Option<&'a [u8]> {
        // Empty delimiter: no split.
        if self.matcher.needle_length() == 0 {
            if self.position > self.haystack.len() {
                return None;
            }
            self.position = self.haystack.len() + 1;
            return Some(self.haystack);
        }
        // `position` only ever exceeds `haystack.len()` once the trailing segment below has
        // already been emitted; that sentinel, rather than tracking "did we ever match", is
        // what makes this correctly yield one empty segment for a completely empty haystack.
        if self.position > self.haystack.len() {
            return None;
        }

        if let Some(index) = self.matcher.find(&self.haystack[self.position..]) {
            debug_assert!(
                self.position + index + self.matcher.needle_length() <= self.haystack.len(),
                "matcher returned a match span past the haystack end"
            );
            let start = self.position;
            let end = self.position + index;
            // A zero-length match (empty needle) must still advance by at least one byte, or
            // this would loop forever re-matching the same position.
            self.position = end + self.matcher.needle_length().max(1);
            Some(&self.haystack[start..end])
        } else {
            let start = self.position;
            self.position = self.haystack.len() + 1;
            Some(&self.haystack[start..])
        }
    }
}

impl<'a, Empty: EmptySegments, const STEPS: usize> Iterator for FindSplits<'a, Empty, STEPS> {
    type Item = &'a [u8];

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let segment = self.next_raw()?;
            if Empty::SKIP && segment.is_empty() {
                continue;
            }
            return Some(segment);
        }
    }
}

/// An iterator over non-overlapping matches of a pattern in a string slice, searching from the end.
/// This iterator yields the matched substrings in reverse order.
///
/// # Empty needle
///
/// An empty needle matches at every position, including past the last byte: iterating over an
/// `n`-byte haystack yields `n + 1` empty matches, in reverse order. Each zero-length match still
/// shrinks the remaining search window by at least one byte, so the iterator always terminates
/// instead of looping forever on the same spot.
///
/// # Examples
///
/// ```
/// use stringzilla::{stringzilla as sz, stringzilla::{MatcherType, RFindMatches}};
///
/// let haystack = b"abababa";
/// let matcher = MatcherType::RFind(b"aba");
/// let matches: Vec<&[u8]> = RFindMatches::new(haystack, matcher).collect();
/// assert_eq!(matches, vec![b"aba", b"aba"]);
/// ```
pub struct RFindMatches<'a, Overlap: Overlaps = NonOverlapping> {
    haystack: &'a [u8],
    matcher: MatcherType<'a>,
    // Right-exclusive bound of the unsearched prefix; `usize::MAX` means exhausted.
    position: usize,
    _overlaps: PhantomData<Overlap>,
}

impl<'a> RFindMatches<'a, NonOverlapping> {
    pub fn new(haystack: &'a [u8], matcher: MatcherType<'a>) -> Self {
        Self {
            haystack,
            matcher,
            position: haystack.len(),
            _overlaps: PhantomData,
        }
    }

    /// Report overlapping matches too (compile-time policy; returns the `Overlapping` variant).
    pub fn overlapping(self) -> RFindMatches<'a, Overlapping> {
        RFindMatches {
            haystack: self.haystack,
            matcher: self.matcher,
            position: self.position,
            _overlaps: PhantomData,
        }
    }
}

impl<'a, Overlap: Overlaps> Iterator for RFindMatches<'a, Overlap> {
    type Item = &'a [u8];

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        if self.position == usize::MAX {
            return None;
        }

        let previous_position = self.position;
        let search_area = &self.haystack[..self.position];
        if let Some(index) = self.matcher.find(search_area) {
            let start = index;
            let end = start + self.matcher.needle_length();
            let result = Some(&self.haystack[start..end]);

            let skip = if Overlap::OVERLAP {
                self.matcher.needle_length().saturating_sub(1)
            } else {
                0
            };
            let next_position = start + skip;
            // A zero-length match (empty needle) can land exactly at the current window's
            // right edge, leaving `next_position == previous_position`; shrink by one more so
            // the window keeps making progress. Once there is nothing left to shrink, mark the
            // iterator exhausted via the `usize::MAX` sentinel instead of wrapping around.
            self.position = if next_position < previous_position {
                next_position
            } else if next_position == 0 {
                usize::MAX
            } else {
                next_position - 1
            };

            result
        } else {
            None
        }
    }
}

/// An iterator over non-overlapping splits of a string slice by a pattern, searching from the end.
/// This iterator yields the substrings between the matches of the pattern in reverse order.
///
/// By default empty segments are **kept** (mirroring `str::rsplit`). Call [`Self::skip_empty`] to drop
/// zero-length segments. The `STEPS` const-generic mirrors the UTF-8 split iterators for API uniformity;
/// substring/byteset splits search match-by-match, so it does not affect the yielded segments.
///
/// # Empty needle
///
/// An empty needle matches at every position, including past the last byte, so it still yields one
/// empty segment per position instead of hanging: each zero-length match shrinks the remaining
/// search window by at least one byte.
///
/// # Examples
///
/// ```
/// use stringzilla::{stringzilla as sz, stringzilla::{MatcherType, RFindSplits}};
///
/// let haystack = b"a,b,c,d";
/// let matcher = MatcherType::RFind(b",");
/// let splits: Vec<&[u8]> = RFindSplits::new(haystack, matcher).collect();
/// assert_eq!(splits, vec![b"d", b"c", b"b", b"a"]);
/// ```
pub struct RFindSplits<'a, Empty: EmptySegments = KeepEmpty, const STEPS: usize = ITERATORS_DEFAULT_STEPS> {
    haystack: &'a [u8],
    matcher: MatcherType<'a>,
    position: Option<usize>, // End of the not-yet-segmented prefix; `None` once the final segment is yielded
    _empties: PhantomData<Empty>,
}

impl<'a> RFindSplits<'a, KeepEmpty, ITERATORS_DEFAULT_STEPS> {
    /// Constructs an iterator with the default batch size ([`ITERATORS_DEFAULT_STEPS`]).
    pub fn new(haystack: &'a [u8], matcher: MatcherType<'a>) -> Self {
        Self::with_steps(haystack, matcher)
    }
}

impl<'a, const STEPS: usize> RFindSplits<'a, KeepEmpty, STEPS> {
    /// Constructs an iterator with an explicit batch size (kept for API uniformity with the UTF-8 splits).
    pub fn with_steps(haystack: &'a [u8], matcher: MatcherType<'a>) -> Self {
        Self {
            haystack,
            matcher,
            position: Some(haystack.len()),
            _empties: PhantomData,
        }
    }

    /// Drop zero-length segments (compile-time policy; returns the `SkipEmpty` variant).
    pub fn skip_empty(self) -> RFindSplits<'a, SkipEmpty, STEPS> {
        RFindSplits {
            haystack: self.haystack,
            matcher: self.matcher,
            position: self.position,
            _empties: PhantomData,
        }
    }
}

impl<'a, Empty: EmptySegments, const STEPS: usize> RFindSplits<'a, Empty, STEPS> {
    /// Yields the next raw segment (reverse order) without the empty-segment filter.
    #[inline(always)]
    fn next_raw(&mut self) -> Option<&'a [u8]> {
        let position = self.position?;
        // Empty delimiter: no split.
        if self.matcher.needle_length() == 0 {
            self.position = None;
            return Some(&self.haystack[..position]);
        }
        let search_area = &self.haystack[..position];
        if let Some(index) = self.matcher.find(search_area) {
            let start = index + self.matcher.needle_length();
            // A non-empty needle always matches strictly inside `search_area`, so `index <
            // position` and the window keeps shrinking. An empty needle instead matches right
            // at the window's own edge (`index == position`); shrink by one more byte there so
            // the next call doesn't re-match the same spot, and stop once nothing is left.
            self.position = if index < position {
                Some(index)
            } else {
                index.checked_sub(1)
            };
            Some(&self.haystack[start..position])
        } else {
            self.position = None;
            Some(&self.haystack[..position])
        }
    }
}

impl<'a, Empty: EmptySegments, const STEPS: usize> Iterator for RFindSplits<'a, Empty, STEPS> {
    type Item = &'a [u8];

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let segment = self.next_raw()?;
            if Empty::SKIP && segment.is_empty() {
                continue;
            }
            return Some(segment);
        }
    }
}

use core::marker::PhantomData;

/// A zero-sized UTF-8 segmentation kernel selector. Each implementor binds one FFI segmenter, so the shared
/// [`Utf8Split`] / [`Utf8Segments`] iterators monomorphize to a direct, branch-free call (no function pointer).
pub trait SegmenterKernel {
    /// Reports up to `capacity` segments of `text` into `offsets` / `lengths`, returning the count and writing
    /// the number of consumed bytes to `consumed`.
    ///
    /// # Safety
    /// `offsets` and `lengths` must each point to at least `capacity` writable `usize` slots, and `text` to
    /// `length` readable bytes.
    unsafe fn segment(
        text: *const c_void,
        length: usize,
        offsets: *mut usize,
        lengths: *mut usize,
        capacity: usize,
        consumed: *mut usize,
    ) -> usize;
}

/// Kernel behind [`Utf8SplitNewlines`] (`sz_utf8_newlines`).
pub struct Newlines;
impl SegmenterKernel for Newlines {
    unsafe fn segment(t: *const c_void, n: usize, o: *mut usize, l: *mut usize, c: usize, u: *mut usize) -> usize {
        sz_utf8_newlines(t, n, o, l, c, u)
    }
}

/// Kernel behind [`Utf8SplitWhitespaces`] (`sz_utf8_whitespaces`).
pub struct Whitespaces;
impl SegmenterKernel for Whitespaces {
    unsafe fn segment(t: *const c_void, n: usize, o: *mut usize, l: *mut usize, c: usize, u: *mut usize) -> usize {
        sz_utf8_whitespaces(t, n, o, l, c, u)
    }
}

/// Kernel behind [`Utf8SplitDelimiters`] (`sz_utf8_delimiters`).
pub struct Delimiters;
impl SegmenterKernel for Delimiters {
    unsafe fn segment(t: *const c_void, n: usize, o: *mut usize, l: *mut usize, c: usize, u: *mut usize) -> usize {
        sz_utf8_delimiters(t, n, o, l, c, u)
    }
}

/// Kernel behind [`Utf8Wordbreaks`] (`sz_utf8_wordbreaks`).
pub struct Wordbreaks;
impl SegmenterKernel for Wordbreaks {
    unsafe fn segment(t: *const c_void, n: usize, o: *mut usize, l: *mut usize, c: usize, u: *mut usize) -> usize {
        sz_utf8_wordbreaks(t, n, o, l, c, u)
    }
}

/// Kernel behind [`Utf8Graphemes`] (`sz_utf8_graphemes`).
pub struct Graphemes;
impl SegmenterKernel for Graphemes {
    unsafe fn segment(t: *const c_void, n: usize, o: *mut usize, l: *mut usize, c: usize, u: *mut usize) -> usize {
        sz_utf8_graphemes(t, n, o, l, c, u)
    }
}

/// Kernel behind [`Utf8Sentences`] (`sz_utf8_sentences`).
pub struct Sentences;
impl SegmenterKernel for Sentences {
    unsafe fn segment(t: *const c_void, n: usize, o: *mut usize, l: *mut usize, c: usize, u: *mut usize) -> usize {
        sz_utf8_sentences(t, n, o, l, c, u)
    }
}

/// Kernel behind [`Utf8Linebreaks`] (`sz_utf8_linebreaks`).
pub struct Linebreaks;
impl SegmenterKernel for Linebreaks {
    unsafe fn segment(t: *const c_void, n: usize, o: *mut usize, l: *mut usize, c: usize, u: *mut usize) -> usize {
        sz_utf8_linebreaks(t, n, o, l, c, u)
    }
}

/// Which parts a [`Utf8Split`] yields, as a compile-time `(FIRST, STRIDE)` over the span boundaries:
/// the segments BETWEEN separators, the SEPARATORS themselves, or BOTH interleaved (lossless).
pub trait SplitParts {
    /// First boundary index to visit (0 for between/both, 1 for separators).
    const FIRST: usize;
    /// Step between visited boundaries (2 for between/separators, 1 for both).
    const STRIDE: usize;
}
/// Yields the segments between separators (the default).
pub struct Between;
impl SplitParts for Between {
    const FIRST: usize = 0;
    const STRIDE: usize = 2;
}
/// Yields the separator runs themselves.
pub struct Separators;
impl SplitParts for Separators {
    const FIRST: usize = 1;
    const STRIDE: usize = 2;
}
/// Yields segments and separators interleaved (concatenating them reproduces the input).
pub struct Both;
impl SplitParts for Both {
    const FIRST: usize = 0;
    const STRIDE: usize = 1;
}

/// Compile-time policy for whether a split keeps or drops empty (zero-length) segments - the named,
/// branchless analogue of C++'s `empty_segments_t` (a marker type, not a raw `bool`).
pub trait EmptySegments {
    /// Whether zero-length segments are skipped.
    const SKIP: bool;
}
/// Keep empty segments (the default).
pub struct KeepEmpty;
impl EmptySegments for KeepEmpty {
    const SKIP: bool = false;
}
/// Drop empty segments (via `.skip_empty()`).
pub struct SkipEmpty;
impl EmptySegments for SkipEmpty {
    const SKIP: bool = true;
}

/// Compile-time policy for whether overlapping matches are reported - a named marker, not a raw `bool`.
pub trait Overlaps {
    /// Whether overlapping matches are included.
    const OVERLAP: bool;
}
/// Report only non-overlapping matches (the default; like `str::matches`).
pub struct NonOverlapping;
impl Overlaps for NonOverlapping {
    const OVERLAP: bool = false;
}
/// Report overlapping matches too (via `.overlapping()`).
pub struct Overlapping;
impl Overlaps for Overlapping {
    const OVERLAP: bool = true;
}

/// A range over UTF-8 text split on the separators a kernel reports, selecting which parts to yield.
///
/// The kernel's separator endpoints are the span boundaries `{0, s0.start, s0.end, ..., [len]}`; span `k` is
/// `bound(k)..bound(k+1)`, and `P` reduces the mode to a `(FIRST, STRIDE)` walk over them - so the hot path is one
/// formula for all three modes. Rust stable cannot size `[usize; 2*STEPS+2]`, so the raw separator spans are kept and
/// each boundary is computed on the fly (vs C++/Python which materialize the boundary array).
pub struct Utf8Split<
    'a,
    Kernel: SegmenterKernel,
    Parts: SplitParts = Between,
    Empty: EmptySegments = KeepEmpty,
    const STEPS: usize = ITERATORS_DEFAULT_STEPS,
> {
    text: &'a [u8],
    suffix: usize,           // Base of the current batch (absolute offset into `text`)
    starts: [usize; STEPS],  // Raw separator offsets from the kernel, relative to `suffix`
    lengths: [usize; STEPS], // Raw separator lengths
    separators: usize,       // Separators in the current batch (the kernel's return value)
    region: usize,           // Bytes of the current batch (`text.len() - suffix` at the last refill)
    spans: usize,            // Number of yieldable boundary spans; `spans == 0` is the end sentinel
    index: usize,            // Current boundary cursor (span is `bound(index)..bound(index + 1)`)
    advance: usize,          // Bytes to advance `suffix` by when the batch drains
    _markers: PhantomData<(Kernel, Parts, Empty)>,
}

impl<'a, Kernel: SegmenterKernel, Parts: SplitParts, Empty: EmptySegments>
    Utf8Split<'a, Kernel, Parts, Empty, ITERATORS_DEFAULT_STEPS>
{
    /// Constructs an iterator with the default batch size ([`ITERATORS_DEFAULT_STEPS`]).
    /// For an explicit batch size use [`Self::with_steps`] with a turbofish.
    pub fn new(text: &'a [u8]) -> Self {
        Self::with_steps(text)
    }
}

impl<'a, Kernel: SegmenterKernel, Parts: SplitParts, Empty: EmptySegments, const STEPS: usize>
    Utf8Split<'a, Kernel, Parts, Empty, STEPS>
{
    /// Constructs an iterator buffering up to `STEPS` separators per FFI call.
    pub fn with_steps(text: &'a [u8]) -> Self {
        let mut splits = Self {
            text,
            suffix: 0,
            starts: [0; STEPS],
            lengths: [0; STEPS],
            separators: 0,
            region: 0,
            spans: 0,
            index: 0,
            advance: 0,
            _markers: PhantomData,
        };
        splits.refill();
        splits.settle();
        splits
    }

    /// The `boundary`-th span boundary relative to `suffix`: `{0, s0.start, s0.end, s1.start, ..., [region]}`.
    #[inline]
    fn bound(&self, boundary: usize) -> usize {
        if boundary == 0 {
            0
        } else if boundary > 2 * self.separators {
            self.region // the end-of-text closing boundary
        } else if boundary & 1 == 1 {
            self.starts[(boundary - 1) / 2]
        } else {
            let separator = boundary / 2 - 1;
            self.starts[separator] + self.lengths[separator]
        }
    }

    /// Refill from `suffix`: fetch a separator batch; boundaries are derived lazily by [`Self::bound`].
    fn refill(&mut self) {
        self.region = self.text.len() - self.suffix;
        let mut consumed = 0usize;
        self.separators = unsafe {
            Kernel::segment(
                self.text[self.suffix..].as_ptr() as *const c_void,
                self.region,
                self.starts.as_mut_ptr(),
                self.lengths.as_mut_ptr(),
                STEPS,
                &mut consumed,
            )
        };
        debug_assert!(
            self.separators <= STEPS,
            "segmenter reported more spans than the capacity STEPS"
        );
        debug_assert!(consumed <= self.region, "segmenter consumed past the region end");
        debug_assert!(
            consumed > 0 || self.region == 0,
            "segmenter made no progress (the iterator would loop forever)"
        );
        debug_assert!(
            (0..self.separators).all(|s| self.starts[s] + self.lengths[s] <= self.region
                && (s == 0 || self.starts[s] >= self.starts[s - 1] + self.lengths[s - 1])),
            "separator spans run past the region, overlap, or are out of order"
        );
        // A batch cut short by `STEPS` must resume exactly at the end of its last separator: the bytes between
        // that separator and wherever the kernel's own scan stopped belong to the next segment, and a resume
        // offset past them drops them from the output.
        debug_assert!(
            self.separators < STEPS || consumed == self.starts[self.separators - 1] + self.lengths[self.separators - 1],
            "segmenter resumed past the end of its last emitted separator"
        );
        let eof = consumed == self.region;
        // Boundaries: `0`, then 2 per separator, plus the closing `region` at end-of-text.
        self.spans = 2 * self.separators + if eof { 1 } else { 0 };
        self.advance = if eof { self.region + 1 } else { consumed };
        self.index = Parts::FIRST;
    }

    /// Position `index` on the next yieldable span, refilling and (when `Empty::SKIP`) skipping empty spans.
    /// `Empty::SKIP` is a const, so the skip loop folds away entirely for the default keep-empties (`KeepEmpty`) case.
    fn settle(&mut self) {
        loop {
            if Empty::SKIP {
                while self.index < self.spans && self.bound(self.index + 1) == self.bound(self.index) {
                    self.index += Parts::STRIDE;
                }
            }
            if self.index < self.spans || self.spans == 0 {
                return;
            }
            self.suffix += self.advance;
            if self.suffix > self.text.len() {
                self.spans = 0;
                return;
            }
            self.refill();
        }
    }
}

impl<'a, Kernel: SegmenterKernel, Parts: SplitParts, const STEPS: usize>
    Utf8Split<'a, Kernel, Parts, KeepEmpty, STEPS>
{
    /// Skips zero-length spans, returning the `SkipEmpty` variant. A compile-time policy (like C++'s
    /// `empty_segments_t`), not a runtime flag, so the keep-empties default stays branchless.
    pub fn skip_empty(self) -> Utf8Split<'a, Kernel, Parts, SkipEmpty, STEPS> {
        Utf8Split::with_steps(self.text)
    }
}

impl<'a, Kernel: SegmenterKernel, Empty: EmptySegments, const STEPS: usize>
    Utf8Split<'a, Kernel, Between, Empty, STEPS>
{
    /// The same split yielding segments **and** separators interleaved. Lossless (concatenation reproduces the
    /// input) only when empties are kept; the `Empty` policy carries through the type, so `.skip_empty()` and
    /// `.with_separators()` compose in either order (matching the C++ binding).
    pub fn with_separators(self) -> Utf8Split<'a, Kernel, Both, Empty, STEPS> {
        Utf8Split::with_steps(self.text)
    }
}

impl<'a, Kernel: SegmenterKernel, Parts: SplitParts, Empty: EmptySegments, const STEPS: usize> Iterator
    for Utf8Split<'a, Kernel, Parts, Empty, STEPS>
{
    type Item = &'a [u8];

    fn next(&mut self) -> Option<Self::Item> {
        if self.spans == 0 {
            return None;
        }
        let begin = self.suffix + self.bound(self.index);
        let end = self.suffix + self.bound(self.index + 1);
        self.index += Parts::STRIDE;
        self.settle();
        Some(&self.text[begin..end])
    }
}

/// An iterator over substrings of UTF-8 text split by newline characters.
///
/// This iterator yields slices between newline characters. The newline characters themselves
/// are not included in the yielded slices. Handles all 8 Unicode newline characters including
/// CRLF as a single delimiter.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::{Utf8SplitNewlines};
///
/// let text = b"Hello\nWorld\r\nRust";
/// let lines: Vec<&[u8]> = Utf8SplitNewlines::new(text).collect();
/// assert_eq!(lines, vec![&b"Hello"[..], &b"World"[..], &b"Rust"[..]]);
/// ```
pub type Utf8SplitNewlines<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> =
    Utf8Split<'a, Newlines, Between, KeepEmpty, STEPS>;

/// An iterator over the newline runs themselves (the separators), in order.
pub type Utf8Newlines<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> =
    Utf8Split<'a, Newlines, Separators, KeepEmpty, STEPS>;

/// An iterator over segments of UTF-8 text split by whitespace characters.
///
/// Splits on all 25 Unicode "White_Space" characters; N whitespace delimiters yield N+1 segments. By
/// default empty segments are **kept** (matching the C++/Python bindings and `str::split`), so runs of
/// whitespace and leading/trailing whitespace produce empty slices. Call [`Self::skip_empty`] for the
/// `str::split_whitespace`-style behavior that drops empties and yields only non-empty tokens.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::{Utf8SplitWhitespaces};
///
/// // Default KEEP policy: empties around the words are preserved.
/// let text = b"  hi  ";
/// let segments: Vec<&[u8]> = Utf8SplitWhitespaces::new(text).collect();
/// assert_eq!(segments, vec![&b""[..], &b""[..], &b"hi"[..], &b""[..], &b""[..]]);
///
/// // Opt in to dropping empties for token-style splitting.
/// let tokens: Vec<&[u8]> = Utf8SplitWhitespaces::new(text).skip_empty().collect();
/// assert_eq!(tokens, vec![&b"hi"[..]]);
/// ```
pub type Utf8SplitWhitespaces<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> =
    Utf8Split<'a, Whitespaces, Between, KeepEmpty, STEPS>;

/// An iterator over the whitespace runs themselves (the separators), in order.
pub type Utf8Whitespaces<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> =
    Utf8Split<'a, Whitespaces, Separators, KeepEmpty, STEPS>;

/// An iterator over segments of UTF-8 text split by any Unicode delimiter codepoint.
///
/// Splits on every codepoint whose Unicode general category is punctuation (`P*`), symbol (`S*`), or
/// separator/whitespace (`Z*`) — the superset of [`Utf8SplitWhitespaces`]. N delimiters yield N+1 segments; empty
/// segments are **kept** by default (call [`Self::skip_empty`] to drop them for token-style splitting).
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::{Utf8SplitDelimiters};
///
/// // "Hi, world—foo" splits on ',', ' ', and U+2014 EM DASH.
/// let tokens: Vec<&[u8]> = Utf8SplitDelimiters::new("Hi, world\u{2014}foo".as_bytes()).skip_empty().collect();
/// assert_eq!(tokens, vec![&b"Hi"[..], &b"world"[..], &b"foo"[..]]);
/// ```
pub type Utf8SplitDelimiters<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> =
    Utf8Split<'a, Delimiters, Between, KeepEmpty, STEPS>;

/// An iterator over the delimiter runs themselves (the separators), in order.
pub type Utf8Delimiters<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> =
    Utf8Split<'a, Delimiters, Separators, KeepEmpty, STEPS>;

/// Default batch size for buffering the `sz_utf8_*` boundary kernels' output, mirroring the core
/// `sz_iterators_default_steps_k` enum in `include/stringzilla/utf8_wordbreaks.h`. Buffering this many
/// boundaries per call amortizes the per-item dispatch/FFI overhead without an unbounded buffer; the
/// kernels report `bytes_consumed`, so a full buffer simply resumes on the next call.
pub const ITERATORS_DEFAULT_STEPS: usize = 64;

pub struct Utf8Segments<'a, Kernel: SegmenterKernel, const STEPS: usize = ITERATORS_DEFAULT_STEPS> {
    text: &'a [u8],
    suffix: usize, // Start of the not-yet-segmented suffix (a TR29 boundary; `text.len()` once exhausted)
    starts: [usize; STEPS], // Buffered word offsets, relative to `suffix`
    lengths: [usize; STEPS], // Buffered word lengths
    count: usize,  // Number of buffered words (0 once exhausted)
    index: usize,  // Index of the next word to yield from the buffer
    _kernel: PhantomData<Kernel>, // Zero-sized; selects the FFI segmenter at monomorphization.
}

impl<'a, Kernel: SegmenterKernel> Utf8Segments<'a, Kernel, ITERATORS_DEFAULT_STEPS> {
    /// Constructs an iterator with the default batch size ([`ITERATORS_DEFAULT_STEPS`]).
    /// For an explicit batch size use [`Self::with_steps`] with a turbofish, e.g.
    /// `Utf8Wordbreaks::<1>::with_steps(text)`.
    pub fn new(text: &'a [u8]) -> Self {
        Self::with_steps(text)
    }
}

impl<'a, Kernel: SegmenterKernel, const STEPS: usize> Utf8Segments<'a, Kernel, STEPS> {
    /// Constructs an iterator buffering up to `STEPS` words per FFI call.
    pub fn with_steps(text: &'a [u8]) -> Self {
        let mut splits = Self {
            text,
            suffix: 0,
            starts: [0; STEPS],
            lengths: [0; STEPS],
            count: 0,
            index: 0,
            _kernel: PhantomData,
        };
        splits.fill();
        splits
    }

    /// Refills the buffer from the current suffix; `count` becomes 0 once the suffix is empty.
    fn fill(&mut self) {
        let mut consumed = 0usize;
        self.count = unsafe {
            Kernel::segment(
                self.text[self.suffix..].as_ptr() as *const c_void,
                self.text.len() - self.suffix,
                self.starts.as_mut_ptr(),
                self.lengths.as_mut_ptr(),
                STEPS,
                &mut consumed,
            )
        };
        self.index = 0;
    }
}

impl<'a, Kernel: SegmenterKernel, const STEPS: usize> Iterator for Utf8Segments<'a, Kernel, STEPS> {
    type Item = &'a [u8];

    fn next(&mut self) -> Option<Self::Item> {
        if self.index == self.count {
            if self.count == 0 {
                return None; // Empty input or fully drained.
            }
            // Batch drained: advance past the last word (a TR29 boundary) and refill from the remaining suffix.
            self.suffix += self.starts[self.count - 1] + self.lengths[self.count - 1];
            self.fill();
            if self.count == 0 {
                return None;
            }
        }
        let begin = self.suffix + self.starts[self.index];
        let end = begin + self.lengths[self.index];
        self.index += 1;
        Some(&self.text[begin..end])
    }
}

/// An iterator over UAX-29 words in UTF-8 text, in order.
///
/// Unlike whitespace splitting, the words tile the input: every byte belongs to exactly one word, so
/// consecutive words are contiguous and no empty slices are produced. Follows the Unicode TR29 rules.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::Utf8Wordbreaks;
///
/// let words: Vec<&[u8]> = Utf8Wordbreaks::new(b"Hi, world").collect();
/// assert_eq!(words, vec![&b"Hi"[..], &b","[..], &b" "[..], &b"world"[..]]);
/// ```
pub type Utf8Wordbreaks<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> = Utf8Segments<'a, Wordbreaks, STEPS>;

/// An iterator over UAX-29 grapheme clusters in UTF-8 text, in order.
///
/// Unlike whitespace splitting, the grapheme clusters tile the input: every byte belongs to exactly one
/// grapheme cluster, so consecutive clusters are contiguous and no empty slices are produced. Follows the
/// Unicode TR29 rules.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::Utf8Graphemes;
///
/// let graphemes: Vec<&[u8]> = Utf8Graphemes::new(b"Hi!").collect();
/// assert_eq!(graphemes, vec![&b"H"[..], &b"i"[..], &b"!"[..]]);
/// ```
pub type Utf8Graphemes<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> = Utf8Segments<'a, Graphemes, STEPS>;

/// An iterator over UAX-29 sentences in UTF-8 text, in order.
///
/// Unlike whitespace splitting, the sentences tile the input: every byte belongs to exactly one
/// sentence, so consecutive sentences are contiguous and no empty slices are produced. Follows the
/// Unicode TR29 rules.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::Utf8Sentences;
///
/// let sentences: Vec<&[u8]> = Utf8Sentences::new(b"Hi. Bye.").collect();
/// assert_eq!(sentences, vec![&b"Hi. "[..], &b"Bye."[..]]);
/// ```
pub type Utf8Sentences<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> = Utf8Segments<'a, Sentences, STEPS>;

/// An iterator over UAX-14 line break opportunities in UTF-8 text, in order.
///
/// Unlike whitespace splitting, the lines tile the input: every byte belongs to exactly one line, so
/// consecutive lines are contiguous and no empty slices are produced. Follows the Unicode TR14 rules.
///
/// Each yielded segment ends at a TR14 break opportunity, including soft breaks where a renderer *may*
/// wrap but is not required to. To split only on hard line breaks (the "splitlines" behaviour), use the
/// newline API ([`StringZillable::sz_utf8_split_newlines`]) instead.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::Utf8Linebreaks;
///
/// let lines: Vec<&[u8]> = Utf8Linebreaks::new(b"Hi\nBye").collect();
/// assert_eq!(lines, vec![&b"Hi\n"[..], &b"Bye"[..]]);
/// ```
pub type Utf8Linebreaks<'a, const STEPS: usize = ITERATORS_DEFAULT_STEPS> = Utf8Segments<'a, Linebreaks, STEPS>;

/// An iterator over uncased matches of a UTF-8 pattern in a string.
///
/// This iterator yields `IndexSpan` values representing the byte offset and length
/// of each match. The match length may differ from the needle length due to Unicode
/// case folding (e.g., "ß" matches "SS", German eszett expands to two characters).
///
/// The iterator caches needle metadata internally for efficient repeated searches.
///
/// Unlike [`find`]/[`rfind`], the underlying UTF-8 search reports an empty needle as a real
/// zero-length match rather than "not found". Each zero-length match still advances the
/// search position by at least one byte, so the iterator always terminates instead of
/// looping forever on the same spot.
///
/// # Examples
///
/// ```
/// use stringzilla::stringzilla::{Utf8UncasedMatches, IndexSpan};
///
/// let haystack = b"Hello WORLD, hello world";
/// let matches: Vec<IndexSpan> = Utf8UncasedMatches::new(haystack, b"hello").collect();
/// assert_eq!(matches.len(), 2);
/// assert_eq!(matches[0], IndexSpan::new(0, 5));
/// assert_eq!(matches[1], IndexSpan::new(13, 5));
/// ```
///
/// With overlapping matches:
///
/// ```
/// use stringzilla::stringzilla::{Utf8UncasedMatches, IndexSpan};
///
/// let haystack = b"aAaAa";
/// let matches: Vec<IndexSpan> = Utf8UncasedMatches::new(haystack, b"aA").overlapping().collect();
/// assert_eq!(matches.len(), 4); // Overlapping matches
/// ```
pub struct Utf8UncasedMatches<'a, O: Overlaps = NonOverlapping> {
    haystack: &'a [u8],
    needle: &'a [u8],
    metadata: Utf8UncasedNeedleMetadata,
    position: usize,
    _overlaps: PhantomData<O>,
}

impl<'a> Utf8UncasedMatches<'a, NonOverlapping> {
    /// Creates a new iterator for non-overlapping uncased matches.
    pub fn new(haystack: &'a [u8], needle: &'a [u8]) -> Self {
        Self {
            haystack,
            needle,
            metadata: Utf8UncasedNeedleMetadata::default(),
            position: 0,
            _overlaps: PhantomData,
        }
    }

    /// Report overlapping matches too (compile-time policy; returns the `Overlapping` variant).
    pub fn overlapping(self) -> Utf8UncasedMatches<'a, Overlapping> {
        Utf8UncasedMatches {
            haystack: self.haystack,
            needle: self.needle,
            metadata: self.metadata,
            position: self.position,
            _overlaps: PhantomData,
        }
    }
}

impl<'a, O: Overlaps> Iterator for Utf8UncasedMatches<'a, O> {
    type Item = IndexSpan;

    fn next(&mut self) -> Option<Self::Item> {
        // Empty needle also matches at `haystack.len()`; park one past it once exhausted.
        if self.position > self.haystack.len() {
            return None;
        }

        let remaining = &self.haystack[self.position..];
        let mut matched_length: usize = 0;

        let result = unsafe {
            sz_utf8_uncased_search(
                remaining.as_ptr() as *const c_void,
                remaining.len(),
                self.needle.as_ptr() as *const c_void,
                self.needle.len(),
                &mut self.metadata,
                &mut matched_length,
            )
        };

        if result.is_null() {
            self.position = self.haystack.len() + 1;
            None
        } else {
            let offset_in_remaining = unsafe { result.offset_from(remaining.as_ptr() as *const c_void) } as usize;
            let absolute_offset = self.position + offset_in_remaining;

            // Advance position for next search. A zero-length match (empty needle) must still
            // advance by at least one byte in the non-overlapping case, or this would loop
            // forever re-matching the same position; the overlapping case already always
            // advances by 1 regardless of `matched_length`.
            if O::OVERLAP {
                self.position = absolute_offset + 1;
            } else {
                self.position = absolute_offset + matched_length.max(1);
            }

            Some(IndexSpan::new(absolute_offset, matched_length))
        }
    }
}

/// Trait for unary string operations that only operate on `self` without needle parameters.
/// These operations include hash computation and byte sum calculation.
///
/// # Examples
///
/// Basic usage on a byte slice:
///
/// ```
/// use stringzilla::sz::StringZillableUnary;
///
/// let text = b"Hello";
/// assert_eq!(text.sz_bytesum(), 500);
/// ```
pub trait StringZillableUnary {
    /// Computes the bytesum value of unsigned bytes in a given string.
    /// This function is useful for verifying data integrity and detecting changes in
    /// binary data, such as files or network packets.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableUnary;
    ///
    /// let text = b"Hello";
    /// assert_eq!(text.sz_bytesum(), 500);
    /// ```
    fn sz_bytesum(&self) -> u64;

    /// Computes a 64-bit AES-based hash value for a given string.
    /// This function is designed to provide a high-quality hash value for use in
    /// hash tables, data structures, and cryptographic applications.
    /// Unlike the bytesum function, the hash function is order-sensitive.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableUnary;
    ///
    /// let s1 = b"Hello";
    /// let s2 = b"World";
    /// assert_ne!(s1.sz_hash(), s2.sz_hash());
    /// ```
    fn sz_hash(&self) -> u64;

    /// Returns a lazy UTF-8 character view with SIMD-accelerated operations.
    ///
    /// The view provides:
    /// - `.len()` for character count (lazy: computed on first call, cached)
    /// - `.offset_of(n)` for random access to Nth character offset
    /// - `.iter()` for efficient batched iteration over characters
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableUnary;
    ///
    /// let text = "Hello🌍";
    /// let view = text.sz_utf8_runes();
    ///
    /// // Lazy character count
    /// assert_eq!(view.len(), 6);
    ///
    /// // Random access (byte offset of Nth character)
    /// assert_eq!(view.offset_of(5), Some(5)); // 🌍 at byte 5
    ///
    /// // Efficient batched iteration
    /// let chars: Vec<char> = view.iter().collect();
    /// assert_eq!(chars, vec!['H', 'e', 'l', 'l', 'o', '🌍']);
    /// ```
    fn sz_utf8_runes(&self) -> Utf8View<'_>;

    /// Returns an iterator over lines split by UTF-8 newline characters.
    ///
    /// The iterator yields slices between newlines. Handles all Unicode newline characters
    /// including CRLF as a single delimiter.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableUnary;
    ///
    /// let text = "Hello\nWorld\r\nRust";
    /// let lines: Vec<&str> = text.sz_utf8_split_newlines()
    ///     .map(|line| std::str::from_utf8(line).unwrap())
    ///     .collect();
    /// assert_eq!(lines, vec!["Hello", "World", "Rust"]);
    /// ```
    fn sz_utf8_split_newlines(&self) -> Utf8SplitNewlines<'_>;

    /// Returns an iterator over the newline runs themselves (the separators).
    fn sz_utf8_newlines(&self) -> Utf8Newlines<'_>;

    /// Returns an iterator over segments split by UTF-8 whitespace characters.
    ///
    /// Handles all 25 Unicode "White_Space" characters; N delimiters yield N+1 segments. By default
    /// **empty segments are kept** (matching the C++/Python bindings and `str::split`), so runs of
    /// whitespace surface empty slices. Chain `.skip_empty()` on the returned iterator to recover the
    /// `str::split_whitespace` token behavior that drops empties.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableUnary;
    ///
    /// // KEEP (default): the double space between "Hello" and "World" yields an empty segment.
    /// let text = "Hello  World\tRust";
    /// let segments: Vec<&str> = text.sz_utf8_split_whitespaces()
    ///     .map(|segment| std::str::from_utf8(segment).unwrap())
    ///     .collect();
    /// assert_eq!(segments, vec!["Hello", "", "World", "Rust"]);
    ///
    /// // skip_empty: drops the empties to yield only the non-empty tokens.
    /// let tokens: Vec<&str> = text.sz_utf8_split_whitespaces()
    ///     .skip_empty()
    ///     .map(|token| std::str::from_utf8(token).unwrap())
    ///     .collect();
    /// assert_eq!(tokens, vec!["Hello", "World", "Rust"]);
    /// ```
    fn sz_utf8_split_whitespaces(&self) -> Utf8SplitWhitespaces<'_>;

    /// Returns an iterator over the whitespace runs themselves (the separators).
    fn sz_utf8_whitespaces(&self) -> Utf8Whitespaces<'_>;

    /// Returns an iterator splitting on any Unicode delimiter (punctuation/symbol/separator/whitespace).
    fn sz_utf8_split_delimiters(&self) -> Utf8SplitDelimiters<'_>;

    /// Returns an iterator over the delimiter runs themselves (the separators).
    fn sz_utf8_delimiters(&self) -> Utf8Delimiters<'_>;

    /// Returns an iterator over UAX-29 words (Unicode TR29), in order. Words tile the input contiguously.
    fn sz_utf8_wordbreaks(&self) -> Utf8Wordbreaks<'_>;

    /// Returns an iterator over UAX-29 grapheme clusters (Unicode TR29), in order. Clusters tile the input contiguously.
    fn sz_utf8_graphemes(&self) -> Utf8Graphemes<'_>;

    /// Returns an iterator over UAX-29 sentences (Unicode TR29), in order. Sentences tile the input contiguously.
    fn sz_utf8_sentences(&self) -> Utf8Sentences<'_>;

    /// Returns an iterator over UAX-14 line-break opportunities (Unicode TR14), in order. Linewrap segments tile the
    /// input contiguously, including soft break opportunities. For hard line splits only, use
    /// [`Self::sz_utf8_split_newlines`].
    fn sz_utf8_linebreaks(&self) -> Utf8Linebreaks<'_>;
}

/// Trait for binary string operations that take a needle parameter.
/// These operations include searching, splitting, and pattern matching.
///
/// # Examples
///
/// Basic usage on a string slice:
///
/// ```
/// use stringzilla::sz::StringZillableBinary;
///
/// let haystack = "Hello, world!";
/// assert_eq!(haystack.sz_find("world".as_bytes()), Some(7));
/// ```
pub trait StringZillableBinary<'a, Needle>
where
    Needle: AsRef<[u8]> + 'a,
{
    /// Searches for the first occurrence of `needle` in `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = "Hello, world!";
    /// assert_eq!(haystack.sz_find("world".as_bytes()), Some(7));
    /// ```
    fn sz_find(&self, needle: Needle) -> Option<usize>;

    /// Searches for the last occurrence of `needle` in `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = "Hello, world, world!";
    /// assert_eq!(haystack.sz_rfind("world".as_bytes()), Some(14));
    /// ```
    fn sz_rfind(&self, needle: Needle) -> Option<usize>;

    /// Finds the index of the first character in `self` that is also present in `needles`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = "Hello, world!";
    /// assert_eq!(haystack.sz_find_byte_from("aeiou".as_bytes()), Some(1));
    /// ```
    fn sz_find_byte_from(&self, needles: Needle) -> Option<usize>;

    /// Finds the index of the last character in `self` that is also present in `needles`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = "Hello, world!";
    /// assert_eq!(haystack.sz_rfind_byte_from("aeiou".as_bytes()), Some(8));
    /// ```
    fn sz_rfind_byte_from(&self, needles: Needle) -> Option<usize>;

    /// Finds the index of the first character in `self` that is not present in `needles`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = "Hello, world!";
    /// assert_eq!(haystack.sz_find_byte_not_from("aeiou".as_bytes()), Some(0));
    /// ```
    fn sz_find_byte_not_from(&self, needles: Needle) -> Option<usize>;

    /// Finds the index of the last character in `self` that is not present in `needles`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = "Hello, world!";
    /// assert_eq!(haystack.sz_rfind_byte_not_from("aeiou".as_bytes()), Some(12));
    /// ```
    fn sz_rfind_byte_not_from(&self, needles: Needle) -> Option<usize>;

    /// Returns an iterator over all non-overlapping matches of the given `needle` in `self`.
    ///
    /// # Arguments
    ///
    /// * `needle`: The byte slice to search for within `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = b"abababa";
    /// let needle = b"aba";
    /// let matches: Vec<&[u8]> = haystack.sz_matches(needle).collect();
    /// assert_eq!(matches, vec![b"aba", b"aba"]); // non-overlapping by default (like str::matches)
    /// let overlapping: Vec<&[u8]> = haystack.sz_matches(needle).overlapping().collect();
    /// assert_eq!(overlapping, vec![b"aba", b"aba", b"aba"]); // opt in with .overlapping()
    /// ```
    fn sz_matches(&'a self, needle: &'a Needle) -> FindMatches<'a>;

    /// Returns an iterator over all non-overlapping matches of the given `needle` in `self`, searching from the end.
    ///
    /// # Arguments
    ///
    /// * `needle`: The byte slice to search for within `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = b"abababa";
    /// let needle = b"aba";
    /// let matches: Vec<&[u8]> = haystack.sz_rmatches(needle).collect();
    /// assert_eq!(matches, vec![b"aba", b"aba"]); // non-overlapping by default
    /// let overlapping: Vec<&[u8]> = haystack.sz_rmatches(needle).overlapping().collect();
    /// assert_eq!(overlapping, vec![b"aba", b"aba", b"aba"]); // opt in with .overlapping()
    /// ```
    fn sz_rmatches(&'a self, needle: &'a Needle) -> RFindMatches<'a>;

    /// Returns an iterator over the substrings of `self` that are separated by the given `needle`.
    ///
    /// # Arguments
    ///
    /// * `needle`: The byte slice to split `self` by.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = b"a,b,c,d";
    /// let needle = b",";
    /// let splits: Vec<&[u8]> = haystack.sz_splits(needle).collect();
    /// assert_eq!(splits, vec![b"a", b"b", b"c", b"d"]);
    /// ```
    fn sz_splits(&'a self, needle: &'a Needle) -> FindSplits<'a>;

    /// Returns an iterator over the substrings of `self` that are separated by the given `needle`, searching from the end.
    ///
    /// # Arguments
    ///
    /// * `needle`: The byte slice to split `self` by.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = b"a,b,c,d";
    /// let needle = b",";
    /// let splits: Vec<&[u8]> = haystack.sz_rsplits(needle).collect();
    /// assert_eq!(splits, vec![b"d", b"c", b"b", b"a"]);
    /// ```
    fn sz_rsplits(&'a self, needle: &'a Needle) -> RFindSplits<'a>;

    /// Returns an iterator over all non-overlapping matches of any of the bytes in `needles` within `self`.
    ///
    /// # Arguments
    ///
    /// * `needles`: The set of bytes to search for within `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = b"Hello, world!";
    /// let needles = b"aeiou";
    /// let matches: Vec<&[u8]> = haystack.sz_find_first_of(needles).collect();
    /// assert_eq!(matches, vec![b"e", b"o", b"o"]);
    /// ```
    fn sz_find_first_of(&'a self, needles: &'a Needle) -> FindMatches<'a>;

    /// Returns an iterator over all non-overlapping matches of any of the bytes in `needles` within `self`, searching from the end.
    ///
    /// # Arguments
    ///
    /// * `needles`: The set of bytes to search for within `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = b"Hello, world!";
    /// let needles = b"aeiou";
    /// let matches: Vec<&[u8]> = haystack.sz_find_last_of(needles).collect();
    /// assert_eq!(matches, vec![b"o", b"o", b"e"]);
    /// ```
    fn sz_find_last_of(&'a self, needles: &'a Needle) -> RFindMatches<'a>;

    /// Returns an iterator over all non-overlapping matches of any byte not in `needles` within `self`.
    ///
    /// # Arguments
    ///
    /// * `needles`: The set of bytes that should not be matched within `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = b"Hello, world!";
    /// let needles = b"aeiou";
    /// let matches: Vec<&[u8]> = haystack.sz_find_first_not_of(needles).collect();
    /// assert_eq!(matches, vec![b"H", b"l", b"l", b",", b" ", b"w", b"r", b"l", b"d", b"!"]);
    /// ```
    fn sz_find_first_not_of(&'a self, needles: &'a Needle) -> FindMatches<'a>;

    /// Returns an iterator over all non-overlapping matches of any byte not in `needles` within `self`, searching from the end.
    ///
    /// # Arguments
    ///
    /// * `needles`: The set of bytes that should not be matched within `self`.
    ///
    /// # Examples
    ///
    /// ```
    /// use stringzilla::sz::StringZillableBinary;
    ///
    /// let haystack = b"Hello, world!";
    /// let needles = b"aeiou";
    /// let matches: Vec<&[u8]> = haystack.sz_find_last_not_of(needles).collect();
    /// assert_eq!(matches, vec![b"!", b"d", b"l", b"r", b"w", b" ", b",", b"l", b"l", b"H"]);
    /// ```
    fn sz_find_last_not_of(&'a self, needles: &'a Needle) -> RFindMatches<'a>;
}

impl<Source> StringZillableUnary for Source
where
    Source: AsRef<[u8]> + ?Sized,
{
    fn sz_bytesum(&self) -> u64 {
        bytesum(self)
    }

    fn sz_hash(&self) -> u64 {
        hash(self)
    }

    fn sz_utf8_runes(&self) -> Utf8View<'_> {
        Utf8View::new(self.as_ref())
    }

    fn sz_utf8_split_newlines(&self) -> Utf8SplitNewlines<'_> {
        Utf8SplitNewlines::new(self.as_ref())
    }

    fn sz_utf8_newlines(&self) -> Utf8Newlines<'_> {
        Utf8Newlines::new(self.as_ref())
    }

    fn sz_utf8_split_whitespaces(&self) -> Utf8SplitWhitespaces<'_> {
        Utf8SplitWhitespaces::new(self.as_ref())
    }

    fn sz_utf8_whitespaces(&self) -> Utf8Whitespaces<'_> {
        Utf8Whitespaces::new(self.as_ref())
    }

    fn sz_utf8_split_delimiters(&self) -> Utf8SplitDelimiters<'_> {
        Utf8SplitDelimiters::new(self.as_ref())
    }

    fn sz_utf8_delimiters(&self) -> Utf8Delimiters<'_> {
        Utf8Delimiters::new(self.as_ref())
    }

    fn sz_utf8_wordbreaks(&self) -> Utf8Wordbreaks<'_> {
        Utf8Wordbreaks::new(self.as_ref())
    }

    fn sz_utf8_graphemes(&self) -> Utf8Graphemes<'_> {
        Utf8Graphemes::new(self.as_ref())
    }

    fn sz_utf8_sentences(&self) -> Utf8Sentences<'_> {
        Utf8Sentences::new(self.as_ref())
    }

    fn sz_utf8_linebreaks(&self) -> Utf8Linebreaks<'_> {
        Utf8Linebreaks::new(self.as_ref())
    }
}

impl<'a, Source, Needle> StringZillableBinary<'a, Needle> for Source
where
    Source: AsRef<[u8]> + ?Sized,
    Needle: AsRef<[u8]> + 'a,
{
    fn sz_find(&self, needle: Needle) -> Option<usize> {
        find(self, needle)
    }

    fn sz_rfind(&self, needle: Needle) -> Option<usize> {
        rfind(self, needle)
    }

    fn sz_find_byte_from(&self, needles: Needle) -> Option<usize> {
        find_byte_from(self, needles)
    }

    fn sz_rfind_byte_from(&self, needles: Needle) -> Option<usize> {
        rfind_byte_from(self, needles)
    }

    fn sz_find_byte_not_from(&self, needles: Needle) -> Option<usize> {
        find_byte_not_from(self, needles)
    }

    fn sz_rfind_byte_not_from(&self, needles: Needle) -> Option<usize> {
        rfind_byte_not_from(self, needles)
    }

    fn sz_matches(&'a self, needle: &'a Needle) -> FindMatches<'a> {
        FindMatches::new(self.as_ref(), MatcherType::Find(needle.as_ref()))
    }

    fn sz_rmatches(&'a self, needle: &'a Needle) -> RFindMatches<'a> {
        RFindMatches::new(self.as_ref(), MatcherType::RFind(needle.as_ref()))
    }

    fn sz_splits(&'a self, needle: &'a Needle) -> FindSplits<'a> {
        FindSplits::new(self.as_ref(), MatcherType::Find(needle.as_ref()))
    }

    fn sz_rsplits(&'a self, needle: &'a Needle) -> RFindSplits<'a> {
        RFindSplits::new(self.as_ref(), MatcherType::RFind(needle.as_ref()))
    }

    fn sz_find_first_of(&'a self, needles: &'a Needle) -> FindMatches<'a> {
        FindMatches::new(self.as_ref(), MatcherType::FindFirstOf(needles.as_ref()))
    }

    fn sz_find_last_of(&'a self, needles: &'a Needle) -> RFindMatches<'a> {
        RFindMatches::new(self.as_ref(), MatcherType::FindLastOf(needles.as_ref()))
    }

    fn sz_find_first_not_of(&'a self, needles: &'a Needle) -> FindMatches<'a> {
        FindMatches::new(self.as_ref(), MatcherType::FindFirstNotOf(needles.as_ref()))
    }

    fn sz_find_last_not_of(&'a self, needles: &'a Needle) -> RFindMatches<'a> {
        RFindMatches::new(self.as_ref(), MatcherType::FindLastNotOf(needles.as_ref()))
    }
}

#[cfg(test)]
mod tests {

    // Realistic multi-script prose fixtures (ASCII-source \u{} escapes; rendered prose in comments).
    // Per-family segment counts are oracle-locked (ICU root / uniseg).
    // Hotel review (German + Japanese): NFD cafe, NBSP-glued units, a sentence-ending abbreviation, a CJK run.
    const PROSE_HOTEL_REVIEW: &str = concat!(
        "Last spring we strolled down M\u{fc}nchner Stra\u{df}e; the cafe\u{301} cortado cost 3,50\u{a0}",
        "\u{20ac} and was unreal. Dr. Vogel, our guide, swore it's the city's finest. Worth the detour?! ",
        "Absolutely \u{2014} and \u{6771}\u{4eac}\u{30bf}\u{30ef}\u{30fc} the next week, all 333\u{a0}m o",
        "f it, was breathtaking at dusk\u{2026}"
    );
    // Pride caption: a ZWJ family and VS16 rainbow flag, a skin-tone modifier, a keycap, an odd regional-indicator run.
    const PROSE_PRIDE_CAPTION: &str = concat!(
        "Best Pride yet \u{1f3f3}\u{fe0f}\u{200d}\u{1f308} \u{2014} the whole crew showed up. Even my par",
        "ents \u{1f468}\u{200d}\u{1f469}\u{200d}\u{1f467}\u{200d}\u{1f466} and grandma \u{1f44d}\u{1f3fd}",
        " came through! We met at booth 5\u{fe0f}\u{20e3}, then waved every flag we packed \u{1f1fa}",
        "\u{1f1f8}\u{1f1ef}\u{1f1f5}\u{1f1eb}. Texting \u{260e}\u{fe0e} over calling \u{2708}\u{fe0f} all",
        " day; 10/10, would march again."
    );
    // Concert post (Korean + Japanese): conjoining L+V+T jamo, a Katakana run, an ideographic stop, a 'p.m.' no-break.
    const PROSE_CONCERT_POST: &str = concat!(
        "\u{c624}\u{b298} \u{cf58}\u{c11c}\u{d2b8}, \u{c9c4}\u{c9dc} \u{bbf8}\u{cce4}\u{b2e4}!! \u{1112}",
        "\u{1161}\u{11ab}\u{ad6d} \u{d32c}\u{b4e4}\u{c774} \u{b2e4} \u{baa8}\u{c600}\u{ace0}, the staff b",
        "owed and said \u{c548}\u{b155}\u{d788} \u{ac00}\u{c138}\u{c694}. Setlist was pure \u{30cf}",
        "\u{30fc}\u{30c9}\u{30b3}\u{30a2}; \u{4eca}\u{65e5}\u{306f}\u{6700}\u{9ad8}\u{3060}\u{3063}",
        "\u{305f}\u{3002} We screamed \u{c0ac}\u{b791}\u{d574} till 11 p.m. sharp."
    );
    // Devanagari note: a virama conjunct, ZWJ/ZWNJ half-forms, a spacing vowel sign, and an NFKC vulgar fraction.
    const PROSE_DEVANAGARI_TIP: &str = concat!(
        "Quick Devanagari tip: \u{915}\u{94d}\u{937} is one cluster (\u{915} + \u{94d} + \u{937}), not th",
        "ree. Force the half-form with ZWJ \u{2014} \u{915}\u{94d}\u{200d}\u{937} \u{2014} or split it wi",
        "th ZWNJ \u{2014} \u{915}\u{94d}\u{200c}\u{937}. The same logic hits \u{915}\u{94d}\u{937}\u{924}",
        "\u{94d}\u{930}\u{93f}\u{92f} and spacing vowel signs like \u{915}\u{940}. Renderers disagree, so",
        " test (\u{bd} the bugs are font bugs) before you ship!"
    );
    // Science abstract: NFKC ligatures/superscripts/Roman/full-width, Kelvin and Angstrom singletons, NBSP, WJ + ZWSP.
    const PROSE_SCIENCE_ABSTRACT: &str = concat!(
        "The \u{fb01}lm grew at 300\u{a0}\u{212a} on a 5\u{a0}\u{212b} buffer (\u{2248} 2\u{b2} monolayer",
        "s). Section \u{216b} covers the \u{ff21}-phase; see Fig. 2 for the \u{3a3}-band dispersion. Resi",
        "stivity scaled as T\u{b2}, vanishing at the 4.2\u{a0}\u{212a} transition. Full dataset: doi:10.1",
        "000\u{2060}/\u{200b}xyz (mirror in Box \u{2461})."
    );
    // News lede: 'U.S.A.' before a lowercase word (no break), curly quotes, thousands, currency, a date range.
    const PROSE_NEWS_LEDE: &str = concat!(
        "The U.S.A. wasn't ready, analysts said. \u{201c}We lost 1,000 jobs,\u{201d} the mayor warned. ",
        "\u{201c}Recovery starts now.\u{201d} Filings spiked 2024/06\u{2013}2024/09, topping $1,000 per c",
        "laim. Will it hold?! No one knows for sure."
    );
    // Language lesson: a Greek final sigma, Cyrillic case pairs, a Croatian titlecase digraph, and a fold-only match.
    #[allow(dead_code)] // used by the Python uncased prose test, not Rust
    const PROSE_LANGUAGE_LESSON: &str = concat!(
        "Greek lesson: \u{39f}\u{394}\u{39f}\u{3a3} becomes \u{3bf}\u{3b4}\u{3cc}\u{3c2} when lowercased,",
        " ending in a final \u{3c2}. Russian's easy too \u{2014} \u{41c}\u{41e}\u{421}\u{41a}\u{412}",
        "\u{410} \u{2194} \u{43c}\u{43e}\u{441}\u{43a}\u{432}\u{430}, no drama. Croatian has the digraph ",
        "\u{1c4}: titlecase \u{1c5}, lowercase \u{1c6}. Quiz \u{2014} does \u{201c}stra\u{df}e\u{201d} ma",
        "tch STRASSE? Yes, once you fold."
    );
    // RTL scripts: Hebrew gershayim, Arabic, a number-sign Prepend, an NFC niqqud reorder, a Malayalam dot-reph.
    const PROSE_RTL_SCRIPTS: &str = concat!(
        "Hebrew acronyms take gershayim: \u{5e6}\u{5d4}\u{5f4}\u{5dc} and \u{5d0}\u{5e8}\u{5d4}\u{5f4}",
        "\u{5d1} aren't typos. Arabic flows right-to-left too \u{2014} \u{645}\u{631}\u{62d}\u{628}",
        "\u{627} \u{628}\u{627}\u{644}\u{639}\u{627}\u{644}\u{645} \u{2014} and finance text can carry th",
        "e number sign \u{600}\u{664}. Niqqud stacks marks: \u{5e9}\u{5c1}\u{5b8}\u{5dc}\u{5d5}\u{5b9}",
        "\u{5dd} must reorder under NFC. Malayalam even has a true prepend, the dot-reph \u{d4e}\u{d15}."
    );
    // A U+2019 contraction tiles as a single word, like the ASCII apostrophe.
    const PROSE_MICRO_APOSTROPHE: &str = "it\u{2019}s worth it";
    // Two Prepend characters (Arabic number sign, Malayalam dot-reph): clusters fewer than codepoints.
    const PROSE_MICRO_PREPEND: &str = "\u{600}\u{664} \u{d4e}\u{d15}";
    // A CR-LF pair and a U+2028 line separator: both Sep (force sentence and line breaks); CR-LF is one grapheme.
    const PROSE_MICRO_HARDBREAKS: &str = "A.\u{d}\u{a}B.\u{2028}C.";
    // "cafe": precomposed e-acute (U+00E9, NFC) vs. base 'e' + combining acute U+0301 (NFD) - the
    // shared NFC/NFD fixture pair for the UTF-8 normalization tests.
    const CAFE_NFC: &str = "caf\u{00E9}";
    const CAFE_NFD: &str = "cafe\u{0301}";

    /// Folds a single codepoint into a fixed-size buffer, returning the buffer and its
    /// used length. A single codepoint case-folds to at most a handful of bytes (the
    /// longest known expansion is the Greek "ΐ" growing to 6 bytes), so a 16-byte buffer
    /// is comfortably oversized.
    fn fold_codepoint(codepoint: char) -> ([u8; 16], usize) {
        let mut source_buffer = [0u8; 4];
        let source = codepoint.encode_utf8(&mut source_buffer);
        let mut folded = [0u8; 16];
        let folded_length = sz::utf8_uncased_fold(source.as_bytes(), &mut folded[..]);
        debug_assert!(folded_length <= folded.len(), "fold expansion exceeded buffer");
        (folded, folded_length)
    }

    /// Independent oracle for uncased UTF-8 search. A match exists iff the fold of
    /// `needle` is a contiguous run of the fold of `haystack`; the earliest such run wins.
    /// The reported `(offset, length)` is in ORIGINAL haystack bytes, snapped to codepoint
    /// boundaries. Implemented by folding each haystack codepoint and remembering, for every
    /// folded byte, the original byte span of the codepoint that produced it.
    fn reference_uncased_find(haystack: &str, needle: &str) -> Option<(usize, usize)> {
        // Fixed-size accumulators sized for the short test inputs.
        const CAPACITY: usize = 512;
        let mut haystack_folded = [0u8; CAPACITY];
        // For each folded byte, the [start, end) byte range in the ORIGINAL haystack of the
        // codepoint that produced it.
        let mut source_starts = [0usize; CAPACITY];
        let mut source_ends = [0usize; CAPACITY];
        let mut haystack_folded_length = 0usize;

        let mut original_offset = 0usize;
        for codepoint in haystack.chars() {
            let codepoint_length = codepoint.len_utf8();
            let codepoint_start = original_offset;
            let codepoint_end = original_offset + codepoint_length;
            let (folded, folded_length) = fold_codepoint(codepoint);
            for byte_index in 0..folded_length {
                debug_assert!(haystack_folded_length < CAPACITY, "haystack fold overflow");
                haystack_folded[haystack_folded_length] = folded[byte_index];
                source_starts[haystack_folded_length] = codepoint_start;
                source_ends[haystack_folded_length] = codepoint_end;
                haystack_folded_length += 1;
            }
            original_offset = codepoint_end;
        }

        // Fold the needle independently.
        let mut needle_folded = [0u8; CAPACITY];
        let mut needle_folded_length = 0usize;
        let mut needle_buffer = [0u8; 4];
        for codepoint in needle.chars() {
            let source = codepoint.encode_utf8(&mut needle_buffer);
            let mut folded = [0u8; 16];
            let folded_length = sz::utf8_uncased_fold(source.as_bytes(), &mut folded[..]);
            for byte_index in 0..folded_length {
                debug_assert!(needle_folded_length < CAPACITY, "needle fold overflow");
                needle_folded[needle_folded_length] = folded[byte_index];
                needle_folded_length += 1;
            }
        }

        let haystack_fold = &haystack_folded[..haystack_folded_length];
        let needle_fold = &needle_folded[..needle_folded_length];

        // An empty needle-fold matches at the very start with zero length.
        if needle_fold.is_empty() {
            return Some((0, 0));
        }
        if needle_fold.len() > haystack_fold.len() {
            return None;
        }

        // Slide the needle-fold over the haystack-fold; earliest run wins.
        for run_start in 0..=(haystack_fold.len() - needle_fold.len()) {
            let run_end = run_start + needle_fold.len();
            if &haystack_fold[run_start..run_end] == needle_fold {
                let offset = source_starts[run_start];
                let length = source_ends[run_end - 1] - offset;
                return Some((offset, length));
            }
        }
        None
    }

    // Realistic multi-script prose fixtures: per-family segment counts (oracle-locked: ICU root / uniseg).
    #[test]
    fn utf8_prose_sentence_counts() {
        assert_eq!(PROSE_HOTEL_REVIEW.as_bytes().sz_utf8_sentences().count(), 5);
        assert_eq!(PROSE_CONCERT_POST.as_bytes().sz_utf8_sentences().count(), 4);
        assert_eq!(PROSE_NEWS_LEDE.as_bytes().sz_utf8_sentences().count(), 6);
        assert_eq!(PROSE_MICRO_HARDBREAKS.as_bytes().sz_utf8_sentences().count(), 3);
    }

    #[test]
    fn utf8_prose_wordbreak_counts() {
        assert_eq!(PROSE_HOTEL_REVIEW.as_bytes().sz_utf8_wordbreaks().count(), 100);
        assert_eq!(PROSE_NEWS_LEDE.as_bytes().sz_utf8_wordbreaks().count(), 83);
        assert_eq!(PROSE_CONCERT_POST.as_bytes().sz_utf8_wordbreaks().count(), 69);
        assert_eq!(PROSE_RTL_SCRIPTS.as_bytes().sz_utf8_wordbreaks().count(), 98);
        assert_eq!(PROSE_MICRO_APOSTROPHE.as_bytes().sz_utf8_wordbreaks().count(), 5);
    }

    #[test]
    fn utf8_prose_grapheme_counts() {
        assert_eq!(PROSE_PRIDE_CAPTION.as_bytes().sz_utf8_graphemes().count(), 206);
        assert_eq!(PROSE_DEVANAGARI_TIP.as_bytes().sz_utf8_graphemes().count(), 252);
        assert_eq!(PROSE_CONCERT_POST.as_bytes().sz_utf8_graphemes().count(), 134);
        assert_eq!(PROSE_RTL_SCRIPTS.as_bytes().sz_utf8_graphemes().count(), 256);
        assert_eq!(PROSE_MICRO_PREPEND.as_bytes().sz_utf8_graphemes().count(), 3);
        // Codepoints are not clusters: the emoji paragraph has more runes than grapheme clusters.
        assert_eq!(PROSE_PRIDE_CAPTION.as_bytes().sz_utf8_runes().iter().count(), 222);
        assert!(
            PROSE_PRIDE_CAPTION.as_bytes().sz_utf8_runes().iter().count()
                > PROSE_PRIDE_CAPTION.as_bytes().sz_utf8_graphemes().count()
        );
    }

    #[test]
    fn utf8_prose_linebreak_counts() {
        assert_eq!(PROSE_HOTEL_REVIEW.as_bytes().sz_utf8_linebreaks().count(), 45);
        assert_eq!(PROSE_SCIENCE_ABSTRACT.as_bytes().sz_utf8_linebreaks().count(), 43);
        assert_eq!(PROSE_NEWS_LEDE.as_bytes().sz_utf8_linebreaks().count(), 32);
    }

    extern crate alloc;
    use alloc::borrow::Cow;
    use alloc::format;
    use alloc::string::String;
    use alloc::vec;
    use alloc::vec::Vec;
    use core::hash::Hasher as _;
    // `HashMap`/`HashSet` have no `alloc`-only equivalent (unlike `Vec`/`String`/`BTreeMap`), so the
    // handful of tests that need them stay behind `feature = "std"`; everything else here runs no_std.
    #[cfg(feature = "std")]
    use std::collections::{HashMap, HashSet};

    use super::*;
    use crate::sz;

    #[test]
    fn metadata() {
        // Runtime dispatch is on with the `dynamic-dispatch` feature (default) and off for the
        // compile-time-dispatch build, where the best ISA tier is baked in instead of table-routed.
        assert_eq!(sz::dynamic_dispatch(), cfg!(feature = "dynamic-dispatch"));
        assert!(sz::capabilities().as_str().len() > 0);
    }

    #[test]
    fn bytesum() {
        assert_eq!(sz::bytesum("hi"), 209u64);
    }

    #[test]
    fn utf8_delimiters() {
        // `split_delimiters` yields the content BETWEEN ',', ' ', U+2014; skip_empty drops the empties.
        let toks: Vec<&[u8]> = "Hi, world\u{2014}foo"
            .as_bytes()
            .sz_utf8_split_delimiters()
            .skip_empty()
            .collect();
        assert_eq!(toks, vec![&b"Hi"[..], &b"world"[..], &b"foo"[..]]);
        // Default policy keeps the empty segment between adjacent delimiters.
        let kept: Vec<&[u8]> = "a,,b".as_bytes().sz_utf8_split_delimiters().collect();
        assert_eq!(kept, vec![&b"a"[..], &b""[..], &b"b"[..]]);
    }

    #[test]
    fn utf8_split_delimiters_sparse_batches() {
        // Sparse delimiters with long undelimited runs: each batch fills on the last delimiter its vector window
        // holds, and the letters between that delimiter and the window edge must survive into the next segment.
        // Dense inputs cannot reach this path, since a filled batch there always leaves hits behind in the window.
        for run in [16usize, 31, 62, 63, 64, 100] {
            let text = format!("a {} c", "b".repeat(run));
            let expected: Vec<&[u8]> = vec![b"a", text.as_bytes()[2..2 + run].as_ref(), b"c"];
            for tiny in [
                Utf8SplitDelimiters::<1>::with_steps(text.as_bytes()).collect::<Vec<_>>(),
                Utf8SplitDelimiters::<2>::with_steps(text.as_bytes()).collect::<Vec<_>>(),
                text.as_bytes().sz_utf8_split_delimiters().collect::<Vec<_>>(),
            ] {
                assert_eq!(tiny, expected, "run of {} undelimited bytes", run);
            }
            // Separators included, the split is lossless however small the batch.
            let both: Vec<&[u8]> = Utf8SplitDelimiters::<1>::with_steps(text.as_bytes())
                .with_separators()
                .collect();
            assert_eq!(both.concat(), text.as_bytes());
        }
    }

    #[test]
    fn utf8_split_modes() {
        // Scheme C: the bare name yields the separators; `split_` yields the content between.
        let text = "a b  c".as_bytes();
        let between: Vec<&[u8]> = text.sz_utf8_split_whitespaces().collect();
        assert_eq!(between, vec![&b"a"[..], &b"b"[..], &b""[..], &b"c"[..]]);
        let seps: Vec<&[u8]> = text.sz_utf8_whitespaces().collect();
        assert_eq!(seps, vec![&b" "[..], &b" "[..], &b" "[..]]);
        // `with_separators` interleaves them losslessly: concatenation reproduces the input.
        let both: Vec<&[u8]> = text.sz_utf8_split_whitespaces().with_separators().collect();
        assert_eq!(both.concat(), text);
        // Lossless round-trip also holds across leading/trailing separators and empty input.
        for t in ["  x  ", "", "abc", "a\r\nb"] {
            let rt: Vec<&[u8]> = t.as_bytes().sz_utf8_split_newlines().with_separators().collect();
            assert_eq!(rt.concat(), t.as_bytes());
        }
        // Empty input still yields one empty segment (matches C++ `[""]`).
        let empty: Vec<&[u8]> = "".as_bytes().sz_utf8_split_whitespaces().collect();
        assert_eq!(empty, vec![&b""[..]]);
        // Small batch size must agree with the default across ALL modes (exercises refill boundaries for
        // separators and both, not just between - the paths where a trailing gap straddles a batch).
        let many = "w ".repeat(50) + "end";
        let between_small: Vec<&[u8]> = Utf8SplitWhitespaces::<2>::with_steps(many.as_bytes()).collect();
        assert_eq!(
            between_small,
            many.as_bytes().sz_utf8_split_whitespaces().collect::<Vec<_>>()
        );
        let seps_small: Vec<&[u8]> = Utf8Whitespaces::<2>::with_steps(many.as_bytes()).collect();
        assert_eq!(seps_small, many.as_bytes().sz_utf8_whitespaces().collect::<Vec<_>>());
        let both_small: Vec<&[u8]> = Utf8SplitWhitespaces::<2>::with_steps(many.as_bytes())
            .with_separators()
            .collect();
        assert_eq!(both_small.concat(), many.as_bytes()); // lossless even across many refills
        assert_eq!(
            both_small,
            many.as_bytes()
                .sz_utf8_split_whitespaces()
                .with_separators()
                .collect::<Vec<_>>()
        );
        // `with_separators` preserves `skip_empty` regardless of chaining order.
        let dropped: Vec<&[u8]> = "a  b"
            .as_bytes()
            .sz_utf8_split_whitespaces()
            .skip_empty()
            .with_separators()
            .collect();
        assert!(dropped.iter().all(|s| !s.is_empty()));
        // `utf8_wordbreaks` tiles into all UAX-29 segments (words and the separators between them).
        let segs: Vec<&[u8]> = "Hello, world!".as_bytes().sz_utf8_wordbreaks().collect();
        assert_eq!(segs.concat(), &b"Hello, world!"[..]);
        assert_eq!(segs.len(), 5);
    }

    #[test]
    fn hash() {
        let hash_hello = sz::hash("Hello");
        let hash_world = sz::hash("World");
        assert_ne!(hash_hello, hash_world);

        // Hashing should work the same for any seed
        for seed in [0u64, 42, 123456789].iter() {
            // Single-pass hashing
            assert_eq!(
                sz::Hasher::new(*seed).update("Hello".as_bytes()).digest(),
                sz::hash_with_seed("Hello", *seed)
            );
            // Dual pass for short strings
            assert_eq!(
                sz::Hasher::new(*seed)
                    .update("Hello".as_bytes())
                    .update("World".as_bytes())
                    .digest(),
                sz::hash_with_seed("HelloWorld", *seed)
            );
        }
    }

    #[test]
    fn streaming_hash() {
        let mut hasher = sz::Hasher::new(123);
        hasher.write(b"Hello, ");
        hasher.write(b"world!");
        let streamed = hasher.finish();

        let mut hasher = sz::Hasher::new(123);
        hasher.write(b"Hello, world!");
        let expected = hasher.finish();
        assert_eq!(streamed, expected);
    }

    #[test]
    fn multiseed_hash() {
        // More than four seeds to exercise the 4-wide tail handling on the Ice Lake backend.
        let seeds: Vec<u64> = (0..9u64)
            .map(|i| i.wrapping_mul(0x9E3779B97F4A7C15).wrapping_add(7))
            .collect();
        let texts: [&[u8]; 5] = [
            b"",
            b"token",
            b"sixteen_bytes!!!",
            b"sixty four chars exactly here to fill one whole block boundary..",
            b"a string definitely longer than sixty four bytes to hit the wide path here please",
        ];
        for text in texts {
            for k in 0..=seeds.len() {
                let mut out = vec![0u64; k];
                sz::hash_multiseed_into(text, &seeds[..k], &mut out);
                for i in 0..k {
                    assert_eq!(
                        out[i],
                        sz::hash_with_seed(text, seeds[i]),
                        "len={} k={} i={}",
                        text.len(),
                        k,
                        i
                    );
                }
            }
        }
    }

    #[test]
    #[cfg(feature = "std")]
    fn hashmap_with_sz() {
        let mut map: HashMap<&str, i32, sz::BuildSzHasher> = HashMap::with_hasher(sz::BuildSzHasher::with_seed(0));
        map.insert("a", 1);
        map.insert("b", 2);
        map.insert("c", 3);
        assert_eq!(map.get("a"), Some(&1));
        assert_eq!(map.get("b"), Some(&2));
        assert_eq!(map.get("c"), Some(&3));
        assert!(map.get("z").is_none());
    }

    #[test]
    #[cfg(feature = "std")]
    fn hashset_with_sz() {
        let mut set: HashSet<&str, sz::BuildSzHasher> = HashSet::with_hasher(sz::BuildSzHasher::with_seed(42));
        assert!(set.insert("alpha"));
        assert!(set.insert("beta"));
        assert!(set.contains("alpha"));
        assert!(set.contains("beta"));
        assert!(!set.contains("gamma"));
        let len_before = set.len();
        assert!(!set.insert("alpha"));
        assert_eq!(set.len(), len_before);
    }

    #[test]
    fn search() {
        let my_string: String = String::from("Hello, world!");
        let my_str: &str = my_string.as_str();
        let my_cow_str: Cow<'_, str> = Cow::from(&my_string);

        // Identical to `memchr::memmem::find` and `memchr::memmem::rfind` functions
        assert_eq!(sz::find("Hello, world!", "world"), Some(7));
        assert_eq!(sz::rfind("Hello, world!", "world"), Some(7));

        // Use the generic function with a String
        let world_string = String::from("world");
        assert_eq!(my_string.sz_find(&world_string), Some(7));
        assert_eq!(my_string.sz_rfind(&world_string), Some(7));
        assert_eq!(my_string.sz_find_byte_from(&world_string), Some(2));
        assert_eq!(my_string.sz_rfind_byte_from(&world_string), Some(11));
        assert_eq!(my_string.sz_find_byte_not_from(&world_string), Some(0));
        assert_eq!(my_string.sz_rfind_byte_not_from(&world_string), Some(12));

        // Use the generic function with a &str
        assert_eq!(my_str.sz_find("world"), Some(7));
        assert_eq!(my_str.sz_rfind("world"), Some(7));
        assert_eq!(my_str.sz_find_byte_from("world"), Some(2));
        assert_eq!(my_str.sz_rfind_byte_from("world"), Some(11));
        assert_eq!(my_str.sz_find_byte_not_from("world"), Some(0));
        assert_eq!(my_str.sz_rfind_byte_not_from("world"), Some(12));

        // Use the generic function with a Cow<'_, str>
        assert_eq!(my_cow_str.as_ref().sz_find("world"), Some(7));
        assert_eq!(my_cow_str.as_ref().sz_rfind("world"), Some(7));
        assert_eq!(my_cow_str.as_ref().sz_find_byte_from("world"), Some(2));
        assert_eq!(my_cow_str.as_ref().sz_rfind_byte_from("world"), Some(11));
        assert_eq!(my_cow_str.as_ref().sz_find_byte_not_from("world"), Some(0));
        assert_eq!(my_cow_str.as_ref().sz_rfind_byte_not_from("world"), Some(12));
    }

    #[test]
    fn empty_needle_matches_std() {
        // The C core reports an empty needle as "not found" by design, but `find`/`rfind`/
        // `contains` synthesize the `str` answer instead.
        assert_eq!(sz::find("abc", ""), Some(0));
        assert_eq!("abc".find(""), Some(0));
        assert_eq!(sz::rfind("abc", ""), Some(3));
        assert_eq!("abc".rfind(""), Some(3));
        assert!(sz::contains("abc", ""));
        assert!("abc".contains(""));

        // An empty haystack is a degenerate but well-defined case too.
        assert_eq!(sz::find("", ""), Some(0));
        assert_eq!("".find(""), Some(0));
        assert_eq!(sz::rfind("", ""), Some(0));
        assert_eq!("".rfind(""), Some(0));
        assert!(sz::contains("", ""));
        assert!("".contains(""));

        // Non-empty needles are unaffected.
        assert_eq!(sz::find("abc", "b"), Some(1));
        assert_eq!(sz::rfind("abc", "b"), Some(1));
        assert!(sz::contains("abc", "b"));
        assert!(!sz::contains("abc", "z"));
    }

    #[test]
    fn fill_random() {
        let mut first_buffer: Vec<u8> = vec![0; 10]; // Ten zeros
        let mut second_buffer: Vec<u8> = vec![1; 10]; // Ten ones
        sz::fill_random(&mut first_buffer, 42);
        sz::fill_random(&mut second_buffer, 42);

        // Same nonce will produce the same outputs
        assert_eq!(first_buffer, second_buffer);
    }

    #[test]
    fn iter_matches_forward() {
        let haystack = b"hello world hello universe";
        let needle = b"hello";
        let matches: Vec<_> = haystack.sz_matches(needle).collect();
        assert_eq!(matches, vec![b"hello", b"hello"]);
    }

    #[test]
    fn iter_matches_reverse() {
        let haystack = b"hello world hello universe";
        let needle = b"hello";
        let matches: Vec<_> = haystack.sz_rmatches(needle).collect();
        assert_eq!(matches, vec![b"hello", b"hello"]);
    }

    #[test]
    fn iter_splits_forward() {
        let haystack = b"alpha,beta;gamma";
        let needle = b",";
        let splits: Vec<_> = haystack.sz_splits(needle).collect();
        assert_eq!(splits, vec![&b"alpha"[..], &b"beta;gamma"[..]]);
    }

    #[test]
    fn iter_splits_reverse() {
        let haystack = b"alpha,beta;gamma";
        let needle = b";";
        let splits: Vec<_> = haystack.sz_rsplits(needle).collect();
        assert_eq!(splits, vec![&b"gamma"[..], &b"alpha,beta"[..]]);
    }

    #[test]
    fn iter_splits_with_empty_parts() {
        let haystack = b"a,,b,";
        let needle = b",";
        let splits: Vec<_> = haystack.sz_splits(needle).collect();
        assert_eq!(splits, vec![b"a", &b""[..], b"b", &b""[..]]);
    }

    #[test]
    fn iter_splits_empty_haystack_yields_one_empty_segment() {
        // Mirrors `"".split(",") == [""]`, not zero segments.
        let matcher = MatcherType::Find(b",");
        let splits: Vec<_> = FindSplits::new(b"", matcher).collect();
        assert_eq!(splits, vec![&b""[..]]);
    }

    #[test]
    fn iter_matches_forward_empty_needle_matches_std() {
        let matches: Vec<_> = FindMatches::new(b"abc", MatcherType::Find(b"")).collect();
        assert_eq!(matches, vec![&b""[..]; 4]);
        assert_eq!("abc".matches("").count(), 4);
    }

    #[test]
    fn iter_matches_reverse_empty_needle() {
        let matches: Vec<_> = RFindMatches::new(b"abc", MatcherType::RFind(b"")).collect();
        assert_eq!(matches, vec![&b""[..]; 4]);
    }

    #[test]
    fn iter_splits_forward_empty_needle() {
        let splits: Vec<_> = FindSplits::new(b"abc", MatcherType::Find(b"")).collect();
        assert_eq!(splits, vec![&b"abc"[..]]);
    }

    #[test]
    fn iter_splits_reverse_empty_needle() {
        let splits: Vec<_> = RFindSplits::new(b"abc", MatcherType::RFind(b"")).collect();
        assert_eq!(splits, vec![&b"abc"[..]]);
    }

    #[test]
    fn utf8_runes_match_std_chars() {
        // Multilingual valid UTF-8, including a long mixed run that spans several decode batches.
        let long_mixed = "Hello, \u{43C}\u{438}\u{440}! \u{4E16}\u{754C} \u{1F30D}\u{1F680} \u{627}\u{644}".repeat(50);
        let samples = [
            "",
            "A",
            "Hello\u{1F30D}",
            "\u{3A9}\u{3BC}\u{3AD}\u{3B3}\u{3B1}",
            long_mixed.as_str(),
        ];
        for text in samples {
            let expected: Vec<char> = text.chars().collect();
            let via_view: Vec<char> = sz::Utf8View::new(text.as_bytes()).iter().collect();
            assert_eq!(
                via_view, expected,
                "rune iteration diverged from std::chars for {:?}",
                text
            );
            let via_trait: Vec<char> = text.as_bytes().sz_utf8_runes().iter().collect();
            assert_eq!(via_trait, expected);
        }
    }

    #[test]
    fn utf8_runes_with_steps_match_default() {
        // The batch width is a performance knob only - every `STEPS` must yield the same codepoints.
        let text = "Hello, \u{43C}\u{438}\u{440}! \u{4E16}\u{754C} \u{1F30D} \u{627}\u{644}".repeat(10);
        let expected: Vec<char> = text.chars().collect();
        let tiny: Vec<char> = sz::Utf8Runes::<1>::with_steps(text.as_bytes()).collect();
        let wide: Vec<char> = sz::Utf8Runes::<256>::with_steps(text.as_bytes()).collect();
        assert_eq!(tiny, expected);
        assert_eq!(wide, expected);
    }

    #[test]
    fn utf8_decode_replaces_ill_formed() {
        // The decoder is total: ill-formed bytes become U+FFFD and it never emits a non-scalar value.
        let ill_formed: [&[u8]; 4] = [b"\x80", b"\xC0\x80", b"\xED\xA0\x80", b"a\xFFb"];
        for bytes in ill_formed {
            let mut runes = [0u32; 16];
            let mut offset = 0;
            while offset < bytes.len() {
                let (consumed, count) = sz::utf8_decode(&bytes[offset..], &mut runes);
                for &rune in &runes[..count] {
                    assert!(
                        rune <= 0x10FFFF && !(0xD800..=0xDFFF).contains(&rune),
                        "non-scalar value 0x{:X}",
                        rune
                    );
                }
                if consumed == 0 {
                    break;
                }
                offset += consumed;
            }
        }
        // A lone 0xFF between two ASCII bytes yields exactly 'a', U+FFFD, 'b' - lossy, never truncated.
        let mut runes = [0u32; 8];
        let (_, count) = sz::utf8_decode(b"a\xFFb", &mut runes);
        assert_eq!(&runes[..count], &['a' as u32, 0xFFFD, 'b' as u32]);
    }

    #[test]
    fn utf8_runes_finalize_truncated_tail() {
        // A string ending mid-codepoint yields the leading runes then a single U+FFFD for the truncated tail,
        // never silently dropping it (matching `String::from_utf8_lossy`).
        let truncated = b"hi\xF0\x9F\x98"; // "hi" + the first 3 bytes of a 4-byte emoji
        let runes: Vec<char> = sz::Utf8View::new(truncated).iter().collect();
        assert_eq!(runes, vec!['h', 'i', '\u{FFFD}']);
    }

    #[test]
    fn iter_splits_forward_skip_empty() {
        // Default KEEP yields empties; skip_empty drops every zero-length segment.
        let haystack = b"a,,b,";
        let needle = b",";
        let kept: Vec<_> = haystack.sz_splits(needle).collect();
        assert_eq!(kept, vec![b"a", &b""[..], b"b", &b""[..]]);
        let nonempty: Vec<_> = haystack.sz_splits(needle).skip_empty().collect();
        assert_eq!(nonempty, vec![b"a", b"b"]);
    }

    #[test]
    fn iter_splits_reverse_skip_empty() {
        // KEEP rsplit of "a,,b," is the reverse of the forward split, empties included.
        let haystack = b"a,,b,";
        let needle = b",";
        let kept: Vec<_> = haystack.sz_rsplits(needle).collect();
        assert_eq!(kept, vec![&b""[..], b"b", &b""[..], b"a"]);
        let nonempty: Vec<_> = haystack.sz_rsplits(needle).skip_empty().collect();
        assert_eq!(nonempty, vec![b"b", b"a"]);
    }

    #[test]
    fn iter_splits_byteset_skip_empty() {
        // Byteset matcher (split on any of ",;"): adjacent delimiters yield empties under the KEEP default.
        let haystack = b",a;;b,";
        let kept: Vec<_> = FindSplits::new(haystack, MatcherType::FindFirstOf(b",;")).collect();
        assert_eq!(kept, vec![&b""[..], b"a", &b""[..], b"b", &b""[..]]);
        let nonempty: Vec<_> = FindSplits::new(haystack, MatcherType::FindFirstOf(b",;"))
            .skip_empty()
            .collect();
        assert_eq!(nonempty, vec![b"a", b"b"]);
    }

    #[test]
    fn iter_matches_with_overlaps() {
        let haystack = b"aaaa";
        let needle = b"aa";
        // Default is non-overlapping; `.overlapping()` opts into the compile-time Overlapping policy.
        let non_overlapping: Vec<_> = haystack.sz_matches(needle).collect();
        assert_eq!(non_overlapping, vec![b"aa", b"aa"]);
        let matches: Vec<_> = haystack.sz_matches(needle).overlapping().collect();
        assert_eq!(matches, vec![b"aa", b"aa", b"aa"]);
    }

    #[test]
    fn iter_splits_with_utf8_haystack() {
        let haystack = "こんにちは,世界".as_bytes();
        let needle = b",";
        let splits: Vec<_> = haystack.sz_splits(needle).collect();
        assert_eq!(splits, vec!["こんにちは".as_bytes(), "世界".as_bytes()]);
    }

    #[test]
    fn iter_find_first_of() {
        let haystack = b"hello world";
        let needles = b"or";
        let matches: Vec<_> = haystack.sz_find_first_of(needles).collect();
        assert_eq!(matches, vec![b"o", b"o", b"r"]);
    }

    #[test]
    fn iter_find_last_of() {
        let haystack = b"hello world";
        let needles = b"or";
        let matches: Vec<_> = haystack.sz_find_last_of(needles).collect();
        assert_eq!(matches, vec![b"r", b"o", b"o"]);
    }

    #[test]
    fn iter_find_first_not_of() {
        let haystack = b"aabbbcccd";
        let needles = b"ab";
        let matches: Vec<_> = haystack.sz_find_first_not_of(needles).collect();
        assert_eq!(matches, vec![b"c", b"c", b"c", b"d"]);
    }

    #[test]
    fn iter_find_last_not_of() {
        let haystack = b"aabbbcccd";
        let needles = b"cd";
        let matches: Vec<_> = haystack.sz_find_last_not_of(needles).collect();
        assert_eq!(matches, vec![b"b", b"b", b"b", b"a", b"a"]);
    }

    #[test]
    fn iter_find_first_of_empty_needles() {
        let haystack = b"hello world";
        let needles = b"";
        let matches: Vec<_> = haystack.sz_find_first_of(needles).collect();
        assert_eq!(matches, Vec::<&[u8]>::new());
    }

    #[test]
    fn iter_find_last_of_empty_haystack() {
        let haystack = b"";
        let needles = b"abc";
        let matches: Vec<_> = haystack.sz_find_last_of(needles).collect();
        assert_eq!(matches, Vec::<&[u8]>::new());
    }

    #[test]
    fn iter_find_first_not_of_all_matching() {
        let haystack = b"aaabbbccc";
        let needles = b"abc";
        let matches: Vec<_> = haystack.sz_find_first_not_of(needles).collect();
        assert_eq!(matches, Vec::<&[u8]>::new());
    }

    #[test]
    fn iter_find_last_not_of_all_not_matching() {
        let haystack = b"hello world";
        let needles = b"xyz";
        let matches: Vec<_> = haystack.sz_find_last_not_of(needles).collect();
        assert_eq!(
            matches,
            vec![b"d", b"l", b"r", b"o", b"w", b" ", b"o", b"l", b"l", b"e", b"h"]
        );
    }

    #[test]
    fn iter_find_matches_overlapping() {
        let haystack = b"aaaa";
        let matcher = MatcherType::Find(b"aa");
        let matches: Vec<_> = FindMatches::new(haystack, matcher).overlapping().collect();
        assert_eq!(matches, vec![&b"aa"[..], &b"aa"[..], &b"aa"[..]]);
    }

    #[test]
    fn iter_find_matches_non_overlapping() {
        let haystack = b"aaaa";
        let matcher = MatcherType::Find(b"aa");
        let matches: Vec<_> = FindMatches::new(haystack, matcher).collect();
        assert_eq!(matches, vec![&b"aa"[..], &b"aa"[..]]);
    }

    #[test]
    fn iter_rfind_matches_overlapping() {
        let haystack = b"aaaa";
        let matcher = MatcherType::RFind(b"aa");
        let matches: Vec<_> = RFindMatches::new(haystack, matcher).overlapping().collect();
        assert_eq!(matches, vec![&b"aa"[..], &b"aa"[..], &b"aa"[..]]);
    }

    #[test]
    fn iter_rfind_matches_non_overlapping() {
        let haystack = b"aaaa";
        let matcher = MatcherType::RFind(b"aa");
        let matches: Vec<_> = RFindMatches::new(haystack, matcher).collect();
        assert_eq!(matches, vec![&b"aa"[..], &b"aa"[..]]);
    }

    #[test]
    fn const_apis() {
        // Each constant is built at compile time, so dropping a `const fn` breaks the build, not this run.
        const SPAN: sz::IndexSpan = sz::IndexSpan::new(6, 5);
        const WHITESPACE: sz::Byteset = sz::Byteset::from_bytes(b" \t\r\n");
        const NEEDLE: sz::Utf8UncasedNeedle = sz::Utf8UncasedNeedle::new(b"hello");
        const TOP_TWO_DESCENDING: sz::ArgsortOptions = sz::ArgsortOptions {
            reverse: false,
            uncased: false,
            top: None,
        }
        .reversed()
        .top(2);

        assert_eq!(SPAN.extract(b"Hello World"), b"World");
        assert_eq!(sz::find_byteset("ab cd", WHITESPACE), Some(2));
        assert_eq!(sz::utf8_uncased_search(b"say HELLO now", &NEEDLE), Some((4, 5)));

        let fruits = ["banana", "apple", "cherry"];
        let mut order = [0; 3];
        sz::argsort(&fruits, &mut order, TOP_TWO_DESCENDING).expect("argsort failed");
        assert_eq!(fruits[order[0]], "cherry");
    }

    #[test]
    fn argsort_default() {
        // Test with a slice of string literals.
        let fruits = ["banana", "apple", "cherry"];
        let mut order = [0; 3]; // output buffer must be at least fruits.len()
        sz::argsort(&fruits, &mut order, Default::default()).expect("argsort failed");

        // Reconstruct sorted order using the returned indices.
        let sorted_from_api: Vec<_> = order.iter().map(|&i| fruits[i]).collect();

        // Compute expected order using the standard sort.
        let mut expected = fruits.to_vec();
        expected.sort();

        assert_eq!(sorted_from_api, expected);
    }

    #[test]
    fn argsort_by_custom() {
        // Define a custom type.
        #[derive(Debug)]
        #[allow(dead_code)]
        struct Person {
            name: &'static str,
            age: u32, //? We won't use this field for intersection
        }

        let people = [
            Person {
                name: "Charlie",
                age: 30,
            },
            Person { name: "Alice", age: 25 },
            Person { name: "Bob", age: 40 },
        ];
        let mut order = [0; 3];
        sz::argsort_by(|i: usize| people[i].name.as_bytes(), &mut order, Default::default())
            .expect("argsort_by failed");

        let sorted_from_api: Vec<_> = order.iter().map(|&i| people[i].name).collect();

        // Compute expected order using standard sorting on the names.
        let mut expected: Vec<_> = people.iter().map(|p| p.name).collect();
        expected.sort();

        assert_eq!(sorted_from_api, expected);
    }

    #[test]
    fn argsort_reverse_is_stable() {
        // Two equal "beta"s must keep their input order even when sorting descending.
        let labels = ["beta", "alpha", "beta", "gamma"];
        let mut order = [0; 4];
        sz::argsort(&labels, &mut order, sz::ArgsortOptions::default().reversed()).expect("argsort failed");
        let sorted: Vec<_> = order.iter().map(|&i| labels[i]).collect();
        assert_eq!(sorted, vec!["gamma", "beta", "beta", "alpha"]);
        // Stability: the first "beta" (index 0) precedes the second (index 2).
        let beta_positions: Vec<_> = order.iter().filter(|&&i| labels[i] == "beta").copied().collect();
        assert_eq!(beta_positions, vec![0, 2]);
    }

    #[test]
    fn argsort_top_k_prefix() {
        let words = ["delta", "alpha", "echo", "bravo", "charlie"];
        let mut order = [0; 5];
        sz::argsort(&words, &mut order, sz::ArgsortOptions::default().top(2)).expect("argsort failed");
        // Only the first two entries are guaranteed sorted (the two smallest).
        assert_eq!(words[order[0]], "alpha");
        assert_eq!(words[order[1]], "bravo");
        // `order` is still a full permutation.
        let mut seen = order.to_vec();
        seen.sort();
        assert_eq!(seen, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn argsort_uncased() {
        let labels = ["Banana", "apple", "BANANA", "Apple"];
        let mut order = [0; 4];
        sz::argsort(&labels, &mut order, sz::ArgsortOptions::default().uncased()).expect("argsort failed");
        let sorted: Vec<_> = order.iter().map(|&i| labels[i]).collect();
        // Fold-equal strings group together and stay in input order: "apple","Apple" then "Banana","BANANA".
        assert_eq!(sorted, vec!["apple", "Apple", "Banana", "BANANA"]);
    }

    #[test]
    #[cfg(feature = "std")]
    fn intersection_default() {
        // Two slices of string literals.
        let set1 = ["banana", "apple", "cherry"];
        let set2 = ["cherry", "orange", "pineapple", "banana"];
        // Output buffers: size must be at least min(set1.len(), set2.len()).
        let mut out1 = [0; 3];
        let mut out2 = [0; 3];

        let n = sz::intersection(&set1, &set2, 0, &mut out1, &mut out2).expect("intersection failed");
        assert!(n <= set1.len().min(set2.len()));

        // For simplicity, we will compare the intersection from the first set.
        // Our API returns indices (for set1 in out1).
        let common_from_api: HashSet<_> = out1[..n].iter().map(|&i| set1[i]).collect();

        // Compute the expected intersection using a `HashSet`.
        let expected: HashSet<_> = set1
            .iter()
            .cloned()
            .collect::<HashSet<_>>()
            .intersection(&set2.iter().cloned().collect())
            .cloned()
            .collect();

        assert_eq!(common_from_api, expected);
    }

    #[test]
    #[cfg(feature = "std")]
    fn intersection_by_custom() {
        // Define a custom type.
        #[derive(Debug)]
        #[allow(dead_code)]
        struct Person {
            name: &'static str,
            age: u32, //? We won't use this field for intersection
        }

        let group1 = [
            Person { name: "Alice", age: 25 },
            Person { name: "Bob", age: 30 },
            Person {
                name: "Charlie",
                age: 35,
            },
        ];
        let group2 = [
            Person { name: "David", age: 40 },
            Person {
                name: "Charlie",
                age: 50,
            },
            Person { name: "Alice", age: 60 },
        ];
        let mut out1 = [0; 3];
        let mut out2 = [0; 3];

        let n = sz::intersection_by(
            |i: sz::SortedIdx| group1[i].name.as_bytes(),
            |j: sz::SortedIdx| group2[j].name.as_bytes(),
            0,
            &mut out1,
            &mut out2,
        )
        .expect("intersection_by failed");
        assert!(n <= group1.len().min(group2.len()));

        // Use the indices for `group1` to get common names.
        let common_from_api: HashSet<_> = out1[..n].iter().map(|&i| group1[i].name).collect();

        // Compute expected common names using a `HashSet`.
        let expected: HashSet<_> = group1
            .iter()
            .map(|p| p.name)
            .collect::<HashSet<_>>()
            .intersection(&group2.iter().map(|p| p.name).collect())
            .cloned()
            .collect();

        assert_eq!(common_from_api, expected);
    }

    #[test]
    #[should_panic(expected = "BadAlloc")]
    fn intersection_size_checks() {
        let mut indices = [0usize; 10];
        let mut indices2 = [0usize; 5];
        let data = vec![0x41u8; 12];

        sz::intersection_by(|_: usize| &data, |_: usize| &data, 1, &mut indices, &mut indices2).unwrap();
    }

    #[test]
    fn intersection_sequences_sharing_an_empty_string() {
        // Regression check for sequences that are each individually duplicate-free but happen
        // to share an empty string - a corner case that must keep working correctly.
        let set1 = ["", "p", "q"];
        let set2 = ["", "z"];
        let mut positions1 = [0usize; 2];
        let mut positions2 = [0usize; 2];
        let matched = sz::intersection(&set1, &set2, 0, &mut positions1, &mut positions2).expect("intersection failed");
        assert_eq!(matched, 1);
        assert_eq!(set1[positions1[0]], set2[positions2[0]]);
    }

    #[test]
    fn sha256_empty() {
        let hash = sz::Sha256::hash(b"");
        let expected = [
            0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae,
            0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
        ];
        assert_eq!(hash, expected);
    }

    #[test]
    fn sha256_abc() {
        let hash = sz::Sha256::hash(b"abc");
        let expected = [
            0xba, 0x78, 0x16, 0xbf, 0x8f, 0x01, 0xcf, 0xea, 0x41, 0x41, 0x40, 0xde, 0x5d, 0xae, 0x22, 0x23, 0xb0, 0x03,
            0x61, 0xa3, 0x96, 0x17, 0x7a, 0x9c, 0xb4, 0x10, 0xff, 0x61, 0xf2, 0x00, 0x15, 0xad,
        ];
        assert_eq!(hash, expected);
    }

    #[test]
    fn sha256_incremental() {
        let mut hasher = sz::Sha256::new();
        hasher.update(b"ab");
        hasher.update(b"c");
        let hash = hasher.digest();
        let expected = [
            0xba, 0x78, 0x16, 0xbf, 0x8f, 0x01, 0xcf, 0xea, 0x41, 0x41, 0x40, 0xde, 0x5d, 0xae, 0x22, 0x23, 0xb0, 0x03,
            0x61, 0xa3, 0x96, 0x17, 0x7a, 0x9c, 0xb4, 0x10, 0xff, 0x61, 0xf2, 0x00, 0x15, 0xad,
        ];
        assert_eq!(hash, expected);
    }

    #[test]
    fn sha256_multistate_matches_single() {
        // Lane counts bracketing both vector widths, with ragged lengths and an empty lane
        for lanes_count in [1usize, 7, 8, 9, 16, 17, 33] {
            let messages: Vec<Vec<u8>> = (0..lanes_count)
                .map(|lane_index| vec![b'a' + (lane_index % 26) as u8; lane_index * 137 % 5000])
                .collect();

            let mut states = vec![sz::Sha256::new(); lanes_count];

            // Feed each lane in three uneven slices, so partial blocks carry across calls
            let mut offsets = vec![0usize; lanes_count];
            for slice_index in 0..3 {
                let ranges: Vec<(usize, usize)> = (0..lanes_count)
                    .map(|lane_index| {
                        let remaining = messages[lane_index].len() - offsets[lane_index];
                        let take = if slice_index == 2 { remaining } else { remaining / 3 };
                        let start = offsets[lane_index];
                        offsets[lane_index] += take;
                        (start, start + take)
                    })
                    .collect();
                sz::sha256_multistate_update_by(&mut states, |lane_index| {
                    let (start, end) = ranges[lane_index];
                    &messages[lane_index][start..end]
                })
                .expect("one chunk per lane");
            }

            let mut digests = vec![[0u8; 32]; lanes_count];
            sz::sha256_multistate_digest(&states, &mut digests).expect("one digest per lane");
            for lane_index in 0..lanes_count {
                assert_eq!(digests[lane_index], sz::Sha256::hash(&messages[lane_index]));
            }
        }
    }

    #[test]
    fn sha256_multistate_borrows_owned_strings() {
        // The generic front door must take `Vec<String>` without an intermediate slice-of-slices.
        let heads: Vec<String> = vec!["Hello, ".into(), "Goodbye, ".into()];
        let tails: Vec<Vec<u8>> = vec![b"world!".to_vec(), b"world!".to_vec()];

        let mut states = vec![sz::Sha256::new(); 2];
        sz::sha256_multistate_update(&mut states, &heads).expect("one chunk per lane");
        sz::sha256_multistate_update(&mut states, &tails).expect("one chunk per lane");

        let mut digests = vec![[0u8; sz::SHA256_DIGEST_LENGTH]; 2];
        sz::sha256_multistate_digest(&states, &mut digests).expect("one digest per lane");
        assert_eq!(digests[0], sz::Sha256::hash(b"Hello, world!"));
        assert_eq!(digests[1], sz::Sha256::hash(b"Goodbye, world!"));
    }

    #[test]
    fn sha256_multistate_size_checks() {
        let mut states = vec![sz::Sha256::new(); 3];
        let too_few: Vec<&[u8]> = vec![b"a".as_slice(), b"b".as_slice()];
        assert_eq!(sz::sha256_multistate_update(&mut states, &too_few), Err(sz::Status::BadAlloc));

        let mut too_few_digests = vec![[0u8; sz::SHA256_DIGEST_LENGTH]; 2];
        assert_eq!(
            sz::sha256_multistate_digest(&states, &mut too_few_digests),
            Err(sz::Status::BadAlloc)
        );
    }

    #[test]
    fn sha256_long() {
        let msg = b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";
        let hash = sz::Sha256::hash(msg);
        let expected = [
            0x24, 0x8d, 0x6a, 0x61, 0xd2, 0x06, 0x38, 0xb8, 0xe5, 0xc0, 0x26, 0x93, 0x0c, 0x3e, 0x60, 0x39, 0xa3, 0x3c,
            0xe4, 0x59, 0x64, 0xff, 0x21, 0x67, 0xf6, 0xec, 0xed, 0xd4, 0x19, 0xdb, 0x06, 0xc1,
        ];
        assert_eq!(hash, expected);
    }

    #[test]
    fn hmac_sha256_basic() {
        // Degenerate case: an empty key is zero-padded to a full block, an empty message adds nothing.
        let key = b"";
        let message = b"";
        let mac = sz::hmac_sha256(key, message);
        // HMAC-SHA256("", "") = b613...
        let expected = [
            0xb6, 0x13, 0x67, 0x9a, 0x08, 0x14, 0xd9, 0xec, 0x77, 0x2f, 0x95, 0xd7, 0x78, 0xc3, 0x5f, 0xc5, 0xff, 0x16,
            0x97, 0xc4, 0x93, 0x71, 0x56, 0x53, 0xc6, 0xc7, 0x12, 0x14, 0x42, 0x92, 0xc5, 0xad,
        ];
        assert_eq!(mac, expected);
    }

    #[test]
    fn hmac_sha256_multistate_matches_single() {
        // Lane counts bracketing both vector widths, with ragged lengths, an empty message, and keys on
        // either side of the one-block boundary where the key is replaced by its own digest.
        for key_length in [0usize, 16, 64, 65, 200] {
            let key: Vec<u8> = (0..key_length).map(|index| (index % 251) as u8).collect();
            for lanes_count in [1usize, 7, 8, 9, 16, 17, 33] {
                let messages: Vec<Vec<u8>> = (0..lanes_count)
                    .map(|lane_index| vec![b'a' + (lane_index % 26) as u8; lane_index * 137 % 5000])
                    .collect();

                let mut states = vec![sz::Sha256::new(); lanes_count];
                let mut tags = vec![[0u8; sz::SHA256_DIGEST_LENGTH]; lanes_count];
                sz::hmac_sha256_multistate(&key, &messages, &mut states, &mut tags).expect("one tag per message");

                for lane_index in 0..lanes_count {
                    assert_eq!(tags[lane_index], sz::hmac_sha256(&key, &messages[lane_index]));
                }
            }
        }
    }

    #[test]
    fn hmac_sha256_multistate_size_checks() {
        let messages: Vec<&[u8]> = vec![b"a".as_slice(), b"b".as_slice()];
        let mut states = vec![sz::Sha256::new(); 2];
        let mut too_few = vec![[0u8; sz::SHA256_DIGEST_LENGTH]; 1];
        assert_eq!(
            sz::hmac_sha256_multistate(b"k", &messages, &mut states, &mut too_few),
            Err(sz::Status::BadAlloc)
        );
    }

    #[test]
    fn hmac_sha256_rfc4231_case1() {
        // The published vector, so this checks against the standard rather than against ourselves.
        let key = [0x0bu8; 20];
        let mac = sz::hmac_sha256(&key, b"Hi There");
        let expected = [
            0xb0, 0x34, 0x4c, 0x61, 0xd8, 0xdb, 0x38, 0x53, 0x5c, 0xa8, 0xaf, 0xce, 0xaf, 0x0b, 0xf1, 0x2b, 0x88, 0x1d,
            0xc2, 0x00, 0xc9, 0x83, 0x3d, 0xa7, 0x26, 0xe9, 0x37, 0x6c, 0x2e, 0x32, 0xcf, 0xf7,
        ];
        assert_eq!(mac, expected);
    }

    #[test]
    fn hmac_sha256_short_key() {
        // Test with short key and message
        let key = b"key";
        let message = b"The quick brown fox jumps over the lazy dog";
        let mac = sz::hmac_sha256(key, message);
        // HMAC-SHA256("key", "The quick brown fox jumps over the lazy dog")
        let expected = [
            0xf7, 0xbc, 0x83, 0xf4, 0x30, 0x53, 0x84, 0x24, 0xb1, 0x32, 0x98, 0xe6, 0xaa, 0x6f, 0xb1, 0x43, 0xef, 0x4d,
            0x59, 0xa1, 0x49, 0x46, 0x17, 0x59, 0x97, 0x47, 0x9d, 0xbc, 0x2d, 0x1a, 0x3c, 0xd8,
        ];
        assert_eq!(mac, expected);
    }

    #[test]
    fn hmac_sha256_long_key() {
        // Test with key longer than block size (> 64 bytes)
        let key = b"this is a very long key that exceeds the SHA256 block size of 64 bytes for testing purposes";
        let message = b"message";
        let mac = sz::hmac_sha256(key, message);
        // Expected value computed with Python: hmac.new(key, message, hashlib.sha256).digest()
        let expected = [
            0xd1, 0x3f, 0xdb, 0x7b, 0xe0, 0x9a, 0x9e, 0x07, 0x04, 0xc6, 0x5b, 0xd7, 0x85, 0xa6, 0x33, 0xbb, 0xc0, 0xee,
            0x2b, 0x99, 0xef, 0xd6, 0x32, 0x2c, 0xa9, 0x4c, 0xd3, 0x2c, 0x1e, 0x45, 0x09, 0xfd,
        ];
        assert_eq!(mac, expected);
    }

    /// Decodes a hexadecimal literal into `output`, returning how many bytes were written.
    fn bytes_from_hex(hex: &str, output: &mut [u8]) -> usize {
        let digits = hex.as_bytes();
        let written = digits.len() / 2;
        for index in 0..written {
            let high = (digits[index * 2] as char).to_digit(16).expect("hexadecimal digit");
            let low = (digits[index * 2 + 1] as char).to_digit(16).expect("hexadecimal digit");
            output[index] = ((high << 4) | low) as u8;
        }
        written
    }

    /// One published Galois/counter mode vector, spelled out rather than derived from any backend.
    struct KnownGcmVector {
        secret: &'static str,
        nonce: &'static str,
        associated: &'static str,
        plaintext: &'static str,
        ciphertext: &'static str,
        tag: &'static str,
    }

    /// Cases 13 through 16 of McGrew and Viega's Galois/counter mode note, the AES-256 vectors
    /// NIST's validation suite is built from, shared verbatim with the C++ suite in `test/cipher.cpp`
    /// so both agree on ground truth.
    const KNOWN_GCM_VECTORS: [KnownGcmVector; 4] = [
        // Empty message, empty associated data.
        KnownGcmVector {
            secret: "0000000000000000000000000000000000000000000000000000000000000000",
            nonce: "000000000000000000000000",
            associated: "",
            plaintext: "",
            ciphertext: "",
            tag: "530f8afbc74536b9a963b4f1c4cb738b",
        },
        // One zero block, empty associated data.
        KnownGcmVector {
            secret: "0000000000000000000000000000000000000000000000000000000000000000",
            nonce: "000000000000000000000000",
            associated: "",
            plaintext: "00000000000000000000000000000000",
            ciphertext: "cea7403d4d606b6e074ec5d3baf39d18",
            tag: "d0d1c8a799996bf0265b98b5d48ab919",
        },
        // Four whole blocks, empty associated data.
        KnownGcmVector {
            secret: "feffe9928665731c6d6a8f9467308308feffe9928665731c6d6a8f9467308308",
            nonce: "cafebabefacedbaddecaf888",
            associated: "",
            plaintext: concat!(
                "d9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a72",
                "1c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b391aafd255"
            ),
            ciphertext: concat!(
                "522dc1f099567d07f47f37a32a84427d643a8cdcbfe5c0c97598a2bd2555d1aa",
                "8cb08e48590dbb3da7b08b1056828838c5f61e6393ba7a0abcc9f662898015ad"
            ),
            tag: "b094dac5d93471bdec1a502270e3cc6c",
        },
        // A partial trailing block plus associated data, which exercises both zero pads.
        KnownGcmVector {
            secret: "feffe9928665731c6d6a8f9467308308feffe9928665731c6d6a8f9467308308",
            nonce: "cafebabefacedbaddecaf888",
            associated: "feedfacedeadbeeffeedfacedeadbeefabaddad2",
            plaintext: concat!(
                "d9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a72",
                "1c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39"
            ),
            ciphertext: concat!(
                "522dc1f099567d07f47f37a32a84427d643a8cdcbfe5c0c97598a2bd2555d1aa",
                "8cb08e48590dbb3da7b08b1056828838c5f61e6393ba7a0abcc9f662"
            ),
            tag: "76fc6ece0f4e1768cddf8853bb2d551b",
        },
    ];

    #[test]
    fn aes256_counter_round_trip() {
        let secret = [0x2Bu8; sz::AES256_KEY_LENGTH];
        let nonce = [0x07u8; sz::AES256_NONCE_LENGTH];
        let key = sz::Aes256CtrKey::new(&secret);
        let plaintext = b"counter mode is its own inverse, so one call serves both directions";

        let mut ciphertext = vec![0u8; plaintext.len()];
        key.xor_into(&nonce, 0, plaintext, &mut ciphertext);
        assert_ne!(ciphertext.as_slice(), &plaintext[..]);

        let mut recovered = vec![0u8; plaintext.len()];
        key.xor_into(&nonce, 0, &ciphertext, &mut recovered);
        assert_eq!(recovered.as_slice(), &plaintext[..]);

        // Transforming in place must agree with transforming into a separate buffer.
        let mut in_place = plaintext.to_vec();
        key.xor_in_place(&nonce, 0, &mut in_place);
        assert_eq!(in_place, ciphertext);
    }

    #[test]
    fn aes256_counter_seek() {
        let secret = [0x3Cu8; sz::AES256_KEY_LENGTH];
        let nonce = [0x5Du8; sz::AES256_NONCE_LENGTH];
        let key = sz::Aes256CtrKey::new(&secret);
        let whole: Vec<u8> = (0..512u32).map(|index| (index * 31 + 7) as u8).collect();

        let mut from_zero = vec![0u8; whole.len()];
        key.xor_into(&nonce, 0, &whole, &mut from_zero);

        // Seeking is the whole reason counter mode is exposed separately, so every offset - block
        // aligned or not - must land on the keystream the from-zero transformation used.
        for offset in 0..200usize {
            let mut sliced = vec![0u8; whole.len() - offset];
            key.xor_into(&nonce, offset as u64, &whole[offset..], &mut sliced);
            assert_eq!(sliced.as_slice(), &from_zero[offset..]);
        }
    }

    #[test]
    fn aes256_gcm_known_answers() {
        for vector in KNOWN_GCM_VECTORS.iter() {
            let mut secret = [0u8; sz::AES256_KEY_LENGTH];
            let mut nonce = [0u8; sz::AES256_NONCE_LENGTH];
            let mut expected_tag = [0u8; sz::AES256_TAG_LENGTH];
            let mut associated = [0u8; 32];
            let mut plaintext = [0u8; 64];
            let mut expected = [0u8; 64];
            bytes_from_hex(vector.secret, &mut secret);
            bytes_from_hex(vector.nonce, &mut nonce);
            let associated_length = bytes_from_hex(vector.associated, &mut associated);
            let length = bytes_from_hex(vector.plaintext, &mut plaintext);
            bytes_from_hex(vector.ciphertext, &mut expected);
            bytes_from_hex(vector.tag, &mut expected_tag);
            let associated = &associated[..associated_length];

            let key = sz::Aes256GcmKey::new(&secret);
            let mut produced = vec![0u8; length];
            let tag = key.encrypt_into(&nonce, associated, &plaintext[..length], &mut produced);
            assert_eq!(produced.as_slice(), &expected[..length]);
            assert_eq!(tag, expected_tag);

            let mut recovered = vec![0u8; length];
            key.decrypt_into(&nonce, associated, &produced, &mut recovered, &tag)
                .expect("the genuine tag must verify");
            assert_eq!(recovered.as_slice(), &plaintext[..length]);

            // In place must reach the same ciphertext and come back the same way.
            let mut in_place = plaintext[..length].to_vec();
            assert_eq!(key.encrypt_in_place(&nonce, associated, &mut in_place), expected_tag);
            assert_eq!(in_place, produced);
            key.decrypt_in_place(&nonce, associated, &mut in_place, &tag)
                .expect("the genuine tag must verify");
            assert_eq!(in_place.as_slice(), &plaintext[..length]);
        }
    }

    #[test]
    fn aes256_gcm_forged_tag() {
        let secret = [0x11u8; sz::AES256_KEY_LENGTH];
        let nonce = [0x22u8; sz::AES256_NONCE_LENGTH];
        let associated = b"routing header";
        let plaintext = b"the tag is the only thing between the reader and forged plaintext";
        let key = sz::Aes256GcmKey::new(&secret);

        let mut ciphertext = vec![0u8; plaintext.len()];
        let tag = key.encrypt_into(&nonce, associated, plaintext, &mut ciphertext);

        // A single flipped tag bit must be refused, and a caller who drops the error must not find
        // forged plaintext waiting in the buffer.
        let mut forged_tag = tag;
        forged_tag[0] ^= 0x01;
        let mut recovered = vec![0xA5u8; plaintext.len()];
        assert_eq!(
            key.decrypt_into(&nonce, associated, &ciphertext, &mut recovered, &forged_tag),
            Err(sz::AuthenticationError::TagMismatch)
        );
        assert!(recovered.iter().all(|byte| *byte == 0));

        // The associated data is authenticated too, so changing it must be refused just as loudly.
        let mut recovered = vec![0xA5u8; plaintext.len()];
        assert_eq!(
            key.decrypt_into(&nonce, b"forged header", &ciphertext, &mut recovered, &tag),
            Err(sz::AuthenticationError::TagMismatch)
        );
        assert!(recovered.iter().all(|byte| *byte == 0));

        // The genuine tag still recovers the message.
        let mut recovered = vec![0u8; plaintext.len()];
        key.decrypt_into(&nonce, associated, &ciphertext, &mut recovered, &tag)
            .expect("the genuine tag must verify");
        assert_eq!(recovered.as_slice(), &plaintext[..]);
    }

    #[test]
    fn aes256_gcm_streaming() {
        let secret = [0x9Eu8; sz::AES256_KEY_LENGTH];
        let nonce = [0x4Fu8; sz::AES256_NONCE_LENGTH];
        let associated = b"chunked records still authenticate their header";
        let plaintext: Vec<u8> = (0..300u32).map(|index| (index * 17 + 3) as u8).collect();
        let key = sz::Aes256GcmKey::new(&secret);

        let mut whole = vec![0u8; plaintext.len()];
        let whole_tag = key.encrypt_into(&nonce, associated, &plaintext, &mut whole);

        // A chunk boundary must be invisible: the keystream block and the hash block both straddle it.
        for chunk in [1usize, 7, 15, 16, 17, 64] {
            let mut streamed = vec![0u8; plaintext.len()];
            let mut encryptor = sz::Aes256GcmEncryptor::new(&key, &nonce);
            encryptor.associate(associated);
            for offset in (0..plaintext.len()).step_by(chunk) {
                let taken = chunk.min(plaintext.len() - offset);
                encryptor.encrypt_into(
                    &plaintext[offset..offset + taken],
                    &mut streamed[offset..offset + taken],
                );
            }
            assert_eq!(streamed, whole);
            assert_eq!(encryptor.digest(), whole_tag);

            let mut recovered = vec![0u8; plaintext.len()];
            let mut decryptor = sz::Aes256GcmDecryptor::new(&key, &nonce);
            decryptor.associate(associated);
            for offset in (0..plaintext.len()).step_by(chunk) {
                let taken = chunk.min(plaintext.len() - offset);
                decryptor
                    .decrypt_unverified_into(&whole[offset..offset + taken], &mut recovered[offset..offset + taken]);
            }
            decryptor.verify(&whole_tag).expect("the genuine tag must verify");
            assert_eq!(recovered, plaintext);
        }

        // The streaming path emits bytes before anything authenticates them, so the refusal comes
        // from `verify` and the caller is left holding output it must discard itself. That is the
        // risk `decrypt_unverified_into` names, and the reason the one-shot call exists.
        let mut forged_tag = whole_tag;
        forged_tag[15] ^= 0x80;
        let mut recovered = vec![0u8; plaintext.len()];
        let mut decryptor = sz::Aes256GcmDecryptor::new(&key, &nonce);
        decryptor.associate(associated);
        decryptor.decrypt_unverified_into(&whole, &mut recovered);
        assert_eq!(decryptor.verify(&forged_tag), Err(sz::AuthenticationError::TagMismatch));
        assert_eq!(recovered, plaintext);
    }

    /// A dropped encryptor must leave none of its payload behind, which a passing build cannot show.
    ///
    /// The encryptor lives in storage this test owns so the bytes can be read back. Only the named
    /// fields are checked; the six trailing padding bytes are never written by the C core.
    #[test]
    fn aes256_gcm_streaming_scrubs_on_drop() {
        use core::mem::{size_of, MaybeUninit};

        let secret = [0xA5u8; sz::AES256_KEY_LENGTH];
        let nonce = [0x5Au8; sz::AES256_NONCE_LENGTH];
        let key = sz::Aes256GcmKey::new(&secret);

        let mut slot = MaybeUninit::<sz::Aes256GcmEncryptor>::uninit();
        unsafe { slot.as_mut_ptr().write(sz::Aes256GcmEncryptor::new(&key, &nonce)) };

        // Drive it so the keystream and the pending block hold live material rather than zeros.
        let mut text = *b"material that must not survive the drop";
        unsafe { (*slot.as_mut_ptr()).encrypt_in_place(&mut text) };
        unsafe { core::ptr::drop_in_place(slot.as_mut_ptr()) };

        let payload =
            unsafe { core::slice::from_raw_parts(slot.as_ptr() as *const u8, size_of::<sz::Aes256GcmEncryptor>()) };
        let named_fields = &payload[..payload.len() - 6];
        let surviving = named_fields.iter().filter(|byte| **byte != 0).count();
        assert_eq!(
            surviving, 0,
            "{surviving} bytes of a dropped encryptor's payload survived"
        );
    }

    #[test]
    fn aes256_gcm_decryptor_alone() {
        let secret = [0x6Du8; sz::AES256_KEY_LENGTH];
        let nonce = [0x1Au8; sz::AES256_NONCE_LENGTH];
        let associated = b"a header the caller happens to hold in two pieces";
        let plaintext: Vec<u8> = (0..201u32).map(|index| (index * 29 + 11) as u8).collect();
        let key = sz::Aes256GcmKey::new(&secret);

        let mut ciphertext = vec![0u8; plaintext.len()];
        let tag = key.encrypt_into(&nonce, associated, &plaintext, &mut ciphertext);

        // The decryptor hashes the bytes it is given rather than the bytes it emits, so both emit
        // paths must reach the tag the one-shot call made, and the header may arrive in any pieces.
        let mut opened = vec![0u8; plaintext.len()];
        let mut decryptor = sz::Aes256GcmDecryptor::new(&key, &nonce);
        decryptor.associate(&associated[..17]);
        decryptor.associate(&associated[17..]);
        for offset in (0..ciphertext.len()).step_by(23) {
            let taken = 23.min(ciphertext.len() - offset);
            decryptor.decrypt_unverified_into(&ciphertext[offset..offset + taken], &mut opened[offset..offset + taken]);
        }
        decryptor.verify(&tag).expect("the genuine tag must verify");
        assert_eq!(opened, plaintext);

        // In place both buffers live at one address, which is the case the direction of the hash
        // could hide in, so it must agree byte for byte with the separate-buffer opening.
        let mut opened_in_place = ciphertext.clone();
        let mut decryptor = sz::Aes256GcmDecryptor::new(&key, &nonce);
        decryptor.associate(associated);
        for chunk in opened_in_place.chunks_mut(23) {
            decryptor.decrypt_unverified_in_place(chunk);
        }
        decryptor.verify(&tag).expect("the genuine tag must verify");
        assert_eq!(opened_in_place, plaintext);

        // A decryptor that never absorbed the header authenticates a shorter message than the sender
        // sealed, so the same tag must be refused.
        let mut unassociated = ciphertext.clone();
        let mut decryptor = sz::Aes256GcmDecryptor::new(&key, &nonce);
        decryptor.decrypt_unverified_in_place(&mut unassociated);
        assert_eq!(decryptor.verify(&tag), Err(sz::AuthenticationError::TagMismatch));

        // A decryptor started on the wrong nonce emits neither the plaintext nor a matching tag.
        let mut wrong_nonce = nonce;
        wrong_nonce[0] ^= 0x01;
        let mut mismatched = ciphertext.clone();
        let mut decryptor = sz::Aes256GcmDecryptor::new(&key, &wrong_nonce);
        decryptor.associate(associated);
        decryptor.decrypt_unverified_in_place(&mut mismatched);
        assert_eq!(decryptor.verify(&tag), Err(sz::AuthenticationError::TagMismatch));
        assert_ne!(mismatched, plaintext);
    }

    #[test]
    #[should_panic(expected = "target must be at least as long as source")]
    fn copy_size_checks() {
        let long: Vec<u8> = vec![0; 20];
        let mut less_long: Vec<u8> = vec![0; 10];

        sz::copy(&mut less_long, &long);
    }

    #[test]
    #[should_panic(expected = "target must be at least as long as source")]
    fn move_size_checks() {
        let long: Vec<u8> = vec![0; 20];
        let mut less_long: Vec<u8> = vec![0; 10];

        sz::move_(&mut less_long, &long);
    }

    #[test]
    #[should_panic(expected = "target must be at least as long as source")]
    fn lookup_size_checks() {
        let long: Vec<u8> = vec![0; 20];
        let mut less_long: Vec<u8> = vec![0; 10];

        let lut: [u8; 256] = (0..=255u8).collect::<Vec<_>>().try_into().unwrap();
        sz::lookup(&mut less_long, &long, lut);
    }

    #[test]
    #[cfg(feature = "std")]
    fn replace_all_same_length() {
        let mut buffer = b"abcabc".to_vec();
        let replaced = sz::try_replace_all(&mut buffer, b"ab", b"XY").expect("try_replace_all failed");
        assert_eq!(replaced, 2);
        assert_eq!(buffer, b"XYcXYc");
    }

    #[test]
    #[cfg(feature = "std")]
    fn replace_all_shrinks() {
        let mut buffer = b"aaaa".to_vec();
        let replaced = sz::try_replace_all(&mut buffer, b"aa", b"b").expect("try_replace_all failed");
        assert_eq!(replaced, 2);
        assert_eq!(buffer, b"bb");
    }

    #[test]
    #[cfg(feature = "std")]
    fn replace_all_grows() {
        let mut buffer = b"aba".to_vec();
        let replaced = sz::try_replace_all(&mut buffer, b"a", b"XYZ").expect("try_replace_all failed");
        assert_eq!(replaced, 2);
        assert_eq!(buffer, b"XYZbXYZ");
    }

    #[test]
    #[cfg(feature = "std")]
    fn replace_all_byteset_basic() {
        let mut buffer = b"hello world".to_vec();
        let vowels = sz::Byteset::from("aeiou");
        let replaced = sz::try_replace_all_byteset(&mut buffer, vowels, b"_").expect("try_replace_all_byteset failed");
        assert_eq!(replaced, 3);
        assert_eq!(buffer, b"h_ll_ w_rld");
    }

    #[test]
    #[cfg(feature = "std")]
    fn replace_all_byteset_grows() {
        let mut buffer = b"yzz".to_vec();
        let vowels = sz::Byteset::from("y");
        let replaced =
            sz::try_replace_all_byteset(&mut buffer, vowels, b"(y)").expect("try_replace_all_byteset failed");
        assert_eq!(replaced, 1);
        assert_eq!(buffer, b"(y)zz");
    }

    #[test]
    #[cfg(feature = "std")]
    fn replace_all_noop_on_empty_pattern() {
        let mut buffer = b"unchanged".to_vec();
        let replaced = sz::try_replace_all(&mut buffer, b"", b"anything").expect("try_replace_all failed");
        assert_eq!(replaced, 0);
        assert_eq!(buffer, b"unchanged");
    }

    #[test]
    fn iter_newline_utf8_splits() {
        let text = b"a\nb\r\nc\n\nd";
        let lines: Vec<_> = Utf8SplitNewlines::new(text).collect();
        assert_eq!(lines, vec![b"a", b"b", b"c", &b""[..], b"d"]);
    }

    #[test]
    fn iter_newline_utf8_splits_unicode() {
        let text = "Hello\u{2028}World".as_bytes(); // LINE SEPARATOR
        let lines: Vec<_> = Utf8SplitNewlines::new(text).collect();
        assert_eq!(lines, vec!["Hello".as_bytes(), "World".as_bytes()]);
    }

    #[test]
    fn iter_whitespace_utf8_splits() {
        // KEEP (default): every one of the 8 whitespace delimiters yields a segment, so leading,
        // trailing, and inner runs all surface empties (str::split semantics, matching C++/Python).
        let text = b"  a \t b\n\nc  ";
        let segments: Vec<_> = Utf8SplitWhitespaces::new(text).collect();
        assert_eq!(
            segments,
            vec![
                &b""[..],
                &b""[..],
                b"a",
                &b""[..],
                &b""[..],
                b"b",
                &b""[..],
                b"c",
                &b""[..],
                &b""[..],
            ]
        );
        // skip_empty: recovers the str::split_whitespace token behavior.
        let tokens: Vec<_> = Utf8SplitWhitespaces::new(text).skip_empty().collect();
        assert_eq!(tokens, vec![b"a", b"b", b"c"]);
    }

    #[test]
    fn iter_whitespace_utf8_splits_keep_default() {
        // The simple example from the doc comment: KEEP yields the surrounding empties, skip_empty drops them.
        let text = b"  hi  ";
        let kept: Vec<_> = Utf8SplitWhitespaces::new(text).collect();
        assert_eq!(kept, vec![&b""[..], &b""[..], b"hi", &b""[..], &b""[..]]);
        let tokens: Vec<_> = Utf8SplitWhitespaces::new(text).skip_empty().collect();
        assert_eq!(tokens, vec![b"hi"]);
    }

    #[test]
    fn iter_whitespace_utf8_splits_unicode() {
        let text = "a\u{3000}b\u{2000}c".as_bytes(); // IDEOGRAPHIC SPACE, EN QUAD
        let segments: Vec<_> = Utf8SplitWhitespaces::new(text).collect();
        assert_eq!(segments, vec![b"a", b"b", b"c"]); // single delimiters between words: no empties
        let tokens: Vec<_> = Utf8SplitWhitespaces::new(text).skip_empty().collect();
        assert_eq!(tokens, vec![b"a", b"b", b"c"]);
    }

    #[test]
    fn iter_whitespace_utf8_splits_skip_empty_all_whitespace() {
        let text = b"   \t  ";
        let kept: Vec<_> = Utf8SplitWhitespaces::new(text).collect();
        assert_eq!(kept.len(), 7); // 6 delimiters → 7 (all empty) segments
        assert!(kept.iter().all(|segment| segment.is_empty()));
        let tokens: Vec<&[u8]> = Utf8SplitWhitespaces::new(text).skip_empty().collect();
        assert!(tokens.is_empty());
    }

    #[test]
    fn iter_newline_utf8_splits_skip_empty() {
        let text = b"a\nb\r\nc\n\nd";
        // Default KEEP: the back-to-back "\n\n" yields an empty line.
        let kept: Vec<_> = Utf8SplitNewlines::new(text).collect();
        assert_eq!(kept, vec![b"a", b"b", b"c", &b""[..], b"d"]);
        // skip_empty: the empty line between "c" and "d" disappears.
        let nonempty: Vec<_> = Utf8SplitNewlines::new(text).skip_empty().collect();
        assert_eq!(nonempty, vec![b"a", b"b", b"c", b"d"]);
    }

    #[test]
    fn iter_newline_utf8_splits_steps_invariance() {
        // The yielded segments must be identical regardless of the batch size `STEPS`; a tiny batch
        // (STEPS == 1) exercises the refill/trailing-segment seam on every delimiter, while large
        // batches fit the whole input in one call.
        let text = b"\r\na\r\n\r\nb\r\nc\nd\n";
        let expected: Vec<&[u8]> = vec![b"", b"a", b"", b"b", b"c", b"d", b""];
        let from_1: Vec<_> = Utf8SplitNewlines::<1>::with_steps(text).collect();
        let from_3: Vec<_> = Utf8SplitNewlines::<3>::with_steps(text).collect();
        let from_65: Vec<_> = Utf8SplitNewlines::<65>::with_steps(text).collect();
        assert_eq!(from_1, expected);
        assert_eq!(from_3, expected);
        assert_eq!(from_65, expected);

        // skip_empty across the same batch sizes.
        let nonempty: Vec<&[u8]> = vec![b"a", b"b", b"c", b"d"];
        assert_eq!(
            Utf8SplitNewlines::<1>::with_steps(text)
                .skip_empty()
                .collect::<Vec<_>>(),
            nonempty
        );
        assert_eq!(
            Utf8SplitNewlines::<3>::with_steps(text)
                .skip_empty()
                .collect::<Vec<_>>(),
            nonempty
        );
        assert_eq!(
            Utf8SplitNewlines::<65>::with_steps(text)
                .skip_empty()
                .collect::<Vec<_>>(),
            nonempty
        );
    }

    #[test]
    fn iter_whitespace_utf8_splits_steps_invariance() {
        let text = b"  a \t b\n\nc  ";
        let expected: Vec<&[u8]> = vec![b"", b"", b"a", b"", b"", b"b", b"", b"c", b"", b""];
        assert_eq!(
            Utf8SplitWhitespaces::<1>::with_steps(text).collect::<Vec<_>>(),
            expected
        );
        assert_eq!(
            Utf8SplitWhitespaces::<3>::with_steps(text).collect::<Vec<_>>(),
            expected
        );
        assert_eq!(
            Utf8SplitWhitespaces::<65>::with_steps(text).collect::<Vec<_>>(),
            expected
        );
        let tokens: Vec<&[u8]> = vec![b"a", b"b", b"c"];
        assert_eq!(
            Utf8SplitWhitespaces::<1>::with_steps(text)
                .skip_empty()
                .collect::<Vec<_>>(),
            tokens
        );
    }

    #[test]
    fn iter_newline_utf8_splits_trailing_newline() {
        // "\r\na\r\n\r\nb\r\n" should produce ["", "a", "", "b", ""]
        let text = b"\r\na\r\n\r\nb\r\n";
        let lines: Vec<&[u8]> = Utf8SplitNewlines::new(text).collect();
        assert_eq!(lines.len(), 5, "Expected 5 lines");
        let expected: Vec<&[u8]> = vec![b"", b"a", b"", b"b", b""];
        assert_eq!(lines, expected);
    }

    #[test]
    fn iter_newline_utf8_splits_no_trailing() {
        let text = b"a\nb\nc";
        let lines: Vec<&[u8]> = Utf8SplitNewlines::new(text).collect();
        assert_eq!(lines.len(), 3);
        assert_eq!(lines, vec![b"a", b"b", b"c"]);
    }

    #[test]
    fn iter_newline_utf8_splits_empty_string() {
        let text = b"";
        let lines: Vec<&[u8]> = Utf8SplitNewlines::new(text).collect();
        assert_eq!(lines.len(), 1);
        assert_eq!(lines, vec![b""]);
    }

    #[test]
    fn iter_newline_utf8_splits_single_newline() {
        let text = b"\n";
        let lines: Vec<&[u8]> = Utf8SplitNewlines::new(text).collect();
        assert_eq!(lines.len(), 2);
        assert_eq!(lines, vec![b"", b""]);
    }

    /// Segments tile the input, so the yielded segments must match regardless of the batch size `STEPS`;
    /// a tiny batch (STEPS == 1) exercises the refill seam on every boundary the kernel reports.
    fn assert_steps_invariant<Kernel: SegmenterKernel>(text: &[u8]) {
        let forward: Vec<&[u8]> = Utf8Segments::<Kernel, ITERATORS_DEFAULT_STEPS>::new(text).collect();
        assert_eq!(Utf8Segments::<Kernel, 1>::with_steps(text).collect::<Vec<_>>(), forward);
        assert_eq!(Utf8Segments::<Kernel, 3>::with_steps(text).collect::<Vec<_>>(), forward);
        assert_eq!(
            Utf8Segments::<Kernel, 65>::with_steps(text).collect::<Vec<_>>(),
            forward
        );
    }

    #[test]
    fn iter_word_utf8_splits_steps_invariance() {
        assert_steps_invariant::<Wordbreaks>(b"Hi, world! A second sentence.");
    }

    #[test]
    fn iter_grapheme_utf8_splits_steps_invariance() {
        assert_steps_invariant::<Graphemes>(b"Hi, world! A second sentence.");
    }

    #[test]
    fn iter_sentence_utf8_splits_steps_invariance() {
        assert_steps_invariant::<Sentences>(b"Hi, world! A second sentence.");
    }

    #[test]
    fn iter_linebreak_utf8_splits_steps_invariance() {
        assert_steps_invariant::<Linebreaks>(b"Hi, world! A second sentence.");
    }

    #[test]
    fn utf8_uncased_fold_golden_vectors() {
        // One probe per kernel family: ASCII, Latin-1 (C3), Latin Extended (C4/C6),
        // Greek (incl. final sigma), Cyrillic, Vietnamese (E1 BA), letterlike symbols,
        // ligature expansions, and the post-Unicode-15 Garay block (4-byte sequences).
        let golden: &[(&str, &[u8])] = &[
            ("HeLLo", b"hello"),                                           // ASCII fast path
            ("ABCDEFGHIJKLMNOPQRSTUVWXYZ", b"abcdefghijklmnopqrstuvwxyz"), // >16B ASCII: SIMD fold loop
            ("Hello, WASM World! 12345.", b"hello, wasm world! 12345."),   // >16B mixed: only A-Z fold
            // Long ASCII run, then a multi-byte codepoint, then more ASCII: SIMD → serial → scalar tail.
            (
                "LONG ASCII PREFIX \u{00C4} SUFFIX",
                "long ascii prefix \u{00E4} suffix".as_bytes(),
            ),
            ("\u{00DF}", b"ss"),                   // ß → ss expansion
            ("\u{1E9E}", b"ss"),                   // ẞ → ss (E1 BA lead bytes)
            ("\u{03A3}", "\u{03C3}".as_bytes()),   // Σ → σ
            ("\u{03C2}", "\u{03C3}".as_bytes()),   // final sigma ς → σ
            ("\u{FB03}", b"ffi"),                  // ffi ligature → ffi
            ("\u{041A}", "\u{043A}".as_bytes()),   // Cyrillic К → к
            ("\u{00C4}", "\u{00E4}".as_bytes()),   // Ä → ä (C3 lead byte)
            ("\u{0110}", "\u{0111}".as_bytes()),   // Đ → đ (C4 lead byte)
            ("\u{0111}", "\u{0111}".as_bytes()),   // đ → đ (already folded)
            ("\u{01A0}", "\u{01A1}".as_bytes()),   // Ơ → ơ (C6 lead byte)
            ("\u{01A1}", "\u{01A1}".as_bytes()),   // ơ → ơ (already folded)
            ("\u{1EA0}", "\u{1EA1}".as_bytes()),   // Ạ → ạ (E1 BA lead bytes)
            ("\u{1EA1}", "\u{1EA1}".as_bytes()),   // ạ → ạ (already folded)
            ("\u{212A}", b"k"),                    // Kelvin sign K → k
            ("\u{10D50}", "\u{10D70}".as_bytes()), // Garay capital Ca → small Ca
        ];
        for (source, expected) in golden {
            let mut destination = vec![0u8; source.len() * 3];
            let folded_length = sz::utf8_uncased_fold(source, &mut destination[..]);
            assert_eq!(&destination[..folded_length], *expected, "folding {:?}", source);
        }

        // Returned length tracks expansion: ẞ shrinks 3 → 2 bytes, ΐ grows 2 → 6 bytes
        let mut destination = [0u8; 16];
        assert_eq!(sz::utf8_uncased_fold("\u{1E9E}", &mut destination), 2);
        let folded_length = sz::utf8_uncased_fold("\u{0390}", &mut destination);
        assert_eq!(folded_length, 6);
        assert_eq!(&destination[..folded_length], "\u{03B9}\u{0308}\u{0301}".as_bytes());
    }

    #[test]
    fn utf8_uncased_search_crossing_expansions() {
        // Curated cross-expansion cases where folding changes byte counts and matches can
        // straddle multiple expanding codepoints. Swept across prefix paddings so the match
        // lands at varied alignments relative to the SIMD window boundaries.
        let cases: &[(&str, &str)] = &[
            ("\u{00DF}\u{00DF}", "sss"),              // ßß → "ssss", needle "sss"
            ("\u{00DF}\u{00DF}", "\u{017F}\u{00DF}"), // ßß vs ſß → "sss" inside "ssss"
            ("\u{1E9E}\u{00DF}", "ssss"),             // ẞß → "ssss"
            ("\u{1E9E}\u{00DF}", "sss"),              // ẞß → "ssss", needle "sss"
            ("\u{FB03}", "fi"),                       // ffi → "ffi", needle "fi"
            ("\u{FB03}", "ffi"),                      // ffi → "ffi"
            ("\u{FB00}\u{FB01}", "ffi"),              // fffi → "ff" + "fi" = "fffi"
        ];
        let paddings: &[usize] = &[0, 30, 62, 63, 64, 65];

        for (haystack_core, needle) in cases {
            for &padding in paddings {
                let mut haystack = String::with_capacity(padding + haystack_core.len());
                for _ in 0..padding {
                    haystack.push('z'); // non-folding filler
                }
                haystack.push_str(haystack_core);

                let actual = sz::utf8_uncased_search(haystack.as_bytes(), needle.as_bytes());
                let expected = reference_uncased_find(&haystack, needle);
                assert_eq!(
                    actual, expected,
                    "mismatch for haystack_core={:?} needle={:?} padding={}",
                    haystack_core, needle, padding
                );
            }
        }
    }

    #[test]
    fn utf8_uncased_matches_empty_needle() {
        let matches: Vec<_> = Utf8UncasedMatches::new(b"abc", b"").collect();
        assert_eq!(matches.len(), 4);
        assert!(matches.iter().all(|span| span.length == 0));
    }

    #[test]
    fn utf8_norm_golden_vectors() {
        // ASCII is invariant under all normalization forms.
        for form in [
            Utf8NormalForm::Nfd,
            Utf8NormalForm::Nfc,
            Utf8NormalForm::Nfkd,
            Utf8NormalForm::Nfkc,
        ] {
            let source = "Hello, world! 123";
            let mut dest = vec![0u8; source.len() * 18];
            let len = sz::utf8_norm(source, form, &mut dest);
            assert_eq!(&dest[..len], source.as_bytes(), "ASCII unchanged under {:?}", form);
        }

        // CAFE_NFC has precomposed é (U+00E9); NFC → NFC is a no-op (same bytes out).
        {
            let mut dest = vec![0u8; CAFE_NFC.len() * 18];
            let len = sz::utf8_norm(CAFE_NFC, Utf8NormalForm::Nfc, &mut dest);
            assert_eq!(&dest[..len], CAFE_NFC.as_bytes(), "café NFC→NFC unchanged");
        }

        // CAFE_NFD has decomposed é (base 'e' + combining acute U+0301); NFD → NFC must produce
        // the precomposed form.
        {
            let mut dest = vec![0u8; CAFE_NFD.len() * 18];
            let len = sz::utf8_norm(CAFE_NFD, Utf8NormalForm::Nfc, &mut dest);
            assert_eq!(&dest[..len], CAFE_NFC.as_bytes(), "café NFD→NFC gives precomposed form");
        }

        // NFD of the precomposed form must give the decomposed form.
        {
            let mut dest = vec![0u8; CAFE_NFC.len() * 18];
            let len = sz::utf8_norm(CAFE_NFC, Utf8NormalForm::Nfd, &mut dest);
            assert_eq!(&dest[..len], CAFE_NFD.as_bytes(), "café NFC→NFD gives decomposed form");
        }

        // Ligature U+FB03 ffi: NFKD and NFKC both decompose to "ffi".
        let ligature = "\u{FB03}"; // 3 bytes: 0xEF 0xAC 0x83
        {
            let mut dest = vec![0u8; ligature.len() * 18];
            let len = sz::utf8_norm(ligature, Utf8NormalForm::Nfkd, &mut dest);
            assert_eq!(&dest[..len], b"ffi", "ligature NFKD → ffi");
        }
        {
            let mut dest = vec![0u8; ligature.len() * 18];
            let len = sz::utf8_norm(ligature, Utf8NormalForm::Nfkc, &mut dest);
            assert_eq!(&dest[..len], b"ffi", "ligature NFKC → ffi");
        }

        // Idempotence: norm(norm(x, NFC), NFC) == norm(x, NFC).
        {
            let source = CAFE_NFD;
            let mut first = vec![0u8; source.len() * 18];
            let first_len = sz::utf8_norm(source, Utf8NormalForm::Nfc, &mut first);
            let first_result = first[..first_len].to_vec();

            let mut second = vec![0u8; first_len * 18];
            let second_len = sz::utf8_norm(&first_result[..], Utf8NormalForm::Nfc, &mut second);
            assert_eq!(&second[..second_len], &first_result[..], "NFC is idempotent");
        }
    }

    #[test]
    fn utf8_find_denormalized() {
        // NFC string: precomposed é — no violation.
        assert_eq!(
            sz::utf8_find_denormalized(CAFE_NFC, Utf8NormalForm::Nfc),
            None,
            "NFC string has no NFC violation"
        );

        // NFD string: decomposed e + combining acute U+0301.
        // The combining mark violates NFC (it should be composed with the preceding base).
        let violation = sz::utf8_find_denormalized(CAFE_NFD, Utf8NormalForm::Nfc);
        assert!(violation.is_some(), "NFD string must report an NFC violation");
        // The violation may point to the base 'e' (byte 3) or to the combining mark (byte 4);
        // either is within the suffix that must change during composition.
        assert!(
            violation.unwrap() >= 3,
            "violation offset must be ≥ 3 (at 'e' or the combining mark)"
        );

        // NFC string has no NFD violation only if it contains no precomposed characters.
        // ASCII is valid NFD.
        assert_eq!(
            sz::utf8_find_denormalized("hello", Utf8NormalForm::Nfd),
            None,
            "pure ASCII has no NFD violation"
        );
    }
}