fxcp_core/

hashing.rs

// SPDX-License-Identifier: GPL-2.0-or-later
// Copyright (C) 2025 Joel Wirāmu Pauling <aenertia@aenertia.net>
//
//! BLAKE3 hashing, Merkle tree, delta detection, directory hashing.

#![allow(clippy::unwrap_used, clippy::ptr_arg)]
use blake3::{Hasher, Hash};
use std::io::{Read, Seek};
use std::os::unix::fs::FileExt;
use std::os::unix::io::AsRawFd;
use std::path::Path;
use std::fs::File;
use crate::error::{Result, FxcpError};
use crate::metrics;
use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};

static LITE_HASH_THRESHOLD_BYTES: AtomicU64 = AtomicU64::new(crate::constants::LITE_HASH_DEFAULT_THRESHOLD);
/// Minimum chunk size for Merkle tree  --  defined in constants.rs for central tuning.
pub const MIN_CHUNK_SIZE: usize = crate::constants::MIN_CHUNK_SIZE;
/// Keep backward compat for callers using CHUNK_SIZE directly
pub const CHUNK_SIZE: usize = MIN_CHUNK_SIZE;
/// Max Merkle leaves per xattr  --  defined in constants.rs for central tuning.
pub const MAX_LEAVES_PER_XATTR: u64 = crate::constants::MAX_LEAVES_PER_XATTR;

const RAYON_HASH_THRESHOLD: usize = crate::constants::RAYON_HASH_THRESHOLD as usize;

static HASHING_ENABLED: AtomicBool = AtomicBool::new(true);

/// Enable or disable BLAKE3 hashing globally
pub fn set_hashing_enabled(enabled: bool) {
    HASHING_ENABLED.store(enabled, Ordering::Relaxed);
}

/// Check whether BLAKE3 hashing is currently enabled
pub fn is_hashing_enabled() -> bool {
    HASHING_ENABLED.load(Ordering::Relaxed)
}

/// Set the minimum file size (in KB) for lite hash computation
pub fn set_lite_threshold_kb(kb: u64) {
    LITE_HASH_THRESHOLD_BYTES.store(kb * 1024, Ordering::Relaxed);
}

/// Get the current lite hash threshold in bytes
pub fn get_lite_threshold_bytes() -> u64 {
    LITE_HASH_THRESHOLD_BYTES.load(Ordering::Relaxed)
}

/// Calculate chunk size for Merkle tree construction.
///
/// For files that fit in xattr (<=~115MB): uses adaptive sizing to keep <=1800 leaves.
/// For large files (>256MB): uses 512KB chunks stored in per-target Merkle index,
/// giving 512KB resync granularity instead of the 55MB+ that xattr limits force.
pub fn calculate_adaptive_chunk_size(file_size: u64) -> u64 {
    if file_size == 0 {
        return MIN_CHUNK_SIZE as u64;
    }
    // Large files: use fixed 512KB chunks (stored in merkle_index, not xattr)
    if file_size > crate::merkle_index::INDEX_THRESHOLD {
        return crate::merkle_index::LARGE_FILE_CHUNK_SIZE;
    }
    // Small/medium files: adaptive sizing to fit in xattr
    let desired = file_size.div_ceil(MAX_LEAVES_PER_XATTR);
    std::cmp::max(MIN_CHUNK_SIZE as u64, desired).next_power_of_two()
}

/// Compute a fast BLAKE3 hash from the first and last 64KB of a file (head+tail sampling)
pub fn hash_file_lite(path: &Path, size: u64) -> Result<Option<Hash>> {
    if !is_hashing_enabled() { return Ok(None); }
    if size < get_lite_threshold_bytes() { return Ok(None); }

    let _timer = metrics::HASH_COMPUTATION_DURATION.start_timer();
    let file = File::open(path)?;
    let mut hasher = Hasher::new();
    hasher.update(&size.to_le_bytes());

    // Use read_at (pread) to avoid stateful seeks and zero-init overhead
    let mut buf = vec![0u8; MIN_CHUNK_SIZE];

    let head_read = file.read_at(&mut buf, 0).unwrap_or(0);
    hasher.update(&buf[..head_read]);

    if size > MIN_CHUNK_SIZE as u64 * 2 {
        let tail_offset = size - MIN_CHUNK_SIZE as u64;
        let tail_read = file.read_at(&mut buf, tail_offset).unwrap_or(0);
        hasher.update(&buf[..tail_read]);
    }

    Ok(Some(hasher.finalize()))
}

/// Compute a full BLAKE3 hash of an entire file.
///
/// Files larger than [`RAYON_HASH_THRESHOLD`] (1 MiB) use `update_rayon()`
/// for multi-threaded hashing. Output is identical to sequential hashing.
pub fn hash_file_full(path: &Path) -> Result<Option<Hash>> {
    if !is_hashing_enabled() { return Ok(None); }
    
    let _timer = metrics::HASH_COMPUTATION_DURATION.start_timer();
    let mut file = File::open(path)?;
    let file_size = file.metadata()?.len() as usize;
    let mut hasher = Hasher::new();

    if file_size > RAYON_HASH_THRESHOLD {
        let mut data = Vec::with_capacity(file_size);
        file.read_to_end(&mut data)?;
        hasher.update_rayon(&data);
    } else {
        let mut buf = vec![0u8; CHUNK_SIZE];
        loop {
            let n = file.read(&mut buf)?;
            if n == 0 { break; }
            hasher.update(&buf[..n]);
        }
    }
    
    Ok(Some(hasher.finalize()))
}

/// Lite hash from an in-memory buffer (head+tail sampling, same algorithm as `hash_file_lite`).
pub fn hash_buffer_lite(data: &[u8], size: u64) -> Option<Hash> {
    if !is_hashing_enabled() { return None; }
    if size < get_lite_threshold_bytes() { return None; }

    let mut hasher = Hasher::new();
    hasher.update(&size.to_le_bytes());

    let head_len = CHUNK_SIZE.min(data.len());
    hasher.update(&data[..head_len]);

    if size > CHUNK_SIZE as u64 * 2 {
        let tail_start = data.len().saturating_sub(CHUNK_SIZE);
        hasher.update(&data[tail_start..]);
    }

    Some(hasher.finalize())
}

/// Full BLAKE3 hash from an in-memory buffer (same algorithm as `hash_file_full`).
///
/// Buffers larger than [`RAYON_HASH_THRESHOLD`] use `update_rayon()` for
/// multi-threaded hashing.
pub fn hash_buffer_full(data: &[u8]) -> Option<Hash> {
    if !is_hashing_enabled() { return None; }
    if data.len() > RAYON_HASH_THRESHOLD {
        let mut hasher = Hasher::new();
        hasher.update_rayon(data);
        Some(hasher.finalize())
    } else {
        Some(blake3::hash(data))
    }
}

/// Verify that src and dst have matching lite hashes (returns true if identical or below threshold)
pub fn verify_incremental(src: &Path, dst: &Path, size: u64) -> Result<bool> {
    if !is_hashing_enabled() { return Ok(true); }
    if size < get_lite_threshold_bytes() { return Ok(true); }

    let src_hash = match hash_file_lite(src, size) {
        Ok(h) => h,
        Err(crate::error::FxcpError::Io(e)) if e.kind() == std::io::ErrorKind::NotFound => {
            // Source vanished  --  file lifecycle ended, skip verification
            return Ok(true);
        },
        Err(e) => return Err(e),
    };
    let dst_hash = match hash_file_lite(dst, size) {
        Ok(h) => h,
        Err(crate::error::FxcpError::Io(e)) if e.kind() == std::io::ErrorKind::NotFound => {
            // Target vanished  --  needs re-copy, not a verification pass
            return Ok(false);
        },
        Err(e) => return Err(e),
    };

    Ok(src_hash == dst_hash)
}

/// Compute a directory hash by reading the directory at `path`.
/// Each child's metadata (size, mtime, type) is hashed, then all children
/// are sorted by name and combined into a single BLAKE3 directory fingerprint.
/// Skips foxing internal files (.foxing*, .foxing_meta sidecars).
pub fn compute_dir_hash_from_path(dir_path: &std::path::Path) -> Option<[u8; 32]> {
    use std::os::unix::fs::MetadataExt;
    let mut children: Vec<(String, [u8; 32])> = Vec::new();
    for entry in std::fs::read_dir(dir_path).ok()? {
        let entry = entry.ok()?;
        let name = entry.file_name().to_string_lossy().into_owned();
        if name.starts_with('.') && name.ends_with(".foxing_meta") { continue; }
        if name.starts_with(".foxing") { continue; }
        if let Ok(meta) = entry.metadata() {
            let mut hasher = Hasher::new();
            hasher.update(&meta.len().to_le_bytes());
            hasher.update(&meta.mtime().to_le_bytes());
            hasher.update(&meta.mtime_nsec().to_le_bytes());
            if meta.is_dir() { hasher.update(b"d"); } else { hasher.update(b"f"); }
            children.push((name, *hasher.finalize().as_bytes()));
        }
    }
    if children.is_empty() { return Some(*blake3::hash(b"foxing:empty_dir").as_bytes()); }
    Some(compute_dir_hash(&mut children))
}

/// Compute a directory hash from sorted child (name, hash) pairs.
/// Uses BLAKE3 over concatenation of sorted `name:hash` entries.
/// Provides a stable, order-independent directory fingerprint.
pub fn compute_dir_hash(children: &mut Vec<(String, [u8; 32])>) -> [u8; 32] {
    children.sort_by(|a, b| a.0.cmp(&b.0));
    let mut hasher = Hasher::new();
    for (name, hash) in children.iter() {
        hasher.update(name.as_bytes());
        hasher.update(b":");
        hasher.update(hash);
    }
    *hasher.finalize().as_bytes()
}

/// Compute a directory hash from S3 child metadata.
///
/// Each child is represented as `(name, size_bytes, blake3_hex_or_etag)`.
/// For CAS restores: blake3_hex_or_etag = the per-file BLAKE3 from the manifest.
/// For plain S3: blake3_hex_or_etag = the S3 ETag (MD5 or multipart hash).
///
/// Child hash = BLAKE3(size_le8 ++ hash_str_bytes).
/// Dir hash = compute_dir_hash(sorted children).
/// Sort-order independent: children are sorted by name inside compute_dir_hash.
pub fn compute_dir_hash_from_s3_children(children: &mut Vec<(String, u64, String)>) -> [u8; 32] {
    let mut hashed: Vec<(String, [u8; 32])> = children
        .iter()
        .map(|(name, size, hash_str)| {
            let mut h = Hasher::new();
            h.update(&size.to_le_bytes());
            h.update(hash_str.as_bytes());
            (name.clone(), *h.finalize().as_bytes())
        })
        .collect();
    compute_dir_hash(&mut hashed)
}

/// Accumulates S3 restore child entries per directory prefix, producing a
/// dir hash when `finalize()` is called for a given prefix.
///
/// Usage:
/// ```ignore
/// let mut acc = DirHashAccumulator::new();
/// acc.add("photos", "img001.jpg", 2_048_000, "abc123def456...");
/// acc.add("photos", "img002.jpg", 1_800_000, "789abc012def...");
/// let hash = acc.finalize("photos"); // Some([u8; 32])
/// ```
pub struct DirHashAccumulator {
    /// prefix -> list of (name, size, hash_str)
    entries: std::collections::HashMap<String, Vec<(String, u64, String)>>,
}

impl DirHashAccumulator {
    pub fn new() -> Self {
        Self {
            entries: std::collections::HashMap::new(),
        }
    }

    /// Add a child entry to the accumulator for the given prefix (dir path).
    pub fn add(
        &mut self,
        prefix: impl Into<String>,
        name: impl Into<String>,
        size: u64,
        hash_str: impl Into<String>,
    ) {
        self.entries
            .entry(prefix.into())
            .or_default()
            .push((name.into(), size, hash_str.into()));
    }

    /// Compute and return the dir hash for all children under `prefix`.
    /// Returns None if no children were added for that prefix.
    pub fn finalize(&mut self, prefix: &str) -> Option<[u8; 32]> {
        let mut children = self.entries.remove(prefix)?;
        if children.is_empty() {
            return None;
        }
        Some(compute_dir_hash_from_s3_children(&mut children))
    }

    /// Drain all prefixes, returning (prefix, dir_hash) pairs.
    pub fn drain_all(&mut self) -> Vec<(String, [u8; 32])> {
        let prefixes: Vec<String> = self.entries.keys().cloned().collect();
        let mut result = Vec::new();
        for prefix in prefixes {
            if let Some(hash) = self.finalize(&prefix) {
                result.push((prefix, hash));
            }
        }
        result
    }
}

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

// ---------------------------------------------------------------------------
// Merkle Tree Engine  --  BLAKE3 chunk-level delta detection
// ---------------------------------------------------------------------------

/// Controls which per-chunk computations `MerkleTree::from_file()` performs.
///
/// Variants are ordered so that `WithSimilarity > WithEntropy > Blake3Only`,
/// enabling `compute_mode >= ComputeMode::WithEntropy` guards.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum ComputeMode {
    /// BLAKE3 hash only (current default). Entropy = 0.0, similarity fields zeroed.
    Blake3Only,
    /// BLAKE3 + Shannon entropy per chunk.
    WithEntropy,
    /// BLAKE3 + Shannon entropy + SimHash/TLSH per chunk (requires `similarity` feature).
    WithSimilarity,
}

/// Per-chunk hash with file offset metadata.
pub struct ChunkHash {
    /// Byte offset of this chunk within the file
    pub offset: u64,
    /// Length of this chunk in bytes
    pub length: u32,
    /// BLAKE3 hash of the chunk data
    pub hash: Hash,
    /// Shannon entropy (bits/byte, 0.0-8.0). Zero when `ComputeMode::Blake3Only`.
    pub entropy: f32,
    /// SimHash locality-sensitive fingerprint. Zero when not computed.
    #[cfg(feature = "similarity")]
    pub simhash: u64,
    /// TLSH fuzzy hash digest. None when not computed.
    #[cfg(feature = "similarity")]
    pub tlsh_digest: Option<Vec<u8>>,
}

/// BLAKE3 Merkle tree over fixed-size file chunks.
pub struct MerkleTree {
    /// Fixed chunk size used for this tree
    pub chunk_size: u64,
    /// Total file size at tree construction time
    pub file_size: u64,
    /// Root hash computed from all leaf hashes
    pub root: Hash,
    /// Per-chunk hashes with offset metadata
    pub leaves: Vec<ChunkHash>,
}

/// A contiguous byte range that differs between source and target.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct DirtyRange {
    /// Start offset of the dirty region
    pub offset: u64,
    /// Length of the dirty region in bytes
    pub length: u64,
}

/// Serializable Merkle signature for xattr/sidecar storage.
#[derive(serde::Serialize, serde::Deserialize, Clone, Debug)]
pub struct MerkleSignature {
    /// BLAKE3 root hash of the Merkle tree
    pub root: [u8; 32],
    /// Chunk size used when building the tree
    pub chunk_size: u64,
    /// File size at signature creation time
    pub file_size: u64,
    /// Ordered leaf hashes (one per chunk)
    pub leaf_hashes: Vec<[u8; 32]>,
    /// Per-chunk Shannon entropy (bits/byte, 0.0-8.0). Present when any leaf has non-zero entropy.
    #[serde(default)]
    pub chunk_entropies: Option<Vec<f32>>,
    /// Per-chunk SimHash fingerprints. Present when similarity feature computed the hashes.
    #[serde(default)]
    pub chunk_simhashes: Option<Vec<u64>>,
}

const MAX_MERKLE_XATTR_BYTES: usize = crate::constants::MERKLE_XATTR_MAX_BYTES;

impl MerkleTree {
    /// Build a Merkle tree by hashing a file in fixed-size chunks.
    pub fn from_file(path: &Path, chunk_size: u64, compute_mode: ComputeMode) -> Result<Self> {
        let file = File::open(path)?;
        let file_size = file.metadata()?.len();
        if file_size == 0 {
            return Ok(MerkleTree { chunk_size, file_size, root: blake3::hash(b""), leaves: Vec::new() });
        }

        // Try sparse-aware path: map data extents via SEEK_HOLE/SEEK_DATA
        let data_extents = map_data_extents(file.as_raw_fd(), file_size);
        let is_sparse = data_extents.as_ref().map(|e| !e.is_empty() && {
            let data_bytes: u64 = e.iter().map(|&(_, len)| len).sum();
            data_bytes < file_size
        }).unwrap_or(false);

        if is_sparse {
            return Self::from_file_sparse(&file, file_size, chunk_size, &data_extents.unwrap(), compute_mode);
        }

        // Dense file: sequential read (original path)
        // CRITICAL: map_data_extents() uses lseek(SEEK_DATA/SEEK_HOLE) which moves the
        // file position to EOF. We must seek back to 0 before reading sequentially.
        let mut file = file;
        file.seek(std::io::SeekFrom::Start(0))?;
        let mut leaves = Vec::new();
        let mut buf = vec![0u8; chunk_size as usize];
        let mut offset = 0u64;

        loop {
            let mut read_total = 0;
            loop {
                let n = file.read(&mut buf[read_total..])?;
                if n == 0 { break; }
                read_total += n;
                if read_total >= chunk_size as usize { break; }
            }
            if read_total == 0 { break; }

            let hash = blake3::hash(&buf[..read_total]);
            let entropy = if compute_mode >= ComputeMode::WithEntropy {
                shannon_entropy(&buf[..read_total])
            } else {
                0.0
            };
            #[cfg(feature = "similarity")]
            let simhash = if compute_mode == ComputeMode::WithSimilarity {
                crate::similarity::simhash_64(&buf[..read_total])
            } else {
                0
            };
            leaves.push(ChunkHash {
                offset,
                length: u32::try_from(read_total).map_err(|_| FxcpError::Config(format!(
                    "Merkle chunk read_total {} exceeds u32::MAX", read_total
                )))?,
                hash,
                entropy,
                #[cfg(feature = "similarity")]
                simhash,
                #[cfg(feature = "similarity")]
                tlsh_digest: None,
            });
            offset += read_total as u64;
        }

        let root = Self::compute_root(&leaves);
        Ok(MerkleTree { chunk_size, file_size, root, leaves })
    }

    /// Build Merkle tree for a sparse file, skipping holes.
    /// Hole chunks get a constant sentinel hash  --  no I/O needed.
    fn from_file_sparse(
        file: &File,
        file_size: u64,
        chunk_size: u64,
        data_extents: &[(u64, u64)],
        compute_mode: ComputeMode,
    ) -> Result<Self> {
        let sentinel = blake3::hash(b"foxing:sparse:hole");
        let total_chunks = file_size.div_ceil(chunk_size);
        let mut leaves = Vec::with_capacity(total_chunks as usize);
        let mut buf = vec![0u8; chunk_size as usize];

        for chunk_idx in 0..total_chunks {
            let chunk_offset = chunk_idx * chunk_size;
            let chunk_len = u32::try_from(chunk_size.min(file_size - chunk_offset)).map_err(|_| FxcpError::Config(format!(
                "Sparse Merkle chunk length {} exceeds u32::MAX", chunk_size.min(file_size - chunk_offset)
            )))?;

            if chunk_is_hole(data_extents, chunk_offset, chunk_len as u64) {
                leaves.push(ChunkHash {
                    offset: chunk_offset,
                    length: chunk_len,
                    hash: sentinel,
                    entropy: 0.0,
                    #[cfg(feature = "similarity")]
                    simhash: 0,
                    #[cfg(feature = "similarity")]
                    tlsh_digest: None,
                });
            } else {
                let read_len = chunk_len as usize;
                buf[..read_len].fill(0);
                let mut read_total = 0;
                loop {
                    let n = file.read_at(&mut buf[read_total..read_len], chunk_offset + read_total as u64)?;
                    if n == 0 { break; }
                    read_total += n;
                    if read_total >= read_len { break; }
                }
                let hash = blake3::hash(&buf[..read_total]);
                let entropy = if compute_mode >= ComputeMode::WithEntropy {
                    shannon_entropy(&buf[..read_total])
                } else {
                    0.0
                };
                #[cfg(feature = "similarity")]
                let simhash = if compute_mode == ComputeMode::WithSimilarity {
                    crate::similarity::simhash_64(&buf[..read_total])
                } else {
                    0
                };
                leaves.push(ChunkHash {
                    offset: chunk_offset,
                    length: u32::try_from(read_total).map_err(|_| FxcpError::Config(format!(
                        "Sparse Merkle chunk read_total {} exceeds u32::MAX", read_total
                    )))?,
                    hash,
                    entropy,
                    #[cfg(feature = "similarity")]
                    simhash,
                    #[cfg(feature = "similarity")]
                    tlsh_digest: None,
                });
            }
        }

        let root = Self::compute_root(&leaves);
        Ok(MerkleTree { chunk_size, file_size, root, leaves })
    }

    /// XOR-fold all chunk SimHash fingerprints into a single file-level SimHash.
    ///
    /// Returns 0 if no simhashes were computed (e.g. `Blake3Only` or `WithEntropy` mode).
    #[cfg(feature = "similarity")]
    pub fn file_simhash(&self) -> u64 {
        self.leaves.iter().fold(0u64, |acc, chunk| acc ^ chunk.simhash)
    }

    /// Compute a root hash from leaf hashes by hashing them together.
    fn compute_root(leaves: &[ChunkHash]) -> Hash {
        if leaves.is_empty() {
            return blake3::hash(b"");
        }
        if leaves.len() == 1 {
            return leaves[0].hash;
        }
        let mut hasher = Hasher::new();
        for leaf in leaves {
            hasher.update(leaf.hash.as_bytes());
        }
        hasher.finalize()
    }

    /// Compare two Merkle trees and return ranges that differ.
    /// Adjacent dirty chunks are merged into contiguous ranges.
    pub fn diff(source: &MerkleTree, target: &MerkleTree) -> Vec<DirtyRange> {
        let mut ranges = Vec::new();
        let max_leaves = source.leaves.len().max(target.leaves.len());

        let mut current_dirty: Option<DirtyRange> = None;

        for i in 0..max_leaves {
            let src_chunk = source.leaves.get(i);
            let tgt_chunk = target.leaves.get(i);

            let is_dirty = match (src_chunk, tgt_chunk) {
                (Some(s), Some(t)) => s.hash != t.hash,
                (Some(_), None) => true,  // source has extra chunks (file grew)
                (None, Some(_)) => false, // target has extra chunks (file shrunk  --  handled by truncate)
                (None, None) => false,
            };

            if is_dirty {
                let s = src_chunk.unwrap();
                match &mut current_dirty {
                    Some(range) => {
                        // Extend existing dirty range
                        range.length = (s.offset + s.length as u64) - range.offset;
                    }
                    None => {
                        // Start new dirty range
                        current_dirty = Some(DirtyRange {
                            offset: s.offset,
                            length: s.length as u64,
                        });
                    }
                }
            } else if let Some(range) = current_dirty.take() {
                ranges.push(range);
            }
        }

        // Flush trailing dirty range
        if let Some(range) = current_dirty {
            ranges.push(range);
        }

        ranges
    }

    /// Convert to a serializable signature.
    pub fn to_signature(&self) -> MerkleSignature {
        let chunk_entropies = if self.leaves.iter().any(|c| c.entropy != 0.0) {
            Some(self.leaves.iter().map(|c| c.entropy).collect())
        } else {
            None
        };

        #[cfg(feature = "similarity")]
        let chunk_simhashes = if self.leaves.iter().any(|c| c.simhash != 0) {
            Some(self.leaves.iter().map(|c| c.simhash).collect())
        } else {
            None
        };
        #[cfg(not(feature = "similarity"))]
        let chunk_simhashes = None;

        MerkleSignature {
            root: *self.root.as_bytes(),
            chunk_size: self.chunk_size,
            file_size: self.file_size,
            leaf_hashes: self.leaves.iter().map(|l| *l.hash.as_bytes()).collect(),
            chunk_entropies,
            chunk_simhashes,
        }
    }

    /// Reconstruct a MerkleTree from a stored signature.
    pub fn from_signature(sig: &MerkleSignature) -> Option<Self> {
        // Bounds check: chunk_size must be positive, leaf count must be reasonable
        if sig.chunk_size == 0 { return None; }
        let expected_max = sig.file_size / sig.chunk_size + 2;
        if sig.leaf_hashes.len() as u64 > expected_max {
            return None;
        }

        let mut leaves = Vec::with_capacity(sig.leaf_hashes.len());
        let mut offset = 0u64;
        for (i, hash_bytes) in sig.leaf_hashes.iter().enumerate() {
            let remaining = sig.file_size.saturating_sub(offset);
            let length = u32::try_from(remaining.min(sig.chunk_size)).ok()?;
            if length == 0 && i > 0 { break; }

            let entropy = sig.chunk_entropies.as_ref()
                .and_then(|v| v.get(i).copied())
                .unwrap_or(0.0);

            #[cfg(feature = "similarity")]
            let simhash = sig.chunk_simhashes.as_ref()
                .and_then(|v| v.get(i).copied())
                .unwrap_or(0);

            leaves.push(ChunkHash {
                offset,
                length,
                hash: Hash::from_bytes(*hash_bytes),
                entropy,
                #[cfg(feature = "similarity")]
                simhash,
                #[cfg(feature = "similarity")]
                tlsh_digest: None,
            });
            offset += length as u64;
        }

        let computed = Self::compute_root(&leaves);
        if computed.as_bytes() != &sig.root {
            return None;
        }

        let root = Hash::from_bytes(sig.root);
        Some(MerkleTree {
            chunk_size: sig.chunk_size,
            file_size: sig.file_size,
            root,
            leaves,
        })
    }
}

impl MerkleSignature {
    /// Estimated serialized size for xattr storage bounds checking.
    pub fn serialized_size(&self) -> usize {
        // root(32) + chunk_size(8) + file_size(8) + vec_len(8) + hashes(32 each)
        let base = 56 + self.leaf_hashes.len() * 32;
        let entropy_size = if self.chunk_entropies.is_some() { self.leaf_hashes.len() * 4 } else { 0 };
        let simhash_size = if self.chunk_simhashes.is_some() { self.leaf_hashes.len() * 8 } else { 0 };
        base + entropy_size + simhash_size
    }

    /// Check if this signature fits within xattr limits.
    pub fn fits_in_xattr(&self) -> bool {
        self.serialized_size() <= MAX_MERKLE_XATTR_BYTES
    }
}

/// Compare a source file's Merkle root against a stored signature.
///
/// Builds the source Merkle tree using the stored signature's chunk size,
/// then compares roots. Returns `Ok(true)` if the roots match (file unchanged),
/// `Ok(false)` if they differ (file needs resync).
pub fn verify_with_merkle(src: &Path, stored_sig: &MerkleSignature) -> Result<bool> {
    let src_tree = MerkleTree::from_file(src, stored_sig.chunk_size, ComputeMode::Blake3Only)?;
    Ok(src_tree.root.as_bytes() == &stored_sig.root)
}

// ---------------------------------------------------------------------------
// Sparse file helpers  --  SEEK_HOLE/SEEK_DATA extent mapping
// ---------------------------------------------------------------------------

/// Map allocated data extents in a file using SEEK_DATA/SEEK_HOLE.
/// Returns Vec of (offset, length) pairs for data regions.
/// Returns Err if the filesystem doesn't support SEEK_HOLE.
pub fn map_data_extents(fd: std::os::unix::io::RawFd, file_size: u64) -> std::result::Result<Vec<(u64, u64)>, FxcpError> {
    let mut extents = Vec::new();
    let mut pos = 0u64;

    while pos < file_size {
        // SAFETY: fd is a valid open file descriptor from the caller.
        let data_start = unsafe { libc::lseek(fd, pos as i64, libc::SEEK_DATA) };
        if data_start < 0 {
            let err = std::io::Error::last_os_error();
            if err.raw_os_error() == Some(libc::ENXIO) {
                break; // No more data regions
            }
            return Err(FxcpError::Io(err));
        }
        let data_start = data_start as u64;
        if data_start >= file_size { break; }

        // SAFETY: fd is a valid open file descriptor, data_start is a valid offset.
        let hole_start = unsafe { libc::lseek(fd, data_start as i64, libc::SEEK_HOLE) };
        let data_end = if hole_start < 0 { file_size } else { (hole_start as u64).min(file_size) };

        if data_end > data_start {
            extents.push((data_start, data_end - data_start));
        }
        pos = data_end;
    }

    Ok(extents)
}

/// Check if a chunk is entirely within a hole (no data extents overlap it).
fn chunk_is_hole(data_extents: &[(u64, u64)], chunk_offset: u64, chunk_len: u64) -> bool {
    let chunk_end = chunk_offset + chunk_len;
    for &(ext_offset, ext_len) in data_extents {
        let ext_end = ext_offset + ext_len;
        // Check for any overlap
        if ext_offset < chunk_end && ext_end > chunk_offset {
            return false;
        }
        // Extents are sorted; if we're past the chunk, stop
        if ext_offset >= chunk_end { break; }
    }
    true
}



// ---------------------------------------------------------------------------
// Shannon entropy  --  bits-per-symbol measurement for data classification
// ---------------------------------------------------------------------------

/// Compute Shannon entropy of a byte slice, returning bits per symbol (0.0-8.0).
///
/// Single-pass O(n) time, O(1) space (256-entry frequency table).
/// Returns 0.0 for empty input.
///
/// Reference ranges:
/// - **English text:** ~4.0-5.5 bits/byte
/// - **Compiled binaries / structured data:** ~5.0-7.0 bits/byte
/// - **Compressed data (zstd, gzip):** ~7.5-7.9 bits/byte
/// - **Encrypted / random data:** ~7.95-8.0 bits/byte
///
/// Used by the copy pipeline to classify chunk content (e.g. skip compression
/// on already-compressed or encrypted data).
pub fn shannon_entropy(data: &[u8]) -> f32 {
    if data.is_empty() {
        return 0.0;
    }
    let mut counts = [0u64; 256];
    for &byte in data {
        counts[byte as usize] += 1;
    }
    let len = data.len() as f64;
    counts
        .iter()
        .filter(|&&c| c > 0)
        .map(|&c| {
            let p = c as f64 / len;
            -(p * p.log2()) as f32
        })
        .sum()
}

// ---------------------------------------------------------------------------
// Crypto acceleration probe  --  log detected hardware paths
// ---------------------------------------------------------------------------

/// Log detected cryptographic hardware acceleration at startup.
/// Called once during initialization to inform operators which hash
/// algorithms benefit from hardware acceleration on this platform.
pub fn log_crypto_capabilities() {
    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
    {
        let blake3_accel = if is_x86_feature_detected!("avx512f") {
            "avx512"
        } else if is_x86_feature_detected!("avx2") {
            "avx2"
        } else if is_x86_feature_detected!("sse4.1") {
            "sse4.1"
        } else {
            "software"
        };

        // SHA-NI is available on Ice Lake+ (2019), Zen 1+ (2017)
        let sha256_accel = if is_x86_feature_detected!("sha") {
            "SHA-NI (hardware)"
        } else if is_x86_feature_detected!("avx2") {
            "avx2 (software)"
        } else {
            "software"
        };

        tracing::info!("Crypto: BLAKE3={}, SHA-256={}, SHA-1={}, MD5=software",
            blake3_accel, sha256_accel,
            if is_x86_feature_detected!("sha") { "SHA-NI" } else { "software" });
    }

    #[cfg(target_arch = "aarch64")]
    {
        let sha_accel = if std::arch::is_aarch64_feature_detected!("sha2") {
            "ARMv8-CE (hardware)"
        } else {
            "software"
        };
        tracing::info!("Crypto: BLAKE3=neon, SHA-256={}, SHA-1={}, MD5=software",
            sha_accel, sha_accel);
    }

    #[cfg(not(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64")))]
    {
        tracing::info!("Crypto: BLAKE3=software, SHA-256=software, SHA-1=software, MD5=software");
    }
}

// ---------------------------------------------------------------------------
// Checksum sidecar file support  --  standard verification formats
// ---------------------------------------------------------------------------

/// Checksum algorithm selection for sidecar file generation.
/// BLAKE3 is FREE (reuses existing computation). Others require extra I/O.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ChecksumType {
    /// BLAKE3  --  FREE: already computed during copy pipeline
    Blake3,
    /// SHA-256  --  AT COST: requires full re-read of file
    #[cfg(feature = "checksums")]
    Sha256,
    /// SHA-1  --  AT COST: requires full re-read (legacy, not recommended)
    #[cfg(feature = "checksums")]
    Sha1,
    /// MD5  --  AT COST: requires full re-read (legacy, not recommended)
    #[cfg(feature = "checksums")]
    Md5,
}

impl ChecksumType {
    /// File extension for the checksum sidecar file.
    pub fn extension(&self) -> &'static str {
        match self {
            Self::Blake3 => "blake3",
            #[cfg(feature = "checksums")]
            Self::Sha256 => "sha256",
            #[cfg(feature = "checksums")]
            Self::Sha1 => "sha1",
            #[cfg(feature = "checksums")]
            Self::Md5 => "md5",
        }
    }

    /// Whether this checksum type is free (reuses existing BLAKE3 computation).
    pub fn is_free(&self) -> bool {
        matches!(self, Self::Blake3)
    }

    /// Parse a single checksum type name.
    pub fn parse(s: &str) -> Option<Self> {
        match s.trim().to_lowercase().as_str() {
            "blake3" | "b3" => Some(Self::Blake3),
            #[cfg(feature = "checksums")]
            "sha256" | "sha-256" | "sha2" => Some(Self::Sha256),
            #[cfg(feature = "checksums")]
            "sha1" | "sha-1" => Some(Self::Sha1),
            #[cfg(feature = "checksums")]
            "md5" => Some(Self::Md5),
            _ => None,
        }
    }

    /// Parse a comma-separated list of checksum types.
    pub fn parse_list(s: &str) -> Vec<Self> {
        s.split(',').filter_map(Self::parse).collect()
    }
}

/// Compute a hex-encoded checksum of a file using the specified algorithm.
pub fn hash_file_checksum(path: &Path, checksum_type: ChecksumType) -> Result<String> {
    match checksum_type {
        ChecksumType::Blake3 => {
            // Reuse existing full hash  --  FREE
            match hash_file_full(path)? {
                Some(h) => Ok(h.to_hex().to_string()),
                None => {
                    // Hashing disabled globally  --  compute anyway for explicit checksum request
                    let mut file = File::open(path)?;
                    let mut hasher = Hasher::new();
                    let mut buf = vec![0u8; CHUNK_SIZE];
                    loop {
                        let n = file.read(&mut buf)?;
                        if n == 0 { break; }
                        hasher.update(&buf[..n]);
                    }
                    Ok(hasher.finalize().to_hex().to_string())
                }
            }
        }
        #[cfg(feature = "checksums")]
        ChecksumType::Sha256 => {
            use sha2::Digest;
            let mut file = File::open(path)?;
            let mut hasher = sha2::Sha256::new();
            let mut buf = vec![0u8; CHUNK_SIZE];
            loop {
                let n = file.read(&mut buf)?;
                if n == 0 { break; }
                hasher.update(&buf[..n]);
            }
            Ok(format!("{:x}", hasher.finalize()))
        }
        #[cfg(feature = "checksums")]
        ChecksumType::Sha1 => {
            use sha1::Digest;
            let mut file = File::open(path)?;
            let mut hasher = sha1::Sha1::new();
            let mut buf = vec![0u8; CHUNK_SIZE];
            loop {
                let n = file.read(&mut buf)?;
                if n == 0 { break; }
                hasher.update(&buf[..n]);
            }
            Ok(format!("{:x}", hasher.finalize()))
        }
        #[cfg(feature = "checksums")]
        ChecksumType::Md5 => {
            use md5::Digest;
            let mut file = File::open(path)?;
            let mut hasher = md5::Md5::new();
            let mut buf = vec![0u8; CHUNK_SIZE];
            loop {
                let n = file.read(&mut buf)?;
                if n == 0 { break; }
                hasher.update(&buf[..n]);
            }
            Ok(format!("{:x}", hasher.finalize()))
        }
    }
}

/// Write checksum sidecar files next to a destination file.
/// Format: GNU coreutils-compatible `<hash>  <filename>\n`
/// When `cid_format` is true and checksum type is BLAKE3, outputs CID base32lower instead of hex.
pub fn write_checksum_files(dst: &Path, types: &[ChecksumType], overwrite: bool, cid_format: bool) -> Result<()> {
    let filename = match dst.file_name() {
        Some(f) => f.to_string_lossy(),
        None => return Ok(()),
    };
    for ct in types {
        let hex = hash_file_checksum(dst, *ct)?;
        let hash_str = if cid_format && *ct == ChecksumType::Blake3 {
            crate::cid::blake3_hex_to_cid_string(&hex).unwrap_or(hex)
        } else {
            hex
        };
        let ext = ct.extension();
        let sidecar = dst.with_file_name(format!("{}.{}", filename, ext));
        if !overwrite && sidecar.exists() { continue; }
        std::fs::write(&sidecar, format!("{}  {}\n", hash_str, filename))
            .map_err(FxcpError::Io)?;
    }
    Ok(())
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod hashing_tests {
    use super::*;
    use tempfile::TempDir;

    #[test]
    fn test_hash_file_lite_on_small_file() {
        set_hashing_enabled(true);
        let dir = TempDir::new().unwrap();
        let path = dir.path().join("test.bin");
        let data = vec![0xABu8; 1024];
        std::fs::write(&path, &data).unwrap();

        // 1KB file with threshold at 1024 -> size < threshold returns None
        let result = hash_file_lite(&path, 1024).unwrap();
        assert!(result.is_none());

        // Lower threshold so the file qualifies
        set_lite_threshold_kb(0);
        let hash1 = hash_file_lite(&path, 1024).unwrap().unwrap();
        let hash2 = hash_file_lite(&path, 1024).unwrap().unwrap();
        assert_eq!(hash1, hash2);

        // Different content -> different hash
        let path2 = dir.path().join("test2.bin");
        std::fs::write(&path2, vec![0xCDu8; 1024]).unwrap();
        let hash3 = hash_file_lite(&path2, 1024).unwrap().unwrap();
        assert_ne!(hash1, hash3);

        // Restore default
        set_lite_threshold_kb(128);
    }

    #[test]
    fn test_compute_dir_hash_deterministic() {
        let entry_hash_a = *blake3::hash(b"entry_a").as_bytes();
        let entry_hash_b = *blake3::hash(b"entry_b").as_bytes();

        let mut children1 = vec![
            ("alpha".to_string(), entry_hash_a),
            ("beta".to_string(), entry_hash_b),
        ];
        let hash1 = compute_dir_hash(&mut children1);

        // Same entries in different order -> same hash (sorted internally)
        let mut children2 = vec![
            ("beta".to_string(), entry_hash_b),
            ("alpha".to_string(), entry_hash_a),
        ];
        let hash2 = compute_dir_hash(&mut children2);
        assert_eq!(hash1, hash2);

        // Different entries -> different hash
        let mut children3 = vec![
            ("alpha".to_string(), entry_hash_a),
            ("gamma".to_string(), entry_hash_b),
        ];
        let hash3 = compute_dir_hash(&mut children3);
        assert_ne!(hash1, hash3);
    }

    #[test]
    fn test_merkle_signature_roundtrip() {
        let chunk_a = blake3::hash(b"chunk_a");
        let chunk_b = blake3::hash(b"chunk_b");
        let chunk_c = blake3::hash(b"chunk_c");

        let leaves = vec![
            ChunkHash { offset: 0, length: 65536, hash: chunk_a, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
            ChunkHash { offset: 65536, length: 65536, hash: chunk_b, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
            ChunkHash { offset: 131072, length: 65536, hash: chunk_c, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
        ];
        let root = MerkleTree::compute_root(&leaves);
        let tree = MerkleTree {
            chunk_size: 65536,
            file_size: 65536 * 3,
            root,
            leaves,
        };

        let sig = tree.to_signature();
        assert_eq!(sig.root, *tree.root.as_bytes());
        assert_eq!(sig.file_size, 65536 * 3);
        assert_eq!(sig.chunk_size, 65536);
        assert_eq!(sig.leaf_hashes.len(), 3);

        let reconstructed = MerkleTree::from_signature(&sig).unwrap();
        assert_eq!(*reconstructed.root.as_bytes(), sig.root);
        assert_eq!(reconstructed.leaves.len(), 3);
        assert_eq!(reconstructed.file_size, 65536 * 3);
    }

    #[test]
    fn test_merkle_diff_detects_changed_chunk() {
        let hash_a = blake3::hash(b"chunk_data_a");
        let hash_b = blake3::hash(b"chunk_data_b");
        let hash_same = blake3::hash(b"chunk_same");

        let source = MerkleTree {
            chunk_size: 65536,
            file_size: 65536 * 3,
            root: blake3::hash(b"source_root"),
            leaves: vec![
                ChunkHash { offset: 0, length: 65536, hash: hash_a, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
                ChunkHash { offset: 65536, length: 65536, hash: hash_same, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
                ChunkHash { offset: 131072, length: 65536, hash: hash_same, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
            ],
        };
        let target_identical = MerkleTree {
            chunk_size: 65536,
            file_size: 65536 * 3,
            root: blake3::hash(b"target_root"),
            leaves: vec![
                ChunkHash { offset: 0, length: 65536, hash: hash_a, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
                ChunkHash { offset: 65536, length: 65536, hash: hash_same, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
                ChunkHash { offset: 131072, length: 65536, hash: hash_same, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
            ],
        };
        assert!(MerkleTree::diff(&source, &target_identical).is_empty());

        let target_modified = MerkleTree {
            chunk_size: 65536,
            file_size: 65536 * 3,
            root: blake3::hash(b"modified_root"),
            leaves: vec![
                ChunkHash { offset: 0, length: 65536, hash: hash_b, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
                ChunkHash { offset: 65536, length: 65536, hash: hash_same, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
                ChunkHash { offset: 131072, length: 65536, hash: hash_same, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
            ],
        };
        let diff = MerkleTree::diff(&source, &target_modified);
        assert_eq!(diff.len(), 1);
        assert_eq!(diff[0].offset, 0);
        assert_eq!(diff[0].length, 65536);
    }

    #[test]
    fn test_merkle_signature_fits_in_xattr() {
        let small_sig = MerkleSignature {
            root: [0u8; 32],
            chunk_size: 65536,
            file_size: 65536,
            leaf_hashes: vec![[0u8; 32]; 1],
            chunk_entropies: None,
            chunk_simhashes: None,
        };
        assert!(small_sig.fits_in_xattr());
        // 56 + 1*32 = 88 bytes
        assert_eq!(small_sig.serialized_size(), 88);

        // 2000 leaves: 56 + 2000*32 = 64056 bytes -> exceeds 64KB (65536)
        let large_sig = MerkleSignature {
            root: [0u8; 32],
            chunk_size: 65536,
            file_size: 65536 * 2000,
            leaf_hashes: vec![[0u8; 32]; 2048],
            chunk_entropies: None,
            chunk_simhashes: None,
        };
        // 56 + 2048*32 = 65592 > 65536
        assert!(!large_sig.fits_in_xattr());
    }

    #[test]
    fn test_hash_file_full_consistency() {
        set_hashing_enabled(true);
        let dir = TempDir::new().unwrap();
        let path = dir.path().join("full_hash.bin");
        let data = b"deterministic content for hashing test";
        std::fs::write(&path, data).unwrap();

        let hash1 = hash_file_full(&path).unwrap().unwrap();
        let hash2 = hash_file_full(&path).unwrap().unwrap();
        assert_eq!(hash1, hash2);

        // Matches direct blake3::hash
        let expected = blake3::hash(data);
        assert_eq!(hash1, expected);
    }

    #[test]
    fn test_merkle_from_signature_rejects_invalid() {
        let bad_sig = MerkleSignature {
            root: [0u8; 32],
            chunk_size: 0, // invalid
            file_size: 1024,
            leaf_hashes: vec![[0u8; 32]; 1],
            chunk_entropies: None,
            chunk_simhashes: None,
        };
        assert!(MerkleTree::from_signature(&bad_sig).is_none());
    }

    #[test]
    fn test_entropy_zeros() {
        assert_eq!(shannon_entropy(&[0u8; 1000]), 0.0);
        assert_eq!(shannon_entropy(&[]), 0.0);
    }

    #[test]
    fn test_entropy_random() {
        // Simple LCG pseudo-random generator for deterministic "random" bytes
        let mut buf = vec![0u8; 10000];
        let mut state: u64 = 0xDEAD_BEEF_CAFE_BABE;
        for b in buf.iter_mut() {
            state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            *b = (state >> 33) as u8;
        }
        let e = shannon_entropy(&buf);
        assert!(
            e > 7.9,
            "pseudo-random entropy should be > 7.9, got {e}"
        );
    }

    #[test]
    fn test_entropy_text() {
        let phrase = b"The quick brown fox jumps over the lazy dog ";
        let mut text = Vec::with_capacity(1000);
        while text.len() < 1000 {
            let remaining = 1000 - text.len();
            text.extend_from_slice(&phrase[..remaining.min(phrase.len())]);
        }
        let e = shannon_entropy(&text);
        assert!(
            (4.0..=5.5).contains(&e),
            "English text entropy should be 4.0-5.5, got {e}"
        );
    }

    #[test]
    fn test_entropy_two_symbols() {
        let mut buf = vec![0u8; 1000];
        for (i, b) in buf.iter_mut().enumerate() {
            *b = (i % 2) as u8;
        }
        let e = shannon_entropy(&buf);
        assert!(
            (0.9..=1.1).contains(&e),
            "two-symbol entropy should be ~1.0, got {e}"
        );
    }

    #[test]
    fn test_sparse_merkle_short_read() {
        // Regression test: from_file_sparse must retry read_at in a loop
        // (like the dense path) and set ChunkHash.length to actual bytes read,
        // not the requested chunk_len. Also must propagate I/O errors (no unwrap_or).
        //
        // Strategy: create a 100-byte file but call from_file_sparse with
        // file_size=65536, forcing read_at to return 100 bytes (short read at EOF).
        // Bug: length would be 65536 (requested). Fix: length must be 100 (actual).

        let dir = TempDir::new().unwrap();
        let path = dir.path().join("short_read.bin");

        // Write exactly 100 bytes of known data
        let data = vec![0xABu8; 100];
        std::fs::write(&path, &data).unwrap();

        let file = File::open(&path).unwrap();
        let fake_file_size = MIN_CHUNK_SIZE as u64; // 65536  --  lie about file size
        let chunk_size = MIN_CHUNK_SIZE as u64;

        // Claim the entire range is data (not a hole)
        let data_extents = vec![(0u64, fake_file_size)];

        // from_file_sparse will try to read 65536 bytes from a 100-byte file.
        // read_at at offset 0 returns 100 bytes (short read).
        let tree = MerkleTree::from_file_sparse(
            &file, fake_file_size, chunk_size, &data_extents, ComputeMode::Blake3Only,
        ).unwrap();

        assert_eq!(tree.leaves.len(), 1, "should have exactly 1 chunk");

        // KEY ASSERTION: length must reflect actual bytes read (100),
        // not the requested chunk_len (65536).
        assert_eq!(
            tree.leaves[0].length, 100,
            "ChunkHash.length should be actual bytes read (100), not requested ({})",
            MIN_CHUNK_SIZE
        );

        // Hash must cover exactly the 100 data bytes (buf pre-filled with zeros,
        // then 100 bytes overwritten by read_at)
        let mut expected_buf = vec![0u8; 100];
        expected_buf[..100].copy_from_slice(&data);
        let expected_hash = blake3::hash(&expected_buf);
        assert_eq!(tree.leaves[0].hash, expected_hash, "hash should cover actual read bytes only");
    }

    #[test]
    fn test_dir_hash_accumulator() {
        let mut acc = DirHashAccumulator::new();
        acc.add("photos", "a.jpg", 1000, "abc123");
        acc.add("photos", "b.jpg", 2000, "def456");
        acc.add("docs", "readme.txt", 500, "xyz789");

        let photos_hash = acc.finalize("photos").unwrap();
        let docs_hash = acc.finalize("docs").unwrap();

        assert_ne!(photos_hash, docs_hash);

        // Same input in reversed order -> same hash (sort-order independent)
        let mut acc2 = DirHashAccumulator::new();
        acc2.add("photos", "b.jpg", 2000, "def456");
        acc2.add("photos", "a.jpg", 1000, "abc123");
        let photos_hash2 = acc2.finalize("photos").unwrap();
        assert_eq!(photos_hash, photos_hash2, "Must be sort-order independent");

        // Different hash_str -> different dir hash
        let mut acc3 = DirHashAccumulator::new();
        acc3.add("photos", "a.jpg", 1000, "changed");
        acc3.add("photos", "b.jpg", 2000, "def456");
        let photos_hash3 = acc3.finalize("photos").unwrap();
        assert_ne!(photos_hash, photos_hash3);

        // compute_dir_hash_from_s3_children directly
        let mut children = vec![
            ("a.jpg".to_string(), 1000u64, "abc123".to_string()),
            ("b.jpg".to_string(), 2000u64, "def456".to_string()),
        ];
        let direct = compute_dir_hash_from_s3_children(&mut children);
        assert_eq!(direct, photos_hash);
    }

    #[test]
    fn test_from_signature_detects_corrupted_root() {
        // Build a valid MerkleTree from known leaves
        let chunk_a = blake3::hash(b"chunk_alpha");
        let chunk_b = blake3::hash(b"chunk_beta");
        let leaves = vec![
            ChunkHash { offset: 0, length: 65536, hash: chunk_a, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
            ChunkHash { offset: 65536, length: 65536, hash: chunk_b, entropy: 0.0, #[cfg(feature = "similarity")] simhash: 0, #[cfg(feature = "similarity")] tlsh_digest: None },
        ];
        let root = MerkleTree::compute_root(&leaves);
        let tree = MerkleTree {
            chunk_size: 65536,
            file_size: 65536 * 2,
            root,
            leaves,
        };

        // Get a valid signature, then corrupt the root
        let mut sig = tree.to_signature();
        sig.root[0] ^= 0xFF; // flip one byte

        // from_signature must reject the corrupted root
        assert!(
            MerkleTree::from_signature(&sig).is_none(),
            "from_signature must return None when root hash does not match recomputed root"
        );
    }

    #[test]
    fn test_from_signature_valid_roundtrip() {
        let dir = TempDir::new().unwrap();
        let path = dir.path().join("roundtrip.bin");
        let data = vec![0xCDu8; 200 * 1024];
        std::fs::write(&path, &data).unwrap();

        let chunk_size = MIN_CHUNK_SIZE as u64;
        let tree = MerkleTree::from_file(&path, chunk_size, ComputeMode::Blake3Only).unwrap();

        let sig = tree.to_signature();
        let reconstructed = MerkleTree::from_signature(&sig);
        assert!(reconstructed.is_some(), "valid signature must round-trip");

        let reconstructed = reconstructed.unwrap();
        assert_eq!(reconstructed.root, tree.root, "root must match");
        assert_eq!(reconstructed.leaves.len(), tree.leaves.len(), "leaf count must match");
    }

    #[test]
    fn test_dir_hash_empty_is_deterministic() {
        let dir1 = TempDir::new().unwrap();
        let hash1 = compute_dir_hash_from_path(dir1.path());
        assert!(hash1.is_some(), "empty dir must return Some(hash), not None");
        let hash2 = compute_dir_hash_from_path(dir1.path());
        assert_eq!(hash1, hash2, "empty dir hash must be deterministic");
    }

    #[test]
    fn test_dir_hash_empty_vs_populated_differ() {
        let empty_dir = TempDir::new().unwrap();
        let populated_dir = TempDir::new().unwrap();
        std::fs::write(populated_dir.path().join("file.txt"), b"content").unwrap();

        let empty_hash = compute_dir_hash_from_path(empty_dir.path());
        let populated_hash = compute_dir_hash_from_path(populated_dir.path());

        assert!(empty_hash.is_some(), "empty dir must return Some");
        assert!(populated_hash.is_some(), "populated dir must return Some");
        assert_ne!(empty_hash, populated_hash, "empty and populated dir hashes must differ");
    }

    #[test]
    fn test_dir_hash_skips_bad_entries() {
        let dir = TempDir::new().unwrap();
        std::fs::write(dir.path().join("a.txt"), b"hello").unwrap();
        std::fs::write(dir.path().join("b.txt"), b"world").unwrap();
        let hash = compute_dir_hash_from_path(dir.path());
        assert!(hash.is_some(), "dir hash must succeed on readable directory");

        // Nonexistent dir returns None (logged, not panicked)
        let bad = std::path::PathBuf::from("/tmp/foxing_nonexistent_dir_test_12345");
        let hash_bad = compute_dir_hash_from_path(&bad);
        assert!(hash_bad.is_none(), "nonexistent dir must return None");
    }

    #[test]
    fn test_merkle_signature_backward_compat_deserialize() {
        let old_json = r#"{
            "root": [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            "chunk_size": 65536,
            "file_size": 131072,
            "leaf_hashes": [
                [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32],
                [32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
            ]
        }"#;
        let sig: MerkleSignature = serde_json::from_str(old_json)
            .expect("old MerkleSignature without optional vectors must deserialize");
        assert_eq!(sig.leaf_hashes.len(), 2);
        assert!(sig.chunk_entropies.is_none(), "missing field must default to None");
        assert!(sig.chunk_simhashes.is_none(), "missing field must default to None");

        let reserialized = serde_json::to_string(&sig).unwrap();
        let sig2: MerkleSignature = serde_json::from_str(&reserialized).unwrap();
        assert_eq!(sig2.leaf_hashes, sig.leaf_hashes);
    }

    #[test]
    fn test_merkle_signature_fat_xattr_size() {
        let leaf_count = crate::constants::MAX_LEAVES_PER_XATTR as usize;
        let sig = MerkleSignature {
            root: [0u8; 32],
            chunk_size: 65536,
            file_size: leaf_count as u64 * 65536,
            leaf_hashes: vec![[0u8; 32]; leaf_count],
            chunk_entropies: Some(vec![0.0f32; leaf_count]),
            chunk_simhashes: Some(vec![0u64; leaf_count]),
        };
        assert!(
            sig.serialized_size() <= crate::constants::MERKLE_XATTR_MAX_BYTES,
            "fat signature with {} leaves ({} bytes) must fit in 64KB xattr",
            leaf_count, sig.serialized_size()
        );

        let one_more = MerkleSignature {
            root: [0u8; 32],
            chunk_size: 65536,
            file_size: (leaf_count + 1) as u64 * 65536,
            leaf_hashes: vec![[0u8; 32]; leaf_count + 1],
            chunk_entropies: Some(vec![0.0f32; leaf_count + 1]),
            chunk_simhashes: Some(vec![0u64; leaf_count + 1]),
        };
        assert!(
            one_more.serialized_size() > crate::constants::MERKLE_XATTR_MAX_BYTES,
            "fat signature with {} leaves must exceed 64KB xattr",
            leaf_count + 1
        );
    }

    #[test]
    fn test_entropy_from_file_zeros() {
        let dir = TempDir::new().unwrap();
        let path = dir.path().join("zeros.bin");
        let data = vec![0u8; 1024 * 1024]; // 1MB of zeros
        std::fs::write(&path, &data).unwrap();

        let tree = MerkleTree::from_file(&path, MIN_CHUNK_SIZE as u64, ComputeMode::WithEntropy).unwrap();
        assert!(!tree.leaves.is_empty());
        for (i, chunk) in tree.leaves.iter().enumerate() {
            assert_eq!(
                chunk.entropy, 0.0,
                "chunk {i} of all-zeros file should have entropy 0.0, got {}",
                chunk.entropy
            );
        }
    }

    #[test]
    fn test_entropy_from_file_random() {
        let dir = TempDir::new().unwrap();
        let path = dir.path().join("random.bin");
        // LCG pseudo-random for deterministic test
        let mut buf = vec![0u8; 1024 * 1024]; // 1MB
        let mut state: u64 = 0xDEAD_BEEF_CAFE_BABE;
        for b in buf.iter_mut() {
            state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            *b = (state >> 33) as u8;
        }
        std::fs::write(&path, &buf).unwrap();

        let tree = MerkleTree::from_file(&path, MIN_CHUNK_SIZE as u64, ComputeMode::WithEntropy).unwrap();
        assert!(!tree.leaves.is_empty());
        for (i, chunk) in tree.leaves.iter().enumerate() {
            assert!(
                chunk.entropy > 7.9,
                "chunk {i} of random file should have entropy > 7.9, got {}",
                chunk.entropy
            );
        }
    }

    #[test]
    fn test_entropy_from_file_blake3only() {
        let dir = TempDir::new().unwrap();
        let path = dir.path().join("blake3only.bin");
        // Mix of data  --  entropy would be non-zero if computed
        let mut buf = vec![0u8; 1024 * 1024];
        let mut state: u64 = 0x1234_5678_9ABC_DEF0;
        for b in buf.iter_mut() {
            state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            *b = (state >> 33) as u8;
        }
        std::fs::write(&path, &buf).unwrap();

        let tree = MerkleTree::from_file(&path, MIN_CHUNK_SIZE as u64, ComputeMode::Blake3Only).unwrap();
        assert!(!tree.leaves.is_empty());
        for (i, chunk) in tree.leaves.iter().enumerate() {
            assert_eq!(
                chunk.entropy, 0.0,
                "chunk {i} in Blake3Only mode must have entropy 0.0, got {}",
                chunk.entropy
            );
        }
    }

    #[test]
    fn test_entropy_from_file_text() {
        let dir = TempDir::new().unwrap();
        let path = dir.path().join("text.bin");
        let phrase = b"The quick brown fox jumps over the lazy dog. ";
        let mut text = Vec::with_capacity(MIN_CHUNK_SIZE + 100);
        while text.len() < MIN_CHUNK_SIZE + 100 {
            let remaining = MIN_CHUNK_SIZE + 100 - text.len();
            text.extend_from_slice(&phrase[..remaining.min(phrase.len())]);
        }
        std::fs::write(&path, &text).unwrap();

        let tree = MerkleTree::from_file(&path, MIN_CHUNK_SIZE as u64, ComputeMode::WithEntropy).unwrap();
        assert!(!tree.leaves.is_empty());
        // At least the first full chunk should have English text entropy
        let e = tree.leaves[0].entropy;
        assert!(
            (4.0..=5.5).contains(&e),
            "English text chunk entropy should be 4.0-5.5, got {e}"
        );
    }

    #[test]
    #[ignore] // Benchmark: run with `cargo test -- --ignored`
    fn test_entropy_benchmark_overhead() {
        let dir = TempDir::new().unwrap();
        let path = dir.path().join("bench.bin");
        // 100MB pseudo-random file
        let mut buf = vec![0u8; 100 * 1024 * 1024];
        let mut state: u64 = 0xCAFE_BABE_DEAD_BEEF;
        for b in buf.iter_mut() {
            state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            *b = (state >> 33) as u8;
        }
        std::fs::write(&path, &buf).unwrap();

        let chunk_size = MIN_CHUNK_SIZE as u64;
        let runs = 10;

        // Warm up
        let _ = MerkleTree::from_file(&path, chunk_size, ComputeMode::Blake3Only).unwrap();
        let _ = MerkleTree::from_file(&path, chunk_size, ComputeMode::WithEntropy).unwrap();

        let start_blake3 = std::time::Instant::now();
        for _ in 0..runs {
            let _ = MerkleTree::from_file(&path, chunk_size, ComputeMode::Blake3Only).unwrap();
        }
        let elapsed_blake3 = start_blake3.elapsed();

        let start_entropy = std::time::Instant::now();
        for _ in 0..runs {
            let _ = MerkleTree::from_file(&path, chunk_size, ComputeMode::WithEntropy).unwrap();
        }
        let elapsed_entropy = start_entropy.elapsed();

        let ratio = elapsed_entropy.as_secs_f64() / elapsed_blake3.as_secs_f64();
        eprintln!(
            "Blake3Only: {:.1}ms, WithEntropy: {:.1}ms, ratio: {:.3}x",
            elapsed_blake3.as_secs_f64() * 1000.0 / runs as f64,
            elapsed_entropy.as_secs_f64() * 1000.0 / runs as f64,
            ratio
        );
        assert!(
            ratio < 1.20,
            "WithEntropy overhead must be < 20% vs Blake3Only, got {:.1}%",
            (ratio - 1.0) * 100.0
        );
    }

    #[cfg(feature = "similarity")]
    #[test]
    fn test_simhash_identical_files() {
        let dir = tempfile::tempdir().unwrap();
        // Use pseudo-random data so each chunk has a unique simhash (avoids XOR cancellation)
        let mut data = vec![0u8; 200_000];
        let mut state: u64 = 0xDEAD_BEEF_CAFE_1234;
        for b in data.iter_mut() {
            state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            *b = (state >> 33) as u8;
        }

        let path_a = dir.path().join("a.bin");
        let path_b = dir.path().join("b.bin");
        std::fs::write(&path_a, &data).unwrap();
        std::fs::write(&path_b, &data).unwrap();

        let tree_a = MerkleTree::from_file(&path_a, MIN_CHUNK_SIZE as u64, ComputeMode::WithSimilarity).unwrap();
        let tree_b = MerkleTree::from_file(&path_b, MIN_CHUNK_SIZE as u64, ComputeMode::WithSimilarity).unwrap();

        assert!(tree_a.leaves.iter().any(|c| c.simhash != 0), "at least one chunk should have non-zero simhash");
        assert_eq!(tree_a.file_simhash(), tree_b.file_simhash(), "identical files must have identical simhash");
    }

    #[cfg(feature = "similarity")]
    #[test]
    fn test_simhash_near_identical() {
        let dir = tempfile::tempdir().unwrap();
        let mut data = vec![0u8; 200_000];
        let mut state: u64 = 0xDEAD_BEEF_CAFE_1234;
        for b in data.iter_mut() {
            state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            *b = (state >> 33) as u8;
        }

        let path_a = dir.path().join("a.bin");
        std::fs::write(&path_a, &data).unwrap();

        data[1000] ^= 0xFF;
        let path_b = dir.path().join("b.bin");
        std::fs::write(&path_b, &data).unwrap();

        let tree_a = MerkleTree::from_file(&path_a, MIN_CHUNK_SIZE as u64, ComputeMode::WithSimilarity).unwrap();
        let tree_b = MerkleTree::from_file(&path_b, MIN_CHUNK_SIZE as u64, ComputeMode::WithSimilarity).unwrap();

        let dist = crate::similarity::hamming_distance(tree_a.file_simhash(), tree_b.file_simhash());
        assert!(
            dist < 10,
            "1-byte difference should yield hamming_distance < 10, got {}",
            dist
        );
    }

    #[cfg(feature = "similarity")]
    #[test]
    fn test_simhash_blake3only_zero() {
        let dir = tempfile::tempdir().unwrap();
        let data = b"Some test data for Blake3Only mode checking".repeat(3000);
        let path = dir.path().join("test.bin");
        std::fs::write(&path, &data).unwrap();

        let tree = MerkleTree::from_file(&path, MIN_CHUNK_SIZE as u64, ComputeMode::Blake3Only).unwrap();

        for chunk in &tree.leaves {
            assert_eq!(chunk.simhash, 0, "Blake3Only mode must leave simhash as 0");
        }
        assert_eq!(tree.file_simhash(), 0, "file_simhash must be 0 in Blake3Only mode");
    }
}