grit_lib/hash/

mod.rs

//! Incremental hashing for Git object ids and file checksums.
//!
//! Parallel batch helpers: [`hash_objects_parallel`], [`par_hash_with`], and [`Parallelism`].
//!
//! This module is the single owner of the `sha1`, `sha2`, and `sha1dc` crates in
//! `grit-lib`.
//!
//! **Object ids** name Git objects. SHA-1 ids are computed with [`sha1dc`] (collision
//! detection, standard digest mode). [`ObjectHasher::finalize`], [`hash_object`], and
//! [`HashAlgo::digest`] return [`Result`] and surface [`Error::HashCollision`] on
//! chosen-prefix collisions. Canonical store bytes are `"<kind> <len>\\0<payload>"`;
//! use [`HashAlgo::digest`] when hashing raw bytes that should become an [`ObjectId`]
//! (for example verifying loose object headers).
//!
//! **Checksums** detect corruption in pack, index, MIDX, commit-graph, and related
//! file trailers. They use the same digest algorithms but are not object identities.
//! Use [`ChecksumHasher`] / [`HashAlgo::checksum_digest`], [`HashingWriter`], and
//! [`verify_trailer`].

#![allow(dead_code)]

use std::io::{self, Write};

use sha1::{Digest as Sha1Digest, Sha1};
use sha1dc::Hasher as Sha1dcHasher;
use sha2::Sha256;

use crate::error::{Error, Result};
use crate::objects::{HashAlgo, ObjectId, ObjectKind};

mod parallel;

pub use parallel::{
    hash_objects_parallel, par_hash_with, parallel_hash_worthwhile, try_par_hash_with,
    try_par_hash_with_force, ParallelHashError, Parallelism, PAR_HASH_MIN_ITEMS,
    PAR_HASH_MIN_TOTAL_BYTES,
};

/// Which implementation the `sha1` / `sha2` dependency selects for `algo` on this CPU.
///
/// Values mirror the `cpufeatures` dispatch inside those crates for the digests
/// Grit uses (SHA-1 and SHA-256). On x86_64, SHA-256 in `sha2` 0.11 only selects
/// SHA-NI or portable code (AVX2 is used for SHA-512, not SHA-256, so there is no
/// separate AVX2 backend variant here).
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Backend {
    /// x86_64 SHA-NI (`sha` target feature) — used for SHA-1 and SHA-256 when available.
    X86ShaNi,
    /// AArch64 SHA2 crypto extensions.
    Aarch64Sha,
    /// Portable software implementation.
    Portable,
}

impl Backend {
    /// Stable lowercase name for scripts and JSON (`x86_sha_ni`, `portable`, …).
    #[must_use]
    pub const fn as_str(self) -> &'static str {
        match self {
            Self::X86ShaNi => "x86_sha_ni",
            Self::Aarch64Sha => "aarch64_sha",
            Self::Portable => "portable",
        }
    }
}

impl std::fmt::Display for Backend {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(self.as_str())
    }
}

/// Report the hashing backend used for object-id digests on this CPU.
///
/// SHA-1 object ids go through [`sha1dc`] (hardware SHA-1 when available). SHA-256
/// uses the `sha2` crate. File checksums use plain accelerated SHA-1 from the `sha1`
/// crate, not sha1dc.
///
/// Detection uses the same target features as those crates (`sha` on x86_64, `sha2` on
/// AArch64). `algo` is accepted for a stable signature; both supported algorithms share
/// the same backend on a given CPU.
#[must_use]
pub fn backend(algo: HashAlgo) -> Backend {
    let _ = algo;
    #[cfg(target_arch = "x86_64")]
    {
        if std::arch::is_x86_feature_detected!("sha") {
            Backend::X86ShaNi
        } else {
            Backend::Portable
        }
    }
    #[cfg(target_arch = "aarch64")]
    {
        if std::arch::is_aarch64_feature_detected!("sha2") {
            Backend::Aarch64Sha
        } else {
            Backend::Portable
        }
    }
    #[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
    {
        Backend::Portable
    }
}
/// Maximum length of a Git object header (`"<kind> <decimal-len>\\0"`) on the stack.
///
/// Longest kind name is `"commit"` (6 bytes) plus space, up to 20 decimal digits
/// for the payload length, plus the trailing NUL.
const OBJECT_HEADER_BUF_LEN: usize = 6 + 1 + 20 + 1;

/// Incremental hasher for Git file checksums (pack/index/MIDX/commit-graph trailers).
///
/// Checksums use the same SHA-1 or SHA-256 digests as object ids but name file
/// integrity, not [`ObjectId`] values. Prefer this type anywhere a trailer or
/// non-object content hash is computed or verified.
#[derive(Debug, Clone)]
pub enum ChecksumHasher {
    /// SHA-1 (20-byte digests).
    Sha1(Sha1),
    /// SHA-256 (32-byte digests).
    Sha256(Sha256),
}

impl ChecksumHasher {
    /// Create a fresh checksum hasher for `algo`.
    #[must_use]
    pub fn new(algo: HashAlgo) -> Self {
        algo.checksum_hasher()
    }

    /// The hash algorithm this hasher produces.
    #[must_use]
    pub fn algo(self: &ChecksumHasher) -> HashAlgo {
        match self {
            Self::Sha1(_) => HashAlgo::Sha1,
            Self::Sha256(_) => HashAlgo::Sha256,
        }
    }

    /// Feed more bytes into the digest.
    pub fn update(&mut self, data: &[u8]) {
        match self {
            Self::Sha1(h) => h.update(data),
            Self::Sha256(h) => h.update(data),
        }
    }

    /// Finish hashing and return the raw digest bytes.
    #[must_use]
    pub fn finalize(self) -> Vec<u8> {
        match self {
            Self::Sha1(h) => h.finalize().to_vec(),
            Self::Sha256(h) => h.finalize().to_vec(),
        }
    }

    /// Write the raw digest into `out` and return the number of bytes written.
    ///
    /// # Panics
    ///
    /// Panics when `out` is shorter than the digest length for this algorithm.
    #[must_use]
    pub fn finalize_into(self, out: &mut [u8]) -> usize {
        let digest = self.finalize();
        let len = digest.len();
        assert!(
            out.len() >= len,
            "checksum digest buffer too short: need {len} bytes, have {}",
            out.len()
        );
        out[..len].copy_from_slice(&digest);
        len
    }
}

impl Write for ChecksumHasher {
    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
        self.update(buf);
        Ok(buf.len())
    }

    fn flush(&mut self) -> io::Result<()> {
        Ok(())
    }
}

/// Incremental hasher for Git's supported object-id algorithms.
#[derive(Debug, Clone)]
pub enum ObjectHasher {
    /// SHA-1 (20-byte digests) with sha1dc collision detection.
    Sha1(Sha1dcHasher),
    /// SHA-256 (32-byte digests).
    Sha256(Sha256),
}

impl ObjectHasher {
    /// Create a fresh hasher for `algo`.
    #[must_use]
    pub fn new(algo: HashAlgo) -> Self {
        algo.hasher()
    }

    /// The hash algorithm this hasher produces.
    #[must_use]
    pub fn algo(self: &ObjectHasher) -> HashAlgo {
        match self {
            Self::Sha1(_) => HashAlgo::Sha1,
            Self::Sha256(_) => HashAlgo::Sha256,
        }
    }

    /// Feed more bytes into the digest.
    pub fn update(&mut self, data: &[u8]) {
        match self {
            Self::Sha1(h) => h.update(data),
            Self::Sha256(h) => h.update(data),
        }
    }

    /// Create a hasher that already consumed the Git object header for `kind` and `len`.
    ///
    /// The header is written into a stack buffer (no heap allocation).
    #[must_use]
    pub fn for_object(algo: HashAlgo, kind: ObjectKind, len: u64) -> Self {
        let mut hasher = Self::new(algo);
        let mut header = [0u8; OBJECT_HEADER_BUF_LEN];
        let header_len = write_object_header(&mut header, kind, len);
        hasher.update(&header[..header_len]);
        hasher
    }

    /// Finish hashing and return the object id.
    ///
    /// # Errors
    ///
    /// Returns [`Error::HashCollision`] when sha1dc detects a chosen-prefix collision.
    pub fn finalize(self) -> Result<ObjectId> {
        match self {
            Self::Sha1(h) => match h.finalize() {
                Ok(digest) => Ok(object_id_from_sha1_digest(&digest)),
                Err(collision) => Err(collision_to_error(collision)),
            },
            Self::Sha256(h) => Ok(ObjectId::from_bytes(h.finalize().as_slice())
                .unwrap_or_else(|_| unreachable!("SHA-256 digest is 32 bytes"))),
        }
    }

    /// Write the raw digest into `out` and return the number of bytes written.
    ///
    /// # Errors
    ///
    /// Returns [`Error::InvalidObjectId`] when `out` is shorter than the digest
    /// length for this algorithm (a diagnostic string names the required size).
    pub fn finalize_into(self, out: &mut [u8]) -> Result<usize> {
        match self {
            Self::Sha1(h) => {
                let oid = match h.finalize() {
                    Ok(digest) => object_id_from_sha1_digest(&digest),
                    Err(collision) => return Err(collision_to_error(collision)),
                };
                let bytes = oid.as_bytes();
                if out.len() < bytes.len() {
                    return Err(Error::InvalidObjectId(format!(
                        "digest buffer too short: need {} bytes, have {}",
                        bytes.len(),
                        out.len()
                    )));
                }
                out[..bytes.len()].copy_from_slice(bytes);
                Ok(bytes.len())
            }
            Self::Sha256(h) => {
                let digest = h.finalize();
                let len = digest.len();
                if out.len() < len {
                    return Err(Error::InvalidObjectId(format!(
                        "digest buffer too short: need {len} bytes, have {}",
                        out.len()
                    )));
                }
                out[..len].copy_from_slice(&digest);
                Ok(len)
            }
        }
    }
}

impl Write for ObjectHasher {
    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
        self.update(buf);
        Ok(buf.len())
    }

    fn flush(&mut self) -> io::Result<()> {
        Ok(())
    }
}

impl HashAlgo {
    /// Return a fresh incremental checksum hasher for this algorithm.
    #[must_use]
    pub fn checksum_hasher(self) -> ChecksumHasher {
        match self {
            Self::Sha1 => ChecksumHasher::Sha1(Sha1::new()),
            Self::Sha256 => ChecksumHasher::Sha256(Sha256::new()),
        }
    }

    /// Hash a byte slice with no Git object header and return a file checksum.
    #[must_use]
    pub fn checksum_digest(self, data: &[u8]) -> Vec<u8> {
        let mut hasher = self.checksum_hasher();
        hasher.update(data);
        hasher.finalize()
    }

    /// Return a fresh incremental hasher for this algorithm.
    #[must_use]
    pub fn hasher(self) -> ObjectHasher {
        match self {
            Self::Sha1 => ObjectHasher::Sha1(Sha1dcHasher::new()),
            Self::Sha256 => ObjectHasher::Sha256(Sha256::new()),
        }
    }

    /// Hash a byte slice with no Git object header.
    ///
    /// # Errors
    ///
    /// Returns [`Error::HashCollision`] when sha1dc detects a chosen-prefix collision.
    pub fn digest(self, data: &[u8]) -> Result<ObjectId> {
        let mut hasher = self.hasher();
        hasher.update(data);
        hasher.finalize()
    }

    /// Hash canonical Git store bytes for `kind` and `data`.
    ///
    /// # Errors
    ///
    /// Returns [`Error::HashCollision`] when sha1dc detects a chosen-prefix collision.
    pub fn hash_object(self, kind: ObjectKind, data: &[u8]) -> Result<ObjectId> {
        hash_object(self, kind, data)
    }
}

/// Hash canonical Git store bytes for `kind` and `data`.
///
/// Equivalent to [`HashAlgo::hash_object`] but accepts the algorithm as the
/// first argument.
///
/// Detection runs over the bytes that form the object id (header and payload), as in
/// Git. A payload that only collides when hashed on its own, such as the SHAttered
/// PDFs stored as blobs in Git's own history, is an ordinary object.
///
/// # Errors
///
/// Returns [`Error::HashCollision`] when sha1dc detects a chosen-prefix collision.
pub fn hash_object(algo: HashAlgo, kind: ObjectKind, data: &[u8]) -> Result<ObjectId> {
    let len = u64::try_from(data.len()).unwrap_or(u64::MAX);
    let mut hasher = ObjectHasher::for_object(algo, kind, len);
    hasher.update(data);
    hasher.finalize()
}

/// Incremental Git object-id hash (header plus payload chunks).
///
/// Use this instead of constructing [`ObjectHasher`] outside the hash module.
pub struct ObjectPayloadHasher {
    inner: ObjectHasher,
}

impl ObjectPayloadHasher {
    /// Start hashing canonical store bytes for `kind` with payload length `len`.
    #[must_use]
    pub fn new(algo: HashAlgo, kind: ObjectKind, len: u64) -> Self {
        Self {
            inner: ObjectHasher::for_object(algo, kind, len),
        }
    }

    /// Feed more decompressed payload bytes.
    pub fn update(&mut self, chunk: &[u8]) {
        self.inner.update(chunk);
    }

    /// Finish and return the object id.
    ///
    /// # Errors
    ///
    /// Returns [`Error::HashCollision`] when sha1dc detects a chosen-prefix collision.
    pub fn finish(self) -> Result<ObjectId> {
        self.inner.finalize()
    }
}

fn object_id_from_sha1_digest(digest: &sha1dc::Digest) -> ObjectId {
    ObjectId::from_bytes(digest.as_ref())
        .unwrap_or_else(|_| unreachable!("SHA-1 digest is 20 bytes"))
}

fn collision_to_error(collision: sha1dc::Collision) -> Error {
    Error::HashCollision {
        oid: object_id_from_sha1_digest(&collision.digest()),
    }
}

/// A writer that forwards bytes to an inner sink while accumulating a checksum.
///
/// Call [`Self::finish`] to append the raw digest trailer to the inner writer
/// and obtain the digest as an [`ObjectId`].
pub struct HashingWriter<W: Write> {
    inner: W,
    hasher: ChecksumHasher,
}

impl<W: Write> HashingWriter<W> {
    /// Wrap `inner`, hashing every byte written through this adapter.
    #[must_use]
    pub fn new(algo: HashAlgo, inner: W) -> Self {
        Self {
            inner,
            hasher: algo.checksum_hasher(),
        }
    }

    /// Borrow the inner writer without finishing the checksum.
    #[must_use]
    pub fn get_ref(&self) -> &W {
        &self.inner
    }

    /// Mutably borrow the inner writer without finishing the checksum.
    pub fn get_mut(&mut self) -> &mut W {
        &mut self.inner
    }

    /// Append the checksum trailer to the inner writer and return it with the digest.
    ///
    /// # Errors
    ///
    /// Propagates I/O errors from writing the trailer to `inner`.
    pub fn finish(mut self) -> io::Result<(W, ObjectId)> {
        let digest_bytes = self.hasher.finalize();
        self.inner.write_all(&digest_bytes)?;
        let digest = ObjectId::from_bytes(&digest_bytes)
            .unwrap_or_else(|_| unreachable!("checksum digest length matches object id for algo"));
        Ok((self.inner, digest))
    }
}

impl<W: Write> Write for HashingWriter<W> {
    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
        let n = self.inner.write(buf)?;
        if n > 0 {
            self.hasher.update(&buf[..n]);
        }
        Ok(n)
    }

    fn flush(&mut self) -> io::Result<()> {
        self.inner.flush()
    }
}

/// Checksum at the end of `bytes` did not match a digest of the leading body.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TrailerMismatch {
    /// Digest computed over the body (everything before the trailer).
    pub expected: Vec<u8>,
    /// Trailing bytes found in `bytes`.
    pub found: Vec<u8>,
}

impl std::fmt::Display for TrailerMismatch {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "trailer checksum mismatch (expected {}, found {})",
            hex::encode(&self.expected),
            hex::encode(&self.found)
        )
    }
}

impl std::error::Error for TrailerMismatch {}

/// Verify that `bytes` ends with the hash of the preceding body.
///
/// # Errors
///
/// Returns [`TrailerMismatch`] when the trailer does not match, or when `bytes`
/// is shorter than one digest for `algo`.
pub fn verify_trailer(algo: HashAlgo, bytes: &[u8]) -> std::result::Result<(), TrailerMismatch> {
    let trailer_len = algo.len();
    if bytes.len() < trailer_len {
        return Err(TrailerMismatch {
            expected: Vec::new(),
            found: bytes.to_vec(),
        });
    }
    let split = bytes.len() - trailer_len;
    let (body, trailer) = bytes.split_at(split);
    let expected = algo.checksum_digest(body);
    if expected.as_slice() == trailer {
        Ok(())
    } else {
        Err(TrailerMismatch {
            expected,
            found: trailer.to_vec(),
        })
    }
}

/// Write `"<kind> <len>\\0"` into `buf` and return the number of bytes used.
fn write_object_header(buf: &mut [u8], kind: ObjectKind, len: u64) -> usize {
    let kind_bytes = kind.as_str().as_bytes();
    let mut pos = 0;
    buf[pos..pos + kind_bytes.len()].copy_from_slice(kind_bytes);
    pos += kind_bytes.len();
    buf[pos] = b' ';
    pos += 1;
    pos += write_decimal(&mut buf[pos..], len);
    buf[pos] = 0;
    pos + 1
}

fn write_decimal(out: &mut [u8], mut n: u64) -> usize {
    if n == 0 {
        out[0] = b'0';
        return 1;
    }
    let mut tmp = [0u8; 20];
    let mut digits = 0usize;
    while n > 0 {
        tmp[digits] = b'0' + (n % 10) as u8;
        digits += 1;
        n /= 10;
    }
    for i in 0..digits {
        out[i] = tmp[digits - 1 - i];
    }
    digits
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Cursor;

    fn hex_oid(_algo: HashAlgo, hex: &str) -> ObjectId {
        ObjectId::from_hex(hex).expect("test vector hex")
    }

    fn assert_digest(algo: HashAlgo, data: &[u8], expected_hex: &str) {
        let got = algo.digest(data).expect("digest");
        assert_eq!(got, hex_oid(algo, expected_hex), "digest mismatch");
    }

    fn assert_checksum_digest(algo: HashAlgo, data: &[u8], expected_hex: &str) {
        let got = algo.checksum_digest(data);
        assert_eq!(hex::encode(&got), expected_hex, "checksum digest mismatch");
    }

    #[test]
    fn checksum_hasher_nist_vectors_sha1_sha256() {
        assert_checksum_digest(
            HashAlgo::Sha1,
            b"",
            "da39a3ee5e6b4b0d3255bfef95601890afd80709",
        );
        assert_checksum_digest(
            HashAlgo::Sha1,
            b"abc",
            "a9993e364706816aba3e25717850c26c9cd0d89d",
        );
        assert_checksum_digest(
            HashAlgo::Sha256,
            b"",
            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
        );
        assert_checksum_digest(
            HashAlgo::Sha256,
            b"abc",
            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad",
        );
    }

    #[test]
    fn checksum_hasher_matches_object_hasher_digest() {
        let data: Vec<u8> = (0..512).map(|i| (i % 251) as u8).collect();
        for algo in [HashAlgo::Sha1, HashAlgo::Sha256] {
            let mut checksum = algo.checksum_hasher();
            checksum.update(&data);
            let checksum_bytes = checksum.finalize();
            assert_eq!(
                checksum_bytes,
                algo.digest(&data).expect("digest").as_bytes()
            );
        }
    }

    #[test]
    fn hashing_writer_uses_checksum_hasher() {
        let body = b"streaming checksum body";
        let mut buf = Vec::new();
        {
            let mut w = HashingWriter::new(HashAlgo::Sha256, Cursor::new(&mut buf));
            w.write_all(body).unwrap();
            let (_, digest) = w.finish().unwrap();
            assert_eq!(
                digest.as_bytes(),
                HashAlgo::Sha256.checksum_digest(body).as_slice()
            );
        }
        verify_trailer(HashAlgo::Sha256, &buf).expect("trailer valid");
    }

    #[test]
    fn sha1_nist_vectors() {
        assert_digest(
            HashAlgo::Sha1,
            b"",
            "da39a3ee5e6b4b0d3255bfef95601890afd80709",
        );
        assert_digest(
            HashAlgo::Sha1,
            b"abc",
            "a9993e364706816aba3e25717850c26c9cd0d89d",
        );
        assert_digest(
            HashAlgo::Sha1,
            b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
            "84983e441c3bd26ebaae4aa1f95129e5e54670f1",
        );
        let million_a = vec![b'a'; 1_000_000];
        assert_digest(
            HashAlgo::Sha1,
            &million_a,
            "34aa973cd4c4daa4f61eeb2bdbad27316534016f",
        );
    }

    #[test]
    fn sha256_nist_vectors() {
        assert_digest(
            HashAlgo::Sha256,
            b"",
            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
        );
        assert_digest(
            HashAlgo::Sha256,
            b"abc",
            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad",
        );
        assert_digest(
            HashAlgo::Sha256,
            b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
            "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1",
        );
        let million_a = vec![b'a'; 1_000_000];
        assert_digest(
            HashAlgo::Sha256,
            &million_a,
            "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0",
        );
    }

    #[test]
    fn incremental_matches_oneshot_random_splits() {
        let data: Vec<u8> = (0..4096).map(|i| (i % 251) as u8).collect();
        for algo in [HashAlgo::Sha1, HashAlgo::Sha256] {
            let oneshot = algo.digest(&data).expect("digest");
            let mut state = 0xdead_beef_u64;
            let mut pos = 0usize;
            let mut hasher = algo.hasher();
            while pos < data.len() {
                state = state
                    .wrapping_mul(6364136223846793005)
                    .wrapping_add(1442695040888963407);
                let remaining = data.len() - pos;
                let chunk = if remaining == 1 {
                    1
                } else {
                    (state as usize % remaining).max(1)
                };
                hasher.update(&data[pos..pos + chunk]);
                pos += chunk;
            }
            assert_eq!(hasher.finalize().expect("finalize"), oneshot);
        }
    }

    #[test]
    fn object_header_encoding() {
        let kinds = [
            (ObjectKind::Blob, "blob"),
            (ObjectKind::Tree, "tree"),
            (ObjectKind::Commit, "commit"),
            (ObjectKind::Tag, "tag"),
        ];
        let lens = [0_u64, 1, 4_294_967_297];
        let cases: Vec<(ObjectKind, u64, String)> = kinds
            .iter()
            .flat_map(|&(kind, name)| {
                lens.iter()
                    .map(move |&len| (kind, len, format!("{name} {len}\0")))
            })
            .collect();
        for (kind, len, expect) in &cases {
            let mut buf = [0u8; OBJECT_HEADER_BUF_LEN];
            let n = write_object_header(&mut buf, *kind, *len);
            assert_eq!(
                &buf[..n],
                expect.as_bytes(),
                "header for {kind:?} len {len}"
            );
        }
    }

    #[test]
    fn hash_object_all_kinds() {
        for kind in [
            ObjectKind::Blob,
            ObjectKind::Tree,
            ObjectKind::Commit,
            ObjectKind::Tag,
        ] {
            for payload in [b"" as &[u8], b"x"] {
                let mut hasher =
                    ObjectHasher::for_object(HashAlgo::Sha1, kind, payload.len() as u64);
                hasher.update(payload);
                assert_eq!(
                    hash_object(HashAlgo::Sha1, kind, payload).expect("hash"),
                    hasher.finalize().expect("finalize")
                );
            }
        }
    }

    /// Inner writer that accepts at most `max` bytes per `write` call.
    struct PartialWrite {
        max: usize,
        buf: Vec<u8>,
        fail: bool,
    }

    impl Write for PartialWrite {
        fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
            if self.fail {
                return Err(io::Error::new(
                    io::ErrorKind::Other,
                    "simulated write failure",
                ));
            }
            let n = buf.len().min(self.max);
            self.buf.extend_from_slice(&buf[..n]);
            Ok(n)
        }

        fn flush(&mut self) -> io::Result<()> {
            Ok(())
        }
    }

    #[test]
    fn hashing_writer_partial_write_checksum() {
        let inner = PartialWrite {
            max: 2,
            buf: Vec::new(),
            fail: false,
        };
        let mut w = HashingWriter::new(HashAlgo::Sha1, inner);
        let n = w.write(b"abcdef").expect("write");
        assert_eq!(n, 2);
        assert_eq!(w.get_ref().buf, b"ab");
        let (_, digest) = w.finish().expect("finish");
        assert_eq!(
            digest.as_bytes(),
            HashAlgo::Sha1.checksum_digest(b"ab").as_slice()
        );
        assert_ne!(
            digest.as_bytes(),
            HashAlgo::Sha1.checksum_digest(b"abcdef").as_slice()
        );
    }

    #[test]
    fn hashing_writer_write_error_does_not_update_checksum() {
        let inner = PartialWrite {
            max: 64,
            buf: Vec::new(),
            fail: true,
        };
        let mut w = HashingWriter::new(HashAlgo::Sha1, inner);
        assert!(w.write(b"abcdef").is_err());
        w.get_mut().fail = false;
        w.write_all(b"ab").expect("write");
        let (_, digest) = w.finish().expect("finish");
        assert_eq!(
            digest.as_bytes(),
            HashAlgo::Sha1.checksum_digest(b"ab").as_slice()
        );
    }

    #[test]
    fn hashing_writer_trailer_matches_digest() {
        let body = b"index payload bytes";
        let mut buf = Vec::new();
        {
            let mut w = HashingWriter::new(HashAlgo::Sha1, Cursor::new(&mut buf));
            w.write_all(body).unwrap();
            let (_, digest) = w.finish().unwrap();
            assert_eq!(
                digest.as_bytes(),
                HashAlgo::Sha1.checksum_digest(body).as_slice()
            );
            assert_eq!(&buf[body.len()..], digest.as_bytes());
        }
        verify_trailer(HashAlgo::Sha1, &buf).expect("trailer valid");
    }

    #[test]
    fn verify_trailer_mismatch_is_typed() {
        let body = b"payload";
        let mut file = body.to_vec();
        file.extend_from_slice(&[0u8; 20]);
        let err = verify_trailer(HashAlgo::Sha1, &file).unwrap_err();
        assert!(matches!(err, TrailerMismatch { .. }));
        assert_ne!(err.expected, err.found);
    }

    #[test]
    fn finalize_into_and_write_trait() {
        let mut hasher = HashAlgo::Sha256.hasher();
        hasher.write_all(b"via write trait").unwrap();
        let mut out = [0u8; 32];
        let n = hasher.finalize_into(&mut out).unwrap();
        assert_eq!(n, 32);
        assert_eq!(
            HashAlgo::Sha256.digest(b"via write trait").expect("digest"),
            ObjectId::from_bytes(&out).unwrap()
        );
    }

    #[test]
    fn backend_matches_cpu() {
        let expected = {
            #[cfg(target_arch = "x86_64")]
            {
                if std::arch::is_x86_feature_detected!("sha") {
                    Backend::X86ShaNi
                } else {
                    Backend::Portable
                }
            }
            #[cfg(target_arch = "aarch64")]
            {
                if std::arch::is_aarch64_feature_detected!("sha2") {
                    Backend::Aarch64Sha
                } else {
                    Backend::Portable
                }
            }
            #[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
            {
                Backend::Portable
            }
        };
        assert_eq!(super::backend(HashAlgo::Sha1), expected);
    }

    #[test]
    fn sha1_object_hasher_matches_sha1_crate_random() {
        let mut state = 0x9e37_79b9_u64;
        for len in [0_usize, 1, 63, 64, 65, 127, 128, 129, 512, 4096, 8192] {
            let mut data = vec![0_u8; len];
            for b in &mut data {
                state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
                *b = (state >> 32) as u8;
            }
            let mut plain = Sha1::new();
            plain.update(&data);
            let expected = plain.finalize();
            let mut hasher = ObjectHasher::new(HashAlgo::Sha1);
            hasher.update(&data);
            assert_eq!(
                hasher.finalize().expect("finalize").as_bytes(),
                expected.as_slice(),
                "len {len}"
            );
        }
    }

    #[test]
    fn finalize_detects_shattered_prefix() {
        let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("tests/data");
        for name in ["shattered-1-prefix.bin", "shattered-2-prefix.bin"] {
            let bytes = std::fs::read(dir.join(name)).expect("fixture");
            let mut hasher = ObjectHasher::new(HashAlgo::Sha1);
            hasher.update(&bytes);
            let err = hasher.finalize().expect_err("SHAttered block must collide");
            assert!(matches!(err, Error::HashCollision { .. }));
            assert!(matches!(
                HashAlgo::Sha1.digest(&bytes),
                Err(Error::HashCollision { .. })
            ));

            // As a blob, the header shifts the colliding blocks: the object id is an
            // ordinary SHA-1, exactly what Git computes for these files.
            let mut plain = Sha1::new();
            plain.update(format!("blob {}\0", bytes.len()).as_bytes());
            plain.update(&bytes);
            let oid = hash_object(HashAlgo::Sha1, ObjectKind::Blob, &bytes)
                .expect("blob holding a SHAttered prefix is not a collision");
            assert_eq!(oid.as_bytes(), plain.finalize().as_slice());
        }
    }

    #[test]
    fn sha256_finalize_never_collides() {
        let data: Vec<u8> = (0..1024).map(|i| (i % 251) as u8).collect();
        let mut hasher = ObjectHasher::new(HashAlgo::Sha256);
        hasher.update(&data);
        hasher
            .finalize()
            .expect("SHA-256 has no collision detection");
    }

    #[test]
    fn sha256_backend_matches_sha2_dispatcher() {
        #[cfg(target_arch = "x86_64")]
        {
            let got = super::backend(HashAlgo::Sha256);
            if std::arch::is_x86_feature_detected!("sha") {
                assert_eq!(got, Backend::X86ShaNi);
            } else {
                assert_eq!(got, Backend::Portable);
            }
        }
    }
}